ECS 20: Discrete Mathematics for Computer Science PS4.Problems UC Davis — Prof. October 12, 2021
Problem Set 4 – Due Tuesday, October 19, at 5pm
1. Complete the following table, answering whether the statement is true (T) or false (F) when the intended universe U is as indicated (the set of reals or the set of integers).
RZ
∀x∃y(2x − y = 0) ∃y∀x(2x − y = 0)
∀x∃y(x − 2y = 0)
∀x(x < 10 → ∀y(y < x → y < 9)) ∃y∃z(y + z = 100)
∀x∃y(y > x ∧ ∃z(y + z = 100))
2. Translate the negation of the following statements into formulas of first-order logic, introducing
predicates as needed.
(a) There is someone in the freshman class who doesn’t have a roommate. (b) Everyone likes someone, but no one likes everyone.
(c) (∀a∈A)(∃b∈B)(a∈C ↔b∈C) (d) (∀y>0)(∃x)(ax2 +bx+c=y)
3. Suppose that A, B and C are sets. For each of the following statements either prove it is true or give a counterexample to show that it is not.
(a) A ∈ B ∧ B ∈ C =⇒ A ∈ C (b) A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C (c) A B ∧ B C =⇒ A C
(d) A ∈ B ∧ B ⊆ C =⇒ A ∈ C (e) C ∈ P(A) ⇐⇒ C ⊆ A
(f) A=∅ ⇐⇒ P(A)=∅
4. Which of the following conditions imply that B = C? In each case, either prove or give a coun- terexample.
(a) A∪B=A∪C (b) A∩B=A∩C (c) A⊕B=A⊕C
(d) A×B=A×C
5. Suppose that A, B and C are sets. For each of the following statements either prove it is true or
give a counterexample to show that it is not.
(a) A(B∪C)=(AB)∪(AC) (b) (AB)×C =(A×C)(B×C) (c) (A⊕B)×C =(A×C)⊕(B×C)
(d) (A∪B)×(C∪D)=(A×C)∪(B×D)