Digital Logic Circuits - Boolean Theorems and DeMorgan's Theorem

Boolean Theorems

Investigating the various Boolean theorems (rules) can help us to simplify logic expressions and logic circuits.

Multivariable Theorems

The theorems presented below involve more than one variable:

(9)	x + y = y + x (commutative law)
(10)	x * y = y * x (commutative law)
(11)	x+ (y+z) = (x+y) +z = x+y+z (associative law)
(12)	x (yz) = (xy) z = xyz (associative law)
(13a)	x (y+z) = xy + xz
(13b)	(w+x)(y+z) = wy + xy + wz + xz
(14)	x + xy = x [proof see below]
(15)	x + x'y = x + y

---

Proof of (14)

x + xy	= x (1+y)
	= x * 1 [using theorem (6)]
	= x [using theorem (2)]

DeMorgan's Theorem

DeMorgan's theorems are extremely useful in simplifying expressions in which a product or sum of variables is inverted. The two theorems are:

(16) (x+y)' = x' * y'

Theorem (16) says that when the OR sum of two variables is inverted, this is the same as inverting each variable individually and then ANDing these inverted variables.

(17) (x*y)' = x' + y'

Theorem (17) says that when the AND product of two variables is inverted, this is the same as inverting each variable individually and then ORing them.

Example

X	= [(A'+C) * (B+D')]'
	= (A'+C)' + (B+D')' [by theorem (17)]
	= (A''*C') + (B'+D'') [by theorem (16)]
	= AC' + B'D

Three Variables DeMorgan's Theorem

(18) (x+y+z)' = x' * y' * z'

(19) (xyz)' = x' + y' + z'

Universality of NAND & NOR Gates

It is possible to implement any logic expression using only NAND gates and no other type of gate. This is because NAND gates, in the proper combination, can be used to perform each of the Boolean operations OR, AND, and INVERT.

In a similar manner, it can be shown that NOR gates can be arranged to implement any of the Boolean operations.

Alternate Logic Gate Representations

The left side of the illustration shows the standard symbol for each logic gate, and the right side shows the alternate symbol. The alternate symbol for each gate is obtained from the standard symbol by doing the following:

1. Invert each input and output of the standard symbol. This is done by adding bubbles (small circles) on input and output lines that do not have bubbles, and by removing bubbles that are already there.

2. Change the operation symbol from AND to OR, or from OR to AND. (In the special case of the INVERTER, the operation symbol is not changed.)

Several points should be stressed regarding the logic symbol equivalences:

1. The equivalences are valid for gates with any number of inputs.

2. None of the standard symbols have bubbles on their inputs, and all the alternate symbols do.

3. The standard and alternate symbols for each gate represent the same physical circuit: there is no difference in the circuits represented by the two symbols.

4. NAND and NOR gates are inverting gates, and so both the standard and alternate symbols for each will have a bubble on either the input or the output. AND and OR gates are noninverting gates, and so the alternate symbols for each will have bubbles on both inputs and output.

Concept of Active Logic Levels:

When an input or output line on a logic circuit symbol has no bubble on it, that line is said to be active-HIGH. When an input or output line does have a bubble on it, that line is said to be active-LOW. The presence or absence of a bubble, then, determines the active-HIGH/active-LOW status of a circuit's inputs and output, and is used to interpret the circuit operation.