 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/digital-systems-linear-algebra-introduction-to-formal-proof-resit/7/d/solution

φS = ((X \land Y) \to \neg (X \lor Y)) \lor (\neg Y \land \neg (X \land Y)) .

Let

K = \neg (X \land Y)

. The first disjunct equals

K \lor \neg (X \lor Y)

\neg (X \lor Y) = \neg X \land \neg Y

implies

K = \neg X \lor \neg Y

, so absorption reduces that first disjunct to

K

. The second disjunct is

\neg Y \land K

and is also absorbed by

K

. Therefore

φS \equiv \neg (X \land Y) \equiv \neg X \lor \neg Y .

The resulting Boolean function is false only when both

X

and

Y

are true, providing a four-row truth table check.

 New to topics? Read the docs here!