Number Systems and Boolean Algebra

• Positional bases and fluent conversionBinary is how hardware stores state; hex is how humans read binary without going mad. One hex digit is exactly four bits, so conversion is regrouping, not arithmetic. Being able to read 0xDEADBEEF as a bit pattern without a calculator is a working requirement, not a party trick.1 hex digit = 4 bits = 1 nibble. 2 hex digits = 1 byte. 0x00-0xFF = 0-255.
• Signed representationsTwo's complement dominates because addition and subtraction use the same hardware and there is one zero. Negate by inverting all bits and adding one. The asymmetric range (-128 to +127 for 8 bits) and the overflow behaviour at the boundary are the source of a large fraction of embedded bugs.n-bit two's complement range: -2^(n-1) to 2^(n-1) - 1. Negate: invert and add 1.
• Fixed point and Q notationMicrocontrollers without an FPU represent fractions by agreeing where the binary point sits. Q15 means 15 fractional bits in a 16-bit word. Multiplication doubles the fractional bits and must be shifted back; this is where precision is silently lost.Qm.n: value = raw / 2^n. Multiplying two Qm.n numbers gives Q(2m).(2n) — shift right by n to restore.
• The Boolean operators and their gate symbolsAND, OR, NOT, XOR, NAND, NOR. NAND and NOR are functionally complete: any logic function can be built from either alone, which is why real silicon is largely NAND. XOR is the odd-parity/difference detector and appears everywhere in arithmetic and error detection.
• The laws, and De Morgan in particularIdentity, null, idempotent, complement, commutative, associative, distributive, absorption. De Morgan's theorems let you push a bubble through a gate: NOT(A AND B) = NOT A OR NOT B. This is how you convert a design into NAND-only form and how you read a schematic drawn with active-low signals.De Morgan: !(A.B) = !A + !B, and !(A+B) = !A . !B. 'Break the line, change the sign.'
• Truth tables, minterms and canonical formsAny function can be written as a sum of products (one term per row where the output is 1) or a product of sums. These canonical forms are always correct and never minimal, which is why minimisation exists.
• Karnaugh maps and don't-caresA K-map reorders the truth table so adjacent cells differ by one variable, making groupings visible. Group in powers of two, as large as possible, wrapping around edges. Don't-care cells can be included in groups when it makes them bigger, and excluded when it does not — free simplification.
• Active-low signalling and namingMany real signals assert low: RESET, CS, OE. Notation varies (nRESET, RESET_N, RESET with an overbar). Get the convention right in your schematics or you will invert a control signal and not notice until bring-up.

ProblemA safety interlock must assert an ENABLE output when: the door is closed (D=1) AND at least two of three sensors (S1, S2, S3) read healthy. Derive minimal logic and convert to NAND-only.

1. 1
   Build the truth table for the 'two of three' majority function M(S1,S2,S3). Output is 1 for the rows 011, 101, 110, 111 — that is 4 of the 8 rows.
2. 2
   Sum of products (canonical): M = !S1.S2.S3 + S1.!S2.S3 + S1.S2.!S3 + S1.S2.S3.
3. 3
   K-map the three variables. The four 1-cells group into three overlapping pairs: (S1.S2), (S1.S3), (S2.S3). Each pair covers the 111 cell, which is why they overlap.
4. 4
   Minimised: M = S1.S2 + S1.S3 + S2.S3. Three 2-input ANDs and one 3-input OR, down from four 3-input ANDs and a 4-input OR.
5. 5
   Add the door term: ENABLE = D . M = D . (S1.S2 + S1.S3 + S2.S3).
6. 6
   Convert to NAND-only. Start with the OR of ANDs. By De Morgan, A + B + C = !(!A . !B . !C), so an OR of terms is a NAND of the inverted terms.
7. 7
   Each AND term becomes a NAND followed by an inverter; but the inverter is cancelled by the De Morgan conversion of the OR. So: M = NAND( NAND(S1,S2), NAND(S1,S3), NAND(S2,S3) ). Three 2-input NANDs feeding one 3-input NAND.
8. 8
   Final ENABLE = D AND M = NAND(NAND(D, M), NAND(D, M)) — a NAND used as an inverter on a NAND. Or more cleanly, fold D into the structure.
9. 9
   Sanity check: put S1=1, S2=1, S3=0, D=1 through the NAND network by hand. NAND(1,1)=0, NAND(1,0)=1, NAND(1,0)=1. NAND(0,1,1)=1. M=1. With D=1, ENABLE=1. Correct.
