Scribd
Upload
58 views4 pages

DLLec5b Notes

The document discusses designing logic circuits using Boolean algebra. It covers topics like: - Representing Boolean functions as algebraic expressions or truth tables - Minimizing Boolean expressions using algebraic rules and identities - Converting logic functions to canonical Sum of Products (SOP) or Product of Sums (POS) form - Defining minterms and maxterms to represent all variable combinations in SOP and POS expressions - Obtaining canonical SOP and POS expressions directly from truth tables

Uploaded by

Chintan Mandal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
58 views4 pages

DLLec5b Notes

The document discusses designing logic circuits using Boolean algebra. It covers topics like: - Representing Boolean functions as algebraic expressions or truth tables - Minimizing Boolean expressions using algebraic rules and identities - Converting logic functions to canonical Sum of Products (SOP) or Product of Sums (POS) form - Defining minterms and maxterms to represent all variable combinations in SOP and POS expressions - Obtaining canonical SOP and POS expressions directly from truth tables

Uploaded by

Chintan Mandal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Lecture 5b

Digital Logic - Designing Logic Circuits


Chintan Kr Mandal

1 Boolean Algebra for Digital Circuits [2]


• The Boolean algebra which we will discuss deals with binary variables and logic operations
• The variables are designated by letters of the alphabet and the three basic logic operations of AND, OR and NOT
(negation/complementation).
• A Boolean function consists of binary variables denoting the function, an equals sign(=), and an algebraic expression
formed by using binary variables, the constants(0 and 1), the logic operation sysmbols and parenthesis.
• The parts of an expression are called terms.
• Each term consists of the variables, either in complemented or uncomplemented form, which are referred to as literals.
• A Boolean function can be represented in a truth table and as an algebraic expression.

2 Minimization of Boolean Expresssions using Algebraic Methods [1]


By manipulating a Boolean expression according to Boolean algebraic rules, it is often possible to obtain a simpler expression
for the same function.
E.g. consider the Boolean function
F (X, Y, Z) = X + Y Z
.
The two parts of the expression, X and Y Z are called terms of the function F (X, Y, Z).
X, Y and Z are the literals of the terms.

2.1 Basic Identities of Boolean Algebra

Property Dual Property Name of Prop-


erty/Law/Theorem
1. A+0=A A.1 = A
2. A+1=1 A.0 = 0
3. A+A=A A.A = A
4. A+A=1 A.A = 0
5. A=A A=A
6. A+B=B+A A.B = B.A Commutative
Property
7. A + (B + C) = (A + A.(B.C) = (A.B).C Associative Prop-
B) + C erty
8. A + BC = (A + A.(B + C) = A.B + Distributive Prop-
B)(A + C) A.C erty
9. (i) A + AB = A (i) A.(A + B) = A Absoption Law
(ii) A+AB = A+B (ii)
10. AB + AC + BC = (A + B)(A + C)(B + Consensus Prop-
AB + AC C) = (A+B)(A+C) erty
11. AB + AB = A (A + B)(A + B) = A Combining Theo-
rem
12. A + B = A.B A.B = A + B De’Morgan’s Theo-
rem

1
1. R.T.P.: AB + BC + BC = AB + C
2. Simplify: AB + AB + ABC(AB + C)

3. Simplify: (AB + C)(A + B + C)


4. Simplify: AB + ABD + ABCD + BC

5. R.T.P.: AC(ABD) + ABCD + ABC = BC + AD(B + C)

Answer !!! Answers to the Brainstorming !!


2. 1
3. (A + B + C)(A + B + C)
4. B(A + AD) + C(B + BAD)
= B(A + D) + C(B + AD) . . . [A + AB = A + B]
= AB + BD + BC + ACD)
= AB + BD + (A + A)BC + ACD)
= AB + BD + ABC + ABC + ACD)
= AB(1 + C) + BD + ABC + ACD)
= AB + BD + ABC + ACD)
= AB + BD + ACB + ACD)
= AB + BD + ACD) . . . [∵ AB + BC + AC = AB + BC]
5. BC + AD(B + C)

3 Expressions
The Logic functions can be expressed in the following forms:
• Sum of Products (S.O.P.)
AB + BC + AC

• Product of Sums (P.O.S.)


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

3.1 Minterms
A product term containing all the k variables of the function in either complemented or uncomplemented form is called a
Minterm
Minterm No. A B C Minterm Value
m0 0 0 0 ABC
m1 0 0 1 ABC
.. .. .. .. ..
. . . . .
m7 1 1 1 ABC

A variable appears either in uncomplemented form if it will have value 1 else in complemented form if it contains the
value of 0.

3.2 Canonical Sum of Product(SOP) Expresssion


Canonical Sum of Product Expresssion is defined as the logical sum of all the minterms derived from the rows of a truth
table, for which the value of the function is 1.
A Canonical Sum of Product Expresssion is represented as
X
Y (A, B, C) = (0, 5, 6)
m

where the truth function Y (A, B, C) for ABC, ABC, ABC is 1.

2
3.3 Conversion of Logic function to Canonical SOP
Check for variables that are missing in each product which is not a Minterm.
Multiply the product by (X + X) for each variable X that is missing.
E.g. Y = A + BC
= A(B + B)(C + C) + (A + A)BC

3.4 Maxterm
A sum term containing all the k variables of the function in either complemented or uncomplemented form is called a
Maxterm
Minterm No. A B C Minterm Value
M0 0 0 0 A+B+C
M1 0 0 1 A+B+C
.. .. .. .. ..
. . . . .
M7 1 1 1 A+B+C

A variable appears either in uncomplemented form if it will have value 0 else in complemented form if it contains the
value of 1.

3.5 Conversion of Logic function to Canonical Product Of Sums(POS)


Check for variables that are missing in each sum which is not a Maxterm.
Add to the sum (X.X) for each variable X that is missing.
E.g. Y = (A + B)(B + C)(A + C)
= (A + B + 0)(0 + B + C)(A + 0 + C)
= (A + B + C.C)(A.A + B + C)(A + B.B + C)
= (A + B + C)(A + B + C) . . .

3.6 Canonical POS and SOP from Truth Table


A B C Y Product Sum
0 0 0 0 - (A + B + C)
0 0 1 0 - (A + B + C)
0 1 0 1 ABC -
0 1 1 1 ABC -
1 0 0 0 - (A + B + C)
1 0 1 1 ABC -
1 1 0 0 - (A + B + C)
1 1 1 1 ABC -

S.O.P. ABC + ABC + ABC + ABC


P.O.S. (A + B + C)(A + B + C)(A + B + C)(A + B + C)

• The POS can be obtained from its SOP by Y = Y


P
E.g. Y (A, B, C) = m (2, 3, 5, 7)

Note The complement Y can be obtained by the OR operation of the maxterms which are not available in Y .

P
∴ Y = m (0, 1, 4, 6)
= ABC + ABC + ABC + ABC
∴ Y = (A + B + C)(A + B + C)(A + B + C)(A + B + C)

References

3
References
[1] Z. Kohavi and N.K. Jha. Switching and Finite Automata Theory. Cambridge University Press, 2010.
[2] Morris M. Mano. Digital Design. Pearson Education Inc., 2003.

You might also like