Software Engineering Tutorial

Discrete Mathematics Tutorial

Digital Electronics Tutorial

Duality Principle and Rules for Reduction of Boolean Expressions

In this tutorial, we will learn about the duality principle and rules for reduction of Boolean expressions. By Saurabh Gupta Last updated : May 10, 2023

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.
    ABCD + ABCD = ABC(D + D) = (ABC).1 = ABC
    AB(C+D) + AB(C+D) = AB [(C+D) + (C+D)] = AB. 1 =AB

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.