Redundancy Theorem and Duality Principle

In this tutorial, you will learn about the redundancy theorem and self-duality principle used in Boolean Algebra to minimize the Boolean expressions. You will also learn about negative-positive logic used in Boolean algebra.

Contents:

1. Redundancy Theorem
2. Rules to Follow in Redundancy Theorem
3. Proof of Redundancy Theorem Using Boolean Algebra
4. Duality-Principle
5. Self-Dual Function
6. Positive Logic
7. Negative Logic
8. Properties of Positive and Negative Logic

Redundancy Theorem

According to the redundancy theorem, for any expression containing conjunction or disjunction of three variables, in which only one variable appears in both its normal form and complemented form, those terms which do not contain this negated and unnegated variable are said to be redundant.
They can be excluded without affecting our results.

For example,

• AB + A’C + BC, in this the variable A occurs as A and A’, thus we can remove any terms that do not contain A or A’. This expression can be re-written as AB + A’C.
• (A+B’) . (C+ B) . (A+C), in this the variable B occurs as B and B’, thus we remove the term (A+C) as it does not contain B or B’, our expression becomes, (A+B’) (C + B).

The Redundancy Theorem is also known as the Consensus law.

Rules to Follow in Redundancy Theorem

Here are the rules to keep in mind while applying the Redundancy theorem to any expression.

• The theorem is valid for only three variables.
• Each variable should occur twice as a normal or a complement.
• Only one of the variables must be present in its normal as well as complemented form.

For example, the duality principle cannot be applied to A’B + A’C + BC, as no variable is present in its both negated and unnegated form. It cannot be applied to A’B’ + BC + CA, as two variables are present in negated and unnegated form.

Proof of Redundancy Theorem Using Boolean Algebra

Here are the examples along with their derivations using Boolean algebra laws.

1. AB + A’C + BC

   = AB + A’C + BC (A + A’) We multiply BC with A + A’ as it is equal to A+A’ = 1 and BC.1 = BC.
   = AB + ABC + A’C + A’BC We group the terms and take out the common.
   = AB (1 + C) + A’C (1+ C)
   = AB + A’C As OR operation with 1 gives 1 according to Boolean algebra.

2. (A+B’) (C+B) (A+C)

   = (A + B’) (C + B) (A + C + BB’) We add BB’ which is equal to 0 as it will make no difference.
   = (A + B’) (C + B) (A + C + B) (A + C + B’) We apply distributive property and group the terms.
   = (A + B’) (A + B’ + C) (C + B) (C + B +A) A + B’ and C + B are common in 1^st two terms and last two.
   = (A + B’) (1 + C) (B + C) (1 + A) Taking out the common
   = (A + B’) (B + C)

Thus, we can see on applying the laws of Boolean algebra, we got the same results as we had using the redundancy theorem which proves the correctness of the redundancy theorem.

Duality Principle

According to the duality principle, in any function the ‘AND’ operations and ‘OR’ operations can be exchanged simultaneously without affecting the result. The obtained result is known as the dual of the function. For example,

• f (A, B, C) = ABC’ + A’B’C + AB’C can be written as,
  f^D (A, B, C) = (A + B + C’) (A’ + B’ +C) (A + B’ + C)
• f (X, Y, Z) = XY’Z + X’YZ’
  f^D (X, Y, Z) = (X + Y’ + Z) (X’ + Y + Z’)

This principle can be applied as we can simultaneously change all 0s into 1s and 1s into 0s and the equality still holds. For example, B + 1 = 1 also holds true if 1–> 0 for both sides, B.0 = 0. Also, if we perform dual twice on a function, we get back the function.

Self-Dual Functions

Any function is said to be self-dual if its one-time dual gives the function back. Expression wise it is, (f^D ) = f. An example of self-dual functions is: –

• f (A, B, C) = AB + BC + CA
  its f^D is (A + B) (B + C) (C + A)
  = (A + B) (A+C) (B + C)
  = (A + BC) (B + C) Applying distributive law (A + BC = (A+B) (A+C))
  = (AB + AC + BC) Expanding the result by multiplying each term
  = f

Positive Boolean Logic

In the positive Boolean logic, we treat the higher value or the more positive value of voltage as HIGH and the less positive voltage as LOW. High is represented by 1 and low by 0 in positive logic. Here are the truth tables of AND, OR and NOT using positive Boolean logic.

Practically as an example, if we take 3V and 0V, then our 3V will represent high (1), and -1V will represent low logic (0).

Negative Boolean Logic

In the negative Boolean logic, the more negative represents HIGH and the less negative value represents LOW. So, here 0 represents high logic and 1 means logic low. Here is the truth table for AND, OR & NOT using negative Boolean logic.

Practically as an example, if we take 3V and -4V, then our -4V will represent high (0) and 3V will represent low logic (1).

Properties of Positive and Negative Boolean Logic

Here are the properties of negative and positive logic listed below.

• The AND operation in positive logic is equivalent to OR Operation in negative logic.
• The OR operation in positive logic is equivalent to AND operation in negative logic.
• The NOR operation remains unchanged as it simply inverts the values.