Unit 20 - Lecture 03

DIGITAL PRINCIPLES
Lecture 3
Boolean Algebra, De Morgan's theorem
Boolean Algebra
Mathematics of Digital Systems
• Variables – Symbols use to represent logical quantities. Can have the values 0 or 1
• Complement – Inverse of a variable

A=1 ഥ=0
A
A=0 ഥ=1
A
• Literal – Variable / Complement of a variable
ഥ , C, B
eg: A, B, A ഥ
Boolean Addition
• Operation of which logic gate is equivalent to this?
• SUM term – Sum of literals
ഥ , A + B + Cത ,
Eg: A+B , A+B ഥ+B+C+D
A ഥ
ഥ+C+D
Determine the values of A, B, C and D that make the sum term A + B ഥ=0
Boolean Multiplication
• Operation of which logic gate is equivalent to this?
• PRODUCT term – Product of literals
ഥ , ABCത ,
Eg: AB , AB ഥ D
ABC ഥ
ഥ CD
Determine the values of A, B, C and D that make the sum term AB ഥ=1
A=
B=
C=
D=
Boolean Addition Boolean Multiplication
• Equivalent to OR operation • Equivalent to AND operation
• 0+0 = 0 • 0.0 = 0
• 0+1 = 1 • 0.1 = 0
• 1+0 = 1 • 1.0 = 0
• 1+1 = 1 • 1.1 = 1
Laws & Rules of Boolean Algebra
Laws :
1. Commutative Law
2. Associative Law
3. Distributive Law
Commutative Laws Associative Laws Distributive Laws
Addition A+B = B+A A+(B+C) = (A+B) +C A(B+C) = AB + AC
Multiplication AB = BA A(BC) = (AB)C

