Digital Electronics

(CSE 2105)

Cox’s Bazar International University

(CBIU)
1
Boolean Algebra

2
2
 Boolean Algebra

1854: Logical algebra was published by George

Boole  known today as “Boolean Algebra”
It’s a convenient way and systematic way of
expressing and analyzing the operation of logic
circuits.
1938: Claude Shannon was the first to apply
Boole’s work to the analysis and design of logic
circuits.

Boolean Algebra 3
3
 Boolean Operations & Expressions

Variable – a symbol used to represent a logical

quantity.

Complement – the inverse of a variable and is

indicated by a bar over the variable.

Literal – a variable or the complement of a

variable.

Boolean Algebra 4
4
 Boolean Addition
Boolean addition is equivalent to the OR operation
0+0 = 0 0+1 = 1 1+0 = 1 1+1 = 1

A sum term is produced by an OR operation with no

AND ops involved.
i.e. A  B, A  B , A  B  C , A  B  C  D
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.

Boolean Algebra 5
5
 Boolean Multiplication
Boolean multiplication is equivalent to the AND
operation
0·0 = 0 0·1 = 0 1·0 = 0 1 ·1 = 1

A product term is produced by an AND operation with

no OR ops involved.
i.e. AB, AB , ABC , A BCD
A product term is equal to 1 only if each of the literals in the
term is 1.
A product term is equal to 0 when one or more of the literals
are 0.

Boolean Algebra 6
6
 Laws & Rules of Boolean Algebra
The basic laws of Boolean algebra:
The commutative laws
The associative laws
The distributive laws

Boolean Algebra 7
7
 Commutative Laws

The commutative law of addition for two

variables is written as: A+B = B+A
A
B
A+B  B
A
B+A

The commutative law of multiplication for two

variables is written as: AB = BA
A
B
AB  B
A
B+A

Boolean Algebra 8
8
 Associative Laws

The associative law of addition for 3 variables is

written as: A+(B+C) = (A+B)+C


A A A+B
A+(B+C)
B B
(A+B)+C
C B+C C

The associative law of multiplication for 3

variables is written as: A(BC) = (AB)C

A A AB
A(BC)
B B
(AB)C
C BC C

Boolean Algebra 9
9
 Distributive Laws

The distributive law is written for 3 variables as

follows: A(B+C) = AB + AC

B A AB
B+C


C B
X
X
A A
C AC

X=A(B+C) X=AB+AC

Boolean Algebra 10
10
 Rules of Boolean Algebra

1. A  0  A 7. A  A  A
2. A  1  1 8. A  A  0
3. A  0  0 9. A  A
4. A  1  A 10. A  AB  A
5. A  A  A 11. A  A B  A  B
6. A  A  1 12.( A  B)( A  C )  A  BC
___________________________________________________________
A, B, and C can represent a single variable or a combination of variables.

Boolean Algebra 11
11
DeMorgan’s
Theorems

12
12
 DeMorgan’s Theorems
DeMorgan’s theorems provide mathematical
verification of:

• the equivalency of the NAND and negative-OR

gates
• the equivalency of the NOR and negative-AND
gates.

DeMorgan’s Theorems 13
13
 DeMorgan’s Theorems

The complement of two or NAND Negative-OR

more ANDed variables is
equivalent to the OR of the
complements of the individual X Y  X  Y
variables.

The complement of two or NOR

more ORed variables is Negative-AND
equivalent to the AND of the
complements of the individual X  Y  X Y
variables.

DeMorgan’s Theorems 14
14
 DeMorgan’s Theorems (Exercises)

Apply DeMorgan’s theorems to the expressions:

X Y  Z
X Y  Z
X Y  Z
W  X Y  Z

DeMorgan’s Theorems 15
15
 DeMorgan’s Theorems (Exercises)

Apply DeMorgan’s theorems to the expressions:

( A  B  C)D
ABC  DEF
AB  C D  EF
A  BC  D( E  F )

DeMorgan’s Theorems 16
16
Boolean Analysis of
Logic Circuits

17
17
 Boolean Analysis of Logic Circuits

Boolean algebra provides a concise way to

express the operation of a logic circuit formed
by a combination of logic gates
so that the output can be determined for various
combinations of input values.

Boolean Analysis of Logic Circuits 18

18
 Boolean Expression for a Logic Circuit

To derive the Boolean expression for a given

logic circuit, begin at the left-most inputs and
work toward the final output, writing the
expression for each gate.
C CD
D
B+CD
B

A(B+CD)
A

Boolean Analysis of Logic Circuits 19

19
 Constructing a Truth Table for a Logic Circuit

Once the Boolean expression for a given logic

circuit has been determined, a truth table that
shows the output for all possible values of the
input variables can be developed.
Let’s take the previous circuit as the example:
A(B+CD)
There are four variables, hence 16 (24) combinations
of values are possible.

Boolean Analysis of Logic Circuits 20

20
 Constructing a Truth Table for a Logic Circuit

Evaluating the expression

To evaluate the expression A(B+CD), first find the
values of the variables that make the expression
equal to 1 (using the rules for Boolean add & mult).
In this case, the expression equals 1 only if A=1 and
B+CD=1 because
A(B+CD) = 1·1 = 1

Boolean Analysis of Logic Circuits 21

21
 Constructing a Truth Table for a Logic Circuit

Evaluating the expression (cont’)

Now, determine when B+CD term equals 1.
The term B+CD=1 if either B=1 or CD=1 or if both B
and CD equal 1 because
B+CD = 1+0 = 1
B+CD = 0+1 = 1
B+CD = 1+1 = 1
The term CD=1 only if C=1 and D=1

Boolean Analysis of Logic Circuits 22

22
 Constructing a Truth Table for a Logic Circuit

Evaluating the expression (cont’)

Summary:
A(B+CD)=1
When A=1 and B=1 regardless of the values of C and D
When A=1 and C=1 and D=1 regardless of the value of B
The expression A(B+CD)=0 for all other value
combinations of the variables.

Boolean Analysis of Logic Circuits 23

23
 Constructing a Truth Table for a Logic Circuit

Putting the results in truth

INPUTS OUTPUT
table format A B C D A(B+CD)
0 0 0 0 0
0 0 0 1 0

A(B+CD)=1 0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
When A=1 and 0 1 0 1 0
B=1 regardless 0 1 1 0 0

of the values 0 1 1 1 0
1 0 0 0 0
of C and D 1 0 0 1 0
When A=1 and C=1 1 0 1 0 0

and D=1 regardless of 1 0 1 1 1

1 1 0 0 1
the value of B 1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Boolean Analysis of Logic Circuits 24
24
 Constructing a Truth Table for a Logic Circuit(Excercises)

•A combinational circuit has 3 inputs A, B, C and output F. F is true for

following input combinations
A is False, B is True
A is False, C is True
A, B, C are False
A, B, C are True
(i) Write the Truth table for F. Use the convention True=1 and False = 0.
(ii) Write the simplified expression for F in Sum-of-Products (SOP) form.
(iii) Write the simplified expression for F in Product-of-Sum (POS) form.
(iv) Draw logic circuit using minimum number of 2-input NAND gates.

Boolean Analysis of Logic Circuits 25

25
Questions?

Thank You!

26
26