10. 10
    Safety note: for a real interlock, consider what happens on a broken wire. If a broken sensor wire floats high, this design fails dangerous. Active-low sensor signals with pull-downs would fail safe. Logic minimisation does not excuse you from thinking about failure modes.

AnswerENABLE = D . (S1.S2 + S1.S3 + S2.S3), implemented as four NAND gates for the majority function plus a NAND-inverter pair for the door term. And the fail-safe polarity question matters more than the gate count.

Tool: Digital (hneemann) - open-source logic simulator

• Download Digital (GPL, Java, runs on any desktop OS) from its GitHub releases page and launch it.
• Place inputs (Components > IO > Input) for D, S1, S2, S3 and an output for ENABLE. Name each one via its properties dialog.
• Build your minimised expression with AND and OR gates from Components > Logic. Wire it up.
• Run the simulation (the play button) and click the inputs to toggle them. Verify the majority behaviour by hand on a few cases.
• Now let the tool check you: Analysis > Analyse Circuit. Digital generates the full truth table from your circuit.
• In the analysis window, use 'Create Circuit' from the minimised expression and compare the generated circuit to yours. If the tool's result has fewer gates than yours, find out why.
• Go the other way: Analysis > Synthesise, enter the truth table by hand, and let Digital generate a circuit. Confirm it matches your K-map result.
• Switch the implementation to NAND-only: in the analysis window there are options for NAND/NOR-only synthesis. Compare to your hand conversion.
• Add a test case component (Components > Misc > Test case) with a table of input/expected-output vectors, and run it. A green pass is machine-verified evidence your logic is correct — attach it to your project.

• nandgame - build a computer from NAND gatesfreeinteractive~120 minFree browser game. Play through the logic-gate levels at minimum. It builds De Morgan and functional-completeness intuition faster than any reading.
• Digital Circuit Projects (Kahn) - open textbookopen licencereading~150 minWork through the number systems and Boolean algebra chapters. Open-licensed and problem-rich.
• All About Circuits - Volume IV, Digitalfreereading~180 minChapters 1-8 cover numeration, binary arithmetic, logic gates, Boolean algebra and K-maps. Excellent K-map treatment.
• Digital (hneemann) simulatoropen licencetoolGPL. Circuit analysis, truth-table synthesis, NAND/NOR-only conversion and automated test cases. Your logic sandbox for the next two skills too.

Specify, minimise, implement and machine-verify a piece of real control logic: a 4-input priority encoder with an enable, or an equivalent function of your choosing with at least four inputs and two outputs.

Deliverables

• A written specification in plain English of what the logic must do, including its behaviour for every input combination — no 'don't care' left undefined without saying so deliberately.
• A complete truth table with any don't-care cells explicitly marked and justified.
• K-map minimisation worked by hand, photographed or drawn, for each output, with the groupings shown.
• The minimised Boolean expressions, plus a gate count comparison against the canonical sum-of-products form.
• A NAND-only (or NOR-only) conversion of one output, worked by hand with the De Morgan steps shown.
• A working circuit in Digital, with an automated test-case table covering every input combination, and a screenshot of the passing test.
• A conversion exercise: express your inputs and outputs as a hex value and show three specific input/output pairs in binary, hex and decimal.
• A fail-safe analysis: for at least two inputs, state what happens if that input is disconnected and floats, and whether the resulting behaviour is safe.

Acceptance criteria — how you know it is good enough

• The truth table is complete and every don't-care is deliberate.
• K-map groupings are maximal and correct; the tool's independently synthesised result agrees with the hand minimisation.
• The automated test case in Digital passes for all input combinations, not a sample.
• The NAND-only conversion is derived, with De Morgan steps shown, not guessed.
• The fail-safe analysis names a specific unsafe or safe outcome for each floating input.

If you want to push further

• Add a 4-bit two's complement adder/subtractor to the design and verify overflow detection with test vectors at the boundary values.
• Implement the same function using only a 16x1 lookup ROM and compare the resource cost and the timing to the gate implementation.

• I convert between binary, hex and decimal without a calculator for byte-sized values.
• I can negate a two's complement number and state the range of an n-bit signed word.
• I can apply De Morgan's theorems in both directions and convert to NAND-only form.
• I can minimise a 4-variable function with a K-map, including don't-cares.
• I build and machine-verify logic with automated test vectors rather than clicking through cases.
• I consider the behaviour of floating inputs before declaring a design correct.