Zum Inhalt springen
Topos Uranos
Deutsch

De-Morgan-Gesetze und Distributivgesetze

Zusammenfassung

Diese Lektion schließt die Einheit über die Deduktion mit zwei Familien von Äquivalenzen ab, die die ganze Mathematik verwendet: den De-Morgan-Gesetzen, die sagen, wie die Negation eine Konjunktion oder eine Disjunktion durchquert, und den Distributivgesetzen, die sagen, wie sich eine Konjunktion über eine Disjunktion und eine Disjunktion über eine Konjunktion verteilt. Bevor sie bewiesen werden, wird eine Unterscheidung geklärt, von der sie abhängen: Zwei Ausdrücke, die dieselbe Zeichenkette bezeichnen, lassen sich ohne Weiteres gegeneinander austauschen, weil sie dieselbe Formel sind; zwei bloß äquivalente Formeln dagegen lassen sich innerhalb einer anderen Formel nur mit der Ersetzung äquivalenter Formeln austauschen, Schicht für Schicht. Mit dieser Vorsicht werden die beiden De-Morgan-Gesetze, ihre Varianten (darunter die Negation einer Implikation) und die beiden Distributivgesetze durch Ableitung bewiesen, jedes in beiden Richtungen. Die Aufgaben verwenden sie, um die Idempotenz, die Absorption und die Assoziativität, einfache Normalformen und Ableitungen zu gewinnen, die De Morgan mit der Kontraposition verbinden.

Lernziele

  1. Die Identität von Zeichenketten, die erlaubt, eine Abkürzung an jeder Stelle durch ihre Auflösung zu ersetzen, von der beweisbaren Äquivalenz unterscheiden, die das Ersetzen innerhalb einer Formel nur mit der Ersetzung äquivalenter Formeln erlaubt, und Äquivalenzen in einer Ableitung verketten.
  2. Die beiden De-Morgan-Gesetze und ihre Varianten, einschließlich der Negation einer Implikation, durch Ableitung beweisen und in ihnen die Rolle der Regel der Ersetzung der doppelten Negation erkennen.
  3. Die Distributivität der Konjunktion über die Disjunktion und der Disjunktion über die Konjunktion in beiden Richtungen beweisen und dabei in jedem Fall die passende Fallunterscheidung wählen.
  4. Formeln mit einer Schritt für Schritt begründeten Kette von Äquivalenzen in einfache Normalformen umformen und die Gesetze der Idempotenz, der Absorption und der Assoziativität durch Ableitung gewinnen.
  5. Ableitungen mit Prämissen konstruieren, die die De-Morgan-Gesetze mit der Kontraposition und mit den Einführungs- und Eliminationsregeln der Junktoren verbinden.

Die vorigen Lektionen dieser Einheit haben, eine auf der anderen, die Werkzeuge der Deduktion aufgebaut: das Axiomensystem und den Modus ponens, die vier grundlegenden Techniken und die Ersetzung der doppelten Negation, die Symmetrien der Junktoren und die Techniken der klassischen Logik. Diese Lektion fügt keine neue Regel hinzu; sie lässt sie zusammenarbeiten. Wenn dem so ist, liegt ihr Reiz nicht so sehr in den Aussagen, die man vielleicht aus anderen Kursen kennt, als in der Art, sie zu gewinnen: Jede Zeile muss durch ein Axiom, eine Prämisse, eine Definition, eine der beiden primitiven Regeln oder ein bereits bewiesenes Ergebnis begründet werden, und keine darf sich auf das stützen, was „offensichtlich scheint“.

Was verwendet wird und wie es sich verkettet

