MATH 1090.03D

Fall 2000

▶ Date posted: Dec. 5, 2000

▶ Due: TBA by Web announcement immediately following the end of the CUPE strike.

Alternative Problem Set No. 5—On Chapter 9 of “GS”. See also our “Basic Equational Logic” report (on the Web).

This problem set is an alternative set to the one collected on Dec. 5, 2000 (for

which solutions were posted on the same day).

It is ONLY FOR THOSE students who exercised their right of choice not to cross the picket lines, and therefore did not attend classes during the strike.

Only ONE problem set #5 will be accepted. Please ignore this problem set IFF you have already handed in the original problem set #5.

In the following problems you can use any tools that we have (e.g., Calculational/Equational proofs, Modus Ponens, Generalization/Specialization, Hilbertstyle proofs, Post’s Theorem, Deduction Theorem, Proof by contradiction, Monotonicity, etc.). Before you start a proof, think about the problem and choose the most convenient approach.

You should remember (and use, when appropriate) the following fact from class:

A ≡ B ⊢ A ⇒ B and A ≡ B ⊢ B ⇒ A

and

A ⇒ B, B ⇒ A ⊢ A ≡ B

which means that to prove Γ ⊢ A ≡ B you can do so by proving two things: Γ ⊢ A ⇒ B and Γ ⊢ B ⇒ A.

• Do the following problems from the text, Chapter 9.

• 9.18, 9.20, 9.22, 9.23, 9.25, 9.27.

Also prove: •

⊢ (∀x)A ∧ (∀y)B ≡ (∀x)(∀y)(A ∧ B)

provided x is not free in B and y is not free in A • Let P be a predicate of arity 1 and Q a predicate of arity 2. To which axiom

groups, if any, do each of the following formulas belong?

(∀y)((∀x)(P (x) ⇒ P (x)) ⇒ (P (c) ⇒ P (c)))

(∀x)(∃y)Q(x, y) ⇒ (∃y)Q(y, y)

• Let P be a predicate of arity 1. Prove or disprove:

⊢ (((∀x)P (x) ⇒ (∀y)P (y)) ⇒ P (z)) ⇒ ((∀x)P (x) ⇒ ((∀y)P (y) ⇒ P (z)))

• Prove:

⊢ (∀x)(A ⇒ B) ∧ (∃x)A ⇒ (∃x)B