Ctrl+K

Iverson 括弧

8. Iverson 括弧#

8.1. 導入#

Iverson 括弧もしくは Iverson の記法とは次に定義するもので，Kenneth Eugene Iverson が考案した．

(1)#\[\begin{split}[P] := \begin{cases} 1 & (P ~ \text{is true}), \\ 0 & (\text{otherwise}) \end{cases}\end{split}\]

\(P\) は命題論理式であり真偽の判定ができるものを想定する．

8.2. 基本公式#

命題論理式 \(P,Q\) について Iverson 括弧の基本的な恒等式は以下の表のとおりである．

分類

恒等式

冪等

\([P]^2 = [P]\)

NOT

\([\lnot P] = 1 - [P]\)

AND

\([P\land Q] = [P]\cdot [Q]\)

OR

\([P\lor Q] = [P] + [Q] - [P]\cdot [Q]\)

XOR

\([P\veebar Q] = |[P] - [Q]|\)

ヒント

XOR の恒等式は \(P\veebar Q = (P\land \lnot Q)\lor (\lnot P\land Q)\) という NOT/AND/OR の合成で書けることから導出できる． この論理合成式から Iverson 括弧 \([P\veebar Q]\) は冪等の性質を用いて \(|[P]-[Q]|^2\) まで整理できる． こうして得た式もまた冪等であることより \(|[P]-[Q]|\) が得られる．

定式化に表れる複雑な総和条件 \(P(i)\) を次式によって外に出して，総和対象として評価できる．

(2)#\[\begin{split}\sum_{\substack{i\in I\\P(i)}} f(i) = \sum_{i\in I} f(i) [P(i)]\end{split}\]

8.3. インジケータ変数との関連#

Iverson 括弧は例えば次のように用いる．

(3)#\[z := [x\geq 0]\]

これは変数 \(x\) が非負であるならば \(1\)，そうでないならば \(0\) をとる二値の変数 \(z\) を定義していることを表す． 今の例のように「二値状態を判別するための変数」を インジケータ変数 といい， Iverson 括弧はこのような変数を数式で簡便に記述するのに便利な記法である．

注釈

インジケータ変数 の indicator とは「指示」の意味で， 所定の範囲にあるかどうかを指し示す何某かを言い表す際に用いられる用語である． つまり インジケータ変数 ならばある条件を満足しているかどうかを指し示す変数のことをいい， このような意図を数式で記述する際に Iverson 括弧は役立つ．

8.4. Iverson 括弧を用いた式変形の例#

Iverson 括弧は \([P]\cdot [Q] = [P\land Q]\) というように，それらの間で演算ができて，代数的に数理最適化に必要な論理条件を処理できるという利点がある．

例として次の二進展開の定式化の論証を考える．

制約式または目的関数に \(x\in\mathbb{Z}_{\geq0}\) と \(y\in\mathbb{R}_{\geq0}\) の積 \(x\cdot y\) があったとする． この非線形項は次の線形和に線形化できる．

(4)#\[x\cdot y = \sum_{k}2^k w_k\]

これは次の制約条件と変数を追加することで二進展開による表現ができる．

(5)#\[\begin{split}& x = \sum_{k}2^k z_k, \\ & 0\leq w_k \leq y, \\ & y - M\cdot (1-z_k)\leq w_k \leq M\cdot z_k\end{split}\]

上記が正しいことは次のようにして論証できる．

(6)#\[x = \sum_{k} 2^k z_k = \sum_{k} 2^k[z_k=1]\]

総和で残るのは \(z_k\) が \(1\) の場合であるから，最右辺のよう変形した．

次に \(y\)，\(z_k\)，\(w_k\) の間の連立不等式は次で表現できる．

(7)#\[\begin{split}w_k = [z_k=1]y = \begin{cases} y & (z_k=1), \\ 0 & (z_k=0) \end{cases}\end{split}\]

すると次のように直接に代数的な変形だけで演繹できる．

(8)#\[\sum_{k}2^k w_k = \sum_{k}2^k [z_k=1]y = y\sum_{k}2^k [z_k=1] = x\cdot y\]

8.5. よくある間違い#

Iverson 括弧の戻り値は \(0\) か \(1\) であった． このため入れ子に評価する場合には，例えば次のような違いが生じ，間違いの要因になる．

(9)#\[[3<2<1] \neq [[3<2]<1]\]

この左辺は (明らかな) 偽の命題 \(3<2<1\)，つまり \((3<2)\land(2<1)\) を表しているため，次の評価になる．

(10)#\[[3<2<1] = [3<2][2<1] = 0\cdot 0 = 0\]

しかし右辺は次のように評価される．

(11)#\[[[3<2]<1] = [0<1] = 1\]

よって両辺は一致しないことがわかる．

数式を処理できる様々なプログラミング言語の中で，単に 3<2<1 と演算順序を明示する括弧を省略して記述した場合に， 偽である期待に反する結果を得るのは，上記で述べた事柄が原因であることが多い．

関連

参考文献

[1]

Donald E. Knuth. Two Notes on Notation. The American Mathematical Monthly, 99(5):403, may 1992. URL: https://www.jstor.org/stable/2325085?origin=crossref, arXiv:9205211, doi:10.2307/2325085.

引用書式

BibTeX

目次