Loading page…
Master the fundamental concepts of digital logic & boolean algebra through this focused micro-challenge.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksThe NAND gate (NOT-AND) outputs 0 only when both inputs are 1. Every other basic gate can be built from NAND alone, which is why foundry standard-cell libraries often ship millions of identical NAND2 cells.
Truth table for NAND(A, B):
| A | B | Out |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND(A, A)NAND(NAND(A,B), NAND(A,B))NAND(NOT A, NOT B)For example, NOT(1) becomes NAND(1,1) = 0, and AND(1,0) chains two NAND calls to yield 0.
cLoading…
For this exercise, you will implement each derived gate as a pure function of nand(a, b) only. This task asks you to prove universality in code, the same reduction step nand2tetris uses before students wire their first ALU.
Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.
For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.
NAND is universal: every other gate can be wired from NAND gates alone. Implement nand(a, b) as your only primitive, build the other gates from it, and use them to evaluate whole circuits written as nested gate expressions. For each circuit, print its size in NAND gates and its truth table.
Each gate must be computed using only calls to nand. Its cost is the number of NAND gates in the standard construction:
| Gate | Construction | NAND gates |
|---|---|---|
nand(a,b) | primitive | 1 |
not(a) | nand(a,a) | 1 |
and(a,b) | not(nand(a,b)) | 2 |
or(a,b) | nand(not(a), not(b)) | 3 |
nor(a,b) | not(or(a,b)) | 4 |
xor(a,b) | t = nand(a,b); nand(nand(a,t), nand(b,t)) | 4 |
xnor(a,b) | not(xor(a,b)) | 5 |
One circuit per line: a gate expression over single lower-case letter variables and the constants 0 and 1, e.g. or(and(a,b), not(c)). Spaces may appear anywhere. A variable name is never a gate name.
For each line:
cLoading…
With no variables, print | out and a single row | <result>. Print a blank line between circuits.
If a line is malformed, print circuit: <line without spaces> followed by error: unknown gate NAME for an unrecognised gate name, error: not takes 1 input or error: GATE takes 2 inputs for a gate called with the wrong number of arguments, or error: syntax for anything else.
Input:
cLoading…
Output:
cLoading…
nand primitive; every other gate is a function built only from nand calls.Hidden tests cover nor/xnor/nand, a variable repeated in several places, and the three error messages.