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

Eliminating logical implications givesAn absorption step simplifies this to the disjunctive normal formEach one-literal term is a permitted logical conjunction in a disjunctive normal form.

The given logical implication is false exactly when $A=B$ and $C\ne D$. For every literal on $A,B,C,D$, there is such a false Boolean valuation making that literal true. For a prescribed value of $A$ or $B$, give the other the same value and choose $C\ne D$. For a prescribed value of $C$ or $D$, give the other the opposite value and choose $A=B$.

Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term $\ell$, then every Boolean valuation satisfying $\ell$ would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.

Use structural induction on the propositional formula. The induction claim is that its truth value under the all-one Boolean valuation is one. A variable has this truth value by definition. For the induction step, suppose the immediate subformulas $\alpha ,\beta$ each have truth value one. ThenThese are all permitted construction cases. Thus every such propositional formula evaluates to one. Equivalently, the three logical connectives define one-preserving Boolean functions, and composition preserves this property. The variable-only base grammar matters: admitting a constant false formula would invalidate the claim.

Let $F=(A\to C)\vee (B\to C)$ and $H=(A\vee B)\to C$, so the two displayed propositional formulas are $\phi =F\to H$ and $\psi =H\to F$. Their complete truth tables areTherefore $\psi$ is a tautology; $\phi$ 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.

Only $\psi$ requires a natural deduction proof. Assume $h:(A\vee B)\to C$. Within that assumption, temporarily assume $a:A$. By disjunction introduction, obtain $A\vee B$; applying $h$ by the implication elimination rule gives $C$. Discharge $a$ by the implication introduction rule to derive $A\to C$. Disjunction introduction now gives $(A\to C)\vee (B\to C)$. Finally discharge $h$ by the implication introduction rule:All temporary assumptions are discharged. No classical rule is needed; the same proof works in Intuitionistic propositional logic. The false propositional formula $\phi$ has no proof in this sound natural deduction system.