ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

数理論理学の些細な気づきごと

数理論理学の勉強はもう終わらせてやめましたが、最近ふと気づいてしまったメチャメチャどうでもいい発見があったので、たいしたことではないですから短くまとめます。

すごく小さな発見を、今回は2点ほど用意しております。

(追記ですが、ちっとも短く書けませんでした…)


まず1つ目ですが、xor演算についてです。
数学というより、プログラミングで論理演算をするときに知っとくとためになるかもしれませんね。

xorは、a xor bだったら、どういう意味かといえば、

aとbが両方ともfalseなら結果もfalse、aかbのどちらかだけがtrueなら結果はtrue、aとbが両方ともtrueなら結果はfalse、ですよね。


じゃあ、これがa xor b xor cと3つになったらどうなるでしょうか。
ちなみに左結合、つまり(a xor b) xor cです。

これは、感覚的には2項バージョンの拡張として、a,b,c全てがfalseなら結果はfalse、a,b,cのどれか1つだけがtrueなら結果はtrue、a,b,cのうち2つ以上がtrueなら結果はfalseになる演算だとみなしたいわけですが、そうはならないようなんですね。

反例としては、a,b,cが全てtrueだとしたら結果はfalseになってもらいたいわけですが、a xor bの時点で一回falseになってしまうので、そのfalseとcつまりtrueをxorして、結果はtrueになってしまうと。

ちなみに情報工学ではメジャーな話ですが、x xor trueをかけるとxの反転が得られますから、a xor b xor c xor dのa,b,c,dが全てtrueならa xor b xor c = trueの反転でfalseですね。

偶数個の項なら反例になりませんが奇数個のとき反例になることになります。


また、補足しておくと、ブール代数での話ですが、2項バージョンのときa,bの片方がtrueならtrueというのは、この“片方がtrue”というのが、
「1つだけtrueで残りはfalse」ということなのか、「1つ以上trueがあるが1つ以上falseがある(確実にすべてfalseではないが確実に1つはfalseがある)」ということなのか、という二つの捉え方があって、

これらは2項バージョンにおいては同値ですから違いが曖昧なのですが、3項以上になると違う命題になるので、後者のほうの捉え方も3項以上バージョンでは、また別個に考えられます。

つまり後者の捉え方で、a xor b xor cを、
a,b,c全てがfalseなら結果はfalse、a,b,cのうち1つ以上trueがあって1つ以上falseがあれば結果はtrue、a,b,c全てがtrueなら結果はfalseになる演算だとみなすこともできるわけですね。


さらに、trueでなくfalseの個数に着目した場合、つまりtrueとfalseが出てくる箇所をひっくり返した場合に後者では同値となりますが、前者では違う命題になるので、前者の捉え方のtrueとfalseをひっくり返した捉え方も論理的にはありますが、
まあa xor b xor cを感覚的に捉えるならばfalseの個数で考えるという発想はないと思いますので、この場合は無視しましょう。

だとすれば、上の話での後者の捉え方はどうなのかというのは考えなければなりませんが、このときも前者のときと同様にa,b,cが全てtrueという反例があって、感覚的なものとは違う真理値になります。


感覚的に捉えたものと同じ真理値にしたい場合はどういう論理式を書けばいいのかというと、後者の捉え方の場合は単純に、
(a or b or c) and not (a and b and c)みたいに全ての項をorでつなげたものと、andでつなげたものの否定の論理積をとるだけです。

むしろ、2項の場合はa xor bは(a or b) and not (a and b)と同値なのに、3項以上の場合は同値でなかったことに驚きますね。


前者の捉え方では、2つ以上の項がtrueにならないことを表現するために、あらゆる2つの項の組み合わせについて論理積がtrueにならないことを言わなければならないわけで、

a,b,cなら(a or b or c) and not (a and b) and not (a and c) and not (b and c)みたいに、長いですね。

全ての項をorでつなげたもののあとに、n項ならばnC2個の2つの項の組み合わせの論理積の否定を付けて、論理積でつなげなければなりません。
nandを使えば(a or b or c) and (a nand b) and (a nand c) and (b nand c)みたいに若干、短くなるか…。


というわけで、イメージ通りにやりたい場合はxorでつなげるのでは駄目で、地味に大変な論理式を書かなければならない、という話でした。

そうそう、上記の論理式を書く以外にも、真理値表をもとに論理式の標準形を書くという手段も、一応ありますね。

続きを読む

tag: 数学 論理学 論理式 論理演算 写像 集合 同値 組み合わせ 考察 クソ記事

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。