Truth Tabels and Canonical Representations

A Truth Table is a way of specifying a boolean function, for example $f(x, y, z)$ depends on three boolean inputs, $x$, $y$ and $z$ as so:

x y z f(x, y, z)      x y z f(x, y, z)
================      ================
0 0 0          0       1 0 0         1
0 0 1          0       1 0 1         0
0 1 0          1       1 1 0         1
0 1 1          0       1 1 1         0

From here, we can create the Canonical Representation, to do that you:

Take every row where the output is 1.
and together each literal in that row.
Apply not to each literal that is 0.
or together each of these terms.

For example, we care about rows 3, 5 and 7:

Row 3: (not x) and y and (not z)
Row 5: x and (not y) and (not z)
Row 7: x and y and (not z)

Function:

   (not x) and y and (not z)
or x and (not y) and (not z)
or x and y and (not z)

Or $\bar{x}y\bar{z} + x\bar{y}\bar{z} + xy\bar{z}$.

This also shows that all boolean functions can be expressed with and and or.

Gates

A gate is a physical device that implements a boolean function.

The NAND gate is complete, any boolean function can be implemented using just that gate. (The NOR gate is also complete.)

Symbols for reference.

Multiplexors and Demulitplexors

A multiplexor (multiplexer? spelling?) has 3 inputs - one is the selection bit that determines which of other inputs the output copies. A demultiplexor does the opposite, taking 2 inputs and providing two outputs. The selection input determines which of outputs the other input is sent to.

Variants

The gates can have multi-bit versions that take inputs of say 32 bits. For basic gates these can be constructed by duplicating the gate.

Some gates can also be multi-way, taking more inputs and working in the way you’d expect.

DeMorgan’s Laws

DeMorgan’s Laws are a pair of transformations on boolean logic.

\[\overline{A \cup B} = \overline{A} \cap \overline{B}\] \[\overline{A \cap B} = \overline{A} \cup \overline{B}\]

Exercises

You start with Nand. Instructions for HDL.

Basic Gates

Not(a)    = Nand(a, a)
And(a, b) = Not(Nand(a, b))
Or(a, b)  = Nand(Not(a), Not(b))
Xor(a, b) = Or(And(a, Not(b)),
               And(Not(a), b))
Mux(a, b, sel) = Or(And(Not(sel), a),
                    And(sel, b)))

DMux(in, sel) = {
  And(Not(sel), in),
  And(sel, in)
}

Example HDL:

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=a, b=notb, out=c);
    And(a=nota, b=b, out=d);
    Or(a=c, b=d, out=out);
}

Buses of bits are indexed from the right, eg:

/**
 * 8-way 16-bit multiplexor:
 * out = a if sel == 000
 *       b if sel == 001
 *       etc.
 *       h if sel == 111
 */

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:
    Mux16(a=a, b=b, sel=sel[0], out=i);
    Mux16(a=c, b=d, sel=sel[0], out=j);
    Mux16(a=e, b=f, sel=sel[0], out=k);
    Mux16(a=g, b=h, sel=sel[0], out=l);

    Mux16(a=i, b=j, sel=sel[1], out=m);
    Mux16(a=k, b=l, sel=sel[1], out=n);

    Mux16(a=m, b=n, sel=sel[2], out=out);
}