Boolean functions
Boolean expressions
NOT(0 OR(1 AND 1)) =
NOT(0 OR 1) =
0
Boolean functions
f(x, y, z) = (x AND y) OR (NOT(x) AND z)
Boolean identities
Commutative laws - (x AND y) = (y AND x) - (x OR y) = (y OR x)
Associative laws - (x AND (y AND z)) = ((x AND y) AND z) - (x OR (y OR z)) = ((x OR y) OR z)
Distributive laws - (x AND (y OR z)) = (x AND y) OR (x AND z) - (x OR (y AND z)) = (x OR y) AND (x OR z)
De Morgan laws - NOT(x AND y) = NOT(x) OR NOT(y) - NOT(x OR y) = NOT(x) AND NOT(y)
Idempotent laws - (x AND x) = x - (x OR x) = x
Double negation law - NOT(NOT(x)) = x
Boolean algebra
NOT(NOT(x) AND NOT(x OR y)) =
NOT(NOT(x) AND NOT(x) AND NOT(y)) =
NOT(NOT(x) AND NOT(y)) =
NOT(NOT(x)) OR NOT(NOT(y)) =
(x OR y)
Truth table to boolean expression
Building a computer involves assembling logic gates from primitive operations. The first step is to convert a truth table to boolean expression.
| x | y | z | f | Boolean expression |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | (NOT(x) AND NOT(y) AND NOT(z)) |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | (NOT(x) AND y AND NOT(z)) |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | (x AND NOT(y) AND NOT(z)) |
| 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 |
After that we combine all these expressions with OR in between them:
(NOT(x) AND NOT(y) AND NOT(z)) OR (NOT(x) AND y AND NOT(z)) OR (x AND NOT(y) AND NOT(z)) =
(NOT(x) AND NOT(z)) OR (x AND NOT(y) AND NOT(z)) =
(NOT(x) AND NOT(z)) OR (NOT(y) AND NOT(z)) =
(NOT(x) AND NOT(z)) OR (NOT(y) AND NOT(z)) =
NOT(z) AND (NOT(x) OR NOT(y))
AND and NOT is bare minimum
Theorem. Any boolean function can be represented using an expression containing AND, OR, and NOT operations.
We can construct a computer using only AND, OR, and NOT gates. But we can also express OR in terms of AND and NOT by using De Morgan law:
NOT(x OR y) = NOT(x) AND NOT(y)
x OR y = NOT(NOT(x) AND NOT(y))
Theorem. Any boolean function can be represented using an expression containing AND and NOT operations.
NAND gate
Definition. (x NAND y) = NOT(x AND y)
| x | y | AND |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Electronics Projects: How to Create a Transistor NAND Gate Circuit
Theorem. Any boolean function can be represented using only NAND operations.
Proof:
- NOT(x) = (x NAND x)
- (x AND y) = NOT(x NAND y) = ((x NAND y) NAND (x NAND y))
Now we have proved that we can compute anything with just NAND gates.
Logic gates
A logic gate is a chip that is design to perform a simple computation. There are elementary and composite logic gates. Elementary logic gates use NAND, AND, OR, and NOT gates. Composite logic gates use more complex composition of elementary logic gates, such as MUX, ADDER, etc.
Composite gates: - triple-input AND
Hardware description language
HDL describes circuits. Most popular languages are VHDL and Verilog. VHDL and Verilog are more complex and allow loops to build chips.
Possible to program FPGA?
Hardware simulator helps verify that the circuit described in HDL works correctly.
A bus is an array of bits that we think as a single entity.
There is no algorithm that can build a computer perfectly. The problem is NP-complete, and existing algorithms are based on heuristics.