banner_BooleanFunctions.gif (10708 bytes)

A binary variable can have two possible states, namely ‘0’ and ‘1’. A Boolean function is an expression formed with binary variables and logical operators, e.g. X=AB+CD+AD. In essence a truth table is a list which defines a Boolean function. For example, lets consider the truth table shown in Table 1-8. Note that the Function (X) is equal to 1 if A=0, B=0, C=1; otherwise X=0. The algebraic expression representing this function is therefore . Accordingly, the logic circuit is as shown in Figure1-10.

Input			Output
A	B	C	X
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

Table 1-8 Truth Table

Figure 1-10 Logic Circuit

Boolean Algebra

Definition:

Boolean Algebra: A mathematical system for formulating logical statements with symbols so that problems can be solved in a manner to ordinary algebra.

In short, Boolean algebra is the mathematics of digital systems. The basic rules for Boolean addition and multiplication are presented in Table 1-9

Addition Rules	Multiplication Rules
0 + 0 = 0	0 ^.0 = 0
0 + 1 = 1	0 ^.1 = 0
1 + 0 = 1	1 ^.0 = 0
1 + 1 = 1	1 ^.1 = 1

Table 1-9 Boolean Addition and Multiplication

Laws of Boolean Algebra

Commutative Laws

The commutative law of addition for two variables is algebraically expressed as

A + B = B + A

The commutative law of multiplication for two variables is expressed as

AB = BA

In summary, the order in which the variables are ORed or ANDed make no difference.

Associative Laws

The associative law of addition of three variables is expressed as

A + (B + C) = (A + B) + C

The associative law of multiplication of three variables is expressed as

A(BC) = (AB)C

In summary, ORing or ANDing a grouping of variables produces the same result regardless of the grouping of the variables.

Distributive Law

The distributive law of three variables is expressed as follows:

A (B+C) = AB + AC

This law states that ORing several variables and ANDing the result is equivalent of ANDing the single variable with each of the variables in the grouping, then ORing the result.