問82
頻出度★★☆
排他的論理和を表す論理式はどれか。ここで，論理変数AとBに対する排他的論理和の真理値表は次のように表される。また，ANDは論理積，ORは論理和，NOTは否定を表す。
| A | B | 排他的論理和 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
平成25年度 春期 ITパスポート試験 問82
テクノロジ系基礎理論 › 離散数学
This question's explanation and your answers so far.
解説
問 82
Incorrectア
(A OR B) AND (A OR (NOT B)) can be factored by the distributive law into A OR (B AND (NOT B)). Since B AND (NOT B) is always 0, this expression is in the end the same as A, that is, an expression that does not refer to the value of B at all. Checking against the truth table: for A=0 and B=0 it is 0 (the table is also 0, a match); for A=0 and B=1 it is 0 (the table is 1, a mismatch); for A=1 and B=0 it is 1; and for A=1 and B=1 it is 1 (the table is 0, a mismatch), so 2 of the 4 rows disagree with the table. The exclusive OR is an operation that treats A and B equally, so an expression in which one of the variables disappears cannot be a candidate.
- イ
正解 The correct answer is イ, “(A OR B) AND ((NOT A) OR (NOT B))”. The exclusive OR (XOR) shown in the truth table is an operation that becomes 1 only when A and B differ, that is, only when “exactly one of them is 1”. This condition can be broken down into two conditions that hold at the same time. The first is “at least one of them is 1”, which is A OR B. The second is “not both of them are 1”, which is NOT(A AND B), and by De Morgan's law it can be written as (NOT A) OR (NOT B). Joining these two with a logical AND gives (A OR B) AND ((NOT A) OR (NOT B)), which means “at least one is 1, and not both are 1” = exactly one is 1, in other words the exclusive OR. Checking by actually substituting all four rows of the truth table: when A=0 and B=0, (0 OR 0)=0, so the whole expression is 0; when A=0 and B=1, (0 OR 1)=1 and ((NOT 0) OR (NOT 1))=(1 OR 0)=1, so the whole expression is 1; when A=1 and B=0, (1 OR 0)=1 and ((NOT 1) OR (NOT 0))=(0 OR 1)=1, so the whole expression is 1; and when A=1 and B=1, (1 OR 1)=1 but ((NOT 1) OR (NOT 1))=(0 OR 0)=0, so the whole expression is 0. The results 0, 1, 1, 0 match the exclusive OR column of the table exactly.
Incorrectウ
In ((NOT A) OR B) AND (A OR (NOT B)), the first half means “if A is 1, then B is also 1” and the second half means “if B is 1, then A is also 1”, so as a whole it is an expression that becomes 1 when A and B are equal, that is, coincidence (the negation of the exclusive OR, XNOR). Substituting the values: for A=0 and B=0 it is 1 AND 1 = 1 (the table is 0); for A=0 and B=1 it is 1 AND 0 = 0 (the table is 1); for A=1 and B=0 it is 0 AND 1 = 0 (the table is 1); and for A=1 and B=1 it is 1 AND 1 = 1 (the table is 0), so all four rows take exactly the opposite value from the table. It has exactly the opposite meaning of the answer, which makes it the most confusing wrong choice.
Incorrectエ
((NOT A) OR B) AND ((NOT A) OR (NOT B)) can be factored by the distributive law into (NOT A) OR (B AND (NOT B)), and since B AND (NOT B) is always 0, it ends up being the same expression as NOT A. As with ア, B has no effect on the result. Substituting the values: for A=0 and B=0 it is 1 (the table is 0, a mismatch); for A=0 and B=1 it is 1 (the table is also 1, a match); for A=1 and B=0 it is 0 (the table is 1, a mismatch); and for A=1 and B=1 it is 0 (the table is also 0, a match), so 2 of the 4 rows disagree with the table.
ここがポイント
- The definition and truth table of the exclusive OR (XOR): an operation that is 1 only when A and B differ and 0 when they are the same. Rewritten with the three basic operations it is (A OR B) AND NOT(A AND B), and applying De Morgan's law NOT(A AND B) = (NOT A) OR (NOT B) gives the form (A OR B) AND ((NOT A) OR (NOT B)). Restating it in everyday words as “at least one is 1” and “not both are 1” first, and only then turning it into an expression, is the reliable way to solve it.
- When checking whether each choice is right or wrong, the most reliable approach is to substitute all four combinations of A and B (0/0, 0/1, 1/0, 1/1) and compare them with the table. In addition, if you know that X AND (NOT X) is always 0, that X OR (NOT X) is always 1, and the distributive law (X OR Y) AND (X OR Z) = X OR (Y AND Z), you can immediately spot expressions like ア and エ in which one of the variables disappears and the expression becomes just A or NOT A, which saves a great deal of calculation.
用語