Digital Logic - Boolean Algebra

A mathematical tool used in describing, analyzing, designing and implementing digital circuits. A Boolean algebra is the combinations of variables and operators. It has one or more inputs and produces an output in the range of 0 or 1. The complement of a variable is shown by a bar over the letter.

Boolean equation can be represented in two forms:

l  Boolean Addition (Sum-of-products(SOP)

It is equivalent to the OR operation.  A sum term is produced by an OR operation with no AND operations involved. A sum term is equal to 1 when one or more of the literals in the term are 1. A sum term is equal to 0 only if each of the literals is 0.

l  Boolean Multiplication (Product-of –sums(POS))

It is equivalent to the AND operation. A product term is produced by an AND operation with no OR operations involved. A sum term is equal to 1 if each of the literals in the term is 1. A sum term is equal to 0 when one or more of literals are 0.

Boolean Function

l  Binary variables/literals (complemented or not)

l  Binary operators : (＋→ OR) and ( · → AND)

l  Unary operator : ( ‘ → NO )

l  Equal sign

l  Parentheses

Example : F1(a,b,c)=ab’+abc’+b’(a’+c’)

   Table Basic Laws of Boolean Algebra

	AND Form	OR Form
Identity Law	A·1 = A	A+0 = A
Zero and One Law	A·0 = 0	A+1 = 1
Inverse Law	A·A’ = 0	A+A’ = 1
Idempotent Law	A·A = A	A+A = A
Commutative Law	A·B = B·A	A+B = B+A
Associative Law	A·(B·C) = (A·B) ·C	A+(B+C) = (A+B) + C
Distributive Law	A+(B·C) = (
	A(A+B) =A	A+A·B = A A+A’B = A+B
DeMorgan’s Law	(A·B)’ = A’+B’	(A+B)’= A’·B’
Double Complement Law	X=X

Other example Law of Boolean Algebra

Absorption Law derivation:

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

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

            = A·1                                                                                   =A+0

            = A                                                                                      =A

A+A’B = (A+B’) ·(A+B)       A·(A’+B) = A·A’+A·B         A·B+A·B’ = A·(B+B’)         (A+B) ·(A+B’) = A+(B+B’)

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

            =A+B                                        =A·B                                  =A                                                =A

Karnaugh Maps

A Karnaugh map is two-dimensional truth-table.

Two inputs A and B can take on values of either 0 or 1, high or low, open or closed, True or False, as the case may be. There are 2² = 4 combinations of inputs producing an output. These four outputs may be observed on a lamp in the relay ladder logic, on a logic probe on the gate diagram. These outputs may be recorded in the truth table, or in the Karnaugh map. Look at the Karnaugh map as being a rearranged truth table. The Output of the Boolean equation may be computed by the laws of Boolean algebra and transfered to the truth table or Karnaugh map.

The Karnaugh map is organized so that we may see that commonality.

Rules of Simplification

1.  No zeros allowed.

2.  No diagonals.

3.  Only power of 2 number of cells in each group.

7.Wrap around allowed.

8.Fewest number of groups possible.

   Example to grouping the 1s

Example:

YU HONG SHENG   

B031210099