ITパスポート試験 ITパスポート 2013年 (平成25年 春期) 問82: 排他的論理和を表す論理式はどれか。ここで,論理変数AとBに対する排他的論理和の真理値表は次のように表される。また,ANDは論理積,ORは論理和,NOTは否定を表

問題本文

排他的論理和を表す論理式はどれか。ここで,論理変数AとBに対する排他的論理和の真理値表は次のように表される。また,ANDは論理積,ORは論理和,NOTは否定を表す。

選択肢

• ア.(A OR B) AND (A OR (NOT B))
• イ.(A OR B) AND ((NOT A) OR (NOT B))
• ウ.((NOT A) OR B) AND (A OR (NOT B))
• エ.((NOT A) OR B) AND ((NOT A) OR (NOT B))

正解

イ. (A OR B) AND ((NOT A) OR (NOT B))

解説

排他的論理和(XOR)は2入力のうちちょうど一方が1のときだけ1を返す論理演算で,真理値表は(A,B)=(0,0)→0,(0,1)→1,(1,0)→1,(1,1)→0.これを論理式で表すと(A AND NOT B) OR (NOT A AND B)が最も直接的だが,他の同値表現として(A OR B) AND ((NOT A) OR (NOT B))も成り立つ:前者は「Aが1またはBが1」(両方0でない)と「Aが0またはBが0」(両方1でない)の論理積で,結果として「ちょうど片方が1」の状態を表す.以上から正解はイ.ア・ウ・エは真理値表を満たさない論理式.XORの複数表現は論理回路設計でも頻出.

選択肢ごとの解説

• ア.(A OR B) AND (A OR (NOT B))を整理すると,Aが1のとき結果は1,A=0のときは(B)AND(NOT B)=0となる.つまりAが1のとき1・Aが0のとき0でこれはA自身.排他的論理和の真理値表(0,0→0,1,1→0,異なれば1)と一致しないため誤り.真理値計算で結果がAと等価.
• イ.正解.(A OR B) AND ((NOT A) OR (NOT B))を真理値表で確認:(0,0)→0 AND 1=0,(0,1)→1 AND 1=1,(1,0)→1 AND 1=1,(1,1)→1 AND 0=0.排他的論理和の真理値表(同じなら0,異なれば1)と完全に一致する.「少なくとも一方が1」かつ「少なくとも一方が0」の論理積として正しく表現できる.
• ウ.((NOT A) OR B) AND (A OR (NOT B))は,(0,0)→1 AND 1=1,(0,1)→1 AND 0=0,(1,0)→0 AND 1=0,(1,1)→1 AND 1=1となる.これは「同じなら1,異なれば0」を表す同値(NXOR・否定排他的論理和)で,排他的論理和とは真逆の真理値表を持つため誤り.符号が反転している.
• エ.((NOT A) OR B) AND ((NOT A) OR (NOT B))=(NOT A) OR (B AND NOT B)=(NOT A) OR 0=NOT A.結果はNOT Aと等価で,排他的論理和の真理値表とは一致しない.真理値表(0,0)→1,(0,1)→1,(1,0)→0,(1,1)→0となりこれはNOT Aそのものであり,XORには該当せず誤り.