 Solution

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

Use structural induction on the formation of a propositional formula. A propositional variable has no parentheses. Applying negation to a logical formula adds no parentheses, so preserves equality of the two counts. If

ψ

and

χ

each have equally many opening and closing parentheses, the formation of

(ψ \to χ)

adds one of each to their combined counts. Thus every propositional formula satisfies

# opening parentheses = # closing parentheses .

This is a necessary condition for being a logical formula; it is not sufficient, since the logical connectives and the placement of symbols must also follow the formation rules.

 New to topics? Read the docs here!