8件
排他的論理和(exclusive or / exclusive disjunction)とは、2つの命題・入力などがどちらか一方のみ真である場合に真と返す論理演算の1つである。
概要
排他的論理和の記号は複数あり、論理学では⊻、電子工学では⊕、プログラミング言語ではXORもしくは^などと書かれる。
以降、この記事では排他的論理和の記号を⊻もしくは⊕で表すことにする。
先述の通り排他的論理和は2項演算子なので2つの入力に対し1つの出力を返す。p, qがそれぞれ1(真)か0(偽)のどちらか一方をとるとき、真理値表は右下のようになる。
| 真理値表 | ||
|---|---|---|
| p | q | p⊻q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
この表の通り、2つの入力について真偽が一致したときは偽(0)を返しそうでないときは真(1)を返す。
右上のベン図について考えると、全体集合の中の任意の要素aについて
「a∈P」と「a∈Q」
の2つの命題のうち片方のみ真であるような要素を集めた集合がP⊻Qであると考えることができる。
すなわち排他的論理和については細かく分類すると、2つの真偽に対して1つの真偽を出力するタイプのものと、2つの集合に対して片方のみ満たす集合を新しく与えるタイプのものがあるということになる。
排他的論理和の性質
集合P, Q, Rを用いて記述していくが、以下の性質は集合でなくても2つの命題・入力などでも成り立つ。
基本的な記号のみで表す
排他的論理和は論理演算における基本的な記号∨(論理和)、∧(論理積)、¬(否定)のみで表すことができ、表し方の例として
P⊻Q = (P∨Q)∧¬(P∧Q)
が挙げられる。あえて読み上げるなら
「PまたはQ」かつ「『PかつQ』じゃない」
となる。分配法則を使ったりド・モルガンの法則を使ったりすると他の表し方も可能である。
交換法則・分配法則・結合法則
以上は全て成り立つ。証明は割と面倒だが、∨∧¬のみで表したうえでひたすら計算すればどうにかなるだろう。
ビット演算で排他的論理和を使う
便宜的に先頭を0にすることがあるが八進数と混同しないように注意。
複数桁を同時に計算する
ビット演算においては全ての桁に対して&(AND)や|(OR)で計算をすることが多い。
例1: 1001&1100…1000 (両方1である桁は最初の1つ目だけ)
例2: 1001|1100…1101 (最後から2番目を除いて1が入っている)
これを⊕に対して使うことも可能である。
例: 1001⊕1100…0101 (片方のみ1が入っている桁は最後から1,3番目である)
なお、このような計算を排他的ビット和などと区別することもあるが単に排他的論理和と呼ばれることも多い。
複数の値を同時に計算する
1⊕0⊕0⊕1⊕0⊕1⊕1
のような複数の値を排他的論理和で結んだものを計算しよう。
結論から述べると、計算結果は1が奇数個のとき1で1が偶数個のとき0となる。
厳密な証明は数学的帰納法などでまかなえるとして、ここでは実際に左から計算していこう(同じ演算子が複数並んだときは基本的に左から順に計算する)。すると、⊕0が与えられると0,1の値は保たれ⊕1が与えられると0,1の値は反転する。このことからも計算結果は1の個数の偶奇に依存することが分かる。
さらに、複数桁の値を複数個同時に計算することも可能である。
例: 11101⊕100111⊕111010 = 0
排他的論理和を活用する
階段・長廊下に電気をつける
まずは上の「スイッチ」を押してみてほしい。どこのスイッチが押されたかによらず、スイッチが押されるたびにON/OFFが切り替わっていると思う。これは階段・長廊下などの「どこで押してもON/OFFが切り替わるスイッチ」のモデルである。
上のモデルを長廊下とみなして具体的な例を与えてみよう。初期状態は「0⊕0⊕0⊕0」とする。
Aさんが左からやってきて廊下が暗いので電気をつけた。このとき「1⊕0⊕0⊕0」となっている。
その後廊下を渡りきって一番右のスイッチを押して電気を消した。このとき「1⊕0⊕0⊕1」となった。
少ししたらBさんが左からやってきて電気をつけた。このとき「0⊕0⊕0⊕1」となっている。
Bさんは廊下の途中にある部屋に入るため右から2番目のスイッチを押して電気を消した。最終的に「0⊕0⊕1⊕1」となった。
このように1回スイッチを押すたびに電気のON/OFF(計算結果)が入れ替わったことが確認できた。
電流の流れる向き(すなわち反時計回り)に沿って考えていこう。4つのスイッチのうち一番左のものは、0のとき下へ1のとき上に電流を送っている。そして残りの3つのスイッチについては、⊕0のとき上下を保ち⊕1のとき上下を入れ替える。電流が4つのスイッチを流れたあと、最終的に電流が上の方を流れていれば電球は光る。
これは4つの(0か1の)値の排他的論理和を計算しているのと同じである。先程も述べたが、⊕0が与えられると0,1の値は保たれ⊕1が与えられると0,1の値は反転するので、計算結果は1が奇数個存在するか偶数個存在するかに依存する。そしてどのスイッチを押しても1の個数の偶奇は必ずひっくり返る。
ニムで勝つ
こんなゲームをやったことがあるだろうか。
いくつかの山に石が何個か積まれている。
2人のプレイヤーは交互に石を取っていく。このとき、1つの山のみから石を1個以上取らないといけない。
最後の石を取ったプレイヤーの勝利である。
これはニム、石取りゲーム、三山崩し(みやまくずし)などと呼ばれるゲームであるのだが、このゲームには排他的論理和を用いた必勝法がある。
まずは準備としてn個の山にある石の数をa1, a2, …, anとしよう。このときa1, a2, …, anを全て二進数にしたときのa1⊕a2⊕…⊕anの値をニム和と定義する。
自明なことだが、勝利した際のニム和は絶対に0である。(∵0⊕0⊕…⊕0=0)
したがって
「(ニム和が0でないときに)自分が石を取ったときのニム和を必ず0にでき」…①
「①のもとで相手が石をとったときのニム和が必ず0にならない」…②
の2点が証明できれば、(自分の手番がきたときにニム和が0のときに限り)必勝法が存在することになる。これらを証明していこう。
①の証明
ニム和が0でないのでその値は必ず1から始まる。したがってそのニム和の桁数と同じ位に「1」がある山が少なくとも1つ存在する。(例えばニム和が101なら101100のような山)
その山からはニム和が0になるように反転させることは可能である。例えばニム和が101ならば101100個(十進数で44個)の石がある山を101001個(十進数で41個)にすることは可能である。(橙色の部分のビットが反転した)
よって示された。
②の証明
ある山から石をとると、少なくとも1つの桁について0と1が入れ替わる。これはニム和が0から変化することに他ならない。よって示された。
①②が示されたので
以上より、自分の手番がきたときにニム和が0でないならば必勝法が存在する。
(Q.E.D.)
なお、プレイヤー2人が最善を尽くしたとき(すなわち必勝法を知っているとき)、スタート時のニム和が0でないなら先手の勝利で0ならば後手の勝利となる。
もし先手になりそうならばスタートの石の数をできるだけ増やそう。桁が増えれば増えるほどニム和は0になりにくい。
パズル1: Spy transmission 15bit
あなたは某国のスパイであり、無事に敵国に侵入することができた。
あなたは敵国から出ることなく自国へと情報を送信したいのだが、使える手段はたった1つで「定期的に敵国の電波塔から自国へと発信される15bitの情報のうち1桁の0,1を反転させる」のみである。
15bitの情報が何なのかはその時にならないと分からないのだが、この手段を使って毎回4bitの情報を自国に送ることは可能だろうか？
なお、敵国に潜り込む前に作戦を立てることを許可する。
以下、解説に入るので注意。
.
.
答え
あらかじめ15bitの各桁に二進数で0001～1111という番号を振っておき、「受け取った情報に対して1である桁の排他的論理和をとる」という取り決めをしておく。例えば上図のように001000110111000(下から4,5,6,8,9,13桁目が1)ならば
100⊕101⊕110⊕1000⊕1001⊕1101 = 1011
となる。このとき自分が1111を送信したい場合、下から4桁目(二進数で100桁目)を0に反転すると
101⊕110⊕1000⊕1001⊕1101
= 100⊕100⊕101⊕110⊕1000⊕1001⊕1101
= 100⊕1011
= 1111
となるし1010と送信したいならば、下から1桁目(二進数で1桁目)を1に反転し
1⊕100⊕101⊕110⊕1000⊕1001⊕1101
= 1⊕1011
= 1010
とすればよい。上記のように反転したい桁の元の状態によらずに「反転したい桁」と「元のデータの排他的論理和」との排他的論理和を計算すればよい。なお、元のデータが伝えたい情報そのままだったときはデータを変更しなければいいだけである。
パズル2: チェス盤とコイン
あなたともう1人の仲間は囚人である。2人はチェス盤がある部屋の外に待機させられている。
上下左右がはっきりわかる8×8マスのチェス盤の各マスにはコインが多くても1枚あらかじめ乗っている。(すなわちチェス盤にはコインが最高64枚最低0枚乗っている)
チェス盤の状態は入室するまで分からない。
1人がチェス盤のある部屋に入れられると、その人は看守から0～63の整数のうち1つを教えらたのち次の行動を必ず取らなければならない。上記の行動をとったあと最初に部屋に入った囚人は隔離され、もう1人の囚人が部屋に入る。もう1人の囚人ができることはチェス盤の状態を見て看守に対し最初に入室した囚人が教えられた整数を伝えることのみである。
正しい整数を伝えることができれば2人は釈放、間違えれば処刑である。
2人は上記のことは事前に分かっており、あらかじめ作戦を立てておくことも許されるのだが、どうすれば2人は無事釈放されるだろうか？
以下、解説に入るので注意。
.
.
答え
事前にチェス盤のマス目に対して000000～111111までの二進数を与えておく。
コインが乗っているマス目の排他的論理和を計算しておき、あとは看守に教えられた整数になるように1マス入れ替える。
例えば最初の状態の排他的論理和が100001であり、看守に教えられた整数が7(二進数で000111)ならば、チェス盤の100110に相当する場所のコインの有無を反転させればよい。このとき最初にコインが乗っていようがいまいがその後のチェス盤に対する排他的論理和は
100001⊕100110 = 000111
となる。あとはもう1人の囚人がチェス盤を見て計算し000111であることから7を看守に伝えればよい。
関連動画
関連項目
関連リンク
- 12
- 0pt