Aus der Lektion über formale Deduktionssysteme werden die Axiome A1, A2 und A3 von Łukasiewicz übernommen, der Modus ponens (MP), auch mit Prämissen, die Reflexivität (Refl: wenn φ∈Γ\varphi \in \Gamma, dann Γ⊢φ\Gamma \vdash \varphi), die Monotonie (Mon), der Schnitt (Schnitt: wenn Γ⊢φi\Gamma \vdash \varphi_i für jedes ii und Γ∪{φ1,…,φn}⊢ψ\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi, dann Γ⊢ψ\Gamma \vdash \psi), das Deduktionstheorem (DT) und die beweisbare Äquivalenz (φ⊣⊢ψ\varphi \dashv\vdash \psi, wenn {φ}⊢ψ\{\varphi\} \vdash \psi und {ψ}⊢φ\{\psi\} \vdash \varphi), mit ihren Eigenschaften: Sie ist reflexiv, symmetrisch und transitiv, und wenn φ⊣⊢ψ\varphi \dashv\vdash \psi, dann gilt Γ⊢φ\Gamma \vdash \varphi genau dann, wenn Γ⊢ψ\Gamma \vdash \psi. Aus der Lektion über die vier Ableitungstechniken die doppelte Negation (DN: φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi), die Kontraposition (KP), insbesondere (φ→ψ)⊣⊢(¬ψ→¬φ)(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi), und die zweite primitive Regel des Kalküls des Kurses, die Ersetzung der doppelten Negation (EDN), mit der das Deduktionstheorem weiterhin gilt: Entsteht χ′\chi' aus χ\chi, indem ein Vorkommen einer Teilformel θ\theta durch ¬¬θ\neg\neg\theta oder eines von ¬¬θ\neg\neg\theta durch θ\theta ersetzt wird, so schließt man aus χ\chi auf χ′\chi'; die so aus der Zeile ii gewonnene Zeile wird mit EDN(i)(i) begründet. Zu ihren unmittelbaren Folgerungen gehören (φ↓ψ)⊣⊢(¬¬φ↓ψ)(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi), (φ↓ψ)⊣⊢(φ↓¬¬ψ)(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi) und allgemein χ⊣⊢χ′\chi \dashv\vdash \chi', wenn χ′\chi' durch EDN aus χ\chi entsteht; daraus folgt, dass EDN(i)(i) auch auf eine Zeile der Form χ⊣⊢φ\chi \dashv\vdash \varphi anwendbar ist, um eine doppelte Negation in φ\varphi zu ändern. Aus der Lektion über die Symmetrien der Junktoren die Ersetzung äquivalenter Formeln (Ers) und die Symmetrien (Sym), darunter (φ∨ψ)⊣⊢(ψ∨φ)(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi) und (φ∧ψ)⊣⊢(ψ∧φ)(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi).

Aus der Lektion über die Techniken der klassischen Logik werden, alle mit einer Menge Γ\Gamma von Prämissen, die folgenden Regeln übernommen. Die Disjunktionseinführung (∨\veeI): Wenn Γ⊢φ\Gamma \vdash \varphi, dann Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) und Γ⊢(ψ∨φ)\Gamma \vdash (\psi \vee \varphi). Die Disjunktionselimination (∨\veeE, disjunktiver Syllogismus): Wenn Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) und Γ⊢¬φ\Gamma \vdash \neg\varphi, dann Γ⊢ψ\Gamma \vdash \psi. Die Konjunktionseinführung (∧\wedgeI): Wenn Γ⊢φ\Gamma \vdash \varphi und Γ⊢ψ\Gamma \vdash \psi, dann Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi). Die Konjunktionselimination (∧\wedgeE): Wenn Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi), dann Γ⊢φ\Gamma \vdash \varphi und Γ⊢ψ\Gamma \vdash \psi. Das Tertium non datur (TND): ⊢(φ∨¬φ)\vdash (\varphi \vee \neg\varphi). Und die Fallunterscheidung (FU) in ihren beiden Formen: Wenn Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi und Γ∪{¬φ}⊢χ\Gamma \cup \{\neg\varphi\} \vdash \chi, dann Γ⊢χ\Gamma \vdash \chi; und wenn Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi, Γ∪{ψ}⊢χ\Gamma \cup \{\psi\} \vdash \chi und Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi), dann Γ⊢χ\Gamma \vdash \chi. In den Ableitungen wird die erste Form mit zwei Zeilen zitiert, FU(i,j)(i, j), und die zweite mit dreien, FU(i,j,k)(i, j, k), in der Reihenfolge, in der sie im Satz stehen: die beiden Fälle und am Ende die Disjunktion. Jene Lektion erinnert außerdem daran, dass jede bereits bewiesene Regel innerhalb eines Kontexts Γ\Gamma gilt, und so werden hier die doppelte Negation und die Kontraposition verwendet.

Namen einer Zeichenkette und äquivalente Formeln

