Logic Function and Boolean Algebra

 

Logic Function and Boolean Algebra

Boolean algebra

The English mathematician George Boole (1815-1864) sought to give symbolic form to Aristotle's system of logic. Boole wrote a treatise on the subject in 1854, titled An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, which codified several rules of relationship between mathematical quantities limited to one of two possible values: true or false, 1 or 0. His mathematical system became known as Boolean algebra.

All arithmetic operations performed with Boolean quantities have but one of two possible outcomes: either 1 or 0. There is no such thing as "2" or "-1" or "1/2" in the Boolean world. It is a world in which all other possibilities are invalid by fiat. As one might guess, this is not the kind of math you want to use when balancing a checkbook or calculating current through a resistor. However, Claude Shannon of MIT fame recognized how Boolean algebra could be applied to on-and-off circuits, where all signals are characterized as either "high" (1) or "low" (0). His 1938 thesis, titled A Symbolic Analysis of Relay and Switching Circuits, put Boole's theoretical work to use in a way Boole never could have imagined, giving us a powerful mathematical tool for designing and analyzing digital circuits.

Boolean arithmetic

Let us begin our exploration of Boolean algebra by adding numbers together:

The first three sums make perfect sense to anyone familiar with elementary addition. The last sum, though, is quite possibly responsible for more confusion than any other single statement in digital electronics, because it seems to run contrary to the basic principles of mathematics. Well, it does contradict principles of addition for real numbers, but not for Boolean numbers. Remember that in the world of Boolean algebra, there are only two possible values for any quantity and for any arithmetic operation: 1 or 0. There is no such thing as "2" within the scope of Boolean values. Since the sum "1 + 1" certainly isn't 0, it must be 1 by process of elimination.

It does not matter how many or few terms we add together, either. Consider the following sums:

Multiplication is valid in Boolean algebra, and thankfully it is the same as in real-number algebra: anything multiplied by 0 is 0, and anything multiplied by 1 remains unchanged:

Like "normal" algebra, Boolean algebra uses alphabetical letters to denote variables. Unlike "normal" algebra, though, Boolean variables are always CAPITAL letters, never lower-case. Because they are allowed to possess only one of two possible values, either 1 or 0, each and every variable has a complement: the opposite of its value. For example, if variable "A" has a value of 0, then the complement of A has a value of 1. Boolean notation uses a bar above the variable character to denote complementation, like this:

Boolean algebraic laws

 

Logic Gates

A logic gate is an elementary building block of a digital circuit . Most logic gates have two inputs and one output. At any given moment, every terminal is in one of the two binary conditions low (0) or high (1), represented by different voltage levels. The logic state of a terminal can, and generally does, change often, as the circuit processes data. In most logic gates, the low state is approximately zero volts (0 V), while the high state is approximately five volts positive (+5 V).

X ^ Y, the logical AND operation, is replaced by x · y, or xy.

X v Y, the logical OR operation, is replaced by x + y.

¬X, the logical NEGATION operation, is replaced by x’ or .

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and XNOR.

AND gate

The AND gate, which is composed of two or more inputs and a single output, performs logical multiplication. The standard symbol for the AND gate is shown in Figure 1-3 and its truth table listed in Table 1-2. The logical operation of the AND gate is such that the output is HIGH (1) when all the inputs are HIGH, otherwise it is LOW (0). The highlighted area represents the function X=AB.

Figure 1-3 Standard Logic Symbol for AND gate

INPUT		OUTPUT
A	B
0	0	0
0	1	0
1	0	0
1	1	1

Table 1-2 Truth table for AND gate

 

OR gate

The OR gate, which is composed of two or more inputs and a single output, performs logical addition. The standard symbol for the OR gate is shown in Figure 1-5 and its truth table listed in Table 1-3. The logical operation of the OR gate is such that the output is HIGH (1) when any of the inputs are HIGH, otherwise it is LOW (0).

