はじめに
AND・OR・XORは論理演算、和集合・積集合・差集合は集合演算として学びます。名前や記号は異なりますが、「ある要素が集合に属するか」を真・偽で考えると、両者の対応関係を整理できます。
ただし、論理演算と集合演算は同じ処理ではありません。論理演算は真偽値を扱い、集合演算は集合を作ります。この記事では、x ∈ Aとx ∈ Bを真偽の条件として考え、AND・OR・NOT・XORが積集合・和集合・補集合・対称差・差集合とどう対応するのかを解説します。
集合演算そのものの意味やベン図を先に確認したい場合は、和集合・積集合・差集合とは？ベン図と記号で違いをわかりやすく解説を参照してください。
論理演算と集合演算は何が違う？
論理演算は、「条件Aが真か」「条件Bが真か」といった真偽値を入力として、結果の真偽を求める演算です。たとえばANDは両方が真のときだけ真、ORは少なくとも一方が真なら真になります。
集合演算は、集合を入力として、条件を満たす要素からなる集合を得る演算です。積集合A ∩ Bは両方に含まれる要素、和集合A ∪ Bは少なくとも一方に含まれる要素を集めます。
この2つを結び付けるのが、ある要素xについて「x ∈ Aは真か」「x ∈ Bは真か」と考える方法です。集合全体を論理値に置き換えるのではなく、各要素の所属条件を論理式として読むと対応関係が明確になります。
AND・OR・XORの違いを真理値表で確認
まず、2つの条件A・Bに対するAND・OR・XORの違いを確認します。
| A | B | AND | OR | XOR |
|---|---|---|---|---|
| 偽 | 偽 | 偽 | 偽 | 偽 |
| 偽 | 真 | 偽 | 真 | 真 |
| 真 | 偽 | 偽 | 真 | 真 |
| 真 | 真 | 真 | 真 | 偽 |
ANDはAとBが両方とも真のときだけ真です。ORはAとBの少なくとも一方が真なら真で、両方とも真の場合も真になります。
XORは「排他的OR」と呼ばれ、AとBのどちらか一方だけが真のときに真です。両方が真の場合は偽になるため、通常のORとの違いは「両方とも真」の行を見ると分かります。
集合演算との対応関係
集合Aと集合Bに対して、要素xが属するかどうかを条件として表すと、論理演算との対応は次のように整理できます。
要素xの条件 | 論理演算 | 対応する集合演算 |
|---|---|---|
x ∈ A かつ x ∈ B | AND | x ∈ A ∩ B |
x ∈ A または x ∈ B、または両方 | OR | x ∈ A ∪ B |
x ∉ A | NOT | x ∈ A^c |
| A・Bのどちらか一方だけに属する | XOR | x ∈ A △ B |
x ∈ A かつ x ∉ B | AND＋NOT | x ∈ A \ B |
たとえばx ∈ A ∩ Bという条件は、「x ∈ Aが真 AND x ∈ Bが真」と同じ条件です。x ∈ A ∪ Bは、「x ∈ Aが真 OR x ∈ Bが真」と読めます。
ここでいう対応は、論理演算と集合演算が同じ種類の演算という意味ではありません。論理式が真になる要素を集めると、対応する集合が得られるという関係です。
ORとXORを集合で比べる
ORとXORの違いは、2つの集合が重なる場合に分かりやすくなります。たとえば、次の集合を考えます。
A = {1, 2, 3}B = {3, 4}
ORに対応する和集合は、AまたはBの少なくとも一方に属する要素なので、A ∪ B = {1, 2, 3, 4}です。共通要素の3も含まれます。
一方、XORに対応する対称差は、AとBのどちらか一方だけに属する要素なので、A △ B = {1, 2, 4}です。両方に属する3は除かれます。
つまり、集合で対応を見ると、ORに対応する和集合は重なりを含み、XORに対応する対称差は重なりを除くのが重要な違いです。「AまたはB」と書かれていても、排他的であることが明示されていなければ、論理演算では通常のORを「少なくとも一方、または両方」と考えます。
差集合・補集合との対応
NOTは、ある条件の真偽を反転する演算です。集合では、x ∈ AにNOTを適用した「x ∉ A」が、集合Aの補集合A^cに対応します。
ただし、補集合は「何を全体とするか」が必要です。たとえば全体集合をUとすると、A^cはUの中でAに属さない要素の集合です。全体集合を決めずに「A以外のすべて」と考えると、範囲が曖昧になります。
差集合A \ Bは、「Aには属するがBには属さない」要素の集合です。論理式では、x ∈ A AND NOT(x ∈ B)のように、ANDとNOTの組み合わせで表せます。同じ全体集合Uのもとで補集合B^cを考えれば、A \ B = A ∩ B^cと表せます。
対応関係を使うときの注意点
論理演算と集合演算の対応を使うときは、「何を真偽条件にしているか」を明確にすることが重要です。この記事では、x ∈ Aとx ∈ Bという所属条件を真偽値として扱っています。
また、ORとXORは区別が必要です。和集合に対応するORはinclusive ORであり、両方の条件が真でも真です。XORはどちらか一方だけが真の場合に真で、集合では対称差に対応します。
プログラミング言語の論理演算子やビット演算子、SQLのUNIONやJOINなどは、それぞれ固有の仕様を持ちます。名称が似ているだけで集合演算と機械的に一対一対応させず、その場面で何を入力し、何を結果として返す演算なのかを確認してください。
まとめ
AND・OR・NOT・XORなどの論理演算は真偽値を扱い、集合演算は集合を扱うため、両者は同じ種類の演算ではありません。ただし、要素xについてx ∈ Aとx ∈ Bを真偽条件として考えると、ANDは積集合、ORは和集合、NOTは補集合、XORは対称差、ANDとNOTの組み合わせは差集合に対応します。
特にORとXORは、両方の条件が真のときに結果が分かれます。集合で対応を見ると、ORに対応する和集合は重なりを含み、XORに対応する対称差は重なりを除くと理解すると、両者の関係を整理しやすくなります。
関連記事
