Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 6/kontrolle

Prädikatenlogik

Mit der Aussagenlogik kann man keine gehaltvollen mathematischen Aussagen behandeln. Beispielsweise fehlt in ihr das Gleichheitszeichen, und man kann nicht über Variabeln, die sich auf eine Grundmenge beziehen, quantifizieren. Dies führt zur Prädikatenlogik, der wir uns nun zuwenden, und mit der man einen Großteil (in einem gewissen Sinn die ganze) der Mathematik ausdrücken kann. Von der mathematischen Praxis her ist sie aber immer noch recht restriktiv.

Terme

Betrachten wir die sinnvollen Ausdrücke, die für eine natürliche Zahl stehen können. Mit dem Ziffernalphabet ${}Z=\{0,1,2,3,4,5,6,7,8,9\}$ kann man mit der rekursiven Vorschrift zur Generierung von Zeichenreihen aus einem Alphabet alle natürlichen Zahlen (im Zehnersystem) aufschreiben, z.B. ${}530386275$. Allerdings gibt es hier ein paar Schwierigkeiten, es sind nämlich auch die Zahlen ${}0530386275$, ${}00530386275$, u.s.w. erlaubt (und untereinander verschieden, da sie eben unterschiedliche Symbolfolgen sind). Der „Zahlenwert“ steht im Moment noch nicht zur Verfügung. Ferner möchte man das leere Zahlwort nicht als erlaubte Ziffernfolge ansehen.

Mit dieser Menge an erlaubten Zahlwörtern kann man Telefonnummern oder Internetadressen bezeichnen, aber noch nicht das machen, was man eigentlich mit Zahlen machen möchte, nämlich Zählen, Rechnen, Probleme formulieren und lösen. Für die innerhalb der natürlichen Zahlen ausführbaren Rechenoperationen, insbesondere das Nachfolgernehmen (also das Zählen) und die Addition und die Multiplikation, brauchen wir neue Symbole. Eine Aussage wie

${}5\cdot 3=8+7\,$

ist natürlich wahr, da links und rechts ${}15$ „steht“, wie man durch „ausrechnen“ (also das korrekte Anwenden der Rechenregeln) überprüfen kann. Wenn man allerdings solche Gleichungen logisch verstehen und analysieren möchte, so sollte man die beiden Seiten nicht als ${}15$ lesen, sondern jeweils als ein neues „komplexes Zahlwort“, das sich aus den Ziffernsymbolen ${}5$ und ${}3$ und dem Malzeichen ${}\cdot$ bzw. den Ziffernsymbolen ${}8$ und ${}7$ und dem Pluszeichen ${}+$ zusammensetzt. Die linke und die rechte Seite sind hier sogenannte Terme, also sinnvolle mathematische Ausdrücke, die einen Zahlwert annehmen können bzw. formal den Charakter einer Zahl haben (der Vergleich der beiden Terme durch ${}=$ macht aus den beiden Termen eine Aussage, das spielt jetzt aber noch keine Rolle). Ein weiteres Beispiel ist eine Gleichung der Form

${}4\cdot x=3\cdot (8+y)\,,$

wo vermutlich nach den erlaubten Werten für ${}x$ und ${}y$ gesucht wird, die diese Gleichung erfüllen. Aber unabhängig von dieser typischen Interpretation stehen links und rechts ebenfalls Terme, in denen jeweils eine Variable vorkommt. Solche Terme sind ein konstitutiver Bestandteil der Prädikatenlogik und werden, ausgehend von einer Variablenmenge (keine Aussagenvariablenmenge), einer Konstantenmenge und verschiedenen Funktionssymbolmengen, rekursiv definiert.

Definition Referenznummer erstellen

Eine Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.

1. eine Variablenmenge ${}V$,
2. eine Konstantenmenge ${}K$,
3. zu jedem ${}n\in \mathbb {N} _{+}$ eine Menge ${}F_{n}$ von Funktionssymbolen.

Dabei können die auftretenden Mengen leer sein, es ist für die Funktionssymbole sogar typisch, dass es nicht zu jeder Stelligkeit (zu jedem ${}n$) ein Funktionssymbol gibt (die Variablenmenge wird hingegen meistens als nicht leer angesetzt, und zwar mit unendlich vielen Variablen, die häufig als ${}x_{1},x_{2},x_{3},\ldots$ angesetzt werden). Die Konstanten kann man auch als nullstellige Funktionssymbole auffassen. Unter dem Termalphabet versteht man die Vereinigung ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$.

Die arithmetische Grundtermmenge besteht aus den beiden Konstanten ${}0,1$, den beiden zweistelligen Funktionssymbolen ${}\{+,\cdot \}$ und einer Variablenmenge.

