 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/7/d/solution

Let

F = (A \to C) \lor (B \to C)

and

H = (A \lor B) \to C

, so the two displayed propositional formulas are

φ = F \to H

and

ψ = H \to F

. Their complete truth tables are

A 00001111 B 00110011 C 01010101 A \to C 11110101 B \to C 11011101 F 11111101 H 11010101 φ 11010111 ψ 11111111

Therefore $ψ$ is a tautology; $φ$ is not. For example

(A, B, C) = (0, 1, 0)

makes the antecedent

F

true via

A \to C

, while

H

is false because

B

is true and

C

is false. This explains why having just one of the two logical implications is insufficient for the forward direction.

 New to topics? Read the docs here!