Digital Logic 1/Boolean Logic

Basic Ideas and Concepts

• What is a truth table and what can it do
• Mapping a function on a truth table and determining all possible outputs
• Applying principles of Boolean Algebra to minimize given function
• Learn how to apply minterms and maxterms expansion to a truth table

Truth Tables

A truth table is basically a representation of all the possible input combinations and the functional output of each of those combinations. It will tell you on a case-by-case basis, what will the functional output be in every input instance.

We need a way to represent the 3 basic logic operations in algebraic formulas. (AND, OR, NOT)
Therefore we adopt the following standards for those representations:
A AND B = $A\cdot B=AB$
A OR B = $A+B$
NOT A (Inverted A) = $\bar{A}$

For a simple example, a truth table of the AND gate is given below.

a and b

a	b	f = a b
0	0	0
0	1	0
1	0	0
1	1	1

In general the number of rows in a truth table will be $2^n,$, where n is the number of variables. So in a 3 variable function where all the inputs are products, the following would be the truth table.

a and b and c

a	b	c	f = a b c
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Boolean Algebra

We introduce rules of Boolean Algebra to help us deal with simplifying more complex functions. The rules that should be learned are as follows.

Boolean Algebra Theorems and Axioms

Single Variable	Multi-Variable
$0\cdot 0=0$	$x\cdot y=y\cdot x$
$1+1=1$	$x+y=y+x$
$1\cdot 1=1$	$x\cdot (y\cdot z)=(x\cdot y)\cdot z$
$0+0=0$	$x+(y+z)=(x+y)+z$
$0\cdot 1=1\cdot 0=0$	$x\cdot (y+z)=x\cdot y+x\cdot z$
$1+0=0+1=1$	$x+(y\cdot z)=(x+y)\cdot (x+z)$
If $x=0$ then $\bar{x}=1$	$x+x\cdot y=x$
If $x=1$ then $\bar{x}=0$	$x\cdot (x+y)=x$
$x\cdot 0=0$	$x\cdot y+x\cdot \bar{y}=x$
$x+1=1$	$(x+y)\cdot (x+\bar{y})=x$
$x\cdot 1=x$	$\overline{x\cdot y}=\bar{x}+\bar{y}$
$x+0=x$	$\overline{x+y}=\bar{x}\cdot \bar{y}$
$x\cdot x=x$	$x+\bar{x}\cdot y=x+y$
$x+x=x$	$x\cdot (\bar{x}+y)=x\cdot y$
$x\cdot \bar{x}=0$	$x\cdot y+y\cdot z+\bar{x}\cdot z=x\cdot y+\bar{x}\cdot z$
$x+\bar{x}=1$	$(x+y)\cdot (y+z)\cdot (\bar{x}+z)=(x+y)\cdot (\bar{x}+z)$
$\overline{\stackrel{‾}{x}}=x$

Activity

Formulate a truth table for the given function below:

$f(a,b,c)=\bar{a}bc+bc+\overline{ab}c$