APDR

Boolean Algebra and Minimisation Lab

Algorithms, Programming, and Data Representation · Module 92313 · Chapter 12a

Predict first, then reveal. Check Boolean identities, build functions from NAND, minimise with maps, compare representations, and prevent a circuit glitch.

How the lab works

  1. Predict. Commit to an answer before the stage moves.
  2. Rate your confidence. A sure but wrong answer is useful; it appears under Your results.
  3. Watch the reveal. Follow the truth rows, gate construction, grouping, or signal handoff, then review the linked guide section.
  4. Explore. Finish an experiment to open its controls and tick its lab skill.

1.2 Identity checks: compare every row

Check an identity by evaluating both sides on every input row. A law is not established by a few examples, but a counterexample is enough to disprove it.

Equal outputs on every row mean the expressions are equivalent

Choose an identity
Or try your own

Use x, y, 0, 1, + for or, xy or x·y for and, ′ for not, ⊕ and brackets.

1.3 NAND completeness: build basic gates

NAND means NOT-AND: its output is 0 only when both inputs are 1. Every function here must be wired from that one gate.

The wiring changes the function while the gate type stays NAND

Choose a construction

1.4 Karnaugh maps: group adjacent ones

Rows and columns use Gray-code order, so neighbouring cells differ in one input. A group of four removes two changing variables; groups may wrap around map edges.

Bit order is A,B,C · columns BC are 00, 01, 11, 10

Map a truth set

Small cover: —

Or try your own

Numbers 0 to 7 with A as the top bit, or click cells on the map: 0 → 1 → d → 0.

1.5 Shannon expansion: split on an input

Setting a variable to 0 and 1 gives two cofactors. A fixed variable order turns these splits into an OBDD; reduction removes duplicate tests and subgraphs.

The selected variable chooses between its two cofactors

Choose a function and an order

The mux A?B:C is AB + A′C. Use A, B, C, 0, 1, + for or, AB or A·B for and, ′ for not, ⊕ and brackets.

—

1.5 Algebraic normal form: transform truth rows

The Möbius transform converts a truth table into coefficients of monomials. The selected terms are combined with XOR over F2.

Coefficient order: 1, B, A, AB

Transform a function

ANF: —

Or try your own

Four bits for rows 00, 01, 10, 11, or click a cell in the f row.

1.6 Static-1 hazards: cover the handoff

In f=xy+x'z, the two product paths can switch at different times when x changes. Follow what each path does during the change.

Illustrative unequal path delays · the timing is not a hardware measurement

Explore the transition

Output: —

Your results

Personal study lab based on the supplied APDR Chapter 12a guide and “APDR lecture01 - extended.pdf” (48 slides). Written in my own words; no lecture pages or figures are reproduced. Not an official FAU publication; check course details against the current materials. Made by Thanate Amornjiraporn (Focus).