De Morgan's Laws (Logic)

This proof is about De Morgan's Laws in the context of Propositional Logic. For other uses, see De Morgan's Laws.

Theorem

Disjunction of Negations

$\neg p \lor \neg q \dashv \vdash \neg \paren {p \land q}$

Conjunction of Negations

$\neg p \land \neg q \dashv \vdash \neg \paren {p \lor q}$

Conjunction

$p \land q \dashv \vdash \neg \paren {\neg p \lor \neg q}$

Disjunction

$p \lor q \dashv \vdash \neg \paren {\neg p \land \neg q}$

The Intuitionist Perspective

Note that this:

$\neg p \land \neg q \dashv \vdash \neg \paren {p \lor q}$

can be proved in both directions without resorting to the LEM.

None of the others:

$\neg p \lor \neg q \vdash \neg \paren {p \land q}$

$p \land q \vdash \neg \left({\neg p \lor \neg q}\right)$

$p \lor q \vdash \neg \paren {\neg p \land \neg q}$

is reversible in intuitionistic logic.

Also known as

De Morgan's Laws are also known as the De Morgan formulas.

Some sources, whose context is that of logic, refer to them as the laws of negation.

Some sources refer to them as the duality principle.

Also see

• De Morgan's Laws in the context of set theory.

Source of Name

This entry was named for Augustus De Morgan.

Historical Note

Augustus De Morgan proposed what are now known as De Morgan's laws in $1847$, in the context of logic.

They were subsequently applied to the union and intersection of sets, and in the context of set theory the name De Morgan's laws has been carried over.

Technical Note

When invoking De Morgan's Laws in a tableau proof, use the {{DeMorgan}} template:

{{DeMorgan|line|pool|statement|depends|type}}

where:

line is the number of the line on the tableau proof where the specific instance of De Morgan's Laws is to be invoked

pool is the pool of assumptions (comma-separated list)

statement is the statement of logic that is to be displayed in the Formula column, without the $ ... $ delimiters

depends is the line (or lines) of the tableau proof upon which this line directly depends

type is the type of De Morgan's Law: Disjunction, Conjunction, Disjunction of Negations or Conjunction of Negations, whose link will be displayed in the Notes column.

Sources

• 1973: Irving M. Copi: Symbolic Logic (4th ed.) ... (previous) ... (next): $2$ Arguments Containing Compound Statements: $2.4$: Statement Forms
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): De Morgan's laws
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): De Morgan's laws