Spring 2001

Dirk Schlimm

Homework No.9

Thursday, March 22, 2001
Due Tuesday, April 3, 2001

1. Logical equivalence (1 point)

Read FOL, pages 44-46 (Section 3.5). Do the following problem:

• Page 46, Problem 9.

2. Satisfiability and logical truth (3 points)

Read FOL, pages 51-64 (Sections 3.7-3.8). Do the following problems:

• Page 55, Problem 18.
• Page 65, Problem 29.
(For an example of how the proof should look like, consult the proof of "Small(c)" on page 61.)

3. Alternative notation (1 point)

Read FOL, pages 88-90 (Section 3.12). The "Polish notation" should remind you of the axiomatization of sentential logic in Handout #16!
Do the following problem:

• Page 90, Problem 63.

4. Reflections (5 points)

Imagine you ware at home over spring break and you met your older sister who is a graduate student of physics at MIT. After you told her that you are attending a course on the nature of mathematical reasoning, she says: "Well, I know what the nature of mathematical reasoning is - it's calculating. The Greeks started it 500 years ago with simple equations, and now we have differential equations and computer programs like Maple or Mathematica to solve them. It has become a zillion times more complex, but basically it's still the same thing." What would you reply to her? Write a few paragraphs.