Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Fuzipedia

I’m writing this paper on Boolean Arithmetic and Boolean Logic from my personal study notes. This will come in handy later when I start publishing my notes and papers on quantum computing and scalable zero knowledge circuits.

CONSTANT-0

\[\displaylines{C0(0) = 0 \\ C0(1) = 0}\]

AND

\[\displaylines{x \land y \\ (x \cdot y)\\\\ x \land y(0,0) = 0\\ x \land y(0,1) = 0\\ x \land y(1,0) = 0\\ x \land y(1,1) = 1}\]

X AND NOT Y

\[\displaylines{x \land \bar{y}\\ (x \cdot \bar{y}) \\ \\ x \land \bar{y}(0,0) = 0\\ x \land \bar{y}(0,1) = 0\\ x \land \bar{y}(1,0) = 1\\ x \land \bar{y}(1,1) = 0}\]

X

\[\displaylines{x\\ \\ x(0,0) = 0\\ x(0,1) = 0\\ x(1,0) = 1\\ x(1,1) = 1}\]

NOT X AND Y

\[\displaylines{\bar{x} \land y\\ (\bar{x} \cdot y)\\ \\ \bar{0} \land 0 = 0\\ \bar{0} \land 1 = 1\\ \bar{1} \land 0 = 0\\ \bar{1} \land 1 = 0}\]

Y

\[\displaylines{y\\ \\ y(0,0) = 0\\ y(0,1) = 1\\ y(1,0) = 0\\ y(1,1) = 1}\]

XOR

\[\displaylines{x \cdot \bar{y} \lor \bar{x} \cdot y\\ (x \cdot \bar{y} + \bar{x} \cdot y)\\ \\ x \cdot \bar{y} \lor \bar{x} \cdot y(0,0) = 0\\ x \cdot \bar{y} \lor \bar{x} \cdot y(0,1) = 1\\ x \cdot \bar{y} \lor \bar{x} \cdot y(1,0) = 1\\ x \cdot \bar{y} \lor \bar{x} \cdot y(0,0) = 0}\]

OR

\[\displaylines{x \lor y\\ (x + y)\\ \\ x \lor y(0,0) = 0\\ x \lor y(0,1) = 1\\ x \lor y(1,0) = 1\\ x \lor y(1,1) = 1}\]

NOR

\[\displaylines{\overline{x \lor y}\\ (\overline{x + y})\\ \\ \overline{x \lor y}(0,0) = 1\\ \overline{x \lor y}(0,1) = 0\\ \overline{x \lor y}(1,0) = 0\\ \overline{x \lor y}(1,1) = 0}\]

Equivalence

\[\displaylines{x \land y \lor \bar x \land \bar y\\ (x \cdot y + \bar x \cdot \bar y)\\ \\ (x \land y) \lor (\bar x \land \bar y)(0,0) = 1\\ (x \land y) \lor (\bar x \land \bar y)(0,1) = 0\\ (x \land y) \lor (\bar x \land \bar y)(1,0) = 0\\ (x \land y) \lor (\bar x \land \bar y)(1,1) = 1}\]

NOT Y

\[\displaylines{\bar y\\ \\ \bar y(0,0) = 1\\ \bar y(0,1) = 0\\ \bar y(1,0) = 1\\ \bar y(1,1) = 0}\]

IF Y THEN X

\[\displaylines{x \lor \bar y\\ (x + \bar y)\\ \\ x \lor \bar y(0,0) = 1\\ x \lor \bar y(0,1) = 0\\ x \lor \bar y(1,0) = 1\\ x \lor \bar y(1,1) = 1}\]

NOT X

\[\displaylines{\bar x\\ \\ \bar x(0,0) = 1\\ \bar x(0,1) = 1\\ \bar x(1,0) = 0\\ \bar x(1,1) = 0}\]

IF X THEN Y

\[\displaylines{\bar x \lor y\\ (\bar x + y)\\ \\ \bar x \lor y(0,0) = 1\\ \bar x \lor y(0,1) = 1\\ \bar x \lor y(1,0) = 0\\ \bar x \lor y(1,1) = 1}\]

NAND

\[\displaylines{\overline{x \land y}\\ (\overline{x + y})\\ \\ \overline{x \land y}(0, 0) = 1\\ \overline{x \land y}(0, 1) = 1\\ \overline{x \land y}(1, 0) = 1\\ \overline{x \land y}(1, 1) = 0}\]

CONSTANT-1

\[\displaylines{C1(0) = 1\\ C1(1) = 1}\]

Boolean Algebra Laws

Commutative Laws

\[\displaylines{x \land y = y \land x\\ x \lor y = y \lor x}\]

Associative Laws

\[\displaylines{x \land (y \land z) = (x \land y) \land z\\ x \lor (y \lor z) = (x \lor y) \lor z}\]

