7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します
排他的論理和
掲示板をﾐﾙ!排他的論理和(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
排他的論理和を活用する
階段・長廊下に電気をつける
次へ»
最終更新日: 19/06/06 12:13
タグ検索
パソコン版を見る
![[0]](/em/zero.gif){kind=small}
TOP