De Morgans Gesetze

Die Gesetze von Morgan sind Identitäten zwischen den Logiken der Vorschläge . Sie wurden vom britischen Mathematiker Augustus De Morgan (1806-1871) formuliert .

Gesprochen auf Französisch

In der klassischen Logik ist die Negation der Disjunktion zweier Sätze gleichbedeutend mit der Konjunktion der Negationen der beiden Sätze, was bedeutet, dass „nicht (A oder B)“ identisch mit „(nicht A) und (nicht B)“ ist. .

Noch in der klassischen Logik ist die Negation der Konjunktion zweier Sätze äquivalent zur Disjunktion der Negationen der beiden Sätze, was bedeutet, dass „nicht (A und B)“ identisch mit „(nicht A) oder (nicht B) ist. " .

Mathematische Aussage

In dem Wissen, dass die Konjunktion durch das Zeichen : ausgedrückt wird , wird die Disjunktion durch das Zeichen ausgedrückt: und die Negation einer Formel wird geschrieben . $\ land$ $\ lor$ $F$ $\ überstreichen {{F}}$

$\ overline {(A \ land B)} \ leftrightarrow (\ overline {A}) \ lor (\ overline {B})$

$\ overline {(A \ lor B)} \ leftrightarrow (\ overline {A}) \ land (\ overline {B})$

Von diesen vier in der klassischen Logik gültigen Implikationen sind drei in der intuitionistischen Logik gültig , aber nicht: $\ overline {(A \ land B)} \ rightarrow (\ overline A) \ lor (\ overline B)$

Rechtfertigung

Um diese Formeln zu rechtfertigen, ist es zum Beispiel, die Methode verwenden , die Semantik von Wahrheitstabellen . Wir erinnern daran, dass zwei Formeln genau dann äquivalent sind, wenn sie dieselbe Wahrheitstabelle haben.

$\ overline {(A \ land B)} \ leftrightarrow (\ overline A) \ lor (\ overline B)$
$BEIM$	$B$	$A \ Land B$	$\ overline {(A \ Land B)}$	$\ überstreichen {A}$	$\ überstreichen B$	$(\ überstrich A) \ lor (\ überstrich B)$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

$\ overline {(A \ lor B)} \ leftrightarrow (\ overline A) \ land (\ overline B)$
$BEIM$	$B$	$A \ oder B$	$\ overline {(A \ oder B)}$	$\ überstreichen A$	$\ überstreichen B$	$(\ überstrich A) \ land (\ überstrich B)$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Verallgemeinerung

De Morgan Aussagen zu verallgemeinern durch Induktion Sätze, die mit Assoziativität der Gesetze und wie auch ihre Doppel distributivity . Da die beiden Beweise symmetrisch sind (es genügt, das eine Gesetz durch das andere zu ersetzen), geben wir das hier nur für das erste Gesetz an. $nicht$ $\ land$ $\ lor$

Dem Rang treu $n = 2$
So getreu der Reihe $nicht$

$\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n} \ land A _ {{n + 1}})}$

$\ leftrightarrow \ overline {((A_ {1} \ land A_ {2} \ land ... \ land A_ {n}) \ land A _ {{n + 1}})}$

$\ leftrightarrow (\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n})}) \ lor (\ overline {A _ {{n + 1}}})$

$\ leftrightarrow ((\ overline {A_ {1}}) \ lor (\ overline {A_ {2}}) \ lor ... \ lor (\ overline {A_ {n}})) \ lor (\ overline {A_ {{n + 1}}})$

Die Verallgemeinerung dieser Regeln über das Endliche hinaus ergibt die Regeln der Undefinierbarkeit universeller und existentieller Quantoren der klassischen Prädikatenrechnung . Der universelle Quantor kann als Verallgemeinerung der Konjunktion und der existenzielle Quantor als Verallgemeinerung der (nicht ausschließlichen) Disjunktion angesehen werden.

$\ forall x (\ overline {Ax}) \ leftrightarrow \ overline {\ existiert x (Ax)}$

$\ existiert x (\ overline {Ax}) \ leftrightarrow \ overline {\ forall x (Ax)}$

Und von diesen vier klassischen Implikationen ist nur eine in der intuitionistischen Logik nicht gültig . $\ overline {\ forall x (Ax)} \ rightarrow \ existiert x (\ overline {Ax})$

In der intuitionistischen Logik

In der intuitionistischen Logik haben wir nur eine abgeschwächte Form von De Morgans Gesetzen. Es gibt nur die Auswirkungen

${\ displaystyle \ lnot (A \ lor B) \ to (\ lnot A \ land \ lnot B)}$
${\ displaystyle (\ lnot A \ land \ lnot B) \ to \ lnot (A \ or B)}$
${\ displaystyle (\ lnot A \ lor \ lnot B) \ to \ lnot (A \ land B)}$

Lassen Sie uns die erste Implikation demonstrieren. Dafür müssen wir das beweisen, indem wir zugeben, dass wir haben . Wir müssen also zeigen, dass wir schießen und dass wir schießen . Beweisen wir das erste. Dies läuft darauf hinaus , zu zeigen , dass wir de und de haben . Gold . Es reicht also aus, den Modus ponens zweimal anzuwenden (Beseitigung der Implikation). ${\ displaystyle \ nicht (A \ oder B)}$ ${\ displaystyle \ nicht A \ land \ nicht B}$ ${\ displaystyle \ nicht (A \ oder B)}$ ${\ displaystyle A \ bis \ bot}$ ${\ displaystyle \ nicht (A \ oder B)}$ ${\ displaystyle B \ bis \ bot}$ ${\ displaystyle (A \ lor B) \ to \ bot}$ $BEIM$ $\ bot$ ${\ Displaystil A \ bis (A \ oder B)}$