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\vee V$ yieldsThis 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.