Duality Theorem in Digital Electronics

In digital electronics, there are two basic types of topologies, AND-OR and OR-AND.

OR-AND topology is also known as Product of Sums [ANDing of ORs].

OR-AND Topology - Product of Sums

AND-OR topology is also known as Sum of Products [ORing of ANDs]

AND-OR Topology - Sum of Products
Using duality theorem, Sum of Products is converted to Product of Sums and vice versa. Each OR gate is changed to AND gate and vice versa, and all 0′s and 1′s are complemented while keeping following points into consideration:

1) A + 1 = 1
2) A + 0 = A
3) A . 1 = A
4) A . 0 = 0
5) A + B = B + A
6) A . B = B . A

Example of Duality Theorem

Let say we have an expression F = ab + bc + ac

To calculate it’s dual, + operator should be changed with . operation and all 0 should be changed to 1. Thus, dual of F is:

Fdual = (a+b) • (b+c) • (a+c)

Now let’s understand how can we obtain F from Fdual:

Fdual = (a+b) • (b+c) • (a+c)
= (ab + ac + b + bc) . (a+c)
= ((ac + b) + b.(a+c)) . (a+c)
= (ac + b).(a+c) + b.(a+c).(a+c)
= ac + ac + ba + bc + b.(a+c)      [A.A = A]
= ac + ba + bc + b.(a+c)         [A+A = A]
= ac + ba + bc + ba + bc
= ac + ba+ bc        [A+A = A]
= ba + bc + ac       [A+B = B+A]
= ab + bc + ac       [AB = BA]
= F

Thus, advantage of duality theorem is that starting from one relation, another relation is obtained which is also a valid boolean identity.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">