排他的論理和単語

9件
ハイタテキロンリワ
5.1千文字の記事
  • 23
  • 0pt
掲示板へ

排他的論理和(exclusive or / exclusive disjunction)とは、2つの命題・入力などがどちらか一方のみである場合にと返す論理演算の1つである。

XOREOREX-ORなどと略記されることが多い。

概要

排他的論理和の記号は複数あり、論理学では⊻、電子工学では⊕、プログラミング言語では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)⊻R

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

3. P∧(Q⊻R) = (P∧Q)⊻(P∧R)

また、論理積は排他的論理和に対して分配法則を満たす。これも2と同様にひたすら計算すれば確認することができる。

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

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

便宜的に先頭を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が切り替わるスイッチ」のモデルである。

上のモデルを長廊下とみなして具体的な例を与えてみよう。初期状態は「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の各桁に二進数で00011111という番号を振っておき、「受け取った情報に対して1である桁の排他的論理和をとる」という取り決めをしておく。例えば上図のように001000110111000(下から4,5,6,8,9,13桁が1)ならば
  100101110100010011101 = 1011
となる。このとき自分が1111を送信したい場合、下から4桁(二進数100)を0に反転すると
   101⊕110100010011101
= 100⊕100101110100010011101
= 1001011
= 1111
となるし1010と送信したいならば、下から1桁(二進数で1桁)を1に反転
   1⊕100101110100010011101
= 1⊕1011
= 1010
とすればよい。上記のように反転したい桁の元の状態によらずに「反転したい桁」と「元のデータの排他的論理和」との排他的論理和を計算すればよい。なお、元のデータが伝えたい情報そのままだったときはデータを変更しなければいいだけである。

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

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

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

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

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

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

.

.

答え

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

関連動画

関連項目

関連リンク

【スポンサーリンク】

  • 23
  • 0pt
記事編集 編集履歴を閲覧

ニコニ広告で宣伝された記事

ニコニ広告 (単) 記事と一緒に動画もおすすめ!
提供: 広告太郎
もっと見る

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

お絵カキコがありません

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

ピコカキコがありません

排他的論理和

15 ななしのよっしん
2024/09/01(日) 15:37:09 ID: 0JNpzOs8/N
パズルゲーの実況でこのタグが使われてた(排他的論理和ルールに使われてた)からそれが原因かな?
👍
高評価
1
👎
低評価
0
16 ななしのよっしん
2024/09/01(日) 18:10:06 ID: FH1jCmeJiG
>>15
排他的論理和検索しても2021年動画が最新なんだがどこのことなんだ
👍
高評価
0
👎
低評価
0
17 ななしのよっしん
2024/09/01(日) 18:13:42 ID: HUfNGefAZd
アセンブラだとアドレスAとアドレスBの中身を入れ替えるときにXOR使うと演算回数少なくなるよね
👍
高評価
0
👎
低評価
0
18 ななしのよっしん
2024/09/01(日) 18:23:41 ID: /N5cuzD2Ws
XORって「ゾア」で良いのかな?
👍
高評価
0
👎
低評価
0
19 ななしのよっしん
2024/09/01(日) 19:49:20 ID: X8crA03IFS
エックスオアが多いと思う。
大昔にお手製の作図ツールで要素をドラッグ移動させるときに使ったわ。
👍
高評価
1
👎
低評価
0
20 ななしのよっしん
2024/09/01(日) 21:20:21 ID: 1nFo7SmCw4
>>15>>16
>>sm43983105exit_nicovideo

Gate氏のTaiji実況プレイにこのタグが付いていたことがあった
ゲームルールネタバレになるからか今はタグが外されているみたい
別に付いていてもいいとは思うけど

それはそうと、上がってきたのは今週のオススメ記事が原因だと思う
👍
高評価
1
👎
低評価
0
21 ななしのよっしん
2024/09/17(火) 09:20:04 ID: oo0EEznQJC
👍
高評価
0
👎
低評価
0
22 ななしのよっしん
2024/10/19(土) 00:05:02 ID: GXKSLHL4Om
チェス盤のやつの回答に納得がいかない
「最初の状態の排他的論理和」って何だ?
64マスチェス盤の状態を二進数で表現するなら64桁要るんじゃないの?
👍
高評価
0
👎
低評価
0
23 ななしのよっしん
2024/10/19(土) 01:36:36 ID: 26vGw2NkOD
いらない
6ビットで表現できる
最初の状態の排他的論理和というのは、つまりコインを入れ替える前の盤面の状態を6ビットで表すとどうなるか、ということ
記事の解説だけでは多分分からないので詳しくはググってね
👍
高評価
0
👎
低評価
0
24 ななしのよっしん
2024/10/19(土) 02:48:39 ID: pFTparRjnm
横からだけど2⁵ 2⁴ 2³ 2² 2¹ 2⁰のフィルタの図を見ながらやってようやく理解した
囚人が二人共頭良くないと片方が理解できてないだけで終わりじゃねえか
(当然最初に入る方がより頭良くないと変換ミスの可性がある)
👍
高評価
0
👎
低評価
0

ニコニコニューストピックス