金   It is worth remembering (from the course outline):

The homework must be each individual’s own work. While consultations with the instructor, tutor, and among students, are part of the learning process and are encouraged, nevertheless, at the end of all this consultation each student will have to produce an individual report rather than a copy (full or partial) of somebody else’s report.

The concept of “late assignments”does not exist in this course.

金

1.  (2 MARKS) Prove that the complexity of a well-formed-formula equals the number of its left brackets.

Hint. Analyse formula-constructions, or use induction on formulas.

2.   (a)  (3 MARKS) Prove that (⊥) is not a wff.

(b)  (2 MARKS) Why would Induction on complexity (or equivalently

on formulas) be not applicable in this problem?

Hint.  One way to address (a) is to analyse formula-constructions.  The other is to look at the inductive definition of formulas, as it would be applied to“(⊥)”.

3.  (1 MARK) Prove that (((q → p) → q) → q) is a wff.

4.  (6 MARKS) Recall that a schema is a tautology iff all its instances are tautologies.

Which of the following six schemata are tautologies?  Show the whole process that led to your answers, including truth tables or equivalent short cuts, if you used one or the other, and words of explanation.

I note that in the six sub- questions below I am not using all the formally necessary brackets.  You need to reinsert missing brackets to answer cor- rectly.

金   Therefore be mindful of connective priorities and associativities!

金

• A → B → (A → ⊥) ∨ B

•  (A → B) → (A → ⊥) ∨ B

• A ∧ B → A ≡ B

• A → B → ¬B → ¬A

•  (A → B) → ¬B → ¬A

• A ∧ B → A → B

5.  (3 MARKS) Prove that if we have A |=taut  ⊥ , then we also have A |=taut  B for every B  .

6.  (6 MARKS) By using truth tables, or using related shortcuts, examine whether or not the following tautological implications are correct.

金   

case that is incorrect (since some other special cases might work).

金