CISC102 Winter 2024
Quiz 1: Logic and Set Theory
Questions
1. (4 marks) Let U = {x ∈ Z | 0 ≤ x ≤ 15}, A = {0, 3, 6, 9, 12, 15}, B = {0, 2, 4, 6, 8, 10, 12, 14}, C = {3, 4, 5, 6, 7, 8, 9, 10}. For each set indicated below: (i) List the elements in the set, (ii) draw the associated Venn Diagram by indicating the sections matching the set description
(a) A ∩ B ∩ C (d) A\C
(b)B ∪ C (e) (A ∩ B)
2. (3 marks) Prove DeMorgan’s Law using a truth table.
3. (3 marks) Let Ai = {−i, −i + 1, . . . 0, 1, . . . , i − 1, i}. (a) Describe the sets Ai in plain language. (b) Find S ni=1 Ai and T ni=1
4. (a) (2 marks) Let S = {0, 1, 2}. Find a set A so that S ⊆ A and S ∈ A. Clearly define A, and show that both properties hold.
(b) (1 mark) Determine P(S).
(c) (1 mark) Is it true in general that S ⊆ P(S) for some set S? Explain why or why not (you may use your answers above as reference).
5. (5 marks) Prove that the following equality holds by simplifying the left and right sides using laws of set operations. State any law that you use (either by name, or by it’s formula if you cannot remember the name). You may also use the set-removal operation formula A\B = A ∩ B.
(B ∪ C) \ (A ∪ B) ≡ C ∩ (A ∪ B)
6. (5 marks) Determine if the following logical expressions are logically equivalent using a Truth Table:
(a)(p ∨ q) ∧ ¬ (q → r) (b) (r → ¬p) ∧ (q ∨ p)
7. (6 marks) Let A = {a ∈ Z | 0 ≤ a ≤ 10} and B = {b ∈ N | b 2 ≤ 100}. Determine whether A = B. If they are equal, prove it. If they are not equal, provide a set A′ = A ∪ {x1, x2, ...} containing additional elements xi ∈ Z so that A′ = B, then prove it.
8. (6 marks) One hundred and two (102) students were polled to determine which winter activity they preferred the most out of:skiing, snow shoeing, and hockey. The following stats were found:
• 64 like hockey, 50 like skiing, and 43 like snow shoeing
• 27 like hockey and skiing, 28 like hockey and snow shoeing
• 49 students like exactly 2 activities (but not all three)
• 7 like all three
Draw a Venn Diagram for the following situation. Determine the size of each segment in the Venn Diagram, and show all your work. How many students listen to NONE of the artists?