排他的論理和単語

ハイタテキロンリワ

排他的論理和(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』じゃない」
となる。分配法則を使ったりド・モルガン法則を使ったりすると他の表し方も可である。

交換法則・分配法則・結合法則

  1. 交換法則…P⊻Q = Q⊻P
  2. 分配法則…P⊻(Q⊻R) = (P⊻Q)⊻(P⊻R)
  3. 結合法則…P⊻(Q⊻R) = (P⊻Q)⊻R

以上は全て成り立つ。明は割と面倒だが、∨∧¬のみで表したうえでひたすら計算すればどうにかなるだろう。

ビット演算で排他的論理和を使う

この項で扱う数は全て二進数排他的論理和記号は⊕を使う。

便宜的に先頭を0にすることがあるが八進数と混同しないように注意。

複数桁を同時に計算する

ビット演算においては全ての桁に対して&(AND)や|(OR)で計算をすることが多い。
  例1: 1001&1100…1000 (両方1である桁は最初の1つだけ)
  例2: 1001|1100…1101 (最後から2番を除いて1が入っている)
これを⊕に対して使うことも可である。
  例: 10011100…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が切り替わるスイッチ」のモデルである。

電流の流れる向き(すなわち反時計回り)に沿って考えていこう。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個の石がある山を101001個にすることは可である。(橙色の部分のビットが反転した)

よって示された。

②の証明

ある山から石をとると、少なくとも1つの桁について0と1が入れ替わる。これはニム和が0から変化することに他ならない。よって示された。

①②が示されたので

以上より、自分の手番がきたときにニム和が0でないならば必勝法が存在する。

(Q.E.D.)

なお、プレイヤー2人が最善を尽くしたとき(すなわち必勝法を知っているとき)、スタート時のニム和が0でないなら先手勝利で0ならば後手の勝利となる。

もし先手になりそうならばスタートの石の数をできるだけ増やそう。桁が増えれば増えるほどニム和は0になりにくい。

パズル1: Spy transmission 15bit

あなたは某スパイであり、事に敵国に侵入することができた。
あなたは敵国から出ることなく自へと情報を送信したいのだが、使える手段はたった1つで「定期的に敵国電波から自へと発信される15bit情報の1桁のみをざんする」のみである。
15bit情報が何なのかはその時にならないと分からないのだが、この手段を使って毎回4bit情報を自に送ることは可だろうか?
なお、敵国に潜り込む前に作戦を立てることを許可する。

以下、解説に入るので注意。

.

.

答え

15bit情報に対して1である桁の排他的論理和をとる。上図のように001000110111000(下から4,5,6,8,9,13桁が1)ならば
  100101110100010011101 = 1011
となる。このとき自分が1111を送信したい場合、下から4桁ざんすると
  1011⊕0100 = 1111
となるし1101と送信したいならば、下から6桁をざんし
  1011⊕0110 = 1101
とすればよい。これは排他的論理和の性質から元のデータが何であろうとも関係なく行うことができる。

パズル2: チェス盤とコイン

あなたともう1人の仲間は囚人である。2人はチェス盤がある部屋の外に待機させられている。
上下左右がはっきりわかる8×8マスチェス盤の各マスにはコインが多くても1枚あらかじめ乗っている。(すなわちチェス盤にはコインが最高64最低0枚乗っている)
チェス盤の状態は入室するまで分からない。
1人がチェス盤のある部屋に入れられると、その人は看守から0~63整数のうち1つを教えらたのち次の行動を必ず取らなければならない。

上記の行動をとったあと最初に部屋に入った囚人は隔離され、もう1人の囚人が部屋に入る。もう1人の囚人ができることはチェス盤の状態を見て看守に対し最初に入室した囚人が教えられた整数を伝えることのみである。

正しい整数を伝えることができれば2人は釈放、間違えれば処刑である。

2人は上記のことは事前に分かっており、あらかじめ作戦を立てておくことも許されるのだが、どうすれば2人は事釈放されるだろうか?

以下、解説に入るので注意。

.

.

答え

事前チェス盤のマスに対して000000~111111までの二進数を与えておく。
コインが乗っているマス排他的論理和を計算しておき、あとは看守に教えられた整数になるように1マス入れ替える。
例えば最初の状態の排他的論理和100001であり、看守に教えられた整数が000111(十進数で7)ならば、チェス盤の100110に相当する場所のコインの有反転させればよい。このとき最初にコインが乗っていようがいまいがその後のチェス盤に対する排他的論理和
  100001⊕100110 = 000111
となる。あとはもう1人の囚人がチェス盤を見て計算し000111であることから7を看守に伝えればよい。

関連動画

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

排他的論理和

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • 排他的論理和についての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!


急上昇ワード