問82
頻出度★★☆
排他的論理和を表す論理式はどれか。ここで，論理変数AとBに対する排他的論理和の真理値表は次のように表される。また，ANDは論理積，ORは論理和，NOTは否定を表す。
| A | B | 排他的論理和 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
平成25年度 春期 ITパスポート試験 問82
テクノロジ系基礎理論 › 離散数学
この問題の解説と、これまでの解答の記録です。
解説
問 82
不正解ア
(A OR B) AND (A OR (NOT B)) は、分配法則でくくると A OR (B AND (NOT B)) となる。B AND (NOT B) は常に0なので、この式は結局 A と同じ、すなわち B の値をまったく参照しない式である。真理値表で確かめると A=0・B=0 は0 (表も0で一致)、A=0・B=1 は0 (表は1なので不一致)、A=1・B=0 は1、A=1・B=1 は1 (表は0なので不一致) となり、4行中2行で表と食い違う。排他的論理和は A と B を対等に扱う演算なので、片方の変数が消えてしまう式は候補になり得ない。
- イ
正解 正解はイ「(A OR B) AND ((NOT A) OR (NOT B))」。真理値表が示す排他的論理和 (XOR) は、AとBが異なるとき、すなわち「ちょうど一方だけが1」のときだけ1になる演算である。この条件は2つの条件の同時成立に分解できる。1つ目は「少なくとも一方が1」で、これは A OR B。2つ目は「両方とも1ではない」で、これは NOT(A AND B)、ドモルガンの法則により (NOT A) OR (NOT B) と書ける。この2つを論理積で結んだ (A OR B) AND ((NOT A) OR (NOT B)) が「少なくとも一方が1、かつ両方が1ではない」= ちょうど一方だけが1、つまり排他的論理和になる。実際に真理値表の4行すべてを代入して確かめると、A=0・B=0 では (0 OR 0)=0 なので全体は0、A=0・B=1 では (0 OR 1)=1 と ((NOT 0) OR (NOT 1))=(1 OR 0)=1 で全体は1、A=1・B=0 では (1 OR 0)=1 と ((NOT 1) OR (NOT 0))=(0 OR 1)=1 で全体は1、A=1・B=1 では (1 OR 1)=1 だが ((NOT 1) OR (NOT 1))=(0 OR 0)=0 なので全体は0となり、0・1・1・0 と表の排他的論理和の列に完全に一致する。
不正解ウ
((NOT A) OR B) AND (A OR (NOT B)) は、前半が「A が1ならB も1」、後半が「B が1ならA も1」を表すので、全体としては A と B が等しいときに1になる式、すなわち一致 (排他的論理和の否定、XNOR) である。代入すると A=0・B=0 は 1 AND 1 = 1 (表は0)、A=0・B=1 は 1 AND 0 = 0 (表は1)、A=1・B=0 は 0 AND 1 = 0 (表は1)、A=1・B=1 は 1 AND 1 = 1 (表は0) となり、4行すべてで表と正反対の値になる。答えとちょうど逆の意味を持つ、最も紛らわしい誤答である。
不正解エ
((NOT A) OR B) AND ((NOT A) OR (NOT B)) は、分配法則でくくると (NOT A) OR (B AND (NOT B)) となり、B AND (NOT B) が常に0なので結局 NOT A と同じ式になる。アと同様に B が結果に影響しない。代入すると A=0・B=0 は1 (表は0で不一致)、A=0・B=1 は1 (表も1で一致)、A=1・B=0 は0 (表は1で不一致)、A=1・B=1 は0 (表も0で一致) となり、4行中2行で表と食い違う。
ここがポイント
- 排他的論理和 (XOR) の定義と真理値表: AとBが異なるときだけ1、同じときは0になる演算。基本の3演算で書き直すと (A OR B) AND NOT(A AND B) であり、ドモルガンの法則 NOT(A AND B) = (NOT A) OR (NOT B) を使うと (A OR B) AND ((NOT A) OR (NOT B)) という形になる。「少なくとも一方が1」かつ「両方が1ではない」と日本語で言い換えてから式に直すのが確実な解き方。
- 選択肢の真偽を確かめるときは、A と B の4通り (0・0/0・1/1・0/1・1) をすべて代入して表と突き合わせるのが最も確実。加えて、X AND (NOT X) は常に0、X OR (NOT X) は常に1、分配法則 (X OR Y) AND (X OR Z) = X OR (Y AND Z) を知っていると、アとエのように片方の変数が消えて単なる A や NOT A になる式をその場で見抜け、計算を大幅に省ける。
用語