ブログ「サイバー少年」

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

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

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

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

すごく小さな発見を、今回は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でつなげるのでは駄目で、地味に大変な論理式を書かなければならない、という話でした。

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





さて、2つ目の発見ですが、2項論理演算、つまり集合I = {true,false}上の2項演算の考えうる個数というのはいくつあるでしょうか。

この2項演算というのはI×Iの要素である2つ組の順序対からIの要素へ写す写像です。

有限集合A,BにおいてAからBへの写像として考えうる個数はn(B)^n(A)、つまりBの要素数のAの要素数乗です。
(これは、みなさんお分かりのものだとします。)


そして、I×Iの要素数というのはn(I)×n(I) = n(I)^2個あります。

つまり、この2項演算の数はn(I)^n(I×I) = n(I)^(n(I)^2) = 2^(2^2) = 16個あることになります。

意外と少ないんですよね。
AND,OR,XOR,IMP,EQ,NAND,NORあたりは名前がついてますから、名前のない2項論理演算は9種類ですか。

論理演算 - Wikipedia
https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97

を見てみると、全16種類に名前がつけられていました。


上のような2項論理演算を、I×Iの要素である2つ組の順序対から、Iの要素(trueまたはfalse)へ写す写像であるとみなす考えがミソで、
実は論理式においても、n個の命題記号を持つ論理式は(ブール代数で解釈する場合)I^nの要素であるnつ組の順序対から、Iの要素へ写す写像であるとみなせるわけですね。

詳細な説明は理解いただいているものと仮定してすっ飛ばしますが、写像へ入力する順序対の1番目、2番目、3番目…をそれぞれ対応する命題記号の真理値に割り当てることによって、論理式全体の真理値が定まるのでそれを出力とするような写像を作るわけです。


この写像は、論理式の形を無視して入力と出力だけに着目した、論理式の別の姿だと考えることができますが、ある論理式から作った写像と、別の論理式から作った写像が同じ写像であれば元となった2つの論理式は同値であるといえます。

なぜなら、2つの論理式から作った2つの写像が同じであるということは、あらゆる同じ順序対を2つの写像に入力しても同じ出力が返ってくるということなので、
これは2つの論理式にあらゆる同じ命題記号の真理値割り当てを行っても2つの論理式は同じ真理値を持つというわけですが、

ここで2つの論理式が同値であるとは、あらゆる真理値割り当てにおいても両方の論理式が同じ真理値を持つということですから、定義そのままで同値になるわけです。


なお、2つの論理式から作った写像が同じでなければ、同じ入力なのに違う出力が返ってくる場合があるということですから、これは2つの論理式に同じ命題記号の真理値割り当てを行っても違う真理値を持つということになって、同値の定義に従わないので同値ではありません。

以上のことから、写像が同じなら論理式は同値ということを説明したのと、裏の命題の写像が同じでないなら論理式は同値でないことを説明しました。


ここで、先ほどの考えうる写像の個数を数えるという話を思い出してみると、このI^nからIへの写像の個数というのは、I^nの要素数はn(I)^nつまり2^nで、出力の要素数2のそれ乗ですから、2^(2^n)となります。

ですからこれらの写像は2^(2^n)個しかないのです。
全種類の写像を用意したら、それ以外の写像はすべてそのどれかと同じ写像になります。


ここでいう写像は、何らかの論理式から作られたというわけですが、ここからどういうことがいえるかというと、

写像が2^(2^n)個しかなくてそれ以外の写像はどれかと同じになるなら、元となった論理式も2^(2^n)個しかなくてそれ以外の論理式はどれかと同値になるだろうということです。

これは先ほど説明した、写像が同じであるなら論理式の側も同値であるということによるものですね。

ただそれだけだと写像が同じでなくても論理式が同値になるパターンがあるかもしれないので、写像が2^(2^n)個なのに対して論理式の個数はそれより少なくなることがあるかもしれないわけですが、上記の裏の命題も示しているので、それはありえません。


論理式の場合は2^(2^n)個というより2^(2^n)種類ですけども。
同じ種類の論理式は同値であるということです。

同値類という言葉を最近、群・環・体の勉強で覚えたので使うとしたら、論理式の同値類が2^(2^n)個発生するわけです。


n個の命題記号を持つ論理式というのはいくらでも種類があるのかと思っていましたが、実は同値なものをまとめると有限の種類しかなかったんですね。

それもたいした数でなく。nが増えると高速に上昇しますけども。

まあ、命題記号0個ではtrueとfalseの2種類、命題記号1個ではaとnot aとa and not aとa or not aの4種類、命題記号2個では16種類、命題記号3個では256種類、命題記号4個では65536種類…と考えると妥当ではありますか。



というわけで、2つの小さな話をしようと思ったらだいぶ長くなってしまいましたけども、以上です。

ただでさえ脳みそのコンディションがいつもより悪かったんですが、それなのにオリジナルの理論を展開するという書くのが難しいジャンルの記事を書いて大変、疲れました。
(以前も書きましたが自分で理論を積み重ねるの大の苦手なんですよ。)

現在、放心状態であります。


記事のわかりやすさ、論理的整合性等々、クオリティも最低な仕上がりになってるかもしれませんね。
まあでも自分で発見したことを理論的にまとめるという、論文作成というと勘違いしすぎかもしれませんが、自由研究完成させたぜ、みたいな感じがして満足です。

あとはいろんな人に読んでもらえて、批評してくれればいいなぁと願うんですけどね~。

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

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/485-ac9c47eb
この記事にトラックバックする(FC2ブログユーザー)

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