Discrete Structures

# HW #5 — §1.5: Rules of Inference

 Last Update: 1 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 #5" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

1. (9 points each; total = 45 points)

• (Compare p. 72: 3–4.)

Below are 5 short arguments in English.

1. (3 points each)
For each argument, first give the syntax and semantics of translations of each sentence into the language of propositional logic;
e.g.: Let a = "Alice is a mathematics major".
2. (3 points each)
Then write each argument in your propositional language.
3. (3 points each)
Finally, state the rule of inference that validates each argument.

1. Logic is worth studying, and it is a foundation of computer science. Therefore, it is a foundation of computer science.

2. Either microeconomics is a foundation of computer science, or logic is a foundation of computer science. Microeconomics is not a foundation of computer science. Therefore, logic is a foundation of computer science.

3. Logic is a foundation of computer engineering, and computer engineering is worth studying. If so, then we can say the same thing about logic and computer science. Therefore, logic is a foundation of computer science and computer science is worth studying.

4. If logic is a foundation of computer science, then logic is worth studying. If logic is worth studying, then you should put a lot of effort into CSE 191. Therefore, if logic is a foundation of computer science, then you should put a lot of effort into CSE 191.

5. Logic is worth studying. Therefore, either logic is worth studying, or I'm a monkey's uncle.

• (Click on the link, if you don't know what that phrase means in English :-)

2. (3 points each; total = 6 points)

Which, if any, of these arguments are valid? Why (or why not)?

1. 2+2=5
(2+2=5) → (Bertrand Russell is the Pope)
∴ Bertrand Russell is the Pope.

2. (Background: A TV ad from several years ago showed a man eating a slice of bread with a butter-like substance spread on it.
He says, "If this is margarine, then I'm a monkey's uncle."
The viewer then sees him holding a baby monkey in his arms, and is supposed to infer the conclusion of the following argument:)

If this is margarine, then I'm a monkey's uncle.
I am a monkey's uncle.
∴ This is margarine.

3. (3 points each; total = 12 points)

Consider the following 4 arguments.
For each argument, the truth value of its premises and conclusion is given.

• For each argument, say whether it is valid, invalid, sound, or unsound.
• For partial credit, give your reasons.

• A reason for an argument being valid is that it is an instance of a rule of inference.
• A reason for an argument being invalid is that you can construct an argument of the same form that clearly has true premises but a false conclusion.
• A reason for an argument being sound is that it satisfies both clauses of the definition of "sound" (as defined in lecture).
• A reason for an argument being unsound is that it fails to satisfy at least one of the two clauses of the definition of "sound".

1. If Lassie is a dog, then Lassie is a mammal. (T)
Lassie is a dog. (T)
∴ Lassie is mammal. (T)

2. If the President's limousine is a Jeep, then it is a vehicle. (T)
The President's limousine is a vehicle. (T)
∴ The President's limousine is a Jeep. (F)

3. If Garfield is a cat, then Garfield is a dog. (F)
If Garfield is a dog, then Garfield is a mammal. (T)
∴ If Garfield is a cat, then Garfield is a mammal. (T)

4. If George W. Bush is a recent President, then he has lived in the White House. (T)
George W. Bush has lived in the White House. (T)
∴ George W. Bush is a recent President. (T)

Total points = 63

A       61-63
A-      57-60
B+      54-56
B       50-53
B-      47-49
C+      43-46
C       36-42
C-      29-35
D+      22-28
D       12-21
F        0-11

 DUE: AT THE BEGINNING OF LECTURE, FRI., OCT. 8