O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 images and images are in Prop, then so are (¬images) and (images) —where I used Images 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): imagesimages, imagesimages ⊢ ⋁ → ⋁ .

  3. Let us prove ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required