De Morgan's First Law

What is De Morgan’s First Law?

In algebra, De Morgan's First law or First Condition states that the complement of the product of two variables is corresponding to the sum of the complement of each variable. In other words, according to De-Morgan's first laws or first theorem if ‘A’ and ‘B’ are the two variables or Boolean numbers. This indicates that the NAND gate function is similar to OR gate function with complemented inputs. Then accordingly the equations are as below;-


For NOR Gate

\[Y = \overline{A} + \overline{B}\]


For the Bubbled AND Gate

 \[Y = \overline{A} . \overline{B}\]


Symbolic representation of De Morgan's First Law Theorem

Since the NOR and the bubbled gates can be interchanged, i.e., both gates have just similar outputs for the identical set of inputs.


Hence, the equation can be algebraically represented in the figure shown below.

This equation presented above is known as DeMorgan's First Theorem. The symbolic illustration of the theorem is presented as shown below.


(image will be uploaded soon)


Role of Complementation Bars

Complementation bars are proposed to operate as grouping symbols. Hence, when a bar is broken, the expressions beneath it should remain grouped. Parentheses may be positioned around these grouped expressions as an assistance to give a miss to changing precedence.


Verifying DeMorgan’s First Theorem Using Truth Table

According to DeMorgan's First law, it proves that in conditions where two (or more) input variables are Added and negated, they are equal to the OR of the complements of the separate variables. Hence, the equivalent of the NAND function and is a negative-OR function verifying that A.B = A+B and we can literally prove this using the following table.


DeMorgan’s First Theorem Proof using Truth Table

A

B

A’

B’

A.B

(A.B)’

A’ + B’

0

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

0

1

0

1

1

1

1

0

0

1

0

0


Now that you have already understood DeMorgan's First Theorem using the Truth Table. We will make you familiar with another way to prove the theorem i.e. by using logic gates.

This is to say, we can also prove that A.B = A+B using logic gates as hereinafter.


Verifying and Execution of DeMorgan’s First Law using Logic Gates

The uppermost logic gate placement of: A.B can be executed considering a NAND gate with inputs A and B. The lowermost logic gate placement, in the beginning, inverts the two inputs yielding A and B which become the inputs to the OR gate. Thus, with this, the output from the OR gate becomes: A+B.


Therefore, an OR gate with inverters (NOT gates) on its every input is equal to a NAND gate function, and an independent NAND gate can be showcased in this way the equality of a NAND gate is a negative - OR.


(image will be uploaded soon)


Simplifying DeMorgan’s First Law with Example

According to DeMorgan’s First Law, what is an equivalent statement to "The kitchen floor needs mopping and the utensils need washing, but I will not do both."?


The two postulations are "I will mop the kitchen floor" and "I will wash the utensils." Simply modify the given statement to an "OR" statement and negate each of these postulations:


"Either I will not mop the kitchen floor or I will not wash the utensils."


P.S: that this statement lay open the likelihood that one of the tasks is completed, and it is also possible that neither chores are being completed.


Solved Examples

Problem1:

How to deduce the following equation to standard form?

F = MNO +M'N

F’ = (MNO + M’N)’l


Solution1:

Using the De Morgan's law

We get,

= (MNO)’ (M’N)’

= (M’+N’+O’) (M+N’)

Now, applying the law of distributivity

= N’ + (M’+O’) M

Again, applying Distributivity

= N’ + M’M + O’M

= N’ + MO’ (standard form)l


Problem2:

Apply De Morgan's Law to determine the inverse of the below given equation and reduce to the form of the sum-of-product:

F = MO' + MNP' + MOP


Solution2:

F’= (MO' + MNP' + MOP)’

= (MO’)’ (MNP’)’ (MOP)’

= (M’+O)(M’+N’+P)(M’+O’+P’)

= M’+O (N’+P) (O’+P’)

= M’+ (N’+P) OP’

= M’ + ON’P’ + OPP’

Thus, we get = M’ + ON’P.


Fun Facts

  • Do you know the full form of DeMorgan’s Theorems? Its Demorgan’s theorem.

  • No matter whether De Morgan's laws apply to sets, propositions, or logic gates, the anatomy always remains the same.

FAQ (Frequently Asked Questions)

What are DeMorgan's Theorems?

DeMorgan’s Theorems typically explain the correspondence between GATES with inverted inputs and GATES with inverted outputs. In simple terms, a NAND gate equals a Negative-OR gate, while a NOR gate equals a Negative-AND gate. There are 2 DeMorgan’s Theorems i.e.

  1. DeMorgan’s First law or Theorem

  2. DeMorgan’s Second law or Theorem

When “breaking-up” a complementation bar in a Boolean expression or equation, the operation without any deviation beneath the break (addition or multiplication) overturns, and moreover the bits of the broken bar still remain over the respective terms or variables.


Time and again, it becomes easier to deal with a mathematical problem by fragmenting the longest (uppermost) bar before breaking any bars beneath it. However, you should never try to break two bars in one step!

Why is DeMorgan’s Theorem Useful?

DeMorgan’s Theorem is chiefly used to solve the different and the longest Boolean algebra expressions. As mentioned above, this theorem describes the equality between the gate with identical inverted input and inverted output thus making it a common application for incorporating the fundamental gate operations like NAND gate and NOR gate. Various other uses of DeMorgan’s Theorem include:-

  • It is most widely executed in digital programming and even for drawing digital circuit diagrams.

  • This law is also applicable in computer engineering for the purpose of creating logic gates.

  • It essentially explains how mathematical concepts, statements as well as expressions are linked through their opposites.

  • In set theory, the theorem relates to the union and bisection of sets through complements.

  • In propositional rationale, De Morgan's theorems establish a link between conjunctions and disjunctions of propositions by way of negation.