Demorgan's Law: Infinite Values, Finite Logic

De Morgan's laws are a pair of transformation rules in Boolean algebra and set theory that relate the union and intersection of sets through complements. In propositional logic, De Morgan's laws relate conjunctions and disjunctions of propositions through negation. The laws are named after Augustus De Morgan, a 19th-century British mathematician, and they consist of two parts: ¬(A ∪ B) = ¬A ∩ ¬B and ¬(A ∩ B) = ¬A ∪ ¬B. In other words, the negation of A and B is the same as not A or not B, and the negation of A or B is the same as not A and not B. De Morgan's laws can be applied to any number of values, and they are used to simplify expressions and calculations, especially in computer engineering and programming.

De Morgan's Law in Boolean Algebra

De Morgan's Law, also known as De Morgan's Theorem, is a set of two postulates widely used in set theory and Boolean algebra. The laws are named after Augustus De Morgan, a 19th-century British mathematician who introduced a formal version of the laws to classical propositional logic.

In Boolean algebra, De Morgan's Law provides a way to simplify complex Boolean expressions and is used to define the operation of digital logic circuits. It allows us to change ORs to ANDs and ANDs to ORs in Boolean expressions.

The two laws can be expressed as follows:

• The negation of "A or B" is the same as "not A and not B." Mathematically, this can be written as: \(\overline{A + B}\) = \(\overline{A}\)•\(\overline{B}\).
• The negation of "A and B" is the same as "not A or not B." Mathematically, this can be written as: \(\overline{A•B}\) = \(\overline{A}\) + \(\overline{B}\).

These laws can be visualised using truth tables, which define the digital operation of logic AND, OR, and NOT operations using "0's" and "1's" to represent input and output conditions.

De Morgan's Law can also be applied to multiple input variables. For example, with three input variables A, B, and C, we can apply De Morgan's Law as follows:

\(\overline{A + B + C}\) = \(\overline{A}\)•\(\overline{B}\)•\(\overline{C}\)

De Morgan's Law is not limited to two or three input variables and can be generalised to n variables.

De Morgan's Law is particularly useful in electronic engineering for developing logic gates and in computer programming for simplifying logical expressions in code, making it easier to verify and optimise code.

De Morgan's Law in Set Theory

De Morgan's Law, also known as De Morgan's Theorem, is a set of two postulates widely used in set theory and Boolean algebra. The laws are named after 19th-century British mathematician Augustus De Morgan and are defined as follows:

De Morgan's First Law (Law of Union)

The complement of the union of two sets is equal to the intersection of their individual complements. This can be expressed as:

> (A ∪ B)’ = A’ ∩ B’

De Morgan's Second Law (Law of Intersection)

The complement of the intersection of two sets is equal to the union of their individual complements. This can be expressed as:

> (A ∩ B)’ = A’ ∪ B’

These laws can be visualised using Venn diagrams and are used to relate the intersection and union of sets through complements. They are useful for simplifying mathematical expressions and performing calculations, especially in the context of Boolean algebra, where they are used to change ORs to ANDs and vice versa.

De Morgan's Laws can be applied to any number of sets. For three sets, the laws can be generalised as follows:

> (A ∪ B ∪ C)’ = A’ ∩ B’ ∩ C’

> (A ∩ B ∩ C)’ = A’ ∪ B’ ∪ C’

These laws are not limited to sets and can also be applied to logical propositions and computer engineering for developing logic gates.

De Morgan's Law Logic Gates

De Morgan's laws are a set of two postulates widely used in set theory and Boolean algebra. They are named after Augustus De Morgan, a 19th-century British mathematician. The laws are as follows:

• The complement of the union of two sets is equal to the intersection of their individual complements.
• The complement of the intersection of two sets is equal to the union of their individual complements.

In other words, De Morgan's laws state that the negation of "A and B" is the same as "not A or not B", and the negation of "A or B" is the same as "not A and not B".

These laws can be applied to logic gates, which are used to perform logical operations in digital electronics. De Morgan's first theorem states that when two or more input variables are AND'ed and negated, they are equivalent to the OR of the complements of the individual variables. This means that a NAND gate (NOT AND) is equivalent to an OR gate with inverted inputs. De Morgan's second theorem states that when two or more input variables are OR'ed and negated, they are equivalent to the AND of the complements of the individual variables. So, a NOR gate (NOT OR) is equivalent to an AND gate with inverted inputs.

De Morgan's theorems are a powerful tool in digital design as they allow for the simplification of Boolean logic expressions. They can be used to express logic expressions in different forms and to simplify complex Boolean equations.

