Subject Name: Digital Electronics

Subject Code: BSC10020

Unit No. :-2
Topic Name :- Boolean algebra and K-maps

Dr. Sumit Gupta

Department of Computer Science & Applications
1
 Content
 Boolean algebra

 Truth Table and Different Gates

 Boolean laws: Commutative

 Boolean laws: Associative

 Boolean laws: Distributive

 Boolean laws: AND, OR and Inversion laws

 De Morgan’s theorem

 Universal gates

 Simplifications of Logic equations using Boolean algebra rules

 K-map (up to 4 bit). 2

 Boolean Algebra
 Boolean Algebra is an algebra, which deals with binary numbers & binary variables.

 Hence, it is also called as Binary Algebra or logical Algebra. Boolean algebra is mathematics of logic.

 A mathematician, named George Boole had developed this algebra.

 The variables used in this algebra are also called as Boolean variables.

 The range of voltages corresponding to Logic ‘High’ is represented with ‘1’ and the range of voltages
corresponding to logic ‘Low’ is represented with ‘0’.

3
 Boolean Algebra
 A Boolean expression is an expression that produces a Boolean value when evaluated. A Boolean value is either
true or false.

 Variables are the different symbols in a Boolean expression. They may take on the value ‘0’ or ‘1’.

 The complement of a variable is not considered as a separate variable.

 Each occurrence of a variable or its complement is called a literal.

 In above expressions, there are eight and seven literals respectively.

4
 Boolean Algebra
Equivalent and Complement of Boolean Expressions:

 Two given Boolean expressions are said to be equivalent if one of them equals ‘1’ only when the other equals ‘1’
and also one equals ‘0’ only when the other equals ‘0’.

 They are said to be the complement of each other if one expression equals ‘1’ only when the other equals ‘0’, and
vice versa.

 The complement of a given Boolean expression is obtained by complementing each literal, changing all ‘.’ to ‘+’
and all ‘+’ to ‘.’, all 0s to 1s and all 1s to 0s.

Example - Boolean expression Corresponding complement

Boolean expression Corresponding complement

5
 Truth Table
A truth table lists all possible combinations of input binary variables and the corresponding outputs of a logic
system. The logic system output can be found from the logic expression, often referred to as the Boolean expression,
that relates the output with the inputs of that very logic system.
n
It can be generalized to say that, if a logic circuit has n binary inputs, its truth table will have 2 possible input
n
combinations, or in other words 2 rows.

Figure (a) Any logical system with Two input (b) Truth Table for Two Input (A & B) and One Output (Y)
6
 Logic Gate
 The logic gate is the most basic building block of any digital system, including computers.

 Each one of the basic logic gates is a piece of hardware or an electronic circuit that can be used to implement
some basic logic expression.

 All the logic expressions are actually implemented in a digital system with the help of electronic circuits called
logic gates.

 The three basic logic gates are

 The OR gate

 The AND gate

 The NOT gate

7
 Logic Gate
OR Gate :

 An OR gate performs an ORing operation on two or more than two logic variables. The OR operation on two
independent logic variables A and B is written as Y = A+B and reads as Y equals A OR B and not as A plus B.

 The output of an OR gate is LOW only when all of its inputs are LOW.

 For all other possible input combinations, the output is HIGH.

 The operation of a two-input OR gate is explained by the logic expression Y = A+B

8
 Logic Gate
AND Gate:

 An AND gate performs an ANDing operation on two or more than two logic variables. The AND operation on two
independent logic variables A and B is written as Y = A . B and reads as Y equals A AND B and not as A multiplied B.

 The output of an AND gate is HIGH only when all of its inputs are HIGH.

 For all other possible input combinations, the output is LOW.

 The operation of a two-input AND gate is explained by the logic expression Y = A . B

9
 Logic Gate
NOT Gate:

 A NOT gate is a one-input, one-output logic circuit whose output is always the complement of the input.

 a LOW input produces a HIGH output, and vice versa.

 It is also known as a ‘complementing circuit’ or an ‘inverting circuit’.

 The NOT operation on a logic variable X is denoted as

10
 Logic Gate
EXCLUSIVE-OR Gate:

 The EXCLUSIVE-OR gate, commonly written as EX-OR gate, is a two-input, one-output gate.

 The output of an EX-OR gate is a logic ‘1’ when the inputs are unlike and a logic ‘0’ when the inputs are like.

 The output of a two-input EX-OR gate is expressed by

