排他的論理和

排他的論理和（XOR）とは

排他的論理和（exclusive or、XOR）は、ブール論理における基本的な演算の一つで、二つの入力値に対して、どちらか一方のみが真（true）の場合に結果が真となり、両方とも真または両方とも偽（false）の場合は偽となる演算です。この演算は、論理回路、プログラミング、データ処理など、幅広い分野で重要な役割を果たしています。

表記法

排他的論理和は、以下のような記号で表記されます。

中置演算子: `⊻` (Unicode: U+22BB), `∨̇`
略称: XOR, xor, EX-OR, EOR
その他: `⊕` (Unicode: U+2295), +, ≠

論理学では `P ⊻ Q` のように `⊻` が、論理回路では `A ⊕ B` のように `⊕` がよく用いられます。

プログラミング言語での扱い

多くのプログラミング言語では、排他的論理和を演算子として提供しています。

記号: `^`, `@`
キーワード: XOR, xor

真理値の排他的論理和を求める場合、同値の否定演算子（`!=`や`/=`)を使用する言語もあります（例：Haskell）。

具体例

例えば、「私の身長は160cm以上である」という命題と「私の体重は52kg未満である」という命題の排他的論理和は、「私は身長160cm以上で体重が52kg以上である」または「私は身長160cm未満で体重が52kg未満である」という状態を表します。

論理和との関係

二つの命題に共通部分がない場合、排他的論理和は論理和と同じ結果になります。例えば、「私の身長は160cmである」と「私の身長は170cmである」は同時に成立しないため、排他的論理和は「私の身長は160cmまたは170cmである」という意味になります。

排他的論理和の性質

排他的[論理和]]は、[[論理和]、[論理積]、[否定]を用いて以下のように表現できます。

`P ⊻ Q = (P ∧ ¬Q) ∨ (¬P ∧ Q)`
`P ⊻ Q = (P ∨ Q) ∧ (¬P ∨ ¬Q)`
`P ⊻ Q = (P ∨ Q) ∧ ¬(P ∧ Q)`

真理値表

2を法とする剰余体

2を法とする剰余体（`Z/2Z`）での加算は、0を偽、1を真とみなすと、排他的論理和と等しくなります。これは、偶数同士または奇数同士の加算結果は偶数（偽）、偶数と奇数の加算結果は奇数（真）となるからです。

ビットごとの排他的論理和

2進数で表現された数値の各ビットに対して排他的論理和を適用した結果を、ビットごとの排他的論理和と呼びます。これは、桁上がりを無視した2進数の加算結果と等しくなります。

例:


P = 0011
K = 0110
P ⊕ K = 0101


ビットごとの排他的論理和は、有限体 `GF(2^n)` における加減算と等価です。

ビット演算での利用

ビットごとの排他的論理和は、コンピュータ上でビット操作を行う際、特定のビットを反転させるのに用いられます。例えば、ある数値と、反転させたいビットが1になっている数値とのXORを取ると、指定されたビットだけが反転します。


0011(2) ⊕ 0110(2) = 0101(2)


また、レジスタの値をゼロにする際に、直接ゼロを転送するよりも、自分自身とのXORを取る方が効率的な場合があります。多くのプロセッサでは、この方法が最適化の対象となります。これは、`X ⊕ X = 0` という性質に基づいています。

排他的論理和の応用

パリティ計算

ビットごとの排他的論理和は、入力データの偶数・奇数のパリティを検出するのに使えます。これにより、誤り検出に役立てることができます。

データ反転

排他的論理和を二度適用すると元のデータに戻る性質を利用して、データの暗号化や復号に活用できます。この性質は、結合法則によって証明できます。

`(P ⊕ K) ⊕ K = P ⊕ (K ⊕ K) = P`

この特性は、XOR交換アルゴリズムやXOR連結リストなど、様々な応用を生み出しています。

暗号化

排他的論理和は、鍵 `K` を用いた簡単な暗号化にも使えます。平文 `P` を `P ⊕ K` として暗号化し、同じ鍵 `K` を用いて再度 `P ⊕ K` を計算することで、元の平文 `P` を復元できます。

例えば、平文 `0011(2)` を鍵 `0110(2)` で暗号化すると `0101(2)` となり、`0101(2)` を再び鍵 `0110(2)` で演算すると `0011(2)` が得られます。

バーナム暗号は、この性質を利用した暗号方式です。ただし、安全な暗号化のためには、鍵が原文と同じ長さを持つワンタイムパッドが理想的です。

その他

排他的論理和は、ニムなどのゲームの必勝法を導く際にも使われます。

まとめ

排他的論理和は、論理演算の基礎でありながら、情報科学や数学の様々な分野で応用されています。そのシンプルながら強力な特性は、今後も様々な形で活用されるでしょう。

もう一度検索