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 
 (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]
 (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.
 (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.
 (3 points)
p. 85: 22
 Suggestion:
 You do not have to try to state this in FOL.
Total points = 33
Tentative grading scheme:
A 3233
A 3031
B+ 2829
B 2627
B 2425
C+ 2223
C 1921
C 1618
D+ 1215
D 711
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 screencaptures 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.html201010193