Solution set of Homework Assignment 1

NOTE: The solutions to problems requiring truth tables to not appear here. If you have questions regarding these please speak with the instructor.

Section 1.1

6. a) If you have the flu, you will miss the final exam.

b) You will pass the course if and only if you don’t miss the final exam.

c) If you miss the final exam, you will not pass the course.

d) You have the flu or you miss the final exam or you pass the course.

e) If you have the flu, you will not pass the course or if you miss the final exam, you will not pass the

course.

f) You have the flu and you miss the final exam, or you don’t miss the final exam and you pass the

course.

14. a) Converse : I will stay at home only if it snows tonight.

Contrapositive : If I don’t stay at home, it will not have snowed tonight.

b) Converse : I go to the beach only if it is a sunny summer day.

Contrapositive : If I don’t go to the beach, it will not have been a sunny summer day.

c) Converse : I sleep until noon only if I have stayed up late.

Contrapositive : If I don’t sleep until noon, I will not have stayed up late.

Section 1.2

10.a)[Ø pÙ (pÚ q)]® q

Û Ø (Ø pÙ (pÚ q))Ú q

Û pÚ Ø (pÚ q)Ú q

Û pÚ (Ø pÙ Ø q)Ú q

Û ((pÚ Ø p)Ù (pÚ Ø q))Ú q

Û (TÙ (pÚ Ø q))Ú q

Û (pÚ Ø q)Ú q

Û pÚ (Ø qÚ q)

Û pÚ T

Û T

b) [(p® q)Ù (q® r)]® (p® r)

Û Ø [(p® q)Ù (q® r)]Ú (p® r)

Û Ø [(Ø pÚ q)Ù (Ø qÚ r)]Ú (Ø pÚ r)

Û Ø (Ø pÚ q)Ú Ø (Ø qÚ r)Ú (Ø pÚ r)

Û (pÙ Ø q) Ú (qÙ Ø r)Ú (Ø pÚ r)

Û [(pÚ q)Ù (Ø qÚ q)Ù (pÚ Ø r)Ù (Ø qÚ Ø r)]Ú (Ø pÚ r)

Û [(pÚ q) Ù (pÚ Ø r)Ù (Ø qÚ Ø r)]Ú (Ø pÚ r)

Û (pÚ qÚ Ø pÚ r)Ù (pÚ Ø rÚ Ø pÚ r)Ù (Ø qÚ Ø rÚ Ø pÚ r)

Û (TÚ qÚ r)Ù (TÚ T)Ù (Ø qÚ Ø pÚ T)

Û TÙ TÙ T

Û T

c) [pÙ (p® q)]® q

Û Ø [pÙ (p® q)] Ú q

Û Ø [pÙ (Ø pÚ q)]Ú q

Û Ø pÚ Ø (Ø pÚ q)Ú q

Û Ø pÚ (pÙ Ø q)Ú q

Û (Ø pÚ pÚ q)Ù (Ø pÚ Ø qÚ q)

Û (TÚ q)Ù (Ø pÚ T)

Û TÙ T

Û T

d) [(pÚ q )Ù (p® r)Ù (q® r)]® r

Û [(pÚ q)Ù (Ø pÚ r)Ù (Ø qÚ r)] ® r

Û [((pÙ Ø p)Ú (qÙ Ø p)Ú (pÙ r)Ú (qÙ r))Ù (Ø qÚ r)]® r

Û [((qÙ Ø p)Ú (pÙ r)Ú (qÙ r))Ù Ø q]Ú [((qÙ Ø p)Ú (pÙ r)Ú (qÙ r))Ù r] ® r

Û [(qÙ Ø pÙ Ø q)Ú (pÙ rÙ Ø q)Ú (qÙ rÙ Ø q)Ú (qÙ Ø pÙ r)Ú (pÙ rÙ r)Ú (qÙ rÙ r)]® r

Û [(FÙ Ø p)Ú (pÙ rÙ Ø q)Ú (FÙ r)Ú (qÙ Ø pÙ r)Ú (pÙ r)Ú (qÙ r)]® r

Û [FÚ (pÙ rÙ Ø q)Ú FÚ (qÙ Ø pÙ r)Ú (pÙ r)Ú (qÙ r)]® r

Û [(pÙ rÙ Ø q)Ú (qÙ Ø pÙ r)Ú (pÙ r)Ú (qÙ r)]® r

Û Ø [(pÙ rÙ Ø q)Ú (qÙ Ø pÙ r) Ú (pÙ r)Ú (qÙ r)]Ú r

Û [Ø (pÙ rÙ Ø q) Ù Ø (qÙ Ø pÙ r) Ù Ø (pÙ r)Ù Ø (qÙ r)]Ú r

Û [(Ø pÚ Ø rÚ q) Ù (Ø qÚ pÚ Ø r) Ù (Ø pÚ Ø r)Ù (Ø qÚ Ø r)]Ú r

Û [(Ø pÚ Ø rÚ qÚ r) Ù (Ø qÚ pÚ Ø rÚ r) Ù (Ø pÚ Ø rÚ r)Ù (Ø qÚ Ø rÚ r)]

Û [(Ø pÚ qÚ T) Ù (Ø qÚ pÚ T) Ù (Ø pÚ T)Ù (Ø qÚ T)]

Û TÙ TÙ TÙ T

Û T

Section 1.3

8.a) \$ x\$ y Q(x, y)

b) Ø (\$ x\$ y Q(x, y)) or " x" y Ø Q(x, y)

c) \$ x (Q(x, Jeopardy) Ù Q(x, "Wheel of Fortune"))

d) " y\$ x Q(x, y)

e) \$ x\$ y (Q(x, Jeopardy) Ù Q(x, Jeopardy) Ù (x¹ y))

9. Please see the text book.

14. Q(x, y) : "x + y = x – y" is true if and only if y = 0 (regardless of x).

a)F b)T c)F d)F e)T f)T g)T h)F i)F

18. a) " x P(x) ® Q(x)

b) \$ x R(x)Ù Ø Q(x)

c) \$ x R(x)Ù Ø P(x)

d) We show that c) follows from a) and b) using proof by contradiction. That is, we assume that c) is

false and then prove a contradiction. For resolution we have to convert a),b),c) into Conjunctive

Normal Form as presented in the lecture.

Eliminating ® and dropping the prefix in a) gives the clause

i) Ø P(x)Ú Q(x)

Eliminating existential quantifier in b) gives

R(sk1) )Ù Ø Q(sk1), where sk1 is a constant symbol denoting an unsatisfactory excuse.

Creating a separate clause corresponding to each conjunct gives the clauses

ii) R(sk1)

iii) Ø Q(sk1)

Negating c) and dropping the prefix gives

iv) Ø R(x)Ú P(x) .

The proof then proceeds as follows.

v) P(sk1) (from ii),iv) )

vi) Q(sk1) (from v),i) )