Quiz 2 Sections 1.4, 2.1, 2.2, 2.3, & 3.1

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
   º P Ù ([(R Ù t] Ú [~Q Ù ~R]) by the negation law
   º P Ù (R Ú [~Q Ù ~R]) by the identity law
   º P Ù ((R Ú ~Q) Ù (R Ú ~R)) by the distributive law
   º P Ù ((R Ú ~Q) Ù t)) by the negation law
   º P Ù (R Ú ~Q) by the identity 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.
   We have " x Î U, C(x) Ù B(x) ® ~P(x)
   The negation is: $ x Î U such that C(x) Ù B(x) Ù P(x).
   
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.
   We calculate p(6) = 11 which adds credence to the conjecture.
   7 can be written as 1+1+1+1+1+1+1, 2+1+1+1+1+1, 3+1+1+1+1, 4+1+1+1, 5+1+1, 6+1, 2+2+1+1+1, 3+2+1+1, 2+2+2+1, 3+3+1, 4+2+1, 2+2+3, 4+3, 5+2, & 7.
   p(7) = 15 is not prime. The conjecture is proven to be false by counterexample.