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.