De Morgan's Law Logic

De Morgan's Law, also known as De Morgan's Theorem, is a set of two postulates widely used in set theory and Boolean algebra. The law is named after 19th-century British mathematician Augustus De Morgan, who introduced a formal version of the law to classical propositional logic.

De Morgan's Law consists of two parts:

First De Morgan's Law (Law of Union): The complement of the union of two sets is equal to the intersection of their individual complements. This can be represented as:

A ∪ B)’ = A’ ∩ B’

Second De Morgan's Law (Law of Intersection): The complement of the intersection of two sets is equal to the union of their individual complements. This can be represented as:

A ∩ B)’ = A’ ∪ B’

These laws can be applied to any number of sets and are not limited to just two sets.

In Boolean algebra, De Morgan's Law defines the relationship between the OR, AND, and the complements of variables. The laws are as follows:

First De Morgan's Law: The complement of the OR of two or more variables is equal to the AND of the complement of each variable.

A + B)’ = A’ . B’

Second De Morgan's Law: The complement of the AND of two or more variables is equal to the OR of the complement of each variable.

A . B)’ = A’ + B’

In logic, De Morgan's Law gives the relationship between AND, OR, or the negation of a statement. The following propositions are tautology:

∼ (a ∧ b) ≡ ∼ a ∨ ∼ b

∼ (a ∨ b) ≡ ∼ a ∧ ∼ b

Where ∧ represents the conjunction of statements, ∨ represents the disjunction of statements, and ~ represents the negation of a statement.

De Morgan's Law is useful in various fields, including mathematics, computer engineering, and programming. It helps simplify complex mathematical expressions, optimise code, and design electronic circuits.

De Morgan's Law in Propositional Logic

De Morgan's Law, also known as De Morgan's Theorem, is a pair of transformation rules in propositional logic and Boolean algebra that are valid rules of inference. Named after 19th-century British mathematician Augustus De Morgan, these rules allow the expression of conjunctions and disjunctions in terms of each other via negation.

The Two Laws

The first law, also known as De Morgan's Law of Union, states that the complement of the union of two sets A and B is equal to the intersection of their individual complements: (A ∪ B)' = A' ∩ B'.

The second law, or De Morgan's Law of Intersection, states that the complement of the intersection of two sets A and B is equal to the union of their individual complements: (A ∩ B)' = A' ∪ B'.

Expressing the Laws in English

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."

Applications

De Morgan's Laws are used to simplify complex expressions and calculations, and they find applications in various fields, including:

• Computer programming, where they help simplify logical expressions in code, leading to optimization.
• Electronics engineering, where they are used to develop logic gates and create cheaper hardware.
• Digital circuit design, where they are used to simplify operations.

De Morgan's Laws in Boolean Algebra

In Boolean algebra, De Morgan's Laws can be expressed as:

• \overline{A•B} = \overline{A} + \overline{B}
• \overline{A+B} = \overline{A} • \overline{B}

Here, "A" and "B" are input binary variables, and "0's" and "1's" represent digital input and output conditions. Truth tables can be created to define operations such as AND (A•B), OR (A + B), and NOT (negation).

Proving De Morgan's Laws

De Morgan's Laws can be proved using various methods, including mathematical proofs, truth tables, and Venn diagrams.

Generalized De Morgan's Laws

The generalized form of De Morgan's Laws provides an equivalence for negating conjunctions or disjunctions involving multiple terms. For a set of propositions {P1, P2, ..., Pn}, the generalized laws are:

• \lnot (P1 ∧ P2 ∧ ... ∧ Pn) = \lnot P1 ∨ \lnot P2 ∨ ... ∨ \lnot Pn
• \lnot (P1 ∨ P2 ∨ ... ∨ Pn) = \lnot P1 ∧ \lnot P2 ∧ ... ∧ \lnot Pn

De Morgan's Laws in Text Searching

De Morgan's Laws are commonly applied in text searching using Boolean operators (AND, OR, and NOT). For example, consider a set of documents containing the words "cats" and "dogs." The following two searches will return the same set of documents:

Search A: NOT (cats OR dogs)

Search B: (NOT cats) AND (NOT dogs)

Historical Context

While De Morgan introduced a formal version of these laws to classical propositional logic, similar observations were made by Aristotle and were known to Greek and Medieval logicians. William of Ockham in the 14th century and Jean Buridan also described rules that followed De Morgan's principles.

Frequently asked questions