Tue 24th Dec 2019

**Table of Contents**

- Truth Tabels and Canonical Representations
- Gates
- Multiplexors and Demulitplexors
- Variants
- DeMorgan’s Laws
- Exercises

# 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

gateis 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.)

# 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.

# 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);
}
```