Syntax und Semantik der Aussagenlogik

Seminar: Einführung in die Modallogik (WS 15/16)
Lehrender: Daniel Milne-Plückebaum, M.A.
E-Mail: [email protected]
Handout: Syntax und Semantik der Aussagenlogik
Die Syntax der Aussagenlogik
Um Formeln der Aussagenlogik bilden zu können, müssen wir zuerst wissen, welche Symbole wir dafür überhaupt benutzen dürfen. Wir vereinbaren:
Folgende Symbole stehen uns für die Bildung von Formeln der Aussagenlogik zur
Verfügung:
Aussagenkonstanten: p0 , p1 , p2 , ...
Operatoren:
einstellige: ¬ (Negationssymbol)
zweistellige: ∧ (Konjunktionssymbol), ∨ (Disjunktionssymbol), → (Symbol
der materialen Implikation), ↔ (Symbol der materialen Biimplikation)
Klammern: (, )
Kein anderes Symbol steht uns für die Bildung von Formeln der Aussagenlogik zur
Verfügung.
Nun da wir wissen, welche Symbole wir benutzen dürfen, müssen wir natürlich noch
wissen, wie wir diese benutzen dürfen. Dafür legen wir eine Reihe von Regeln fest:
Folgende Symbolketten sind Formeln der Aussagenlogik (AL-Formeln):
1. Jede Aussagenkonstante ist eine AL-Formeln, und zwar ein (AL-)Atom.
2. Jede Zeichenkette der Form ¬A, wobei A eine AL-Formel ist, ist eine AL-Formel,
und zwar eine (AL-)Negation.
3. Jede Zeichenkette der Form (A ∧ B), wobei A und B AL-Formeln sind, ist eine
AL-Formel, und zwar eine (AL-)Konjunktion.
1
4. Jede Zeichenkette der Form (A ∨ B), wobei A und B AL-Formeln sind, ist eine
AL-Formel, und zwar eine (AL-)Disjunktion.
5. Jede Zeichenkette der Form (A → B), wobei A und B AL-Formeln sind, ist eine
AL-Formel, und zwar eine materiale (AL-)Implikation.
6. Jede Zeichenkette der Form (A ↔ B), wobei A und B AL-Formeln sind, ist eine
AL-Formel, und zwar eine materiale (AL-)Biimplikation.
Nichts sonst ist eine AL-Formel.
Die Regeln sind rekursiv definiert. Das bedeutet, dass wir einen Startpunkt haben, gegeben in Regel 1. Dadurch wissen wir schon einmal, dass z.B. p0 , p1 und p2 AL-Formeln sind
(nämlich Atome). Ausgehend von diesem (unendlich großen) Grundstock an AL-Formeln
können wir rekursiv weitere Formeln bauen. Da p0 eine AL-Formel ist, ist auch ¬p0 eine
AL-Formel (nämlich eine Negation, Regel 2). Da p1 und ¬p0 AL-Formeln sind, ist auch
(p1 ∧¬p0 ) eine AL-Formel (nämlich eine Konjunktion, Regel 3). Da p1 und p2 AL-Formeln
sind, ist auch (p1 ∨ p2 ) eine AL-Formel (nämlich eine Disjunktion, Regel 4). Da (p1 ∨ p2 )
und (p1 ∧¬p0 ) AL-Formeln sind, ist auch ((p1 ∨p2 ) → (p1 ∧¬p0 )) eine AL-Formel (nämlich
eine materiale Implikation, Regel 5). Da ((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) und ¬p0 AL-Formeln
sind, ist auch (((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) ↔ ¬p0 ) eine AL-Formel (nämlich eine materiale
Biimplikation, Regel 6). Und so weiter.
Bevor wir mit der Semantik der Aussagenlogik weitermachen, folgen noch ein paar Hinweise zur Schreibweise. Die Großbuchstaben A, B, C, ... im obigen Kasten repräsentieren beliebige AL-Formeln, die allesamt nur aus den ganz oben aufgeführten Symbolen
bestehen dürfen. Außerdem wollen wir vereinbaren, dass die äußeren Klammern von ALFormeln stets weggelassen werden dürfen, jedoch keine weiteren Klammern.
Die Semantik der Aussagenlogik
AL-Formeln müssen interpretiert werden. Jede AL-Formel soll etwas bedeuten. Wir können sagen, dass jede AL-Formel einen semantischen Wert zugewiesen bekommen soll.
Doch welche semantischen Werte gibt es überhaupt?
Die semantischen Werte für AL-Formeln sind t (das Wahre) und f (das Falsche). Diese
werden auch Wahrheitswerte genannt. Wir benötigen keine weiteren semantischen
Werte für die Interpretation von AL-Formeln.
2
Um wirklich jeder AL-Formel einen Wahrheitswert zuweisen zu können, müssen wir natürlich irgendwo anfangen. Dafür bieten sich die basalen AL-Formeln, die Atome, an.
Von diesen müssen die Wahrheitswerte vorgegeben sein. Wir können sie nicht wie die
Wahrheitswerte komplexer AL-Formeln ermitteln.
Die Syntax der Aussagenlogik sagt, dass uns unendlich viele Aussagenkonstanten zur
Verfügung stehen, die selbst die Atome bilden und aus denen wir wiederum (mithilfe der
Operatoren und Klammern) unendlich viele weitere komplexe AL-Formeln bilden können. Da Atome die basalen AL-Formeln sind, muss erst einmal unendlich vielen Atomen
jeweils genau ein Wahrheitswert zugewiesen werden. Diese Zuordnung ist Teil einer sogenannten basalen AL-Interpretationsfunktion.1 Diese kann später zu einer (vollständigen)
AL-Interpretationsfunktion erweitert werden, die uns für alle (also auch alle komplexen)
AL-Formeln den Wahrheitswert liefert.
Eine basale AL-Interpretationsfunktion I ist eine Funktion, die jedem Atom
genau einen Wahrheitswert zuordnet (I ∶ {A ∶ A ist ein Atom} Ð→ {t, f }).
Wird einem Atom A von einer basalen AL-Interpretationsfunktion I ein Wahrheitswert
x zugeordnet, schreiben wir ⟨A, x⟩ ∈ I oder I(A) = x.
Natürlich interessieren uns in der Regel nicht die Wahrheitswerte aller Atome. Nichtsdestotrotz handelt es sich bei einer Relation erst dann um eine basale AL-Interpretationsfunktion, wenn wirklich jedem Atom genau ein Wahrheitswert zugewiesen wird. Wir können uns damit behelfen, für alle Atome, die uns im gegebenen Fall nicht interessieren,
ein allgemeines Rezept für die Wahrheitswert-Zuordnung aufzuschreiben. Betrachten wir
die basale AL-Interpretationsfunktion I1 :
Beispiel 1: I1 (p0 ) = f, I1 (p1 ) = f, I1 (p2 ) = t, I1 (p3 ) = f, I1 (pn ) = t (für alle n > 3).
I1 wurde damit vollständig bestimmt, weil eine Bedingung für die Indizes der nicht explizit aufgeführten Atome angegeben wurde, sodass für jedes Atom eindeutig definiert ist,
welchen Wahrheitswert I1 ihm zuordnet. Man kann basale AL-Interpretationsfunktionen
natürlich auch komplett durch ein Rezept angeben, z.B. so:
Beispiel 2: I2 (pn ) = f, falls n gerade ist und I2 (pn ) = t, falls n ungerade ist.
Bis hierher muss alles vorgegeben sein oder bestimmt werden. Ohne eine basale ALInterpretationsfunktion, die jedem Atom einen Wahrheitswert zuordnet, geht gar nichts.
Eine Funktion ist eine eindeutige Zuordnungsrelation zwischen einer Definitionsmenge M und einer
Zielmenge N , wobei jedem Element aus M genau ein Element aus N zugeordnet wird.
1
3
Haben wir jedoch eine basale AL-Interpretationsfunktion, kann auf ihrer Grundlage eine vollständige AL-Interpretationsfunktion, oder einfach eine AL-Interpretationsfunktion,
definiert werden:
Eine AL-Interpretationsfunktion I ist eine Funktion, die jeder AL-Formel genau
einen Wahrheitswert zuordnet (I ∶ {A ∶ A ist eine AL-Formel} Ð→ {t, f }).
Angenommen, wir haben eine basale AL-Interpretationsfunktion I vorgegeben; wie lautet dann die vollständige AL-Interpretationsfunktion I? Grundsätzlich lässt sich diese
Frage immer gleich beantworten – egal, wie I beschaffen ist. Denn es gibt eine Reihe
von Regeln, die uns für jede basale AL-Interpretationsfunktion I genau sagt, wie ihre
Erweiterung I lautet. Mit anderen Worten: Egal, welche Wahrheitswerte den Atomen
von I zugeordnet werden, diese Regeln sagen uns für jede (also auch für jede komplexe)
AL-Formel, welcher Wahrheitswert ihr von I zugeordnet wird. Diese Regeln nennt man
auch Wahrheitsbedingungen für AL-Formeln oder einfach AL-Wahrheitsbedingungen:
Sei I eine basale AL-Interpretationsfunktion. Die AL-Interpretationsfunktion I ergibt
sich aus I durch folgende AL-Wahrheitsbedingungen:
1. Für alle Atome A: I(A) = t genau dann, wenn I(A) = t.
2. I(¬A) = t genau dann, wenn I(A) = f.
3. I(A ∧ B) = t genau dann, wenn I(A) = I(B) = t.
4. I(A ∨ B) = t genau dann, wenn I(A) = t oder I(B) = t.
5. I(A → B) = t genau dann, wenn I(A) = f oder I(B) = t.
6. I(A ↔ B) = t genau dann, wenn I(A) = I(B).
Da es nur zwei Wahrheitswerte gibt, und I und I Funktionen sind, ergeben sich aus den
AL-Wahrheitsbedingungen auch direkt die AL-Falschheitsbedingungen.
Nun können wir die Wahrheitswerte für beliebige AL-Formeln ermitteln. Betrachten wir
z.B. die AL-Formel (p1 ∨p2 ) → (p1 ∧¬p0 ). Wir haben (für alle basalen AL-Interpretationsfunktionen I):
• I((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) = t gdw. I(p1 ∨ p2 ) = f oder I(p1 ∧ ¬p0 ) = t (Regel 5).
– wobei I(p1 ∨ p2 ) = f gdw. I(p1 ) = f und I(p2 ) = f (Regel 4).
4
∗ wobei I(p1 ) = f gdw. I(p1 ) = f (Regel 1).
∗ wobei I(p2 ) = f gdw. I(p2 ) = f (Regel 1).
– wobei I(p1 ∧ ¬p0 ) = t gdw. I(p1 ) = t und I(¬p0 ) = t (Regel 3).
∗ wobei I(p1 ) = t gdw. I(p1 ) = t (Regel 1).
∗ wobei I(¬p0 ) = t gdw. I(p0 ) = f (Regel 2).
· wobei I(p0 ) = f gdw. I(p0 ) = f (Regel 1).
Also haben wir die folgende Wahrheitsbedingung für die AL-Formel (p1 ∨ p2 ) → (p1 ∧ ¬p0 )
(für alle basalen AL-Interpretationsfunktionen I):
• I((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) = t gdw. [I(p1 ) = f und I(p2 ) = f] oder [I(p1 ) = t und
I(p0 ) = f].
Nun können wir überprüfen, ob eine unserer basalen AL-Interpretationsfunktionen I1 ,
I2 die ermittelte Wahrheitsbedingung erfüllt. Falls ja, wird der komplexen AL-Formel
(p1 ∨ p2 ) → (p1 ∧ ¬p0 ) von der jeweils vervollständigten AL-Interpretationsfunktion I 1 , I 2
der Wahrheitswert t zugeordnet; falls nein, wird der komplexen AL-Formel (p1 ∨ p2 ) →
(p1 ∧ ¬p0 ) von der jeweils vervollständigten AL-Interpretationsfunktion I 1 , I 2 der Wahrheitswert f zugeordnet.
Unter I1 ist die Wahrheitsbedingung für die komplexe AL-Formel nicht erfüllt. Damit
gilt: I 1 ((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) = f. Unter I2 hingegen ist die Wahrheitsbedingung für die
komplexe AL-Formel erfüllt. Damit gilt: I 2 ((p1 ∨ p2 ) → (p1 ∧ ¬p0 )) = t.
Insgesamt gilt es zu beachten, dass keine AL-Formel A einfach den Wahrheitswert t oder
den Wahrheitswert f hat. Stattdessen hat eine AL-Formel A einen Wahrheitswert immer
nur relativ zu einer AL-Interpretationsfunktion I, und damit relativ zu einer basalen
AL-Interpretationsfunktion I.
5

Download Report