Man erinnere sich aus der Lektion über die Sprache der Aussagenlogik daran, dass die Junktoren außer ↓\downarrow Abkürzungen mit einer offiziellen und eindeutigen Definition sind: ¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi), (φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi), (φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi), (φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi), (φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi)) und (φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi). Eine Definition behauptet nichts über die Formeln: Sie gibt einer Zeichenkette, die es schon gab, einen zweiten Namen. Daraus folgt: Bezeichnen zwei Ausdrücke dieselbe Zeichenkette, so kann der eine an jeder Stelle für den anderen gesetzt werden, auch innerhalb einer größeren Formel, denn was geschrieben wird, ist dieselbe Folge von Kreisen und Scheiben. So sind ¬(φ∧ψ)\neg(\varphi \wedge \psi) und ¬¬(¬φ∨¬ψ)\neg\neg(\neg\varphi \vee \neg\psi) dieselbe Zeichenkette: Die zweite entsteht, indem man innerhalb der ersten die Auflösung der Konjunktion schreibt. In den Ableitungen wird dieser Namenswechsel mit „Def“ begründet, gefolgt von dem Junktor, der aufgelöst oder eingeführt wird.

Nun ist eine beweisbare Äquivalenz keine Identität. Dass φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi gilt, bedeutet, dass jede der beiden Formeln aus der anderen abgeleitet wird, nicht, dass sie dieselbe Zeichenkette sind: ¬¬φ\neg\neg\varphi ist viel länger als φ\varphi. Daher berechtigt das Wissen, dass φ⊣⊢φ′\varphi \dashv\vdash \varphi', nicht ohne Weiteres dazu, innerhalb einer größeren Formel φ′\varphi' an die Stelle von φ\varphi zu schreiben. Ebenso wenig berechtigt es dazu, „beide Seiten zu negieren“: Dass aus φ⊣⊢φ′\varphi \dashv\vdash \varphi' die Äquivalenz ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' folgt, ist ein Satz, die Ersetzung äquivalenter Formeln, deren Beweis die Kontraposition verwendet, und keine offensichtliche Operation. Es gibt einen einzigen Fall, in dem das System die Ersetzung direkt erlaubt, an jeder Stelle einer Formel: den von θ\theta durch ¬¬θ\neg\neg\theta oder umgekehrt, und das ist die Regel EDN; und die Lektion über Deduktionssysteme hat mit der Markierung gezeigt, dass nicht einmal dieser Fall aus den Axiomen und dem Modus ponens ableitbar ist, sodass er postuliert werden musste. Diese Sorgfalt ist keine Pedanterie; sie ist es, die einen Beweis von einer Symbolmanipulation unterscheidet, die, auf andere Junktoren oder in anderen Systemen angewandt, zu Falschem führen könnte.

Zwei Ergebnisse legen genau fest, was erlaubt ist. Das erste ist die Proposition über die Eigenschaften der beweisbaren Äquivalenz aus der Lektion über formale Deduktionssysteme: Wenn Γ⊢φ\Gamma \vdash \varphi und φ⊣⊢φ′\varphi \dashv\vdash \varphi', dann Γ⊢φ′\Gamma \vdash \varphi', sodass eine beweisbare Äquivalenz auf die ganze Formel einer Zeile angewandt werden kann; und die beweisbare Äquivalenz ist reflexiv, symmetrisch und transitiv, sodass sich Äquivalenzen verketten lassen (wenn χ⊣⊢φ\chi \dashv\vdash \varphi und φ⊣⊢φ′\varphi \dashv\vdash \varphi', dann χ⊣⊢φ′\chi \dashv\vdash \varphi') und zwei Ausdrücke, die dieselbe Zeichenkette bezeichnen, wegen der Reflexivität beweisbar äquivalent sind. Das zweite, das folgende Lemma, fasst, damit man sie bequem zitieren kann, die Erweiterung der Ersetzung äquivalenter Formeln auf die Disjunktion und die Konjunktion zusammen, die die Lektion über die Symmetrien für die Negation, die Implikation und den Peirce-Pfeil beweist und in einer ihrer gelösten Aufgaben auf diese beiden Junktoren ausdehnt.

LemmaErsetzung in der Disjunktion und in der Konjunktion

