1. Show that negations can be moved down to the variables in any
   circuit with only a polynomial increase in size.

2. Show that n Boolean variables can be negated using a circuit with 
   O(log n) NOT gates, and an unlimited number of AND and OR gates.
   Show an Omega(log n) lower bound for this problem.

3. Page 33: Problem 2.

4. Page 33: Problem 3.

5  Page 34: Problem 6 (b).

6. Page 34: Problem 8. 

7. Page 69: Problem 2.

8. Page 69: Problem 4.

9. Page 69: Problem 6.

10. Page 69: Problem 7.

11. Page 69: Problem 8.

12. Page 69: Problem 9.