L3-2e6-digital.docx

Lecture 3: Boolean Algebra I  the Basics A knowledge of Boolean algebra serves two main purposes: firstly, to formally describe and define the function of a logic circuit; and secondly, by simplifying the Boolean expression defining a particular circuit, one can simplify the or reduce the associated hardware, ie make more efficient use of the available hardware resources. Learning Outcomes: On completing this lecture, you will be able to  prove a number of useful basic theorems from given Boolean axioms;  simplify and complement Boolean expressions;  define the fundamental logic operations AND, OR, Invert;  relate Boolean expressions to truth tables and logic diagrams. 3.1

Boolean Algebra Definitions and Axioms

So-called two-valued Boolean algebra comprises  the set of values B  0, 1 ,

 

  

variables a, b, c, …….. x, y, z which represent either element of B, a pair of binary operators “+” and “.” and a unary inverse operator denoted “  “ a set of basic algebraic relations called axioms which we subsequently use to build up a repertoire of useful theorems.

A binary operator here means a function f which operates on two variables, say a and b, to produce a dependent variable, say x

( a, b) 

f (a, b)  x  a  b in the case of  or  a.b in the case of .

Clearly a unary operator applies to a single variable. Because each variable is restricted to two possible values, it is most convenient to define the operations by means of truth tables, ie listings of function values for all possible valuecombinations of the independent variables: a 0 0 1 1

b 0 1 0 1

a+b 0 1 1 1

a 0 0 1 1

b 0 1 0 1

a.b 0 0 0 1

a 0 1

a 1 0

The + operator is known as the OR function in the logic domain; the function has a value of 1 if either or both of the independent variables has the value of 1. The Boolean multiplication operator is known as the AND function in the logic domain; the function evaluates to 1 only if both the independent variables have the value 1. Based on these definitions the following axiomatic relationships hold:

3-1

for a, b, c  B A1

Closure

(a)

a  bB

(b)

a.b  B

A2

Identity

(a)

a0a

(b)

a.1  a

A3

Commutation (a)

ab ba

(b)

a.b  b.a

A4

Distribution

(a) a.(b  c)  (a.b)  (a.c)

A5

Inverse

(a)

(b) a  (b.c)  (a  b).( a  c)

a  a  1

(b)

a.a  0

We must now check that the axioms do indeed accord with the definitions. Properties A1 are immediately obvious while the following truth tables verify A2: a 0 1

a+0 0+0=0 1+0=1

a 0 1

a.1 0.1=0 1.1=1

A3 may also be verified by truth table: a 0 0 1 1

b 0 1 0 1

a+b 0+0=0 0+1=1 1+0=1 1+1=1

b+a 0+0=0 1+0=1 0+1=1 1+1=1

a.b 0.0=0 0.1=0 1.0=0 1.1=1

b.a 0.0=0 1.0=0 0.1=0 1.1=1

We next consider A4(a) a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

b+c 0 1 1 1 0 1 1 1

a.(b+c) 0 0 0 0 0 1 1 1

a.b 0 0 0 0 0 0 1 1

a.c 0 0 0 0 0 1 0 1

(a.b)+(a.c) 0 0 0 0 0 1 1 1

Axiom A4(b) may be similarly verified and is left as an exercise. Finally, the A5 relations are verified from a 0 1

a 1 0

a+a 1 1

a.a 0 0

While much of the algebra is similar to standard algebra, the differences are that A4 (b) does not hold in standard algebra and there is no counterpart to the inverse function as defined here. Another important feature of Boolean algebra is duality. The set of (b) axioms

3-2

are said to be duals of the (a) axioms, and vice versa, in that a (b) axiom can be formed from its (a) counterpart by exchanging operators and identity elements:

  .

and

1  0

Thus for every theorem derived from one particular set of axioms, one can construct a dual theorem based on the corresponding set of dual axioms. 3.2

Some Theorems of Boolean Algebra

As stated earlier these theorems will subsequently be used for simplifying logic circuits and also, sometimes, for devising alternative logic networks to realise a particular function. The theorems are mainly proved using algebraic manipulation of the given axioms. Where this method becomes awkward, the truth table method may be used as an alternative. T1 (a)

xxx Proof:

x  x  ( x  x).1 from A2 (b)  ( x  x).( x  x) A5 (a )  x  x.x A4 (b)  x0 A5 (b) x A2 (a)

From the Duality Principle, we have the dual theorem T1 (b) T2 (a)

x 11 Proof:

x  1  ( x  1).1 from A2 (b)  ( x  1).( x  x) A5 (a )  x  1.x A4 (b)  x  x A2 (b) 1 A5 (a )

Again from duality, we have the dual theorem T2 (b) T3

 X   X

By truth table analysis we have X 0 1

X 1 0

3-3

(X)’ 0 1

x .0  0

x. x  x

T4(a)

X  Y  Z    X  Y   Z

X .Y . Z   X .Y . Z

and (b)

may also be readily proved by truth table analysis and again are left as exercises. T5 (a)

X

  Y  X .Y X 0 0 1 1

Y 0 1 0 1

X+Y 0 1 1 1

(X+Y)’ 1 0 0 0

