Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 2/latex
\setcounter{section}{2}
\zwischenueberschrift{Sprache als Symbolketten}
Wir knüpfen an die Überlegungen der ersten Vorlesung an, ob es eine Maschine \zusatzklammer {einen Computer, einen Algorithmus} {} {} gibt, der \zusatzklammer {alle korrekten} {} {} mathematische Aussagen ausdrücken, ausdrucken, überprüfen, beweisen oder widerlegen kann. Eine solche Maschine operiert mit Zeichenreihen, die wir in diesem Zusammenhang Wörter einer \zusatzklammer {formalen} {} {} Sprache nennen. Wir beschreiben daher den Aufbau einer formalen Sprache.
\inputdefinition
{}
{
Es sei $A$ eine Menge von Symbolen. Dann nennt man jede endliche Zeichenreihe, die man mit den Elementen aus $A$ aufstellen kann, ein \definitionswort {Wort über dem Alphabet}{} $A$.
}
Die Menge aller Wörter über dem Alphabet $A$ bezeichnen wir mit $A^*$.
Das zugrunde liegende Alphabet kann endlich oder unendlich sein, für praktische Anwendungen reicht ein endliches Alphabet. Die Elemente des Alphabets nennt man Buchstaben, Zeichen oder Symbole. Mit einer Zeichenreihe meint man eine hintereinander geschriebene Buchstabenkette \zusatzklammer {oder Symbolkette} {} {.} Dazu gehören die einelementigen Ketten, also die Elemente aus $A$ selbst, aber auch die leere Kette \zusatzklammer {das leere Wort} {} {,} die wir mit $\emptyset$ bezeichnen. Bei dieser Definition kommt es nicht auf irgendeine Sinnhaftigkeit der Wörter an, es handelt sich um eine rein formale Definition.
\inputbeispiel{}
{
Es sei ein einelementiges
\definitionsverweis {Alphabet}{}{}
\mavergleichskette
{\vergleichskette
{A
}
{ = }{\{ {{|}} \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Dann besitzt jedes Wort über $A$ die Gestalt
\mathdisp {{{|}} {{|}}{{|}} \ldots {{|}}} { }
mit einer gewissen Anzahl von Strichen. Zwei solche Wörter sind genau dann gleich, wenn ihre Strichanzahl übereinstimmt. In diesem Fall entsprechen also die Wörter den natürlichen Zahlen
\zusatzklammer {das leere Wort entspricht der $0$} {} {.}
}
Der Binärcode besteht aus den beiden Symbolen
\mathkor {} {0} {und} {1} {,}
der Morsecode besteht aus drei Zeichen: kurzes Signal, langes Signal, Pause. Grundsätzlich führt jedes nichtleere endliche Alphabet zu einer abzählbar-unendlichen Menge an Wörtern und hat somit prinzipiell die gleiche Ausdrucksstärke.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {DNA structure and bases FR.svg} }
\end{center}
\bildtext {} }
\bildlizenz { DNA structure and bases FR.svg } {} {Dosto} {Commons} {CC-by-sa 2.5} {}
Die DNA-Stränge, die die Erbinformationen aller Lebewesen tragen, sind Doppelketten in Helixform aus Nukleotiden. Die entscheidenden Bestandteile der Nukleotiden sind die Basen, wofür es nur vier Möglichkeiten gibt, nämlich Adenin (A), Thymin (T), Guanin (G) und Cytosin (C). Die Nukleotiden treten in der Helix stets mit einem festen Partner \zusatzklammer {nämlich Adenin mit Thymin und Guanin mit Cytosin} {} {} auf, so dass die Struktur durch die eine Hälfte der Helix festgelegt ist. Daher entspricht \zusatzklammer {bis auf die Leserichtung und die Strangauswahl} {} {} die genetische Information eines DNA-Stranges einem Wort über dem Alphabet mit den Buchstaben A,T,G,C.
}
Wenn zu einem Alphabet $A$ ein neues Zeichen $-$ als \anfuehrung{Leerzeichen}{} hinzugenommen wird, so werden manchmal die Wörter aus $A$ als
\zusatzklammer {eigentliche} {} {}
Wörter und die Wörter aus dem Alphabet
\mathl{A \cup \{ - \}}{} als Texte
\zusatzklammer {oder Sätze} {} {}
bezeichnet. Mit der Hinzunahme eines weiteren Satzbeendungssymbols kann man auch zwischen Sätzen und Texten unterscheiden.
Die geschriebene natürliche Sprache umfasst das Alphabet, das aus den Großbuchstaben A,B,C,...,Z,Ä,Ö,Ü, den Kleinbuchstaben a,b,c,...,z,ä,ö,ü,ß, den Ziffern, den Satzzeichen und einem Leerzeichen für den Abstand zwischen den Wörtern besteht. Jede lineare Hintereinanderreihung dieser Zeichen gilt für uns als Text. Im Moment interessieren wir uns nicht dafür, ob die geschriebenen Texte syntaktisch richtig gebildet oder semantisch sinnvoll sind. Im Moment ist also z.B.
\mathdisp {!!fL33kAs.,r} { }
ein erlaubter Text.
\zwischenueberschrift{Rekursive Definitionen}
In der Definition von einem Wort über einem Alphabet haben wir von einer Menge gesprochen und somit eine naive Mengenlehre vorausgesetzt. Im endlichen Fall wird die Symbolmenge einfach durch Auflisten ihrer Elemente gegeben. Für die gebildeten Wörter haben wir implizit verwendet, dass das Bilden von linearen Zeichenreihen unproblematisch ist.
Ein wichtiges Prinzip, Mengen zu definieren, ist das der \stichwort {rekursiven Definition} {.} Eine rekursive Definition besteht aus zwei Sorten von Regeln. (1) Einerseits gewisse Startregeln, die sagen, was direkt zu der Menge gehört, und (2) Rekursionsregeln \zusatzklammer {Generierungsregeln} {} {,} die die Form einer Bedingung haben, und besagen, dass wenn gewisse Objekte zu der Menge gehören, und wenn neue Objekte aus diesen Objekten in bestimmter Weise gebildet sind, dass dann diese neuen Objekte ebenfalls dazu gehören \zusatzklammer {die dritte stillschweigende Bedingung an eine rekursive Definition ist, dass es keine weitere Möglichkeit gibt, zu der Menge zu gehören, außer den in (1) und (2) genannten} {} {.}
\inputbeispiel{}
{
Die Menge der Wörter über einem Alphabet $A$ kann man auch folgendermaßen rekursiv definieren.
\aufzaehlungzwei {$\emptyset$ ist ein Wort über $A$.
} {Wenn $x$ ein Wort ist und
\mathl{a \in A}{} ein Buchstabe, so ist auch $xa$ ein Wort.
}
Hier repräsentiert $x$
\zusatzklammer {eine Variable} {} {}
ein beliebiges schon konstruiertes Wort. Dabei ist $\emptyset a$ als $a$ zu lesen, so dass die beiden erlaubten Konstruktionsschritte
\zusatzklammer {also der Anfangsschritt und der Rekursionsschritt} {} {}
sichern, dass die einzelnen Symbole aus $A$ Wörter sind. Wenn das Alphabet durch
\mavergleichskette
{\vergleichskette
{A
}
{ = }{\{a,b,c\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben ist, so würde der rekursive Nachweis, dass
\mathl{abbac}{} ein Wort ist, folgendermaßen gehen.
\aufzaehlungsechs{Wegen der Anfangsbedingung ist $\emptyset$ ein Wort.
}{Deshalb und wegen des Rekursionsschrittes ist
\mavergleichskette
{\vergleichskette
{ \emptyset a
}
{ = }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Wort.
}{Deshalb und wegen des Rekursionsschrittes ist $ab$ ein Wort
\zusatzklammer {hier ist also
\mavergleichskette
{\vergleichskette
{x
}
{ = }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das schon nachgewiesene Wort und der Buchstabe $b$ wird angehängt} {} {.}
}{Deshalb und wegen des Rekursionsschrittes ist
\mathl{abb}{} ein Wort
\zusatzklammer {hier ist also
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ab
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das schon nachgewiesene Wort und der Buchstabe $b$ wird angehängt} {} {.}
}{Deshalb und wegen des Rekursionsschrittes ist
\mathl{abba}{} ein Wort
\zusatzklammer {hier ist also
\mavergleichskette
{\vergleichskette
{x
}
{ = }{abb
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das schon nachgewiesene Wort und der Buchstabe $a$ wird angehängt} {} {.}
}{Deshalb und wegen des Rekursionsschrittes ist
\mathl{abbac}{} ein Wort
\zusatzklammer {hier ist also
\mavergleichskette
{\vergleichskette
{ x
}
{ = }{abba
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das schon nachgewiesene Wort und der Buchstabe $c$ wird angehängt} {} {.}
}
}
Natürlich kann man
\mathl{abbac}{} sofort ansehen, dass es sich um eine linear angeordnete Zeichenreihe über
\mathl{\{a,b,c\}}{} handelt, und der rekursive Nachweis scheint übertrieben pedantisch zu sein. Bei komplexer gebildeten Mengen ist aber die rekursive Definition unerlässlich, vor allem auch deshalb, da sie ermöglicht, Eigenschaften der Elemente einer Menge über den rekursiven Aufbau nachzuweisen.
\inputbemerkung
{}
{
Es sei $M$ eine rekursiv definierte Menge, die durch eine Startmenge
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und gewisse Rekursionsvorschriften gegeben sei. Nehmen wir an, wir möchten für alle Elemente der Menge $M$ eine gewisse Eigenschaft $E$ nachweisen. Das \stichwort {Beweisprinzip durch Rekursion} {\zusatzfussnote {Oft spricht man einfach von einem Beweis durch Induktion} {.} {}}
oder \stichwort {Beweisprinzip über den rekursiven Aufbau der Menge} {} funktioniert folgendermaßen.
\aufzaehlungzwei {Man zeigt, dass jedes Element aus der Startmenge die Eigenschaft $E$ erfüllt
\zusatzklammer {Rekursionsanfang} {} {.}
} {Man zeigt für jede Rekursionsvorschrift, dass unter der Voraussetzung, dass die in dieser Vorschrift verwendeten Elemente die Eigenschaft $E$ besitzen, dann auch das durch die Vorschrift produzierte Element die Eigenschaft besitzt
\zusatzklammer {Rekursionsschritt} {} {.}
}
Daraus kann man dann schließen, dass jedes Element aus $M$ die Eigenschaft erfüllt. Die Richtigkeit dieses Beweisprinzips beruht auf folgender Betrachtung: Es sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Menge aller Elemente, für die die Eigenschaft $E$ gilt. Aufgrund des Rekursionsanfangs gilt
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Aufgrund des Rekursionsschrittes ist $N$ abgeschlossenen unter sämtlichen Rekursionsvorschriften. Dies ist aber die Definition für $M$, also ist
\mavergleichskette
{\vergleichskette
{N
}
{ = }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Eigenschaft gilt für ganz $M$.
}
Ein Spezialfall dieses Beweisprinzips ist das Prinzip der vollständigen Induktion für natürliche Zahlen. Die natürlichen Zahlen sind rekursiv durch das Startelement $0$ und eine einzige Rekursionsregel, nämlich die Nachfolgerregel festgelegt: Wenn $n$ eine natürliche Zahl ist, so ist auch der Nachfolger
\mavergleichskette
{\vergleichskette
{n'
}
{ = }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
von $n$ eine natürliche Zahl.
\inputbemerkung
{}
{
Es sei $M$ eine rekursiv definierte Menge mit der Startmenge
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Verwandt mit dem
\definitionsverweis {Beweisprinzip über den rekursiven Aufbau der Menge}{}{}
ist das Prinzip, eine Abbildung $\varphi$ von $M$ in eine weitere Menge $N$ rekursiv zu definieren. Dazu geht man folgendermaßen vor.
\aufzaehlungdrei{Man legt eine Abbildung
\maabbdisp {\varphi_0} {S} {N
} {}
fest.
}{Für jede Rekursionsvorschrift erklärt man, wie man aus den schon festgelegten Werten
\mathl{\varphi(m_1) , \ldots , \varphi(m_k)}{} der Elemente
\mathl{m_1 , \ldots , m_k}{,} auf die die Vorschrift Bezug nimmt, den Wert unter $\varphi$ für das durch die Vorschrift produzierte Element $m$ festlegt.
}{Man muss sicherstellen, dass, falls es für ein Element mehrere Mög\-lichkeiten gibt, dieses rekursiv zu erzeugen, die verschiedenen Mög\-lichkeiten zum gleichen Wert führen.
}
Wenn diese Bedingungen erfüllt sind, ist eine wohldefinierte Abbildung
\maabbdisp {\varphi} {M} {N
} {}
definiert.
}
Eine Sprache besteht aus sinnvollen Wörtern und sinnvollen Sätzen, nicht aus der beliebigen Aneinanderreihung von Symbolen oder Buchstaben \zusatzklammer {oder Lauten} {} {.} Es ist aber vorteilhaft, erstmal alle Möglichkeiten zuzulassen und daraus durch eine Vorgabe von Regeln die sinnvollen Ausdrücke, Wörter, Lautkombinationen herauszufiltern. So funktioniert auch der kleinkindliche Spracherwerb und der Aufbau der formalen Sprachen. Wir werden nun den rekursiven Aufbau von syntaktisch korrekten Aussagen besprechen.
\seitenueberschrift{Aussagenlogik}
Die mathematische Logik beschäftigt sich hauptsächlich mit Prädikatenlogik, da in dieser ein Großteil der Mathematik beschrieben werden kann. Als Vorstufe dazu behandeln wir jetzt die Aussagenlogik. Wie bei der Prädikatenlogik später folgen wir dem Schema
Formale Sprache - Interpretationen und semantische Tautologien - Syntaktische Tautologien und Ableitungskalkül - Vollständigkeit.
\zwischenueberschrift{Die Sprache der Aussagenlogik}
Die formallogische Sprache der Aussagenlogik wird ausgehend von einer Variablenmenge $V$ und einer einfachen Menge an Junktoren rekursiv aufgebaut. Die Aussagenvariablen werden wir zumeist mit
\mathl{p,q,r,p_1 , \ldots , p_k, p_n \,\, (n \in \N)}{} etc. bezeichnen. Sie repräsentieren Aussagen, haben aber keinen eigenen Inhalt, sondern teilen mit Aussagen lediglich gewisse syntaktische Eigenschaften
\zusatzklammer {semantische Eigenschaften werden hier noch nicht besprochen} {} {.}
Beispiele für solche syntaktischen Eigenschaften sind, dass man zu einer Aussage eine Negation bilden kann, oder dass man zwei Aussagen durch \anfuehrung{und}{} verknüpfen kann. Die Aussagenvariablen repräsentieren Grundaussagen, die durch solche Verknüpfungen zu komplexeren Aussagen zusammengesetzt werden können, die selbst wiederum zu weiter verschachtelten Aussagen verbunden werden können. Die folgende Definition fixiert die formale Sprache der Aussagenlogik; es handelt sich um eine rekursive Definition, wobei die Aussagenvariablen die Startelemente sind und die logischen Operationen als Generierungsregeln auftreten. Das dieser rekursiven Definition zugrunde liegende Alphabet besteht neben einer Menge $V$ an Aussagenvariablen aus den Symbolen
\mathdisp {\neg,\, \wedge ,\, \vee ,\, \rightarrow,\, \leftrightarrow,\, (,\, )} { , }
die als
nicht, und, oder, impliziert, genau dann, wenn, Klammer auf, Klammer zu
gelesen werden; die zugehörigen Substantive sind \stichwort {Negation} {,} \stichwort {Konjunktion} {,} \stichwort {Disjunktion} {,} \stichwort {Implikation} {} und \stichwort {Äquivalenz} {.} Die Bezeichnungen orientieren sich natürlich an den später einzuführenden Bedeutungen, im Moment sind es lediglich Wörter für bestimmte Symbole. Die Sprache der Aussagenlogik wird als Teilmenge von $A^*$ realisiert, wobei
\mavergleichskette
{\vergleichskette
{A
}
{ = }{V \cup \{ \neg,\, \wedge ,\, \vee ,\, \rightarrow,\, \leftrightarrow,\, (,\, )\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
\inputdefinition
{}
{
Es sei $V$ eine Menge
\zusatzklammer {deren Elemente wir als
\definitionswort {Aussagenvariable}{}
bezeichnen} {} {.}
Dann wird die zugehörige
\definitionswort {Sprache der Aussagenlogik}{}
\mathl{L^V}{}
\zusatzklammer {zu $V$} {} {}
rekursiv durch folgende Regeln definiert.
\aufzaehlungdrei{Jedes
\mavergleichskette
{\vergleichskette
{p
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gehört zu $L^V$.
}{Wenn
\mavergleichskette
{\vergleichskette
{\alpha
}
{ \in }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist auch
\mavergleichskette
{\vergleichskette
{ \neg (\alpha)
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Wenn
\mavergleichskette
{\vergleichskette
{\alpha, \beta
}
{ \in }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind, so sind auch
\mavergleichskette
{\vergleichskette
{ (\alpha) \wedge (\beta) ,\, (\alpha) \vee (\beta) ,\, (\alpha) \rightarrow (\beta) ,\, (\alpha) \leftrightarrow (\beta)
}
{ \in }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
Häufig verwendet man weniger Symbole, beispielsweise verzichtet man auf
\mathl{\rightarrow, \leftrightarrow}{.} Die Klammerungen werden oft auch anders gesetzt. Z.B. erlaubt man manchmal
\mathl{\neg \alpha}{}
\zusatzklammer {ohne Klammer} {} {}
oder man macht die Klammern außen, also
\mathl{(\alpha \wedge \beta )}{.} Sehr oft lässt man Klammern, um die Lesbarkeit der Aussagen zu erhöhen, einfach weg, obwohl dies vom syntaktischen Standpunkt aus ein schweres Vergehen ist.
\inputbeispiel{}
{
Es seien
\mathl{p,q,r}{}
\definitionsverweis {Aussagenvariablen}{}{.}
Dann sind beispielsweise
\mathdisp {p,\, \neg (p),\, \neg (\neg( \neg (p))) , \,(p) \wedge (\neg ( q) ), \, ((p) \wedge (\neg (q))) \wedge (\neg (r)),\, ((( \neg (\neg (p))) \rightarrow (\neg ( q))) \vee ((\neg (r))) \leftrightarrow ( \neg (r) ) \wedge (q ))} { }
korrekt gebildete Aussagen, d.h. sie gehören zu $L^V$. Dagegen sind
\mathdisp {\neg,\, \rightarrow ,\, p \wedge,\, p \wedge q ,\, (p) \wedge (\neg q, \, (p) \wedge (q) \wedge (r),\,} { }
keine Aussagen in $L^V$
\zusatzklammer {aber natürlich Wörter über dem gegebenen Alphabet} {} {.}
}
Der Nachweis, dass ein gegebenes Wort eine korrekt gebildete Aussage ist, erfolgt über eine Ableitungskette oder einen Aussagestammbaum. Bei einer \stichwort {Ableitungskette} {} listet man Zeile für Zeile korrekt gebildete Aussagen auf, wobei diese Aussagen entweder Aussagenvariablen oder aber mittels einer Rekursionsregel aus vorhergehenden Aussagen entstanden sind. Die letzte Zeile enthält die Aussage, deren Korrektheit man zeigen will.
\inputbeispiel{}
{
Eine Ableitungskette für
\mathdisp {( (p) \wedge (r) ) \rightarrow ( ( \neg (q) ) \vee (r) )} { }
sieht folgendermaßen aus.
\aufzaehlungsieben{ $p$
\zusatzklammer {Aussagenvariable} {} {,}
}{$q$
\zusatzklammer {Aussagenvariable} {} {,}
}{$r$
\zusatzklammer {Aussagenvariable} {} {,}
}{
\mathl{\neg (q)}{}
\zusatzklammer {Negation auf 2} {} {,}
}{
\mathl{(p) \wedge (r)}{}
\zusatzklammer {Konjunktion auf 1 und 3} {} {,}
}{
\mathl{( \neg (q) ) \vee (r)}{}
\zusatzklammer {Disjunktion auf 4 und 3} {} {,}
}{
\mathl{( (p) \wedge (r) ) \rightarrow ( ( \neg (q) ) \vee (r) )}{}
\zusatzklammer {Implikation auf 5 und 6} {} {.}
}
}
Ein Aussagenstammbaum ist eine graphisch übersichtliche Version einer Ableitungskette. Er beginnt mit den verwendeten Aussagenvariablen als Blättern und erzeugt dann Schritt für Schritt durch Vereinigungen von Zweigen die beteiligten Teilaussagen, bis schließlich die in Frage stehende Aussage als Stamm erzeugt ist.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Abstammungsbaum.png} }
\end{center}
\bildtext {} }
\bildlizenz { Abstammungsbaum.png } {} {Funnyflowerpot} {Commons} {CC-by-sa 4.0} {}
Wir wollen uns anhand eines Stammbaumes klar machen, dass die Zeichenkette
\mathdisp {( (p) \wedge (r) ) \rightarrow ( ( \neg (q) ) \vee (r) )} { }
eine Aussage ist, also gemäß den
\definitionsverweis {Regeln}{}{}
korrekt gebildet ist. Der Abstammungsbaum entsteht ausgehend von den Blättern, die die vorkommenden
\definitionsverweis {Aussagenvariablen}{}{}
\zusatzklammer {mit ihrer Häufigkeit} {} {}
repräsentieren, indem man Schritt für Schritt komplexere Teilaussagen zusammensetzt.
}
Jede Aussage hat eine eindeutige \anfuehrung{rekursive Geschichte}{,} d.h. es gibt für jede Aussage nur eine Abfolge von Rekursionsschritten \zusatzklammer {bis auf die Reihenfolge} {} {,} um sie aus Aussagenvariablen aufzubauen, siehe Aufgabe 2.20.
\zwischenueberschrift{Aussagenlogische Interpretationen}
Wir kommen zur Interpretation einer aussagenlogischen Sprache und insbesondere der darin auftretenden Junktoren. Der Ansatz ist, dass eine Aussagenvariable nur wahr oder falsch sein kann.
\inputdefinition
{}
{
Es sei $V$ eine Menge von Variablen und
\mathl{L^V}{} die zugehörige
\definitionsverweis {aussagenlogische Sprache}{}{.}
Unter einer
\definitionswort {Wahrheitsbelegung}{}
versteht man eine
\definitionsverweis {Abbildung}{}{}
\maabbdisp {\lambda} {V} {\{0,1\}
} {}
\zusatzklammer {oder mit
\mathl{\{f,w\}}{} als Wertebereich} {} {.}
}
Eine Wahrheitsbelegung ist also einfach dadurch gegeben, dass einer jeden Aussagenvariablen ein Wahrheitswert, nämlich
\mathkor {} {0} {oder} {1} {}
bzw.
\mathkor {} {f} {oder} {w} {}
zugeordnet wird. Eine solche Wahrheitsbelegung möchte man auf die gesamte Sprache fortsetzen, wobei die folgenden Festlegungen die inhaltliche Bedeutungen der Junktoren widerspiegeln. Die folgende Definition ist möglich, da der rekursive Aufbau einer Aussage eindeutig bestimmt ist.
\inputdefinition
{}
{
Es sei $V$ eine Menge von Variablen,
\mathl{L^V}{} die zugehörige
\definitionsverweis {aussagenlogische Sprache}{}{}
und
\maabbdisp {\lambda} {V} {\{0,1\}
} {}
eine
\definitionsverweis {Wahrheitsbelegung}{}{.}
Unter der zugehörigen
\definitionswort {Interpretation}{}
\mavergleichskette
{\vergleichskette
{I
}
{ = }{I^\lambda
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
versteht man die über den
\definitionsverweis {rekursiven Aufbau der Sprache}{}{}
festgelegte Abbildung
\maabbdisp {I} {L^V} {\{0,1\}
} {}
mit
\aufzaehlungsechs{
\mavergleichskette
{\vergleichskette
{I(v)
}
{ = }{ \lambda (v)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jede Aussagenvariable
\mathl{v \in V}{.}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{\neg ( \beta)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = 0 \, , \\ 0 , \text{ falls } I( \beta)= 1 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ (\beta) \wedge ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = I( \gamma) = 1\, , \\ 0 \text{ sonst}\, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ (\beta) \vee (\gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = 1 \text{ oder } I( \gamma) = 1 \, , \\ 0, \text{ falls } I( \beta) = I( \gamma) = 0 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{( \beta) \rightarrow ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1 , \text{ falls } I( \beta) = 0 \text{ oder } I( \gamma) = 1 \, , \\ 0 , \text{ falls } I( \beta) = 1 \text{ und } I( \gamma) = 0 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{( \beta) \leftrightarrow ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1 , \text{ falls } I( \beta) = I( \gamma) \, , \\ 0 , \text{ falls } I( \beta) \neq I( \gamma) \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}
}
Bei
\mavergleichskettedisp
{\vergleichskette
{I( \alpha )
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
sagt man, dass der Ausdruck $\alpha$ bei der Wahrheitsbelegung $\lambda$
\zusatzklammer {oder der Interpretation $I$} {} {}
wahr wird
\zusatzklammer {oder gilt} {} {,}
andernfalls, dass er falsch wird
\zusatzklammer {nicht gilt} {} {.}
Dafür schreibt man auch
\mathl{I \vDash \alpha}{} bzw.
\mathl{I \not \vDash \alpha}{.} Mit $I^\vDash$ bezeichnen wir die Menge aller bei der Interpretation $I$ wahren Ausdrücke aus der Sprache. Wenn
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Menge an Ausdrücken ist, so bedeutet
\mathl{I \vDash \Gamma}{,} dass
\mathl{I \vDash \alpha}{} für alle
\mathl{\alpha \in \Gamma}{} gilt. Dafür sagt man auch, dass $\Gamma$ bei der Interpretation $I$ gilt oder dass $I$ ein \stichwort {Modell} {} für $\Gamma$ ist.
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{V
}
{ = }{\{p,q,r\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $\lambda$ sei die
\definitionsverweis {Wahrheitsbelegung}{}{}
mit
\mathl{\lambda(p)=1,\, \lambda(q)=1, \, \lambda(r)=0}{.} Es sei $I$ die zugehörige
\definitionsverweis {Interpretation}{}{.}
Zur Berechnung des Wahrheitswertes von
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { { \left( \neg { \left( (p) \wedge (\neg (q) ) \right) } \right) } \rightarrow ( r )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
unter dieser Interpretation muss man rekursiv gemäß
Definition 2.12
die einzelnen Bestandteile auswerten. Es ist
\mavergleichskettedisp
{\vergleichskette
{ I((\neg q))
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit
\mavergleichskettedisp
{\vergleichskette
{ I( (p) \wedge ( \neg (q)))
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Also ist
\mavergleichskettedisp
{\vergleichskette
{ I { \left( \neg { \left( (p) \wedge ( \neg (q)) \right) } \right) }
}
{ =} { 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Andererseits ist
\mavergleichskettedisp
{\vergleichskette
{ I( r)
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und daher ist
\mavergleichskettedisp
{\vergleichskette
{I(\alpha)
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Der Ausdruck ist also bei dieser Wahrheitsbelegung nicht wahr.
}