 Solution

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

Use

0

and

1

for false and true truth values. The truth table is:

$A$	$B$	$C$	$A \leftrightarrow B$	$\neg B \to C$	$φ$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$	$0$
$1$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$1$	$1$	$1$
$1$	$1$	$1$	$1$	$1$	$1$

The two satisfying rows with

A = B = 1

combine by eliminating

C

, while the remaining satisfying row has

A = B = 0, C = 1

. An equivalent disjunctive normal form is therefore

(A \land B) \lor (\neg A \land \neg B \land C) .

Expanding the logical biconditional into its two implications, and using

\neg B \to C \equiv B \lor C

(\neg A \lor B) \land (A \lor \neg B) \land (B \lor C) .

Each form has exactly the same three satisfying assignments as the original propositional formula.

 New to topics? Read the docs here!