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

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

Text copyright © 2010 by William J. Rapaport (rapaport@buffalo.edu)
Cartoon links and screen-captures appear here for your enjoyment. They are not meant to infringe on any copyrights held by the creators. For more information on any cartoon, click on it, or contact me.
http://www.cse.buffalo.edu/~rapaport/191/F10/hw07.html-20101019-3