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

Reading the abstract syntax tree recursively gives the eight distinct subformulas

A, B, C, \neg A, \neg B, C \to \neg A, \neg B \land (C \to \neg A), A \lor (\neg B \land (C \to \neg A)) .

A subformula includes the complete propositional formula itself as well as the operands of its connectives. There are nine occurrences in the abstract syntax tree, because the atomic formula

A

occurs twice, but only eight different propositional formulas in the set.

 New to topics? Read the docs here!