Wenn φ⊣⊢φ′\varphi \dashv\vdash \varphi', dann gilt für jede Formel ψ\psi: (φ∨ψ)⊣⊢(φ′∨ψ)(\varphi \vee \psi) \dashv\vdash (\varphi' \vee \psi), (ψ∨φ)⊣⊢(ψ∨φ′)(\psi \vee \varphi) \dashv\vdash (\psi \vee \varphi'), (φ∧ψ)⊣⊢(φ′∧ψ)(\varphi \wedge \psi) \dashv\vdash (\varphi' \wedge \psi) und (ψ∧φ)⊣⊢(ψ∧φ′)(\psi \wedge \varphi) \dashv\vdash (\psi \wedge \varphi').

Beweis

  1. (φ∨ψ)=¬(φ↓ψ)(\varphi \vee \psi) = \neg\resaltar{(\varphi \downarrow \psi)}

    Die Disjunktion ist nach Definition die Negation eines Peirce-Pfeils.

  2. (φ↓ψ)⊣⊢(φ′↓ψ)\dato{int}{(\varphi \downarrow \psi) \dashv\vdash (\varphi' \downarrow \psi)}

    Die Ersetzung äquivalenter Formeln für den Peirce-Pfeil liefert die Äquivalenz der inneren Schicht.

  3. (φ∨ψ)⊣⊢(φ′∨ψ)\dato{disy}{\resaltar{(\varphi \vee \psi)} \dashv\vdash \resaltar{(\varphi' \vee \psi)}}

    Die Ersetzung äquivalenter Formeln für die Negation trägt sie in die äußere Schicht, ¬(φ↓ψ)⊣⊢¬(φ′↓ψ)\neg(\varphi \downarrow \psi) \dashv\vdash \neg(\varphi' \downarrow \psi), und das ist die Disjunktion. Ebenso erhält man mit (ψ↓φ)⊣⊢(ψ↓φ′)(\psi \downarrow \varphi) \dashv\vdash (\psi \downarrow \varphi') die Ersetzung rechts.

  4. (φ∧ψ)=¬(¬φ∨¬ψ),¬φ⊣⊢¬φ′(\varphi \wedge \psi) = \neg(\resaltar{\neg\varphi} \vee \neg\psi), \qquad \neg\varphi \dashv\vdash \neg\varphi'

    Die Konjunktion ist die Negation einer Disjunktion von Negationen. Die Ersetzung für die Negation liefert zuerst ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi'.

  5. ¬(¬φ∨¬ψ)⊣⊢¬(¬φ′∨¬ψ),(φ∧ψ)⊣⊢(φ′∧ψ)\neg(\neg\varphi \vee \neg\psi) \dashv\vdash \neg(\neg\varphi' \vee \neg\psi), \qquad \resaltar{(\varphi \wedge \psi)} \dashv\vdash \resaltar{(\varphi' \wedge \psi)}

    Der für die Disjunktion bereits bewiesene Teil, auf ¬φ\neg\varphi und ¬φ′\neg\varphi' angewandt, liefert (¬φ∨¬ψ)⊣⊢(¬φ′∨¬ψ)(\neg\varphi \vee \neg\psi) \dashv\vdash (\neg\varphi' \vee \neg\psi), und wiederum trägt die Ersetzung für die Negation die Äquivalenz zur Konjunktion; rechts schließt man ebenso.

Im Folgenden bezeichnet „Ers“ die Ersetzung äquivalenter Formeln in jeder ihrer Formen, auch in denen dieses Lemmas, und sie kann mehrmals hintereinander angewandt werden, Schicht für Schicht, um eine Teilformel in beliebiger Tiefe zu erreichen. Wird eine Zeile aus der Zeile ii gewonnen, indem man eine bereits bewiesene Äquivalenz anwendet, sei es auf die ganze Formel, sei es mit Ers auf einen ihrer Teile, so wird sie mit dem Namen dieser Äquivalenz und der Nummer der Zeile begründet: DN(i)(i), „Ers, DM(i)(i)“. Ein Namenswechsel, der keine Äquivalenz anwendet, sondern dieselbe Zeichenkette neu schreibt, wird ebenso begründet, mit Def, gefolgt von dem Junktor, der aufgelöst oder eingeführt wird: Def ∧\wedge (i)(i). Die Proposition der Lektion über formale Deduktionssysteme gewährleistet, dass solche Zeilen begründet sind, ob die Zeile ii nun Γ⊢φ\Gamma \vdash \varphi behauptet oder eine Äquivalenz χ⊣⊢φ\chi \dashv\vdash \varphi, die fortgesetzt wird.