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).

1. 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

2. 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.

3. p. 60: #20 a, b

• Ditto
• 3 points each; total = 6 points

4. 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.

1. 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.

2. Either New Zealand is a continent or Australia is a continent. New Zealand is not a continent. Therefore, Australia is a continent.

3. Australia is an island and a continent. Therefore, it is a continent.

4. 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.

5. Australia is an island. Therefore, either Australia is an island, or I'm a monkey's uncle.

5. Which, if any, of these arguments are valid? Why?

1. 2+2=5
(2+2=5) → (2 is an odd integer)
Therefore, 2 is an odd integer.

2. 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.

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