MATH 1090.03D

Fall 2000

▶ Date posted: Nov. 20, 2000

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

Alternative Problem Set No. 4—On Chapters 3, 4 and 9 of “GS”. See also our “Web–Ch.1, and “Basic Equational Logic” report (on the Web).

This problem set is an alternative set to the one collected today (Nov. 20, 2000).

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 #4 will be accepted. Please ignore this problem set IFF you have already handed in the original problem set #4.

In the following problems you are expected to use the Deduction Theorem to your “full advantage”.

Do not use the Tautology theorem, but you can use all the other “tools” we have learned (e.g., modus ponens, cut, combine/split hypotheses—that is, “A, B, C ⊢ D iff A ∧ B ∧ C ⊢ D”—resolution, etc.)

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 3.

p.66, problems 3.76, 3.77, 3.78, 3.79, 3.80, and 3.81.

For the following use a combination of Deduction Theorem and cut-rule:

• p.122, problems 6.3, 6.4, 6.6.

The following are on Predicate Calculus:

• Problems 9.4, 9.6, 9.10.