ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


排他的論理和


ヨミ: ハイタテキロンリワ
掲示板をミル!
2カキコ!

排他的論理和(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


排他的論理和を活用する


階段・長廊下に電気をつける


次へ»
最終更新日: 19/06/06 12:13
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