Grundzüge der Logik - Ruhr-Universität Bochum · Ein Satz istbejahend, wenn das Pr adikat dem...

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


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


Euklid (360 v. Chr. – ca. 280 v. Chr.)

Euklid wendete die so genannte axiomatische Methode des logischenSchließens auf die Geometrie an.

3 / 230


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


George Boole (1815 – 1864)

Boole legte die erste (publizierte) Formalisierung der Aussagenlogik alsAlgebra vor. (An Investigation of The Laws of Thought, 1854)

5 / 230


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


Gottlob Frege (1848 – 1925)

Frege entwickelte eine Formalisierung der Pradikatenlogik mittels einergraphischen Notation (Begriffsschrift, 1879).

7 / 230


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


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


Gerhard Gentzen (1909 – 1945)

Gentzen entwickelte den Kalkul des naturlichen Schließens und denSeqenzenkalkul fur die Pradikatenlogik (1934).

10 / 230


Alonzo Church (1903 – 1995)

Church entwickelte den Lambda-Kalkul, die Grundlage der funktionalenProgrammiersprachen, und zeigte die Unentscheidbarkeit derAllgemeingultigkeit pradikatenlogischer Formeln.

11 / 230


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


Saul Kripke (1940 – )

Kripke entwickelte u.a. die so genannte “mogliche Welten Semantik” furnicht-klassische Logiken.

13 / 230


Nur Manner?

Helena Rasiowa (1917 – 1994) Larisa Maksimova (1943 – )

Siehehttp://loriweb.org/women-in-philosophy-of-logic-and-philosophical-logic/

14 / 230


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


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


Die Logik als interdisziplinare Theorie

'&$%

'

&

$

%

'&

$%

Logik PhilosophieMathematik

Informatik

Linguistik

Abbildung: Die Logik als Teilsdisziplin anderer Disziplinen.

17 / 230


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


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



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



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



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



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



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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Die Idee der realistischen, modelltheoretischen Semantik

Welt

Reprasentation (Modelle reprasentieren Ausschnitte der Welt)

Modelle

Interpretation (Sprachliche Ausdrucke werden in Modelleninterpretiert)

sprachliche Ausdrucke

39 / 230


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


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



(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



“wenn ..., dann −−−” 7→ ⊃ (→)“...und−−−” 7→ ∧“...oder−−−” 7→ ∨

((p ⊃ (s ∨m)) ∧ (m ⊃ h))

(p ⊃ (h ∨ s))

Gultige Schlussfolgerung

43 / 230



(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



(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



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



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



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



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



(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



(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



(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


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



∅((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



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



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



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


Die Sprache der Aussagenlogik

Sprache

��

QQ

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



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



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



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



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


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



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



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



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



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



�

�

�

�rrr

-

-

��1

f

Die Funktion f ist surjektivaber nicht injektiv.

�

�

�

�rr

�

�

�

�rr -

PPPPPq

g

Die Funktion g ist injektivaber nicht surjektiv.

�

�

�

�rrr

68 / 230



�

�

�

�rrr

-

-

��1

h

Die Funktion h ist wedersurjektiv noch injektiv.

�

�

�

�rrr

�

�

�

�rrr

-

PPPPPq��1

h′

Die Funktion h′ ist bijektiv.

�

�

�

�rrr

69 / 230



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



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



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



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


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



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



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



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



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



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



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



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


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


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


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


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


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


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



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



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



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


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



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



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



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



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



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



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



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


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


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


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


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


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


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


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


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



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



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



Diese Schlussfolgerung ist gultig. Sie ist ein Beispiel fur eine Einfuhrungder Negation.

[ p ]p ⊃ ¬u¬u ⊃ ¬g¬g g¬p

110 / 230


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


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


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


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


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


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



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



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



[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



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



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



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



∆....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



∆, [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



∆, [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



∆, [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



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



[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



(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



(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



(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



[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



(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



(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



(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



(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



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



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



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



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


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



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



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


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


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



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



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



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



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



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


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


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


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


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


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


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


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



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



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



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



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



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


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


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


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



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



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



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


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



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


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



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


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


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


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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



Die folgende Schlussfolgerung ist ungultig:

(∗ ∗ ∗) ∀x∃yS(x , y)

∃y∀xS(x , y)

Ein Gegenbeispiel ist:

vv

�� 194 / 230


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



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



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


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


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


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


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


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


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


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


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


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


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


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


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


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


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



∆...

∀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



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



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



∆...

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



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



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



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



[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



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



∀-Einfuhrungsregel: ∆...

A(x)

∀xA(x)

(∀E )

falls x in keiner Annahme frei vorkommt, von der A(x) abhangt.

221 / 230



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



[∀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



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



∃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



∃-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



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



(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



(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


Nicht korrekte Ableitung von (∀ xA(x) ≡ ¬∃ x¬A(x)).Wo liegt der Fehler?

[¬A(x)]3

∃ x¬A(x)(∃E)

[¬∃ x¬A(x)]2

A(x)(¬B∗)3

∀xA(x)(∀E)

∃ x¬A(x)

[¬A(x)]4

∀xA(x)

A(x)(∀E)

¬∃ x¬A(x)(¬B)

¬∃ x¬A(x)(∃B)4

(∀ xA(x) ≡ ¬∃ x¬A(x))(≡E)1,2

230 / 230

Date post:	24-Aug-2019
Category:	Documents
Upload:	duongtram
View:	220 times
Download:	0 times

Grundzüge der Logik - Ruhr-Universität Bochum · Ein Satz istbejahend, wenn das Pr adikat dem...

Documents