Discrete Structures

# HW #5

 Last Update: 13 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.5 (rules of inference).

1. p. 73: #10 a, d, f

You are given premises and need to find conclusions.

Hint:

• Translate each English sentence into either propositional logic or first-order logic.
• Then see what rules of inference can be applied.
(In some cases, more than one can be applied.)
• Finally, translate your conclusion(s) back into English.

• 3 points each; total = 9 points.

2. p. 73: #14 d

The text gives you an argument in English, and asks you to "explain which rules of inference are used for each step".

1. Translate the argument into FOL;
be sure to give the syntax and semantics of your representation.
2. Prove that the argument is valid;
be sure to justify each step as either being a premise or as following from previous steps by a rule of inference, as we have done in lecture.

• syntax & semantics: 3 points
• translation: 3 points
• proof steps: 3 points
• proof justifications: 3 points

total = 12 points

3. p. 73: #16 b

• You are given an argument in English and must determine whether it is valid. Do this as follows:

1. Translate the argument into first-order logic;
be sure to give the syntax and semantics of your representation.
2. Try to prove that it is valid, using rules of inference.
3. If you succeed, you're done.
4. If you get stuck, then try to show whether it is valid by using truth tables.

• syntax & semantics: 3 points
• translation: 3 points
• determination of validity: 6 points

total = 12 points

Grand total = 33 points.

```A          33
A-      31 - 32
B+      29 - 30
B       27 - 28
B-      25 - 26
C+      23 - 24
C       19 - 22
C-      16 - 18
D+      12 - 15
D        7 - 11
F        0 -  6
```

 DUE: AT THE BEGINNING OF LECTURE, FRIDAY, FEBRUARY 20