11
 Logic Gate
EXCLUSIVE-NOR Gate:

 EXCLUSIVE-NOR (commonly written as EX-NOR) means NOT of EX-OR. The logic gate that we get by
complementing the output of an EX-OR gate.

 The truth table of an EX-NOR gate is obtained from the truth table of an EX-OR gate by complementing the output
entries.

 The output of a two-input EX-NOR gate is a logic ‘1’ when the inputs are like and a logic ‘0’ when they are unlike.

 The output of a two-input EX-NOR gate is logically expressed as

12
 Logic Gate
NAND Gate:

 NAND stands for NOT AND.

 An AND gate followed by a NOT circuit makes it a NAND gate.

 The truth table of a NAND gate is obtained from the truth table of an AND gate by complementing the output entries.

 The output of a NAND gate is a logic ‘0’ when all its inputs are a logic ‘1’. For all other input combinations, the
output is a logic ‘1’.

 NAND gate operation is logically expressed as

13
 Logic Gate
NOR Gate:

 NOR stands for NOT OR.

 An OR gate followed by a NOT circuit makes it a NOR gate.

 The truth table of a NOR gate is obtained from the truth table of an OR gate by complementing the output entries.

 The output of a NOR gate is a logic ‘1’ when all its inputs are logic ‘0’. For all other input combinations, the output is
a logic ‘0’.

 The output of a two-input NOR gate is logically expressed as

14
 Logic Gate

Universal Gates :

 OR, AND & NOT gates are the three basic logic gates as they together can be used to construct the logic circuit for
any given Boolean expression.

 NOR and NAND gates have the property that they individually can be used to hardware-implement a logic circuit
corresponding to any given Boolean expression.

 It is possible to use either only NAND gates or only NOR gates to implement any Boolean expression.

 It is the reason that NAND and NOR gates are Universal Gates.

15
 Postulates of Boolean Algebra

The following are the important postulates of Boolean algebra:

1. 1.1 = 1 0+0 = 0

2. 1 . 0 = 0 . 1 = 0 0+1 = 1+0 = 1

3. 0 . 0 = 0 1+1 = 1

4.

Many theorems of Boolean algebra are based on these postulates, which can be used to simplify Boolean expressions.

16
 Theorems of Boolean Algebra

Theorem 1

where X is not necessarily a single variable – it could be a term or even a large expression.

Theorem 2

where X could be a variable, a term or even a large expression. According to this theorem, ANDing a Boolean
expression to ‘1’ or ORing ‘0’ to it makes no difference to the expression

Theorem 3 (Identity Laws)

Theorem 4 (Complementation Law)

According to this theorem, in general, any Boolean expression when ANDed to its complement yields a ‘0’ and when
ORed to its complement yields a ‘1’, irrespective of the complexity of the expression

17
 Theorems of Boolean Algebra
Theorem 5 (Commutative Laws)

where X is not necessarily a single variable – it could be a term or even a large expression.
Theorem 5(a) implies that the order in which variables are ADDed or ORed is immaterial. That is, the result of A OR
B is the same as that of B OR A. Theorem 5(b) implies that the order in which variables are ANDed is also
immaterial. The result of A AND B is same as that of B AND A.

Theorem 6 (Associative Laws)

Theorem 6(a) says that, when three variables are being ORed, it is immaterial whether we do this by ORing the result
of the first and second variables with the third variable or by ORing the first variable with the result of ORing of the
second and third variables or even by ORing the second variable with the result of ORing of the first and third
variables. According to theorem 6(b), when three variables are being ANDed, it is immaterial whether you do this by
ANDing the result of ANDing of the first and second variables with the third variable or by ANDing the result of
ANDing of the second and third variables with the first variable or even by ANDing the result of ANDing of the third
and first variables with the second variable.
18
 Theorems of Boolean Algebra
Theorem 7 (Distributive Laws)

Theorem 7(b) proved by students themself.

Proof of Distributive Law

19
 Theorems of Boolean Algebra
Theorem 8 (Absorption Law or Redundancy Law)

The proof of absorption law is straightforward: (a) X+X.Y = X.(1+Y) = X.1 = X

(b) X.X + X.Y =X+X.Y = X.(1+Y) = X.1 = X

Proof that

20
 Theorems of Boolean Algebra
Theorem 9 (Consensus Theorem)

If in a given Boolean expression, we

