3.1 Chapter 0

Complete the following problems:

1. (0.15) Sets. If A × B × C = {(2,b,3),(1,b,3),(2,c,3),(2,a,3),(1,c,3),(1,a,3)}, then

   1. (0.09) List the elements of each of the sets A, B, and C.

   2. (0.06) List the elements of the powerset of B.

2. (0.10) Boolean Logic. Create a truth table for the following logical expression: ((P ∨ Q) ∧ (P → Q)) ↔ (¬Q)

3. (0.10) Strings. Find a language D and a language E for which: D ⋅ E = {100, 101, 1110, 1111}

4. (0.15) Relations. Let H be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ∈ H ⇔ ad = bc. Select True or False for the following statement and justify your answer: H is an equivalence relation.

5. (0.10) Graphs. Draw an example of undirected, connected graph G = (V,E) such that one vertex has degree |V| - 1 and every other vertex has degree 1.

6. (0.40) Proofs. Conduct the following proofs:

   1. (0.20) Prove that if m and n are integers and mn is even, then m is even or n is even.

   2. (0.20) Prove, by induction, that for every natural number: 1⋅2 + 2⋅3 + ⋯ + n⋅(n+1) = (n ⋅ (n+1) ⋅ (n+2)) / 3