Chapter 4 Boolean Algebra and Logic Simplification

Boolean Algebra and Logic Simplification

======================================
 Boolean algebra is the mathematics of digital systems

Boolean Operations and Expressions:

 Variable:
- Is a symbol that represent logical quantity
- It can have 0 or 1 value
- a variables is represented as upper case letter
 Complement:
- Is the inverse of a variable
- Complement of a variable is indicated by a bar over the variable
- The complement of a variable A is read “not A” or “A bar”
 A literal: is a variable or the complement of a variable
 Boolean Addition:
- Boolean addition is equivalent to OR operation

- Sum Term:
o In Boolean algebra a sum term is a sum of literals
o In logic circuits a sum term is implemented as OR gate
- A sum term is equal to 1 when one or more of its literal are 1
- A sum term is equal to 0 if all of its literals ar 0

___________________________________________________________________________

Example 4.1:

Determine the values of A, B, C, and D that make the sum term +C+ equal to 0.

Solution

For the sum term to be 0, each of the literals in the term must be 0. Therefore, A = 0, B = 1
so that = 0, C = 0, and D = 1 so that = 0.

A+ +C+ =0+ +0+ =0+0+0+0=0

1
Chapter 4 Boolean Algebra and Logic Simplification

___________________________________________________________________________

 Boolean Multiplication:
- Boolean multiplication is equivalent to AND operation

- Product Term:
o In Boolean algebra a product term is a product of literals
o In logic circuits a product term is implemented as AND gate
- A product term is equal to 0 if one or more of its literals are 0
- A product term is equal to 1 if all of its terms are 1

___________________________________________________________________________

Example 4.2:

Determine the values of A, B, C, and D that make the product term A C equal to 1.

For the term to be 1, each of the literals in the term must be 1. Therefore, A = 1, B = 0 so
that = 1, C = 1, and D = 0 so that =1.

A C =1∙ ∙1∙ =1∙1∙1∙1=1

___________________________________________________________________________

Laws of Boolean Algebra:

 Commutative Laws:
-

 Associative Laws:

2
Chapter 4 Boolean Algebra and Logic Simplification

- ( ) ( )

- ( ) ( )

 Distributive Law:
( )

Rules of Boolean Algebra:

 These rules are very useful for expression simplification
 The following rules apply to single variable and combination of variables as well

 Rule 1:

3
Chapter 4 Boolean Algebra and Logic Simplification

 Rule 2:

 Rule 3:

 Rule 4:

 Rule 5:

 Rule 6:

 Rule 7:

 Rule 8:

 Rule 9:

 Rule 10:

4
Chapter 4 Boolean Algebra and Logic Simplification

 Rule 11:

 Rule 12: ( )( ) ( )

5
Chapter 4 Boolean Algebra and Logic Simplification

Demorgan’s Theorims:
 Demorgan’s First Theorem:
The complement of a product of variables is equal to the sum of complements of
variables

 Demorgan’s Second Theorem:

the complement of a sum of variables is equal to the product of the complements of
the variables

6
Chapter 4 Boolean Algebra and Logic Simplification

 Demorgan’s law apply also to expressions in which there are more than one variable

___________________________________________________________________________

Example 4.3:

Apply Demrgan’s law to each of the following:

(a) ( ) (b) (c)

Solution

(a) Let A + B + C = X and D = Y. The expression ( ) is of the form

and can be rewritten as
( ) =
Next, apply DeMorgan’s theorem to the term

(b) Let ABC = X and DEF = Y. The expression is of the form and
can be rewritten as
=( )( )
Next, apply DeMorgan’s theorem to each of the terms and
( )( )=( )( )
(c) Let A = X. D = Y. and EF = Z The expression is of the form
= And can be rewritten as
=( )( )( )
Next, apply DeMorgan’s theorem to each of the terms , ,and
( )( )( ) = ( + B)( C + )( + )

_______________________________________________________________________

Boolean Analysis of Logic Circuits:

7
Chapter 4 Boolean Algebra and Logic Simplification

 Writing a Boolean expression for a logic circuit:

o First we start from the left most gate and write its Boolean expression
o Then we move further to the next level of gates and use the output from the
previous level as input to the current level and we write its Boolean expression
o We continue like this till we reach the output level gate

 Constructing a truth table for a logic circuit:

o First list all the inputs in the table
o Then we list down all input combinations using binary counting
o Starting from the inner most term in the Boolean expression and moving
outward; we evaluate the value of each term for its input combinations putting
each term in its own column in the table

A B C D CD B+CD A(B+CD)

0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 0
0 1 0 0 0 1 0
0 1 0 1 0 1 0
0 1 1 0 0 1 0
0 1 1 1 1 1 0
1 0 0 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 0 0 0
1 0 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 1 0 1 1
1 1 1 0 0 1 1
1 1 1 1 1 1 1

Simplification Using Boolean Algebra:

8
Chapter 4 Boolean Algebra and Logic Simplification

 From engineering and economic point of view it is desirable to implement a given

design with a minimal number of gates and wiring
 Using the law and rules of Boolean algebra in addition demorgan’s law; we can
simplify a given Boolean expression to more compact form

___________________________________________________________________________

Example 4.4:

Using Boolean algebra techniques, simplify this expression:

AB + A(B + C) + B(B + C)

Solution

The following is not necessarily the only approach.

Step1: Apply the distributive law to the second and third terms in the expression, as follows:

AB +AB + AC+ BB + BC

Step2: Apply rule 7 (BB = B) to the fourth term.

AB + AB + AC + B + BC

Step3: Apply rule 5 (AB + AB = AB) to the first two terms.

AB + AC + B + BC

Step4: Apply rule 10 (B + BC = B) to the last two terms.

AB + AC + B

Step5: Apply rule 10 (AB + B = B) to the first and third terms.

B + AC

___________________________________________________________________________

Example 4.5:

9
Chapter 4 Boolean Algebra and Logic Simplification

Simplify the following Boolean expression:

[A ( ) ]C

Note that brackets and parentheses mean the same thing: the term inside is multiplied
(ANDed) with the term outside.

Solution

Step1: Apply the distributive law to the terms within the brackets.

(A C + A )C

Step2: Apply rule 8 ( ) to the second term within the parentheses.

(A )C

Step3: Apply rule 3 (A ∙ 0 ∙ D = 0) to the second term within the parentheses.

(A C + 0 + )C

Step4: Apply rule1 (drop the 0) within the parentheses.

(A C + )C

Step5: Apply the distributive law.

A CC +

Step6: Apply rule 7 (CC = C) to the first term.

A C+ C

Step7: Factor out

( )

Step8: Apply rule 6 (A + = 1).

Step9: Apply rule 4 (drop the 1).

10
Chapter 4 Boolean Algebra and Logic Simplification

___________________________________________________________________________

Example 4.6:

Simplify the following Boolean expression:

Solution

Step1: Apply DeMorgan’s theorem to the first term.

( )( )+

Step2: Apply DeMorgan’s theorem to each term in parentheses.

( )( )+

Step3: Apply the distributive law to the two terms in parentheses.

Step4: Apply rule 7 ( = ) to the first term, and rule 10

[ ( ) ] to the third and last terms.

Step5: Apply rule 10 [ ( ) ] to the first and second terms.

Step6: Apply rule 10 [ ( ) ] to the first and second terms.

___________________________________________________________________________

11