Logik

Grund- und Aufbaukurs in Aussagen- und Prädikatenlogik

Gerhard Schurz

• Publisher: De Gruyter
• Year: 2018
• eBook ISBN: 9783110590685
• Edition: 1
• Topic: Philosophy
• Subtopic: Logic in Philosophy

Diese Einführung in die Logik umfaßt einen Grundkurs und einen Aufbaukurs.

Der Grundkurs ist voraussetzungsfrei geschrieben und führt in die Semantik und Beweistheorie der Aussagenlogik und elementaren Prädikatenlogik ein, eingebettet in die allgemeine Theorie des rationalen Schließens. Logische Zusammenhänge werden in Verbindung mit sorgfältig ausgewählten Übungsbeispielen – inklusive Lösungen – einsichtig gemacht. Auf die philosophische Anwendung der Logik in der logischen Rekonstruktion natursprachlicher Texte und Argumente liegt besonderes Augenmerk. Zusammenhänge zwischen alternativen logischen Notationen und Techniken, die anfangs oft Schwierigkeiten bereiten, werden sorgfältig erklärt.

Der anschließende Aufbaukurs schlägt die Brücke zwischen einer philosophischen Logikeinführung und dem fortgeschrittenen Niveau moderner formaler Logik. Nach einer gründlichen Einführung in die volle Prädikatenlogik und ihrer mengentheoretischen Semantik wendet sich der Band metalogischen Methoden zu. Prominente Resultate zur Korrektheit und Vollständigkeit der Prädikatenlogik, zur Entscheidbarkeit der monadischen und Unentscheidbarkeit der vollen Prädikatenlogik sowie zur Unvollständigkeit der Arithmetik 1. Stufe werden Schritt um Schritt erklärt.

Abgerundet wird der Band durch zahlreiche Exkurse zur philosophischen Vertiefung logischer Grundlagenfragen. Zahlreiche Übungsbeispiele mit Lösungen zum Download vertiefen den Stoff. Die Lösungen werden ab Oktober 2018 verfügbar sein.

Teil II:Aufbaukurs in Prädikatenlogik und Metalogik

Sektion C: Fortgeschrittene Prädikatenlogik (inklusive Aussagenlogik)

13Äquivalenzumformungen in der Aussagen- und Prädikatenlogik

Zwei Aussagen (der AL oder PL) sind logisch äquivalent, oder kurz L-äquivalent, wenn ⊨ A↔B gilt. Zwei L-äquivalente Aussagen haben genau dieselben logischen Konsequenzen. Wir schreiben Cn(A) für die Menge der logischen Konsequenzen einer Aussage A („Cn“ für „consequences“). Oder in mengentheoretischer Schreibweise (Kap. 18): Cn(A) = {B: A ⊨ B}. Offenbar gilt:

⊨ A ↔ B g.d.w. Cn(A) = Cn(B).

Man bezeichnet „Cn(A)“ auch als den logischen Gehalt, kurz den Gehalt, von A. L-äquivalente Aussagen haben denselben Gehalt. Man sagt auch, sie drücken dieselbe Proposition aus, wobei man die von A ausgedrückte Proposition oft mit der Menge aller mit A L-äquivalenten Aussagen identifiziert.

Logisch äquivalente Umformungen sind eine zweite wichtige logische Beweismethode. Im Kalkül „Ä“ (für äquivalente Umformungen) fungiert das logische Symbol ↔ nicht als definiertes, sondern als primitives Symbol. Man kann in diesem Kalkül gegebene Aussagen in andere L-äquivalente Ausagen umformen, insbesondere in maximal einfache Aussagen, sogenannte Normalformen. Letztlich ist der Kalkül Ä sogar gleich stark wie der Kalkül S, denn man kann darin eine Aussage A als L-wahr beweisen, indem man die L-Äquivalenz ⊢ A ↔ p∨¬p beweist. (Analog für Schlüsse unter Anwendung des Deduktionstheorems.)

Wir erläutern den Kalkül Ä zunächst für die AL und dann für die PL.

13.1Der aussagenlogische Äquivalenzkalkül Ä

Dem aussagenlogischen Äquivalenzkalkül liegen folgende L-wahre Basisäquivalenzen zugrunde (beachte: ↔ bindet schwächer als die anderen Junktoren):

Basisaxiome des AL-Äquivalenzkalküls Ä0:

(DN)	A ↔ ¬¬A	Doppelte Negation
(Komm∧)	(A ∧ B) ↔ (B ∧ A)	Kommutativität von ∧
(Komm∨)	(A ∨ B) ↔ (B ∨ A)	Kommutativität von ∨
(Ass∧)	(A ∧ (B ∧ C)) ↔ ((A ∧ B) ∧ C)	Assoziativität von ∧
(Ass∨)	(A ∨ (B ∨ C)) ↔ ((A ∨ B) ∨ C)	Assoziativität von ∨
(Idem∧)	A ↔ (A ∧ A)	Idempotenz von ∧
(Idem∨)	A ↔ (A ∨ A)	Idempotenz von ∨
(Distr∧∨)	(A ∧ (B ∨ C)) ↔ ((A ∧ B) ∨ (A ∧ C))	∧-∨-Distributivität
(Distr∨∧)	(A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C))	∨-∧-Distributivität
(DM∧)	¬(A ∧ B) ↔ (¬A ∨ ¬B)	De Morgan ∧
(DM∨)	¬(A ∨ B) ↔ (¬A ∧ ¬B)	De Morgan ∨
(Def→)	(A → B) ↔ (¬A ∨ B)	Bedeutung von →
(Def↔)	(A ↔ B) ↔ ((A → B) ∧ (B → A))	Bedeutung von ↔
(ÜbTaut)	A ∧ (B ∨ ¬B) ↔ A	Überflüssige Tautologie
(ÜbKont)	A ∨ (B ∧ ¬B) ↔ A	Überflüssige Kontradiktion
(Taut)	A ∨ (B ∨ ¬B) ↔ (C ∨ ¬C)	Tautologie
(Kont)	A ∧ (B ∧ ¬B) ↔ (C ∧ ¬C)	Kontradiktion
(Abs∧)	A ∧ (A ∨ B) ↔ A	∧-Absorption
(Abs∨)	A ∨ (A ∧ B) ↔ A	∨-Absorption