Definition Definition 6.2 ändern

Zu einer Grundtermmenge ${}G=(V,K,F_{n})$ ist die zugehörige Termmenge (oder die Menge der ${}G$-Terme) diejenige Teilmenge ${}T=T(G)$ der Wörter ${}A^{*}$ über dem Termalphabet ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$, die durch die folgenden rekursiven Vorschriften festgelegt wird.

1. Jede Variable ${}v\in V$ ist ein Term.
2. Jede Konstante ${}c\in K$ ist ein Term.
3. Für jedes ${}f\in F_{n}$ und ${}n$ Terme ${}t_{1},t_{2},\ldots ,t_{n}$ ist auch ${}ft_{1}t_{2}\ldots t_{n}$ ein Term.

Hierbei sind ${}(1)$ und ${}(2)$ die Anfangsbedingungen und ${}(3)$ die Rekursionsregel, da darin auf schon gebildete Terme Bezug genommen wird. Wie bei jeder rekursiven Definition ist ein Wort nur dann ein Term, wenn es gemäß dieser Regeln gebildet werden kann.

Gemäß dieser Definition verzichten wir auf Klammern, und die Funktionssymbole werden einheitlich links geschrieben und daran werden rechts davon die Terme angefügt (das wird später so interpretiert, dass in ${}n$-stellige Funktionen ${}n$ Elemente eingesetzt werden). Schon in einfachen Beispielen ist es aber wegen der Lesbarkeit sinnvoll, auch Klammern zu verwenden und von der strengen Reihenfolge bei den Funkltionssymbolen abzuweichen und beispielsweise ${}s+t$ statt ${}+st$ zu schreiben. Solche Schreibweisen sind als Ersatz für die formal korrekt gebildeten Terme zu interpretieren, sie gehören aber nicht zu den Termen.

Beispiel Beispiel 6.3 ändern

Eine Grundtermmenge sei durch die Variablenmenge ${}V=\{x,y,z\}$, eine Konstantenmenge ${}K=\{c_{1},c_{2}\}$, die einstelligen Funktionssymbole ${}F_{1}=\{f,g\}$ und die zweistelligen Funktionssymbole ${}F_{2}=\{\alpha ,\beta ,\gamma \}$ gegeben. Dann sind die folgenden Wörter Terme.

$x,y,z,c_{1},c_{2},fx,fc_{1},gz,\alpha xy,\alpha xx,\alpha xfy,\alpha fxgc_{1},\gamma \gamma xxx,\beta \alpha xgc_{2}\gamma fy\alpha gzx.$

Auch wenn es für das Auge etwas ungewohnt aussieht, so sind diese Terme auch ohne Klammern allesamt wohldefiniert. Davon überzeugt man sich, indem man die Terme von links nach rechts liest, und dabei bei jedem Funktionssymbol die zugehörige Stelligkeit bestimmt (zu welchem ${}F_{n}$ gehört das Funktionssymbol?) und dann die folgenden Symbole in die geforderten ${}n$ Terme aufspaltet (wenn dies nicht geht, so ist das Wort kein Term). Dabei entsteht schnell eine große Verschachtelungstiefe. Den letzten angeführten Term, also

$\beta \alpha xgc_{2}\gamma fy\alpha gzx,$

kann man mit (suggestiven) Klammern und Kommata nach und nach lesbarer gestalten. Er beginnt mit dem zweistelligen Funktionssymbol ${}\beta$, also muss das Folgende aus zwei Termen bestehen. Es folgt zunächst das ebenfalls zweistellige Funktionssymbol ${}\alpha$, worauf zwei Terme folgen müssen. Wenn diese gefunden sind, muss der verbleibende Rest (also alles, was weiter rechts steht) den zweiten Term bilden, der von ${}\beta$ verlangt wird. Die beiden Terme des an zweiter Stelle stehenden ${}\alpha$ sind ${}x$ und ${}gc_{2}$. Man kann also den Term nach dieser Analyse auch als

$\beta (\alpha (x,g(c_{2})),\gamma fy\alpha gzx)$

schreiben. Wenn man ebenso den zweiten Term für das äußere ${}\beta$ auflöst, so erhält man

$\beta (\alpha (x,g(c_{2})),\gamma (f(y),\alpha (g(z),x))).$

