基本論理演算のAND (論理積)、OR (論理和)、NOT (否定) を用いて構成した次の式のうち、排他的論理和 (XOR) となる式として、最も適切なものはどれか。
なお、
a AND b を AND (a, b)、
a OR b を OR (a, b)、
NOT a を NOT (a)
と表現する。
① XOR(a, b) = AND(OR(a, NOT(b)), OR(NOT(a), b))
② XOR(a, b) = OR(AND(a、NOT(b)), AND(NOT(a)、b))
③ XOR(a, b) = AND(OR(a, b)、OR(a, b))
④ XOR(a, b) = OR(AND(a, b), AND(a, b))
⑤ XOR(a, b) = NOT(AND(a, OR(a, b)))
②
排他的論理和は、a, b の値が異なる時に1となる。
XOR(0, 0) = 0
XOR(0, 1) = 1
XOR(1, 0) = 1
XOR(1, 1) = 0
① XOR(0, 0) = AND(OR(0, NOT(0)), OR(NOT(0), 0))
= AND(OR(0, 1), OR(1, 0))
= AND(1, 1) = 1 となる。
ちなみに選択肢の論理式は、排他的論理和の否定である。
② 正しい。便宜上、NOT(X) = X と表記とし、
AND(a, b) を c と置くと
OR(AND(a, b), AND(a, b)) = OR(AND(a, b), c)
ド・モルガンの法則より
(Ａ ∩ Ｂ) ∪ Ｃ ＝ (Ａ ∪ Ｃ) ∩ (Ｂ ∪ Ｃ)、すなわち
OR(AND(A, B), C) = AND(OR(A, C), OR(B, C))が成り立つから
OR(AND(a, b), c)
= AND(OR(a, c), OR(b, c)
= AND(OR(a, AND(a, b)), OR(b, AND(a, b))
= AND(AND(OR(a, a), OR(a, b)), AND(OR(b, a), OR(b, b)))
= AND(OR(a, b), OR(b, a))
= AND(OR(a, b), OR(a, b))
とも変形できる。
③ XOR(1, 1) = AND(OR(1, 1)、OR(1, 1))
= AND(1, 1) = 1 となる。
④ XOR(1, 1) = OR(AND(1, 1), AND(1, 1))
= OR(1, 1) = 1 となる。
⑤ XOR(0, 0) = NOT(AND(0, OR(0, 0)))
= NOT(AND(0, 0)) = NOT(0) = 1 となる。
| Ⅲ－４ | 目次 | Ⅲ－６ |