Boolean Algebra

Boolean Values and Operations

Boolean algebra works with two values:

• 0 (false)
• 1 (true)

Basic Operations

Operation	Symbol	Alternative
AND	$\cdot$ or $\land$	$xy$
OR	$+$ or $\lor$	$x + y$
NOT	$\overline{x}$ or $\neg$	$x'$

Truth Tables for Basic Operations

AND ($x \cdot y$)

$x$	$y$	$x \cdot y$
0	0	0
0	1	0
1	0	0
1	1	1

OR ($x + y$)

$x$	$y$	$x + y$
0	0	0
0	1	1
1	0	1
1	1	1

NOT ($\overline{x}$)

$x$	$\overline{x}$
0	1
1	0

Boolean Algebra Laws

Identity Laws

$x + 0 = x$ $x \cdot 1 = x$

Null Laws

$x + 1 = 1$ $x \cdot 0 = 0$

Idempotent Laws

$x + x = x$ $x \cdot x = x$

Complement Laws

$x + \overline{x} = 1$ $x \cdot \overline{x} = 0$

Involution Law

$\overline{\overline{x}} = x$

Commutative Laws

$x + y = y + x$ $x \cdot y = y \cdot x$

Associative Laws

$(x + y) + z = x + (y + z)$ $(x \cdot y) \cdot z = x \cdot (y \cdot z)$

Distributive Laws

$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ $x + (y \cdot z) = (x + y) \cdot (x + z)$

De Morgan's Laws

$\overline{x + y} = \overline{x} \cdot \overline{y}$ $\overline{x \cdot y} = \overline{x} + \overline{y}$

Absorption Laws

$x + (x \cdot y) = x$ $x \cdot (x + y) = x$

Logic Gates

Basic Gates

Gate	Symbol	Boolean Expression
AND	$\land$	$F = A \cdot B$
OR	$\lor$	$F = A + B$
NOT	—	$F = \overline{A}$
NAND	—	$F = \overline{A \cdot B}$
NOR	—	$F = \overline{A + B}$
XOR	$\oplus$	$F = A \oplus B$
XNOR	—	$F = \overline{A \oplus B}$

XOR Properties

$A \oplus B = (A \cdot \overline{B}) + (\overline{A} \cdot B)$ $A \oplus B = (A + B) \cdot \overline{(A \cdot B)}$ $A \oplus 0 = A$ $A \oplus 1 = \overline{A}$ $A \oplus A = 0$ $A \oplus \overline{A} = 1$

Canonical Forms

Minterm and Maxterm

For $n$ variables, a minterm is an AND of all variables (each complemented or not). A maxterm is an OR of all variables.

For $n = 2$ with variables $x, y$:

$x$	$y$	Minterm	Maxterm
0	0	$\overline{x}\overline{y}$ ($m_0$)	$x + y$ ($M_0$)
0	1	$\overline{x}y$ ($m_1$)	$x + \overline{y}$ ($M_1$)
1	0	$x\overline{y}$ ($m_2$)	$\overline{x} + y$ ($M_2$)
1	1	$xy$ ($m_3$)	$\overline{x} + \overline{y}$ ($M_3$)

Disjunctive Normal Form (DNF)

Sum of Products (SOP): OR of minterms where function is 1

$F = \sum m(i_1, i_2, \ldots)$

Conjunctive Normal Form (CNF)

Product of Sums (POS): AND of maxterms where function is 0

$F = \prod M(j_1, j_2, \ldots)$

Example

For $F(x,y) = xy + \overline{x}y$:

• DNF: $F = m_1 + m_3 = \sum m(1, 3)$
• CNF: $F = M_0 \cdot M_2 = \prod M(0, 2)$

Simplification Techniques

Algebraic Simplification

Example: Simplify $F = xy + x\overline{y} + \overline{x}y$

$F = x(y + \overline{y}) + \overline{x}y$ $= x \cdot 1 + \overline{x}y$ $= x + \overline{x}y$ $= (x + \overline{x})(x + y) \text{ (distributive)}$ $= 1 \cdot (x + y)$ $= x + y$

Karnaugh Maps (K-maps)

For 2 variables:

	$\overline{y}$	$y$
$\overline{x}$	$m_0$	$m_1$
$x$	$m_2$	$m_3$

Group adjacent 1s in powers of 2 to find simplified expression.

Functional Completeness

A set of operations is functionally complete if any Boolean function can be expressed using only those operations.

Complete Sets

• $\{AND, OR, NOT\}$
• $\{AND, NOT\}$
• $\{OR, NOT\}$
• $\{NAND\}$ alone!
• $\{NOR\}$ alone!

Expressing with NAND

$\overline{x} = x \text{ NAND } x$ $x \cdot y = (x \text{ NAND } y) \text{ NAND } (x \text{ NAND } y)$ $x + y = (x \text{ NAND } x) \text{ NAND } (y \text{ NAND } y)$