 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/logic-and-proof/1/a/solution

Apply the distributive law of Boolean algebra to the two logical conjunctions. With

A = P

B = \neg Q

C = \neg P

, and

D = Q

, the identity

(A \land B) \lor (C \land D) \equiv (A \lor C) \land (A \lor D) \land (B \lor C) \land (B \lor D)

gives

(P \land \neg Q) \lor (\neg P \land Q) \equiv (P \lor \neg P) \land (P \lor Q) \land (\neg Q \lor \neg P) \land (\neg Q \lor Q) \equiv ⊤ \land (P \lor Q) \land (\neg P \lor \neg Q) \land ⊤ \equiv (P \lor Q) \land (\neg P \lor \neg Q) .

The second step uses complementation and commutativity in Boolean algebra; the last uses the identity law for logical conjunction. The result is in conjunctive normal form: its first Boolean clause requires at least one input to be true, and its second Boolean clause prohibits both inputs being true. Together they express exclusive or.

 New to topics? Read the docs here!