1 Boolean Algebra and Digital Logic

1.7 Duality Principle and Boolean Lattices

1.7 Duality Principle and Boolean Lattices

From the Boolean Postulates and Theorems introduced in Chapter 1.6 important generalizations can be derived that are of fundamental importance for Digital Design.

1.7.1 The Duality Principle

From the basic requirements for a Boolean Algebra defined in the form of postulates the duality principle can be derived.

Duality Principle:

For each statement that can be derived from the Boolean postulates a dual statement exists, that can be formed by simultaneously interchanging the operators "+" and "-" as well as the individual elements "0" and "1".

Obviously this principles is a direct result of the symmetric construction of the postulates as far as the operations and the elements are concerned.

Especially the De Morgan Theorem is a dual statement. Using the three functions "+", "-", and "NOT" it can be written in a generalized form:

(1.31),

where f is a Boolean function and x_i are the Boolean variables.

Using this equation, the term "dual operation" (dual function) can be introduced in modified form:

Definition: dual

Two operations f₁ and f₂sub> are dual to each other, when the following is valid:

(1.32).

It follows that two functions are dual to each other when they are transformed through an exchange of the 0- and 1-elements:

Example:

The function that is dual to the AND-function should be determined through inversion of the individual elements.

Obviously this can easily be done using truth tables (function tables):

The left function table shows the AND-function. The right table shows the same function after the transformation. Obviously the second table corresponds directly to the known OR-function.

Result:

The conjunction (AND) and the disjunction (OR) are dual to each other.

1.7.2 Boolean Lattices

The above introduced entity of

• the elementary values 0/1 (or n-tuples formed with these values, respectively) and
• the operations "Conjunction", Disjunction", and "Negation"

is of very special importance in mathematics. It is called a Boolean Lattice. The importance of these three operations is based on the fact that every problem in propositional logic can be solved just with them alone. Therefore the system formed with "AND, "OR", and "NOT" alone is also referred to as a "complete logical system".

Evidently this statement corresponds directly to the fact, that for the implementation of the Boolean Algebra only these functions or their operators (•, +, ¯) are needed.

The limitation to these three basic functions has very important consequences for practical applications. It shows that for the realization of arbitrary logical circuits only exactly these functions are necessary. And this on the other hand means that the design of logical circuits can be limited to the use of only very few components. Ultimately this fact leads to the introduction of so-called "universal logical blocks", which in turn form the foundation for what is called "Programmable Logic" (see below).

But the definition of a complete system is not limited to these three basic functions. Such a system can even be described using just one function. Functions with this property are the inverse forms of the functions "AND" and "OR", which are also known as "NAND" (Not-AND) and "NOR" (Not-OR), respectively.

Because of their outstanding importance, special names have been given to these function, in order to honour their discoverers:

That means that each of these two functions forms a complete system. As the entire logic algebra can be defined using "AND", "OR", and "NOT", it is sufficient for a proof to show that these functions can be built up just using the Sheffer or Peirce function, respectively.

Proof using the Sheffer Function (NAND):

Negation:
AND:
OR:

Using NAND gates this leads to the following practical implementations:

Figure 1.34: NAND Realization of Negation, AND, OR.

Beyond this, also the necessary constants "0" and "1" can be realized with the help of the Sheffer or Peirce Function.

Proof for the realization using the Sheffer Function (NAND):

Based on the fact that this system can also generate the two constants, it is also referred to as a "strongly complete system".

Thus it has been shown that all logical circuits can be built up using a single component (e.g. a NAND gate).