Discrete Math for Computer Science  Assignment # 1

CS201: Discrete Math for Computer Science
 Assignment # 1

Q.1 Use truth tables to decide whether or not the following two propositions
are equivalent.
(a) p ⊕ q and ¬p ∨ ¬q
(b) (¬q ∧ ¬(p → q)) and ¬p
(c) (p ∨ q) → r and (p → r) ∧ (q → r)
(d) (p → ¬q) ↔ (r → (p ∨ ¬q)) and q ∨ (¬p ∧ ¬r)
Q.2 Use logical equivalences to prove the following statements.
(a) ¬(p → q) → p is a tautology.
(b) (p ∧ ¬q) → r and p → (q ∨ r) are equivalent.
(c) ¬p → (q → r) and q → (p ∨ r) are equivalent.
(d) ¬(p ⊕ q) and p ↔ q are equivalent.
(e) (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.
(a) (p → q) ∨ (p → r) and p → (q ∨ r)
(b) (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), quantifiers, and logical
connectives. Let the domain consist of all students in your class.
1
(a) A student in your class has a cat, a dog, and a ferret.
(b) All students in your class have a cat, a dog, or a ferret.
(c) Some student in your class has a cat and a ferret, but not a dog.
(d) No student in your class has a cat, a dog, and a ferret.
(e) 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 quantifiers to express each of
these statement.
(a) Everybody loves Jerry.
(b) Everybody loves somebody.
(c) There is somebody whom everybody loves.
(d) Nobody loves everybody.
(e) There is somebody whom Lydia does not love.
(f) There is somebody whom no one loves.
(g) There is exactly one person whom every body loves.
(h) There are exactly two people whom Lynn loves.
(i) Everyone loves himself or herself.
(j) 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.
(a) ∀x∃y∀zT(x, y, z)
(b) ∀x∃yP(x, y) ∨ ∀x∃yQ(x, y)
2
(c) ∀x∃y(P(x, y) ∧ ∃zR(x, y, z))
(d) ∀x∃y(P(x, y) → Q(x, y))
Q.9
(a) Let P be a proposition in atomic propositions p and q. If P = ¬(p ↔
(q ∨ ¬p)), prove that P is equivalent to ¬p ∨ ¬q.
(b) If P is of any length, using any of the logical connectives ¬, ∧, ∨, →,
↔, prove that P is logically equivalent to a proposition of the from
AB,
where is one of ∧, ∨, ↔, and A and B are chosen from {p, ¬p, q, ¬q}.
Q.10 For each of these arguments, explain which rules of inference are used
for each step.
(a) “Each of five roommates, A, B, C, D, and E, has taken a course in
discrete mathematics. Every student who has taken a course in discrete mathematics can take a course in algorithms. Therefore, all five
roommates can take a course in algorithms next year.”
(b) “All movies produced by John Sayles are wonderful. John Sayles produced 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.
Q.12 Prove that √3
2 is irrational.
Q.13 Give a direct proof that: Let a and b be integers. If a
2 + b
2
is even,
then a + b is even.
Q.14 Prove that between every two rational numbers there is an irrational
number.
3