can identify two terms with one
having a variable and the other
having its complement, then the
term that is formed by the product
of the remaining variables in the two
terms in the case of a sum-of-
products expression or by the sum
of the remaining variables in the
case of a product-of-sums
expression will be redundant.

Student Assignment:
1. Prove consensus theorem
without truth table method?
2. Prove theorem b also.
21
 Theorems of Boolean Algebra
Theorem 10 (DeMorgan’s Theorem)

According to the first theorem the complement of a sum equals the product of complements, while according to the
second theorem the complement of a product equals the sum of complements.

DeMorgan’s theorem can be proved as follows. Let us assume that all variables are in a logic ‘0’ state. In that case

Therefore, LHS = RHS.

22
Simplification Techniques

23
 Simplification Techniques

1. F = ABC + A’ + AB’C  A’+C

2. F = A’BC+AB’C’+A’B’C’+AB’C+ABC  AC+BC+B’C’
3. F = ABC + A(B’+C’) A
4. F = A’(A+B) + (B+AA)(A+B’)  A+B
5. F = C+(BC)’ 1
6. F = AB + A(B+C) + B(C+B) B+AC
7. F = (A+C)(AD+AD’)+AC+C A+C
8. F = AC’+ABC’ AC’
9. F = A’B’C+A’BC’+A’BC+AB’C’+ABC’ A’C+AC’+BC’
10. F = A’BC+AB’C+ABC’+ABC AC+BC+AB
11. F = AB’+(A’+B’+C.C’)’ A
12. F = A(A+B’C)+A(B’+C) A
13. F = (A+B)(A’+P)(B’+P) P(A+B)
14. F = (A+A’B)(A+B) A+B
15. F = (A+B’+CD’)’ A’B(C’+D)
16. F = (X+Y)(X’+Z)(Y+Z) XZ+X’Y+YZ
24
 Simplification Techniques
The primary objective of all simplification procedures is to obtain an expression that has the minimum number of terms.
Obtaining an expression with the minimum number of literals is usually the secondary objective. If there is more than
one possible solution with the same number of terms, the one having the minimum number of literals is the choice.

The techniques are : (a) the K-map (K-map) method (b) the Quine–McCluskey tabular method.

Before we move on to these techniques in detail, it would be relevant to describe

 Sum-of-Products (SOP)

and

 Product-of-Sums (POS)

Boolean expressions.

25
 Simplification Techniques
Sum-of-Products Boolean Expressions :

A sum-of-products expression contains the sum of different terms, with each term being either a single literal or a
product of more than one literal. It can be obtained from the truth table directly by considering those input combinations
that produce a logic ‘1’ at the output. Each such input combination produces a term. Different terms are given by the
product of the corresponding literals. The sum of all terms gives the expression.

26
 Simplification Techniques
Product-of-Sums Expressions :

A product-of-sums expression contains the product of different terms, with each term being either a single literal or a
sum of more than one literal. It can be obtained from the truth table by considering those input combinations that
produce a logic ‘0’ at the output. Each such input combination gives a term, and the product of all such terms gives the
expression. Different terms are obtained by taking the sum of the corresponding literals. Here, ‘0’ and ‘1’ respectively
mean the uncomplemented and complemented variables, unlike sum-of-products expressions where ‘0’ and ‘1’
respectively mean complemented and uncomplemented variables.

Y = 27
 Simplification Techniques
A given sum-of-products expression can be transformed into an equivalent product-of-sums expression by (a) taking the
dual of the given expression, (b) multiplying out different terms to get the sum-of-products form, (c) removing
redundancy and (d) taking a dual to get the equivalent product-of-sums expression.

Transforming the given product-of-sums expression into an equivalent sum-of-products expression is a straightforward
process.

28
 Simplification Techniques
Canonical Form of Boolean Expressions :

An expanded form of Boolean expression, where each term contains all Boolean variables in their true or
complemented form, is also known as the canonical form of the expression.

This expression is a Boolean function of three variables expressed in canonical form. This function after simplification
reduces to A’.B’+A.B.C after losing its canonical form.
Y(A,B,C, D) = A+C

Σ and Π Nomenclature : Σ and Π notations are respectively used to represent sum-of-products and product-of-sums
Boolean expressions.

29
 Simplification Techniques
Σ Nomenclature : Let us consider the following Boolean function: f (A,B,C,D) = AB’C’+ABCD+A’BC’D+A’B’C’D
The first step is to write the expanded sum-of-products given by

