Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
De Morgan's laws
Summary
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.
The rules can be expressed in English as:
The negation of a disjunction is the conjunction of the negations
The negation of a conjunction is the disjunction of the negations
or
The complement of the union of two sets is the same as the intersection of their complements
The complement of the intersection of two sets is the same as the union of their complements
or
not (A or B) = (not A) and (not B)
not (A and B) = (not A) or (not B)
where "A or B" is an "inclusive or" meaning at least one of A or B rather than an "exclusive or" that means exactly one of A or B.
In set theory and Boolean algebra, these are written formally as
where
and are sets,
is the complement of ,
is the intersection, and
is the union.
In formal language, the rules are written as
and
where
P and Q are propositions,
is the negation logic operator (NOT),
is the conjunction logic operator (AND),
is the disjunction logic operator (OR),
is a metalogical symbol meaning "can be replaced in a logical proof with", often read as "if and only if". For any combination of true/false values for P and Q, the left and right sides of the arrow will hold the same truth value after evaluation.
Another form of De Morgan's law is the following as seen in the right figure.
Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan's laws are an example of a more general concept of mathematical duality.
The negation of conjunction rule may be written in sequent notation:
and
The negation of disjunction rule may be written as:
and
In rule form: negation of conjunction
and negation of disjunction
and expressed as a truth-functional tautology or theorem of propositional logic:
where and are propositions expressed in some formal system.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.