[SOLVED] Cs215: discrete math (h) written assignment #1

Q.1 Let p, q and r be the following propositions
p: You get an A on the final exam.
q: You do every exercise in this book.
r: You get an A in this class.
Write these propositions using p, q, and r and logical connectives (including
negations).
(a) You get an A in this class, but you do not do every exercise in this
book.
(b) To get an A in this class, it is necessary for you to get an A on the
final.
(c) You get an A on the final, but you don’t do every exercise in this book;
nevertheless, you get an A in this class.
(d) Getting an A on the final and doing every exercise in this book is
sufficient for getting an A in this class.
(e) You will get an A in this class if and only if you either do every exercise
in this book or you get an A on the final.
Q.2 Use truth tables to decide whether or not the following two propositions
are equivalent.
(a) (p ⊕ q) → (p ∧ q) and (p ⊕ q) → (p ⊕ ¬q)
(b) p ↔ q and (p ∧ q) ∨ (¬p ∧ ¬q)
(c) (¬q ∧ ¬(p → q)) and ¬p
(d) (p → ¬q) ↔ (r → (p ∨ ¬q)) and q ∨ (¬p ∧ ¬r)
Q.3 Use logical equivalences to prove the following statements.
(a) (p ∧ ¬q) → r and p → (q ∨ r) are equivalent.
1
(b) ((p → q) ∧ (q → r)) → (p → r) is a tautology.
Q.4 Show that (p → q) → r and p → (q → r) are not logically equivalent.
Q.5 Suppose that p, q, r, s are all propositions. You are given the following
statement
(q → (r ∨ p)) → ((¬r ∨ s) ∧ ¬s).
Prove that this implies ¬r using logical equivalences and inference rules.
Q.6 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 somebody.
(b) There is somebody whom everybody loves.
(c) Nobody loves everybody.
(d) There is somebody whom no one loves.
(e) There is exactly one person whom every body loves.
(f) There are exactly two people whom Lynn loves.
(g) There is someone who loves no one besides himself or herself.
Q.7 Suppose that variables x and y represent real numbers, and L(x, y) :
x<y, Q(x, y) : x = y, E(x) : x is even, I(x) : x is an integer. Write the
following statements using these predicates and any needed quantifiers.
(1) Every integer is even.
(2) If x<y, then x is not equal to y.
(3) There is no largest real number.
Q.8 For the predicate P(x, y) with two variables x, y, answer the following
two questions.
2
(1) Give an example of a predicate P(x, y) such that ∃x∀yP(x, y) and
∀y∃xP(x, y) have different truth values.
(2) If ∀y∃xP(x, y) is true, does it necessarily follow that ∃x∀yP(x, y) is
true?
Q.9 Each of the two below contains a pair of statements, (i) and (ii). For
each pair, say whether (i) is equivalent to (ii), i.e., for all P(x) and Q(x), (i)
is true if and only if (ii) is true. Here R denotes the set of all real numbers.
If they are equivalent, all you have to do is to say that they are equivalent.
If they are not equivalent, give a counterexample. A counterexample should
involve a specification of P(x) and Q(x) and an explanation as to why the
resulting statement is false.
(1) (i) (∀x ∈ R P(x)) ∨ (∀x ∈ R Q(x))
(ii) ∀x ∈ R (P(x) ∨ Q(x))
(2) (i) (∀x ∈ R P(x)) ∧ (∀x ∈ R Q(x))
(ii) ∀x ∈ R (P(x) ∧ Q(x))
(3) (i) (∀x ∈ R P(x)) ∧ (∃y ∈ R Q(y))
(ii) ∀x ∈ R (∃y ∈ R (P(x) ∧ Q(y)))
(4) (i) (∀x ∈ R P(x)) ∨ (∃y ∈ R Q(y))
(ii) ∀x ∈ R (∃y ∈ R (P(x) ∨ Q(y)))
Q.10
(a) Give the negation of the statement
∀n ∈ N (n3 + 6n + 5 is odd → n is even).
(b) Either the original statement in (a) or its negation is true. Which one
is it and explain why?
Q.11
(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.
3
(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
A!B,
where ! is one of ∧, ∨, ↔, and A and B are chosen from {p, ¬p, q, ¬q}.
Q.12 For the following argument, explain which rules of inference are used
for each step.
“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.13 Prove or disprove the following.
(1) For two irrational numbers a and b, ab is also irrational.
(2) For an irrational number a,
√a is also irrational.
(3) There is a rational number x and an irrational number y such that xy
is irrational.
Q.14 Suppose that we have a theorem: “√n is irrational whenever n is a
positive integer that is
√
not a perfect square.” Use this theorem to prove that
2 + √3 is irrational.
Q.15 Prove that between every rational number and every irrational number
there is an irrational number.
Q.16 Give a direct proof that: Let a and b be integers. If a2 + b2 is even,
then a + b is even.
Q.17 Let the coefficients of the polynomial f(x) = a0 + a1x + a2x2 + ··· +
an−1xn−1 + xn be integers. Show that any real root of the equation f(x)=0
is either integral or irrational. Note that in your proof, you may direct use
the following result without a proof. “Fact. If a prime p is a factor of some
power of an integer, then it is a factor of that integer.”