COMP 1002 Winter 2019
Homework Assignment # 4
Due: March 12, by 10pm
(Type it up and upload on D2L)
**YOUR NAME HERE**
------------------------------------------------------------------------
1. **Sets, relations and functions**[50]
(a). Disprove by counterexample that for all sets $A, B, C$ in some universe $U$, $\overline{A \cup B \cup C } = \overline{A} \cup \overline{B} \cup \overline{C}$
*Solution:*
(b). Prove that $(A - C) \cap (C - B) = \emptyset$. Hint: use proof by contradiction.
*Solution:*
(c). Prove that for any sets $A$ and $B$, powerset $\mathcal{P}( A \cap B ) = \mathcal{P} (A) \cap \mathcal{P}(B)$. Hint: show that every element of $\mathcal{P}(A \cap B)$ is an element of $\mathcal{P} (A) \cap \mathcal{P}(B)$, and vice versa.
*Solution:*
(d). Let $g\colon A \to B$ and $f\colon B \to C$ be one-to-one functions, where A, B, C are arbitrary sets. Prove that their composition $f \circ g \colon A \to C$ is a one-to-one function.
*Solution:*
2. **Boolean algebras**[25]
For this question you need the axioms of Boolean algebra:
| $x +y=y+x$ | $x\cdot y = y \cdot x$ | Commutativity |
| ------------------------------------ | ---------------------------------------- | -------------- |
| $(x+y)+z=x+(y+z)$ | $(x\cdot y)\cdot z = x \cdot (y\cdot z)$ | Associativity |
| $x\cdot (y+z) = x\cdot y + x\cdot z$ | $x +y\cdot z = (x+y)\cdot (x+z)$ | Distributivity |
| $x+0 = x$ | $x\cdot 1 = x$ | Identity |
| $x+\bar{x} =1$ | $x \cdot \bar{x} = 0$ | Inverse |
| $0 \neq 1$ | | |
(a). Write a formula $\bar{x}+\overline{y\cdot z}$ in both the language of propositional logic (using variables $p, q, r$ for $x,y,z$) and in the language of set theory (using variables $A,B,C$ for $x,y,z$).
*Solution:*
(b). Show how to derive the rule $x + x = x$ using only these axioms.
*Solution:*
3. **Cardinalities of sets** [25]
In biology, a DNA is a double helix made of 2 sequences of nucleotides C, G, A and T. From computer science perspective, we can view it as a pair ot two finite strings of the same length made out of letters C, G, A, T.
(a). Show that the number of possible DNAs is countable. That is, show how to associate with every DNA a different natural number (either give a formula or just explain the procedure that does it). Hint: do it for one string rather than 2, then refer to the theorem used in the proof that $\mathbb{Q}$ is countable.
*Solution:*
(b). Suppose a biologist defines a “species” as a (potentially infinite) set of possible DNAs. Show that with this definition the number of species is uncountable. Hint: you could do it by diagonalization, or you can, much simpler, directly infer it from one of the results that we stated when talking about diagonalization.
*Solution:*