7.3 Combinational Circuits
This chapter under major construction.
Domino adder. This video shows a 4bit ripplecarry adder that was implemented using 10,000 dominoes.
Exercises.
 Design a circuit to control a single light bulb by three switches. The circuit has three inputs (the switch settings x, y, and z) and one output (the light control). At any time, you should be able to turn the light off (if on) or on (if off) by changing the position of any one of the three switches. When all three switches are 0 (down position), the light control is 0 (light off).

Which of the following TOY machine components are
not combinational circuits?
 Control
 Counter
 Registers
 Main memory
 Adder
Creative Exercises.
 Sumofproducts. Disjunctive normal form. Algebraic properties: sum and product are commutative and associative, distributive property, etc.
 Productofsums. Conjunctive normal form. Include a term for each 0 in the truth table trow.
 Consensus theorems. Verify that (a+b)(a'+c)(b+c) = (a+b)(a'+c) and (ab) + (a'c) + (bc) = (ab) + (a'c).
 Duality. The dual of any boolean identity is obtained by exchanging OR with AND and 0 with 1.
 DeMorgan laws.
 XOR using NAND. Implement an XOR gate using only NAND gates. Assume you can have inputs that are 0 or 1.
 XOR using NAND. Implement an XOR gate using only 4 NAND gates. Assume you can have inputs that are 0 or 1. Answer: XOR(a, b) = NAND(d, e), where c = NAND(a, b), d = NAND(a, c), and e = NAND(b, c).
 OR and NAND using NOR. Implement OR using NOR gates. Implement NAND using NOR gates. Don't assume that you can use inputs that are 0 or 1.
 Universality.
Prove that the following combinations of gates are universal:
 { AND, NOT }
 { OR, NOT }
 { NAND }
 { NOR }
 { XOR, AND }
 Nonuniversality.
Prove that the following gates are not universal:
 { AND }
 { OR }
 { XOR }
 AND from XOR.
Prove that you can't make an AND gate out of XOR gates.
Solution. As above { XOR, AND } is universal. So if you could make an AND gate out of XOR gaets, { XOR } would be univeral. But in the previous question, you proved that it was not universal.
 The 2NOTs problem. Give three inputs a, b, and c, design a circuit that outputs a', b', and c'. You may use as many AND and OR gates as you like, but at most two NOT gates. Warning: high degree of difficulty.
 Flat computer. Show that, in principle, you can draw and circuit in the plane. Assume two input AND, OR, and NOT can be drawn in the plane. It suffices to draw a crossover circuit. planar crossover circuit.
 Comparator circuit.
 At least k. A nway majority circuit takes n inputs and returns 1 if and only if at least strictly more of its inputs are 1 than 0. Given an nway majority circuit, describe how to build an AtLeastk circuit that returns 1 if and only if at least k of its inputs are 1. Answer: consider a 2nway majority circuit. Make nk+1 of the inputs 1, k1 of the inputs 0, and the original n inputs.
 Exactly k circuit. Describe how to build a circuit that outputs 1 if and only if exactly k of its inputs are 1. Answer: If k = n, use an nway and gate. Otherwise build up an Atleastk circuit and an Atleastk+1 circuit as in the previous exercise. It has exactly k inputs that are 1 if the first circuit outputs 1, but the second one outputs 0.
 Odd parity from majority gates. Describe how to build an nway odd parity circuit using only majority gates. You may assume that you have 0s and 1s as inputs.
 Odd parity.
Describe how to build an Nway odd parity circuit using
only AND, OR, NOT.
Hint: build a tree of 3way odd parity gates,
using ceil(2.5(N1)) total gates.
What is the smallest such circuit you can build for N = 2 to 6? The 3way XOR tree construction is optimal for N = 2 to 5: 3 gates, 5 gates, 8 gates, and 10 gates respectively. The answer is unknown for N = 6 (but is known to be either 12 or 13). (Ingo Wegener, 1991)
 XOR from AND. Design an XOR circuit using only AND and NOT. Use as few AND gates as possible. Min = 3.
 MAJ from AND. Design a 3way MAJ circuit using only AND and NOT. Use as few AND gates as possible. Min = 4.
 Adder from majority gates. Describe how to build an nbit ripplecarry adder circuit using only majority gates. You may assume that you have 0s and 1s available as inputs. Hint: build up a 3way odd parity circuit out of 3way majority circuits. Note that MAJ(x, y) = AND(x, y) and MAJ(x, y, 1) = OR(x, y).
 Boolean logic puzzle.
You must transport a wolf, a goat, and a cabbage to the other side
of the river using a boat. Due to natural predator relationships,
you cannot leave the goat and the wolf alone on the same side of the river
at the same time. Nor can you leave the goat and the cabbage together.
 Overflow of two's complement adder.
How to detect overflow of two's complement adder? Subtractor?
Answer If the carry out of the leftmost bit is different from the carry in.  Boolean functions and circuits. Let f be a boolean function on n input bits. Prove that for most functions f, the number of AND, OR, and NOT gates needed to implement f is at least 2^(n/3). Hint: prove that the number of circuits with m gates is at most 2^m and compare this quantity to the number of boolean functions on n inputs.