De Mlorgan Laws

\[\displaylines{\neg (x \land y) = \neg(x) \lor \neg(y)\\ \neg (x \lor y) = \neg(x) \land \neg(y)}\]

Idempotent Laws

\[\displaylines{x \land x = x\\ x \lor x = x}\]

Example

Consider the function:

\(\displaylines{\lnot(\lnot(x) \land \lnot(x \lor y))}\) Using the laws of Boolean Algebra we can simplify as:

De Morgan Law

\[\displaylines{\lnot(\lnot(x) \land \lnot(x \lor y))}\]

Associative Law

\[\displaylines{\lnot(\lnot(x) \land \lnot(x) \land \lnot(y))}\]

Idempotent Law

\[\displaylines{\lnot((\lnot(x) \land \lnot(x)) \land \lnot(y))}\]

De Morgan Law

\[\displaylines{\lnot(\lnot(x) \land \lnot(y))}\]

Double Negation

\[\displaylines{\lnot(\lnot(x)) \lor \lnot(\lnot(y))}\]

Reducing a Boolean expression into its simplest form is an NP-hard problem.

\[\displaylines{\lnot(\lnot(x) \land \lnot(x \lor y)) \sim x \lor y}\]

Synthesizing Boolean Functions from a truth table

xyzf(x,y,z)f3(x,y,z)f5(x,y,z)f7(x,y,z)
0000000
0010000
0101100
0110000
1001010
1010000
1101001
1110000
\[\displaylines{f_3(x,y,z) = \lnot(x) \land y \land \lnot(z)\\ f_5(x,y,z) = x \land \lnot(y) \land \lnot(z)\\ f_7(x,y,z) = x \land y \land \lnot(z)\\ f(x,y,z) = f_3(x,y,z) \lor f_5(x,y,z) \lor f_7(x,y,z)\\ \\ f(x,y,z) = (\lnot(x) \land y \land \lnot (z)) \lor (x \land \lnot(y) \land \lnot(z)) \lor (x \land \lnot(y) \land \lnot (z)) \lor (x \land y \land \lnot (z))}\]

Steps

  1. Focus only on the rows in which the function’s value is 1 (Rows 3, 5, 7)

  2. For such row i we define a boolean function fi that returns 0 for all the variables in row i for which the function returns 1 (last 3 columns)

  3. Each of these functions fi can be represented by a conjunction (AND) of three terms one for each variable x, y, and z which is either the variable or its negation depending on whether the value of this variable is 1 or 0 in row i.

  4. This yields to the three functions f3, f5, and f7

  5. Any Boolean function can be systematically represented by a Boolean expression that has a very specific structure: it is the disjunction (Or-ing) of all the conjunctive (And-ing) functions fi whose function was described.

  6. See Disjunctive Normal Form

The Power of NAND

NAND is a versatile boolean operator which can be used to build other boolean circuits.

Lemma 1

Any Boolean function can be represented by a Boolean expression containing only AND, OR, and NOT operators.

Lemma 2

Any Boolean function can be represented by a Boolean expression containing only NOT and AND operators.

Theorem

Any Boolean function can be represented by a Boolean expression containing only NAND operators.

Proof

An insepction of the NAND truth table

\[\displaylines{\overline{x \land y}\\ (\overline{x + y})\\ \\ \overline{x \land y}(0, 0) = 1\\ \overline{x \land y}(0, 1) = 1\\ \overline{x \land y}(1, 0) = 1\\ \overline{x \land y}(1, 1) = 0}\]

We can discover the two properties:

\[\displaylines{\lnot(x) = \barwedge(x,x)}\]

If you set both the x and y variables of the NAND function to the same value (0 or 1) the function evaluates to the negation of that value.

\[\displaylines{\land(x,y) = \lnot(\barwedge(x,y))}\]

Logic Gates Diagrams

AND OR NOT NAND

XOR Using AND and OR Gates

HDL pseudo-code

/* Xor (exclusive or) gate: If a!=b out=1 else out=0 */

CHIP Xor {
  IN a, b;
  OUT out;
  PARTS:
  Not (in=a, out=nota);
  Not (in=b, out=notb);
  And (a=a, b=notb, out=w1);
  And (a=nota, b=b, out=w2);
  Or  (a=w1, b=w2, out=out);
}

Test

load Xor.hdl,
output-list a, b, out;
set a 0, set b 0,
eval, output;
set a 0, set b 1,
eval, output;
set a 1, set b 0,
eval, output;
set a 1, set b 1,
eval, output;
\[\displaylines{ XOR & \\ } \begin{array}{|c|c|c|} \hline a & b & out\\ \hline 0 & 0 & 0\\ \hline 0 & 1 & 1\\ \hline 1 & 0 & 1\\ \hline 1 & 1 & 0\\ \hline \end{array}\]

XOR XOR

Further Reading