Different terms are then arranged in ascending order of the binary numbers represented by various terms, with true
variables representing a ‘1’ and a complemented variable representing a ‘0’. The expression becomes

The different terms represent 0001, 0101, 1000, 1001 and 1111. The decimal equivalent of these terms enclosed in the Σ
then gives the Σ notation for the given Boolean function i.e. f (A,B,C,D) = Σ (1,5,8,9,15)

The complement of f (A,B,C,D) is f’(A,B,C,D) i.e. f’(A,B,C,D) = Π (0,2,3,4,6,7,10,11,12,13,14)

30
 Simplification Techniques
Π Nomenclature : Let us consider the following Boolean function: f (A,B,C,D) =
(B+C’+D’).(A’+B’+C+D).(A+B’+C’+D’)
The first step is to write the expanded product-of-sums form and is given by

The binary numbers represented by the different sum terms are 0011, 1011, 1100 and 0111 (true and complemented
variables here represent 0 and 1 respectively). When arranged in ascending order, these numbers are 0011, 0111, 1011
and 1100. Therefore,
Σ

31
 Simplification Techniques
K-map Method : A K-map is a graphical representation of the logic system. It can be drawn directly from either
minterm (sum-of-products) or maxterm (product-of-sums) Boolean expressions. Drawing a K-map from the truth table
involves an additional step of writing the minterm or maxterm expression depending upon whether it is desired to have
a minimized sum-of-products or a minimized product-of-sums expression.
n
Construction of a K-map : An n-variable K-map has 2 squares, and each possible input is allotted a square. In the
case of a minterm K-map, ‘1’ is placed in all those squares for which the output is ‘1’, and ‘0’ is placed in all those
squares for which the output is ‘0’. 0s are omitted for simplicity. An ‘X’ is placed in squares corresponding to ‘don’t
care’ conditions.

In the case of a maxterm K-map, a ‘1’ is placed in all those squares for which the output is ‘0’, and a ‘0’ is placed for
input entries corresponding to a ‘1’ output. Again, 0s are omitted for simplicity, and an ‘X’ is placed in squares
corresponding to ‘don’t care’ conditions.

The only condition to be satisfied is that the designation of adjacent rows and adjacent columns should be the same
except for one of the literals being complemented.

Also, the extreme rows and extreme columns are considered adjacent.
32
 Simplification Techniques
Having drawn the Karnaugh map, the next step is to form groups of 1s as per the following guidelines:

 Each square containing a ‘1’ must be considered at least once, although it can be considered as often as desired.

 The objective should be to account for all the marked squares in the minimum number of groups.

 The number of squares in a group must always be a power of 2, i.e. groups can have 1, 2, 4, 8, 16, ….squares.

 Each group should be as large as possible, which means that a square should not be accounted for by itself if it can
be accounted for by a group of two squares; a group of two squares should not be made if the involved squares can
be included in a group of four squares and so on.

 ‘Don’t care’ entries can be used in accounting for all of 1-squares to make optimum groups. They are marked ‘X’ in
the corresponding squares. It is, however, not necessary to account for all ‘don’t care’ entries. Only such entries that
can be used to advantage should be used.

33
Simplification Techniques

34
Simplification Techniques

35
Simplification Techniques

36
 Simplification Techniques
Minimize the Boolean function

using the mapping method in both minimized sum-of-products and product-of-sums forms.

37
 Simplification Techniques
Minimize the Boolean function

using the mapping method in both minimized sum-of-products and product-of-sums forms.

SOP

POS

38
 Simplification Techniques

Simplify the following expression using K-Map

1. F = Σ(1, 2, 3, 5, 7, 11, 13) A’D + A’B’C + BC’D + B’CD

2. F = A’BD+ ABC + d(ABC’D’, ABC’D) AB + BD
3. F = Σ(2, 6, 12, 13, 14, 15) AB + A’CD’
4. F = Σ(1, 3, 6, 7) A’C + AB Most Important
5. F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15) QS+Q’S’
6. F(A,B,C) = Σ(0, 1, 3, 5) + d(2, 7) A’+C
7. F = A’BC’+AB’C’+ABC+A’B’C’ B’C’+A’C’+ABC
8. F = A’B’C+ABC’+A’B’C’+AB’C+ABC AB+A’B’C’+B’C

39