Discrete Structures

# HW #1

## §1.1: Propositional Logic

 Last Update: 8 September 2010 Note: or material is highlighted

All problems come from the Rosen text.

Each HW problem's solution should consist of:

All solutions must be handwritten.

 PUT YOUR NAME, DATE, & RECITATION SECTION AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

1. (3 points:
3 = clearly correct;
1 = clearly incorrect;
2 = neither clearly correct nor clearly incorrect;

p. 17: 8f

• This asks you to translate a proposition from the language of propositional logic into English.

2. (3 points)

p. 17: 10e

• This asks you to translate an English sentence into the language of propositional logic.

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

p. 18: 20a–g (i.e., do each of a, b, c, d, e, f, g, but not h)

• This asks you to rewrite 7 English sentences that express conditional propositions so that they are in "if-then" form.

• For this problem, you may have to rewrite some of the English phrases that make up the sentences as grammatically correct, full sentences of English.

E.g., the phrases "to be a citizen of this country" and "that you ge the job" are not full sentences, but they can be rewritten as "You are a citizen of this country" (or "You get the job" (or "You got the job"), etc.

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

p. 19: 28a, d (i.e., do both a and d, but not b, c, e, or f)
p. 19: 32a, b (i.e., do both a and b, but not c, d, e, or f)

• These problems ask you to construct truth tables.

• Be sure to show all of the "intermediate" columns of your truth tables.

5. (3 points)

p. 19: 42

• This asks you whether a certain English expression is a proposition.

• If you're not sure how our text defines "proposition", look it up! (Try the index!)

• Besides answering "yes", "no", "maybe", "I don't know", etc., you must also say why that's your answer!

6. (3 points)

Consider a (male) barber who lives in a village and who shaves all and only those (males) who live in the village and who do not shave themselves. Who shaves the barber?
(Compare this to p. 19, #44.)

• As before, besides answering "the barber", "someone", "no one", "I don't know", etc. you must also say why that's your answer!

7. (3 points)

p. 20: 52

• This asks whether a certain set of 5 sentences is consistent. (If you're not sure what our text means by "consistent", look it up!)

• As you will soon learn, English sentences are usually expressed logically as "molecular" (or "compound") propositions, each of which consists of certain "atomic" propositions.

(For example, "Buffalo is in New York State and Albany is the captial of New York State" is a "molecular" (or "compound") proposition containing two "atomic" propositions: "Buffalo is in NYS" and "Albany is the capital of NYS". The molecular proposition is formed by connecting the two atomic propositions with the English word "and", which is represented in our language for propositional logic by the symbol "∧". If we represent the atomic propositions by the proposition letters "B" and "A", then the molecular proposition would be represented as "(B ∧ A)".)

• Suggestion:

• For each atomic proposition in problem 52, choose a proposition letter.
• Then use appropriate logical connectives to represent each molecular proposition in the language of propositional logic.
• Is there an assignment of truth values to the atomic propositions that will make all 5 molecular propositions true?

• If so, what is it?
• If not, why not?

• Alternatively, construct truth tables for the sentences.

• Use the truth tables to help answer the question.
• But don't just show the truth tables;

```Total points = 48

A       46-48
A-      43-45
B+      41-42
B       38-40
B-      35-37
C+      33-34
C       27-32
C-      22-26
D+      17-21
D        9-16
F        0- 8

```

 DUE: AT THE BEGINNING OF LECTURE, FRI., SEP. 10