Solution

ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2008/a/1/e/iii/solution

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. Thus
The 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!