Übrigens kann man auch bei einem beliebigen Funktionssymbol mittendrin beginnen und die zugehörigen Terme, auf die es Bezug nimmt, bestimmen. Besonders übersichtlich wird die Termstruktur durch einen Termstammbaum ausgedrückt. Dabei werden die verwendeten Variablen und Konstanten (mehrfach, um die unterschiedlichen Stellen, in die sie eingesetzt werden, beachten zu können) als Blätter nebeneinander aufgeführt. Sie bilden die ${}0$-te Reihe des Baumes. Wenn ein ${}n$-stelliges Funktionssymbol auf ${}n$ solche Blätter angewendet wird, so zeichnet man einen Knoten, bezeichnet ihn mit dem Funktionssymbol (bzw. dem Funktionssymbol mit den eingelesenen Termen) und verbindet es mit den eingelesenen Blättern (die Einlesungsreihenfolge entspricht der Blätterreihenfolge). So entsteht aus allen Funktionssymbolen, die nur auf Variablen und Konstanten Bezug nehmen, die erste Reihe des Baumes. Die Funktionssymbole, die auf solche Knoten (und Blätter) Bezug nehmen, bilden die nächste Reihe, u.s.w. Der Stamm des Baumes ist dann der in Frage stehende Term. In unserem Beispiel sieht das so aus:

Beispiel Referenznummer erstellen

Wir betrachten ein Modell für die Termmenge der natürlichen Zahlen. Als Grundtermmenge nehmen wir eine Variablenmenge ${}V$, die Konstantenmenge ${}K=\{0\}$, die einstelligen Funktionssymbolmenge ${}F_{1}=\{N\}$ (${}N$ steht für Nachfolger) und die zweistellige Funktionssymbolmenge ${}F_{2}=\{\alpha ,\mu \}$ (für Addition und Multiplikation). Allein aus der Konstante ${}0$ und dem Nachfolgersymbol ${}N$ kann man dann für jede natürliche Zahl eine Repräsentierung finden, nämlich

$N0\,,NN0,\,NNN0,\,NNNN0,\,etc.$

Typische Terme sind dann Ausdrücke wie (${}u,v,w$ seien Variablen)

$\alpha NN0NNNv,\,\mu NN0\alpha NN0NNN0,\,\mu \alpha NNN0\mu NNuN0NNNNw,\,{\text{etc}}.$

Wenn man ${}x'$ statt ${}Nx$, ${}(x+y)$ statt ${}\alpha xy$ und ${}(x\cdot y)$ statt ${}\mu xy$ schreibt, so „verschönern“ sich diese Terme zu

$(0^{\prime \prime }+v^{\prime \prime \prime }),\,(0^{\prime \prime }\cdot (0^{\prime \prime }+0^{\prime \prime \prime })),\,((0^{\prime \prime \prime }+(u^{\prime \prime }\cdot 0^{\prime }))\cdot w^{\prime \prime \prime \prime }),\,{\text{etc}}.$

Mit den Abkürzungen ${}1=0^{\prime }$, ${}2=0^{\prime \prime }$ etc. wird daraus

$2+v^{\prime \prime \prime },\,(2\cdot (2+3)),\,((3+(u^{\prime \prime }\cdot 1))\cdot w^{\prime \prime \prime \prime }),\,{\text{etc}}..$

Man beachte, dass die Einführung dieser Abkürzungen nicht bedeutet, dass dadurch die üblicherweise mit diesen Symbolen verwendeten Rechenregeln erlaubt sind. Der zweite Term oben ist nicht gleich ${}10$, dem zehnten Nachfolger der ${}0$.

Wir erklären noch, was die Variablenmenge eines Terms ist. Diese ist stets eine Teilmenge der Variablenmenge ${}V$ und enthält diejenigen Variablen, die in dem Term irgendwo vorkommen. Die rekursive Definition lautet folgendermaßen.

1. Wenn ${}t=x$ eine Variable ist, so ist ${}\operatorname {Var} (x)=\{x\}$.
2. Wenn ${}t=c$ eine Konstante ist, so ist ${}\operatorname {Var} (c)=\emptyset$.
3. Wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist und wenn ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist ${}\operatorname {Var} (ft_{1},\ldots ,t_{n})=\operatorname {Var} (t_{1})\cup \ldots \cup \operatorname {Var} (t_{n})$.

Aristoteles (384-322 v.C.) gilt als Erfinder der Prädikatenlogik. Er verwendet in seiner Analytik Variablen, einstellige Prädikate, Quantoren und die logischen Junktoren.

Nachdem wir die Terme zur Verfügung haben, fahren mit dem syntaktischen Aufbau der Ausdrücke in der Prädikatenlogik (mit Identität) fort. Um den Aufbau dieser formalen Sprache zu motivieren und das Verständnis der zunächst rein formalen Ausdrücke zu erleichtern, ist es hilfreich, an Bildungsweisen von mathematischen Aussagen zu erinnern. Der konsequente Aufbau der Syntax und der Semantik folgt in der nächsten Vorlesung.

