Theory of Computation

1.8  ADDITIONAL EXERCISES

  1. Let us first define: The set of propositional formulae of, say, set theory, denoted here by Prop, is the smallest set such that

(1) Every Boolean variable is in Prop (cf. 1.1.1.26)

(2) If and are in Prop, then so are (¬) and () —where I used as an abbreviation of any member of {⋀, ⋁, →, ≡}.

If we call WFF the set of all formulae of set theory as defined in 1.1.1.3, then show that WFF = Prop.

Hint. This involves two structural inductions, one each over WFF and Prop.

  2. Prove the general case of proof by cases (cf. 1.1.1.48): → , → ⊢ ⋁ → ⋁ .

  3. Let us prove ...