ADVERTISEMENT
ADVERTISEMENT

Home » Digital Electronics

Duality Principle and Rules for Reduction of Boolean Expressions

Here, we are going to learn about the duality principle and rules for reduction of Boolean expressions.
Submitted by Saurabh Gupta, on November 14, 2019

Duality Principle

According to this principle, if we have postulates or theorems of Boolean Algebra for one type of operation then that operation can be converted into another type of operation (i.e., AND can be converted to OR and vice-versa) just by interchanging '0 with 1', '1 with 0', '(+) sign with (.) sign' and '(.) sign with (+) sign'. This principle ensures if a theorem is proved using postulates of Boolean algebra, then the dual of this theorem automatically holds and we need not prove it again separately.

Some Boolean expressions and their corresponding duals are given below,

Given Expression Dual Given Expression Dual
0 = 1 1 = 0 A. (A+B) = A A + A.B = A
0.1 = 0 1 + 0 = 1 AB = A + B A+B = A.B
A.0 = 0 A + 1 = 1 (A+C) (A +B) = AB + AC AC + AB = (A+B). (A+C)
A.B = B. A A + B = B + A A+B = AB + AB +AB AB = (A+B).(A+B).(A+B)
A.A = 0 A + A = 1 AB + A + AB = 0 ((A+B)).A.(A+B) = 1
A. (B.C) = (A.B). C A+(B+C) = (A+B) + C

Reducing Boolean Expressions

Every Boolean expression must be reduced to its simplest form before realizing it because each logic operation in the expression is carried out using hardware. Thus, realizing the simplest expression requires less circuitry hence reduces the cost of the system. Also, it is highly reliable and less complex in nature. For reducing the Boolean expression, we use the axioms and laws of Boolean algebra (see them in our previous article). Some instructions for reducing the given Boolean expression are listed below,

  1. Remove all the parenthesis by multiplying all the terms if present.
  2. Group all similar terms which are more than one, then remove all other terms by just keeping one.
    Example: ABC + AB +ABC + AB = ABC +ABC + AB +AB = ABC +AB
  3. A variable and its negation together in the same term always results in a 0 value, it can be dropped.
    Example: A. BCC + BC = A. 0 + BC = BC
  4. Look for the pair of terms that are identical except for one variable which may be missing in one of the terms. The larger term can be dropped.
    Example: ABCD + ABC = ABC(D + 1) = (ABC).1 = ABC
  5. Look for the pair of terms that have the same variables, with one or more variables complimented. If a variable in one term of such a variable is complimented while in the second term it is not, then such terms can be combined into a single term with that variable dropped.
    Example
    ABCD + ABCD = ABC(D + D) = (ABC).1 = ABC
    OR
    AB(C+D) + AB(C+D) = AB [(C+D) + (C+D)] = AB. 1 =AB
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.