CSC263 Computer Org & Arch I

Boolean Algebra

Boolean algebra is the algebra of logical variables and operations. Variables have the possible values 1 (True) and 0 (False). The basic operators are AND (represented by the symbol ·), OR (represented by the symbol +), and NOT (represented by ). Sometimes we will represent NOT with the symbol '. When it is not ambiguous, we can leave out the · and just write AB for A·B.

As in arithmetic, multiple logical operations can be combined in a single expression. If there are no parentheses, the order of precedence is:

Truth Tables

Truth tables provide a convenient way to define the meaning of a logical operator or function. In the truth table there is a column for each input variable and a column for the funcion, and a row for each of the possible input values. Since each input variable can take on values 0 and 1, there are 2^N rows for a function of N inputs. In each row the value of the function for the given inputs is placed the column for the function. The truth tables for the basic logical operators are:

P	Q	P AND Q P·Q	P OR Q P+Q	NOT P P
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

Axioms

The axioms of Boolean algebra define the way that Boolean operations are interpreted.

P · Q = Q · P	P + Q = Q + P	Commutative Laws
P · (Q · R) = (P · Q) · R	P + (Q + R) = (P + Q) + R	Associative Laws
P · (Q + R) = (P · Q) + (P · R)	P + (Q · R) = (P + Q) · (P + R)	Distributive Laws
1 · P = P	0 + P = P	Identity Elements
P · P = 0	P + P = 1	Inverse Elements

Identities

The following important identities can be derived from the axioms.

0 · P = 0	1 + P = 1
P · P = P	P + P = P	Idempotent Law
P · (P + Q) = P	P + (P · Q) = P	Law of Absorption
P · (P + Q) = P · Q	P + (P · Q) = P + Q	Law of Common Identities
P · Q = P + Q	P + Q = P · Q	DeMorgan's Laws

Using Truth Tables to Prove Equivalence

We can use truth tables to verify whether two expressions are equivalent: write out the truth table for both expressions, and see whether they have the same value in every row of the table. For example, the following uses truth tables to verify that A · (A + B) = A · B. Since the values in each row of the last two columns is the same, the two expressions are equivalent.

A	B	A	A + B	A · (A + B)	A · B
0	0	1	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	1	0	1	1	1

Here is another example, where we show that ~D · E = D + E

D	E	D	E	D · E	~D · E	D + E
0	0	1	1	0	1	1
0	1	1	0	1	0	0
1	0	0	1	0	1	1
1	1	0	0	0	1	1

Simplifying Expressions Algebraically

We can use the axioms to prove the identities algebraically and we can use both to simplify Boolean expressions algebraically. For example,

     A + AB = A · (1 + B)
            = A · (1)
            = A


     ~D · E = ~D + E (DeMorgan)
            = D + E