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 / c / Solution

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.