Discrete Structures
HW #4
Last Update: 4 February 2009
Note:
or
material is highlighted

Reminder: Each HW problem solution should consist of:
 a restatement of the entire problem (you may copy it word for word),
 followed by a complete solution with all intermediate steps shown.
REMINDER: NAME, DATE, RECITATION SECTION AT TOP RIGHT OF
EACH PAGE;

STAPLE MULTIPLE PAGES

All exercises are from §1.4 (nested quantifiers) and §1.5
(rules of inference).
 p. 59: #10 a, b, c, d, e
 Translate English sentences into FOL.
 Be sure to give the syntax and semantics of any new
terms that you have to introduce.
 3 points each; total = 15 points
 p. 60: #14 a, b, e
 Ditto, but now you have to supply your own predicates.
 To do that, you must give the syntax and semantics of the
predicates you choose.

E.g.: Dog(x) = x is a dog
Loves(x,y) = x loves y
 3 points each; total = 9 points
Suggestion: #60e is ambiguous; interpret it to mean that
the student has taken all the courses that are offered by a
single department.
 p. 60: #20 a, b
 Ditto
 3 points each; total = 6 points

Below are 5 short arguments in English.
 For each part, first give the syntax and semantics of
translations of each sentence into the language of propositional logic;
e.g., K = "Kangaroos live in Australia."
 Then write each argument in your propositional language.
 Finally, state the rule of inference that validates each
argument.
 If Australia is a continent, then it is also an island.
If it is an island, then it is completely surrounded by water.
Therefore, If Australia is a continent, then it is completely
surrounded by water.
 Either New Zealand is a continent or Australia is
a continent. New Zealand is not a continent. Therefore,
Australia is a continent.
 Australia is an island and a continent. Therefore,
it is a continent.
 Europe is an island and a continent. If Europe is an island
and a continent, then so is Australia. Therefore, Australia is
an island and a continent.
 Australia is an island. Therefore, either Australia
is an island, or I'm a monkey's uncle.
 Which, if any, of these arguments are valid? Why?
 2+2=5
(2+2=5) → (2 is an odd integer)
Therefore, 2 is an odd integer.

If this is margarine, then I'm a monkey's uncle.
I am a monkey's uncle.
Therefore, this is margarine.
Grand total = 51 points.
Tentative grading scheme:
A 49  51
A 46  48
B+ 44  45
B 41  43
B 38  40
C+ 35  37
C 29  34
C 24  28
D+ 18  23
D 10  17
F 0  9
DUE: AT THE BEGINNING OF LECTURE, FRIDAY!, FEBRUARY 13 
Copyright © 2009 by
William J. Rapaport
(rapaport@cse.buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/S09/hw04.html200902023