Boolean Logic

• A Boolean function is a function that operates on binary inputs and returns binary outputs.
• Any Boolean function can be realized using Nand.
• De Morgan's laws are important rules in Boolean algebra:
  • Not (A And B) = Not A Or Not B
  • Not (A Or B) = Not A And Not B

This is truth table for Nand.

If we set both A and B to the same variable X, the truth table is equal to the Not truth table.

Not X = X Nand X.

Since And is equal to Not Nand，and Not can be expressed using Nand:

A And B = Not (A Nand B) = (A Nand B) Nand (A Nand B)

Accroding to De Morgan's laws, it can be proven that Or can also be expressed using Nand:

A Or B = Not (Not A and Not B)

Boolean Arithmetic

In the ALU design project, there is a description:
if (f == 1) sets out = x + y, else sets out = x & y

Equal to:

• Calculate sets out = x + y

  Add16(a=a, b=b, out=aAddb);

• Calculate sets out = x & y

  And16(a=a, b=b, out=aAndb);

• Use Mux for branch operation

  Mux16(a=aAddb, b=aAndb, sel=f, out=out);