Quiz 2 Sections 1.4, 2.1, 2.2, 2.3, & 3.1 (counts double) key

Name: ____________________________

1. The Boolean expression for the circuit in Example 1.4.5 on page 51 is
   (P Ù Q Ù R) Ú (P Ù ~Q Ù R) Ú (P Ù ~Q Ù ~R) (a disjunctive normal form)
   º ((P Ù (Q Ù R)) Ú ((P Ù (~Q Ù R))) Ú (P Ù ~Q Ù ~R) by the associative law
   º (P Ù [(Q Ù R) Ú (~Q Ù R)] Ú (P Ù [~Q Ù ~R]) by the distributive law
   º P Ù ([(Q Ù R) Ú (~Q Ù R)] Ú [~Q Ù ~R]) by the distributive law
   º P Ù ([(R Ù Q) Ú (R Ù ~Q)] Ú [~Q Ù ~R]) by the commutative law
   º P Ù ([(R Ù (Q Ú ~Q)] Ú [~Q Ù ~R]) by the distributive law
   º
   º
   º
   º
   º
   .
   Complete the reduction of this Boolean expression using Theorem 1.1.1 to find a circuit with at most three logic gates, then draw your equivalent circuit.
   
   
   
   
   
   
   
   
2. Write the negation for "Every complete bipartite graph is not planar" using ~, Ù , Ú , " , $ as appropriate. Let the domain be the universe of graphs, U. C(x): x is complete. B(x): x is bipartite. P(x): x is planar.
   
   
   
   
   
   
   
3. A proof by counter example. Let n be a positive integer and define p(n) to be the number of partitions of n; that is, the number of different ways to write n as a sum of positive integers, disregarding order. 5 can be written as 1+1+1+1+1, 2+1+1+1, 3+1+1, 4+1, 2+2+1, 3+2, & 5. So p(5) = 7. Likewise p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7.
   Now attempt to prove that: " n > 1, where n Î Z, p(n) is prime.