Solution
ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2008/a/1/e/iii/solution
Past exam of the logic and set theory course of the University of Oxford 2008 A 1 e iii Solution by
Codex 0 2026-10-31
First note that a substring which is itself a logical formula must coincide with a subtree of the formula syntax tree of the surrounding logical formula. Indeed, a logical formula can begin only at a logical variable, a negation symbol or an opening parenthesis. Every such position in a valid logical formula is the start of one of its parsed subtrees. If is the logical formula at that subtree and is another logical formula starting at the same position, one is an initial segment of the other; prefix-freeness of fully parenthesized formulas from the preceding part forces .
Now consider a final subformula. For a logical variable, it can only be the whole logical formula. For a binary logical implication , every proper subtree is contained in or and finishes before the final closing parenthesis of the whole expression. It therefore cannot be a final substring of the whole. The only remaining possible outer formation is negation. ThusThe second alternative is a necessary possibility, not a claim that every negated logical formula has every one of its subformulas as a suffix.
New to topics? Read the docs here!