アイバーソンの記法

アイバーソンの記法（英語: Iverson bracket）はケネス・アイバーソンにちなんで名づけられた記法。Pが真ならば1で偽ならば0である。

[ P ] = { 1 if  P  is true; 0 otherwise. {\displaystyle [P]={\begin{cases}1&{\mbox{if }}P{\mbox{ is true;}}\\0&{\mbox{otherwise.}}\end{cases}}}

性質

アイバーソンの記法の計算規則と論理、集合演算の間には直接的な対応関係がある。いまA, Bを集合とし、 P ( k 1 , … ) {\displaystyle P(k_{1},\dots )} を整数についての任意の性質とすると、以下が成り立つ。

[ P ∧ Q ] = [ P ] [ Q ] , [ ¬ P ] = 1 − [ P ] . [ P ∨ Q ] = [ P ] + [ Q ] − [ P ] [ Q ] . [ k ∈ A ] + [ k ∈ B ] = [ k ∈ A ∪ B ] + [ k ∈ A ∩ B ] . [ x ∈ A ∩ B ] = [ x ∈ A ] [ x ∈ B ] . [ ∀ m   .   P ( k , m ) ] = ∏ m [ P ( k , m ) ] . [ ∃ m   .   P ( k , m ) ] = min ( 1 , ∑ m [ P ( k , m ) ] ) = 1 − ∏ m ( 1 − [ P ( k , m ) ] ) . # { m ∣ P ( k , m ) } = ∑ m [ P ( k , m ) ] . {\displaystyle {\begin{aligned}[][P\land Q]&=[P][Q],\qquad [\neg P]=1-[P].\\[1em][P\lor Q]&=[P]+[Q]-[P][Q].\\[1em][k\in A]+[k\in B]&=[k\in A\cup B]+[k\in A\cap B].\\[1em][x\in A\cap B]&=[x\in A][x\in B].\\[1em][\forall m\ .\ P(k,m)]&=\prod _{m}[P(k,m)].\\[1em][\exists m\ .\ P(k,m)]&=\min {\Big (}1,\sum _{m}[P(k,m)]{\Big )}=1-\prod _{m}\left(1-[P(k,m)]\right).\\[1em]\#\{m\mid P(k,m)\}&=\sum _{m}[P(k,m)].\end{aligned}}}

参照

  • Donald Knuth, "Two Notes on Notation", American Mathematical Monthly, Volume 99, Number 5, May 1992, pp. 403–422. (TeX, arXiv:math/9205211)
  • Kenneth E. Iverson, "A Programming Language", New York: Wiley, p. 11, 1962.

関連項目

  • 表示
  • 編集