De Morgan's Laws (Logic)

From ProofWiki
Jump to navigation Jump to search

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

Formulation 1

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

Formulation 2

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


Conjunction of Negations

Formulation 1

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

Formulation 2

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


Conjunction

Formulation 1

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

Formulation 2

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


Disjunction

Formulation 1

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

Formulation 2

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


Also known as

Some sources refer to these laws as the laws of negation.


The Intuitionist Perspective

Note that this:

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


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


All the others:

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


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


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


are not reversible in intuitionistic logic.


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