De Morgan's Laws (Logic)

From ProofWiki
Jump to: navigation, 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 \left({\neg p \lor \neg q}\right) \iff \left({\neg \left({p \land q}\right)}\right)$


Conjunction of Negations

Formulation 1

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

Formulation 2

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


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)$


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.


Sources