Applying De Morgan's Law To Gates: A Comprehensive Guide

De Morgan's theorem, also known as De Morgan's law, is a fundamental principle in Boolean algebra that provides two transformation rules for expressions in propositional logic. In simple terms, it allows us to change 'OR' to 'AND' and vice versa, as well as negate the expressions. This theorem is named after Augustus De Morgan, a 19th-century British mathematician. De Morgan's theorem is commonly applied in computer engineering and digital logic to simplify circuit designs. It is also used to express logic expressions in different forms and to simplify Boolean logic expressions. In the context of logic gates, De Morgan's theorem states that a NAND gate is equivalent to an OR gate with inverted inputs, and a NOR gate is equivalent to an AND gate with inverted inputs.

De Morgan's first theorem

For example, if we perform the AND operation of two input variables and then perform the NOT operation of the result, the result will be the same as the OR operation of the complement of that variable. This theorem can be applied to three, four, or more input variables as well.

De Morgan's second theorem

De Morgan's theorem is a fundamental principle in Boolean algebra that allows for the simplification of Boolean logic expressions and can be used to express logic expressions in different forms. It is commonly used in computer engineering and digital logic to simplify circuit designs.

De Morgan's theorem can be broken down into two theorems. De Morgan's Second Theorem states that the NAND gate is equivalent to a bubbled OR gate. In other words, when two or more input variables are OR'ed and negated, they are equivalent to the AND of the complements of the individual variables. This means that the equivalent of the NOR function is a negative-AND function, proving that A+B = AB, where A and B are logic (or Boolean) input binary variables.

The Boolean expression for the NAND gate can be given as:


The Boolean expression for the bubbled OR gate can be given as:


Since NAND and bubbled OR gates produce the same output for the same set of inputs, we can conclude that:


This identity or equation is known as De Morgan's Second Theorem.

De Morgan's theorems can be applied to the simplification of gate circuits. For example, we can start by generating an equivalent Boolean expression by placing a sub-expression label at the output of each gate as the inputs become known. We can then label the outputs of the first NOR gate and the NAND gate. When dealing with inverted-output gates, it is often easier to write an expression for the gate's output without the final inversion and then add an arrow pointing to the bubble before the inversion.

De Morgan's theorems describe the equivalence between gates with inverted inputs and gates with inverted outputs. This means that we can replace all the AND operators with OR operators, or vice versa, and then complement each of the terms or variables in the expression by inverting it (i.e., changing 0's to 1's and 1's to 0's) before inverting the entire function.

Boolean algebra

DeMorgan's Theorem, named after 19th-century British mathematician Augustus De Morgan, is a fundamental principle in Boolean algebra. It is a pair of transformation rules that are valid rules of inference, allowing the expression of conjunctions and disjunctions in terms of each other via negation. In other words, DeMorgan's Theorem states that the complement of the result obtained by 'OR'ing variables is the same as 'AND'ing the complements of the individual variables, and vice versa.

DeMorgan's Theorem can be expressed in English as:

> The negation of "A and B" is the same as "not A or not B".

> The negation of "A or B" is the same as "not A and not B".

In Boolean algebra, this can be expressed as:

> The complement of A and B is the same as the complement of A or the complement of B

> The complement of A or B is the same as the complement of A and the complement of B

This can be further simplified to:

> not (A and B) = (not A) or (not B)

> not (A or B) = (not A) and (not B)

DeMorgan's Theorem can be applied to the negation of a disjunction or the negation of a conjunction in all or part of a formula. For example, if it is false that either A or B is true, then it must follow that both A and B are not true. Conversely, if at least one of A or B must be false for the claim "A and B are both true" to be true, then the disjunction of A and B must be false, and the negation of said disjunction must be true.

DeMorgan's Theorem is useful for simplifying Boolean logic expressions, as it can be used to express logic expressions in different forms. It can be applied to the simplification of logical expressions in computer programs and digital circuit designs.

In digital logic, DeMorgan's Theorem describes the equivalence between gates with inverted inputs and gates with inverted outputs. For example, a NAND gate is equivalent to a Negative-OR gate, and a NOR gate is equivalent to a Negative-AND gate.

Logic gates

De Morgan's laws are a set of two transformation rules that can express conjunctions and disjunctions in terms of each other via negation. In other words, they allow us to convert between AND and OR operations by applying negation to the inputs or outputs of a gate. This is particularly useful when we want to prove that a NAND gate is equivalent to an OR gate with inverted inputs, and a NOR gate is equivalent to an AND gate with inverted inputs.

The first theorem states that the negation of "A and B" is the same as "not A or not B". In other words, the complement of the product of two or more variables is equal to the sum of the complement of each variable. For example, if we have two sets, A and B, the complement of their union (A U B) is equal to the intersection of their complements (A' and B').

The second theorem states that the negation of "A or B" is the same as "not A and not B". In other words, the complement of the sum of two or more variables is equal to the product of the complement of each variable. For instance, if we have two variables, A and B, the complement of A + B is equal to A' . B'.

These theorems can be applied to logic gates to simplify circuits. For example, 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. This means that by adding NOT gates to the inputs or outputs of a gate, we can convert it into its logical equivalent.

De Morgan's laws are not limited to two variables and can be generalised to multiple inputs. They are widely used in computer engineering and digital logic to optimise circuit designs and simplify complex logical conditions, making code more efficient and readable.

Digital logic

De Morgan's laws, also known as De Morgan's theorems, are a set of rules in propositional logic and Boolean algebra that allow for the simplification of logical expressions in computer programs and digital circuit designs. These laws are named after Augustus De Morgan, a 19th-century British mathematician.

De Morgan's first theorem states that the complement of the AND operation of two input variables is equal to the OR operation of the complement of those variables. In other words, if you perform the AND operation on two input variables and then negate the result, you will get the same outcome as performing the OR operation on the complements of those variables. This theorem proves that NAND (NOT AND) is equivalent to a negative OR function, demonstrating the equation A.B = A+B.

De Morgan's second theorem states that the complement of the OR operation of two input variables is equal to the AND operation of the complement of those variables. So, if you perform the OR operation on two input variables and then negate the result, you will obtain the same result as performing the AND operation on the complements of those variables. This theorem shows that NOR (NOT OR) is equivalent to a negative AND function, proving that A+B = A.B.

These theorems can be applied to more complex expressions by breaking down the expression into smaller parts and treating each part as a single variable. Additionally, De Morgan's theorems can be used to express logic expressions in different forms, even if they don't originally contain inversion terms. This can be useful for simplifying Boolean equations, but care must be taken to remember to apply the final inversion.

In digital logic and computer engineering, De Morgan's laws are commonly applied to simplify circuit designs. They provide an understanding of the equivalence between gates with inverted inputs and gates with inverted outputs. For example, a NAND gate is equivalent to a Negative-OR gate, and a NOR gate is equivalent to a Negative-AND gate. This principle can be extended to other logic gates, such as XOR and XNOR, by creating alternate symbols with De Morgan-style symbols.

De Morgan's laws also have applications in set theory and computer science. In set theory, they can be used to understand the relationship between unions and intersections of sets and their complements. In computer science, they can be applied to text searching using Boolean operators (AND, OR, and NOT), helping to refine and optimise search queries.

Frequently asked questions