Logic Function and Boolean Algebra
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 threeinput AND gate with the A input inverted:
Boolean algebra
The English mathematician George Boole (18151864) 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 onandoff 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 realnumber 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 lowercase. 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 13 and its truth table listed in Table 12. 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 13 Standard Logic Symbol for AND gate
OUTPUT
 
A

B
 
0

0

0

0

1

0

1

0

0

1

1

1

Table 12 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 15 and its truth table listed in Table 13. 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 15 Standard Logic Symbol for OR gate
INPUT

OUTPUT
 
A

B
 
0

0

0

0

1

1

1

0

1

1

1

1

Table 13 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 11.
Figure 11 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 11.
INPUT

OUTPUT

A
 
0

1

1

0

Table 11Truth table for NOT gate
XOR ( exclusiveOR ) gate
The XOR ( exclusiveOR ) 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
XOR OUTPUT
 
A

B
 
0

0

0

0

1

1

1

0

1

1

1

0

XNOR (exclusiveNOR) gate
The XNOR (exclusiveNOR) 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 NOTAND and implies an AND function with an inverted output. The standard symbol for the NAND gate is shown in Figure 17 and its truth table listed in Table 14. The logical operation of the NAND gate is such that the output is LOW (0) only when all the inputs are HIGH (1).
Figure 17 Standard logic symbol for NAND gate
INPUT

OUTPUT
 
A

B
 
0

0

1

0

1

1

1

0

1

1

1

0

Table 14 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 NOTOR and implies an OR function with an inverted output. The standard symbol for the NOR gate is shown in Figure 17 and its truth table listed in Table 15. The logical operation of the NOR gate is such that the output is HIGH (1) only when all the inputs are LOW.
Figure 17 Standard logic symbol for NOR gate
INPUT

OUTPUT
 
A

B
 
0

0

1

0

1

0

1

0

0

1

1

0

Table 15 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 NegativeOR gate) behaves the same as a NAND gate, and an AND gate with all inputs inverted (a NegativeAND 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 threeinput 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 11 and Figure 12, respectively.
Figure 11 Standard Logic Symbol for Inverter
Figure 12 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 11.
INPUT

OUTPUT

A
 
0

1

1

0

Table 11Truth table for NOT gate
Note: The total number of possible input combinations (N) is determined by the mathematical formula:
(11)
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 13 and its truth table listed in Table 12. 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 14 provides an insight into the AND function. The highlighted area represents the function X=AB.
Figure 13 Standard Logic Symbol for AND gate
Figure 14 Venn diagram illustrating AND operation
INPUT

OUTPUT
 
A

B
 
0

0

0

0

1

0

1

0

0

1

1

1

Table 12 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 15 and its truth table listed in Table 13. 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 16 provides an insight into the OR function. The highlighted area represents the function X=A+B.
Figure 15 Standard Logic Symbol for OR gate
INPUT

OUTPUT
 
A

B
 
0

0

0

0

1

1

1

0

1

1

1

1

Table 13 Truth table for OR gate
Figure 16 Venn diagram illustrating OR operation