17.6 De Morgan’s Laws – Pulse and Digital Circuits

17.6 DE MORGAN'S LAWS

De Morgan, a mathematician, stated two important rules for group complementation in Boolean algebra. These are known as De Morgan’s laws.

Law 1: This law states that the complement of a sum of variables is equal to the product of their individual complements, shown in Fig. 17.14(a).

De Morgan’s first law allows the breaking of one bar at a time, generally, starting with the longest bar. Consider When the bar is broken, the resultant expression is . This means that a NOR is converted as a negative AND, as shown in Fig. 17.14(b).

The truth tables for a NOR gate and a bubbled AND gate are given in Table 17.22(a) and Table 17.22(b), respectively. It shows that the NOR gate is equivalent to a bubbled AND gate (inputs inverted) from the Tables 17.22(a) and (b).

  1. If there are multiple layers of bars, the procedure is to break the longest bar first, then the next long bar and so on. Consider . Breaking the largest bar gives us and. this is the same as .QR, since . Thus, we see that This is a three-input AND gate with input P inverted, as shown in Fig. 17.15.
  2. Alternately, you can first break the shortest bar and proceed by breaking the next shortest bar and so on. Consider the earlier Boolean expression Now if we first break the short bar the expression reduces to . Now breaking the long bar at two places, this reduces to which, is the same as QR. This law can be extended to any number of variables or combinations.

Example 1:

Example 2:

This law allows the transformation from the sum of products (SOP) to the product of sums (POS).

Law 2: This law states that the complement of a product of variables is equal to the sum of their individual complements.

Implementation of LHS of Eq. 17.1

FIGURE 17.14(a) The circuits for the complement of a sum of variables

Implementation of RHS of Eq. 17.1

FIGURE 17.14(b) The circuit for the product of the individual complements

FIGURE 17.15 The three-input AND gate with input P inverted

 

TABLE 17.22 (a) The truth table for a NOR gate; (b) the truth table for a bubbled AND gate

TABLE 17.23 (a) The truth table for NAND gate; (b) the truth table for bubbled OR gate

Consider the Boolean function . When the bar is broken as per this law, the resultant function is + . This means that a NAND is converted as a negative OR, as shown in Fig. 17.16(a) and Fig. 17.16(b).

The truth tables for NAND gate and the negative OR gate are shown in Table 17.23(a) and Table 17.23(b). It shows that the NAND gate is equivalent to a bubbled OR gate from Tables 17.23(a) and (b). This law can be extended to any number of variables or combination of variables.

Example 1:

Example 2:

The SOP form can be changed to POS form and vice-versa using De Morgan’s laws following these three steps:

Implementation of LHS of Eq. 17.2

FIGURE 17.16(a) The complement of a product of variables

Implementation of RHS of Eq. 17.2

FIGURE 17.16(b) The sum of their individual complements

FIGURE 17.17 The logic circuit of Example 17.3

  1. Complement the entire given function.
  2. Change all the ANDs to ORs and all ORs to ANDs.
  3. Complement each of the individual variables.

Thus, De Morgan’s laws help us in simplifying a Boolean function, thereby reducing the complexity of the logic circuit.

EXAMPLE

Example 17.3: Consider the Boolean function , and derive the gate circuit using the POS form.

Solution:

Breaking the long bar in the middle, the resultant function is:

Now breaking the other two bars, this reduces to,

The resultant circuit is as shown in Fig. 17.17.

EXAMPLE

Example 17.4: Simplify the gate circuit shown in Fig. 17.18(a).

FIGURE 17.18(a) The logic gate circuit of Example 17.4

Solution: As this circuit appears complicated, we use De Morgan’s laws to simplify the circuit shown in Fig. 17.18(a). The Boolean function is

FIGURE 17.18(b) The simplified circuit of the circuit shown in Fig. 17.18(a)

Breaking the largest bar, this reduces to:

Using the relation for double inversion, we know that = P

Therefore,

 

f = P

The simplified gate circuit of Fig 17.18(a) reduces to that shown in Fig. 17.18(b).

EXAMPLE

Example 17.5: Apply De Morgan’s theorem and simplify the expression .

Solution:

EXAMPLE

Example 17.6: Reduce the expression .

Solution: