[ENGN3213 Home]

Theorems of Boolean Algebra

Here are some of the most important theorems of boolean algebra.

1.

$X \cdot 0 = 0$

2.

$X \cdot 1 = X$

3.

$X \cdot X = X$

4.

$X \cdot \overline{X} = 0$

5.

X + 0 = X

6.

X+1 = 1

7.

X+X = X

8.

$X+\overline{X} = 1$

9.

X+Y = Y+X

10.

$X \cdot Y = Y \cdot X$

11.

X + (Y + Z) = (X+Y) +Z

12.

X(YZ) = (XY)Z

13.

X(Y+Z) = XY + XZ

14.

(W+X)(Y+Z) = WY + XY + WZ +XZ

15.

X+XY = X

16.

$X + \overline{X}Y = X + Y$

De Morgan's laws:

17.

$\overline{X+Y} = \overline{X} \cdot \overline{Y}$

18.

$\overline{X \cdot Y} = \overline{X} + \overline{Y}$

These theorems can be proved in a straightforward way: write down the truth tables for the left and right sides of each asserted equality and check that they are the same.

These theorems help us simplify boolean expressions, such as

$$X = \overline{(\overline{A}+C)\cdot (B + \overline{D})}$$ (2)

We would like to reduce this to an expression involving only the variables and complements, as follows:

$$\begin{array}{rl} X & = \overline{(\overline{A}+C)} + \overli... ...\\ & = A \cdot \overline{C} + \overline{B} \cdot D \end{array}$$

Exercise. Determine which theorems are being applied in each step.

[ENGN3213 Home]