Figure 1-5 Standard Logic Symbol for OR gate

INPUT		OUTPUT
A	B
0	0	0
0	1	1
1	0	1
1	1	1

Table 1-3 Truth table for OR gate

 

NOT gate

The inverter (NOT circuit) performs a basic logic function called inversion or complementation. The purpose of the inverter is to change one logic level (HIGH / LOW) to the opposite logic level. In terms of bits, it changes a ‘1’ to a ‘0’ and vice versa. The standard logic symbol for the inverter and a Venn diagram illustrating the relationship between the variables and the logic gate operation, are shown in Figure 1-1. 

    Figure 1-1 Standard Logic Symbol for Inverter

We generally express the logical operation of a gate with a truth table which lists all input combinations and the corresponding outputs. The truth table for the NOT gate is shown in Table 1-1.

INPUT	OUTPUT
A
0	1
1	0

Table 1-1Truth table for NOT gate

XOR ( exclusive-OR ) gate

The XOR ( exclusive-OR ) gate acts in the same way as the logical "either/or." The output is "true" if either, but not both, of the inputs are "true." The output is "false" if both inputs are "false" or if both inputs are "true." Another way of looking at this circuit is to observe that the output is 1 if the inputs are different, but 0 if the inputs are the same.

 

 XOR gate

INPUT		XOR OUTPUT
A	B
0	0	0
0	1	1
1	0	1
1	1	0

  

 XNOR (exclusive-NOR) gate

The XNOR (exclusive-NOR) gate is a combination XOR gate followed by an inverter. Its output is "true" if the inputs are the same and "false" if the inputs are different.

 

XNOR gate

INPUT		XNOR OUTPUT
A	B
0	0	1
0	1	0
1	0	0
1	1	1

Universal Gates:

A universal gate is a gate which can implement any Boolean function without need to use any other gate type.

The NAND and NOR gates are universal gates.

In practice, this is advantageous since NAND and NOR gates are economical and easier to fabricate and are the basic gates used in all IC digital logic families.

In fact, an AND gate is typically implemented as a NAND gate followed by an inverter not the other way around!!

Likewise, an OR gate is typically implemented as a NOR gate followed by an inverter not the other way around!!

NAND gate

The NAND, which is composed of two or more inputs and a single output, is a very popular logic element because it may be used as a universal function. That is, it may be employed to construct an inverter, an AND gate, an OR gate, or any combination of these functions. The term NAND is formed by the concatenation NOT-AND and implies an AND function with an inverted output. The standard symbol for the NAND gate is shown in Figure 1-7 and its truth table listed in Table 1-4. The logical operation of the NAND gate is such that the output is LOW (0) only when all the inputs are HIGH (1).

 Figure 1-7 Standard logic symbol for NAND gate

INPUT		OUTPUT
A	B
0	0	1
0	1	1
1	0	1
1	1	0

Table 1-4 Truth table for NAND gate

NOR gate

The NOR gate, which is composed of two or more inputs and a single output, also has a universal property. The term NOR is formed by the concatenation NOT-OR and implies an OR function with an inverted output. The standard symbol for the NOR gate is shown in Figure 1-7 and its truth table listed in Table 1-5. The logical operation of the NOR gate is such that the output is HIGH (1) only when all the inputs are LOW.

Figure 1-7 Standard logic symbol for NOR gate

INPUT		OUTPUT
A	B
0	0	1
0	1	0
1	0	0
1	1	0

Table 1-5 Truth table for NOR gate

Duality Principle:

This property of Boolean algebra state that all binary expressions remain valid when following two steps are performed:

Step 1: Interchange OR and AND operators.

Step 2: Replace all 1’s by 0’s and 0’s by 1’s.

 

DeMorgan's Theorems

