Discrete Structures

# HW #7 — §1.6: Proofs

 Last Update: 22 October 2010 Note: or material is highlighted

All exercises come from, or are based on exercises from, the Rosen text.

Each HW problem's solution should consist of:

All solutions must be handwritten.

 PUT YOUR NAME, DATE, RECITATION SECTION, & "HW #7" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

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:

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

```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
```

 DUE: AT THE BEGINNING OF LECTURE, FRI., OCT. 29