ECS 20: Discrete Mathematics for Computer Science PS4.Problems
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).
R Z
∀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) Ar (B ∪ C) = (ArB) ∪ (Ar C)
(b) (ArB)× C = (A× C) r (B × C)
(c) (A⊕B)× C = (A× C)⊕ (B × C)
(d) (A ∪B)× (C ∪D) = (A× C) ∪ (B ×D)