Upload
duongtram
View
220
Download
0
Embed Size (px)
Citation preview
Eine Einfuhrung in die klassische Logik
Grundzuge der Logik
Prof. Dr. Heinrich Wansing
Ruhr Universitat BochumInstitut fur Philosophie II
Vorlesung im Wintersemester 2014/2015
1 / 230
Eine Einfuhrung in die klassische Logik
Geschichte der Logik
Aristoteles (384 v. Chr. – 322 v. Chr.)
Die Aristotelische Logik ist eine Termlogik. Es wird angenommen, dass jederAussagesatz aus einem Subjekt(term) und einem Pradikat(term) besteht.Ein Satz ist bejahend, wenn das Pradikat dem Subjekt zugesprochen wird,verneinend, wenn es dem Subjekt abgesprochen wird. Ein Satz ist daruber hinausallgemein oder partikular.
Aristoteles unternahm eine systematische Erforschung von Prinzipien des logischen
Schlussfolgerns und untersuchte so genannte Syllogismen, Schlussfolgerungen, die
aus genau zwei Annahmen und einer Konklusion bestehen.
2 / 230
Eine Einfuhrung in die klassische Logik
Euklid (360 v. Chr. – ca. 280 v. Chr.)
Euklid wendete die so genannte axiomatische Methode des logischenSchließens auf die Geometrie an.
3 / 230
Eine Einfuhrung in die klassische Logik
Gottfried Wilhelm Leibniz (1646 – 1716)
Leibniz formulierte als erster das Ziel einer universellen formalen Sprache(characteristica universalis) und eines Kalkuls zur Herleitung aller wahrenAussagen.
Das Leibnizsche Gesetz:
die Identitat ununterscheidbarer Dinge
die Ununterscheidbarkeit identischer Dinge
Verwendung des Begriffs der moglichen Welt.
4 / 230
Eine Einfuhrung in die klassische Logik
George Boole (1815 – 1864)
Boole legte die erste (publizierte) Formalisierung der Aussagenlogik alsAlgebra vor. (An Investigation of The Laws of Thought, 1854)
5 / 230
Eine Einfuhrung in die klassische Logik
Georg Cantor (1845 – 1918)
Cantor entwickelte die Mengenlehre, den Begriff der transfiniten Menge,das Diagonalverfahren, und formulierte die so genannteKontinuumshypothese, eine Hyopthese uber den moglichen Umfangunendlicher Mengen.Es gibt keine Menge, deren Machtigkeit zwischen der Machtigkeit dernaturlichen Zahlen und der Machtigkeit der reellen Zahlen (desKontinuums) liegt.
6 / 230
Eine Einfuhrung in die klassische Logik
Gottlob Frege (1848 – 1925)
Frege entwickelte eine Formalisierung der Pradikatenlogik mittels einergraphischen Notation (Begriffsschrift, 1879).
7 / 230
Eine Einfuhrung in die klassische Logik
Bertrand Russell (1872 – 1970)
Russell leitete eine Krise der Logik ein mit dem Russell-Paradox undentwickelte mit Alfred N. Whitehead die moderne Pradikatenlogik und dieso genannte Typentheorie (Principia Mathematica, 1910 – 1913).
8 / 230
Eine Einfuhrung in die klassische Logik
Kurt Godel (1906 – 1978)
Godel zeigte die Vollstandigkeit und damit die Widerspruchsfreiheit derPradikatenlogik (1930) und leitete ein Krise der Logik ein, indem er zeigte,dass (i) in der Peano Arithmetik nicht alle zahlentheoretischen Wahrheitenbewiesen werden konnen und (b) die Widerspruchsfreiheit der Arithmetiknicht innerhalb der Arithmetik beweisbar ist (1931).
9 / 230
Eine Einfuhrung in die klassische Logik
Gerhard Gentzen (1909 – 1945)
Gentzen entwickelte den Kalkul des naturlichen Schließens und denSeqenzenkalkul fur die Pradikatenlogik (1934).
10 / 230
Eine Einfuhrung in die klassische Logik
Alonzo Church (1903 – 1995)
Church entwickelte den Lambda-Kalkul, die Grundlage der funktionalenProgrammiersprachen, und zeigte die Unentscheidbarkeit derAllgemeingultigkeit pradikatenlogischer Formeln.
11 / 230
Eine Einfuhrung in die klassische Logik
Alfred Tarski (1901 – 1983)
Tarski entwickelte wesentlich die Modelltheorie. In der analytischenSprachphilosophie spielen sein Arbeiten zur Wahrheitstheorie ein wichtigeRolle, insbesondere seine so genannte T-Konvention (Der Wahrheitsbegriffin den formalisierten Sprachen, 1935).
12 / 230
Eine Einfuhrung in die klassische Logik
Saul Kripke (1940 – )
Kripke entwickelte u.a. die so genannte “mogliche Welten Semantik” furnicht-klassische Logiken.
13 / 230
Eine Einfuhrung in die klassische Logik
Nur Manner?
Helena Rasiowa (1917 – 1994) Larisa Maksimova (1943 – )
Siehehttp://loriweb.org/women-in-philosophy-of-logic-and-philosophical-logic/
14 / 230
Eine Einfuhrung in die klassische Logik
Was ist Logik?
Eine nicht unkontroverse Antwort:Die Logik ist die Theorie des korrekten Denkens.
Die korrekte, unkontroverse Antwort:Die Logik ist die Theorie der gultigen Schlussfolgerungen.
Die Frage, worum es in der Logik geht, zerfallt damit in zwei Teilfragen:
Was ist eine Schlussfolgerung?
Wann ist eine Schlussfolgerung gultig?
15 / 230
Eine Einfuhrung in die klassische Logik
Logik versus Logiken
Wird von Logiken (im Plural) oder einer Logik im Gegensatz zu der Logikgesprochen, dann sind in der Regel Logiksysteme gemeint. Ein logischesSystem ist aufgebaut aus
einer formalen Sprache,
einer Klasse von Situationen (Modellen, Strukturen), und
einem Beweissystem.
Eine Sprache umfasst eine Menge von Ausdrucken.Modelle sind Ausschnitte der Realitat oder Reprasentationen vonAusschnitten der Realitat, und ein Beweissystem ist eine Menge vonRegeln, deren input und output Ausdrucke oder Ansammlungen vonAusdrucken bestimmter Art sind.
Wird von der Logik (im Singular) gesprochen, dann ist die Disziplingemeint.
16 / 230
Eine Einfuhrung in die klassische Logik
Die Logik als interdisziplinare Theorie
'&$%
'
&
$
%
'&
$%
Logik PhilosophieMathematik
Informatik
Linguistik
Abbildung: Die Logik als Teilsdisziplin anderer Disziplinen.
17 / 230
Eine Einfuhrung in die klassische Logik
Teilgebiete der Logik, klassische Logik
Die Logik zerfallt in verschiedene Teilgebiete:
algebraische Logik
Mengenlehre
Rekursionstheorie
Modelltheorie
Beweistheorie.
Klassische versus nicht-klassische Logik.
In der klassischen Logik werden Annahmen zugrunde gelegt, die plausibelund unproblematisch sind fur Schlussfolgerungen in der ublichenMathematik und vielen anderen Bereichen der Wissenschaft. Zu diesenGrundannahmen gehort z.B. die Annahme, dass jeder Behauptungssatzentweder wahr oder falsch ist (aber nicht beides). In der nicht-klassischenLogik werden einige dieser Annahmen aufgegeben.
18 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
In der Aussagenlogik werden Schlussfolgerungen untersucht, die, wenn siegultig sind, gultig sind allein aufgrund der Bedeutung vonAussageverknupfungen.
Aussageverknupfungen (Junktoren) sind Ausdrucke, die Behauptungssatzemiteinander verbinden, wie:
“und”, “oder”, “falls”, “es ist nicht der Fall, dass”.
Die in der Aussagenlogik untersuchten Sprachen heißen aussagenlogischeSprachen. In diesen formalen Sprachen sind Satze, die keine Junktorenenthalten, intern nicht weiterstrukturiert. Die Satze ohne Junktoren bilden die kleinsten, atomarenBestandteile komplexer Satze, die unter Verwendung von Junktorenaufgebaut werden.
19 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
Die Betrachtung aussagenlogischer Sprachen ist dadurch gerechtfertigt,dass viele Schlussfolgerungen gultig sind ausschließlich aufgrund derBedeutung von Junktoren.
Es gibt Schlussfolgerungen, die, wenn sie gultig sind, nicht gultig sindallein aufgrund der Bedeutung von Junktoren, sondern auch aufgrund derBedeutung von Ausdrucken anderen syntaktischen Typs. Eine besonderswichtige Rolle spielen Ausdrucke, die in einem sehr allgemeinen Sinnequantitative Angaben machen, wie z.B. die Ausdrucke “alle”, “einige”,“keiner” usw. Derartige Ausdrucke heißen Quantoren.
20 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
Beispiele
Maria ist eine Professorin und Peter ist ein Student.Also: Peter ist ein Student.
Alle Studenten sind aufmerksam.Peter ist ein Student.Also: Peter ist aufmerksam.
21 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
Beispiele
Maria ist eine Professorin und Peter ist ein Musiker.Also: Peter ist ein Musiker.
Alle Studenten sind aufmerksam.Max ist ein Student.Also: Max ist aufmerksam.
22 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
Beispiele
Maria ist eine Professorin und Peter ist ein Musiker.Also: Peter ist ein Musiker.
Alle Studenten sind intelligent.Max ist ein Student.Also: Max ist intelligent.
23 / 230
Eine Einfuhrung in die klassische Logik
Aussagenlogik versus Pradikatenlogik
Die Sprachen der Pradikatenlogik sind formale Sprachen, in denen Satzeohne Junktoren eine interne Struktur besitzen. Neben Junktoren enthaltenpradikatenlogische Sprachen auch Quantoren, Namen fur Gegenstande(sogenannte Individuenkonstanten), und Ausdrucke die Eigenschaften vonoder Beziehungen zwischen Gegenstanden bezeichen (sogenanntePradikatsymbole).
Die Aussagenlogik kann daher als eine Teildisziplin der Pradikatenlogikverstanden werden. Die Bezeichnung “Pradikatenlogik” verdankt sich derVerwendung von Pradikatausdrucken. Pradikatsymbole werden haufig auchkurz “Pradikate” genannt.
24 / 230
Eine Einfuhrung in die klassische Logik
Abweichungen von der klassischen Logik
Das Gebiet der Logik kann aber auch auf andere Weise in Teildisziplinengegliedert werden. Einteilungskriterien bilden dabei Hinsichten, in denenlogische Systeme sich von der klassischen Logik unterscheiden.
Wir konnen differenzieren zwischen Erweiterungen, Modifikationen,Verallgemeinerungen und Teilsystemen der klassischen Logik.
25 / 230
Eine Einfuhrung in die klassische Logik
Erweiterungen:Modallogiken,Zeitlogiken,epistemische Logiken,Handlungslogiken,dynamische Logiken
6
?
� -klassische Aussagen- undPradikatenlogik
Teilsysteme:intuitionistische Logik,substrukturelle Logiken,intermediare Logiken
Modifikationen:mehrwertige Logiken,freie Logiken,parakonsistente Logiken
Verallgemeinerungen:hoherstufige Logiken,infinitare Logiken
Abbildung: Abweichungen von der klassischen Logik.
26 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
Eine Schlussfolgerung ist ein abstraktes Gebilde und besteht aus
(a) einer Menge von Annahmen (Pramissen) ∆(b) einem Ableitungszeichen(c) einer Konklusion A
(in linearer Notation: ∆/A)
27 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
Beispiele:
(1) {Peter lacht oder Marie lacht.Peter lacht nicht.}Marie lacht.
(2) Wenn Peter gewinnt, dann freut sich Marie.Wenn Marie sich freut, dann freut sich Hans.
Wenn Peter gewinnt, dann freut sich Hans.
(3) ∅Wenn Peter gewinnt, dann freut sich Hans.
“∅” ist eine Bezeichnung fur die leere Menge.
Pramissenmengen durfen unendlich oder auch leer sein. Die Anordnung derPramissen spielt keine Rolle.
28 / 230
Eine Einfuhrung in die klassische Logik
Gultige Schlussfolgerungen
Definition
Eine Schlussfolgerung ∆/A ist gultig (symbolisch: ∆ |= A) genau dann,wenn gilt: immer wenn alle Pramissen in ∆ wahr sind, dann ist auch dieKonklusion wahr.(Informelle Erklarung einer gultigen Schlussfolgerung)
Ein Gegenbeispiel fur ∆/A ist eine (mogliche) Situation, in der allePramissen in ∆ wahr sind (d.h., in der keine der Pramissen falsch ist), inder die Konklusion aber falsch ist.
Eine Schlussfolgerung ∆/A ist ungultig (symbolisch: ∆ 6|= A) genau dann,wenn ein Gegenbeispiel fur ∆/A existiert.
29 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
Beispiele:
(4) Bochum ist die Hauptstadt von Norwegen.Wenn Bochum die Hauptstadt von Norwegen ist, dann spieltMarie Piano.
Marie spielt Piano.
Gultige Schlussfolgerung.
(5) Bochum ist die Hauptstadt von Norwegen.Wenn Bochum die Hauptstadt von Norwegen ist, dann ist Parisdie Hauptstadt von Sachsen.
Paris ist die Hauptstadt von Sachsen.
Gultige Schlussfolgerung.
30 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
(6) Marie spielt Piano oder Peter spielt Piano.
Marie spielt Piano.
Ungultige Schlussfolgerung.Gegenbeispiel: Eine Situation, in der Marie nicht Piano spielt undPeter Piano spielt.Besser: Eine Situation, in der eine Person namens Marie nicht dasmacht, was als Piano Spielen bezeichnet wird, wahrend eine Personnamens Peter das macht, was als Piano Spielen bezeichnet wird.
(7) Wenn Peter Marie liebt, dann liebt Hans Sabine.
Wenn Peter Marie nicht liebt, dann liebt Hans Sabine nicht.
Ungultige Schlussfolgerung.Gegenbeispiel: Eine Situation, in der Peter Marie nicht liebt und HansSabine liebt.
31 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
(8) Alle F sind G .Alle H sind G .
Alle H sind F .
Ungultige Schlussfolgerung.Gegenbeispiel: Eine Situation, in der einige H keine F sind, aber jedesF und auch jedes H ein G ist.
(9) Jedes F ist ein G .Es gibt ein F .Einige G sind keine H.
Einige F sind H.
Ungultige Schlussfolgerung.Gegenbeispiel: Eine Situation, in der es ein F gibt, jedes F ein G ist,einige G keine H sind und in der es kein F gibt, das ein H ist.
32 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
(10) Alle F sind G .Alle G sind H.
Einige F sind H.
Ungultige Schlussfolgerung.Gegenbeispiel: Eine Situation, in der es kein F gibt, aber jedes G einH ist. In dieser Situation ist die erste Pramisse wahr, weil sie sovielbesagt wie “Es gibt kein F , das nicht ein G ist.”
33 / 230
Eine Einfuhrung in die klassische Logik
Schlussfolgerungen
Richard Feldman, Voluntary Belief and Epistemic Evaluation, in: M. Steup(ed.), Knowledge, Truth, and Duty, Oxford UP, 2001, p. 79:
The Voluntarism Argument
People do not have voluntary control over their beliefs.
If deontological judgements about beliefs are sometimes true, thenpeople have voluntary control over their beliefs.
Deontological judgements about beliefs are not sometimes true.
nicht p
wenn q, dann p
nicht q
34 / 230
Eine Einfuhrung in die klassische Logik
Situationen
Sind Pramissen und Konklusionen einfach nur wahr oder falsch odervielleicht immer nur wahr oder falsch in Situationen ?Was bedeutet es, dass eine Pramisse oder Konklusion wahr bzw. falsch istin einer Situation?Was ist eine Situation?
Wahrend Konklusionen und Pramissen abstrakte Entitaten sind, gibt essowohl abstrakte Situationen, als auch konkrete Situationen, die vonkonkreten, sinnlich wahrnehmbaren Gegenstanden in Raum und Zeit‘bevolkert’ werden.
35 / 230
Eine Einfuhrung in die klassische Logik
Situationen
Beispiele:
({Peter, Walter, Marie}, raucht, liebt, ist Ehemann von)
(N, <)
({Peter, Walter, Marie},f ), wobei f eine Funktion ist, die denvorhandenen Individuen ihren bevorzugten Tennispartner zuordnet,z.B. Peter 7→ Marie, Marie 7→ Peter, Walter 7→ Marie.
Bestanddteile der ersten Struktur sind nicht die Worter “raucht”, “liebt”und “ist Ehemann von”, sondern die Eigenschaft zu rauchen, dieBeziehung, die zwischen zwei Individuen besteht, wenn sie einander lieben,und die Beziehung, die zwischen zwei Individuen besteht, wenn das eineder Ehemann des anderen ist.
Der Satz “Zu jeder Zahl existiert eine kleinere” ist falsch in (N, <) aberwahr in (Z, <).
36 / 230
Eine Einfuhrung in die klassische Logik
Situationen
Definition
Ein aussagenlogisches Modell ist eine Funktion v , die jedem nicht weiterzerlegbaren Aussagesatz einer gegebenen Sprache genau einen der Werte“wahr” (W) oder “falsch”(F) zuordnet.
Wenn das Modell M ein aussagenlogisches Modell v ist, dann ist ein nichtweiter zerlegbarer Aussagesatz p wahr in M genau dann, wenn v(p) = W.Angenommen, Peter liebt Marie. Dieser Ausschnitt der Welt kannreprasentiert werden durch das Modell v , das dem Satz “Peter liebtMarie” den Wert W zuordnet. Der Satz wird in v als wahr interpretiert .
37 / 230
Eine Einfuhrung in die klassische Logik
Gultige Schlussfolgerungen
Definition
(Gultige Schlussfolgerung)Sei K eine nicht-leere Klasse von Modellen (fur die betrachtete Sprache).∆/A ist gultig bezuglich K genau dann, wenn fur jedes Modell M∈ Kgilt:Wenn jede Pramisse aus ∆ wahr ist in M, dann ist A wahr in M.
∆/A heißt logisch gultig (symbolisch ∆ |= A) genau dann, wenn ∆/Agultig ist bezuglich der Klasse aller Modelle (der betrachteten Sprache).
38 / 230
Eine Einfuhrung in die klassische Logik
Die Idee der realistischen, modelltheoretischen Semantik
Welt
Reprasentation (Modelle reprasentieren Ausschnitte der Welt)
Modelle
Interpretation (Sprachliche Ausdrucke werden in Modelleninterpretiert)
sprachliche Ausdrucke
39 / 230
Eine Einfuhrung in die klassische Logik
Interpretation durch Ubersetzung
Modelle
Interpretation (Sprachliche Ausdrucke werden in Modelleninterpretiert)
Ausdrucke einer formalen Sprache
Ubersetzung(Ausdrucke einer naturlichen Sprache werden inAudrucke einer formalen Sprache ubersetzt)
Ausdrucke einer naturlichen Sprache
40 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(i) Formale Sprachen sind besonders ubersichtlich. Sie konnen verwendetwerden, um die aussagen- und die pradikatenlogische Strukturkomplexer Behauptungssatze und damit auch komplexer Pramissenund Konklusionen deutlich zu machen.
Beispiele:
(11) Wenn Peter gewahlt wird, dann argert sich Sybilloder Max tritt zuruck, und wenn Max zurucktritt,dann freut sich Hans.Wenn Peter gewahlt wird, dann freut sich Hansoder Sybill argert sich.
41 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(12) Wenn Peru in den Anden liegt, dann argert sichSybill oder Max tritt zuruck, und wenn Maxzurucktritt, dann freut sich Hans.Wenn Peru in den Anden liegt, dann freut sichHans oder Sybill argert sich.
“Peter wird gewahlt.” 7→ p“Sybill argert sich.” 7→ s“Max tritt zuruck.” 7→ m“Hans freut sich.” 7→ h
Wenn p, dann s oder m, und wenn m, dann h.
Wenn p, dann h oder s.
42 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
“wenn ..., dann −−−” 7→ ⊃ (→)“...und−−−” 7→ ∧“...oder−−−” 7→ ∨
((p ⊃ (s ∨m)) ∧ (m ⊃ h))
(p ⊃ (h ∨ s))
Gultige Schlussfolgerung
43 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(ii.) Formale Sprachen sind syntaktisch (strukturell) eindeutig, naturlicheSprachen nicht.
Beispiele:
“Flying planes can be dangerous.” (N. Chomsky)Zwei Lesarten:(a) Fliegende Flugzeuge konnen gefahrlich sein.(b) Flugzeuge zu fliegen kann gefahrlich sein.
“die Kritik der reinen Vernunft” (I. Kant)Zwei Lesarten:(a) die Kritik, die von der reinen Vernunft geubt wird(b) die Kritik, die an der reinen Vernunft geubt wird
44 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(13) Wenn Arthur nicht weint und Sherry trinkt, dann ist er glucklich.
Es existieren drei Lesarten:
(a) Wenn Arthur nicht sowohl weint als auch Sherry trinkt,dann ist Arthur glucklich.
(b) Wenn Arthur nicht weint aber Sherry trinkt, dann istArthur glucklich.
(c) Wenn Arthur sowohl nicht weint als auch nicht Sherrytrinkt, dann ist Arthur glucklich.
45 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
Formalisierung liefert:
“Arthur weint.” 7→ w“Arthur trinkt Sherry.” 7→ s“Arthur ist glucklich.” 7→ g
“wenn ..., dann −−−” 7→ ⊃“... und−−−” 7→ ∧“nicht ...” 7→ ¬
(a)∗ (¬(w ∧ s) ⊃ g)(b)∗ ((¬w ∧ s) ⊃ g)(c)∗ ((¬w ∧ ¬s) ⊃ g)
46 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
Wird (13) gelesen als (b)∗ (((¬w ∧ s) ⊃ g)), dann ist die Schlussfolgerung
¬ws(13)
g
gultig (bezuglich der Klasse aller aussagenlogischen Modelle, d.h. allerZuordnungen von Wahrheitswerten zu den Symbolen “w”, “s”, und “g”).
Wird (13) aber verstanden als (c)∗ (((¬w ∧ ¬s) ⊃ g)), dann ist dieSchlussfolgerung ungultig.
47 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
Nota bene: Die Verwender naturlicher Sprachen sind nicht zursyntaktischen Mehrdeutigkeit verurteilt. Syntaktisch mehrdeutige Satzekonnen dadurch desambiguiert werden, dass mogliche Lesarten durchnaturlichsprachliche Formulierungen auseinander gehalten werden.
(iii) In formalen Sprachen wird von bestimmten syntaktischenPhanomenen naturlicher Sprachen abstrahiert, die fur die Gultigkeitoder Ungultigkeit von Schlussfolgerungen keine Rolle spielen.
Beispiel: Die Nebensatzstellung im Deutschen.
(iv) Durch die Verwendung einer formalen Sprache konnen wir uns aufbestimmte Aspekte der Bedeutung/Verwendung naturlichsprachlicherJunktoren (aber auch Quantoren) beschranken.
48 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
Z.B. sind naturlichsprachliche “und”-Verknupfungen nicht immerkommutativ: Die Satze
“Peter stiehlt 100.000 Euro und kommt ins Gefangnis.”
und
“Peter kommt ins Gefangnis und stiehlt 100.000 Euro.”
haben unterschiedliche Wahrheitsbedingungen, d.h. sind nicht in denselbenSituationen wahr oder falsch.
Wir werden festlegen, dass eine “und”-Verknupfung A ∧ B wahr ist ineinem Modell M genau dann, wenn A wahr ist in M und B wahr ist inM. Damit haben A ∧ B und B ∧ A dieselben Wahrheitsbedingungen.
Wir werden auch eine Normierung der Bedeutung des “wenn..., dann−−−”und des “...oder−−−” vornehmen.
49 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(v) Durch die Verwendung einer formalen Sprache konnen wir einenaturliche Sprache als sogenannte Metasprache gebrauchen, um uberdie formale Sprache als sogenannte Objektsprache zu sprechen.
Beispiel:
Amsterdam besteht aus neun Buchstaben.
“︸︷︷︸ Amsterdam︸ ︷︷ ︸ ” besteht aus neun Buchstaben.︸ ︷︷ ︸Metaspr. Objektsprache Metasprache
Wenn eine Sprache reichhaltig genug ist, Aussagen nicht nur uber ihreeigene Syntax, sondern auch uber die Bedeutung ihrer Ausducke zu bilden,fuhrt dies zu semantischen Paradoxien. Der Satz: “Dieser Satz ist falsch”z.B. ist falsch, wenn angenommen wird, dass er wahr ist, und er ist wahr,wenn angenommen wird, dass er falsch ist. Beides zusammen liefert einenWiderspruch.
50 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(vi) Die Sprache der Pradikatenlogik spielt die eine zentrale Rolle in densymbolischen Wissenschaften, z.B.
MathematikInformatikformale LinguistikKI (Kunstliche Intelligenzforschung)formale Philosophie
Wenn in diesen Wissenschaften eine Fragestellung eindeutig formuliertwerden soll, dann wird sie in der Regel unter Ruckgriff (u.a.) auf diesprachlichen Mittel der Pradkatenlogik formuliert.
Wie wir sehen werden, ist die Sprache der Pradikatenlogik eineSprachenfamilie, deren Mitglieder allerdings uber dasselbe Inventar anJunktoren und Quantoren verfugen und sich lediglich hinsichtlich desnicht-logischen, ‘deskriptiven’ Vokabulars unterscheiden.
51 / 230
Eine Einfuhrung in die klassische Logik
Wozu formale Sprachen?
(vii) Ausdrucke formaler Sprachen gehoren zu genau einem syntaktischenTyp.
Gegenbeispiel fur naturliche Sprachen:
“Peter spricht gelegentlich laut und deutlich.”
“Peter spricht gelegentlich laut und Peter spricht gelegentlich deutlich.”
(viii) Es existiert kein Beweissystem fur (komplette) naturliche Sprachen.
52 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von Beweissystemen
Ein Beweissystem ist eine Menge von schematischen Regeln, dieAbleitungsregeln genannt werden. Anwendungen vonAbleitungsregeln heißen Ableitungsschritte, und Ergebnisse der Anwendungvon Ableitungsregeln werden Ableitungen genannt. Jeder Ableitungentspricht eine Schlussfolgerung.
Beispiel:
Drei Ableitungsregeln, wobei A, B und C schematische Buchstaben furAussagesatze sind:
∅((A ⊃ B) ⊃ ((C ⊃ A) ⊃ (C ⊃ B)))
∅(B ⊃ (A ⊃ B))
A, (A ⊃ B)
B53 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von Beweissystemen
∅((A ⊃ B) ⊃ ((C ⊃ A) ⊃ (C ⊃ B)))
∅(B ⊃ (A ⊃ B))
A, (A ⊃ B)
B
In diesem Ableitungssystem ist ((C ⊃ B) ⊃ (C ⊃ (A ⊃ B))) aus der leerenMenge ableitbar:
∅ ∅(B ⊃ (A ⊃ B)) ((B ⊃ (A ⊃ B)) ⊃ ((C ⊃ B) ⊃ (C ⊃ (A ⊃ B))))
((C ⊃ B) ⊃ (C ⊃ (A ⊃ B)))
54 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von Beweissystemen
Bedingungen an Ableitungen in einem Beweissystem:
Jede Ableitung muss endlich sein.
Jeder Ableitungsschritt muss effektiv (in endlicher Zeit) aufKorrektheit hin uberprufbar sein, d.h., darauf hin, ob es sichtatsachlich um die Anwendung einer Ableitungsregel handelt.
Es muss moglich sein, die Pramissenmenge (den Ausgangspunkt derAbleitung) und die Konklusion (den Endpunkt) der Ableitung effektivfeststellen zu konnen.
Definition
Sei S ein Beweissystem. Die Ableitung ∆/A ist korrekt bezuglich S genaudann, wenn A in S aus ∆ ableitbar ist.
55 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von Beweissystemen
Definition
Sei K eine nicht-leere Klasse von Modellen. Ein Beweissystem S heißtkorrekt bezuglich K genau dann, wenn jede bezuglich S korrekteSchlussfolgerung gultig ist bezuglich K.
Definition
Sei K eine nicht-leere Klasse von Modellen. Ein Beweissystem S heißtvollstandig bezuglich K genau dann, wenn jede bezuglich K gultigeSchlussfolgerung korrekt ist bezuglich S .
56 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von Beweissystemen
Sei S ein bezuglich der (nicht-leeren) Modellklasse K korrektesBeweissystem. Dann gilt:
eine Ableitung von A aus ∆ in S zeigt, dass ∆/A gultig ist bezuglichK;
ein Gegenbeispiel zu ∆/A aus K zeigt, dass keine Ableitung von Aaus ∆ in S existiert.
Sei S bezuglich K vollstandig. Dann gilt:
fur jede bezuglich K gultige Schlussfolgerung ∆/A existiert eineAbleitung von A aus ∆ in S .
57 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Sprache
�����
QQQ
Alphabet Syntax Semantik
Definition
Das Alphabet der Sprache der klassischen Aussagenlogik besteht aus
abzahlbar unendlich vielen Aussagebuchstaben p0, p1, p2, . . . ,
den Junktoren genannten Symbolen ¬,∧,∨,⊃,≡,
den Hilfssymbolen “(”, “)”.
58 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Variationen dieser Sprache ergeben sich dadurch, dass andereAussagebuchstaben oder eine andere Menge von Junktoren verwendetwird.
Die Menge der aussagenlogischen Formeln ist unendlich und wird induktivdefiniert.
Eine induktive Definition besteht aus drei Teilen:
(1) einem Basisschritt, in dem bestimmte Dinge zu Objekten einergewunschten Sorte erklart werden,
(2) einem oder mehreren Aufbauschritten, die Konstruktionsprinzipienbeschreiben, um aus gegebenen Objekten weitere zu konstruieren,
(3) einer Abschlussbedingung, die besagt, dass alles was nicht inendlichen Schritten, mit Hilfe von (1) und (2) gebildet werden kann,kein Objekt der gewunschten Art ist.
59 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Definition
Die Menge der aussagenlogischen Formeln ist wie folgt induktiv definiert:
Jeder Aussagebuchstabe ist eine Formel.
Wenn A eine Formel ist, dann ist auch ¬A eine Formel.
Wenn A und B Formeln sind, dann sind auch (A ∧ B), (A ∨ B),(A ⊃ B), (A ≡ B) Formeln.
Nichts anderes ist eine Formel.
Wir verwenden Kleinbuchstaben p, q, r , s, t, u als Variablen furAussagenbuchstaben und Großbuchstaben A,B,C ,D,E ,F als Variablenfur Formeln.
60 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Aussagenlogische Formeln
Formel Aussprache Formelname syntaktischer Typ derAussagenverknupfung
¬A nicht A Negation einstelliger Junktor(A ∧ B) A und B Konjunktion zweistelliger Junktor(A ∨ B) A oder B Disjunktion zweistelliger Junktor(A ⊃ B) wenn A, dann B Implikation zweistelliger Junktor(A ≡ B) A genau dann,
wenn B Aquivalenz zweistelliger Junktor
Beispiele:¬p1, (p1 ∧ p2) und (p2 ⊃ ¬p0) sind Formeln.
61 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Welche der folgenden Symbole sind Formeln?
• (¬(p2 ⊃ p3)) keine aussagenlogische Formel
• (p1 ⊃ (p1 ⊃ p0)) Formel
• (p1 ∧ p1 ∨ p0)) keine Formel
• (⊃ p1 ∧ p4) keine Formel
• (p0 ∧ p0) ⊃ p1 keine Formel
Konvention:Außere Klammern von Formeln konnen weggelassen werden. Also ist z.B.auch A ∧ B eine Formel, falls A und B Formeln sind.
62 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
Elementbeziehung a ∈ X (a ist Element von Menge X )a 6∈ X (a ist nicht Element von X )
Mengenschreib- {a1, a2, a3, . . . , an} endliche Mengenweise {a ∈ X | a hat Eigenschaft E}
endliche und unendliche Mengendie Menge derjenigen Elemente vonX , die die Eigenschaft E haben
Teilmengen- X ⊆ Y (X ist Teilmenge von Y )beziehung X ⊆ Y genau dann, wenn jedes
Element von X auch Element von Y ist.
Schnittmengen- X ∩ Y (der Durchschnitt von X und Y )operation X ∩ Y = {a | a ∈ X und a ∈ Y }
63 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
Vereinigungs- X ∪ Y (die Vereinigung von X und Y )mengenoperation X ∪ Y = {a | a ∈ X oder a ∈ Y }
relatives X \ YKomplement {a ∈ X | a 6∈ Y }
Cartesisches X × YProdukt die Menge der geordneten Paare (a, b)
mit a ∈ X und b ∈ Y{(a, b) | a ∈ X , b ∈ Y }
n-faches X n
Cartesisches die Menge der n-FolgenProdukt von Elementen aus X
{(a1, . . . , an) | ai ∈ X , 1 ≤ i ≤ n}
64 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
Potenzmengen- P(X ) (Menge aller Teilmengen von X )operation P(X ) = {Y | Y ⊆ X}
immer: ∅ ∈ P(X ) und X ∈ P(X )
Beispiele:
{1, 2, 3} = {3, 1, 2}, N = {a ∈ Z | a > 0}N ⊆ Z. N ∪ Z = Z, N ∩Q = N{a ∈ N | a < 3} ∩ {a ∈ Z | a > −3} = {1, 2}N \ {a ∈ N | a ≥ 5} = {1, 2, 3, 4}{(1, 2, 3)} 6= {(3, 1, 2)}
Extensionale Mengenauffassung: die Mengen X und Y sind identischgenau dann, wenn sie dieselben Elemente haben, d.h., X = Y genau dann,wenn gilt: X ⊆ Y und Y ⊆ X .
65 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
Relationen R ⊆ X × YEine zweistellige Relation R zwischen (Elementen aus) Xund (Elementen aus) Y ist eine Teilmenge von X × Y ,d.h. eine Menge von Paaren, deren erste Komponenteein Element von X und deren zweite Komponente einElement von Y ist.R ⊆ X × X ist eine zweistellige Relation uber X .R ⊆ X n ist eine n-stellige Relation uber X .
Funktionen f ⊆ X × Y , wobeifur jedes a ∈ X genau ein b ∈ Y existiert mit (a, b) ∈ f .D.h., eine zweistellige Funktion f von X nach Y isteine zweistellige Relation zwischen X und Y , die einebestimmte Eigenschaft hat, namlich fur jedes a aus Xexistiert genau ein b aus Y mit (a, b) ∈ X × Y .
66 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
Wenn R ⊆ X × Y , dann heißt X der Vorbereich und Y der Nachbereichvon R. Wenn f eine Funktion von X nach Y ist, dann wird X als derDefinitionsbereich und Y als der Wertebereich von f bezeichnet.Funktionen konnen einige interessante und wichtige Eigenschaften haben.Eine Funktion f heißt injektiv (oder 1-1) genau dann, wenn voneinanderverschiedene Elemente des Definitionsbereichs auf voneinanderverschiedene Elemente des Wertebereichs abgebildet werden: Wenna, b ∈ X und a 6= b, dann gilt f (a) 6= f (b). Eine Funktion f heißt surjektiv(im Englischen “onto”) genau dann, wenn fur jedes Element b desWertebereichs ein Element a des Definitionsbereichs existiert, so dassb = f (a). Und schließlich heißt eine Funktion f bijektiv genau dann, wennf sowohl injektiv, als auch surjektiv ist.
67 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
�
�
�
�rrr
-
-
�����1
f
Die Funktion f ist surjektivaber nicht injektiv.
�
�
�
�rr
�
�
�
�rr -
PPPPPq
g
Die Funktion g ist injektivaber nicht surjektiv.
�
�
�
�rrr
68 / 230
Eine Einfuhrung in die klassische Logik
Einschub: Einige mengentheoretische Begriffe
�
�
�
�rrr
-
-
�����1
h
Die Funktion h ist wedersurjektiv noch injektiv.
�
�
�
�rrr
�
�
�
�rrr
-
PPPPPq�����1
h′
Die Funktion h′ ist bijektiv.
�
�
�
�rrr
69 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Definition
(Alternative Definition der Menge der aussagenlogischen Formeln) DieMenge der aussagenlogischen Formeln ist die kleinste Menge Γ, so dass
(1) jeder Aussagebuchstabe zu Γ gehort,
(2) wenn A ∈ Γ, dann ¬A ∈ Γ,
(3) wenn A und B ∈ Γ, dann auch (A ∧ B), (A ∨ B),(A ⊃ B), (A ≡ B) ∈ Γ.
Wozu ist die induktive Definition der Menge der aussagenlogischenFormeln gut?
70 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Behauptung
Sei E (A) eine Abkurzung fur “Formel A hat Eigenschaft E ”. Jede Formelhat die Eigenschaft E , genau dann, wenn
(i) jeder Aussagebuchstabe die Eigenschaft E hat,
(ii) wenn E (A), dann E (¬A),
(iii) wenn E (A) und E (B), dann E (A ∧ B), E (A ∨ B),E (A ⊃ B) und E (A ≡ B).
Beweis. Sei Form die Menge aller aussagenlogischen Formeln und sei∆ = {A ∈ Form | E (A)}. Dann ist offensichtlich ∆ ⊆ Form. Aber wenn (i),(ii) und (iii) erfullt sind, dann erfullt ∆ die Bedingungen (1), (2) und (3)in der alternativen Definition von Form. Da Form die kleinste Menge ist,die (1)–(3) erfullt, ist Form ⊆ ∆, und damit ∆ = Form. q.e.d.
71 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Behauptung
Jede aussagenlogische Formel hat eine gerade Anzahl von Klammern.
Beweis. Mit Induktion uber den Aufbau der Formel A.
Basisschritt:Sei A ein Aussagebuchstabe. Dann ist die Anzahl der Klammern von A gleich Nullund Null ist eine gerade Zahl.Aufbauschritte:Sei A eine Formel der Form ¬B und B habe eine gerade Anzahl von Klammern.Dann ist die Anzahl der Klammern von A gleich der Anzahl der Klammern von B,also gerade.Sei A eine Formel der Form (B ∧ C ) und B und C haben jeweils eine geradeAnzahl von Klammern (m und n). A hat dann 2 + m + n Klammern, also einegerade Anzahl von Klammern.
A = (B ∨ C ), A = (B ⊃ C ), A = (B ≡ C ): Analog. q.e.d.
72 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Aussagenlogik
Definition
Die Menge der Teilformeln TF (A) eineraussagenlogischen Formel A ist wie folgt induktiv definiert:
(i) TF (p) = {p} fur Aussagebuchstaben p;
(ii) TF (¬A) = TF (A) ∪ {¬A};(iii) TF (A # B) = TF (A) ∪ TF (B) ∪ {(A # B)},
mit # ∈ {∧,∨,⊃,≡}.
73 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
Semantische Grundannahmen der klassischen Aussagenlogik
Zweiwertigkeitsprinzip (Bivalenzprizip):Jede Formel hat genau einen der Wahrheitswerte (“wahr” oder“falsch”) in einem Modell.
(a) tertium non datur:Jede Formel hat mindestens einen der Wahrheitswerte (“wahr” oder“falsch”).
(b) Satz vom ausgeschlossenen Widerspruch:Jede Formel hat hochstens einen der Wahrheitswerte (“wahr” oder“falsch”).
Extensionalitatsprinzip (Kompositionalitatsprinzip):Der Wahrheitswert einer zusammengesetzten Formel hangt eindeutigund ausschießlich ab von den Wahrheitswerten der Teilformeln.
74 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
Definition
Sei v ein aussagenlogisches Modell. Der Wert einer Formel A unter derFunktion v (symbolisch V (A)) ist wie folgt induktiv definiert:
V (p) = v(p)
V (A ∧ B) =
{W falls V (A) = V (B) =WF sonst
V (A ∨ B) =
{F falls V (A) = V (B) = FW sonst
V (A ⊃ B) =
{F falls V (A) = W und V (B) = FW sonst
V (A ≡ B) =
{W falls V (A) = V (B)F sonst
V (¬A) =
{W falls V (A) = FF sonst
75 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
Definition
Eine aussagenlogische Formel A ist wahr in M (= v), (symbolischM |= A) genau dann, wenn V (A) = W . Dann heißt A auch wahr unterder Belegung v .
Wahrheitstabellen
A B (A ∧ B)
W W WW F FF W FF F F
Konjunktion
A B (A ∨ B)
W W WW F WF W WF F F
Disjunktion
76 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
A B (A ⊃ B)
W W WW F FF W WF F W
Implikation
A B (A ≡ B)
W W WW F FF W FF F W
Aquivalenz
A ¬A
W FF W
Negation
77 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
Wenn eine aussagenlogische Formel n verschiedene Aussagebuchstabenenthalt, dann hat die Wahrheitstabelle fur diese Formel 2n Zeilen.
Bemerkungen
Einschließendes “oder”:
Dieses Medikament hilft in Fallen von Kopfschmerz oderUnwohlsein.
Ausschließendes “oder”:
Die Begunstigung einer schweren Straftat kann mit Gefangnisbestraft werden oder mit einer Geldstrafe bis 10.000 EURO.
78 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
A B (A ⊃ B)
W W WW F FF W WF F W
Implikation:
Wenn es regnet, dann ist die Straße nass.
Wenn Berlin die Hauptstadt von Deutschland ist, dann liegt Berlin inEuropa.
Wenn Wasser nicht H2O ist, dann ist Wasser nicht H2O.
Wenn Wasser nicht H2O ist, dann ist Eisen kein Metall.
Wenn es regnet und gleichzeitig nicht regnet, dann ist Eisen keinMetall.
79 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
p ¬ (p ⊃ p)
W F WF F W
p q p ⊃ (q ⊃ p)
W W W WW F W WF W W FF F W W
p q (p ⊃ q) ≡ (¬q ⊃ ¬p)
W W W W F W FW F F W W F FF W W W F W WF F W W W W W
80 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Aussagenlogik
p q r (p ∧ q) ∨ ¬rW W W W W FW W F W W WW F W F F FW F F F W WF W W F F FF W F F W WF F W F F FF F F F W W
p q r ¬ (p ⊃ q) ⊃ r
W W W F W WW W F F W WW F W W F WW F F W F FF W W F W WF W F F W WF F W F W WF F F F W W
p q r (p ⊃ q) ⊃ ( (¬r ∨ p) ⊃ (r ⊃ q) )
W W W W W F W W WW W F W W W W W WW F W F W F W F FW F F F W W W W WF W W W W F F W WF W F W W W W W WF F W W W F F W FF F F W W W W W W
81 / 230
Eine Einfuhrung in die klassische Logik
Tautologien, Kontradiktionen und kontingente Formeln
Definition
Sei A eine aussagenlogische Formel. Ein aussagenlogisches Modell M(= v) heißt Modell von A genau dann, wenn A wahr ist in M, d.h. V (A)= W , symbolisch M |= A.
Definition
Eine aussagenlogische Formel A heißt allgemeingultig (oder tautologisch),wenn fur jedes aussagenlogisches Modell M gilt: M |= A.
Eine aussagenlogische Formel A heißt kontradiktorisch, wenn fur keinaussagenlogisches Modell M gilt: M |= A.
Eine aussagenlogische Formel A heißt kontingent (neutral, faktisch), wennA weder allgemeingultig noch kontradiktorisch ist.
82 / 230
Eine Einfuhrung in die klassische Logik
Logische Aquivalenz
Definition
Zwei aussagenlogische Formeln A und B heißen logisch aquivalent genaudann, wenn die Formel (A ≡ B) tautologisch ist.
Beispiele:
A und ¬¬A sind logisch aquivalent
A (A ≡ ¬ ¬A)W W W FF W F W
¬A und ¬¬A sind nicht logisch aquivalent
A (¬A ≡ ¬ ¬A)W F F W FF W F F W
83 / 230
Eine Einfuhrung in die klassische Logik
Logische Aquivalenz
A ⊃ B und ¬B ⊃ ¬A sind logisch aquivalent
A B (A ⊃ B) ≡ (¬B ⊃ ¬A)
W W W W F W FW F F W W F FF W W W F W WF F W W W W W
A ⊃ B und ¬A ∨ B sind logisch aquivalent
A B (A ⊃ B) ≡ (¬A ∨ B)
W W W W F W WW F F W F F FF W W W W W WF F W W W W F
84 / 230
Eine Einfuhrung in die klassische Logik
Logische Aquivalenz
Die folgenden Bikonditionale sind tautologisch:
DE MORGANsche Gesetze
¬(A ∧ B) ≡ (¬A ∨ ¬B)
¬(A ∨ B) ≡ (¬A ∧ ¬B)
Distributivgesetze
(A ∧ (B ∨ C )) ≡ ((A ∧ B) ∨ (A ∧ C ))
(A ∨ (B ∧ C )) ≡ ((A ∨ B) ∧ (A ∨ C ))
Assoziativgesetze
(A ∧ (B ∧ C )) ≡ ((A ∧ B) ∧ C )
(A ∨ (B ∨ C )) ≡ ((A ∨ B) ∨ C )
Kommutativgesetze
(A ∧ B) ≡ (B ∧ A)
(A ∨ B) ≡ (B ∨ A)
85 / 230
Eine Einfuhrung in die klassische Logik
Terminologie und Notation
Definition
Wenn die Implikation (A ⊃ B) wahr ist, dann heißt A hinreichendeBedingung fur B und B heißt notwendige Bedingung fur A.
Aufgrund der Assoziativgesetze, konnen wir verabreden,
(A1 ∧ (A2 ∧ . . . (An−1 ∧ An) . . .)) zu schreiben alsA1 ∧ . . . ∧ An und
(A1 ∨ (A2 ∨ . . . (An−1 ∨ An) . . .)) zu schreiben alsA1 ∨ . . . ∨ An
Falls n = 1, dann ist
A1 ∨ . . . ∨ An = A1 = A1 ∧ . . . ∧ An
86 / 230
Eine Einfuhrung in die klassische Logik
Disjunktive Normalform
Existiert zu jeder aussagenlogischen Formel A eine logisch aquivalenteFormel, die nur aus den Aussagebuchstaben aus TF (A), ¬, ∧ und ∨aufgebaut ist?
Definition
Eine aussagenlogische Formel A befindet sich in disjunktiver Normalformgenau dann, wenn A die folgende Gestalt hat: A1 ∨ . . . ∨ An, wobei jedesAi entweder (i) ein Aussagebuchstabe oder ein negierter Aussagebuchstabeist oder (ii) eine Konjunktion B1 ∧ · · · ∧ Bm von Aussagebuchstaben odernegierten Aussagebuchstaben ist.
Die folgenden Formeln befinden sich in disjunktiver Normalform:p1, ¬p2, (p1 ∨ p2), (p1 ∧ (¬p3 ∧ p4)), (¬p2 ∨ (p3 ∧ ¬p2))
Die folgende Formel befindet sich nicht in disj. Normalform:(p1 ∧ (¬p3 ∨ p4))
87 / 230
Eine Einfuhrung in die klassische Logik
Disjunktive Normalform
Definition
(Alternative Definition von “befindet sich in disjunktiver Normalform”)
Jeder Aussagebuchstabe ist eine Basiskonjunktion.
Jeder negierte Aussagebuchst. ist eine Basiskonjunktion.
Wenn A und B Basiskonjunktionen sind, dann ist auch (A ∧ B) eineBasiskonjunktion.
Nur was aufgrund der genannten Bedingungen eine Basiskonjunktion ist, isteine Basiskonjunktion.
Jede Basiskonjunktion befindet sich in disj. Normalform.
Wenn A und B sich in disj. Normalform befinden, dann befindet sich auch(A ∨ B) in disj. Normalform.
Nur was sich aufgrund der genannten Bedingungen in disj. Normalformbefindet, befindet sich in disj. Normalform.
88 / 230
Eine Einfuhrung in die klassische Logik
Disjunktive Normalform
Eine Basiskonjunktion A ist maximal in einer Formel B in disj. Normalformgenau dann, wenn gilt: A ist eine Teilformel von B aber keine Teilformeleiner anderen Basiskonjunktion in B.
Behauptung
Wenn A eine aussagenlogische Formel ist, dann existiert eine Formel A∗ indisjunktiver Normalform, so dass A und A∗ logisch aquivalent sind.
89 / 230
Eine Einfuhrung in die klassische Logik
Disjunktive Normalform
Beispiele:
p q r (p ≡ q) ⊃ rW W W W W ((p ∧ q) ∧ r) ∨W W F W FW F W F W ((p ∧ ¬q) ∧ r) ∨W F F F W ((p ∧ ¬q) ∧ ¬r) ∨F W W F W ((¬p ∧ q) ∧ r) ∨F W F F W ((¬p ∧ q) ∧ ¬r) ∨F F W W W ((¬p ∧ ¬q) ∧ r)F F F W F
90 / 230
Eine Einfuhrung in die klassische Logik
Disjunktive Normalform
Existiert zu jeder aussagenlogischen Formel A genau eine logischaquivalente Formel A∗ in disjunktiver Normalform?
p q (p ⊃ q) (¬p ∨ q) p qW W W (p ∧ q)∨ F W W WW F F F F W FF W W (¬p ∧ q)∨ W W F WF F W (¬p ∧ ¬q) W W F F
p q (p ∧ q) ∨ ((¬p ∧ q) ∨ (¬p ∧ ¬q))
W W W W F F FW F F F F F FF W F W W W FF F F W F W W
91 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Definition
Sei ∆ eine endliche Menge von Junktoren. ∆ heißt funktional vollstandiggenau dann, wenn jede aussagenlogische Formel A logisch aquivalent ist zueiner Formel B, die allein Junktoren aus ∆ enthalt.
Die Menge {¬,∧,∨,⊃,≡} ist funktional vollstandig, da sie alle Junktorenenthalt, die in der Definition der Menge der aussagenlogischen Formelnerwahnt werden.
92 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Folgende Formeln sind Tautologien:
1. (A ≡ B) ≡ ((A ⊃ B) ∧ (B ⊃ A))
2. (A ⊃ B) ≡ (¬A ∨ B)(A ≡ B) ≡ ((¬A ∨ B) ∧ (¬B ∨ A))
3. (A ∧ B) ≡ ¬(¬A ∨ ¬B)(A ≡ B) ≡ ¬(¬(¬A ∨ B) ∨ ¬(¬B ∨ A))
4. (A ∨ B) ≡ ¬(¬A ∧ ¬B)5. (A ⊃ B) ≡ ¬(A ∧ ¬B)
(A ≡ B) ≡ (¬(A ∧ ¬B) ∧ ¬(B ∧ ¬A))
6. (A ∧ B) ≡ ¬(A ⊃ ¬B)7. (A ∨ B) ≡ (¬A ⊃ B)
(A ≡ B) ≡ ((A ⊃ B) ∧ (B ⊃ A))≡ ¬((A ⊃ B) ⊃ ¬(B ⊃ A))
93 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Funktional vollstandig sind:
(a) {¬,∧,∨,⊃} wegen 1.
(b) {¬,∧,∨} wegen (a) und 2.
(c) {¬,∧,⊃} wegen (a) und 7.
(d) {¬,∧} wegen (c) und 5.
(e) {¬,∨} wegen (d) und 3.
(f) {¬,⊃} wegen (d) und 6. (oder wegen (e) und 7.)
(g) {¬,∨,⊃} wegen (f)
94 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Gibt es eine einelementige Junktorenmenge, die funktional vollstandig ist?
Wir wahlen (A NOR B) als Abkurzung fur (¬A ∧ ¬B). Die Menge { NOR }ist funktional vollstandig.
¬A ≡ (A NOR A)
(A ∧ B) ≡ ((A NOR A) NOR (B NOR B))
(A ∨ B) ≡ ((A NOR B) NOR (A NOR B))
(A ⊃ B) ≡ (((A NOR A) NOR B) NOR ((A NOR A) NOR B)))
95 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Ist es gerechtfertigt zu sagen, dass ∧ durch ¬ und ∨ definiert werdenkann, da (A ∧ B) ≡ ¬(¬A ∨ ¬B) tautologisch ist?
Definition
Das Resultat der Ersetzung des Aussagebuchstabens p durch eine FormelA in der Formel B (symbolisch [A/p] B, lies: “A fur p in B”) ist wie folgtinduktiv definiert:
(i) [A/p] p = A
[A/p] q = q
(ii) [A/p] ¬C = ¬[A/p] C
(iii) [A/p] (C # D) = [A/p] C # [A/p] D(wobei # ∈ {∧,∨,⊃,≡})
96 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Satz
(Ersetzbarkeitssatz)Wenn A und B zwei logisch aquivalente aussagenlogische Formeln sind,dann sind auch (A/p) C und (B/p) C logisch aquivalent.
Beweis. Mit Induktion nach C . q.e.d.
Ist jede Menge zweistelliger Junktoren funktional vollstandig? Wir wollenzeigen, dass {⊃} nicht funktional vollstandig ist.
97 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Lemma
Jede aussagenlog. Formel A, die nur aus dem Aussagebuchstaben p und dem Junktor ⊃(und Klammern) aufgebaut ist, ist logisch aquivalent mit p oder mit p ⊃ p.
Beweis. Mit Induktion nach A. (i) A = p: Klar. (ii) A = (B ⊃ C). Nach derInduktionshyp. gilt das Lemma fur B und C , d.h. B und C sind logisch aquivalent mit poder mit (p ⊃ p). Dann existieren vier Falle:
(a) B und C sind beide logisch aquivalent mit p.
(b) B und C sind beide logisch aquivalent mit (p ⊃ p).
(c) B ist logisch aquivalent mit p und C mit (p ⊃ p).
(d) C ist logisch aquivalent mit p und B mit (p ⊃ p).
Im Fall (a) ist (B ⊃ C) logisch aquivalent mit p ⊃ p.Im Fall (b) ist (B ⊃ C) logisch aquivalent mit (p ⊃ p) ⊃ (p ⊃ p) und damitlogisch aquivalent mit p ⊃ p.Im Fall (c) ist (B ⊃ C) logisch aquiv. mit p ⊃ (p ⊃ p) und damit logischaquivalent mit p ⊃ p.Im Fall (d) ist (B ⊃ C) logisch aquiv. mit (p ⊃ p) ⊃ p und damit logischaquivalent mit p. q.e.d.
98 / 230
Eine Einfuhrung in die klassische Logik
Funktionale Vollstandigkeit
Behauptung
{⊃} ist nicht funktional vollstandig.
Beweis. Wir zeigen, dass keine aussagenlogische Formel A, dieausschließlich aus Aussagebuchstaben und ⊃ aufgebaut ist, logischaquivalent mit p ∧ ¬p ist.Angenommen, A ist ausschließlich aus Aussagebuchstaben und ⊃aufgebaut und A ist logisch aquivalent mit (p ∧ ¬p). Sei A∗ das Resultatder Ersetzung aller Aussagebuchstaben in A durch p. Da A falsch ist injedem Modell ist auch A∗ logisch aquivalent mit (p ∧ ¬p). Aber das ist einWiderspruch zum vorherigen Lemma. q.e.d.
99 / 230
Eine Einfuhrung in die klassische Logik
Terminologie
Definition
Eine Abbildung von k-Folgen von Wahrheitswerten (k ∈ N) in die Menge{W,F} heißt k-stellige Wahrheitsfunktion.
Beispiel:Wir definieren den Junktor ♥ durch die Festlegung:
♥(A,B,C ,D) =def (A ∧ B) ⊃ (¬C ∧ D)
Dieser Junktor bezeichnet eine vierstellige Wahrheitsfunktion.
Gibt es 0-stellige Wahrheitsfunktionen?
Eine Menge ∆ von Wahrheitsfunktionen heißt funktional vollstandig, wennjede Wahrheitsfunktion durch Elemente von ∆ definiert werden kann.
100 / 230
Eine Einfuhrung in die klassische Logik
Bendall Normalform
Das Bestreiten ist ein Sprechakt, der ohne Verwendung der Negation ausgefuhrtwerden kann.
Es ist z.B. moglich, zu bestreiten, dass Josef Stalin ein weiser Staatsmann war,indem man den Satz “Josef Stalin war ein weiser Staatsmann” ironisch außertoder behauptet, dass Josef Stalin der weiseste Staatsmann aller Zeiten war.
Man konnte allerdings meinen, dass zu bestreiten, dass A, am besten zuanalysieren und verstehen ist als das Behaupten der Negation von A. Wenn mandann weiterhin annimmt, dass das Wesen der Negation gerade darin besteht, denSprechakt des Bestreitens unabhangig von Phanomenen wie der Ironie oderEigenschaften eines Außerungskontextes zu ermoglichen, dann ergibt sich einProblem.
Negationen konnen iteriert werden und innerhalb komplexer Satze oder Formelnverwendet werden; Sprechakte konnen nicht derartig verschachtelt werden.
101 / 230
Eine Einfuhrung in die klassische Logik
Bendall Normalform
Wenn behauptet werden soll, dass der Begriff des Bestreitens grundlegendist fur das Verstandnis der Negation, dann ware es gut, wenn fur jedenSatz (jede Formel) A gelten wurde, dass A logisch aquivalent ist zu einemSatz (einer Formel), in dem (der) das Negationssymbol wenn uberhauptnur einmal und als Hauptjunktor vorkommt.
Fur die klassische Logik gilt das.
Definition
Eine aussagenlogische Formel befindet sich in Bendall Normalform genaudann, wenn sie negationsfrei ist oder die Gestalt ¬B hat und Bnegationsfrei ist.
102 / 230
Eine Einfuhrung in die klassische Logik
Definition
Seien B, C negations-freie aussagenlogische Formeln. Die ex-Negation exAeiner aussagenlogischen Formel A ist wie folgt induktiv definiert.
exB = B
ex¬B = ¬Bex¬¬B = B
ex(B ∧ ¬C) = ¬(B ⊃ C)
ex(¬B ∧ C) = ¬(C ⊃ B)
ex(¬B ∧ ¬C) = ¬(B ∨ C)
ex(B ∨ ¬C) = (C ⊃ B)
ex(¬B ∨ C) = (B ⊃ C)
ex(¬B ∨ ¬C) = ¬(B ∧ C)
ex(B ⊃ ¬C) = ¬(B ∧ C)
ex(¬B ⊃ C) = (B ∨ C)
ex(¬B ⊃ ¬C) = (C ⊃ B)
103 / 230
Eine Einfuhrung in die klassische Logik
Bendall Normalform
Mit Hilfe der Operation ex kann gezeigt werden, dass
Lemma
Jede aussagenlogische Formel A ist logisch aquivalent zu einer Formel derGestalt B, ¬B oder ¬¬B, wobei B negationsfrei ist.
Behauptung
Jede aussagenlogische Formel ist logisch aquivalent zu einer Formel inBendall Normalform.
Beweis. Sei A eine aussagenlogische Formel. Mit dem vorhergehendenLemma ist A logisch aquivalent zu einer Formel der Gestalt B, ¬B oder¬¬B, wobei B negatiosnfrei ist. Die Formeln B und ¬B befinden sich inBendall Normalform. Die Formel ¬¬B ist logisch aquivalent zu B. q.e.d.
104 / 230
Eine Einfuhrung in die klassische Logik
Ein einfaches semantisches Faktum
Behauptung
Sei A eine aussagenlogische Formel, sei at(A) die Menge der in Avorkommenden Aussagebuchstaben und seien v, v ′ aussagenlogischeModelle, so dass fur alle p ∈ at(A) gilt: v(p) = v ′(p). Dann istV (A) = V ′(A).
Beweis. Mit Induktion nach A. Wir zeigen zunachst, dass die Behauptunggilt, falls A ein Aussagebuchstabe ist. Falls A eine zusammengesetzteFormel ist, zeigen wir, dass die Behauptung fur A gilt unter der Annahme,dass die Behauptung bereits fur Teilformeln von A gilt, die verschieden vonA sind (Induktionsannahme).
105 / 230
Eine Einfuhrung in die klassische Logik
Ein einfaches semantisches Faktum
(i) A ist ein Aussagebuchstabe.Dann ist V (A) = v(A) = v ′(A) = V ′(A)
(ii) A ist eine Negation ¬B. Dann haben wir:
V (¬B) = W gdw
V (B) = F gdw mit der Induktionsannahme
V ′(B) = F gdw
V ′(¬B) = W
(iii) A ist eine Konjunktion (B ∧ C ). Dann haben wir:
V (B ∧ C ) = W gdw
V (B) = V (C ) = W gdw mit der Induktionsann.
V ′(B) = V ′(C ) = W gdw
V ′(B ∧ C ) = W
Die restlichen Falle zeigt man analog. q.e.d.106 / 230
Eine Einfuhrung in die klassische Logik
Ein Schritt zuruck: Platons Kratylos
Platon gilt als ein Vorlaufer der modernen sprachanalytischen Philosophie.In dem Dialog Kratylos lasst er Sokrates fur die Ansicht eines gewissenKratylos von der naturlichen Korrektheit der Bennungen argumentieren.Hermogenes, der anfanglich die Auffassung vertritt, die Bennungenberuhten auf Konventionen, wird von Sokrates dazu gebracht, derAuffassung des Kratylos zuzustimmen. Ein Schritt in diesem Prozess ist dieZuruckweisung der These des Protagoras, der Mensch sei das Maß allerDinge. Platon (Kratylos 386a–d) schreibt:
107 / 230
Eine Einfuhrung in die klassische Logik
Ein Schritt zuruck: Platons Kratylos
Sokrates: Wohlan, lass uns sehen, Hermogenes, ob dir vorkommt, dass es auch mit den Dingen ebenso steht, dass ihr Sein undWesen fur jeden einzelnen in besonderer Weise ist, wie Protagoras meinte, wenn er sagt, der Mensch sei das Maß aller Dinge,dass also die Dinge, wie sie mir erscheinen, so auch fur mich wirklich sind, und wiederum wie dir, so auch fur dich? Oder dunktdich, dass sie in sich eine Bestandigkeit ihres Wesens haben?Hermogenes: Ich bin wohl sonst schon in der Verlegenheit auch dahin geraten, Sokrates, auf dasselbe, was auch Protagorassagt; ganz und gar so glaube ich jedoch nicht, dass es sich verhalte.Sokrates: Wie aber? Bist du auch darauf schon geraten, dass du nicht glauben konntest, ein Mensch sei gar schlecht?Hermogenes: Nein, beim Zeus, vielmehr ist mir schon oft begegnet, dass mir Menschen gar schlecht vorgekommen sind, undzwar recht viele.Sokrates: Und wie? Gar gut hast du noch nicht geglaubt, dass Menschen waren?Hermogenes: Nur sehr wenige.Sokrates: Also doch welche?Hermogenes: Oh ja.Sokrates: Wie aber meinst du es? Etwa so, dass die gar guten auch gar vernunftig sind und die gar schlechten auch garunvernunftig?Hermogenes: Ich meine es gerade so.Sokrates: Konnen nun wohl, wenn Protagoras wahr redete und dies die Wahrheit ist, dass fur jeden, wie ihm etwas erscheint,so es auch ist, als dann einige von uns vernunftig sein und andere unvernunftig?Hermogenes: Nicht fuglich.Sokrates: Auch dies, denke ich, glaubst du gar sehr, dass, wenn es Vernunft und Unvernunft gibt, es dann eben nicht sehrmoglich ist, dass Protagoras recht habe. Denn es ware ja in Wahrheit nicht einer vernunftiger als der andere, wenn, was jedemschiene, auch fur jeden wahr ware.Hermogenes: Das ist richtig.
108 / 230
Eine Einfuhrung in die klassische Logik
Ein Schritt zuruck: Platons Kratylos
Die Argumentation des Sokrates kann als die folgende Schlussfolgerungverstanden werden:
Die Dinge sind so, wie sie einem jeden einzelnenerscheinen. (These des Protagoras)
Wenn die Dinge so sind, wie sie einem jeden erscheinen, dann gibt eskeinen Unterschied zwischen vernunftigen und unvernunftigenMenschen.
Wenn es keinen Unterschied zwischen vernunftigen undunvernunftigen Menschen gibt, dann existiert kein Unterschiedzwischen guten und schlechten Menschen.
Es existiert ein Unterschied zwischen guten und schlechten Menschen.
Die Dinge sind nicht so, wie sie einem jeden einzelnen erscheinen.
109 / 230
Eine Einfuhrung in die klassische Logik
Ein Schritt zuruck: Platons Kratylos
Diese Schlussfolgerung ist gultig. Sie ist ein Beispiel fur eine Einfuhrungder Negation.
[ p ]p ⊃ ¬u¬u ⊃ ¬g¬g g¬p
110 / 230
Eine Einfuhrung in die klassische Logik
Beweissysteme
Typen von Beweissystemen
axiomatische Systeme (Hilbert-Systeme)
Systeme des naturlichen Schließens(Stanis law Jaskowski, Gerhard Gentzen)
Sequenzenkalkule (G. Gentzen)
semantische Tableaux (Evert Beth)
111 / 230
Eine Einfuhrung in die klassische Logik
Beweissysteme
Hilbert-Systeme: • viele Axiome(nschemata)(Regeln der Gestalt ∅/A)
• wenige Regeln (∆/A)
naturliches Schließen: • keine Axiome• viele Regeln
Sequenzenkalkule: • nur eine axiomatischeAbleitbarkeitsbehauptung“A ist aus A ableitbar” (A ` A)
• Regeln, um Ableitbarkeits-behauptungen zu manipulieren
semantische Tableaux • Regeln fur die Suchenach Gegenbeispielen
112 / 230
Eine Einfuhrung in die klassische Logik
Beweissysteme
Ein Axiomensystem fur die klassische Aussagenlogik
Axiomenschemata: 1) A ⊃ (B ⊃ A)2) (A ⊃ (B ⊃ C )) ⊃ ((A ⊃ B) ⊃ (A ⊃ C ))3) (¬A ⊃ B) ⊃ ((¬A ⊃ ¬B) ⊃ A)
Ableitungsregeln: modus ponens A A ⊃ BB
Axiome konnen als Grenzfalle von Ableitungsregeln gesehen werden, alsRegeln ohne Input.
Sei S ein Beweissystem. Wenn eine Formel A aus einer Formelmenge ∆mit Hilfe der Regeln von S ableitbar ist, dann schreiben wir ∆ `S A. Wennaus dem Kontext klar ist, welches Beweissystem betrachtet wird, schreibenwir auch einfach ∆ ` A.
113 / 230
Eine Einfuhrung in die klassische Logik
Beweissysteme
Eine axiomatische Ableitung einer Formel A aus einer Formelmenge ∆ isteine endliche Folge A1, . . .An von Formeln, so dass An = A und jedeFormel in der Folge entweder eine Einsetzung eines Axiomenschemas, einElement von ∆ oder das Erebnis der Anwendung einer Ableitungsregel aufvorhergehende Formeln als Pramissen ist.
Beispiel:
(A ⊃ ((A ⊃ A) ⊃ A)) Axiom 1(A ⊃ ((A ⊃ A) ⊃ A)) ⊃ ((A ⊃ (A ⊃ A)) ⊃ (A ⊃ A)) Axiom 2
((A ⊃ (A ⊃ A)) ⊃ (A ⊃ A)) modus ponens, 1, 2((A ⊃ (A ⊃ A)) Axiom 1
(A ⊃ A) modus ponens, 3, 4
114 / 230
Eine Einfuhrung in die klassische Logik
Beweissysteme
Sei SL das obige Beweissystem.
SL ist korrekt und vollstandig bezuglich der Klasse aller aussagenlogischenModelle.
Deduktionstheorem
Wenn ∆ ∪ {A} `SLB, dann ∆ `SL
A ⊃ B.
Im System des naturlichen Schließens fur die klassische Aussagenlogik wirddas Deduktionstheorem als eine Ableitungsregel angenommen.
115 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Einfuhrungsregeln geben an, wie auf Konklusionen bestimmter Gestaltgeschlossen werden kann.
Beseitigungsregeln geben an, wie Formeln bestimmter Gestalt verwendetwerden (um Information zu extrahieren).
Beispiele:Jan lacht. 7→ j ; Peter lacht. 7→ p; Marie lacht. 7→ m.
Annahme: Jan lacht und Peter lacht.Konklusion: Peter lacht oder Marie lacht.
(j ∧ p)p
(∧B)
(p ∨m)(∨E)
In einem ersten Schritt wird eine Konjunktion beseitigt (∧B) und ineinem zweiten Schritt eine Disjunktion eingefuhrt (∨E ).
116 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Annahmen: Wenn Jan lacht, dann lacht Peter.Wenn Marie lacht, dann lacht Peter.Jan lacht oder Marie lacht.
Konklusion: Peter lacht.
(j ∨m)[j ]1 (j ⊃ p)
p(⊃B)
[m]1 (m ⊃ p)p
(⊃B)
p(∨B)1
Es wird p aus (j ∨m) durch Disjunktionsbes. (∨B) abgeleitet. Idee: Wenn p
sowohl aus j , als auch aus m ableitbar ist, dann ist p aus (j ∨m) ableitbar. Um zu
sehen, ob p sowohl aus j , als auch aus m ableitbar ist, werden j und m temporar
angenommen. Wenn gezeigt werden kann, dass p sowohl aus j , als auch aus m
ableitbar ist, konnen die temporaren Annahmen aufgegeben werden. Sie werden
mit der ∨-Beseitigung getilgt. Die Tilgung wird durch eckige Klammern um j und
m kenntlich gemacht. Die Ableitung von p hangt nur noch von den nicht
getilgten Annahmen ab.
117 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Annahmen: Wenn Jan lacht, dann ist es so, dassPeter lacht, falls Jan lacht.
Konklusion: Wenn Jan lacht, dann lacht Peter.
[j ]1
[j ]1 j ⊃ (j ⊃ p)
j ⊃ p(⊃B)
p(⊃B)
j ⊃ p(⊃E)1
Die Konklusion in diesem Beispiel ist eine Implikation: j ⊃ p. Um die Konklusion
aus j ⊃ (j ⊃ p) abzuleiten, genugt es zu zeigen, dass p aus j und j ⊃ (j ⊃ p)
ableitbar ist. Also wird die temporare Annahme j gemacht. Mit (⊃ B) kann
(j ⊃ p) abgeleitet werden, und unter nochmaliger Verwendung von j kann wieder
mit (⊃ B) schließlich p abgeleitet werden. Die temporare Annahme j wird
aufgegeben, und j ⊃ p damit aus j ⊃ (j ⊃ p) allein abgeleitet.
118 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
[j ]1
[j ]1 j ⊃ (j ⊃ p)
j ⊃ p(⊃B)
p(⊃B)
j ⊃ p(⊃E)1
In diesem Beispiel werden mit der Anwendung der Regel (⊃ E ) zweiVorkommnisse der temporaren Annahme j getilgt. Die Regel (⊃ E )gestattet es, bei der Einfuhrung einer Implikation (A ⊃ B) beliebig vieleVorkommnisse von A in einer Ableitung von B aufzugeben.
119 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Auch die folgenden Gebilde stellen Ableitungen dar:
j
[j ]1 j ⊃ (j ⊃ p)
j ⊃ p(⊃B)
p(⊃B)
j ⊃ p(⊃E)1
j
j j ⊃ (j ⊃ p)
j ⊃ p(⊃B)
p(⊃B)
j ⊃ p(⊃E)
Diese Ableitungen hangen aber von j ab, da nicht alle Vorkommnisse von j
aufgegeben werden. Die Regel (⊃ E ) gestattet es in diesem Fall, Vorkommnisse
von j aufzugeben, aber die Tilgung ist nicht obligatorisch.
120 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Annahmen: ∅Konklusion: Wenn Jan lacht, dann ist es so, dass
Jan lacht, falls Peter lacht.
[j ]1
(p ⊃ j)(⊃E)
j ⊃ (p ⊃ j)(⊃E)1
Hier begegnen wir einer leeren Implikationseinfuhrung. Die Einfuhrung der
Implikation (p ⊃ j) im ersten Ableitungsschritt ist insofern leer oder
irrelevant, als dass das Antezedens p nicht tatsachlich verwendet wird, um j
abzuleiten. Dennoch ist der Ableitungsschritt korrekt: Wenn j wahr ist, dann
sicherlich auch p ⊃ j . Die Regel (⊃ E ) ist so zu verstehen, dass leere
Implikationseinfuhrungen gestattet sind. In sogenannten Relevanzlogiken
sind irrelevante Implikationseinfuhrungen nicht erlaubt.
121 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Die Regeln des naturlichen Schließens fur die klassische Aussagenlogik. DieFormelmengen ∆, Γ und Θ sind endlich. Regeln fur die Konjunktion: small
∆....A
Γ....B
(A ∧ B)(∧E )
∆....(A1 ∧ A2)
Ai(∧B)
i = 1, 2
(∧E ): Aus einer Ableitung von A aus der Pramissenmenge ∆ und einerAbleitung von B aus Γ erhalt man eine Ableitung von (A∧B) aus ∆∪ Γ.
(∧B): Hier handelt es sich um zwei Regeln. Wenn (A1 ∧ A2) aus ∆ableitbar ist, dann ist jedes der beiden Konjunktionsglieder aus ∆ ableitbar.
122 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
∆....Ai
(A1 ∨ A2)(∨E )
i = 1, 2
∆....(A ∨ B)
Γ, [A]....
C
Θ, [B]....
C
C(∨B)
(∨E ): Wenn A1 (bzw. A2) aus ∆ ableitbar ist, dann auch (A1 ∨ A2).(∨B): Betrachten wir zunachst den Fall, dass ∆, Γ und Θ leer sind:
(A ∨ B)
[A]....
C
[B]....
C
C(∨B)
C ist aus (A ∨ B) ableitbar ist, wenn C sowohl aus A, als auch aus B ableitbarist. Regel (∨B) verallgemeinert den Spezialfall. Angenommen (A ∨ B) ist aus ∆ableitbar und C ist sowohl aus Γ ∪ {A}, als auch aus Θ ∪ {B} ableitbar. Dann istC aus ∆ ∪ Γ ∪Θ ableitbar.
123 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
∆, [A]....B
(A ⊃ B)(⊃ E )
∆....A
Γ....(A ⊃ B)
B(⊃ B)
(⊃ E ): Aus einer Ableitung von B aus den Pramissen in ∆ zusammen mitA erhalt man eine Ableitung von (A ⊃ B) aus ∆.
(⊃ B): Aus einer Ableitung von A aus ∆ und einer Ableitung von (A ⊃ B)aus Γ erhalt man eine Ableitung von B aus ∆ ∪ Γ.
124 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
∆, [A]....B
Γ, [A]....¬B
¬A(¬E )
∆....B
Γ....¬B
A(¬B)
∆, [¬A]....B
Γ, [¬A]....¬B
A(¬B)∗
(¬E ): Betrachten wir zunachst den Fall, dass ∆ = Γ = ∅:
[A]....B
[A]....¬B¬A
(¬E)
¬A ist ableitbar, wenn die Annahme, dass A der Fall ist, zu einem Widerspruch
fuhrt: Wenn aus A eine Formel B ableitbar ist und deren Negation ¬B. Die Regel
(¬E ) verallgemeinert diesen Fall: Aus einer Ableitung von B aus ∆ ∪ {A} und
einer Ableitung von ¬B aus Γ∪{A} erhalt man eine Ableitung von ¬A aus ∆∪Γ.
125 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
∆, [A]....B
Γ, [A]....¬B
¬A(¬E )
∆....B
Γ....¬B
A(¬B)
∆, [¬A]....B
Γ, [¬A]....¬B
A(¬B)∗
(¬B): Die Regel ist seit der Antike unter dem Namen ex contradictionequodlibet (aus einem Widerspruch ist Beliebiges ableitbar) bekannt.
(¬B)∗: Diese zweite Negationsbeseitigungsregel ist als die Regel derklassischen reductio ad absurdum (Zuruckfuhrung auf etwas Absurdes)bekannt. Eine Formel A (welche Gestalt auch immer sie haben mag) kannabgeleitet werden, wenn die Annahme, dass ¬A der Fall ist, zu einemWiderspruch fuhrt.
126 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Definition
SN (das System des naturlichen Schließens fur die klassischeAussagenlogik) ist die Menge der Regeln des naturlichen Schließens fur dieklassische Aussagenlogik.
Wir nehmen an, dass jede Formel A eine Ableitung von A aus {A}darstellt.
Beispiele:
(a) Ableitung von p ⊃ ¬¬p aus ∅. Da aus ∅ abgeleitet werden soll,durfen nur temporare Annahmen gemacht werden, die getilgt werden.
[p]2 [¬p]1
¬¬p (¬E)1
p ⊃ ¬¬p(⊃E)2
127 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
[p]2 [¬p]1
¬¬p (¬E)1
p ⊃ ¬¬p(⊃E)2
Wie findet man diese Ableitung von p ⊃ ¬¬p aus ∅? Abzuleiten ist eineImplikation. Das geschieht normalerweise mit Implikationseinfuhrung.Damit erhalt man p als temporare Pramisse, aus der die Negation ¬¬pabzuleiten ist. Die kanonische Ableitung einer Negation erfolgt durchNegationseinfuhrung, d.h. hier, dass die temporare Annahme ¬p zu einemWiderspruch fuhren soll. Die Annahme ¬p widerspricht bereits der anderentemporaren Annahme. Der benotigte Widerspruch zwischen einer FormelB und ihrer Negation liegt damit vor, und die Annahme ¬p kann getilgtwerden. Die Annahme p wird mit der Anwendung von (⊃ E ) getilgt. DieIndizes heben hervor, an welcher Stelle welche temporare Pramisseaufgegeben wird.
128 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(b) Ableitung von (p ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃ (p ⊃ r)) aus ∅.
[p]1 [p ⊃ q]2
q(⊃B)
[p]1 [p ⊃ (q ⊃ r)]3
q ⊃ r(⊃B)
r(⊃B)
(p ⊃ r)(⊃E)1
(p ⊃ q) ⊃ (p ⊃ r)(⊃E)2
(p ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃ (p ⊃ r))(⊃E)3
Zu beweisen ist eine Implikation. Das geschieht normalerweise mit (⊃ E ). Wir
erhalten so sukzessive die Formeln p ⊃ (q ⊃ r), p ⊃ q und p als temporare
Annahmen und mussen aus diesen Pramissen die atomare Formel r ableiten. Auf
die atomare Pramisse p kann keine Bes.regel angewandt werden. Die anderen
Pramissen sind Implikationen. Um auf sie die Regel (⊃ B) anzuwenden, wird
jeweils das Antezedens der Implikation benotigt. Die Pramissen p und p ⊃ q
liefern offensichtlich q, und q zusammen mit q ⊃ r liefert r . Die drei
Anwendungen von (⊃ E ) erlauben es, die temporaren Annahmen aufzugeben.129 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(c) Ableitung von p ⊃ q aus {¬p ∨ q}.
¬p ∨ q[¬p]1 [p]2
q (¬B) [q]1
q (∨B)1
p ⊃ q(⊃E)2
Die Implikation p ⊃ q wird mit (⊃ E ) abgeleitet, was die temporare Annahme p
liefert. Die einzige Pramisse, auf die eine Bes.regel anwendbar ist, ist die
gegebene Annahme ¬p ∨ q. Auf diese Formel wird die Beseitigungsregel fur ihren
Hauptjunktor angewendet: (∨B). Die Formel q ist also jeweils aus den beiden
Disjunktionsgliedern und eventuell weiteren Annahmen abzuleiten. Das rechte
Disjunktionsglied stellt eine Ableitung von q aus q dar; das linke Disjunktionsglied
¬p liefert zusammen mit der temporaren Annahme und (¬B) ebenfalls q. Die
Disjunktionsglieder werden mit der Anwendung von (∨B) als zwischenzeitliche
Annahmen aufgegeben.
130 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(d) Ableitung von (p ∨ (q ∧ r)) ⊃ ((p ∨ q) ∧ (p ∨ r)) aus ∅.
[p ∨ (q ∧ r)]3[p]1
p ∨ q(∨E)
[q ∧ r ]1
q(∧B)
p ∨ q(∨E)
p ∨ q(∨B)1
[p ∨ (q ∧ r)]3[p]2
p ∨ r(∨E)
[q ∧ r ]2
r(∧B)
p ∨ r(∨E)
p ∨ r(∨B)2
(p ∨ q) ∧ (p ∨ r)(∧E)
(p ∨ (q ∧ r)) ⊃ ((p ∨ q) ∧ (p ∨ r))(⊃E)3
Abzuleiten ist eine Implikation. Das geschieht mit (⊃ E). Wir erhalten p ∨ (q ∧ r) als
temp. Pramisse, aus der (p ∨ q) ∧ (p ∨ r) abzuleiten ist. Die kanonische Ableitung einer
Konj. erfolgt mit (∧E). Das linke Konj.glied ist p ∨ q. Typischerweise werden Disj. mit
(∨E) abgeleitet. Diese Uberlegung fuhrt jedoch nicht zum Ziel. Wenn p ∨ q aus p
abgeleitet werden soll, muss p aus der einzigen zur Verfugung stehenden Annahme
abgeleitet werden, einer Disj.. Diese zu verwenden, bedeutet die Regel (∨B)
anzuwenden. D.h., dass p (i) aus p und (ii) aus q ∧ r abgeleitet werden muss. Die
Aufgabe (i) ist trivial; (ii) nicht losbar.131 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
[p ∨ (q ∧ r)]3[p]1
p ∨ q(∨E)
[q ∧ r ]1
q(∧B)
p ∨ q(∨E)
p ∨ q(∨B)1
[p ∨ (q ∧ r)]3[p]2
p ∨ r(∨E)
[q ∧ r ]2
r(∧B)
p ∨ r(∨E)
p ∨ r(∨B)2
(p ∨ q) ∧ (p ∨ r)(∧E)
(p ∨ (q ∧ r)) ⊃ ((p ∨ q) ∧ (p ∨ r))(⊃E)3
Wann kann man tun? Man kann schauen, ob die abzuleitende Formel p ∨ q direkt
aus der zur Verfugung stehenden Pramisse ableitbar ist. Das ist der Fall. Die
Formel p ∨ q erhalt man aus dem linken Disj.glied der temp. Annahme mit (∨E )
und aus dem rechten Disj.glied mit (∧B) und (∨E ). Die Anwendung von (∨B)
auf die temp. Annahme erlaubt es, die Disjunktionsglieder zu tilgen. Die
temp. Annahme selbst wird im letzten Ableitungsschritt getilgt. Das rechte
Disj.glied von ((p ∨ q) ∧ (p ∨ r)) kann analog abgeleitet werden.
132 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(e) Ableitung der Kontrapositionsregel p ⊃ q ` ¬q ⊃ ¬p.
[p]1 p ⊃ qq (⊃B) [¬q]2
¬p (¬E)1
¬q ⊃ ¬p(⊃E)2
(f) Ableitung von ¬¬p ⊃ p aus ∅.
[¬¬p]2 [¬p]1
p (¬B∗)1
¬¬p ⊃ p(⊃E)2
In dieser Ableitung wird von der Regel der klassischen reductio adabsurdum, (¬B)∗, Gebrauch gemacht. Aus der Annahme ¬¬p ist p nichtdirekt ableitbar. Wenn aber mit (¬B)∗ temporar ¬p angenomen wird, liegtein Widerspruch vor und ¬p kann aufgegeben werden.
133 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(g) Ableitung von ¬(¬p ∨ q) ⊃ (p ∧ ¬q) aus ∅.
[¬(¬p ∨ q)]3[¬p]2
¬p ∨ q(∨E)
p (¬B∗)2[¬(¬p ∨ q)]3
[q]1
¬p ∨ q(∨E)
¬q (¬E)1
p ∧ ¬q(∧E)
¬(¬p ∨ q) ⊃ (p ∧ ¬q)(⊃E)3
Die ersten beiden Schritte der Beweissuche sind klar. Abzuleiten sind diezwei Konj.glieder p und ¬q. Negationen werden typischerweise mit (¬E )abgeleitet. Hier wird die temp. Annahme q zum Widerspruch gefuhrt. Zueinem Widerspruch wozwischen? Mit der tem. Annahme ¬(¬p ∨ q) liegtschon eine negierte Formel ¬B vor, und es ist leicht zu sehen, dass q mit(∨E ) ¬p ∨ q liefert. Fur die Ableitung von p steht eine Pramisse zurVerfugung: ¬(¬p ∨ q). Mittels (¬B) kann p daraus nicht abgeleitetwerden. Die Regel (¬B)∗ gestattet es, ¬p temporar anzunehmen, so dassmit (∨E ) die Formel ¬p ∨ q abgeleitet werden kann.
134 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(h) Ableitung von ¬(p ∧ q) ⊃ (¬p ∨ ¬q) aus ∅.
[¬(¬p ∨ ¬q)]3
[¬p]1
¬p ∨ ¬q (∨E)
p (¬B∗)1[¬(¬p ∨ ¬q)]3
[¬q]2
¬p ∨ ¬q (∨E)
q (¬B∗)2
p ∧ q(∧E)
[¬(p ∧ q)]4
¬p ∨ ¬q (¬B∗)3
¬(p ∧ q) ⊃ (¬p ∨ ¬q)(⊃E)4
Im vorletzten Bew.schritt ist ¬p ∨ ¬q aus ¬(p ∧ q) abzuleiten. Es gibt zunachst zwei
Strategien fur die Beweissuche: (1) ¬p ∨ ¬q kann mit (∨E) abgeleitet werden; (2) die
Anwendung von (¬B) auf ¬(p ∧ q) fuhrt zu ¬p ∨ ¬q. Die Vermutung, dass ¬p ∨ ¬qdurch (∨E) abgeleitet werden kann, fuhrt nicht zum Ziel. Auch ist nicht klar, wie (¬B)
auf ¬(p ∧ q) anwendbar sein sollte. Damit sind aber nicht alle Optionen erschopft:
¬p ∨ ¬q kann mit (¬B)∗ abgeleitet werden. Aus der Negation von ¬p ∨ ¬q ist ein
Widerspruch abzuleiten. Da die Annahme ¬(p ∧ q) eine Negation ist, ist es nicht
abwegig, zu versuchen, (p ∧ q) aus ¬(¬p ∨ ¬q) abzuleiten.135 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
(i) Ableitung einer Einsetzung in Peirce’s Gesetz: ((p ⊃ q) ⊃ p) ⊃ p.
[¬p]3[p ⊃ q]2 [(p ⊃ q) ⊃ p]4
p (⊃B)
¬(p ⊃ q)(¬E)2
[p]1 [¬p]3
q (¬B)
p ⊃ q(⊃E)1
p (¬B∗)3
((p ⊃ q) ⊃ p) ⊃ p(⊃E)4
Wie kann p aus (p ⊃ q) ⊃ p) abgeleitet werden? p kann nicht mit einer Einf.regel
abgeleitet werden, und fur die Anwendung von (⊃ B) auf die temp. Pramisse wird
p ⊃ q benotigt. Als Option fur die Beweissuche bleibt, dass p mit (¬B)∗ ableitbar
ist. Gesucht ist also eine Formel B und ihre Negation ¬B. Aus den
temp. Annahmen ¬p und (p ⊃ q) ⊃ p ergibt sich p (und somit ein Widerspruch
zu ¬p), wenn (p ⊃ q) angenommen wird. Diese neue temp. Annahme kann
aufgegeben werden, wenn aus p und ¬p mit (¬E ) die Formel ¬(p ⊃ q) und
damit eine Formel der Gestalt ¬B abgeleitet wird. Die Formel B = p ⊃ q erhalt
man dann leicht unter Verwendung der temp. Annahme ¬p.136 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Die Beispiele (a) – (i) legen folgende Heuristik fur die Suche nach Ableitungen inSN nahe:
Zur Ableitung einer zusammengesetzten Formel A nehme man zunachst an, dassder letzte Schritt in der Ableitung von A die Einfuhrung des Hauptjunktors von Aist.
Dieses Vorgehen iteriere man. Wenn schließlich eine atomare Formel p abzuleitenist, betrachte man die zur Verfugung stehenden Pramissen und versuche, ausdiesen Formeln durch Anwendung der Beseitigungsregeln fur die Hauptjunktoren pabzuleiten. [(a), (b), (c), (e)]
Wenn diese Strategie nicht zum Ziel fuhrt, versuche man, die Pramissen zuverwenden, bevor durch sukzessive Anwendung von Einfuhrungsregeln die FormelA vollstandig in atomare Bestandteile zerlegt ist. [(d)]
Ist auch dieses Vorgehen ergebnislos, versuche man, in einem moglichst spatenSchritt der bisherigen erfolglosen Beweissuche durch Anwendung von (¬B)∗ eineAbleitung zu finden. [(f), (g), (h)]
137 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Ableitungen in SN haben die Gestalt sich maximal dreifach verzweigenderendlicher Baume, mit der Konklusion als Wurzel. Die obige Ableitung (d)z.B. hat die folgende Baumstruktur:
rrr rr r r r r rr r r rr r
QQQ
QQQ
������
@@
��
@@
��
138 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Regeln, die es erlauben, zwischenzeitliche Annahmen aufzugeben,gestatten die Tilgung dieser Pramissen nur in dem Teilbaum oberhalb derRegelanwendung. Pramissentilgungen z.B. der Form:
AAAA
����
AAAA
����
@@
@@@
�����
[A]1 [A]1
(A ⊃ B)(⊃E)1
C
(A ⊃ B) ∧ C
sind nicht zulassig.
139 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen
Definition
Eine aussagenlogische Formel A heißt ableitbar aus der Pramissenmenge ∆in SN genau dann, wenn eine endliche Teilmenge Γ von ∆ und eineAbleitung von A aus Γ in SN existiert. Wenn A aus ∆ ableitbar ist,schreiben wir ∆ `SN
A oder kurz ∆ ` A. A heißt beweisbar in SN genaudann, wenn ∅ ` A. Wir schreiben stattdessen auch einfach ` A. EineAbleitung von A aus ∅ wird auch als Beweis bezeichnet.
140 / 230
Eine Einfuhrung in die klassische Logik
Konsistenz und Inkonsistenz
Definition
Eine aussagenlogische Formel A wird erfullbar genannt gdw A keineKontradiktion ist. A wird falsifizierbar genannt gdw A keine Tautologie ist.Eine Formelmenge ∆ heißt erfullbar genau dann, wenn ein Modell Mexistiert, so dass fur jedes A ∈ ∆ gilt: M |= A. Wir schreiben dann auchM |= ∆.
Wenn eine Formel oder Formelmenge erfullbar ist, wird sie auch alssemantisch konsistent bezeichnet. Analog werden unerfullbare (nichterfullbare) Formeln und Formelmengen auch semantisch inkonsistentgenannt. Neben diesen semantischen Begriffen der Konsistenz undInkonsistenz gibt es allerdings auch syntaktische, beweistheoretischeBegriffe der Konsistenz und Inkonsistenz.
141 / 230
Eine Einfuhrung in die klassische Logik
Konsistenz und Inkonsistenz
Definition
Eine Formemenge ∆, heißt syntaktisch konsistent genau dann, wenn eskeine Formel A gibt, so dass ∆ ` A und ∆ ` ¬A.
Behauptung
Eine Formelmenge ∆ ist syntaktisch konsistent genau dann, wenn es eineFormel A gibt, so dass ∆ 6` A, d.h. wenn nicht gilt ∆ ` A.
Beweis.
“⇒” Wenn ∆ konsistent ist, dann existiert kein A mit ∆ ` A und ∆ ` ¬A. D.h. fur jedebeliebige Formel B gilt entweder ∆ 6` B oder ∆ 6` ¬B. Wenn ∆ 6` B, dann ist Bdie gesuchte Formel, ansonsten ¬B.
“⇐” Mit Kontraposition. Wenn ∆ nicht konsistent ist, dann existiert ein A mit ∆ ` Aund ∆ ` ¬A. Dann ist mit der ¬ -Beseitigungsregel (¬B) jede Formel aus ∆ableitbar. D.h. es gibt keine Formel A mit ∆ 6` A. q.e.d.
q.e.d.
142 / 230
Eine Einfuhrung in die klassische Logik
Konsistenz und Inkonsistenz
Behauptung
Wenn ∆ 6` A, dann ist ∆ ∪ {¬A} syntaktisch konsistent.
Beweis. Wenn ∆ ∪ ¬A syntaktisch inkonsistent ist, dann gibt es eineFormel B mit ∆ ∪ {¬A} ` B und ∆ ∪ {¬A} ` ¬B. Aber dann ist A aus ∆ableitbar:
∆, [¬A]1....B
∆, [¬A]1....¬B
A(¬B)∗ 1
q.e.d.
Die Gegenrichtung gilt ebenfalls, wie leicht durch Anwendung von (¬B)gezeigt werden kann. Wir werden spater sehen, dass eine Formelmengegenau dann semantisch konsistent ist, wenn sie syntaktisch konsistent ist.
143 / 230
Eine Einfuhrung in die klassische Logik
Ableitungsregeln fur die Aquivalenz
Das Beweissystem SN enthalt keine Einfuhrungs- und Beseitigungsregelnfur die Aquivalenz. Das ist kein gravierendes Defizit, da die Aquivalenz eindefinierbarer Junktor ist.
Andererseits lassen sich leicht Einfuhrungs- und Beseitigungsregeln fur dieAquivalenz formulieren:
∆, [B]....A
Γ, [A]....B
(A ≡ B)(≡ E )
∆....A
Γ....(A ≡ B)
B(≡ B)
∆....B
Γ....(A ≡ B)
A(≡ B)
144 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
Satz
Das Beweissystem SN ist korrekt bezuglich der Klasse alleraussagenlogischen Modelle: ∆ `SN
A impliziert ∆ |= A.
Beweis. Mit Induktion uber den Aufbau der Ableitungen. Jede Formel A isteine Ableitung von A aus {A}, und offensichtlich gilt {A} |= A. Es ist nochzu zeigen, dass jede Ableitungsregel von logisch gultigenSchlussfolgerungen zu einer logisch gultigen Schlussfolgerung fuhrt. Das istaber, wie man leicht sieht, der Fall. q.e.d.
145 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
Lemma
Angenommen, A und B sind aussagenlogische Formeln in disjunktiver Normalform(DNF). Dann gilt:1. A ∧ B ist wechselseitig ableitbar mit einer Formel in DNF;2. ¬A ist wechselseitig ableitbar mit einer Formel in DNF;3. A ⊃ B ist wechselseitig ableitbar mit einer Formel in DNF;4. A ≡ B ist wechselseitig ableitbar mit einer Formel in DNF.
Aus diesem Lemma folgt:
Lemma
Jede aussagenlogische Formel ist wechselseitig ableitbar mit einer Formelin DNF.
146 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
Beweis. 1. Mit Induktion uber den Aufbau von A ∧ B.Basisschritt. A und B sind beide Aussagebuchstaben. Dann befindet sich A∧B inDNF.Aufbauschritt. A und B sind nicht beide Aussageb. aber Basiskonj.(Fall (i)) oder mindestens eine der zwei Formeln ist keine Basiskonj., sondern eineDisjunktion aus Formeln in DNF (Fall (ii)).(i). Wenn A und B beides Basiskonj. sind, dann ist A ∧ B in DNF.(ii). Sei A keine Basiskonjunktion. Dann hat A die Gestalt C ∨D, wobei C und Dsich in DNF befinden. Die folgenden Formeln sind wechselseitig ableitbar:
(C ∨ D) ∧ B (C ∧ B) ∨ (D ∧ B)
Mit der Induktionsannahme ist sowohl (C ∧ B) als auch (D ∧ B) wechselseitigableitbar mit einer (nicht notwendigerweise derselben) Formel in DNF. Damit ist(C ∧ B) ∨ (D ∧ B) wechselseitig ableitbar mit einer Disjunktion aus Formeln inDNF und damit wechselseitig ableitbar mit einer Formel in DNF. Schließlich istdamit auch (C ∨ D) ∧ B wechselseitig ableitbar mit einer Formel in DNF.
Der Fall, dass B keine Basiskonjunktion ist, ist ahnlich.
147 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
2. Mit Induktion uber den Aufbau von A.Basisschritt. Wenn A ein Aussagebuchstabe ist, dann ist ¬A in DFN.Aufbauschritt. A hat die Gestalt (i) ¬C , oder (ii) C ∨ D oder (iii) C ∧ D.(i). ¬C ist nur dann in DNF, wenn C ein Aussagebuchstabe ist. Die Formel ¬¬Cist wechselseitig ableitbar mit C .(ii) C ∨ D ist nur dann in DNF, wenn sowohl C als auch D in DNF ist. Mit derInduktionsann. sind sowohl ¬C als auch ¬D wechsels. ableitbar mit Formeln inDNF (d.h. die Vorauss. des Lemmas ist erfullt). Die Formel ¬(C ∨ D) istwechsels. ableitbar mit ¬C ∧ ¬D, und letztere Formel ist mit Beh. 1. des Lemmaswechselseitig ableitbar mit einer Formel in DNF.(iii) C ∧ D befindet sich nur dann in DNF, wenn C und D Basiskonj. und damitFormeln in DNF sind. Mit der Induktionsann. sind sowohl ¬C als auch ¬Dwechsels. ableitbar mit Formeln in DNF. Damit ist auch ¬C ∨ ¬D wechselseitigableitbar mit einer Disjunktion aus Formeln in DNF, und damit ist ¬C ∨ ¬Dwechsels. ableitbar mit einer Formel in DNF. Aber ¬C ∨ ¬D istwechsels. ableitbar mit ¬(C ∧ D).3. und 4.: Mit Induktion ber den Aufbau von A ⊃ B bzw. A ≡ B. q.e.d.
148 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
Satz
(Theoremvollstandigkeit) Wenn ∅ |= A, dann ∅ `SNA.
Beweis. Angenommen, jedes aussagenlogische Modell v ist ein Modell vonA, d.h. V (A) = W fur jede Belegung v . Es existiert eine Formel B inDNF, die wechselseitig ableitbar ist mit ¬A. Da angenommen wird, dass Aeine Tautologie ist, und da SN korrekt ist, ist B kontradiktorisch. Da Bsich in DNF befindet, enthalt jede maximale Basiskonjunktion in B einenAussagebuchstaben p und dessen Negation ¬p. Durch Anwendungen derRegeln (∧B) und (¬B) ist damit aus jeder maximalen Basiskonjunktionfur eine bestimmte Formel C , (C ∧ ¬C ) ableitbar. Damit ist aus B mitHilfe von (∨B) die Formel (C ∧ ¬C ) ableitbar. Da B aus ¬A ableitbar ist,ist (C ∧¬C ) aus ¬A ableitbar. Mit der Regel (¬B)∗ erhalten wir ∅ `SN
A.q.e.d.
149 / 230
Eine Einfuhrung in die klassische Logik
Korrektheit und Vollstandigkeit von SN
Satz
(Kompaktheit) Wenn ∆ |= A, dann existiert eine endliche Teilmenge Γ von∆, so dass Γ |= A.
Satz
((starke) Vollstandigkeit) Wenn ∆ |= A, dann ∆ `SNA.
Beweis. Angenommen ∆ |= A. Mit dem Kompaktheitssatz folgt A gultigaus endlich vielen A1,A2, . . . ,An aus ∆. Dann gilt∅ |= A1 ⊃ (A2 ⊃ (. . . ⊃ A) . . .). Aufgrund der Theoremvollst. folgt
∅ `SNA1 ⊃ (A2 ⊃ (. . . ⊃ A) . . .).
Eine n-fache Anwendung der Implikationsbes.regel liefert:
{A1, . . . ,An} `SNA
und damit ∆ `SNA. q.e.d.
150 / 230
Eine Einfuhrung in die klassische Logik
Kompaktheit
Behauptung
∆ |= A genau dann, wenn ∆ ∪ {¬A} nicht erfullbar ist.
Beweis.“⇐” Mit Kontraposition. Angenommen ∆ 6|= A. Dann gibt es ein Modell M mitM |= ∆ und M 6|= A. Letzteres impliziert M |= ¬A. M.a.W., M |= ∆ ∪ {¬A}.“⇒” Mit Kontraposition. Angenommen, es gibt ein Model M mit
M |= ∆ ∪ {¬A}. Dann gilt M |= ∆ und M 6|= A, und somit ∆ 6|= A. q.e.d.
Angenommen, wenn jede endliche Teilmenge einer Formelmenge ∆ erfullbar ist,
dann ist ∆ erfullbar. Wenn nun ∆ |= A, dann ist ∆ ∪ {¬A} unerfullbar und damit
gilt fur jedes endliche Γ ⊆ ∆: Γ ∪ {¬A} ist unerfullbar, d.h., Γ |= A.
151 / 230
Eine Einfuhrung in die klassische Logik
Kompaktheit
Beweis des Kompatkheitssatzes. Es genugt es zu zeigen:Wenn jede endliche Teilmenge einer Formelmenge ∆ erfullbar ist, dann ist ∆erfullbar.
Sei vn eine Funktion, die den ersten n (n ≥ 1) Aussagebuchstaben aus der Folgep0, p1, p2, . . . einen der Werte W oder F zuordnet. v0 = ∅. Die Eigenschaft E vonvn sei wiefolgt definiert:
E (vn) gdw Fur jedes endliche Γ ⊆ ∆ existiert ein Modellv , das mit vn in der Zuordnung von Wahr-heitswerten zu p0, p1, . . . , pn−1 ubereinstimmtund v |= Γ
E (v0) besagt: Fur jedes endliche Γ ⊆ ∆ existiert ein Modell v mit v |= Γ.
152 / 230
Eine Einfuhrung in die klassische Logik
Kompaktheit
Angenommen, wir haben vn mit E (vn) konstruiert. Wir konstruieren vn+1 mitE (vn+1) wie folgt. Wenn vn ∪ {(pn,W)} die Eigenschaft E besitzt, setzen wirvn+1 = vn ∪ {(pn,W)}. Ansonsten setzen wir vn+1 = vn ∪ {(pn,F)} und zeigen(*): dass vn+1 = vn ∪ {(pn,F)} die Eigenschaft E hat, wenn vn+1 = vn ∪{(pn,W)} die Eigenschaft E nicht besitzt.
(*): Sei vn+1 = vn ∪ {(pn,W)} und gelte E (vn+1) nicht. Dann existiert eine
endl. Teilmenge Θ von ∆, wobei fur jedes Modell v , das mit vn+1 ubereinstimmt
gilt (**) v 6|= Θ. Sei Ψ eine beliebige endl. Teilmenge von ∆. Da Θ ∪Ψ endlich
ist und E (vn) gilt, existiert ein Modell v ′, das mit vn (in der Zuordnung von
Wahrheitsw. zu p0, p1, . . . , pn−1) ubereinstimmt und fur das gilt: v ′ |= Θ ∪Ψ.
Angenommen, v ′(pn) = W. Dann stimmt v ′ mit vn+1 uberein und v ′ |= Θ:
Widerspruch zu (**). D.h., v ′(pn) = F, und fur vn+1 = vn ∪ {(pn,F)} stimmt v ′
mit vn+1 in der Zuordnung von Wahrheitsw. zu p0, p1, . . . , pn uberein, und es gilt
v ′ |= Ψ. Aber Ψ war eine beliebige Teilmenge von ∆. D.h., fur jedes endl. Ψ ⊆ ∆
existiert ein Modell v ′, das mit vn+1 in der Zuordnung von Wahrheitsw. zu
p0, p1, . . . , pn ubereinstimmt und so dass gilt v ′ |= Ψ. M.a.W., E (vn+1).
153 / 230
Eine Einfuhrung in die klassische Logik
Kompaktheit
Wir konnen also eine Folge v0, v1, v2, . . . konstruieren, so dass fur jedes vn
gilt E (vn) und vn+1 stimmt mit vn in der Zuordnung von Wahrheitswertenzu p0, p1, . . . , pn−1 uberein. Sei nun
v =⋃n∈N
vn (= {a | a ∈ vn fur mindestens ein n ∈ N}).
Die Funktion v stimmt also mit allen vn in der Zuordnung vonWahrheitswerten uberein. Es zeigt sich, dass v |= ∆. Sei A irgendeinbeliebiges Element von ∆. Sei pm derjenige Aussagebuchstabe in A mitdem hochsten Index. Da E (vm+1) und v mit vm+1 in der Zuordnung vonWahrheitswerten zu p0, p1, . . . , pm ubereinstimmt, gilt v |= Γ fur jedesendliche Γ ⊆ ∆. Da {A} endlich ist, gilt v |= A, und da A ein beliebigesgewahltes Element von ∆ ist, gilt v |= ∆. q.e.d.
154 / 230
Eine Einfuhrung in die klassische Logik
Pradikatenlogik
Beispiele:
Aristotelische Syllogismen:
Jeder Parlamentarier ist intelligent. Jeder P ist I .Max ist Parlamentarier. m ist P.Max ist intelligent m ist I .
Kein Professor ist vergesslich.Arthur ist vergesslich.
Arthur ist kein Professor.
155 / 230
Eine Einfuhrung in die klassische Logik
Pradikatenlogik
Beispiele fur Zuschreibungen von Eigenschaften und Beziehungen:
P1(a) Arthur ist Parlamentarier.S2(p,m) Peter sucht Marie.S2(m, p) Marie sucht Peter.L2(p, p) Peter liebt Peter.L2(p, p) Peter liebt sich selbst.Z 3(a, l , b) Amsterdam liegt zwischen London
und Berlin.
156 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Naturliche Sprache Pradikatenlogische Sprache
Eigennamen Individuenkonstanten- Erik, Marie, Hans - e, m, h
Verben, Pradikate Pradikatsymbole
- . . . ist klug, . . . lacht - K 1, L1, einstellig- . . . liebt−−−, . . . sucht−−− - L2, S2, zweistellig- . . . liegt zwischen−−− und ∗∗∗ - L3, dreistellig
funktionale Ausdrucke Funktionssymbole
- die Hauptstadt von . . . - h1, einstellig- der einzige Sohn von . . . und −−− - s2, zweistellig
naturlichsprachliche Quantoren Quantoren- alle, jeder, jedes Ding - ∀- ein, einige, irgendein, jemand, etwas - ∃
Individuenvariablen- x , y , z
157 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Wenn die Stelligkeit von Pradikatsymbolen (Relationsausdrucken) klar ist,schreiben wir statt Rn(t1, . . . , tn) oft auch einfach R(t1, . . . , tn).
Sprachliche Ausdrucke vom syntaktischen Typ der Eigennamen heißenTerme. Es gibt naturlichsprachliche Terme, die keine echten Eigennamensind:
“Maries Mutter”, “die Hauptstadt von Frankreich”
“das Fahrrad von Peters Mutter” f 1(m1(p))
Quantoren:
- der Allquantor ∀ “fur jedes Objekt”∀x “fur jedes Objekt x”
- der Existenzquantor ∃ “es gibt mindestens einObjekt”
∃x “es gibt mindestens einObjekt x”
158 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Beispiele:
(1) Alles ist intelligent.∀x I 1(x)
(2) Jeder Delphin ist intelligent.∀x (D1(x) ⊃ I 1(x))
(3) Es gibt etwas intelligentes.∃x I 1(x)
(4) Es gibt einen intelligenten Professor.∃x (I 1(x) ∧ P1(x))
(5) Jemand sucht jemanden.∃x ∃y S2(x , y)
(6) Einige Menschen sind nett.∃x (M(x) ∧ N(x))
159 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Beispiele:
(7) Alle Delphine sind Fische.∀x (D(x) ⊃ F (x))
(8) Es gibt Menschen, die nicht nett sind.∃x (M(x) ∧ ¬N(x))
(9) Kein Politiker lugt.¬∃x (P(x) ∧ L(x))
(10) Jemand sucht sich selbst.∃x S(x , x)
(11) Jeder Mann liebt irgendeine Frau.∀x (M(x) ⊃ ∃y (F (y) ∧ L(x , y)))
(12) Es gibt einen Mann, der von jeder Frau geliebt wird.∃x (M(x) ∧ ∀y (F (y) ⊃ L(y , x)))
160 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Was ist die Rolle der Individuenvariablen?
Wozu brauchen wir Individuenvariablen?
Unterscheidung von Aktiv- und Passivkonstruktionen∃x∀yL(x , y) versus ∃x∀yL(y , x)
Ubersetzung von Satzen mit Reflexivpronomia∃xL(x , x)
Ubersetzung von Relativsatzen∃x (M(x) ∧ ¬N(x))
allgemein: Offenlegung von Quantifikationsmustern.
161 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Beispiele:
Jeder Mann liebt irgendeine Frau. Jeder Mann wird vonirgendeiner Frau geliebt.
� � � �� �
∀x (M(x) ⊃ ∃y (F (y) ∧ L(x, y)))
∀ (M( ) ⊃ ∃ (F ( ) ∧ L( , )))
� � � �� �
∀x (M(x) ⊃ ∃y (F (y) ∧ L(y, x)))
∀ (M( ) ⊃ ∃ (F ( ) ∧ L( , )))
Individuenvariablen sind Platzhalter, die angeben, auf welcheArgumentstellen von Pradikat- und Funktionssymbolen sich Quantorenbeziehen.
162 / 230
Eine Einfuhrung in die klassische Logik
Das Alphabet der Sprache der Pradikatenlogik
Definition
Das Alphabet der Sprache der Pradikatenlogik besteht aus:
abzahlbar unendlich vielen Individuenkonstanten:a, b, c, . . . , r , s a1, a2, a3, . . .
Pradikatsymbolen: An,An1,A
n2,A
n3, . . . Bn,Bn
1 ,Bn2 , . . .
Funktionssymbolen: f n, f n1 , f
n2 , f
n3 , . . . g n, g n
1 , gn2 , . . .
den logischen Symbolen: ¬,∧,∨,⊃,≡,∃,∀Individuenvariablen: x , y , z x1, x2, . . .
Hilfszeichen: (, ) und das Komma
dem Identitatssymbol (einem gesondert aufgefuhrten zweistelligenPradikatsymbol): =
163 / 230
Eine Einfuhrung in die klassische Logik
Die Terme der Sprache der Pradikatenlogik
Definition
Die Menge der Terme der Sprache der Pradikatenlogik ist wie folgtinduktiv definiert:
(i) Alle Individuenvariablen und –konstanten sind Terme.
(ii) Wenn f k ein k-stelliges Funktionssymbol ist und t1, . . . , tk Termesind, dann ist auch f k (t1, . . . , tk ) ein Term.
(iii) Nichts anderes ist ein Term.
Ein Term, in dem keine Variablen vorkommen, heißt geschlossen. Wirverwenden die Symbole t1, t2, t3, . . . als (metasprachliche) Variablen furTerme.
164 / 230
Eine Einfuhrung in die klassische Logik
Die Formeln der Sprache der Pradikatenlogik
Definition
Die Menge der Formeln der Sprache der Pradikatenlogik ist wie folgtinduktiv definiert:
(i) Wenn Pn ein n-stelliges Pradikatsymbole ist und t1, . . . , tn Termesind, dann ist Pn(t1, . . . , tn) eine Formel.
(ii) Wenn t1 und t2 Terme sind, dann ist (t1 = t2) eine Formel.
(iii) Wenn A und B Formeln sind, dann sind auch ¬A,(A ⊃ B), (A ∧ B), (A ∨ B), (A ≡ B) Formeln.
(iv) Wenn A eine Formel und x eine Individuenvariable ist, dann sind ∃xAund ∀xA Formeln.
(v) Nichts anderes ist eine Formel.
Formeln der Gestalt Pn(t1, . . . , tn) und (t1 = t2) heißen atomare Formeln.
165 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Pradikatenlogische Sprachen werden z.B. dadurch erhalten, dass nur einegewisse endliche Anzahl von Pradikat- und Funktionssymbolen mitbestimmter Stelligkeit verwendet wird.
Eine pradikatenlogische Sprache L wird durch ihre Signatur σ(L)festgelegt. Eine Signatur gibt an, wieviele Relationssysmbole undFunktionssymbole welcher Stelligkeit und wieviele Individuenkonstanten inL verwendet werden. Werden in einer Sprache L z.B. nur zwei zweistelligeRelationssymbole, ein einstelliges Funktionssymbol und dreiIndividuenkonstatnen verwendet, ist die Signatur σ(L) = (2,2;1;3). DieInterpretation der Relationssysmbole, Funktionssymbole undIndividuenkonstanten kann von Modell zu Modell variieren.
166 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Definition
Der Bereich (Skopus) des anfanglichen Vorkommens des Allquantors ∀ in∀xA (des Existenzquantors ∃ in ∃xA) ist die Symbolreihe xA.Ein Vorkommnis einer Variablen x in einer pradikatenlgischen Formel Aheißt frei, wenn dieses Vorkommnis von x nicht im Bereich einesVorkommnisses eines Quantors ∀ oder ∃ liegt. Ansonsten wird dasVorkommnis von x als (durch ∀ oder ∃) gebunden bezeichnet.Wenn x in A frei (gebunden) vorkommt, dann heißt x freie (gebundene)Variable von A.Eine pradikatenlogische Formel heißt offen, wenn sie mindestens eine freieVariable enthalt, ansonsten heißt sie geschlossen. Eine geschlossene Formelwird gelegentlich auch als Satz bezeichnet.
167 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Beispiele:
Formel freie Var. wahrheitsfahig
∀y L(x, y) x nein, da offen∀x (M(x) ⊃ ∃y L(x , y)) keine ja, da geschlossen∀x M(x) ⊃ ∃y L(x, y) x nein
Wir schreiben A(x1, . . . , xn), um mitzuteilen, dass die Formel A dieVariablen x1, . . . , xn als freie Variablen enthalt.
168 / 230
Eine Einfuhrung in die klassische Logik
Ubersetzungen in die Pradikatenlogik
Definition
Geschlossene Formeln vom Typ ∀xA(x) heißen Allbehauptungen,Geschlossene Formeln vom Typ ∃xA(x) Existenzbehauptungen.
Existenzbehauptungen, in denen der Bereich der Objekte, uber die eineExistenzbehauptung gemacht wird, eingeschrankt wird, sind verdeckteKonjunktionen.
Beispiel: Einige Menschen sind sterblich. 7→ ∃x(M(x) ∧ S(x))
Semantische Erklarung: Wenn das Pradikatsymbol M interpretiert wird als dieMenge aller Menschen (= I(M)), d.h., wenn dem Ausdruck M die Menge allerMenschen als bezeichneter Gegenstand zugeordnet wird, und wenn S interpretiertwird als die Menge der sterblichen Objekte (= I(S)), dann besagt “EinigeMenschen sind sterblich” offenbar, dass die Menge der Objekte, die menschlichund sterblich sind, nicht leer ist:
I(M) ∩ I(S) = {x | x ∈ I(M) und x ∈ I(S)} 6= ∅
169 / 230
Eine Einfuhrung in die klassische Logik
Ubersetzungen in die Pradikatenlogik
Allbehauptungen, in denen der Bereich der Objekte, uber die eineAllbehauptung gemacht wird, eingeschrankt wird, sind verdeckteImplikationen.
Beispiel: Alle Menschen sind sterblich. 7→ ∀x(M(x) ⊃ S(x))
Semantische Erklarung: Wenn das Pradikatsymbol M interpretiert wird alsdie Menge aller Menschen (= I(M)), d.h., wenn dem Ausdruck M dieMenge aller Menschen als bezeichneter Gegenstand zugeordnet wird, undwenn S interpretiert wird als die Menge der sterblichen Objekte (= I(S)),dann besagt “Alle Menschen sind sterblich” offenbar, dass jedes Objektsterblich ist, wenn es menschlich ist:
I(M) ⊆ I(S)
170 / 230
Eine Einfuhrung in die klassische Logik
Desambiguierung durch Ubersetzung
Jeder Mann liebt eine Frau.
���
��+
QQQQs
Jeder Mann liebt irgend-eine Frau.
Es gibt eine Frau, diejeder Man liebt.
∀x (M(x) ⊃ ∃y (F (y) ∧ L(x , y))) ∃y (F (y) ∧ ∀x (M(x) ⊃ L(x , y)))
171 / 230
Eine Einfuhrung in die klassische Logik
Ubersetzungen in die Pradikatenlogik
Frage: Bedeuten in den folgenden Paaren von Formeln (a) und (b) intuitivjeweils dasselbe?
(a) ∀x (M(x) ⊃ ∃y L(x , y)) (b) ∀x (M(x) ⊃ ∃z L(x , z))
(a) ∀x (M(x) ⊃ ∃y L(x , y)) (b) ∀x (M(x) ⊃ ∃x L(x , x))
(a) ∀x M(x) ⊃ ∃y L(a, y) (b) ∀x M(x) ⊃ ∃x L(a, x)
172 / 230
Eine Einfuhrung in die klassische Logik
Ubersetzungen in die Sprache der Pradikatenlogik
Es gibt einen Typus von Satzen naturlicher Sprachen, die, obschon sie aufden ersten Blick unauffallig und unkompliziert zu sein scheinen, nicht derOberflachensyntax folgend angemessen in pradikatenlogische Formelnubersetzbar sind. Diese Satze heißen Eselssatze, weil die meistdikutiertenBeispiele fur derartige Satze Variationen auf folgende Beispiele sind:
Wenn eine Bauerin einen Esel besitzt, dann schlagt sie ihn.Eine Bauerin, die einen Esel besitzt, schlagt ihn.
Die Ubersetzungsprobleme mit diesen Satzen entstehen durch dieanaphorische Verwendung von Personalpronomina. Hier ist ein etwaseinfacheres Beispiel, in dem nur ein Personalpronomen anaphorischverwendet wird.
(*) Wenn jemand von Rudolf beeinflusst wird, wird ervon Bertrand beinflusst.
173 / 230
Eine Einfuhrung in die klassische Logik
Ubersetzungen in die Sprache der Pradikatenlogik
Die folgenden Ubersetzungen sind inadaquat:
1. ∃xB(r , x) ⊃ B(b, x)
2. ∃x(B(r , x) ⊃ B(b, x))
3. ∃xB(r , x) ⊃ ∃xB(b, x)
Formel 1. ist eine offene Formel und deshalb kein deklarativer Ausdruck,wohingegen (*) jedoch ein Deklarativsatz ist.Die geschlossene Formel 2. ist eine Existenzbehauptung, aber (*) ist keineExistenzbehauptung sondern eine Implikation.Ubersetzung 3. ist sowohl geschlossen als auch eine Implikation, aber trotzdemkeine angemessene Ubersetzung von (*), weil 3. soviel besagt wie Wenn jemandvon Rudolf beeinflusst wird, dann wird jemand von Bertrand beeinflusst. DerRuckbezug von er auf das durch den Quantor jemand als existent eingefuhrteIndividuum wird durch 3. nicht erfasst.
Korrekt ist offenbar die folgende, den Allquantor verwendende Ubersetzung:
∀x(B(r , x) ⊃ B(b, x)).
174 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Pradikatenlogische Formeln werden interpretiert in Strukturen
D = 〈D,R,O〉,
wobei
D ein nicht-leerer Individuenbereich ist, d.h. eine nicht-leere Menge vonGegenstanden (alias Objekten, Individuen)
R eine Menge von Relationen zwischen Objekten aus D ist und
O eine Menge von Operationen (d.h. Funktionen) ist, die auf D definiertsind.
Falls D unendlich ist heißt auch D unendlich.
175 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Pradikatenlogische Formeln werden in einer Struktur 〈D,R,O〉interpretiert durch eine Interpretationsfunktion I:
I ordnet jeder Individuenkonstante a genau ein Objekt I(a) ∈ D zu,
I ordnet jedem einstelligen Pradikatsymbol P1 eineTeilmenge von D zu (die Objekte mit der durch P1
bezeichneten Eigenschaft). I(P1) ⊆ D,I ordnet jedem k-stelligen Pradikatsymbol Pk (k > 1) eine k-stelligeRelation zu (die Menge der k-Folgen vonObjekten, die in der durch Pk bezeichneten Relationzueinander stehen). I(Pk ) ⊆ Dk ,
I ordnet jedem k-stelligen Funktionssymbol f k einek-stellige Funktion zu, die uber D definiert ist.
176 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Einstellige Pradikatsymbole, d.h., Ausdrucke zur Bezeichnung vonEigenschaften, werden durch Mengen interpretiert. Eigenschaften werdenals Mengen aufgefasst. (Dies wird auch die extensionale Auffassung vonEigenschaften genannt.) Allgemein werden n-stellige Pradikatsymbole,d.h., Ausdrucke zur Bezeichnung n-stelliger Beziehungen, durch Mengenvon n-Tupeln interpretiert. (Mengen werden als einstellige Relationenaufgefasst.)
Definition
Ein Paar M = 〈D, I〉 wird ein pradikatenlogisches Modell genannt.
177 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Wenn die Menge der Relationen, der Operationen und der Funktioneneiner Struktur jeweils endlich ist und wenige Elemente enthalt, werdendiese Elemente auch explizit aufgelistet.
Beispiele:
D = 〈N, <,+〉
Diese Struktur ist geeignet, um eine zweistelliges Pradikatsymbol P undein zweistelliges Funktionssymbol f zu interpretieren. I(P) = <, I(f ) =die Additionsoperation uber N.
D = 〈Familie Muller, {x | x wohnt in Bochum},{〈x , y〉 | x ist Mutter von y}, {〈x , y〉 | x ist Bruder von y}〉
Diese Struktur ist geeignet, um ein einstelliges und zwei zweistelligePradikatsymbole zu interpretieren.
178 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Gesucht ist eine Wahrheitsdefinition fur pradikatenlogische Formeln, diedas Kompositionalitatsprinzip erfullt.
Beispiel: Die Wahrheit von ∃xP(x) in einem Modell hangt allein undeindeutig ab von der Wahrheit von P(x) in dem Modell.Aber: P(x) ist eine offene Formel, und x bezeichnet nichts.
Losung des Problems: Tarskis Wahrheitsdefinition
Da Individuenvariablen nichts bezeichnen, werden fur jedes Modell‘Hilfsinterpretationen’ der Variablen eingefuhrt, so dass relativ zu einersolchen Hilfsinterpretation jede Variable ein Objekt aus demIndividuenbereich denotiert.
179 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Definition
Eine Belegung α in D ist eine Funktion, die jeder Individuenvariable x einObjekt α(x) ∈ D zuordnet.
Mit α[d/x ] (lies: “α mit d fur x”) bezeichnen wir diejenige Belegung, diesich von α hochstens dadurch unterscheidet, dass der Variablen x dasObjekt d zugeordnet wird.
Mit Hilfe von I und einer Belegung α konnen wir jetzt zunachstdefinieren, was der semantische Wert eines beliebigen Terms t in einempradikatenlgischen Modell M unter der Belegung α ist. Wir schreibendafur:
VM,α(t).
180 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Definition
Sei M = 〈D, I〉 ein Modell und α eine Belegung in D. Der semantischeWert von Termen ist wie folgt induktiv definiert:
VM,α(x) = α(x), fur Individuenvariablen x ,
VM,α(b) = I(b), fur Individuenkonstanten b,
VM,α(f (t1, . . . , tn)) = I(f )(VM,α(t1), . . . ,VM,α(tn)).
Beispiel:Sei M = 〈D, I〉 ein Model, D = 〈N,+〉, I(f ) = die Addition uber N, undI(a) = 3. Sei α eine Belegung in D mit α(x) = 9. Dann gilt:
VM,α(f (x , a))= I(f )(VM,α(x),VM,α(a))= I(f )(α(x), I(a))= +(9, 3)= 9 + 3 = 12
181 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Definition
Sei M = 〈D, I〉 ein Modell und α eine Belegung in D. Der Wahrheitswerteiner pradikatenlogischen Formel in M unter der Belegung α ist wie folgtinduktiv definiert:
(i) VM,α(P(t1, . . . , tn)) = W gdwI(P)(VM,α(t1), . . . ,VM,α(tn)),VM,α((t1 = t2)) = W gdw VM,α(t1) = VM,α(t2),
(ii) VM,α(¬A) = W gdw VM,α(A) = F ,
(iii) VM,α(A ∧ B) = W gdw VM,α(A) = VM,α(B) = W ,
(iv) VM,α(∃xA) = W gdw es gibt ein d ∈ D, so dassVM,α[d/x](A) = W ,
(v) VM,α(∀xA) = W gdw fur alle d ∈ D gilt: VM,α[d/x](A) = W .
Anstelle von VM,α(A) = W schreiben wir auch M, α |= A.
182 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Beispiel: Sei M = 〈D, I〉 ein Model mit D = 〈N, <〉 und I(R) = <. Sei α eineBelegung in D mit α(y) = 5. Dann gilt:
M, α |= ∀x(R(y , x) ⊃ ∃zR(x , z))
gdw fur alle n ∈ N :M, α[n/x ] |= (R(y , x) ⊃ ∃zR(x , z))
gdw fur alle n ∈ N : (wennM, α[n/x ] |= R(y , x), dannM, α[n/x ] |= ∃zR(x , z))
gdw fur alle n ∈ N : (wenn I(R)(VM,α[n/x](y),VM,α[n/x](x)),dann existiert m ∈ N, mitM, α[n/x ][m/z ] |= R(x , z))
gdw fur alle n ∈ N : (wenn < (5,VM,α[n/x](x)), dannexistiert m ∈ N, mitI(R)(VM,α[n/x][m/z](x),VM,α[n/x][m/z](z)))
gdw fur alle n ∈ N : (wenn < (5,VM,α[n/x](x)), dannexistiert m ∈ N, mit < (n,m))
gdw fur alle n ∈ N : (wenn 5 < n, dann existiert m ∈ N, mit n < m)
∀x(R(y , x) ⊃ ∃zR(y , z)) ist wahr in M unter α:
M, α |= ∀x(R(y , x) ⊃ ∃zR(y , z)).183 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Fur alle Modelle M = 〈D, I〉 und Belegungen α in D gilt:
M, α |= ∀xA ≡ ¬∃x¬A
M, α |= ∃xA ≡ ¬∀x¬A
Definition
Eine pradikatenlogische Formel A heißt gultig in einem ModellM = 〈D, I〉 (symbolisch M |= A) genau dann, wenn A wahr ist in Munter jeder Belegung in D. Die Formel A heißt allgemeingultig (symbolisch|= A) genau dann, wenn A gultig ist in jedem pradikatenlogischen Modell.
Definition
Zwei pradikatenlogische Formeln A und B heißen logisch aquivalent genaudann, wenn |= A ≡ B.
184 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Eine Ubersetzung des Syllogismus
Alle Menschen sind sterblich.Platon ist ein Mensch.
Platon ist sterblich.
in pradikatenlogisches Vokabular macht eine Sprache L mit Signaturσ(L) = (1, 1;−; 1) erforderlich.
In pradikatenlogischen Formeln lasst sich die Schlussfolgerung als
∀ x(M(x) ⊃ S(x)),M(a) / S(a)
ubersetzen. Diese Schlussfolgerung ist gultig genau dann, wenn((∀ x(M(x) ⊃ S(x)) ∧M(a)) ⊃ S(a)) allgemeingultig ist.
185 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Sei M ein Modell passend zur Signatur σ(L) mit M =(D, {I(S), I(M)},∅, I), wobei I(a) ∈ D und I(S), I(M) ⊆ D. Die Wahlder Belegung β ist irrelevant, da es sich bei der betrachteten Formel umeinen Satz handelt. Dann gilt:
M, β|=((∀ x(M(x) ⊃ S(x)) ∧M(a)) ⊃ S(a))
gdw [wenn M, β|=∀ x(M(x) ⊃ S(x)) und M, β|=M(a)], dann M, β|=S(a)gdw [wenn fur alle d ∈ D gilt, falls M, β[d/x ]|=M(x), dann M, β[d/x ]|=S(x),
und I(a) ∈ I(M)], dann I(a) ∈ I(S)gdw [wenn fur alle d ∈ D gilt, falls β[d/x ](x) ∈ I(M), dann β[d/x ](x) ∈ I(S),
und I(a) ∈ I(M)], dann I(a) ∈ I(S)gdw [wenn fur alle d ∈ D gilt, falls d ∈ I(M), dann d ∈ I(S), und I(a) ∈ I(M)],
dann I(a) ∈ I(S)gdw [wenn I(M) ⊆ I(S) und I(a) ∈ I(M)], dann I(a) ∈ I(S)
186 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Die letzte Aussage ist offensichtlich gultig unabhangig von dem gewahltenModell, d.h. unabhangig von der Interpretation der auftretendenRelationssymbole und Konstanten. Es handelt sich um eineallgemeingultige Formel, also ist der betrachtete Syllogismus eine gultigeSchlussfolgerung.
Ein weiteres Beispiel: Die Signatur der Sprache ist σ(L) = (2; 2;−). EinModell M sei mit M = (N, {<},{+}, I) gegeben, wobei I(R) = < (={(x , y)|x < y} ⊆ N× N) und I(f ) = + (= {(x , y)|x + y ∈ N}) und I(a)= 0. Fur die Belegung β gelte β(z) = 4.
187 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Dann kann die folgende Formel in M unter β ausgewertet werden.M, β|=∀ x(R(z , x) ⊃ ∃ yR(x , f (z , y)))
gdw fur alle d ∈ D, wenn M, β[d/x ]|=R(z , x), dann M, β[d/x ]|=∃ yR(x , f (z , y))gdw fur alle d ∈ D, wenn I(R)(β[d/x ](z), β[d/x ](x)), dann existiert d ′ ∈ D mit
M, β[d/x ][d ′/y ]|=R(x , f (z , y))gdw fur alle d ∈ D, wenn 4 < d , dann existiert d ′ ∈ D mit
I(R)(β[d/x ][d ′/y ](x), I(f )(β[d/x ][d ′/y ](z), β[d/x ][d ′/y ](y))gdw fur alle d ∈ D, wenn 4 < d , dann existiert d ′ ∈ D mit d < 4 + d ′
Diess Aussage in wahr M unter β. Sie ist aber in M auch unter jederBelegung von z wahr, so dass ∀ x(R(z , x) ⊃ ∃ yR(x , f (z , y))) in M gultigist. Die Formel ist jedoch nicht allgemeingultig. Im Modell M′ =(N, {<}, {−}, I) mit I(f )(x , y) = x − y ist sie falsch, da die Aussage,dass fur alle d ∈ D, wenn β(z) < d , dann existiert d ′ ∈ D mitd < β(z)− d ′, fur mindestens eine Belegung β falsch ist. In M′ ist siesogar fur alle Belegungen falsch.
188 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Sei M = 〈D, I〉 ein Modell. Eine geschlossene Formel A ist wahr in Munter jeder Belegung in D genau dann, wenn A wahr ist in M unter einerBelegung in D.
Behauptung
Sei M = 〈D, I〉, seien x1, . . . , xn die freien Variablen derpradikatenlogischen Formel A, und seien α und β zwei Belegungen in Dmit α(xi ) = β(xi ); fur i = 1, . . . , n. Dann gilt:
M, α |= A gdw M, β |= A.
189 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Behauptung
|= ∀x(A ∧ B) ≡ (∀xA ∧ ∀xB)
|= ∃x(A ∨ B) ≡ (∃xA ∨ ∃xB)
|= ¬∀xA ≡ ∃x¬A
|= ¬∃xA ≡ ∀x¬A
|= ∀x∀yA ≡ ∀y∀xA
|= ∃x∃yA ≡ ∃y∃xA
|= ∀xA ≡ A, falls x nicht frei in A.
|= ∃xA ≡ A, falls x nicht frei in A.
Die Anordnung von Quantoren derselben Art ist also irrelevant, und einQuantorprafix Qx in QxA kann vernachlassigt werden, falls x in A nichtfrei vorkommt.
190 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Eine zentrale Rolle von Modellen ist ihre Rolle als Gegenbeispiele zuungultigen Schlussfolgerungen. Die folgenden Schlussfolgerungen z.B. sindoffensichtlich nicht gultig.
∀x(A(x) ∨ B(x))
∀xA(x) ∨ ∀xB(x)
∃xA(x) ∧ ∃xB(x)
∃x(A(x) ∧ B(x))
Ein Gegenbsp. zu beiden Schlussfolgerungen ist das Modell:
M = 〈D = {Hans,Fritz},R = { {Hans}, {Fritz} },O = ∅, I〉,
wobei I(A) = {Hans} und I(B) = {Fritz}.Die Relationenmenge R enthalt zwei 1-stellige Relationen, d.h. Eigenschaften,
d.h. Mengen von Objekten. Die durch das einstellige Relationssymbol A
bezeichnete Eigenschaft wird von Hans besessen; die andere, durch das einstellige
Relationssymbol B bezeichnete Eigenschaft hat Fritz.
191 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Auch die folgenden Schlussfolgerungen sind ungultig.
(∗) ∀xA(x) ⊃ ∀xB(x)
∀x(A(x) ⊃ B(x))
(∗∗) ∃xB(x) ⊃ ∃xA(x)
∃x(A(x) ⊃ B(x))
Ein Gegenbeispiel zu (∗) ist das obige Modell M.Ein Gegenbeispiel zu (∗∗) ist:
M′ = 〈D = {Hans,Fritz},R = { {Hans,Fritz}, ∅},O = ∅, I〉,
wobei I(A) = {Hans,Fritz} und I(B) = ∅.
192 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Endliche Modelle 〈D, I〉, in denen pradikatenlogische Formeln mit nureinem zweistelligen Pradikatsymbol (z.B. S) interpretiert werden, erlaubeneine einfache graphische Darstellung. Die Objekte des Individuenbereichskonnen z.B. durch Punkte wiedergegeben werden, und die durch Sbezeichnete Relation I(S) kann durch Pfeile angedeutet werden, z.B.:
v
vv6
���� v���
193 / 230
Eine Einfuhrung in die klassische Logik
Semantik der Pradikatenlogik
Die folgende Schlussfolgerung ist ungultig:
(∗ ∗ ∗) ∀x∃yS(x , y)
∃y∀xS(x , y)
Ein Gegenbeispiel ist:
vv
��� ��� 194 / 230
Eine Einfuhrung in die klassische Logik
Eigenschaften binarer Relationen
Definition
Eine zweistellige Relation R heißt
reflexiv gdw ∀xR(x , x)nicht-reflexiv gdw ∃x¬R(x , x)irreflexiv gdw ∀x¬R(x , x)
symmetrisch gdw ∀x∀y(R(x , y) ⊃ R(y , x))nicht-symmetrich gdw ∃x∃y(R(x , y) ∧ ¬R(y , x))asymmetrisch gdw ∀x∀y(R(x , y) ⊃ ¬R(y , x))antisymmetrisch gdw ∀x∀y((R(x , y) ∧ R(y , x)) ⊃ (x = y))
transitiv gdw ∀x∀y∀z((R(x , y) ∧ R(y , z)) ⊃ R(x , z))nicht-transitiv gdw ∃x∃y∃z((R(x , y) ∧ R(y , z)) ∧ ¬R(x , z))intransitiv gdw ∀x∀y∀z((R(x , y) ∧ R(y , z)) ⊃ ¬R(x , z))
seriell gdw ∀x∃yR(x , y)euklidisch gdw ∀x∀y∀z((R(x , y) ∧ R(x , z)) ⊃ R(y , z))konfluent gdw ∀x∀y∀z((R(x , y) ∧ R(x , z)) ⊃
∃u(R(y , u) ∧ R(z , u)))konnex (total) gdw ∀x∀y((R(x , y) ∨ R(y , x)) ∨ (x = y))
195 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Kann man in der Sprache der Pradikatenlogik ausdrucken, dass einezweistellige Relation uber einer Menge eine Funktion ist?
Eine zweistellige Relation R uber einer Menge X ist eine Teilmenge von{〈x , y〉 | x ∈ X und y ∈ X}. Die Relation ist eine Funktion, wenn fur jedesx aus X genau ein y aus X existiert, so dass 〈x , y〉 ∈ R.
Kann man “es gibt genau ein x” in der Sprache der Pradikatenlogikausdrucken? Und vielleicht auch “es gibt mindestens zwei x” und “es gibtgenau 2 x”? Kann man fur jede naturliche Zahl n ausdrucken “es gibtgenau n x”?
196 / 230
Eine Einfuhrung in die klassische Logik
Die Sprache der Pradikatenlogik
Es gibt mindestens einen Philosophen.∃xP(x)
Es gibt hochstens einen Philosophen.∀x∀y((P(x) ∧ P(y)) ⊃ (x = y))
Es gibt genau einen Philosophen.∃x(P(x) ∧ ∀y(P(y) ⊃ (x = y))) Abkurzung: ∃!xP(x)
Es gibt genau zwei Philosophen.∃x(P(x) ∧ ∃y((P(y) ∧ ¬(x = y)) ∧ ∀z(P(z) ⊃ ((z = x) ∨ (z = y))))
Definition
Eine zweistellige Relation R heißt funktional gdw ∀x∃!yR(x , y).
197 / 230
Eine Einfuhrung in die klassische Logik
Klassen relationaler Strukturen
Einige wichtige Klassen von Strukturen sind durch die Kombination mehrererrelationaler Eigenschaften definiert.
Definition
Eine nicht-leere Menge D mit einer zweistelligen Relation R uber D heißt
Praordnung gdw R reflexiv und transitiv istpartielle Ordnung gdw R reflexiv, transitiv
und anti-symmetrisch istlineare Praordnung gdw R reflexiv, transitiv und konnex istlineare Ordnung gdw R reflexiv, transitiv, anti-symmetrisch
und konnex iststrikte Ordnung gdw R irrreflexiv und transitiv ist
198 / 230
Eine Einfuhrung in die klassische Logik
Klassen relationaler Strukturen
Jede irreflexiv transitive Relation ist asymmetrisch, d.h., die folgendeSchlussfolgerung ist gultig:
∀x¬R(x , x)∀x∀y∀z((R(x , y) ∧ R(y , z)) ⊃ R(x , z))
∀x∀y(R(x , y) ⊃ ¬R(y , x))
199 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Frage: Ist jede pradikatenlogische Formel logisch aquivalent zu einerFormel, die aus einem Quantorprafix gefolgt von einer quantor-freienFormel besteht?
Definition
Eine pradikatenlogische Formel A ist in pranexer Normalform (PNF) genaudann, wenn A aus einer endlichen (eventuell) leeren Folge vonQuantorprafixen besteht, auf die eine quantorfreie Formel folgt. Wenn Asich in pranexer Normalform befindet, heißt A auch pranex.
Pranexe Formeln sind zerlegt in eine Kette von Quantifikationen gefolgtvon einem quantorfreien, Booleschen Teil:
Q1x1 . . .QnxnA,
wobei Q ∈ {∃, ∀} und A quantorfrei ist.
200 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wir hatten bereits gesehen, dass
|= ∀x(A ∧ B) ≡ (∀xA ∧ ∀xB)
|= ∃x(A ∨ B) ≡ (∃xA ∨ ∃xB)
Auch die folgenden Beispiele fur allgemeingultige Formeln sind instruktivfur ‘das Vorziehen’ von Quantoren.
Theorem
|= ∀x(A(x) ∨ B) ≡ (∀xA(x) ∨ B), falls x nicht frei in B vorkommt
|= ∃x(A(x) ∧ B) ≡ (∃xA(x) ∧ B), falls x nicht frei in B vorkommt
201 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Um von einer beliebigen Formel zu einer logisch aquivalenten Formel inPNF zu gelangen, ist auch die folgende Beobachtung hilfreich, die erneutverdeutlicht, dass die Variablen nur zu Festlegung vonQuantifikationsmustern verwendet werden.
Theorem
(Umbenennung gebundener Variablen)Wenn z nicht in A vorkommt, dann gilt:
|= ∀xA(x) ≡ ∀zA(z)
|= ∃xA(x) ≡ ∃zA(z)
202 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wir werden einen simplen Algorithmus angeben, mit dem jede beliebigeFormel in eine logisch aquivalente pranexe Formel umgeformt werdenkann. Diese Umformungen erfolgen, indem logisch aquivalente Formeln (inFormeln) fureinander eingesetzt werden. Das ist zulassig, wenn diewechselseitige Ersetzung logisch aquivalenter Formeln keinen Einfluß hatauf die Wahrheitsbedingungen der Formeln, in denen ersetzt wird. M.a.W.,wir benotigen ein Ersetzungstheorem.
Wir definieren induktiv den Begriff der Ersetzung eine Formel A fur eineatomare Formel p in einer Formel B (symbolisch [A/p]B).
Theorem
(Ersetzungstheorem)
|= A ≡ B impliziert |= [A/p]C ≡ [B/p]C
203 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Definition
Eine Formel A ist in Negationsnormalform (NNF) genau dann, wenn furjede Teilformel ¬B von A gilt, dass B atomar ist.
Theorem
(Negationsnormalform) Zu jeder Formel A existiert eine logischaquivalente Formel A′ in NNF.
Beweis. Die Behauptung folgt mit dem Ersetzungstheorem und:
|= ¬∀xA ≡ ∃x¬A, |= ¬∃xA ≡ ∀x¬A, |= ¬¬A ≡ A
|= ¬(A ∧ B) ≡ (¬A ∨ ¬B)
|= ¬(A ∨ B) ≡ (¬A ∧ ¬B)
|= ¬(A ⊃ B) ≡ (A ∧ ¬B)
|= ¬(A ≡ B) ≡ ((A ∧ ¬B) ∨ (B ∧ ¬A))
204 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Die aufgelisteten Aquivalenzen liefern einen Algorithmus, um eine beliebigeFormel A in eine logisch aquivalente Formel A′ in NNF zu transformieren.
Theorem
(pranexe Normalform) Zu jeder Formel A existiert eine logisch aquivalenteFormel A∗ in PNF.
205 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Beweis. Zunachst eliminieren wir alle Vorkommnisse von ⊃ und ≡ in derFormel A unter Verwendung des Ersetzungstheorems und folgender Fakten:
|= (A ⊃ B) ≡ (¬A ∨ B)
|= (A ≡ B) ≡ ((A ⊃ B) ∧ (B ⊃ A))
Dann bringen wir die so erhaltene Formel in Negationsnormalform und erhalteneine Formel A′. Nun verwenden wir Induktion uber den Aufbau von A′. Wenn A′
eine atomare Formel oder eine negierte atomare Formel ist, dann ist A′ pranex.
206 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wenn A′ = (B ∨ C ), konnen wir mit der Induktionsannahme davonausgehen, dass B und C logisch aquivalent sind zu Formeln B∗ und C ∗ inPNF. D.h.,
B∗ = Q1x1 . . .QnxnB1, und
C ∗ = Q ′1y1 . . .Q′mymC1,
wobei Q ∈ {∀, ∃} und B1, C1 quantorfrei sind. Wir konnen allegebundenen Variablen so wahlen, dass sie verschieden sind und dass keineVariable sowohl gebunden als auch frei vorkommt. Wir erhalten:
|= A′ ≡ Q1x1 . . .QnxnQ ′1y1 . . .Q′mym(B1 ∨ C1)
und sind fertig.
207 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wenn A′ = (B ∧ C ), verfahren wir analog.
Wenn A′ = ∀xB or A′ = ∃xB, wahlen wir ∀zB∗ bzw. ∃zB∗ fur eine frischeVariable z . q.e.d.
Beispiele. Wir transformieren die Formel:
¬∀x∃y¬∃z(R(x , y) ⊃ P(y , z)) ∧ ∃xR(a, x)
sukzessive in PNF:
¬∀x∃y¬∃z(R(x , y) ⊃ P(y , z)) ∧ ∃xR(a, x)¬∀x∃y¬∃z(¬R(x , y) ∨ P(y , z)) ∧ ∃xR(a, x)∃x∀y∃z(¬R(x , y) ∨ P(y , z)) ∧ ∃xR(a, x)∃x∀y∃z(¬R(x , y) ∨ P(y , z)) ∧ ∃x1R(a, x1)∃x∀y∃z∃x1((¬R(x , y) ∨ P(y , z)) ∧ R(a, x1))
208 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wir transformieren die Formel:
∃xQ(z , x) ⊃ ∀x(R(x , y) ⊃ P(x))
sukzessive in PNF:
∃xQ(z , x) ⊃ ∀x(R(x , y) ⊃ P(x))
¬∃xQ(z , x) ∨ ∀x(¬R(x , y) ∨ P(x))
∀x¬Q(z , x) ∨ ∀x(¬R(x , y) ∨ P(x))
∀x¬Q(z , x) ∨ ∀x1(¬R(x1, y) ∨ P(x1))
∀x(¬Q(z , x) ∨ ∀x1(¬R(x1, y) ∨ P(x1)))
∀x∀x1(¬Q(z , x) ∨ (¬R(x1, y) ∨ P(x1)))
209 / 230
Eine Einfuhrung in die klassische Logik
Pranexe Normalform
Wir transformieren die Formel:
∀yK (y) ⊃ ∃xT (x)
sukzessive in PNF:
∀yK (y) ⊃ ∃xT (x)
¬∀yK (y) ∨ ∃xT (x)
∃y¬K (y) ∨ ∃xT (x)
∃y(¬K (y) ∨ ∃xT (x))
∃y∃x(¬K (y) ∨ ∃xT (x))
Man beachte, dass ∀yK (y) ⊃ ∃xT (x) und ∀y∃x(K (y) ⊃ T (x)) nicht logischaquivalent sind.
210 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Regel der ∃-Einfuhrung
Motivation der ∃-Einfuhrungsregel
∆...
L(a, b)
∃xL(x , b)
∆...
L(a, b)
∃yL(a, y)
∆...
L(a, b)
∃yL(a, y)
∃x∃yL(x , y)
∆...
L(c , c)
∃xL(x , c)
∆...
L(c , c)
∃yL(c , y)
∆...
L(c , c)
∃xL(x , x)
211 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
∆...
∀xL(x , b)
∃y∀xL(x , y)
∆...
∀xL(x , b)
∃x∀xL(x , x)
nicht korrekt
∆...
∀yL(y , y)
∃x∀yL(x , y)
nicht korrekt
Es muss vermieden werden, dass die Einfuhrung des Existenzquantorsbestehende Quantifikationsmuster antastet.
212 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Definition
Mit [t/x ]A bezeichnen wir das Ergebnis der Ersetzung jedes freienVorkommnisses der Variablen x in der Formel A durch den Term t.
Definition
Der Term t ist frei fur x in A genau dann, wenn keine Variable von t ineinem substituierten Vorkommnis von t in [t/x ]A gebunden vorkommt.
213 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Definition
(Alternative Definition von “frei fur”) Der Begriff “Term t ist frei fur x inA” ist induktiv wie folgt definiert:
t ist frei fur x in A, wenn A atomar ist.
t ist frei fur x in ¬B, wenn t frei fur x in B ist.
t ist frei fur x in B]C (] ∈ {∧,∨,⊃,≡}), wenn t frei fur x in B istund frei fur x in C .
t ist frei fur x in ∃yB, wenn y nicht in t vorkommt und t frei ist fur xin B.
t ist frei fur x in ∀yB, wenn y nicht in t vorkommt und t frei ist fur xin B.
214 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
∆...
A(t)
∃xA
(∃E )
falls t frei ist fur x in A(x), wobei A(t) = [t/x ](A).
In dem Beispiel∆...
∀yL(y , y)
∃x∀yL(x , y)
haben wir ∀yL(y , y) = [y/x ]∀yL(x , y), aber y ist nicht frei fur x in∀yL(x , y).
215 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Auch das vorletzte Beispiel ist keine Einsetzung in die Regel (∃E ):
∆...
∀xL(x , b) 6= [b/x ]∀xL(x , x) = ∀xL(x , x)∃x∀xL(x , x)
216 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Regel der ∀-Beseitigung
Motivation der ∀-Beseitigungsregel∆...
∀x∃yL(y , x)
∃yL(y , z)
(korrekt)
∆...
∀x∃yL(y , x)
∃yL(y , y)
(nicht korrekt)
∆...
∀xA(x)
A(t)
(∀B)
falls t frei ist fur x in A(x).
217 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Regel der ∀-Einfuhrung
Motivation der ∀-Einfuhrungsregel
Alle F sind GAlle G sind H
Alle F sind H
∀x(F (x) ⊃ G (x))∀x(G (x) ⊃ H(x))
∀x(F (x) ⊃ H(x))
Eine informelle Ableitung:
Sei x ein beliebiges Objekt.Angenommen x ist F .Alle F sind G , also ist x G.Alle G sind H, also ist x H.Also, wenn x F ist, dann ist x H.Aber x war beliebig gewahlt.Also gilt: Alle F sind H.
218 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
[F (x)]1∀x(F (x) ⊃ G (x))
F (x) ⊃ G (x)(∀B)
G (x)(⊃B)
∀x(G (x) ⊃ H(x))
G (x) ⊃ H(x)(∀B)
H(x)(⊃B)
F (x) ⊃ H(x)(⊃E)1
∀x(F (x) ⊃ H(x))(∀E)
An der Stelle
F (x) ⊃ H(x)
∀x(F (x) ⊃ H(x))(∀E)
der Ableitung wird nichts Spezifisches uber x angenommen. Die Annahme,dass x F ist, wurde bereits als temporare Annahme im (⊃ E ) Schrittaufgegeben.
219 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Beispiele:
[F (x)1]
∀xF (x)(∀E) nicht korrekt
F (x) ⊃ ∀xF (x)(⊃E)1
∀x(F (x) ⊃ ∀xF (x))(∀E) korrekt
F (a) ⊃ ∀xF (x)(∀B)
[F (y)]1
∀xF (x)(∀E) nicht korrekt
F (y) ⊃ ∀xF (x)(⊃E)1
∀x(F (x) ⊃ ∀xF (x))(∀E) korrekt
F (a) ⊃ ∀xF (x)(∀B)
220 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
∀-Einfuhrungsregel: ∆...
A(x)
∀xA(x)
(∀E )
falls x in keiner Annahme frei vorkommt, von der A(x) abhangt.
221 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Beispiele:
[∀x(A(x) ∧ B(x))]1
A(x) ∧ B(x)(∀B)
A(x)(∧B)
∀xA(x)(∀E)
[∀x(A(x) ∧ B(x))]1
A(x) ∧ B(x)(∀B)
B(x)(∧B)
∀xB(x)(∀E)
∀xA(x) ∧ ∀xB(x)(∧E)
∀x(A(x) ∧ B(x)) ⊃ (∀xA(x) ∧ ∀xB(x))(⊃E)1
In den (∀E )-Schritten hangt A(x) bzw. B(x) jeweils von einer Pramisseab, in der die Variable x allerdings nicht frei vorkommt.
222 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
[∀x∀yL(x , y)]1
∀yL(x , y)(∀B)
L(x , y)(∀B)
∀xL(x , y)(∀E)1
∀y∀xL(x , y)(∀E)
∀x∀yL(x , y) ⊃ ∀y∀xL(x , y)(⊃E)
223 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Regel der ∃-Beseitigung
Motivation der ∃-Beseitigungsregel
Jemand ist FAlle F sind G
Jemand ist G
∃xF (x)∀x(F (x) ⊃ G (x))
∃xG (x)
Eine informelle Ableitung:
Jemand ist F; nennen wir dieses Objekt y .Alle F sind G , also ist y G .Also ist jemand G .Alles was wir uber y angenommen hatten, war, dass y F ist.M.a.W., y war ein beliebiges F . Da jemand F ist, hangt dieKonklusion (dass jemand G ist) also nicht von der Annahme ab,dass y F ist.
224 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
∃xF (x)
[F (y)]1∀x(F (x) ⊃ G (x))
F (y) ⊃ G (y)(∀B)
G (y)(⊃B)
∃xG (x)(∃E)
∃xG (x)(∃B)1
225 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
∃-Beseitigungsregel:Γ ∆, [A(y)]...
...∃xA B
B
(∃B)
wenn x 6∈ fv(B) und fur alle C ∈ ∆ mit C 6= A(y), x 6∈ fv(C ), wobeifv(B) die Menge der in B frei vorkommenden Variablen ist.
226 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
Beispiele:
(a)∃xG (x) [G (x)]1
G (x)(∃B)1 ‡
∀xG (x)(∀E)
∃xG (x)
∃xF (x)
[F (x)]1 [G (x)]2
F (x) ∧ G (x)(∧E)
∃x(F (x) ∧ G (x))(∃E)
∃x(F (x) ∧ G (x))(∃B)1 ‡
∃x(F (x) ∧ G (x))(∃B)2
‡: nicht korrekte Anwendung von (∃B)227 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
(b) {∃x(F (x) ∧ G (x))} ` ∃xF (x) ∧ ∃xG (x)
[(F (x) ∧ G (x))] [(F (x) ∧ G (x))]
F (x) G (x)
∃x(F (x) ∧ G (x)) ∃xF (x) ∃x(F (x) ∧ G (x)) ∃xG (x)
∃xF (x) ∃xG (x)
∃xF (x) ∧ ∃xG (x)
228 / 230
Eine Einfuhrung in die klassische Logik
Naturliches Schließen fur die Pradikatenlogik
(c) {∃x(A(x) ∧ B(x)),¬∃x(B(x) ∧ C (x))} ` ¬∀x(A(x) ∧ C (x))
[∀x(A(x) ∧ C (x))]
[A(x) ∧ B(x)] (A(x) ∧ C (x)
B(x) C (x)
(B(x) ∧ C (x))
∃x(A(x) ∧ B(x)) ∃x(B(x) ∧ C (x))
∃x(B(x) ∧ C (x)) ¬∃x(B(x) ∧ C (x))
¬∀x(A(x) ∧ C (x))
229 / 230