Solution: 4 NAND Gates
function NAND(a, b) {
return !(a && b);
}
function XOR_from_NAND(a, b) {
// Gate 1: NAND of inputs
const nand1 = NAND(a, b);
// Gate 2: NAND of A and nand1
const nand2 = NAND(a, nand1);
// Gate 3: NAND of B and nand1
const nand3 = NAND(b, nand1);
// Gate 4: NAND of nand2 and nand3
const result = NAND(nand2, nand3);
return result;
}
// Test all combinations
console.log("A B | XOR");
console.log("----------");
console.log(`0 0 | ${XOR_from_NAND(0, 0) ? 1 : 0}`);
console.log(`0 1 | ${XOR_from_NAND(0, 1) ? 1 : 0}`);
console.log(`1 0 | ${XOR_from_NAND(1, 0) ? 1 : 0}`);
console.log(`1 1 | ${XOR_from_NAND(1, 1) ? 1 : 0}`);
// Expected output:
// A B | XOR
// ----------
// 0 0 | 0
// 0 1 | 1
// 1 0 | 1
// 1 1 | 0
Step-by-Step Trace
For A=1, B=0:
nand1 = NAND(1, 0) = !(1 && 0) = !0 = 1
nand2 = NAND(1, 1) = !(1 && 1) = !1 = 0
nand3 = NAND(0, 1) = !(0 && 1) = !0 = 1
result = NAND(0, 1) = !(0 && 1) = !0 = 1 ✓
For A=1, B=1:
nand1 = NAND(1, 1) = !(1 && 1) = !1 = 0
nand2 = NAND(1, 0) = !(1 && 0) = !0 = 1
nand3 = NAND(1, 0) = !(1 && 0) = !0 = 1
result = NAND(1, 1) = !(1 && 1) = !1 = 0 ✓
Building Other Gates from NAND
function NOT_from_NAND(a) {
return NAND(a, a);
}
function AND_from_NAND(a, b) {
const nand = NAND(a, b);
return NOT_from_NAND(nand);
}
function OR_from_NAND(a, b) {
const notA = NOT_from_NAND(a);
const notB = NOT_from_NAND(b);
return NAND(notA, notB);
}
function NOR_from_NAND(a, b) {
const or = OR_from_NAND(a, b);
return NOT_from_NAND(or);
}
function XNOR_from_NAND(a, b) {
const xor = XOR_from_NAND(a, b);
return NOT_from_NAND(xor);
}
// Test
console.log("NOT 1:", NOT_from_NAND(1)); // 0
console.log("AND(1,0):", AND_from_NAND(1,0)); // 0
console.log("OR(1,0):", OR_from_NAND(1,0)); // 1
console.log("XOR(1,0):", XOR_from_NAND(1,0)); // 1
Circuit Diagram (ASCII)
A ----+----[NAND]---- nand1 ----+---- [NAND]---- nand2 ----+
| | | |
B ----+-------+ | |
| | |
+----[NAND]---- nand3 -----+---- [NAND]-------------- XOR
|
+----------------------+
Alternative: 5 NAND Implementation
function XOR_5gates(a, b) {
// XOR = (A AND NOT B) OR (NOT A AND B)
// Build NOT gates
const notA = NAND(a, a);
const notB = NAND(b, b);
// Build AND gates using NAND
const aAndNotB = NAND(NAND(a, notB), NAND(a, notB));
const notAAndB = NAND(NAND(notA, b), NAND(notA, b));
// Build OR using NAND
const result = NAND(NAND(aAndNotB, aAndNotB), NAND(notAAndB, notAAndB));
return result;
}
// This uses more gates but follows the logical formula directly
Truth Table Verification
function verifyXOR() {
const inputs = [[0,0], [0,1], [1,0], [1,1]];
const expected = [0, 1, 1, 0];
console.log("Verification:");
for (let i = 0; i < inputs.length; i++) {
const [a, b] = inputs[i];
const result = XOR_from_NAND(a, b) ? 1 : 0;
const match = result === expected[i] ? "✓" : "✗";
console.log(`XOR(${a}, ${b}) = ${result} ${match}`);
}
}
verifyXOR();
Why NAND is Universal
Functional completeness: Any boolean function can be expressed using only NAND.
Practical importance: NAND gates are easy to manufacture in hardware (transistor implementation is simple).
NOR is also universal: Same properties, different implementation.
Complexity
Gates needed for XOR: 4 (optimal)
Alternative methods: 5 gates (easier to understand)
Time complexity: O(1) - constant number of operations
Space complexity: O(1)
Real-World Applications
- CPU design: All logic gates in processors
- Error detection: Parity bits use XOR
- Cryptography: XOR for encryption
- Memory: XOR for error correction codes
Common Mistakes
- Wrong gate count: Using more than 4 NAND gates
- Incorrect wiring: Wrong connections between gates
- Not testing all cases: Must verify all 4 input combinations
- Confusing XOR with OR: XOR is exclusive OR (not both)
Follow-Up Questions
Q: Build half adder using NAND?
A: Sum = XOR, Carry = AND (both from NAND)
Q: Build full adder?
A: Use two half adders and an OR gate
Q: Why not use NOR instead?
A: NOR is also universal, choice depends on manufacturing
Related Problems