A mathematician named DeMorgan developed a pair of important rules regarding group complementation in Boolean algebra. Logic gates that inverting all inputs to a gate reverses that gate's essential function from AND to OR, or vice versa, and also inverts the output. So, an OR gate with all inputs inverted (a Negative-OR gate) behaves the same as a NAND gate, and an AND gate with all inputs inverted (a Negative-AND gate) behaves the same as a NOR gate. DeMorgan's theorems state the same equivalence in "backward" form: that inverting the output of any gate results in the same function as the opposite type of gate (AND vs. OR) with inverted inputs:

 

A long bar extending over the term AB acts as a grouping symbol, and as such is entirely different from the product of A and B independently inverted. In other words, (AB)' is not equal to A'B'. Because the "prime" symbol (') cannot be stretched over two variables like a bar can, we are forced to use parentheses to make it apply to the whole term AB in the previous sentence. A bar, however, acts as its own grouping symbol when stretched over more than one variable. This has profound impact on how Boolean expressions are evaluated and reduced, as we shall see.
DeMorgan's theorem may be thought of in terms of breaking a long bar symbol. When a long bar is broken, the operation directly underneath the break changes from addition to multiplication, or vice versa, and the broken bar pieces remain over the individual variables. To illustrate:


When multiple "layers" of bars exist in an expression, you may only break one bar at a time, and it is generally easier to begin simplification by breaking the longest (uppermost) bar first. To illustrate, let's take the expression (A + (BC)')' and reduce it using DeMorgan's Theorems:


Following the advice of breaking the longest (uppermost) bar first, I'll begin by breaking the bar covering the entire expression as a first step:


As a result, the original circuit is reduced to a three-input AND gate with the A input inverted:

Venn diagram and its represent of logic gates(AND, OR, NOT)

Inverter

The inverter (NOT circuit) performs a basic logic function called inversion or complementation. The purpose of the inverter is to change one logic level (HIGH / LOW) to the opposite logic level. In terms of bits, it changes a ‘1’ to a ‘0’ and vice versa. The standard logic symbol for the inverter and a Venn diagram illustrating the relationship between the variables and the logic gate operation, are shown in Figure 1-1 and Figure 1-2, respectively. 

    Figure 1-1 Standard Logic Symbol for Inverter

Figure 1-2 Venn diagram illustrating inverter operation

We generally express the logical operation of a gate with a truth table which lists all input combinations and the corresponding outputs. The truth table for the NOT gate is shown in Table 1-1.

INPUT	OUTPUT
A
0	1
1	0

                                    Table 1-1Truth table for NOT gate

Note: The total number of possible input combinations (N) is determined by the mathematical formula:

                                                                    (1-1)

where n is the number of input variables.

The AND gate

The AND gate, which is composed of two or more inputs and a single output, performs logical multiplication. The standard symbol for the AND gate is shown in Figure 1-3 and its truth table listed in Table 1-2. The logical operation of the AND gate is such that the output is HIGH (1) when all the inputs are HIGH, otherwise it is LOW (0). The Venn diagram shown in Figure 1-4 provides an insight into the AND function. The highlighted area represents the function X=AB.

Figure 1-3 Standard Logic Symbol for AND gate

 

Figure 1-4 Venn diagram illustrating AND operation

INPUT		OUTPUT
A	B
0	0	0
0	1	0
1	0	0
1	1	1

Table 1-2 Truth table for AND gate

The OR gate

The OR gate, which is composed of two or more inputs and a single output, performs logical addition. The standard symbol for the OR gate is shown in Figure 1-5 and its truth table listed in Table 1-3. The logical operation of the OR gate is such that the output is HIGH (1) when any of the inputs are HIGH, otherwise it is LOW (0). The Venn diagram shown in Figure 1-6 provides an insight into the OR function. The highlighted area represents the function X=A+B.

 Figure 1-5 Standard Logic Symbol for OR gate

INPUT		OUTPUT
A	B
0	0	0
0	1	1
1	0	1
1	1	1

Table 1-3 Truth table for OR gate

 

Figure 1-6 Venn diagram illustrating OR operation