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.

                                    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

     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

     Table 1-3 Truth table for OR gate

 

Figure 1-6 Venn diagram illustrating OR operation

 

 

The 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 theses 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

  Table 1-4 Truth table for NAND gate

 

The 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

Table 1-5 Truth table for NOR gate

 

The Exclusive-OR (XOR) and Exclusive NOR (XNOR) gates

These gates are usually formed from the combination of the other logic gates already discussed. However, because of their functional importance, these gates are treated as basic gates with their own unique symbols. The truth tables for the XOR and XNOR gates, shown in Figure 1-8, are listed in Table 1-6. The Exclusive-OR is an "inequality" function and the output is HIGH (1) when the inputs are not equal to each other. Conversely, the Exclusive-NOR is an "equality" function and the output is HIGH (0) when the inputs are equal to each other.

 

Figure 1-8 Standard logic symbols for: (a) XOR (b) XNOR

 

Table 1-6 Truth table for XOR and XNOR logic gates

 

Recall that the functions associated with logic gates describe their operation. Accordingly, the interconnected assembly of these gates may be used to create any logic function. The resulting architecture formed by the grouping of these gates is referred to as a logic circuit.

The truth tables for logic circuits are constructed by applying each of the possible input combinations to the circuit inputs and determining the corresponding output.

Figure 1-9 illustrates the logic circuit diagram for the function and the corresponding truth table is listed in Table 1-7.

Figure 1-9 Logic circuit for function X=AB+A

 

         Table 1-7 Truth table for function X=AB

 

A binary variable can have two possible states, namely ‘0’ and ‘1’. A Boolean function is an expression formed with binary variables and logical operators, e.g. X=AB+CD+AD. In essence a truth table is a list which defines a Boolean function. For example, lets consider the truth table shown in Table 1-8. Note that the Function (X) is equal to 1 if A=0, B=0, C=1; otherwise X=0. The algebraic expression representing this function is therefore . Accordingly, the logic circuit is as shown in Figure1-10.

 

     Table 1-8 Truth Table

                                                                                                          

Figure 1-10 Logic Circuit

 

Boolean Algebra

Definition:

Boolean Algebra: A mathematical system for formulating logical statements with symbols so that problems can be solved in a manner to ordinary algebra.

In short, Boolean algebra is the mathematics of digital systems. The basic rules for Boolean addition and multiplication are presented in Table 1-9

 

       Table 1-9 Boolean Addition and Multiplication

 

Laws of Boolean Algebra

 

Commutative Laws

The commutative law of addition for two variables is algebraically expressed as

A + B = B + A

The commutative law of multiplication for two variables is expressed as

AB = BA

In summary, the order in which the variables are ORed or ANDed make no difference.

Associative Laws

The associative law of addition of three variables is expressed as

A + (B + C) = (A + B) + C

The associative law of multiplication of three variables is expressed as

A(BC) = (AB)C

In summary, ORing or ANDing a grouping of variables produces the same result regardless of the grouping of the variables.

Distributive Law

The distributive law of three variables is expressed as follows:

A (B+C) = AB + AC

This law states that ORing several variables and ANDing the result is equivalent of ANDing the single variable with each of the variables in the grouping, then ORing the result.

 

 

By combining the laws of Boolean algebra and our knowledge of logic gates we form several useful rules that may be used in manipulating and simplifying Boolean algebra expressions. Rules 1-9, as listed in Table 1-10, are the core precepts from which rules 10-12 are derived. Note that in each case, A, B, or C can either represent a single variable of a combination of variables.

 

Rule Number	Boolean Expression
1
2
3
4
5
6
7
8
9
10
11
12

   Table 1-10 Rules of Boolean Algebra

All these rules, in particular rules 1-9, are easily verified using truth tables.

Let us examine two methods by which we can prove the relationships of rules 10-12. First we use the laws and rules of Boolean algebra. Second we employ the use of truth tables.

 

Method 1:

A + AB = A (1+B)	distributive law
= A .1	rule 2
=A	rule 4

 

Method 2:

            Table 1-11 Table illustrating A+AB=A

As the shaded columns are equal then the rule has be shown to be correct.

Similarly for Rule 12, we can apply the same two methods to prove the relationship.

Method 1:

(A + B)(A+C) = AA +AC + BA + BC	distributive law
= A + AC + BA + BC	rule 7
= A (1 + C) + BA + BC	distributive law
= A.1 +BA + BC	rule 2
= A + BA + BC	rule 4
= A (1 + B) + BC	distributive law
= A.1 + BC	rule 2
= A + BC	rule 4

Method 2:

      Table 1-11 Table illustrating (A + B)(A+C) = A+BC

Again, as the shaded columns are equal then the rule has be shown to be correct

 

Can you prove rule 11 using both the truth table and the Boolean algebra methods