HW #7 — §1.6: Proofs

All solutions must be handwritten.

1. (9 points)

   p. 85: 6

   • You are asked to prove a proposition.
     • First, state it in FOL (3 points)
     • Let the domain be Z, and be sure to give your syntax & semantics (3 points).
     • Then prove it (3 points). You may do it formally or informally.

   • Hint: Odd(n) =def ∃x[n = 2x + 1]

   ---

2. (9 points)

   p. 85: 16

   • You are asked to prove the proposition that we appealed to in our proof that ¬Q(√2).
     • First, state it in FOL (3 points)
     • Let the domain be Z, and be sure to give your syntax & semantics (3 points).
     • Then prove it (3 points). You may do it formally or informally.

   • Suggestion: Try Proof by Contraposition
   • Hint: You may appeal to problem #6, above.

   ---

3. (12 points)

   p. 85: 18 a–b

   • You are asked to prove a proposition in 2 different ways.
     • First, state it in FOL (3 points);
     • Let the domain be Z, and be sure to give your syntax & semantics (3 points);
     • Then prove it in 2 different ways (3 points each; total = 6 points). You may do it formally or informally.

   ---

4. (3 points)

   p. 85: 22

   • Suggestion:
     The instructor's answer manual suggests using Proof by Contradiction.

     But I think you might find it easier to try using Proof by Cases (see pp. 86–90).

   • You do not have to try to state this in FOL.

Total points = 33

Tentative grading scheme:

A       32-33
A-      30-31
B+      28-29
B       26-27
B-      24-25
C+      22-23
C       19-21
C-      16-18
D+      12-15
D        7-11
F        0- 6