Discrete Structures

# HW #2

## §1.2: Propositional Equivalences

 Last Update: 10 September 2010, 7:52 P.M. Note: or material is highlighted

All exercises 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 for truth table; 3 points for explanation; 6 points total)

p. 28: 4a

• Use truth tables to show that 2 propositions are logically equivalent.

• You must not only show the complete truth table, including all intermediate columns,
but you must also say why or how the truth table shows that the two propositions are equivalent.

2. (12 points)

p. 28: 8b

• Compute the negation of an English sentence.

• Do this problem in 4 steps (3 points each; you do not have to construct a truth table, however!):

1. (3 points)
Identify the atomic propositions and choose letters to represent them.

2. (3 points)
Represent the compound proposition that is given in the problem (i.e., translate it from English to the language of propositional logic).

3. (3 points)
Use DeMorgan's Laws (and any other logical equivalences from Table 6 in the text) to construct its negation.

4. (3 points)
Translate back into English.

3. (24 points)

to correct page:
p. 29: 44

• Show that negation (¬) and conjunction (∧) are "functionally complete",
i.e., that only the two connectives ¬ and ∧ are needed in order to represent any molecular proposition.
(I.e., show that you don't need to use ∨, ⊕, →, or ↔.)

• Be sure to read the paragraph on p. 29 between problems 42 and 43 that defines "functionally complete"

• To show that these two connectives are functionally complete, you need to do two things:

1. (3 points each; total = 12 points)
For any proposition containing ∨, →, ↔, or ⊕,
find a logically equivalent proposition that only contains ¬ and ∧.

2. (3 points each; total = 12 points)
Construct truth tables that show the following:

1. Any proposition of the form "(p ∨ q)" can be written as a logically equivalent proposition using only ¬ and ∧ (using the hint in the text).

2. Any proposition of the form "(p → q)" can be written as a logically equivalent proposition using only ¬ and ∧.

• Hint: Either directly show that "(p → q)" can be written as a logically equivalent proposition using only ¬ and ∧,
or else show that it can be written as a logically equivalent proposition using only ¬ and ∨, and then use the equivalence in part (i)

3. Any proposition of the form "(p ↔ q)" can be written as a logically equivalent proposition using only ¬ and ∧.

• Hint: Show that "(p ↔ q)" can be written as a logically equivalent proposition using only ∧ and →.
Then, using previous equivalences, show how it can be re-written using only ¬ and ∧.

4. Any proposition of the form "(p ⊕ q)" can be written as a logically equivalent proposition using only ¬ and ∧.

• Hint: Show that "(p ⊕ q)" can be written as a logically equivalent proposition using ¬, ∨, and ∧.
Then use previous equivalences to show that you can re-write it using only ¬ and ∧.

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

p. 29: 48, 50b

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