A Level Computer Science 9618: Deriving XNOR from XOR Using De Morgan's Laws

The exclusive-OR (XOR) of two single-bit inputs A and B can be written as the Boolean expression A XOR B = A.NOT B + NOT A.B.

(a) Starting from NOT(A XOR B) = NOT(A.NOT B + NOT A.B), apply De Morgan's laws to remove the NOT from outside each bracket, so that no NOT is applied to a bracketed term. Show each application of the law. [2]

(b) Continue simplifying your answer to part (a), using the distributive law and the complement law, to show that NOT(A XOR B) = A.B + NOT A.NOT B. Show each step and name the law used at each step. [3]

(c) Complete a truth table showing A XOR B and NOT(A XOR B) for all four combinations of A and B, and confirm that your simplified expression from part (b) gives the same values as the NOT(A XOR B) column in every row. [3]

Part (a): Applying De Morgan’s laws

De Morgan’s laws state:

NOT(X + Y) = NOT X . NOT Y
NOT(X . Y) = NOT X + NOT Y

Starting from NOT(A XOR B) = NOT(A.NOT B + NOT A.B), first apply the OR form of De Morgan’s law to the outer NOT, with X = A.NOT B and Y = NOT A.B:

NOT(A.NOT B + NOT A.B) = NOT(A.NOT B) . NOT(NOT A.B)

This still has a NOT applied to each bracketed term, so apply the AND form of De Morgan’s law to each bracket in turn:

NOT(A.NOT B) = NOT A + NOT(NOT B) = NOT A + B      [AND form of De Morgan's law, then double negation NOT(NOT B) = B]
NOT(NOT A.B) = NOT(NOT A) + NOT B = A + NOT B      [AND form of De Morgan's law, then double negation NOT(NOT A) = A]

Combining these:

NOT(A XOR B) = (NOT A + B).(A + NOT B)

No NOT is now applied to a bracketed term. [2 marks: 1 for correctly applying the OR form of De Morgan’s law to the outer NOT, 1 for correctly applying the AND form of De Morgan’s law to both inner brackets, including simplifying the double negations NOT(NOT A) = A and NOT(NOT B) = B]

Part (b): Expanding and simplifying

Starting from (NOT A + B).(A + NOT B), expand using the distributive law, multiplying out every pair of terms:

(NOT A + B).(A + NOT B) = NOT A.A + NOT A.NOT B + B.A + B.NOT B    [distributive law]

Two of these four terms cancel using the complement law (X.NOT X = 0):

NOT A.A = 0    [complement law]
B.NOT B = 0    [complement law]

Substituting these in and applying the identity law (X + 0 = X) to drop the zero terms:

NOT A.A + NOT A.NOT B + B.A + B.NOT B = 0 + NOT A.NOT B + A.B + 0    [complement law]
                                        = NOT A.NOT B + A.B           [identity law]
                                        = A.B + NOT A.NOT B           [commutative law, reordering terms]

So NOT(A XOR B) = A.B + NOT A.NOT B, as required. [3 marks: 1 for the fully correct four-term expansion using the distributive law, 1 for correctly cancelling both NOT A.A and B.NOT B to 0 using the complement law, 1 for the final correct expression A.B + NOT A.NOT B]

Part (c): Verifying with a truth table

Evaluating A XOR B, NOT(A XOR B), and the simplified expression A.B + NOT A.NOT B for all four combinations of A and B:

A	B	A XOR B	NOT(A XOR B)	A.B	NOT A.NOT B	A.B + NOT A.NOT B
0	0	0	1	0	1	1
0	1	1	0	0	0	0
1	0	1	0	0	0	0
1	1	0	1	1	0	1

Checking one row explicitly: for A = 0, B = 0, A XOR B = 0, so NOT(A XOR B) = 1; and A.B = 0.0 = 0, NOT A.NOT B = 1.1 = 1, so A.B + NOT A.NOT B = 0 + 1 = 1, this matches NOT(A XOR B) = 1.

The NOT(A XOR B) column reads 1, 0, 0, 1 and the A.B + NOT A.NOT B column also reads 1, 0, 0, 1, for AB = 00, 01, 10, 11 respectively. The two columns match in every row, confirming that the simplified expression from part (b) correctly represents NOT(A XOR B). This expression is also known as the XNOR (exclusive-NOR) function. [3 marks: 1 for the correct A XOR B column (0, 1, 1, 0), 1 for the correct NOT(A XOR B) column (1, 0, 0, 1), 1 for explicitly confirming that A.B + NOT A.NOT B matches the NOT(A XOR B) column in every row]

Final answers

(a) NOT(A XOR B) = (NOT A + B).(A + NOT B)
(b) (NOT A + B).(A + NOT B) expands and simplifies to A.B + NOT A.NOT B, so NOT(A XOR B) = A.B + NOT A.NOT B
(c) A XOR B = 0, 1, 1, 0 and NOT(A XOR B) = 1, 0, 0, 1 for AB = 00, 01, 10, 11; A.B + NOT A.NOT B gives the same values (1, 0, 0, 1), confirming the simplification (the XNOR function)