all? と any? の変換と論理学 - プログラミング漫遊記

昔なんかの書籍でArray#all?で書いたコードをany?に変換しましょう(逆だったかも)というのがあって結構苦手だったんだけど、これだたの論理式では？と思い直したら楽になったので記しておく。

最近(数理)論理学の学び直しをしてるのにプログラミングと全然結びついてなかったですね。反省。

本題

配列の要素が全て偶数か？偶数ならtrue1つでも偶数でないものがあればfalseを返すという単純なお題。

ary1 = [0, 2, 4, 6, 8, 10]
ary1.all?(&:even?) => true

ary2 = [0, 1, 4, 6, 8, 10]
ary2.all?(&:even?) => false

でこれをany?に変換する。(そんな需要はあるのか？というのは置いていこう！)

!ary1.any?(&:odd?) => true

!ary2.any?(&:odd?) => false

構造がわかるようにちょっと同じ意味のコードに変換しておく。

!ary1.any? { |n| !n.even? } => true

!ary2.any? { |n| !n.even? } => true

all?は「すべての(任意の)」という全称量化子( $\forall$ )に対応する。またany?は「ある(~が存在する)」という存在量化子( $\exists$ )に対応する。

「配列内の要素 $x$ が偶数である」を述語 $P(x)$ で表す。

また命題が同値であることを $\equiv$ で表す。

で、「配列内の全ての要素が偶数である」という命題は以下の式に変換できる配列内の要素の集合をAとすると

$\forall x \in A (P(x))$

二重否定を使って表すと

$\displaystyle \forall x \in A (P(x)) \equiv \neg \neg (\forall x \in A (P(x)))$

あとは全称命題の否定は否定の存在命題になることをうまく使って

$\displaystyle \neg \neg (\forall x \in A (P(x))) \equiv \neg (\neg \forall x \in A (P(x))) \ \equiv \neg (\exists x \in A (\neg P(x))$

となる。最後の式の形が !ary1.any? { |n| !n.even? }という形になってるので偶数の否定を奇数に変換したり見栄えを整えると最初のコードになる。

なにやら難しい論理記号の仕組みを伝えたいのではなくて、条件式を操作するのは論理式と対応づけられているよということが自分の中の再発見だった(当たり前)というのを伝えたかった。