Relationen

Ein Term kann weder wahr noch falsch sein, und zwar unabhängig davon, ob man ihn einfach als ein nach gewissen formalen Regeln aufgebautes Symbolwort auffasst oder ihn in einer bestimmten Menge (etwa den natürlichen Zahlen) interpretiert. Wahr oder falsch können nur Aussagen sein. Wichtig sind für uns zunächst die formalen Eigenschaften einer Aussage. In mathematischen Aussagen kommen häufig Terme zusammen mit einem Vergleichssymbol vor, z. B. in der (wahren) Gleichung

$2\cdot (2+3)=10$

oder der (falschen) Abschätzung

$2\cdot (2+3)<10.$

Mit zwei Termen und dem Gleichheitszeichen oder Kleinerzeichen gelangt man also zu Aussagen, man spricht von zweistelligen Relationen (in Logik und Grammatik auch von zweistelligen Prädikaten). Der Wahrheitsgehalt hängt dabei von den zwei Eingaben ab.

Eine einstellige Relation oder ein Prädikat ist eine Eigenschaftsform, die einem Element zukommen kann oder nicht, z.B. die Eigenschaft einer natürlichen Zahl, prim zu sein oder gerade zu sein oder eine Quadratzahl zu sein, oder das Positivitätsprädikat, das besagt, dass eine reelle Zahl positiv ist. Einstellige Prädikate definieren eine Teilmenge einer gegebenen Grundmenge: Einem einstelligen Prädikat wird diejenige Teilmenge zugeordnet, die aus allen Elementen besteht, für die das Prädikat gilt. Daher entspricht die Mengenlehre weitgehend der Prädikatenlogik mit nur einstelligen Prädikaten.

Mit ${}n$-stelligen Relationenssymbolen und ${}n$ Termen gelangt man ebenfalls zu einer Aussage. Wenn z.B. ${}A,B,C$ als Punkte in der Ebene interpretiert werden können, und ${}G$ die Relation „bildet ein gleichseitiges Dreieck“ bedeutet, so bedeutet ${}G(A,B,C)$, dass diese drei Punkte ein gleichseitiges Dreieck bilden. Der Wahrheitsgehalt hängt natürlich von der Lage der Punkte ${}A,B,C$ ab, hier interessiert aber lediglich, dass ${}G(A,B,C)$ eine sinnvolle Aussageform repräsentiert.

Andere geometrische Beispiele für dreistellige Relationen sind die Eigenschaften, dass die drei Punkte ${}A,B,C$ auf einer Geraden liegen, sagen wir ${}L(A,B,C)$, oder dass die drei Punkte ein rechtwinkliges Dreieck bilden, wobei der rechte Winkel an dem zuerst genannten Eckpunkt liegen muss, sagen wir ${}R(A,B,C)$. Man kann sich darüber streiten, ob bei einem Dreieck die Eckpunkte alle verschieden sein müssen, jedenfalls kann man die Eigenschaft der drei Punkte, dass sie paarweise verschieden sind, durch ein dreistelliges Prädikat ausdrücken, sagen wir ${}V(A,B,C)$.

Quantoren

Mathematische Aussage enthalten häufig auch Existenzaussagen. Wenn wir bei dem eben erwähnten Beispiel bleiben, so bedeutet

${\text{es gibt }}z\,G(A,B,z)$

die Aussage, dass es zu gegebenen festen ${}A$ und ${}B$ ein ${}z$ gibt derart, dass die drei Punkte ${}A,B,z$ ein gleichseitiges Dreieck bilden (diese Aussage ist in der reellen Zahlenebene wahr). In dem Beispielsatz wird nur über ${}z$ quantifiziert, nicht über ${}A$ und ${}B$. Dies kann man durch die folgenden Aussagen erreichen.

${\text{es gibt }}x{\text{ und es gibt }}y{\text{ und es gibt }}z\,G(x,y,z),$

was bedeutet, dass es Punkte ${}x,y,z$ gibt, die ein gleichseitiges Dreieck bilden, die wahr ist, aber deutlich schwächer als die Aussage

${\text{ für alle }}x{\text{ und }}{\text{ für alle }}y{\text{ gibt es }}z\,G(x,y,z)$