Die im Folgenden aufgelisteten Äquivalenzen für n-stellige Operationen (Abschn. 7.2) gewinnt man durch Iteration der Basisaxiome. Da man hierfür viele Schritte benötigt, nehmen wir sie dennoch zu den Basisäquivalenzen des Kaküls Ä hinzu:

Ableitbare Äquivalenzen für n-stellige Konjunktionen/Disjunktionen (gehören zu Ä):

(GAss)	$\left({\text{A}}_{\text{1}}{}_{\wedge }^{\vee }{\left(\mathrm{...}\right)}_{\wedge }^{\vee }{\text{A}}_{\text{n}}\right)\left[\text{beliebige}\text{2er-Klammerung}\right]\leftrightarrow {\text{A}}_{\text{1}}{}_{\wedge }^{\vee }{\mathrm{...}}_{\wedge }^{\vee }{\text{A}}_{\text{n}}$
(GKomm)	${\text{A}}_{{\text{i}}_{\text{1}}}{}_{\wedge }^{\vee }{\mathrm{...}}_{\wedge }^{\vee }{\text{A}}_{{\text{i}}_{\text{n}}}\left[\text{beliebige}\text{Indizesreihenfolge}\right]\leftrightarrow {\text{A}}_{\text{1}}{}_{\wedge }^{\vee }{\mathrm{...}}_{\wedge }^{\vee }{\text{A}}_{\text{n}}$
(GÜbTaut)	A ∧ (C1∨B∨C2∨¬B∨C3) ↔ A	(C1,C2,C3 können auch fehlen)
(GÜbKont)	A ∨ (C1∧B∧C2∧¬B∧C3) ↔ A	"
(GTaut)	(A1∨B∨A2∨¬B∨A3) ↔ C∨¬C	(A1,A2,A3 können auch fehlen)
(GKont)	(A1∧B∧A2∧¬B∧A3) ↔ C∧¬C	"
(GAbs∧)	A∧B∧(A∨C) ↔ A∧B
(GAbs∨)	A∨B∨(A∧C) ↔ A∨B
(GIdem)	${\text{A}}_{\wedge }^{\vee }{\mathrm{...}}_{\wedge }^{\vee }\text{A}\leftrightarrow \text{A}$
(GDistr∧∨)	(A1∨…∨Am) ∧ (B1∨…∨Bn) ↔ (A1∧B1) ∨ (A1∧B2) ∨…∨ (Am∧Bn) (m⋅n Disjunkte)
(GDistr∨∧)	(A1∧…∧Am) ∨ (B1∧…∧Bn) ↔ (A1∨B1) ∧ (A1∨B2) ∧ … ∧ (Am∨Bn) (m⋅n Konjunkte)
(GDM∧)	¬(A1∧…∧An) ↔ (¬A1∨…∨¬An)
(GDM∨)	¬(A1∨…∨An) ↔ (¬A1∧…∧¬An)

Die Grundidee von Äquivalenzbeweisen ist einfach: man kann jede Formel A in eine gewünschte L-äquivalente andere Form umformen, indem man sukzessive geeignete Teilformeln von A durch L-äquivalente Teilformeln ersetzt. Die Grundlage hierfür bildet die logische Ersetzungsregel.

Definition 13-1. Logische Ersetzungsregel:

Notation: Wenn B eine Teilformel von A ist, dann bezeichnet A[C/B] – lies: A mit C anstelle von B – eine Formel, die aus der Ersetzung von einigen oder allen Vorkommnisse von B durch C in A resultiert.

Beachte: Im Gegensatz zur Substitutionsnotation „A[t/x]“ erlaubt die Ersetzungsnotation „A[C/B]“ auch die Ersetzung von nur einigen B-Vorkommnissen. Somit hat „A[C/B]“ variable Referenz; die Regel (EL) gilt für alle Ersetzungsmöglichkeiten.

Logische Ersetzungsregel (EL) (auch „Regel der Ersetzung von Äquivalenten“):

Semantische Version: Wenn ⊨ B ↔ C, dann ⊨ A ↔ A[C/B].

Syntaktische Version: Wenn ⊢ B ↔ C, dann ⊢ A ↔ A[C/B].

Die logische Ersetzungsregel ist semantisch korrekt. Der Korrektheitsbeweis basiert auf einer ‚metalogischen Induktion nach der Komplexität von A[C/B]‘ und wird in Kap. 19 nachgetragen.

Die Ersetzungsregel gilt auch in der logisch stärkeren prämissenrelativierten Form:

Prämissenrelativierte Ersetzungsregel (EP):

Semantische Version: Wenn Γ ⊨ B ↔ C, dann Γ ⊨ A ↔ A[C/B].

Synt...

Table of contents

• Cover
• Titelseite
• Impressum
• Vorwort
• Inhaltsverzeichnis
• Teil I: Grundkurs in Aussagenlogik und elementarer Prädikatenlogik
• Teil II: Aufbaukurs in Prädikatenlogik und Metalogik
• Literaturverzeichnis
• Symbol- und Abkürzungsverzeichnis
• Übersicht über Definitionen, Merksätze und Abbildungen
• Sachregister
• Personenregister