2008年12月20日土曜日

排他的論理和

歯痛的論理は?
じゃなくて.

論理和 OR(または) は
false OR false = false
true OR false = true
false OR true = true
true OR true = true

true とか false では字数が多いので,
true = 1,false = 0
などと記号化する.

0 OR 0 = 0
1 OR 0 = 1
0 OR 1 = 1
1 OR 1 = 1

さらに,OR には ∨ といった記号がある.
0 ∨ 0 = 0
1 ∨ 0 = 1
0 ∨ 1 = 1
1 ∨ 1 = 1

ブール代数は「 + 」記号を使う.
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 1
最後の 1+1 だけが普通の算術和と論理和との違いではある.

論理積(且つ AND ∧ ・)はすべて算術と同じになる.
0 ・ 0 = 0
1 ・ 0 = 0
0 ・ 1 = 0
1 ・ 1 = 1

さて,排他的論理和 Exclusive Or(XOR)は
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
となるもの.
(A∨B)∧¬(A∧B)= A XOR B
と定義されている.(¬ は否定)

複雑だが,日常語の「または」に近い気がする.

たとえば,人を呼び出すとき,
「Aくん,または,Bさんが来てください」
と連絡したら,1人だけが行けばいいのであって,二人そろっていくことはあまりないのではないか.
つまりこの場合の「または」は排他的論理和に近いものである.
本来の論理和「または」の場合,「少なくとも一方」なので,二人そろって行くことも考えていい.

英語でも,
「Freeze! or you'll die」(動くな,さもないと死ぬぞ)
直訳すれば,
「とまれ! または,死ぬだろう」
だが,もしこの「OR」が論理和なら両方起きてもよいので,止まって殺されても文句はいえない.
やはり,この OR も  Exclusive Or なのだろうと思う.
もちろん,銃を持つような人間にとっては,「両方あり」(つまり排他的でないただの論理和OR)だろうが.

排他的論理和を「情報」の時間に説明するときに,そんな話をする.

さて,XOR がコンピュータで重要なのは,1ビットの算術和になっているからではある.
ただの論理和では
 1+1=1
で算術和ではない.1の位は(繰上りして)0に戻らねばならぬからである.
 1 xor 1=0
その意味で,xor は1ビットの加算であるといえる.

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.