1. The Main Insight
To understand a circuit, distinguish the inputs and outputs of individual gates from the original inputs and final output of the complete circuit. A gate inside a circuit does not need to perform the same logical function as the complete circuit.
2. AND and NAND
AND produces 1 only when both inputs are 1. NAND means NOT AND: P ↑ Q = ¬(P ∧ Q).
| P | Q | AND | NAND |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
3. Using NAND as NOT
Connecting the same value A to both inputs of a NAND gate gives A ↑ A = ¬(A ∧ A) = ¬A. Thus, a NAND gate with tied inputs behaves like NOT.
4. Constructing AND from NAND
Let R = P ↑ Q = ¬(P ∧ Q). Apply NAND to R twice: R ↑ R = ¬R = ¬¬(P ∧ Q) = P ∧ Q.
Therefore (P ↑ Q) ↑ (P ↑ Q) = P ∧ Q. The entire expression implements AND even though each individual operation is NAND.
5. Worked Example: P = 1, Q = 1
The first NAND produces 1 ↑ 1 = 0. Feeding that result into both inputs of another NAND produces 0 ↑ 0 = 1. The final result matches 1 AND 1 = 1.
The important comparison is between the original inputs (1,1) and the complete circuit’s final output (1). Comparing 0 NAND 0 with 0 AND 0 instead would compare the last gate’s inputs rather than the circuit’s original inputs.
6. Why the Expression Looks Like Three NAND Operations
In (P ↑ Q) ↑ (P ↑ Q), NAND appears three times: twice inside the parentheses and once outside. A literal implementation could use three NAND gates. But the two inner calculations are identical, so a circuit can calculate P ↑ Q once and feed its result to both inputs of the final NAND. This optimized circuit needs only two physical NAND gates, using fan-out.
7. Complete Truth Table
| P | Q | R = P NAND Q | R NAND R | P AND Q |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
8. Connection to Functional Completeness
NAND can implement NOT by tying its inputs together. NAND can implement AND by negating the result of a NAND operation. Since NOT and AND can express every Boolean function, NAND alone is functionally complete. In circuit terminology, NAND is a universal gate.
9. Connection to Quantum Computing
This classical construction illustrates how larger computations emerge from compositions of elementary gates. Later, reversible computation and quantum gates introduce additional restrictions. In particular, arbitrary unknown quantum states cannot be copied through classical-style fan-out.
Key Takeaway
Do not judge a circuit by the truth table of its final individual gate in isolation. Trace intermediate values, then compare the complete circuit’s original inputs with its final output.
Note metadata
- Note type: learning-note
- Subject: learning-notes
- Source: Quantum Computing for Everyone