Assignment #1 Solution

Description

Q.1 Use truth tables to decide whether or not the following two propositions are equivalent.

1. p q and :p _ :q

2. (:q ^ :(p ! q)) and :p

3. (p _ q) ! r and (p ! r) ^ (q ! r)

4. (p ! :q) $ (r ! (p _ :q)) and q _ (:p ^ :r)

Q.2 Use logical equivalences to prove the following statements.

1. :(p ! q) ! p is a tautology.

2. (p ^ :q) ! r and p ! (q _ r) are equivalent.

3. :p ! (q ! r) and q ! (p _ r) are equivalent.

4. :(p q) and p $ q are equivalent.

5. (p ! q) ! ((r ! p) ! (r ! q)) is a tautology.

Q.3 Show that (p ! q) ^ (q ! r) ! (p ! r) is a tautology.

Q.4 Determine whether or not the following two are logically equivalent, and explain your answer.

1. (p ! q) _ (p ! r) and p ! (q _ r)

2. (p ! q) ! r and p ! (q ! r)

Q.5 Prove that if p ^ q, p ! :(q ^ r), s ! r, then :s.

Q.6 Let C(x) be the statement \x has a cat”, let D(x) be the statement \x has a dog” and let F (x) be the statement \x has a ferret.” Express each of these sentences in terms of C(x), D(x), F (x), quanti ers, and logical connectives. Let the domain consist of all students in your class.

1. A student in your class has a cat, a dog, and a ferret.

2. All students in your class have a cat, a dog, or a ferret.

3. Some student in your class has a cat and a ferret, but not a dog.

4. No student in your class has a cat, a dog, and a ferret.

5. For each of the three animals, cats, dogs, and ferrets, there is a student in your class who has this animal as a pet.

Q.7 Let L(x; y) be the statement \x loves y”, where the domain for both x and y consists of all people in the world. Use quanti ers to express each of these statement.

1. Everybody loves Jerry.

2. Everybody loves somebody.

3. There is somebody whom everybody loves.

4. Nobody loves everybody.

5. There is somebody whom Lydia does not love.

6. There is somebody whom no one loves.

7. There is exactly one person whom every body loves.

8. There are exactly two people whom Lynn loves.

9. Everyone loves himself or herself.

10. There is someone who loves no one besides himself or herself.

Q.8 Express the negations of each of these statements so that all negation symbols immediately precede predicates.

1. 8x9y8zT (x; y; z)

2. 8x9yP (x; y) _ 8x9yQ(x; y)

3. 8x9y(P (x; y) ^ 9zR(x; y; z))

3. 8x9y(P (x; y) ! Q(x; y))

Q.9

1. Let P be a proposition in atomic propositions p and q. If P = :(p $

(q _ :p)), prove that P is equivalent to :p _ :q.

2. If P is of any length, using any of the logical connectives :, ^, _, !, $, prove that P is logically equivalent to a proposition of the from

A B;

where is one of ^, _, $, and A and B are chosen from fp; :p; q; :qg.

Q.10 For each of these arguments, explain which rules of inference are used for each step.

1. \Each of ve roommates, A, B, C, D, and E, has taken a course in discrete mathematics. Every student who has taken a course in dis-crete mathematics can take a course in algorithms. Therefore, all ve roommates can take a course in algorithms next year.”

2. \All movies produced by John Sayles are wonderful. John Sayles pro-duced a movie about coal miners. Therefore, there is a wonderful movie about coal miners.”

Q.11 Prove or disprove that there is a rational number x and an irrational number y such that x^y is irrational.

p

Q.12 Prove that ³ 2 is irrational.

Q.13 Give a direct proof that: Let a and b be integers. If a² + b² is even, then a + b is even.

Q.14 Prove that between every two rational numbers there is an irrational number.

3