Commutative Law
Associative Law
Distributive Law
Rules of Boolean Algebra
1. A + 0 =A 7. A . A = A
2. A + 1 = 1 ഥ=0
8. A . A
3. A . 0 = 0 ഥ =A
9. A
4. A . 1 = A 10. A + AB =A
5. A + A =A ഥB=A+B
11. A + A
ഥ =1
6. A + A 12. (A+B)(A+C) = A + BC
Construct the truth tables & verify the rules 10, 11 & 12
A B C A+B A+C (A+B)(A+C) A+BC
10. A + AB =A 0 0 0
ഥB=A+B 0 0 1
11. A + A
0 1 0
12. (A+B)(A+C) = A + BC 0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
De Morgan’s Theorems
1. The Complement of a product of variables is equal to the sum of the complements of
the variables.
The complement of ANDed variables is equal to the OR of the complements of individual
variables.
XY=ഥ
X +ഥ
Y
2. The Complement of a sum of variables is equal to the product of the
complements of the variables.
The complement of 2 or more ORed variables is equivalent to the AND of the complements
of individual variables.
X + Y = ഥX. Y
ഥ
Example:
ഥ B(C + D
Apply De Morgan’s theorem to the expression A ഥ) + E
ഥB C + D
A ഥ +E Apply theorem 2
ഥ
= AB(C ഥ) . E
+D ഥ Apply theorem 1
ഥ + C+D
= ( AB ഥ ). E
ഥ Apply theorem 1 & theorem 2
ഥ+B
= (( A ഥ))E
ഥ ) +( Cത . D ഥ
ത 𝐄ത
ഥ + 𝐂D)
=(A+𝐁
1.AB+ A(B+C) + B(B+C)
ഥ + A.(B + C) + B.(B + C)
2.AB
For the above mentioned expressions,

a. Draw the logic circuit.
b. Simplify the expression.
c. Draw the logic circuit for the simplified expression
Simplify the following Boolean expressions
1.[AB ഥB
ഥ(C+BD) + A. ഥ]C
2.[AB(C+BD) + AB]CD
Standard forms of Boolean Expressions
1. SOP – Sum of Products
2. POS – Product of Sums
The Sum of Products (SOP)
▪ Two or more Product terms are summed with Boolean Addition.
▪ Can be expressed with 1 OR gate & 2 or more AND gates.
ഥC + ABCത + A
ABC + AB ഥ BC
A B C
0 0 0 A’B’C’
0 0 1 A’B’C
0 1 0 A’BC’
0 1 1 A’BC
1 0 0 AB’C’
1 0 1 AB’C
1 1 0 ABC’
1 1 1 ABC
Standard SOP form : All the variables in the domain appear in each product
term.
Converting Product Terms to Standard SOP form

Multiply each nonstandard product term by a term made up of sum of the
missing variable & its complement.
ഥ
Eg: ABC + AB ഥ(C+ Cത ) = AB
ഥ = AB
[ AB ഥCത ]
ഥ C + AB
ഥCത
ഥ C + AB
= ABC + AB
The Product of Sums (POS)
▪ Two or more Sum terms are multiplied.

▪ Can be expressed with 1 AND gate & 2 or more OR gates.
(A+B+C ).(A+Bഥ+C).(A+B+Cത ).(A
ഥ +B+C)
Standard POS form : All the variables in the domain appear in each sum term.
Converting Sum Terms to Standard POS form

Add to each nonstandard sum term, a term made up of product of the
missing variable & its complement.
ഥ )
Eg: (A+B+C) .( A+B ഥ)+(CCത ) = (A+B
ഥ) = (A+B
(A+B ഥ + Cത )
ഥ+C). (A+B
ഥ + Cത )
ഥ+C). (A+B
=(A+B+C).(A+B
Converting Standard SOP to Standard POS form
Step 1: Evaluate each product term in the SOP expression. Determine the binary numbers
that represent the product terms.
Step 2: Determine all of the binary numbers not included in evaluation in step 1.
Step 3: Write the equivalent sum term for each binary number from step 2 & express in POS
form.
A B C
Eg: 0 0 0 A’B’C’
ഥB
SOP Expression → A ഥCത + ABC + AB
ഥC + ABCത + ABC
ഥ 0 0 1 A’B’C
0 1 0 A’BC’
Relevant Binary numbers → 000 111 101 110 011
0 1 1 A’BC
Other 3 binary numbers → 010 100 001 1 0 0 AB’C’
POS expression → (A + B’ + C).(A’ + B + C).(A + B + C’ ) 1 0 1 AB’C
1 1 0 ABC’
ഥB
A ഥCത + ABC + AB
ഥC + ABCത + A
ഥBC ≡ (A + B’ + C).(A’ + B + C).(A + B + C’ )
1 1 1 ABC
Express the following in SOP form & then convert into standard SOP form.
ഥ BCത + (A+B
A ഥ)(B+Cത +AB
ഥ)
Convert to standard POS form
(A+B’) (B+C)
(A+B’+C) (B’+ C+ D)(A+B’+C’+D)

Develop the truth table for standard SOP expression,
A’B’C + AB’C’ + ABC = 1
Determine the truth table for standard POS expression,
(A+B+C).(A+B’+C).(A+B’+C’).(A’+B+C’).(A’+B’+C)
A B C Y Write down the SOP & POS expressions
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
Thank You!

Unit 20 - Lecture 03

Uploaded by

Copyright:

Available Formats

Unit 20 - Lecture 03

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 20 - Lecture 03

Uploaded by

Copyright:

Available Formats

DIGITAL PRINCIPLES

• Complement – Inverse of a variable

• Literal – Variable / Complement of a variable

• SUM term – Sum of literals

• PRODUCT term – Product of literals

Commutative Laws Associative Laws Distributive Laws

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

Multiplication AB = BA A(BC) = (AB)C

For the above mentioned expressions,

Converting Product Terms to Standard SOP form

▪ Two or more Sum terms are multiplied.

Converting Sum Terms to Standard POS form

(A+B’+C) (B’+ C+ D)(A+B’+C’+D)

You might also like