ist, die behauptet, dass es zu (beliebig vorgegebenen) Eckpunkten ${}x$ und ${}y$ stets einen dritten Punkt gibt, sodass ein gleichseitiges Dreieck entsteht. Die Ausdrücke „es gibt“ und „für alle“ nennt man Quantoren. Für diese Quantoren gibt es spezielle Symbole, nämlich ${}\exists$ für „es gibt“ und ${}\forall$ für „für alle“. Die obigen Beispielsätze schreibt man dann formal als

$\exists x\exists y\exists zG(x,y,z)$

bzw. als

$\forall x\forall y\exists zG(x,y,z).$

Auf die Reihenfolge bei gleichartigen Quantoren kommt es nicht an (dies ist von der inhaltlichen Bedeutung her klar, wird später aber auch formal im Ableitungskalkül nachgebildet), sie ist aber bei wechselnden Quantoren entscheidend. Beispielsweise ist die Aussage

$\exists z\forall x\forall yG(x,y,z)$

(also die Aussage, dass es einen Punkt gibt, der mit je zwei beliebigen weiteren Punkten ein gleichseitiges Dreieck bildet) im Gegensatz zur vorherigen Aussage nicht wahr.

Junktoren

Eine weitere Art von mathematischen Aussagen entsteht dadurch, dass man Aussagen selbst zueinander in eine logische Beziehung setzt, indem man beispielsweise sagt, dass aus der Aussage ${}\alpha$ die Aussage ${}\beta$ folgt, oder dass ${}\alpha$ und ${}\beta$ zueinander äquivalent sind. Der Satz des Pythagoras besagt, dass wenn zwischen drei Punkten ${}A,B,C$ in der Ebene die Beziehung der Rechtwinkligkeit am Punkt ${}A$ besteht, dass dann zwischen den durch die drei Punkte definierten Streckenlängen ebenfalls eine bestimmte Beziehung zwischen den Abständen besteht. Wenn man die Rechtwinkligkeit wie oben mit dem dreistelligen Relationssymbol ${}R$ und die pythagoreische Längenbeziehung mit dem dreistelligen Relationssymbol ${}S$ bezeichnet, so gilt also

${\text{ aus }}R(A,B,C){\text{ folgt }}S(A,B,C),$

was wir formal als

$\forall A\forall B\forall C(R(A,B,C)\longrightarrow S(A,B,C))$

schreiben. Gilt davon auch die Umkehrung? Folgt also aus ${}S(A,B,C)$, dass ein rechter Winkel an ${}A$ vorliegt? Dies ist in der Tat der Fall! Der Kosinussatz besagt für ein beliebiges (echtes) Dreieck mit einem an ${}A$ anliegenden Winkel ${}\alpha$, dass

${}d(B,C)^{2}=d(A,B)^{2}+d(A,C)^{2}-2d(A,B)d(A,C)\cos \alpha \,$

gilt, wobei ${}d$ den Abstand zwischen zwei Punkten bezeichne. Der „Störterm“ rechts entfällt genau dann, wenn ${}\cos \alpha =0$ ist, und dies ist nur bei ${}90$ Grad der Fall. Daher gilt die Äquivalenz

$\forall A\forall B\forall C(R(A,B,C)\longleftrightarrow S(A,B,C))$

(ein Dreieck, bei dem zwei Eckpunkte zusammenfallen, akzeptieren wir als rechtwinklig an dem doppelten Punkt).

Unser Rechtwinkligkeitsprädikat ${}R(A,B,C)$ besagt, dass der Winkel am Eckpunkt ${}A$ ein Rechter ist. Wenn man sich dafür interessiert, ob überhaupt ein rechtwinkliges Dreieck vorliegt, so muss ${}R(A,B,C)$ oder ${}R(B,C,A)$ oder ${}R(C,A,B)$ gelten. Die Oderverknüpfung wird formal als

$(R(A,B,C)\vee R(B,C,A))\vee R(C,A,B)$

geschrieben (die Assoziativität der oder-Verknüpfung steht im Moment noch nicht zur Verfügung).

Für ein echtes Dreieck haben wir oben gefordert, dass die konstituierenden Punkte ${}A,B,C$ paarweise verschieden sind. Die Gleichheit von zwei Punkten wird durch ${}A=B$ und die Negation davon, also die Verschiedenheit der beiden Punkte, wird in der Mathematik durch ${}A\neq B$, in der Logik aber durch ${}\neg {\left(A=B\right)}$ ausgedrückt. Dass drei Punkte paarweise verschieden sind, erfordert ein logisches und, das durch ${}\wedge$ symbolisiert wird, sodass sich die Echtheit eines Dreiecks durch

${\left(\neg {\left(A=B\right)}\wedge \neg {\left(A=C\right)}\right)}\wedge \neg {\left(B=C\right)}$

ausdrücken lässt.

Fußnoten