X’ 1 1 0 0

Y’ 1 0 1 0

X’ . Y’ 1 0 0 0

 X .Y   X   Y 

The dual is the relation T5 (b)

T5 (a) and (b) constitute what are known as De Morgan’s laws.

3.3

Boolean Simplifications

As stated earlier, one of the primary purposes of developing a familiarity with Boolean algebra is to allow for the possibility of simplifying Boolean expressions and thereby saving hardware resources. We demonstrate some examples of such simplifications.

X  X .Y

Example 3.1: Simplify the expression Result:

X  X .Y

 X .1  X .Y  X . (1  Y )  X . (1)  X

Example 3.2: Simplify the expression Result

a.x  a. y  x. y      

a . x  a . y  x . y



a . x  a. y

a.x  a. y  x. y.1 a.x  a. y  x. y.a  a a.x  a. y  a.x. y  a.x. y a.x1  y   a. y 1  x  a.x1  a. y 1 a.x  a. y

The complexity of a Boolean expression is specified by the number of literals in the expression  a literal is each occurrence of a variable or its complement. Thus, the left hand side of Example 3.2 has 6 literals while the final right hand side has 4 literals.

3-4

3.4

Logic Gates

These are electronic circuits which are specifically designed (a) to operate on digital signals VH and VL representing the Boolean values 1 and 0, and (b) to carry out the basic logic functions already defined in the context of Boolean algebra. The basic logic gates and their associated logic diagrams are as follows: AND Gate

A B

X = A.B

OR Gate

A B

X = A+B

Inverter

A

X = A'

For reasons to do with the way electronic devices function in a switching mode, the most primitive or fundamental logic circuits are: NAND Gate

A B

a 0 0 1 1

X = (A.B)'

b 0 1 0 1

(a.b)’ 1 1 1 0

From a logic point of view, this gate is equivalent to an AND gate followed by an inverter. However, electronically it contains fewer devices than the AND gate. NOR Gate

A B

a 0 0 1 1

X = (A+B)'

b 0 1 0 1

(a+b)’ 1 0 0 0

Again this is logically equivalent to an OR gate followed by an Inverter but is more simple electronically than the OR gate. For the present, we will stick with the more intuitively accessible AND/OR/Inverter elements. Later, we will demonstrate how to generate equivalent circuits using NAND/NOR elements.

3-5

3.5

The Logic Circuit

Consider the following logic circuit based on AND, OR and Inverter elements:

X

Y F

Z

By following the circuit through from the three inputs X, Y, Z, to the output F, it should be clear that the output can be described by the Boolean equation

F  X .Y .Z  X .Y .Z  X .Y  In effect, the equation is stating:

 X  0 AND Y  0 AND OR  X  0 AND Y  1 AND OR  X  1 AND Y  0

F  1 if

Z  1

Z  1

The statement may also be encapsulated in the following truth table Row 0 1 2 3 4 5 6 7

X 0 0 0 0 1 1 1 1

Y 0 0 1 1 0 0 1 1

Z 0 1 0 1 0 1 0 1

F 0 1 0 1 1 1 0 0

The column marked “Row” is simply used as a means of tagging particular input combinations. Note that the output 1 in row 1 is associated with the X’.Y’.Z term in F, the 1 in row 3 is associated with X’.Y.Z while the 1’s in rows 4 and 5 are associated with X.Y’ It is also worth emphasising that precisely the same information is conveyed by the logic circuit, the Boolean equation, and the truth table. From our knowledge of Boolean algebra, we can manipulate the F expression as follows:

3-6

F

   

X .Y .Z  X .Y .Z  X .Y  X .Z Y   Y   X .Y  X .Z 1  X .Y  X .Z  X .Y 

and this alternative formulation leads to the following logic diagram which is clearly a more simple circuit:

X Z

F

Y

Formally, whereas the original expression for F has a complexity of 8 literals, the alternative has a complexity of 4 literals. 3.6

Complements

Sometimes, rather than implementing a particular Boolean function, we might consider implementing its logical complement. Consider for example the function

F  X .Z  X .Y  We can find the complementary function through repeated application of De morgan’s laws:

 F   X .Z  X .Y     X .Z  .X .Y   X  Z  . XY  X . X   X .Y  X .Z   Y .Z   X .Y  X .Z   Y .Z   X .Y  X .Z  where the last line follows from Example 3.2. We note that in this particular case there is no reduction in complexity. Comparing truth tables for F and F’, we get

3-7

Row 0 1 2 3 4 5 6 7

X 0 0 0 0 1 1 1 1

Y 0 0 1 1 0 0 1 1

Z 0 1 0 1 0 1 0 1

F=X’.Z+X.Y’ 0 1 0 1 1 1 0 0

F’=X.Y+X’.Z’ 1 0 1 0 0 0 1 1

As might be expected, the 1’s and 0’s are interchanged as one goes from F to F’. 3.7

Conclusion

In this lecture, we have defined and set out the basic concepts and theorems of Boolean algebra. We have seen the one-to-one relationship between Boolean algebra and logic circuits composed of AND, OR, and Invert gates. Our next task is to develop further the Boolean formalism.

3-8