Description

CS 70 Discrete Mathematics and Probability Theory

1 Implication
Which of the following implications are always true, regardless of P? Give a counterexample for each false assertion (i.e. come up with a statement P(x,y) that would make the implication false).
(a) ∀x∀yP(x,y) =⇒ ∀y∀xP(x,y).
(b) ∀x∃yP(x,y) =⇒ ∃y∀xP(x,y). (c) ∃x∀yP(x,y) =⇒ ∀y∃xP(x,y).
2 Equivalences with Quantifiers
Evaluate whether the expressions on the left and right sides are equivalent in each part, and briefly justify your answers.

3 XOR
The truth table of XOR (denoted by ⊕) is as follows.
A B A⊕B
F F F
F T T
T F T
T T F
1. Express XOR using only (∧,∨,¬) and parentheses.
2. Does (A⊕B) imply (A∨B)? Explain briefly.
3. Does (A∨B) imply (A⊕B)? Explain briefly.
4 Truth Tables
Determine whether the following equivalences hold, by writing out truth tables. Clearly state whether or not each pair is equivalent.
(a) P∧(Q∨P) ≡ P∧Q
(b) (P∨Q)∧R≡(P∧R)∨(Q∧R)
(c) (P∧Q)∨R≡(P∨R)∧(Q∨R)