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

Repeated use of

U \to V \equiv \neg U \lor V

yields

φ_{n} \equiv \neg A_{n} \lor \neg A_{n - 1} \lor \dots \lor \neg A_{2} \lor A_{1} .

This logical disjunction is false exactly when

A_{2}, \dots, A_{n}

are all true and

A_{1}

is false. There is precisely one such Boolean valuation out of the

2^{n}

assignments to the

n

independent propositional variables. Thus the number of satisfying assignments is $2^{n} - 1$ . This is the satisfying-assignment count for nested implications; the implication brackets associate to the right here.

 New to topics? Read the docs here!