MATH 1090.03D

Fall 2000

Date: Nov. 1, 2000

Due: Nov. 15, 2000—▶In class—NO papers will be accepted after 11:45am◀

Problem Set No. 4—On Chapters 3, 4 and 9 of “GS”.

There will be one more problem set (#5), that I will post on November 15, 2000.

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.61, prove the statements labeled 3.84 (b) and (c) (We have done (a) in class) p.66, problems 3.77, 3.78, 3.80, 3.81, 3.83 (this is easiest if you use an equational

proof!), and 3.84.

For the following use a combination of Deduction Theorem and resolution:

• p.122, problems 6.6, 6.7, 6.8.

The following are on Predicate Calculus:

• Problems 9.1, 9.2, 9.3.