Mathematisches Basiswissen für Informatiker

Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik Johann Wolfgang Goethe-Universität Postfach 11 19 32 D-60054 Frankfurt Germany E-mail:schauss@ki.informatik.uni-frankfurt.de

22. Dezember 1997

1 Aussagenlogik (propositional logic)

Eine Aussage ist ein (schrift-)sprachliches Gebilde, von dem es sinnvoll ist zu sagen, es sei wahr oder falsch.

Beispiele.

• 0 = 1

• “es regnet“

• “Es ist jetzt 8:15“

Die obige “Definition“ ist problematisch, wie die Antinomie (das Paradoxon) des Lügners zeigt: “Die Aussage dieses Satzes ist falsch“.

Die klassische formale Aussagenlogik geht daher von der Vorstellung aus, daß es atomare Aussagen gibt, die wahr oder falsch sein können, und daß komplexere Aussagen aus Junktoren und solchen atomaren Aussagen zusammengesetzt sind. Die Antinomie des Lügners wird dadurch umschifft, daß es Regeln gibt für die Wahrheit bzw. Falschheit von Aussagen, die nur abhängig sind vom Wert der Einzelaussagen (atomaren Aussagen). Für die Wahrheit/Falschheit von Aussagen ist es nicht notwendig, daß man die Wahrheit oder Falschheit von (z.B. atomaren Aussagen) auch leicht bestimmen kann: z.B. “Jede ungerade Zahl, die größer als drei ist, ist Summe von zwei Primzahlen“. Diese Aussage (Goldbachsche Vermutung) ist entweder wahr oder falsch, aber zur Zeit kennt man deren Wahrheitswert nicht.

Die klassische Aussagenlogik geht von zwei Wahrheitswerten aus, T und F (T für True, wahr; F für falsch, und von Junktoren ∧, ∨, ¬, ⇔, ⇒ für und, oder, nicht, äquivalent, impliziert. Hierbei ist ¬ einstellig, während alle anderen Junktoren (Operatoren) zweistellig sind. Eine Grammatik zur (syntaktischen) Erzeugung von Aussagen ist:

\begin{aligned}F & ::= & A | F | (¬F) | (F ∧ F) | \\ & & (F ∨ F) | (F ⇒ F) | (F ⇔ F) \end{aligned}

Hierbei bezeichnet A ein Atom und F eine bereits gebildete Aussage.

Die Berechnung des Wahrheitswertes von zusammengesetzten Aussagen wird mittels Wahrheitswerttabellen definiert:

\begin{matrix}A & ¬A \\ T & F \\ F & T \end{matrix}

\begin{matrix}A & B & A ∧ B & A ∨ B & A ⇒ B & A ⇔ B \\ T & T & T & T & T & T \\ T & F & F & T & F & F \\ F & T & F & T & T & F \\ F & F & F & F & T & T \end{matrix}

Zum Beispiel:

“7 ist nicht prim ∧ die Goldbachsche Vermutung“ entspricht (¬(7 ist prim) ) ∧ (die Goldbachsche Vermutung stimmt).

Wertet man das entsprechend der Wahrheitstafel aus, so ergibt sich (¬(T))∧ “die Goldbachsche Vermutung stimmt“) = (F ∧ “die Goldbachsche Vermutung stimmt“ = F

Definition 1. Eine Aussageform (aussagenlogische Formel, Boolesche Form, propositional formula) ist ein Ausdruck, in dem von atomaren Aussagen abstrahiert wird, und statt dessen Aussagenbezeichner (aussagenlogische Variablen) eingesetzt werden. Eine Grammatik zur syntaktischen Erzeugung von Aussageformen ist:

\begin{aligned}F & ::= & P | (¬F) | (F ∧ F) | \\ & & (F ∨ F) | (F ⇒ F) | (F ⇔ F) \end{aligned}

Hierbei bezeichnet P eine Variable und F eine bereits gebildete Aussage.

Beispiele für Aussageformen sind:

Beispiel 1.

1. A, B, … Aussagenvariablen 2. (A ∨ (¬A))

3. (A ⇔ (¬(¬A)))

Im folgenden werden wir Aussageformen auch kurz als Aussagen bezeichnen.

Die formale Definition erfordert mehr Klammern als tatsächlich notwendig sind, deshalb läßt man zum Teil Klammern weg, wenn sie nicht für die Eindeutigkeit notwendig sind. Als Konvention nimmt man an, daß es folgende Prioritäten von Operatoren gibt: ¬ vor ∧ vor ∨ vor ⇒ vor ⇔. Weiterhin läßt man im allgemeinen auch die Klammern bei assoziativen Operatoren wie ∨ und ∧ weg und nimmt implizite Linksklammerung an. Zum Beispiel ist A ⇒ A∨B∨¬C die Aussage A ⇒ ((A∨B)∨(¬C)). Siehe auch Paragraph 14 über Notationen.

Es gilt: Gegeben eine Aussage A mit den Aussagenvariablen A_{i}, i = 1, …, n. Wenn man allen Aussagenvariablen einen der Werte T oder F zuordnet, so läßt sich der Wahrheitswert der so gebildeten Aussage ausrechnen.

Beispiel 2. Betrachte die Aussage (¬A ∧ B) ∨ (A ∧ ¬B) mit den Aussagevariablen A, B. Die möglichen Belegungen sind in der Tabelle aufgelistet.

\begin{matrix}A & B & ¬B & A ∧ ¬B & ¬A & ¬A ∧ B & (A ∧ ¬B) ∨ (¬A ∧ B) \\ T & T & F & F & F & F & F \\ T & F & T & T & F & F & T \\ F & T & F & F & T & T & T \\ F & F & T & F & T & F & F \end{matrix}

Die Aussage (A ∧ ¬B) ∨ (¬A ∧ B) verhält sich wie ein auschließendes oder (exclusive or, XOR), das auf die zwei Variablen A, B angewendet wird.

Definition 2. Eine Interpretation (Belegung) einer Aussageform A ist eine Abbildung, die allen aussagenlogischen Variablen in A einen Wert in {T, F } zuordnet. Eine Aussageform heißt Tautologie (bzw.Widerspruch, unerfüllbar), wenn sie bei jeder Belegung der Variablen mit Wahrheitswerten stets T (bzw. F) ergibt. Eine Aussageform A heißt erfüllbar, wenn es eine Belegung der Variablen mit Wahrheitswerten gibt, so daß die Auswertung der Aussageform T ergibt; eine solche Belegung heißt auch Modell von A. Zwei Aussageformen heißen äquivalent, wenn ihre Wahrheitstafeln gleich sind.

Beispiel 3.

1. A ∨ ¬A ist eine Tautologie.

2. A ∧ ¬A ist ein Widerspruch.

3. A ∨ B ist weder eine Tautologie noch ein Widerspruch, aber erfüllbar Die Aussagen A ∨ B und ¬(¬A ∧ ¬B) sind äquivalent.

Satz 3. Eine Aussage A ist eine Tautologie genau dann, wenn ¬A unerfüllbar ist.

Satz 4. Zwei Aussagen A, B sind äquivalent genau dann wenn A ⇔ B eine Tautologie ist.

Damit gilt auch: A ist eine Tautologie gdw. A äquivalent zu T ist. A ist ein Widerspruch gdw. A äquivalent zu F ist.

Wir wollen im folgenden Variablen in Aussagen nicht nur durch die Wahrheitswerte T, F ersetzen, sondern auch durch Aussageformen. Wir schreiben dann A[B/x], wenn in der Aussage A die Aussagenvariable x durch die Aussage B ersetzt wird. In Erweiterung dieser Notation schreiben wir auch: A[B_{1}/x_{1}, …, B_{n}/x_{n}], wenn mehrere Aussagevariablen ersetzt werden sollen. Diese Einsetzung passiert gleichzeitig, so daß dies kompatibel zur Eigenschaft der Komposition als Funktionen ist: Wenn A n-stellige Funktion in den Aussagevariablen ist, dann ist A[B_{1}/x_{1}, …, B_{n}/x_{n}] die gleiche Funktion wie A ∘ (B_{1}, …, B_{n}).

Satz 5. Sind A_{1}, A_{2} äquivalente Aussagen, und B_{1}, …, B_{n} weitere Aussagen, dann sind A_{1}[B_{1}/x_{1}, …, B_{n}/x_{n}] und A_{2}[B_{1}/x_{1}, …, B_{n}/x_{n}] ebenfalls äquivalent.

Beweis. Man muß zeigen, daß jede Zeile der Wahrheitstabelle für die neuen Ausdrücke gleich sind. Seien y_{1}, …, y_{m} die Variablen. Den Wert einer Zeile kann man berechnen, indem man zunächst die Wahrheitswerte für B_{i} berechnet und dann in der Wahrheitstabelle von A_{i} nachschaut. Offenbar erhält man für beide Ausdrücke jeweils denselben Wahrheitswert. ⊓ ⊔

Man kann auch T und F selbst als Konstanten in Aussageformen zulassen. Wir werden diese im folgenden zulassen, und so tun als wären die Konstanten und der entsprechende Wert identisch. Dies erweitert nicht die Fähigkeit zum Hinschreiben von logischen Ausdrücken, denn man könnte T als Abkürzung von A∨¬A , und F als Abkürzung von A∧¬A auffassen. Die Junktoren ∧ und ∨ sind kommutativ, assoziativ, und idempotent, d.h. es gilt:

\begin{aligned}F ∧ G & ⇔ & G ∧ F \\ F ∧ F & ⇔ & F \\ F ∧ (G ∧ H) & ⇔ & (F ∧ G) ∧ H \\ F ∨ G & ⇔ & G ∨ F \\ F ∨ (G ∨ H) & ⇔ & (F ∨ G) ∨ H \\ F ∨ F & ⇔ & F \end{aligned}

Weiterhin gibt es für Aussageformen noch Rechenregeln und Gesetze, die wir im folgenden auflisten wollen. Alle lassen sich mit Hilfe der Wahrheitstafeln beweisen, allerdings erweist sich das bei steigender Variablenanzahl als mühevoll, denn die Anzahl der Überprüfungen ist 2^{n} wenn n die Anzahl der Aussagenvariablen ist. Die Frage nach dem maximal nötigen Aufwand (in Abhängigkeit von der Größe der Aussageform) für die Bestimmung, ob eine Aussageform erfüllbar ist, ist ein berühmtes offenes Problem der (theoretischen) Informatik, das SAT ∈ P-Problem, dessen Lösung weitreichende Konsequenzen hätte, z.B. würde P = N P daraus folgen. Im Moment geht man davon aus, daß dies nicht gilt.

Lemma 6 Äquivalenzen:.

¬(¬A))  ⇔ A
A ⇒ B  ⇔ ¬A ∨ B
A ⇔ B  ⇔ A ⇒ B ∧ B ⇒ A
¬(A ∧ B) ⇔ ¬A ∨ ¬B (DeMorgansche Gesetze)
¬(A ∨ B)  ⇔ ¬A ∧ ¬B
A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)  Distributivität
A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)  Distributivität
(A ⇒ B) ⇔ (¬B ⇒ ¬A) Kontraposition
A ∨ (A ∧ B) ⇔ A  Absorption
A ∧ (A ∨ B) ⇔ A  Absorption

Diese Regeln sind nach Satz 5 nicht nur verwendbar, wenn A; B; C Aussagevariablen sind, sondern auch, wenn A, B, C für Aussagen stehen.

Einige Vereinfachungen, wenn T und F als Konstante vorkommen. Beachte, daß wegen der Kommutativität hier auch die symmetrischen Regeln gelten.

Lemma 7.

\begin{aligned}A ∧ T & ⇔ & A \\ A ∧ F & ⇔ & F \\ A ∨ T & ⇔ & T \\ A ∨ F & ⇔ & A \\ ¬T & ⇔ & F \\ ¬F & ⇔ & T \end{aligned}

Vom logischen Standpunkt aus gesehen, sind Schlußregeln Anweisungen, wie man aus einer Menge von gegebenen Formeln, die man als wahr annimmt, oder als wahr eingesehen hat, weitere wahre Formeln herleiten kann. In der klassischen Aussagenlogik kann man Schlußregeln in direkte Beziehung zu Tautologien setzen.

Schlußregeln:

((A ⇒ B) ∧ A)  ⟹ B  (modus ponens)
((A ⇒ B) ∧ ¬B)  ⟹ ¬A  (modus tollens)
((A ⇒ B) ∧ (B ⇒ C)) ⟹ (A ⇒ C) (modus barbara, Transitivität von ⇒)

Satz 8. Jede Aussage kann durch eine äquivalente Aussage ersetzt werden, die nur noch die folgenden Mengen von Junktoren enthält.

1. {∨, ∧, ¬} oder

2. {∨, ¬} oder 3. {∧, ¬} oder

4. {NAND}, wobei NAND(x, y) := ¬(x ∧ y), oder

5. {NOR}, wobei NOR(x, y) := ¬(x ∨ y).

Beweis. 1. folgt aus den obigen Regeln.

2. A ∧ B ist äquivalent zu ¬(¬A ∨ ¬B). Damit kann man ∧ simulieren. Die Behauptung folgt dann aus 1).

3. A ∨ B ist definierbar durch ¬(¬A ∧ ¬B)

4. ¬A ist definierbar durch NAND(A, A). A ∧ B ist definierbar durch ¬(NAND(A, B))

5. ähnlich zu 4. ⊓ ⊔

Bemerkung. Aussagen können in verschiedene Normalformen überführen werden:

• konjunktive Normalform (KNF). Diese ist von der Form: (L_{1,1}∨L_{1,n_{1}})∧…∧(L_{m,1}∨L_{m,n_{m}}). Hierbei sind L_{i,j} die Literale, d.h. Aussagenvariablen oder Negationen von Aussagenvariablen.

• disjunktive Normalform (DNF). Diese ist von der Form: (L_{1,1} ∧L_{1,n_{1}})∨…∨(L_{m,1} ∧L_{m,n_{m}}) Hierbei sind L_{i,j} die Literale, d.h. Aussagenvariablen oder Negationen von Aussagenvariablen.

Die Erzeugung der Normalformen erfolgt durch folgende Transformation unter Verwendung der Regeln für Aussagen: 1) Elimination aller Operatoren, die verschieden sind von ¬, ∨, ∧, 2) Negationszeichen nach innen schieben. 3) Anwenden der Distributivgesetze, je nach gewünschter Normalform. Beachte, daß die KNF und DNF nicht eindeutig sind, auch wenn man Kommutativität, Assoziativität und Idempotenz von ∨, ∧ in Betracht zieht.

Nach Überführung einer Aussage in DNF kann man leicht überprüfen, ob sie einen Widerspruch darstellt: Dies gilt gdw. jede konjunktive Komponente eine Aussagenvariable sowohl negiert als auch nicht negiert enthält. Zur Überprüfung auf Tautologie ist die KNF geeignet: Eine KNF ist Tautologie gdw. in jeder disjunktiven Komponente eine Aussagenvariable existiert, die dort negiert und nicht negiert vorkommt. Allerdings ist diese Überprüfung nicht ganz kostenlos: Die Normalformen können sehr groß werden, auch schon für kleine Formeln.

Eine mechanisches, syntaktisches Verfahren, das aus Aussageformen neue herstellt und/oder Aussageformen umformt, nennen wir Kalkül. Ein Kalkül soll natürlich nicht beliebige Umformungen machen, sondern möglichst solche, bei denen der Wahrheitswert erhalten bleibt. Normalerweise ist es das Ziel eines Kalküls, Tautologien zu erkennen. Hierfür gibt es verschiedene Methoden. Eine haben wir schon kennengelernt: die Methode der Wahrheitstabellen. Eine andere Methode ist es, mit einer Aussageform zu starten, und diese solange nach festgelegten Regeln umzuformen und neue Aussageformen herzustellen, bis ein bestimmtes Ereignis eintritt.

Beispiel 4. Wir geben ein Beispiel für das Vorgehen des Tableaukalküls zum Erkennen, ob eine eingegebene Aussage eine Tautologie ist:

Ist (p ⇒ (q ⇒ p) eine Tautologie?

Idee: Teste ob diese Aussage falsch sein kann. Annahme: p ⇒ (q ⇒ p) = F,

dies erfordert: p = T, q ⇒ p = F,

dies wiederum erfordert p = T, q = T, p = F. Dies ergibt einen Widerspruch, da p nicht wahr und gleichzeitig falsch sein kann.

Dieser Kalkül enthält Regeln, wie jede syntaktische Form einer Aussageform zu zerlegen und daraus ein “Tableau“ zu erstellen ist. z.B. für A ∧ B = T kann A = T und B = T angenommen werden. Für A ∧ B = F muß eine Fallunterscheidung gemacht werden. Ein Fall ist A = F, der andere ist B = F. Der Tableaukalkül liefert bei Eingabe einer Formel A entweder eine erfüllende Belegung für A = F) (also ein Modell für ¬A) oder er findet einen Konflikt bei den Zuweisungen und hat damit die Tautologie-Eigenschaft nachgewiesen.

Eine ganz andere, für unsere Zwecke zunächst nicht so interessante Methode ist die der Hilbertkalküle, die mit einer festen Menge von (einfachen) Tautologien (den Axiomen) starten, und daraus weitere Tautologien herstellen mittels Ersetzung von Aussagevariablen durch Formeln (Einsetzung) oder mittels modus ponens. Ziel ist die Herstellung aller Tautologien. Der modus ponens wird folgendermaßen verwendet: Wenn man schon die folgenden zwei Aussagen abgeleitet hat: F, F ⇒ G, dann kann man damit auch G ableiten. Hier wird das Prinzip der Einsetzung verwendet: wenn F eine Tautologie ist, und A_{1}, …, A_{n} die Aussagenvariablen in F, dann ist auch F(G_{1}, …, G_{n}) eine Tautologie für beliebige Aussageformen G_{i}.

Jede Aussageform mit n Aussagevariablen ist eine Funktion {T, F }^{n} → {T, F }, wobei die Junktoren spezielle Funktionen von {T, F }^{2} → {T, F } und ¬ eine Funktion {T, F } → {T, F } ist. Jede solche Funktion kann man durch ein Aussageform darstellen, d.h., es gilt die funktionale Vollständigkeit:

Satz 9. Jede Funktion von {T, F }^{n} → {T, F } mit n ≥ 1 läßt sich durch eine Aussageform, die höchstens n Aussagenvariablen enthält, darstellen .

Beweis. Wir können die Funktion IF THEN ELSE(x, y, z) darstellen durch die Aussageform (x ⇒ y) ∧ (¬x ⇒ z). Wenn x den Wert T hat, dann hat (x ⇒ y) ∧ (¬x ⇒ z) denselben Wert wie y, und wenn x den Wert F hat, dann hat (x ⇒ y) ∧ (¬x ⇒ z) denselben Wert wie z. Sei f eine beliebige Funktion f : {T, F }^{n} → {T, F }. Wir benutzen Induktion nach der Anzahl der Argumente. Wenn n = 1 ist, dann gibt es genau 4 Funktionen von T, F → T, F. Diese können durch die Ausdrücke x, ¬x, x ∨ ¬x, x ∧ ¬x dargestellt werden, wie man durch Ausprobieren feststellt. Wenn n > 1 ist, dann definiere f_{1}(x_{2}, …, x_{n}) := f(T, x_{2}, …, x_{n}) und f_{2}(x_{2}, …, x_{n}) := f(F, x_{2}, …, x_{n}). Nach Induktionsvoraussetzung gibt es Aussageformen A_{1} und A_{2}, die f_{1}(x_{2}, …, x_{n}) und f_{2}(x_{2}, …, x_{n}) repräsentieren. Dann ist IF THEN ELSE(x_{1}, A_{1}, A_{2}) eine Aussageform, die äquivalent zu f(x_{1}, …, x_{n}) ist. ⊓ ⊔

Die Menge der Aussageformen ist eine Boolesche Algebra.

Definition 10. Eine Boolesche Algebra ist folgendermaßen definiert: In einer Menge B ≠ ∅ gibt es Elemente T und F, weiterhin eine einstellige Operation ¬ und zwei 2-stellige Operationen ∧ und ∨, so daß die Äquivalenzen in 6und 7 erfüllt sind, wobei A, B, C beliebige Elemente der Menge B sind.

Die einfachste Boolesche Algebra ist die Menge {T, F } mit den Operationen ∧, ∨, und ¬.

Übungsaufgabe 11.

Beweise einige Gesetze mit Hilfe der Wahrheitstafeln

Zeige, daß sich ein Absorptiongesetz aus dem anderen herleiten läßt mit Hilfe der anderen Gesetze

Welche Aussageform entspricht der Funktion F (A, B, C), so daß F genau dann wahr ist wenn mindestens 2 Variablen wahr sind.

Übungsaufgabe 12. 1. Schreibe eine Funktion in Gofer, die Aussageformen (mit Operatoren ∧, ∨, ¬) vereinfacht, indem alle T und F entsprechend den Äquivalenzen entfernt werden.

2. Schreibe eine Funktion in Gofer, mit zwei Eingaben:

(a) eine Aussageform als Datenstruktur, und

(b) eine Liste der Belegungen für alle Aussagenvariablen, die den Wahrheitswert der Aussage als Ausgabe liefert.

2 Prädikatenlogik

Die Aussagenlogik abstrahiert nur die Verwendung der Junktoren und die Wahrheitswerte und erfasst somit nicht alle logischen Schlußweisen. Aussagen über Mengen von Individuen wie “alle Menschen sind sterblich“ oder “es gibt eine Primzahl ≤ 3“ werden erst in der Prädikatenlogik auf formale Art und Weise behandelt. Hier wollen wir nur die Schreibweisen der Prädikatenlogik erster Stufe (PL1) einführen, um sie im folgenden zu verwenden. Die folgenden Aussagen lassen sich in PL1 formulieren:

• Alle Menschen sind sterblich

• Jede Primzahl ≥ 3 ist ungerade • Für jede Eigenschaft E: Wenn alle Menschen die Eigenschaft E haben, dann gibt es

auch einen Menschen mit der Eigenschaft E.

Eigenschaften werden durch Prädikate ausgedrückt, zum Beispiel: “x ist Primzahl“ kann als PRIMZAHL(x) geschrieben werden. Prädikate haben eine feste Stelligkeit. Wenn D die Menge der betrachteten Objekte ist, dann kann man ein n-stelliges Prädikat als Funktion von D^{n} → {T, F } betrachten. Zum Beispiel ist < ein zweistelliges Prädikat auf den ganzen Zahlen. Die syntaktische Entsprechung von Funktionen oder Operatoren sind die Funktionssymbole. Hier ist ebenfalls die Stelligkeit festgelegt. Prädikatenlogische Terme sind dann Variablen, oder Konstantensymbole (0-stellige Funktionssymbole) oder Ausdrücke der Form f(s_{1}, …, s_{n}), wobei f ein n-stelliges Funktionssymbol und s_{1}, …, s_{n} prädikatenlogische Terme sind. Der besseren Lesbarkeit halber schreibt man solche Terme manchmal auch in Infixschreibweise: x ∗ y statt ∗(x, y) .

Die All- und Existenzaussagen werden mit Hilfe der Quantoren ∀, ∃ (Allquantor und Existenzquantor) ausgedrückt: “Jede Primzahl ≥ 3 ist ungerade“ kann man hinschreiben als:

∀x : PRIM(x) ∧ x ≥ 3 ⇒ UNGERADE(x),

wobei man PRIM und UNGERADE noch zu definieren hat, z.B. als

∀x : UNGERADE(x) ⇔ ¬(∃y : x = 2 ∗ y)

∀x : PRIM(x) ⇔ (∀y(∀z : x = y ∗ z ⇒ (y = 1 ∨ z = 1)))

Prädikatenlogische Atome sind von der Form Q(t_{1}, …, t_{n}) ,wobei

• Q ein n-stelliges Prädikat ist und,

• t_{1}, …, t_{n} prädikatenlogische Terme sind.

Prädikatenlogische Formeln sind

• Atome, oder

• (¬F), (F ∨ G), (F ∧ G), (F ⇔ G), (F ⇒ G) für Formeln F, G oder

• ∀x : F, ∃x : F für eine Formel F. (Die Zeichen ∀, ∃ nennt man Quantoren).

Eigentlich bräuchte man nur einen Quantor, denn es gilt:

∀x : F ist äquivalent zu ¬(∃x : ¬F) für alle Formeln F.

Eine Variable x ist eine freie Variable in der Formel F, wenn x nicht im Bindungsbereich eines Quantors ist, eine Variable x ist eine gebundene Variable in der Formel F, wenn x im Bindungsbereich eines Quantors ist. Eine Formel ohne freie Variablen heißt auch geschlossene Formel. Man beachte, daß die Variablen in der Prädikatenlogik nicht den Aussagenvariablen entsprechen.

Eine formal exakte Definition kann man wie im Paragraph über λ-Kalkül machen. Man unterscheidet Prädikatenlogiken verschiedener Stufen, wobei diese Unterscheidung nur danach geht, welche Bedeutung die Variablen haben, die von einem Quantor gebunden sind. D.h. ob sie Individuenvariablen sind, oder Prädikate bezeichnen.

Bei der Prädikatenlogik erster Stufe (PL1) darf nur über Individuenvariablen quantifiziert werden. Übersetzt man die Aussage “Für jede Eigenschaft E: Wenn alle Menschen die Eigenschaft E haben, dann gibt es auch einen Menschen mit der Eigenschaft E“ , so erhält man ∀E : ((∀x : Mensch(x) ⇒ E(x)) ⇒ ((∃x : Mensch(x) ∧ E(x)). Dies ist eine Formel der Prädikatenlogik zweiter Stufe. Ebenso ist das Induktionsaxiom nur in der Prädikatenlogik zweiter Stufe formulierbar. Ein weiteres Beispiel ist die Axiomatisierung der reellen Zahlen, wo das sogenannte Supremumsaxiom eine Formel zweiter Stufe ist, da über Teilmengen quantifiziert wird:

(∀M : (M ⊆ R ∧ M ≠ ∅ ∧ UB(M) ≠ ∅) ⇒ ∃r : SUP (M) = r). Normalerweise gilt, daß Formeln der ersten Stufe “normale Prädikatenlogik“ sind, während Formeln zweiter Stufe eher logischen Regeln und Metaregeln entsprechen. Für Formeln dritter und höherer Stufe gibt es kaum anschauliche Anwendungen.

Die Definition einer Tautologie, d.h. eines Satzes der Prädikatenlogik erster Stufe machen wir im folgenden. Beachte dazu den Paragraphen über interpretierte Systeme.

Definition 13. Eine Interpretation I wird folgendermaßen definiert. Als Resultatmenge nimmt man eine Menge D, und definiert I folgendermaßen: Für jedes Funktionssymbol f der Stelligkeit n gibt es eine Abbildung I(f) : D^{n} → D, Für jedes Prädikatensymbol P der Stelligkeit n gibt es eine Funktion I(P) : D^{n} → {T, F }. (Äquivalent dazu ist die Methode, stattdesssen eine n-stellige Relation zu nehmen.) Weiterhin ordnet I jeder Variablen einen Wert in D zu. Eine neue Interpretation kann man durch Abändern des Wertes auf einer Variablen definieren. Indem man den Wert auf x zu d macht, und alles andere läßt. Man erhält eine neue Interpretation, die mit I[d/x] bezeichnet wird. Dann definiert man I induktiv:

I(f(s_{1}, …, s_{n})) := I(f)(I(s_{1}), …, I(s_{n})) (ergibt Werte aus D)
I(P (s_{1}, …, s_{n})) := I(P)(I(s_{1}), …, I(s_{n})) (ergibt T oder F)
I(F ∧ G)  := I(F) ∧ I(G)
I(F ∨ G )  := I(F) ∨ I(G)
I(¬F)  := ¬I(F)
. I(∀x.F) := T, wenn für alle d ∈ D : I[d/x](F) = T
F  anderenfalls.
I(∃x.F) := T, wenn es ein d ∈ D gibt mit I[d/x](F) = T
F  anderenfalls.

Eine Tautologie ist eine geschlossene Formel, die von jeder Interpretation wahr gemacht wird, d.h., die immer auf T abgebildet wird.

Dies ist die Semantik der Prädikatenlogik. Wie können jetzt auch sagen, was die wahren Sätze sind:

Definition 14. Eine Tautologie ist eine Formel ohne freie Variablen, die von jeder Interpretation zu wahr evaluiert wird. Eine Formel F ist erfüllbar, wenn es eine Interpretation I gibt, so daß I(F) wahr wird. Eine solche Interpretation heißt auch Modell der Formel. Eine Formel G, die kein Modell hat, nennt man auch unerfüllbar.

Auch in der Prädikatenlogik erster Stufe gilt:

Satz 15. Eine Formel F ist eine Tautologie genau dann wenn ¬F unerfüllbar ist.

Alle Transformationen auf der syntaktischen Ebene müssen, wenn sie korrekt sein sollen, diese Semantik erhalten. D.h. für eine Transformation G_{1} → G_{2} muß gewährleistet sein, daß I(G_{1}) = I(G_{2}) für alle Interpretationen I gilt. Die erweiterte Ausdruckskraft der Prädikatenlogik gegenüber der Aussagenlogik hat einen Preis: die Überprüfung (anhand der Definition 14, ob eine Aussage eine Tautologie ist, erfordert die Überprüfung von unendlich vielen verschiedenen Interpretationen. D.h. für diesen Zweck ist diese Semantik ungeeignet. Allerdings kann man mit dieser Semantik die Eigenschaften von Transformationen nachweisen.

Es gibt für die Prädikatenlogik Kalküle, die feststellen können, ob eine Aussage eine Tautologie ist. d.h., die für jede Tautologie nach endlich langer Zeit dies auch feststellen. Allerdings kann es passieren, daß diese Kalküle unendlich lange weiterlaufen, falls die zu testende Formel keine Tautologie ist.

3 Mengen

Von G. Cantor stammt die “Definition“ dafür, was eine Menge sein soll:

“Eine Menge ist eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen. Die Objekte heißen Elemente der Menge.“ (G. Cantor).

Man beachte, daß dies keine echte Definition ist, da die vorkommenden Begriffe undefiniert sind. Trotzdem ist dies eine gute intuititve Erklärung des Mengenbegriffs. Wir gehen also davon aus, daß wir wissen was Mengen sein sollen, und führen folgende Schreibweise ein: Wenn x ein Element der Menge M ist, so schreiben wir x ∈ M, und wenn x kein Element von M ist, so schreiben wir x ∉ M.

Im allgemeinen genügt die sogenannte “naive Mengenlehre“, in der die Mengenbildung nicht weiter eingeschränkt ist, d.h. man erlaubt das naive Mengenbildungsprinzip:

∀E : ∃M : ∀x : (x ∈ M ⇔ E(x)) (Jede Eigenschaft definiert eine Menge.)

Hierbei ist E stellvertretend für eine (fast) beliebige prädikatenlogische Formel mit der freien Variablen x.

Diese Menge wird auch geschrieben als {x | E(x)}. Bekanntermaßen führt dieses Mengenbildungsprinzip im Extremfall auf Widersprüche: (Russelsche Antinomie): wenn man die folgende Menge bildet: R := {x|x ∉ x} so führt dies zu einem direkten Widerspruch, denn es würde gelten: R ∈ R ⇔ R ∉ R.

Es gibt verschiedene axiomatische Ansätze, die diese Widersprüche vermeiden, jedoch würde uns das hier zu weit führen. Eine einfache Methode, die diese Widersprüche erfolgreich verhindert, ist die Unterscheidung zwischen Mengen und Klassen, wobei man bestimmte Klassen als Mengen auszeichnet. Das Mengenbildungsaxiom wird zu einem Klassenbildungsaxiom und wird leicht geändert: {x | E(x) und x ist Menge}. Damit kann man dann die Klasse aller Mengen bilden, die dann allerdings keine Menge mehr ist. Auch kann man dann gefahrlos die Klasse aller Programm, Halbgruppen, usw. verwenden. Diese Methode benötigt zusätzlich noch einige Axiome, die definieren, welche Klassen Mengen sind.

Es gilt das Extensionalitätsprinzip:

∀M : ∀N : ((∀x : x ∈ M ⇔ x ∈ N) ⇒ M = N)

D.h.: “Mengen mit den gleichen Elementen sind gleich“

Beispiel 5. Beispiele für Mengenbildung:

Durchschnitt von Mengen: A ∩ B := {x | x ∈ A ∧ x ∈ B}
Vereinigung von Mengen: A ∪ B := {x | x ∈ A ∨ x ∈ B}
Differenz von Mengen:  A \ B := {x | x ∈ A ∧ x ∉ B}
leere Menge:  ∅ := {x | x ≠ x}

\begin{aligned}⋂_{i∈I} A_{i} & := & \{x|∀i : i ∈ I ⇒ x ∈ A_{i}\} \\ ⋃_{i∈I} A_{i} & := & \{x|∃i : i ∈ I ∧ x ∈ A_{i}\} \end{aligned}

Für die Vereinigung (bzw. Durchschnitt) von mehreren Mengen schreiben wir auch: ⋃{A_{i} | i ∈ I} bzw. ⋂{A_{i} | i ∈ I}

Definition 16. Seien A, B Mengen.

1. A ist Teilmenge von B (Schreibweise A ⊆ B), genau dann wenn ∀x : x ∈ A ⇒ x ∈ B.

2. A ist echte Teilmenge von B (Schreibweise A ⊂ B), genau dann wenn A ⊆ B ∧ A ≠ B

3. Potenzmenge von A (Schreibweise P(A), 2^{A}), 2^{A} := {B|B ⊆ A} ( Menge aller Teilmengen)

4. zwei Mengen A und B heißen disjunkt, wenn A ∩ B = ∅. A_{1}, …, A_{n} heißt Zerlegung von A, wenn die A_{i} paarweise disjunkt sind und ⋃{A_{i} | i = 1, …, n} = A.

5. Die Mächtigkeit einer Menge ist die Anzahl der Elemente. Bezeichnung |A|, #A, oder card(A).

Standardbezeichnungen für Mengen:

IN Menge der natürlichen Zahlen (ohne 0)
IN_{0} Menge der natürlichen Zahlen mit 0.
ZZ Menge der ganzen Zahlen.
Q Menge der rationalen Zahlen.
IR Menge der reellen Zahlen.
C Menge der komplexen Zahlen.

Definition 17. Seien A, B Mengen. Das kartesische Produkt von A und B ist definiert durch

• A × B := {(x, y) | x ∈ A, y ∈ B}, wobei (x, y) das geordnete Paar aus den Elementen x, y bezeichnet.

• A_{1} × … × A_{n} := {(x_{1}, …, x_{n})|x_{i} ∈ A_{i}, i = 1, …, n}

• A^{n} := \underbrace{A × … × A}_{n}

Ein Element (x_{1}, …, x_{n}) ∈ A_{1} × … × A_{n} nennt man auch (geordnetes) n-Tupel. Dies kann man auch als Liste von n Elementen ansehen.

Beispiel: {1, 2}^{3} = {(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}

4 Relationen und Funktionen

Definition 18. Seien A, B Mengen. Eine Teilmenge R ⊆ A×B heißt (zweistellige) Relation. Für Mengen A_{1}, …, A_{n} heißt eine Teilmenge R ⊆ A_{1} × … × A_{n} (n-stellige) Relation.

Schreibweise für zweistellige Relationen: (x, y) ∈ R oder xRy oder R(x, y). Beachte, daß Informatiker sehr erfinderisch sind in der Bezeichnung von Relationen, sie kommen in vielen Notationen vor. z.B. ⟹^{∗} ; G,r kann eine Notation für eine Relation sein.

Definition 19. Eine Relation R ⊆ A × B heißt

linkstotal (serial) ⇔ ∀x ∈ A : ∃y ∈ B : (x, y) ∈ R
rechtstotal  ⇔ ∀y ∈ B : ∃x ∈ A : (x, y) ∈ R
rechtseindeutig ⇔ ∀x ∈ A : ∀y ∈ B : ∀z ∈ B : (x, y) ∈ R ∧ (x, z) ∈ R ⇒ y = z
linkseindeutig  ⇔ ∀x ∈ A : ∀y ∈ A : ∀z ∈ B : (x, z) ∈ R ∧ (y, z) ∈ R ⇒ x = y
eineindeutig  ⇔ rechtseindeutig und linkseindeutig

Definition 20.

Eine rechtseindeutige Relation R ⊆ X × Y heißt Funktion (partielle Funktion) von X nach Y.

Eine rechtseindeutige und linkstotale Relation R ⊆ X × Y heißt total definierte Funktion.

Eine total definierte, rechtstotale Funktion R ⊆ X×Y heißt Surjektion (surjektive Funktion) von X auf Y.

Eine total definierte, linkseindeutige Funktion R ⊆ X × Y heißt Injektion (injektive Funktion) von X nach Y.

Ist R ⊆ X × Y eine Injektion und Surjektion, so heißt R Bijektion (bijektive Funktion) von X auf Y.

Ist R ⊆ X × Y eine Funktion, so daß ∀x, y, u, v : (x, u) ∈ R ∧ (y, v) ∈ R ⇒ u = v, so heißt R konstante Funktion.

Schreibweise für Funktionen: R : X → Y, oder X ⟶_{R} Y Bezeichnung: ABB(X, Y) := {R | R : X → Y ist Funktion}.

Definition 21. Sei R ⊆ X × Y eine Relation. Dann definieren wir:

X heißt der Argumentbereich,

Y heißt der Wertebereich,

DEF_{R} := {x ∈ X | ∃y ∈ Y : (x, y) ∈ R} ist der Definitionsbereich (domain) von R.

BIL_{R} := {y ∈ Y | ∃x ∈ X : (x, y) ∈ R} ist der Bildbereich (co-domain, range) von R.

Bemerkung: Wenn R : X → Y total definierte Funktion ist, dann gilt X = DEF_{R}. Wenn R : X → Y rechtstotale Funktion ist, dann gilt Y = BIL_{R}. Insbesondere gilt dies für Surjektionen.

Definition 22. Seien R ⊆ Y ×Z und S ⊆ X ×Y Relationen, dann ist das Kompositum R∘S definiert als R ∘ S := {(x, z) | y ∈ Y, (x, y) ∈ S ∧ (y, z) ∈ R}.

Bemerkung: Sind R und S Funktionen, so auch R ∘ S. Die Anwendung einer Funktion R auf ein Element x schreibt man R(x), wobei R(x) das eindeutig bestimmte Element mit (x, R(x)) ∈ R ist. Für die Anwendung der Komposition R ∘ S gilt: (R ∘ S)(x) = R(S(x)). Beachte, daß die Komposition assoziativ ist, d.h. R ∘ (S ∘ T) = (R ∘ S) ∘ T. (Beachte, daß für die Anwendung verschiedene Konventionen gebräuchlich sind, z.B. wird in manchen Artikeln oder Büchern (R ∘ S)(x) := S(R(x)) definiert.

Beispiel 6. Betrachte die Funktion quadrat: IN → IN mit quadrat := {(a, b) | a, b ∈ IN ∧ b = a∗a}. Üblicherweise kann man dies dadurch beschreiben, daß man sagt: quadrat(x) = x∗x für alle x ∈ IN. Diese Funktion ist total definiert, aber nicht rechtstotal, da 3 nicht in BIL_{quadrat}. Die Funktion quadrat ist linkseindeutig, d.h. quadrat ist Injektion.

Übungsaufgabe 23. . Bestimme alle Funktionen R : X → X mit X = 0, 1. Wieviel total definierte (Surjektionen, Injektionen, Bijektionen) gibt es?

Eine anschauliche Interpretation von Bijektion, Injektion und Surjektion ist die Zuordnung Mäntel → Kleiderhaken:

Bijektion:  An jedem Haken genau ein Mantel
Injektion:  An jedem Haken höchstens ein Mantel
Surjektion:  An jedem Haken mindestens ein Mantel.
Definitionsbereich: Menge der aufgehängten Mäntel
Bildbereich:  Menge der besetzten Haken.

Definition 24. Ist R ⊆ X ×Y eine Relation (Funktion), so heißt R^{−1} := {(y, x) | (x, y) ∈ R} die inverse Relation (bzw. inverse Funktion).

Beispiel 7. F : {0, 1, 2} → {0, 1, 2} mit F = {(0, 0), (1, 0), (2, 1)} ist total definierte Funktion. Es ist F^{−1} = {(0, 0), (0, 1), (1, 2)}. F^{−1} ist keine Funktion, da nicht rechtseindeutig.

Es gilt: Ist F injektiv, dann ist F^{−1} eine Funktion, ist F bijektiv, dann ist F^{−1} ist ebenfalls Bijektion

Definition 25. Sei F : X → Y eine Funktion, A ⊆ X und B ⊆ Y.

1. Das Bild von A unter F ist definiert durch F (A) := {y | ∃x ∈ A : y = F (x)}.

2. Die Restriktion von F auf A ist definiert durch F |_{A} := F ∩ (A × Y)

3. Das Urbild von B unter F ist definiert durch F^{−1}(B) := {x ∈ X | ∃y ∈ B : F x = y}.

4. Ist der Argumentbereich von F ein kartesisches Produkt aus n Mengen X_{1}, …, X_{n}, so ist F eine n-stellige Funktion.

Beispiel 8. Betrachte die Funktion quadrat: IN → IN. Sei G := Menge der geraden Zahlen. Dann ist quadrat(G) = {4, 16, 36, …}, quadrat|_{G} := {(x, y) ∈ quadrat | x ∈ G}. Es ist quadrat^{−1}(G) = IN.

einstellige Funktionen: quadrat : IN → IN

− : IR → IR mit − (x) := −x sin : IR → IR

zweistellige Funktionen: + : IR × IR → IR

∗ : IN × IN → IN

n-stellige Funktionen: |.| : IR^{n} → R mit |(x_{1}, …, x_{n})| := \sqrt{∑_{i=1}^{n} x_{i}^{2}}

(Abstand eines Punktes vom Ursprung in IR^{n})

Definition 26. Eine Menge M heißt unendlich, wenn es eine Injektion f : IN → M gibt. M heißt endlich, wenn sie nicht unendlich ist. Eine Menge heißt abzählbar unendlich, wenn es eine Bijektion f : IN → M gibt. Eine Menge heißt abzählbar, wenn sie endlich ist oder abzählbar unendlich. Eine Menge heißt überabzählbar unendlich, wenn sie unendlich viele Elemente hat und es keine Bijektion f : IN → M gibt.

In der Informatik hat man es im allgemeinen mit abzählbaren Mengen zu tun. Zum Beispiel ist die Menge aller möglichen Programme einer bestimmten Programmiersprache i.a. abzählbar. Wir gehen deshalb etwas genauer darauf ein:

Satz 27. Folgende Konstruktionen erzeugen abzählbare Mengen:

1. Wenn M eine abzählbare Menge ist und f : M → K eine surjektive Abbildung, dann ist K ebenfalls abzählbar.

2. Teilmengen von abzählbaren Mengen sind abzählbar

3. Wenn M_{i}, i ∈ IN abzählbare Mengen sind, dann ist ⋃ M_{i} ebenfalls abzählbar.

4. Wenn M eine abzählbare Menge ist, dann ist M^{n} ebenfalls abzählbar.

5. Wenn M eine abzählbare Menge ist, dann ist ⋃{M^{n} | n > 0} ebenfalls abzählbar.

Beweis. (Skizze) 1.), 2.) und 3.) überlassen wir den Monographien über Mengenlehre. Zum Beweis von 4.) genügt es, n = 2 zu betrachten. Man sieht leicht, daß sich diese Menge als abzählbare Vereinigung von endlichen Mengen schreiben läßt, wobei M_{k} := {(a_{i}, a_{j}) | i + j ≤ k}. ⊓ ⊔

Satz 28. P(IN) ist nicht abzählbar. Ebenso ist die Menge {f | f : IN → IN} nicht abzählbar.

Beweis. (Diagonalisierung) Sei M_{i} eine Aufzählung der Mengen in P(IN). Dann definiere D := {i | i ∉ M_{i}}. Offenbar ist D ∈ P(IN). Deshalb existiert ein j so daß M_{j} = D. Wenn j ∈ M_{j}, dann ist nach Definition von D: j ∉ D = M_{j}. Wenn j ∉ M_{j}, dann ist nach Definition von D: j ∈ D = M_{j}. In beiden Fällen erhalten wir einen Widerspruch.

Zu jeder Menge M ∈ P(IN) gibt es eine Funktion f mit f(IN) = M, also gibt es mindestens soviele Funktionen wie Mengen in P(IN). ⊓ ⊔ Definition 29. Eine Relation in einer Menge M ist eine Teilmenge R ⊆ M^{n}.

Bemerkung. Zweistellige Relationen in einer Menge lassen sich durch Pfeildiagramme (gerichtete Graphen) veranschaulichen. Die Knoten sind die Elemente. Gibt es ein (x, y) ∈ R, so gibt es einen Pfeil (gerichtete Kante) von x nach y.

Definition 30. Eine zweistellige Relation in einer Menge M heißt

reflexiv  :⇔ ∀x ∈ M : xRx.
transitiv  :⇔ ∀x, y, z ∈ M : xRy ∧ yRz ⇒ xRz.
symmetrisch  :⇔ ∀x, y ∈ M : xRy ⇔ yRx.
antisymmetrisch :⇔ ∀x, y ∈ M : xRy ∧ yRx ⇒ x = y
asymmetrisch  :⇔ ∀x, y ∈ M : xRy ⇒ ¬(yRx)
irreflexiv  :⇔ ∀x ∈ M : ¬xRx
linear  :⇔ ∀x, y ∈ M : x ≠ y ⇒ xRy ∨ yRx

Eine reflexive, transitive Relation heißt Präordnung. Eine reflexive, transitive und antisymmetrische Relation R heißt partielle Ordnung (reflexive

Ordnung) Schreibweise ist: (M, R). Eine lineare reflexive Ordnung heißt lineare Ordnung (totale Ordnung, Kette). Eine irreflexive transitive Relation heißt irreflexive Ordnung. Eine antisymmetrische, transitive Relation heißt Präzedenzordnung. Eine asymmetrische, transitive Relation heißt asymmetrische Ordnung. Eine reflexive, symmetrische, transitive Relation heißt Äquivalenzrelation.

Beispiel 9. Beispiele für verschiedene Ordnungen sind: Präordnung: Die Relation R auf Menge definiert durch M R N gdw. |M| ≤ |N|. reflexive Ordnung: ≤ auf Zahlen , ⊆ auf Mengen. lineare Ordnung: ≤ auf Zahlen. irreflexive Ordnungen: < auf Zahlen , ⊂ auf Mengen. Präzedenzordnungen: <, ≤ auf Zahlen , ⊂, ⊆ auf Mengen. asymmetrische Ordnungen: < auf Zahlen , ⊂ auf Mengen. Äquivalenzrelationen: = auf Zahlen , = auf Mengen, R auf Mengen mit der Bedeutung:

M R N, gdw. M und N gleiche Kardinalität haben.

Satz 31. R ist irreflexive Ordnung genau dann wenn R eine asymmetrische Ordnung ist.

Beweis. “⇒ “: Zu zeigen ist, daß irreflexiv ⇒ asymmetrisch. Nehme an, dies sei falsch, dann existieren a, b mit aRb und bRa. Transitivität ergibt aRa, was ein Widerspruch zur Irreflexivität ist. “⇐“: Zu zeigen: asymmetrisch ⇒ irreflexiv. Nehme an, dies sei falsch, dann existiert ein a mit aRa, ein Widerspruch zur Asymmetrie. ⊓ ⊔

Satz 32. Reflexive Ordnungen und irreflexive Ordnungen sind gleichwertig.

1. sei R reflexive Ordnung. Definiere R^{i} mit R^{i} := {(x, y) ∈ R | x ≠ y}. Dann ist R^{i} irreflexive Ordnung mit ∀x, y : x ≠ y ⇒ (xRy ⇔ xR^{i}y)

2. Sei R irreflexive Ordnung: Definiere R^{r} mit R^{r} := R ∪ {(x, x) | x ∈ M}. Dann ist R^{r} reflexive Ordnung mit ∀x, y : x ≠ y ⇒ (xRy ⇔ xR^{r}y)

Bemerkung. Mit den Bezeichnungen oben gilt:

1. (R^{i})^{r} = R wenn R reflexive Ordnung ist

2. (R^{r})^{i} = R, wenn R irreflexive Ordnung ist.

Bemerkung. Zusammenfassend kann man sagen: wesentlich verschiedene Relationen sind: Präordnung, Ordnung, und Äquivalenzrelation. Bei Ordnungen kommt es nicht so sehr darauf an, ob Reflexivität gilt oder nicht, je nachdem was man gerade braucht, schreibt man < für die irreflexive Version und ≤ für die reflexive Version.

Aus jeder Präordnung R auf M läßt sich eine Ordnung konstruieren, indem man zunächst die Äquivalenzrelation R^{=} bildet mit xR^{=}y gdw. xRy ∧ yRx. Danach definiert man die Ordnung auf den Äquivalenzklassen. Diese ist dann eine partielle Ordnung.

Übungsaufgabe 33.

1. Sei R linkstotale, symmetrische und transitive Relation. Dann ist R auch reflexiv.

2. Gilt das noch wenn R nicht linkstotal ist?

Definition 34. Sei R ⊆ M × M eine Relation in M.

1. Die reflexive Hülle R^{r} ist definiert als: R^{r} := R ∪ {(x, x) | x ∈ M}.

2. Die transitive Hülle R^{+} von R ist definiert durch:

(x, y) ∈ R^{+} :⇔ ∃n > 1, x_{1}, …, x_{n} ∈ M : (x = x_{1} ∧ y = x_{n} ∧ ∀i ∈ {1, …, n − 1} : (x_{i}, x_{i+1}) ∈ R 3. Die reflexiv transitive Hülle R^{∗} von R ist definiert als R^{∗} := R^{r} ∪ R^{+}.

Die transitive Hülle einer Relation R kann man sich veranschaulichen als die (gerichtete) Erreichbarkeitsrelation. Z.B. Aufrufhierarchie von Modulen. Wenn R die Relation ist, die zum direkten Aufruf gehört, d.h. M_{1} R M_{2} gdw. M_{1} M_{2} direkt aufruft, dann ist R^{+} die Relation “ruft indirekt auf“. Diese Ordnung ist eine partielle Ordnung, wenn es keine Zyklen gibt (zyklischen Aufrufe), ansonsten eine Präordnung, die wieder eine partielle Ordnung auf den Äquivalenzklassen bildet.

In Programmen oder in der Textverarbeitung werden oft Abkürzungverzeichnisse (Standardtexte) verwendet. Hierbei kann eine Zeichenkette als Abkürzung definiert werden. Die Relation “verwendet direkt“ hat als transitive Hülle die Relation “verwendet indirekt“. Da man keine unendlich großen Zeichenketten definieren will, verbieten man Zyklen, d.h. die transitive Hülle ist eine partielle Relation. Analoges gilt für die Verwendung von “Include“, das es erlaubt, andere Text-files an eine bestimmte Stellen (logisch) zu kopieren, unter gemeinsamer Verwendung derselben Textdatei.

Satz 35. Sei R ⊆ M × M eine Relation in M. R^{r} ist der Durchschnitt aller reflexiven Relationen in M, die R enthalten. R^{+} ist der Durchschnitt aller transitiven Relationen in M, die R enthalten.

R^{r} := ⋂{S | R ⊆ S, S ⊆ M × M, S reflexiv}

R^{+} := ⋂{S | R ⊆ S, S ⊆ M × M, S transitiv}

Ordnungen können durch Hasse-Diagramme veranschaulicht werden.

• Jedem Element entspricht ein Knoten,

• Wenn a < b, dann ist a in der Zeichnung weiter unten,

• Zwei Knoten a, b werden durch eine Kante verbunden, wenn kein Element dazwischen liegt.

Beispiel 10. M = {1, 2, 3, 5, 6, 10, 15, 30}, R = {(x, y) | x, y ∈ M und x teilt y}.

Definition 36. Sei (M, R) eine reflexive Ordnung und sei N ⊆ M.

1. Ein Element a ∈ N heißt größtes Element von N, wenn es größer als alle anderen Elemente von N ist : (∀x ∈ N : xRa). Ein größtes Element von M heißt Einselement.

2. Ein Element a ∈ N heißt kleinstes Element von N, wenn es kleiner als alle anderen Elemente ist : (∀x ∈ N : aRx). Ein kleinstes Element von M heißt Nullelement.

3. Ein Element a heißt maximal, wenn es kein größeres Element gibt .

4. Ein Element a heißt minimal, wenn es kein kleineres Element gibt .

5. Die Menge der oberen Schranken (upper bounds) von N ist: UB(N) := {x ∈ M | ∀y ∈ N : yRx}.

6. Die Menge der unteren Schranken (lower bounds) von N ist: LB(N) := {x ∈ M | ∀y ∈ N : xRy}.

7. Die Menge der kleinsten Elemente in UB(N) wird mit LUB(N) bezeichnet (least upper bounds).

8. Die Menge der größten Elemente in LB(N) wird mit GLB(N) bezeichnet (greatest lower bounds).

9. Wenn GLB(N) und LUB(N) für alle endlichen Teilmengen von N existieren und genau ein Element enthalten, so ist M ein Verband. Wenn GLB(N) (bzw. LUB(N)) immer existiert und einelementig ist, aber LUB(N) (bzw. GLB(N)) nicht immer, so spricht man auch von unteren (bzw. oberen) Halbverband.

Beispiel 11. Betrachte die Ordnung in Beispiel 10.

• 30 ist größtes Element (und Einselement)

• 1 ist kleinstes Element (und Nullelement)

• 6, 10 und 15 sind maximale Elemente von M \ {30}.

• 2, 3 und 5 sind minimale Elemente von M \ {1}.

• UB({1, 2, 3, 5}) = {30}.

• GLB(M \ {1}) = {1}:

• M ist ein Verband

• M \ {1} ist ein oberer Halbverband.

Im folgenden Diagramm gibt es kein größtes Element, aber zwei maximale, kein kleinstes Element, aber zwei minimale Elemente. Diese Ordnung ist kein Verband.

Definition 37. Sei (M, R) eine Äquivalenzrelation. Ist x ∈ M, so heißt die Menge [x]_{R} := {y | xRy} die Äquivalenzklasse von x. x heißt Repräsentant von [x]_{R}.

Satz 38. Sei R ⊆ M × M eine Äquivalenzrelation.

1. Zwei Äquivalenzklassen sind entweder disjunkt oder identisch.

2. Jedes x ∈ M gehört genau zu einer Äquivalenzklasse.

Beweis. Sei [x]_{R} ∩ [y]_{R} ≠ ∅. zu zeigen: [x]_{R} = [y]_{R} . Sei a ∈ [x]_{R} und b ∈ [x]_{R} ∩ [y]_{R} . Dann gilt xRa, xRb und yRb. Aus Symmetrie und Transitivität folgt yRa also a ∈ [y]_{R} . Die Behauptung ist symmetrisch, also gilt [x]_{R} = [y]_{R}. ⊓ ⊔

Ist R eine Äquivalenzrelation auf M, so lassen sich die Äquivalenzklassen als Elemente einer neuen Menge M/R (der Faktormenge, Quotient) auffassen. d.h. M/R = {[x]_{R} | x ∈ M}. Die Kardinalität von M/R heißt der Rang von R (rk(R)).

Beispiel 12.

1. Ist R eine Präordnung auf M (Z.B. Aufrufhierarchie von Modulen), so sei ≡ definiert als x ≡ y :⇔ (xRy ∧ yRx), eine Äquivalenzrelation. Die vererbte Ordnung R/≡ auf M/≡ ist eine reflexive Ordnung. Dabei ist R/≡ definiert als [x]_{R} R/≡ [y]_{R} genau dann wenn xRy.

2. Sei M die Menge der Aussagen und R = {(A, B) | A ⇒ B ist Tautologie}. Dann ist R reflexive Präordnung. Für die Relation ≡ gilt: A ≡ B, genau dann wenn A zu B äquivalent ist.

3. Betrachte die Bruchdarstellung für rationale Zahlen, d.h. die Menge {(a, b) | a ∈ ZZ, b ∈ IN}. Auf dieser Menge ist eine Äqivalenzrelation ≡ definiert durch (a, b) ≡ (c, d) :⇔ a ∗ d = b ∗ c. Dann sind die Äquivalenzklassen gerade die rationalen Zahlen Q. Die Multiplikation ist dann definiert als [(a, b)]_{≡} ∗ [(c, d)]_{≡} := [(a∗c, b∗d)]_{≡} , Die Addition ist definiert als [(a, b)]_{≡} + [(c, d)]_{≡} := [(a ∗ d + b ∗ c, b ∗ d)]_{≡} . Ein Paar (a, b) ist ein Repräsentant der Äquivalenzklasse [(a, b)]_{≡} . Man kann hier sogar einen kanonischen Repräsentanten (a, b) (eine sogenannte Normalform) wählen, wobei a und b teilerfremd sind. Dieser kanonische Repräsentant kann dann dazu dienen, die Gleichheit von Äquivalenzklassen zu testen

4. Definiere auf ZZ für eine gegebene ganze Zahl p die Relation R_{p} := {(m, n) | m und n haben bei Division durch p den gleichen Rest}. Für (m, n) ∈ R_{p} schreibt man üblicherweise m ≡ n(mod p). Offensichtlich gilt auch: m ≡ n(mod p) ⇔ p ist Teiler von (m − n). Diese Relation ist eine Äquivalenzrelation. Die Äquivalenzklassen [x]_{p} heißen auch Restklassen modulo p in ZZ. z.B. [0]_{p} = {0, p, −p, 2p, −2p, 3p, …}

Zweistelligen Relationen kann man vielseitig verwenden: z.B. Vereinfachung von Aussageformen, Vereinfachung von Polynomausdrücken zur Summe von Produkten, Berechnung als Zustandsübergang. In diesem Zusammenhang sind folgende Eigenschaften von Relationen wichtig:

Definition 39. R sei eine (zweistellige) Relation auf einer Menge M.

1. Eine Relation R heißt terminierend, wenn es keine unendliche Kette a_{1} R a_{2} R a_{3} R a_{4} … gibt.

2. Wir sagen eine irreflexive Ordnung R ist fundiert (Noethersch), wenn R^{−1} terminierend ist, d.h. es gibt keine unendlich absteigenden Ketten.

3. Ein Element a heißt irreduzibel, wenn es kein gibt mit aRb .

4. Eine Relation heißt konfluent, wenn es zu Elementen b und c mit aR^{∗}b und aR^{∗}c stets ein Element d gibt, so daß bR^{∗}d und cR^{∗}d gilt.

Satz 40. Sei R eine konfluente und terminierende Relation. Dann gilt:

1. Für jedes a gibt es ein eindeutig bestimmtes irreduzibles b, so daß aR^{∗}b.

2. Jede Kette a R a_{1} R a_{2} … endet mit diesem Element b.

Beweis. Zunächst mal existiert zu jedem a ein irreduzibles b, so daß aR^{∗}b, denn anderenfalls gäbe es eine nichtterminierende Kette. Weiterhin muß auch jede Kette a R a_{1} R a_{2} … mit einem irreduziblen Element enden, denn alle solchen Ketten sind endlich. Wir nehmen an, es gibt zwei verschiedene irreduzible Elemente b und c mit aR^{∗}b und aR^{∗}c. Da R konfluent ist, gibt es ein Element d, so daß bR^{∗}d und cR^{∗}d. Da sowohl c als auch d irreduzibel ist, und c ≠ d, folgt ein Widerspruch. ⊓ ⊔

Unter den Voraussetzungen des obigen Satzes sagt man, daß b die Normalform von a ist.

Beispiel 13. Betrachte wieder die Bruchdarstellung für rationale Zahlen mittels der Menge {(a, b) | a ∈ ZZ, b ∈ IN}. Um die Normalformen zu berechnen, definiere eine Relation → auf den Paaren: (a, b) → (c, d), wenn eine Zahl q ∈ IN mit q > 1 existiert mit q∗c = a und q∗d = b. Offenbar ist diese Relation terminierend und auch transitiv. Diese ist auch konfluent, denn sei (a_{1}, a_{2}) → (b_{1}, b_{2}) mit q und (a_{1}, a_{2}) → (c_{1}, c_{2}) mit p. Dann definiere d_{1} = a_{1}/(p ∗ q) und d_{2} = a_{2}/(pq). Offenbar gilt (b_{1}, b_{2}) → (d_{1}, d_{2}) mit p und (c_{1}, c_{2}) → (d_{1}, d_{2}) mit q. Es gilt (a_{1}, a_{2}) → (d_{1}, d_{2}). Das bedeutet, daß diese Berechnungsmethode auf eine (eindeutige) Normalform führt.

Bemerkung: Bei einer terminierenden Relation muß nicht notwendigerweise auch die inverse Relation terminierend sein. Ein Gegenbeispiel ist die lexikographische Ordnung (siehe 41). Fundierte Ordnungen sind oftmals hilfreich bei Terminierungsbeweisen von Algorithmen.

Beispiel 14.

1. Ausmultiplizieren von arithmetischen Ausdrücken ist konfluent und terminierend.

2. Ausmultiplizieren ist eine Relation auf den Darstellungen von Polynomen, die konfluent und terminierend ist.

3. in Kapitel 6 ist Reduktion von λ-Termen eine konfluente Relation.

Definition 41. Hat man Mengen A_{1}, …, A_{n} gegeben, wobei auf den jeweiligen Mengen eine Ordnung <_{i} definiert ist, so lassen sich diese Ordnungen auf verschiedene Weisen auf kartesische Produkte fortsetzen.

1. punktweise: (a_{1}, …, a_{n}) <_{pkt} (b_{1}, …, b_{n}) :⇔ a_{1} <_{1} b_{1}, …, a_{n} <_{n} b_{n},

2. lexikographisch: (a_{1}, …, a_{n}) <_{lex} (b_{1}, …, b_{n}) :⇔ ∃i ≤ n : a_{i} <_{i} b_{i} ∧ ∀j < i : a_{j} = b_{j}.

Satz 42.

1. Sind alle Ordnungen (A_{i}, <_{i}), i = 1, …, n fundiert, so ist die lexikographische Ordnung auf dem kartesischen Produkt ebenfalls fundiert.

2. Sind alle Ordnungen (A_{i}, <_{i}), i = 1, …, n linear, so ist die lexikographische Ordnung auf dem kartesischen Produkt ebenfalls linear.

Beweis. (Übungsaufgabe mit Induktion): Man betrachte eine unendlich absteigende Kette und zeige, daß es dann auch eine unendlich absteigende Kette in einem A_{i} geben müßte. ⊓ ⊔

Die lexikographische Ordnung ist die Sortierordnung z.B. bei Lexika, wo die Ordnung auf einem Einzelzeichen die alphabetische Reihenfolge ist und die Ordnung auf den Wörtern die lexikographische. Hier kommt es nur darauf an, daß die Ordnung linear ist, d.h., daß sich alle Worte vergleichen lassen. Die Sortierreihenfolge bei Dateien, bei einem Index o.ä. wird noch durch die Erweiterung der Ordnung auf die Ziffern und Sonderzeichen bestimmt.

Beispiel 15. Anwendung bei Terminierungsbeweisen. Betrachte den Blasen-Sort (Bubblesort), der ein n-Tupel aus natürlichen Zahlen solange mittels Vertauschung transformiert, bis die Elemente aufsteigend sortiert sind. Die einzige Transformationsregel ist:

Gilt für zwei Indizes i ≠ j mit i < j, daß a_{i} > a_{j}, so vertausche a_{i} und a_{j}.

Sei also (a_{1}, … a_{i}, … a_{j}, …, a_{n}) überführt in (a_{1}, … a_{j} … a_{i}, …, a_{n}). Um zu zeigen, daß der Blasensort terminiert, kann man so vorgehen:

1. < ist fundierte Ordnung auf IN_{0},

2. also ist auch die lexikographische Ordnung <_{lex,n} auf IN_{0}^{n} fundiert.

3. weiterhin gilt: Wenn man (a_{1}, … a_{j} … a_{i}, …, a_{n}) durch Anwenden der Regel aus (a_{1}, … a_{i}, …, a_{j}, …, a_{n}) erhält, so ist a_{j} < a_{i}, also auch (a_{1}, … a_{j} … a_{i}, …, a_{n}) <_{lex,n} (a_{1}, … a_{i}, … a_{j}, …, a_{n}).

Also kann man die Operationsregel nicht unendlich oft anwenden.

5 Das Prinzip der vollständigen Induktion.

Induktionsbeweise treten auf beim Beweis von Eigenschaften über der Menge IN_{0}. Dies wird im ersten Teil des Paragraphen kurz dargestellt. Das Induktionsprinzip für induktiv definierte Mengen, das wir noch öfters brauchen werden, behandeln wir im Anschluß daran.

Sei E eine Eigenschaft der natürliche Zahlen IN_{0}. Prinzip der einfachen Induktion:

(E(m) ∧ (∀n ≥ m : E(n) ⇒ E(n + 1))) ⇒ (∀n ≥ m : E(n))

Prinzip der vollständigen Induktion:

(E(m) ∧ (∀n ≥ m : (∀k : m ≤ k ≤ n ⇒ E(k)) ⇒ E(n + 1))) ⇒ (∀n ≥ m : E(n))

Beispiel 16. 1. einfache Induktion:

E(n) :⇔ ∑_{i=1}^{n} = \frac{1}{2}n(n + 1). Beweis mit dem Prinzip der einfachen Induktion:

Induktionsanfang: ∑_{i=1}^{1} 1 = 1 = \frac{1}{2}1(1 + 1).

Induktionsvoraussetzung: ∑_{i=1}^{n} i = \frac{1}{2}n(n + 1).

Induktionsschluß: ∑_{i=1}^{n+1} i = ∑_{i=1}^{n} i + n + 1 = \frac{1}{2}n(n + 1) + (n + 1) = \frac{1}{2}(n + 1)(n + 2) d.h.

E(n + 1) gilt. Also gilt: ∀n.n ≥ 1 ⇒ E(n)

2. vollständigen Induktion:

Seien die Fibonaccizahlen gegeben durch F ib(0) := 0, F ib(1) := 1 und F ib(n + 1) = F ib(n) + F ib(n − 1) für n > 1. Behauptung: E(n) := F ib(n) ≤ 2^{n−1}

Induktionsanfang: E(0), E(1) gilt, denn 0 ≤ 2^{−1}, 1 ≤ 2^{0} Induktionsvoraussetzung: Für alle 0 ≤ k ≤ n gilt: E(k), d.h. F ib(k) ≤ 2^{k−1}. Induktionsschluß: für n ≥ 1 gilt: F ib(n + 1) = F ib(n) + F ib(n − 1) ≤ 2^{n−1} + 2^{n−2} = 3 ∗ 2^{n−2} < 2^{n} = 2^{(n+1)−1}. Also gilt ∀n ≥ 0 : E(n).

Mengen lassen sich oft induktiv (rekursiv) definieren, was sehr oft einfacher ist, als die Menge direkt anzugeben. D.h. man gibt ein Konstruktionsverfahren an, das es ermöglicht, alle Elemente der Menge zu konstruieren. Um Eigenschaften dieser so konstruierten Menge zu beweisen, bedient man sich der Induktion, entweder über die Anzahl der notwendigen Konstruktionsschritte, oder im Fall, daß man den Elementen ihre Konstruktion ansieht, der sogenannten Induktion über die Struktur der erzeugten Elemente.

Beispiel 17. Menge der Aussageformen:

1. alle Atome sind Aussageformen (Verankerung)

2. Wenn A, B Aussageformen, dann sind (¬A), (A ∨ B) und (A ∧ B) auch Aussageformen.

Wir erklären die Höhe h(A) folgendermaßen:

1. h(A) := 0 wenn A ein Atom ist,

2. h(¬A) := 1 + h(A)

3. h(A ∨ B) := 1 + max{h(A), h(B)}

4. h(A ∧ B) := 1 + max{h(A), h(B)}

Wir erklären die Anzahl der Blätter b(A) folgendermaßen:

1. b(A) := 1 wenn A ein Atom ist,

2. b(¬A) := b(A)

3. b(A ∨ B) := b(A) + b(B)

4. b(A ∧ B) := b(A) + b(B)

Durch Induktion über die Konstruktion der Menge (oder die Struktur der Aussageformen) zeigen wir: b(A) ≤ 2^{h(A)}.

1. Induktionsanfang: Wenn A ein Atom ist, dann b(A) = 1 ≤ 1 = 2^{0}.

2. Induktionsschritt: Wir müssen alle Fälle durchgehen.

(a) b(¬A) = b(A) ≤ 2^{h(A)} < 2^{h(A)+1} = 2^{h(¬A)}

(b) b(A ∨ B) = b(A) + b(B) ≤ 2^{h(A)} + 2^{h(B)} ≤ 2 ∗ 2^{max{h(a),h(B)}} = 2^{h(A∨B)}

(c) Für b(A ∧ B) zeigt man das analog zu 2b.

Damit ist die Behauptung gezeigt.

6 Der λ-Kalkül

Der λ-Kalkül wurde von Alonzo Church eingeführt, um Funktionen notieren zu können und um mit Funktionen rechnen zu können. Zum Beispiel würde man die Quadrat-Funktion, die mit quadrat(x) := x ∗ x definiert ist, als quadrat := λx.x ∗ x definieren. Die λ-Notation wird auch sehr häufig als informelle Notation für Funktionen benutzt. Diese Schreibweise wird in funktionalen Sprachen benutzt, insbesondere in LISP und dem LISP-Dialekt Scheme. Im λ-Kalkül sind alle Objekte einstellige Funktionen, wobei diese Objekte durch Ausdrücke dargestellt werden. Diese Ausdrücke nennt man auch λ-Terme. Ein Term der Form (λx.t) ist eine Funktion mit x als Argumentvariablen. Einen solchen Term bezeichnet man auch als Abstraktion. Eine Anwendung einer Funktion f auf eine Objekt (das auch eine Funktion ist) schreibt man einfach (f g). Formal ist die Syntax^{1} gegeben durch: ⟨Term⟩ ::= ⟨Variable⟩|⟨Konstante⟩|(⟨Term⟩⟨Term⟩)|λx.⟨Term⟩

D.h. : λ-Terme sind Variablen, Konstante, Anwendungen, oder Abstraktionen.

1 Die Metazeichen haben folgende Bedeutung: ::= bedeuten “definiert als“, ⟨…⟩ ist ein definierter Name, |

bedeutet Alternative. Siehe auch Kapitel 12

Beispiel 18. Beispiele für λ-Terme sind:

1. λx.x Das ist die ist die Identitätsfunktion I d.h. I x = x.

2. λx.(λy.(xy)) Das ist der Anwendungskombinator.

3. λx.(λy.x) (bekannt als K-Kombinator mit (Kx)y = x)

4. λx.λy.λz(xz)(yz) (bekannt als S-Kombinator mit ((Sx)y)z = (xz)(yz))

5. λx.(xx)

Definition 43. Die Menge der freien Variablen F V (t) von t ist definiert als:

1. {x}, wenn t die Variable x ist,

2. ∅, wenn t eine Konstante ist.

3. F V (r) ∪ F V (s), wenn t = (r s)

4. F V (s) \ {x}, wenn t der Term (λx.s) ist

Eine Variable x ist in F V (t), wenn sie ein freies Vorkommen in t hat. Nicht jedes Vorkommen von x muß frei sein.

Definition 44. Die Menge der gebundenen Variablen GV (t) von t ist definiert als: 1. ∅, wenn t die Variable x ist,

2. ∅, wenn t eine Konstante ist.

3. GV (r) ∪ GV (s), wenn t = (r s).

4. GV (s) ∪ {x}, wenn t der Term (λx.s) ist und x ∈ F V (s).

Einen Term ohne freie Variablen nennt man auch geschlossen. Im λ-Kalkül ist es möglich, als Erweiterung der Syntax zuzulassen, daß man geschlossenen Terme neue Namen (als Abkürzungen) gibt. Diese Namen werden dann wie Konstanten behandelt. Um λ-Terme evaluieren zu können, brauchen wir das Konzept der Ersetzung oder Substitution. Wenn t ein λ-Term ist mit der freien Variablen x, so soll t[x → s] der λ-Term sein, der durch Ersetzen von x durch s entsteht.

Definition 45. (Substitution) Formal können wir den Prozess der Substitution rekursiv definieren:

1. t[x → s] := s wenn t die Variable x ist.

2. t[x → s] := t wenn t eine Konstante ist.

3. (r t)[x → s] := (r[x → s] t[x → s]) für eine Anwendung (r t).

4. (λy.t)[x → s] := λy.(t[x → s]) falls x und y verschieden sind, und (y ∉ F V (s) oder x ∉ F V (t)).

5. (λy.t)[x → s] := λz.(t[y → z][x → s]) falls x und y verschieden sind, y ∈ F V (s) und x ∈ F V (t), wobei z eine freie Variable ist, die nicht in s oder t vorkommt.

6. (λx.t)[x → s] := λx.t.

Die Unterscheidung der Fälle einer Abstraktion in 45.4 und 45.5 ist so, daß der erste Fall der unproblematische ist, in dem keine Konflikte auftreten können. Würde man im Fall daß gleichzeitig y ∈ F V (s) und x ∈ F V (t) gelten, ohne Umbenennung ersetzen, so würde die Variable y in s, die vorher frei war, sozusagen eingefangen, da sie in den Bindungsbereich von λy. gerät. Um diesen Konflikt der eher zufälligen Wahl der Namen der gebundenen Variablen zu umgehen, wird vorher die Funktionsvariable umbenannt. Im Fall 6.) ist die Variable x in t gebunden, und hat nichts mit dem Wert der freien Variablen x aus [x → s] zu tun.

Diese Problemfälle und die Überlegungen dazu gelten nicht nur im scheinbar theoretischen Fall des λ-Kalküls, sondern auch im Prädikatenkalkül und in vielen Programmiersprachen. Die Methode, die hier verwendet wird, nennt sich in Programmiersprachen statische Bindung (static binding, lexical scoping), d.h. die zugeordnete freie Variable wird aus dem textuellen Kontext im Programm entnommen. Diese wird auch in Haskell (Gofer) und Scheme benutzt. Dynamische Bindung, wie sie in manchen LISP-Dialekten verwendet wird, erlaubt das Einfangen von freien Variablen, was immer wieder zu verwirrenden Effekten führen kann.

Die wichtigste Operation im λ-Kalkül ist die sogenannte β-Reduktion, die nichts anderes ist als die formale Einsetzung von Argumenten in die Definition einer Funktion. Der Name β-Reduktion hat historische Gründe.

Definition 46. β-Reduktion Sei (λx.t) und s λ-Terme. Dann ist die β-Reduktion die folgende Ersetzung.

(λx.t)s → t[x → s].

Wenn in einem λ-Term ein Unterterm entsprechend ersetzt wird, dann sprechen wir ebenfalls von β-Reduktion.

Eine weitere wichtige Äquivalenz, die wir schon benutzt haben, ist die Umbenennung von gebundenen Variablen.

Definition 47. α-Konversion Sei (λx.s ein λ-Term. Dann ist die α-Reduktion die folgende Ersetzung.

λx.s → λz.s[x → z]

Wenn in einem λ-Term ein Unterterm entsprechend ersetzt wird, dann sprechen wir ebenfalls von α-Konversion.

Bei beiden Reduktionen ist zu beachten, daß die Regeln für die Ersetzung einzuhalten sind. D.h. in λz.s[x → z] darf z weder frei noch gebunden in s vorkommen.

Beispiel 19. Die Funktion λx.y ist eine konstante Funktion, die jedes Argument auf y abbildet: (λx.y)s = y[x → s] = y. Diese Funktion sollte sich nicht wesentlich ändern, wenn man y durch eine andere Variable ersetzt: z.B. Ersetzung von y durch z sollte die Funktion ergeben, die alles konstant auf z abbildet. Genauso sollte die Ersetzung von y durch x eine Funktion ergeben, die alles konstant auf x abbildet. Aber, hätte man die Ersetzung (λx.y)[y → x] in einer zu naiven Art und Weise definiert, so wäre das Ergebnis: (λx.x), was die Identitätsfunktion darstellt. Richtiges Ergebnis von (λx.y)[y → x] ist λz.x mit z ≠ x.

Übungsaufgabe 48. Die Relation s ≡_{α} t sei der transitive Abschluß der α-Konversion, d.h. t kann man aus s durch eine Folge von α-Konversionen herstellen. Zeige, daß ≡_{α} eine Äquivalenzrelation ist.

Definition 49. β-Reduktion. Ein Term s reduziert auf einen Term t, (Notation s ⟹_{βα} t) wenn t aus s durch eine Folge von β-Reduktionen und α-Konversionen (auch von inneren λ-Termen) erreicht wird. Wenn die Reduktion nur mit β-Reduktionen erreicht wurde, dann schreiben wir s ⟹_{β} t).

Mit anderen Worten, ⟹_{βα} ist die reflexive-transitive Hülle der von der β-Reduktion und der α-Konversionen erzeugten Relationen. Die Relation ⟹_{β} ist die reflexive-transitive Hülle der von der β-Reduktion erzeugten Relation.

Ein Redex von r ist ein Unterterm der Form ((λx.s)t). Ein Term ist in Normalform, wenn er keine Redexe mehr enthält. Wenn s ⟹_{βα} t und t ist in Normalform, so sagt man t ist Normalform von s.

Beispiel 20.

1. (λx.x y)F ⟹ F y

2. (λx.x)(λx.x) ⟹ (λx.x)

3. (λx.x x)(λx.x x) ⟹ (λx.x x)(λx.x x) ⟹ …

Die intuitive Bedeutung ist, daß die Berechnung im λ-Kalkül durch die Anwendung der β-Reduktion erfolgt, und daß die Normalform das Ergebnis einer Berechnung ist. Das Beispiel 3 zeigt, daß die Reduktionsrelation nicht terminierend ist. Es gilt aber der wichtige Satz:

Satz Church-Rosser Theorem .

1. Die Relation ⟹_{βα} ist konfluent.

2. Die Relation ⟹_{β} ist konfluent modulo ≡_{α}.

Der Beweis kann von Interessierten in entsprechenden Lehrbüchern nachgelesen werden.

Korollar 50. Wenn s zwei Normalformen t_{1} und t_{2} hat, so sind t_{1} und t_{2} gleich bis auf Umbenennung von gebundenen Variablen.

Beweis. Aus dem Satz von Church-Rosser folgt, daß t_{1} und t_{2} aufeinander reduziert werden können. Da beide keine Redexe mehr enthalten und α-Konversion keine Redexe einführen kann, sind t_{1} und t_{2} gleich bis auf Umbenennung von gebundenen Variablen.

Es gibt Terme, die keine Normalform besitzen. Diese entsprechen nichtterminierenden Berechnungen.

Definition 51. Es gibt verschiedene Auswertungsstrategien für λ–Terme.

1. Man spricht von normaler Reihenfolge der Reduktion (normal order reduction) , wenn β-Reduktion stets für den obersten und am meisten links (in der Termdarstellung) stehenden Redex angewendet wird.

2. Man spricht von applikativer Reihenfolge der Reduktion (applicative order reduction) , wenn (λx.t)s = t[x → s] nur ausgeführt wird, wenn s in Normalform ist. Weiterhin muß die Auswertungsprozedur auch weiter links stehende Redexe vor weiter rechts stehenden reduzieren.

Beispiel 21. Betrachte den λ-Term (λx.a)((λx.(x x))(λx.(x x))). Wertet man diesen Term in applikativer Reihenfolge aus, so muß zunächst ((λx.(x x))(λx.(x x))) auf Normalform gebracht werden. Dieser Prozess terminiert nicht, so daß applikative Reihenfolge keine Normalform erzeugt. Versucht man es mit normaler Reihenfolge, so erhält man sofort als Normalform die Konstante a.

Satz 52. Wenn ein Term s eine Normalform t hat, so berechnet Reduktion in normaler Reihenfolge diese Normalform in endlich vielen Schritten.

Beweis. (siehe z.B. Barendregt: Functional Programming and λ-Calculus.) ⊓ ⊔

In dieser Hinsicht ist die normale Reihenfolge der applikativen Reihenfolge überlegen. Unter Implementierungsgesichtspunkten hat normale Reihenfolge, wenn sie naiv implementiert wird, Nachteile, denn der Ersetzungsprozess kann den λ-Term sehr stark vergrößeren und auch mehrfache Ausführung der gleichen Reduktion erfordern. Zum Beispiel: (λx.(f x x))s ergibt in normaler Reihenfolge den Term (f s s). Im Falle, daß s nicht in Normalform ist, muß dann die Reduktion von s zweimal gemacht werden, um zur Normalform zu gelangen. Bei applikativer Reihenfolge dagegen wird s zur Normalform s′ reduziert, und dann erst die Reduktion zu (f s′ s′) durchgeführt. In den meisten Implementierungen der normalen Reihenfolge wird eine sogenannte Graphreduktion durchgeführt, wobei durch geschickte Darstellung erreicht wird, daß dieser Effekt der Verdopplung von Reduktionen nicht auftritt. Die Anzahl der Reduktionsschritte bis zur Normalform ist dann bei normaler Reihenfolge kleiner (oder gleich) der Anzahl der Reduktionen bei applikativer Reihenfolge. Die Implementierungen der applikativen Ordnung führen mit relativ wenig Aufwand zu effizienter Reduktion, denn die Optimierungsmöglichkeiten auf tieferer Ebene sind leichter zu implementieren. Die Sprachen mit normaler Reihenfolge haben aber dafür eine höheren Abstraktionsgrad. Es gibt eine Anzahl von funktionalen Programmiersprachen wie LISP, Scheme, ML (MetaLanguage), Miranda, Haskell, Gofer, die alle auf dem λ–Kalkül basieren. Einige verwenden ausschließlich applikative Reihenfolge (eager evaluation), andere normale Reihenfolge (verzögerte Auswertung, lazy evaluation), und einige erlauben eine Mischung, wie Scheme. Alle diese Sprachen verwenden allerdings nicht den reinen λ-Kalkül, sondern stellen Basisdatentypen und zugehörige Funktionen zur Verfügung, wie z.B. Integer, String usw. Außerdem erlauben diese Sprachen mehrstellige Funktionen. Dies stellt keine echte Erweiterung dar, denn eine zweistellige Funktion λ(x, y).F (x, y) läßt sich folgendermaßen darstellen : λx.(λy.F (x, y)). Diese Übersetzung ist auch unter dem Namen Currying (nach H.B.Curry) bekannt.

Man kann mit Hilfe der λ-Terme und der β-Reduktion einen Berechenbarkeitsbegriff definieren (siehe Aufgabe und Abschnitt über Turingmaschinen), allerdings ist das technisch zu aufwendig, so daß wir hier nicht darauf eingehen.

Übungsaufgabe 53.

1. Zeige, daß der Operator Y := λf.((λx.f(x x))(λx.f(x x))) ein sogenannter Fixpunktoperator ist. d.h., für jeden λ-Term F gilt: (Y F) ≡_{α} F (Y F)

2. Schreibe informelle λ-Notation hin für

(a) Die Ableitung von x^{2} ist 2x

(b) Die Produktregel der Differentialrechnung

3. Wir benutzen die Kombinatoren I, S, K des Beispiels 18.

(a) Reduziere ((S K)K)X

(b) Reduziere ((S S)S)S)

4. (Church-Zahlen)

Definiere B := (S(K S))K und Z_{n} := (S B)^{n}(K I), wobei X^{m} dasselbe wie (… (\underbrace{X X)X) … X})_{m} bedeuten soll. Zeige: (Z_{n} F)X ≡_{α} F^{n}X

7 Halbgruppen, Monoide, Homomorphismen

Sei M eine Menge. Eine totale Funktion ∘ : M × M → M heißt Verknüpfung. Statt ∘(a, b) schreibt man auch a ∘ b.

Definition 54. Sei ∘ eine Verknüpfung in der Menge M. ∘ heißt 1. kommutativ (abelsch), falls ∀a, b ∈ M : a ∘ b = b ∘ a.

2. assoziativ, falls ∀a, b, c ∈ M : (a ∘ b) ∘ c = a ∘ (b ∘ c)

Definition 55. Eine Menge mit assoziativer Verknüpfung heißt Halbgruppe.

Schreibweise: (M, ∘)

Beispiel 22. Beispiel für Halbgruppen sind: (IN, +), (IN_{0}, +), (ABB(M, M), ∘). Ein wichtige Halbgruppe werden wir noch kennenlernen, die Halbgruppe der Worte.

Definition 56. Sei (M, ∘) eine Halbgruppe.

1. ein Element x heißt idempotent, falls x ∘ x = x.

2. Ein Element 0_{M} heißt Nullelement, falls ∀m ∈ M : 0_{M} ∘ m = m ∘ 0_{M} = 0_{M}.

3. Ein Element 1_{M} heißt Einselement, falls ∀m ∈ M : 1_{M} ∘ m = m ∘ 1_{M} = m.

4. (M, ∘) heißt linkskürzbar (bzw. rechtskürzbar), falls ∀a, b, c ∈ M : a ∘ b = a ∘ c ⇒ b = c (bzw. ∀a, b, c inM : b ∘ a = c ∘ a ⇒ b = c.

Beispiel 23.

1. In (IN, +) existiert kein Einselement und kein Nullelement.

2. Null- und Einselemente sind idempotente Elemente.

3. In (IN_{0}, +) ist 0 Einselement, es gibt kein Nullelement.

4. In (IN_{0}, ∗) ist 0 Nullelement, und 1 ist ein Einselement.

5. In (ABB(M, M), ∘) ist die Identität (I mit Ix = x für alle x) ein Einselement, die überall undefinierte Funktion ist Nullelement.

Definition 57. Eine Unterhalbgruppe (N, ∘) einer Halbgruppe (M, ∘) ist eine nichtleere Teilmenge N von M, die Halbgruppe bzgl. ∘ ist. Schreibweise: (N, ∘) ⊑ (M, ∘)

Definition 58. Eine Halbgruppe (M, ∘) mit Einselement 1_{M} nennt man Monoid. Schreibweise: (M, ∘, 1_{M})

Satz 59. In einem Monoid existiert genau ein Einselement.

Aber: das Einselement einer Unterhalbgruppe eines Monoids muß nicht das Einselement des Monoids sein: Beispiel: Das Monoid ({0}, ∗, 0) ist Unterhalbgruppe von (IN_{0}, ∗, 1), aber 0 ≠ 1.

Definition 60. Sei (M, ∘, 1_{M}) ein Monoid und 1_{M} ∈ N ⊆ M, so daß (N, ∘, 1_{M}) eine Unterhalbgruppe von (M, ∘, 1_{M}) ist. Dann heißt (N, ∘, 1_{M}) Untermonoid von (M, ∘, 1_{M}).

Satz 61. Der Schnitt von Unterhalbgruppen einer Halbgruppe M ist wieder eine Unterhalbgruppe.

Beachte, daß die Vereinigung von Unterhalbgruppen i.a. keine Unterhalbgruppe sein muß, da diese Menge möglicherweise nicht gegen Verknüpfung abgeschlossen ist.

Definition 62. Sei (M, ∘) eine Halbgruppe und seien U, V ⊆ M. Dann ist (U ⊔V, ∘) definiert als ⋂{W | (W, ∘) ⊑ (M, ∘) und U ⊆ W, V ⊆ W }.

(U ⊔ V, ∘) heißt die von U und V erzeugte Unterhalbgruppe.

Eine direktere Beschreibungsmöglichkeit für (U ⊔ V, ∘) ist: U ⊔ V besteht aus allen endlichen Verknüpfungen von Elementen aus U und V. Für U ⊔ U schreiben wir auch ⟨U⟩ und sagen ⟨U⟩ ist die von U erzeugt Unterhalbgruppe.

Definition 63. Sei (M, ∘) eine Halbgruppe und sei E ⊆ M. E ist ein Erzeugendensystem von M, falls ⟨E⟩ = M.

Bemerkung: Ist ⟨E⟩ = M, so kann man jedes m ∈ M als Produkt von Elementen aus E darstellen, allerdings möglicherweise nicht eindeutig.

Beispiel 24. {1} ist Erzeugendensystem von (IN, +). {1, 2} ist Erzeugendensystem von (IN, +), aber Darstellung ist nicht eindeutig, da 1 + 2 = 1 + 1 + 1.

Definition 64. Seien (M_{1}, ∘_{1}) und (M_{2}, ∘_{2}) Halbgruppen. Eine Abbildung φ : M_{1} → M_{2} heißt (Halbgruppen-) Homomorphismus, falls ∀a, b ∈ M_{1} : φ(a ∘_{1} b) = φ(a) ∘_{2} φ(b). φ heißt

• Monomorphismus, falls φ injektiv.

• Epimorphismus, falls φ surjektiv.

• Isomorphismus, falls φ bijektiv.

• Endomorphismus, falls (M_{1}, ∘_{1}) = (M_{2}, ∘_{2}) .

• Automorphismus, falls (M_{1}, ∘_{1}) = (M_{2}, ∘_{2}) und φ bijektiv.

Schreibweise: φ : (M_{1}, ∘_{1}) → (M_{2}, ∘_{2})

Beispiel 25. : Sei IR^{+} := {x ∈ IR | x > 0}. Betrachte (IR^{+}, ∗) und (IR^{+}, +) Die Abbildung φ : (IR^{+}, ∗) → (IR, +) mit φ(x) := ln x ist ein Homomorphismus: φ(x ∗ y) = ln(x ∗ y) = ln(x) + ln(y). φ ist sogar bijektiv, also ist φ ein Isomorphismus.

Definition 65. Seien (M_{1}, ∘_{1}, 1_{1}) und (M_{2}, ∘_{2}, 1_{2}) Monoide. Eine Halbgruppenhomomorphismus φ : M_{1} → M_{2} heißt (Monoid-) Homomorphismus, falls φ(1_{1}) = 1_{2}.

Man sieht, daß die Begriffe sich immer auf eine Klasse von Strukturen beziehen, die eine gemeinsame Menge von Eigenschaften (Axiomen) haben. Dieselbe Abbildung auf einer Menge kann je nachdem ob man sie als Menge, als Halbgruppen, als Monoid, oder als Gruppe betrachtet, verschiedene Eigenschaften im Sinne der Homomorphismen haben. Die Kategorientheorie beschäftigt sich mit Klassen von ähnlichen Objekten und den Eigenschaften der zugehörigen Abbildungen (siehe Kapitel 8).

Definition 66. Sei (M, ∘) eine Halbgruppe, E ⊆ M . E heißt freies Erzeugendensystem von M, falls gilt:

1. ⟨E⟩ = M

2. Für alle Halbgruppen H: ∀φ_{0} : E → H : ∃φ : φ ist ein Homomorphismus und φ|_{E} = φ_{0}. (jede Abbildung von E → H läßt sich zu einem Homomorphismus fortsetzen)

Eine Halbgruppe (M, ∘) heißt frei, falls sie ein freies Erzeugendensystem besitzt.

Beachte, daß die Fortsetzung φ von φ_{0} in 2 eindeutig bestimmt ist.

Beispiel 26. Die Halbgruppe (IN, +) hat {1} als freies Erzeugendensystem.

Übungsaufgabe 67. Wenn φ ein Isomorphismus von Halbgruppen (Monoiden) ist, so ist auch φ^{−1} ein Isomorphismus.

8 Kategorien, Homomorphismen

Kategorien beschreiben den Begriff der strukturverträglichen Abbildungen zwischen gleichartigen Objekten. Beispiele sind: Mengen und Abbildungen, Halbgruppen und Halbgruppenhomomorphismen, Monoide und Monoid-Homomorphismen, oder Programme einer Programmiersprache und semantikerhaltende Transformationen.

Definition 68. Eine Kategorie besteht aus einer Menge (Klasse) O von Objekten und einer Menge (Klasse) von Morphismen A. Jeder Morphismus f hat als zugeordnete Objekte genau eine Quelle dom(f) und genau ein Ziel cod(f). Wir schreiben f : a → b, wenn a die Quelle und b das Ziel von f ist. Man schreibt auch HOM(a, b) für die Menge aller Morphismen f : a → b.

Folgende Axiome gelten:

Verknüpfung: Wenn f : a → b und g : b → c, dann existiert der zusammengesetzte Morphismus g ∘ f : a → c.

Assoziativität: Wenn f : a → b, g : b → c, h : c → d, dann gilt (h ∘ g) ∘ f = h ∘ (g ∘ f).

Einselement: Zu jedem Objekt a gibt es eine Abbildung 1_{a} : a → a, so daß für alle Morphismen f : a → b und g : b → a gilt: f ∘ 1_{a} = f und 1_{a} ∘ g = g

Definition 69. Seien a, b Objekte einer Kategorie. Ein Morphismus f : a → b heißt

• Monomorphismus, falls ein Morphismus f^{−} : b → a existiert, so daß f^{−} ∘ f = 1_{a}

• Epimorphismus, falls ein Morphismus f^{−} : b → a existiert, so daß f ∘ f^{−} = 1_{b}

• Isomorphismus, falls φ Monomorphismus und Epimorphismus ist.

• Endomorphismus, falls f : a → a .

• Automorphismus, falls f : a → a und f Isomorphismus.

Diese Definition von Mono-, Epi-, und Isomorphismus kann man als Rezept auffassen, in Strukturen die richtigen strukturerhaltenden Abbildungen zu finden. Beachte, daß alle kategorientheoretischen Betrachtungen die innere Struktur der Objekte ignorieren und nur die Pfeile (Morphismen) und deren Eigenschaften verwenden.

Z.B. kann man Unterobjekte und Quotienten von Objekten definieren:

• b ist ein Unterobjekt von a, wenn es einen Monomorphismus f : b → a gibt.

• b ist ein Quotient von a, wenn es einen Epimorphismus f : a → b gibt.

Abbildungen zwischen Kategorien nennt man Funktoren:

Definition 70. Seien C, D zwei Kategorien. F ist ein Funktor von C nach D, wenn es eine Abbildung F : O_{C} → O_{D} und eine Abbildung F : A_{C} → A_{D} gibt, so daß

• Für alle Morphismen f : a → b ist F (f) ein Morphismus F (f) : F (a) → F (b)

• Wenn f ∘_{C} g definiert ist, dann gilt F (f ∘_{C} g) = F (f) ∘_{D} F (g)

• F (1_{C}) = 1_{D}

Beispiel 27. Kann man Monoide auch als Halbgruppen ansehen, wenn man die ausgezeichnete Rolle des Einselements (der inneren Verknüpfung) außer acht läßt. Dies entspricht einem Funktor von der Kategorie der Monoide in die Kategorie der Halbgruppen. Diese Abbildung ist ein sogenannter Vergiß-Funktor.

9 Alphabete, Worte, Formale Sprachen

In der Informatik sind Worte, Wortmengen (formale Sprachen) grundlegend zur Betrachtung der Syntax von Programmiersprachen. Sei A eine endliche nichtleere Menge (Alphabet).

Definition 71. Die Menge A^{+} := ⋃{A^{n} | n ≥ 1} heißt die Menge aller Wörter über A. Ist w ∈ A^{n}, dann heißt w Wort über A und n heißt die Länge von w. (|w| = n)

Statt (a_{1}, a_{2}, …, a_{n}) schreiben wir in Zukunft a_{1}a_{2} … a_{n}.

Definition 72. Seien u = u_{1} … u_{n} ∈ A^{+} und v = v_{1} … v_{m} ∈ A^{+} zwei Worte über A, dann heißt die Verknüpfung • definiert durch u • v := u_{1} … u_{n}v_{1} … v_{m} die Konkatenation von u und v.

Statt u • v schreiben wir in Zukunft uv

Satz 73. (A^{+}, •) ist eine Halbgruppe, (die Worthalbgruppe).

Satz 74.

1. Jedes Wort w ∈ A^{+} ist eindeutig als Produkt von Elementen aus A darstellbar.

2. (A^{+}, •) ist links- und rechts-kürzbar

3. (A^{+}, •) ist frei

Beweis. : 1 und 2 gelten, da Gleichheit in kartesischen Produkten elementweise definiert ist. 3: Sei (H, ∘) eine Halbgruppe und sei φ_{0} : A → H eine Abbildung. Definiere φ : A^{+} → H durch φ(a_{1} … a_{n}) := φ_{0}(a_{1}) ∘ … ∘ φ_{0}(a_{n}). Wegen φ(uv) := φ(u) ∘ φ(v) definiert dies einen Homomorphismus. Da φ|_{A} = φ_{0}, ist φ eine homomorphe Fortsetzung von φ_{0}. Da trivialerweise ⟨A⟩ := A^{+}, ist A ein freies Erzeugendensystem von A^{+}. ⊓ ⊔

Satz 75. Worthalbgruppen über Alphabeten gleicher Kardinalität sind isomorph.

Beweis. Wir zeigen A^{+} ≡ B^{+} ⇔ |A| = |B|.

⇒: Sei φ : A^{+} → B^{+} der Isomorphismus. Dann ist auch φ^{−1} ein Isomorphismus. Wir zeigen, daß φ eine Bijektion von A und B vermittelt: Sei a ∈ A und sei φ(a) = b_{1} … b_{n} ∈ B^{+}. Dann ist a = φ^{−1}(b_{1}) … φ^{−1}(b_{n}). Daraus folgt n = 1, da wir die Struktur von A^{+} kennen. Also ist φ(a) ∈ B. Analog können wir zeigen, daß φ^{−1}(b) ∈ A für alle b ∈ B ist. Also bildet φ|_{A} eine Bijektion von A auf B.

⇐: Sei φ_{0} : A → B eine Bijektion. Da A^{+} frei mit Erzeugendensystem A ist, gibt es eine homomorphe Fortsetzung φ von φ_{0}. Da φ(A) = B ist, ist φ ein Epimorphismus. Sei φ(a_{1} … a_{n}) = φ(a′_{1} … a′_{m}) mit a_{i}, a′_{i} ∈ A. Es gilt dann auch φ_{0}(a_{1}) … φ_{0}(a_{n}) = φ_{0}(a′_{1}) … φ_{0}(a′_{m}) . Da φ_{0}(a_{i}), φ_{0}(a′_{i}) ∈ B folgt mit Satz 74 daß n = m und φ_{0}(a_{i}) = φ_{0}(a′_{i}). Da φ_{0} eine Bijektion ist, gilt dann auch a_{i} = a′_{i} für alle i. Damit ist φ auch ein Monomorphismus. Also ist φ ein Isomorphismus. ⊓ ⊔

Satz 76. Sei (M, ∘) eine Halbgruppe mit endlichem Erzeugendensystem. Dann gilt: (M, ∘) ist frei ⇔ Es gibt eine Menge A so daß (M, ∘) isomorph zu A^{+} ist.

Beweis.

⇒: Sei (M, ∘) frei mit dem freien Erzeugendensystem E ⊂ M. Betrachte die Menge E^{+}. Sei ι die Einbettung von E in E^{+}, also ι(e) = e für alle e ∈ E. Da M frei mit Erzeugendensystem E, gibt es eine homomorphe Fortsetzung φ von ι. Wir zeigen, daß φ ein Isomorphismus ist.

1. φ ist Epimorphismus: Sei f := e_{1} … e_{n} ∈ E^{+}. Betrachte f′ = e_{1} ∘ … ∘ e_{n}. Es gilt φ(f′) = φ(e_{1} ∘ … ∘ e_{n}) = φ(e_{1}) … φ(e_{n}) = ι(e_{1}) … ι(e_{n}) = e_{1} … e_{n} = f ∈ E^{+}. Also ist φ ein Epimorphismus.

2. φ ist Monomorphismus: Sei f := e_{1} ∘ … ∘ e_{n} ∈ M und g := e′_{1} ∘ … ∘ e′_{m} ∈ M mit φ(f) = φ(g). Dann ist φ(e_{1}) … φ(e_{n}) = φ(e′_{1}) … φ(e′_{m}) und beides sind Elemente in E^{+}, woraus folgt, daß m = n und e_{i} = e′_{i} ist für alle i = 1, …, n.

⇐: Wir haben schon gezeigt, daß A^{+} frei ist. Diese Eigenschaft haben auch alle isomorphen Halbgruppen.

⊓ ⊔

Damit haben wir gezeigt, daß die freien Halbgruppen genau die Worthalbgruppen sind.

Bemerkung. Ist (M, ∘) eine Halbgruppe, aber kein Monoid, dann kann man (M, ∘) stets zu einem Monoid machen, indem man ein Einselement 1_{M} adjungiert. D.h. Man betrachtet M ∪ {1_{M}} und definiert 1_{M} ∘ f = f ∘ 1_{M} = f für alle f ∈ M und 1_{M} ∘ 1_{M} = 1_{M}. Ist (M, ∘) schon ein Monoid, so erhält man ein neues Monoid mit neuer 1. Ist (A^{+}, ∘) eine Worthalbgruppe, dann liefert diese Konstruktion ein Einselement, das wir in Zukunft mit ε bezeichnen, ε nennt man auch das leere Wort. Die Länge des leeren Wortes soll 0 sein: |ε| := 0. A^{∗} := (A^{+} ∪ {ε}, •) nennt man auch das vom Alphabet A erzeugte Wort-Monoid.

Worte werden auch als Strings (Zeichenketten) bezeichnet. Die Menge A^{∗} bezeichnet man auch als Kleene-Abschluß von A.

Das Monoid A^{∗} ist nicht mehr frei im Sinne der Definition für Halbgruppen, diese Definition kann aber für Monoide entsprechend angepaßt werden.

Ein Wort v ist Präfix eines Wortes w, wenn vu = w für ein Wort u. Ein Wort v ist Suffix eines Wortes w, wenn uv = w für ein Wort u. Eine echter Präfix (Suffix) v von w ist ein Präfix ( Suffix) v mit v ≠ w.

Definition 77. Sei A ein endliches Alphabet. Eine Menge L ⊆ A^{∗} heißt formale Sprache, Elemente von L heißen Worte der Sprache L.

Beispiel 28.

1. Die Menge {0, 1} ist die Menge der Binärziffern. Diese werden auch Bits genannt.

2. Die Menge {0, 1}^{8} ist die Menge der Binärfolgen der Länge 8. Diese werden auch Bytes genannt.

3. Die Menge der Palindrome : {a_{1} … a_{n} ∈ A^{∗} | a_{1} … a_{n} = a_{n} … a_{1}} ist eine formale Sprache.

4. Die Menge {ε} ist eine formale Sprache

5. {0, 1}^{∗} ist die formale Sprache aller binären Strings

6. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}^{∗} ist gerade die Sprache aller Bezeichnungen von natürlichen Zahlen (allerdings ist nicht garantiert, daß die erste Stelle ≠ 0 ist).

Eine Möglichkeit, formale Sprachen zu beschreiben, sind reguläre Ausdrücke über einem Alphabet A. Diese sind folgendermaßen definiert:

Definition 78. Wir geben die Syntax für reguläre Ausdrücke an.

1. ε ist ein regulärer Ausdruck

2. a ist ein regulärer Ausdruck für a ∈ A.

3. Wenn r und s reguläre Ausdrücke sind, dann auch (r + s), (rs) und (r^{∗}).

Wenn man Sprachen R und S über dem Alphabet A hat, dann bezeichnet RS die Menge aller Konkatenationen von Wörtern aus R und S, d.h. RS := {uv | u ∈ R, v ∈ S}. Definiert man R^{n} durch R^{0} := {ε}, R^{1} := R und R^{n} := RR^{n−1}, dann ist der (Kleene-)Abschluß definiert als R^{∗} := ⋃{R^{n} | n ≥ 0} , der positive Abschluß ist definiert als R^{+} := ⋃{R^{n} | n ≥ 1}.

Jeder reguläre Ausdruck r über dem Alphabet A beschreibt eine formale Sprache I_{A}(r), wobei I die Interpretation ist, wenn man induktiv definiert:

1. I_{A}(ε) := {ε}.

2. I_{A}(a) := {a} für a ∈ A.

3. I_{A}((r + s)) := I_{A}(r) ∪ I_{A}(s).

4. I_{A}((rs)) := I_{A}(r)I_{A}(s).

5. I_{A}(r^{∗}) := (I_{A}(r))^{∗}.

Beispiel 29. Mit Hilfe der regulären Ausdrücke können wir die Sprache der Binärdarstellung aller positiven ganzen Zahlen ohne führende Nullen hinschreiben: (1((0 + 1)^{∗})

Definition 79. Eine formale Sprache L heißt regulär, wenn es einen regulären Ausdruck gibt, der L erzeugt.

Bemerkung: es gibt Sprachen, die nicht regulär sind.

10 Turingmaschine und Turingberechenbarkeit

Das abstrakte Modell eines möglichst einfachen und doch universellen Rechners wurde von Alan Turing (1936) eingeführt, um auch formal sagen zu können, was Berechenbarkeit heißt, insbesondere um herauszufinden, welche Funktionen berechenbar sind und ob es auch nichtberechenbare Funktionen gibt.

Zunächst wollen wir die Turingmaschine informell einführen. Diese besteht aus einem beiderseits unendlichen Band mit Feldern, auf denen jeweils ein Zeichen steht. Diese Zeichen können mittels eines Schreib/Lesekopfes gelesen und geschrieben werden, allerdings kann der Schreib/Lesekopf nur das Feld bearbeiten, das gerade im Zugriff ist. Der Schreib/Lesekopf kann folgende Aktionen ausführen: Lesen eines Zeichens, Schreiben eines neuen Zeichens, Verschieben um ein Feld nach links, Verschieben um ein Feld nach rechts.

Eine spezielle Turingmaschine (Abkürzung: TM) T besteht außerdem noch aus einem endlichen Programm, das in Tabellenform geschrieben werden kann, und das die Aktionen des Kopfes steuert. Dieses Programm kann man sich in numerierten Einzelbefehle gegliedert vorstellen: Jeder Einzelbefehl ist eine Fallunterscheidung über das gelesene Zeichen und als Aktion kann ein Zeichen geschrieben, der Lese-Schreibkopf um eine Stelle verschoben werden, und zu einem anderen Befehl verzweigt werden. Befehle können folgendermaßen aussehen:

80.  Wenn gelesenes Zeichen = "a", dann  schreibe "b" ,
verschiebe den Lesekopf nach links,
weiter mit Befehl 199.
        oder gelesenes Zeichen  = "b", dann schreibe "b" ,
verschiebe den Lesekopf nach rechts,
weiter mit Befehl 3.

Als Eingabe (Input) erhält die TM ein beschriftetes Band, der Schreib/Lesekopf steht auf dem linkesten Zeichen der Eingabe. Der beschriftete Teil muß endlich sein, und es muß zu erkennen sein, wo er endet, deshalb nimmt man an, daß das Band außerhalb des beschrifteten Teils mit blank (wir schreiben B) initialisiert ist. Die Maschine fängt mit dem ersten Befehl an und arbeitet Befehle solange ab, bis es nicht mehr weitergeht, d.h., ein Fall nicht definiert ist oder zu einem nicht existierenden Befehl verzweigt wird. Die Ausgabe der TM ist der dann beschriftete Teil des Bandes.

Beispiel 30. Eingabe: eine Zahl n in Binärdarstellung. Ausgabe: n + 1 in Binärdarstellung. Das Programm soll folgendes tun:

1. Lesekopf nach rechts schieben:

2. Addieren mit Übertrag von rechts nach links.

Z1.  Wenn 0, dann schreibe 0, gehe nach rechts, weiter mit Z1.
Wenn 1, dann schreibe 1, gehe nach rechts, weiter mit Z1.
Wenn B, dann schreibe B, gehe nach links, weiter mit Z2.
Z2.  Wenn 0, dann schreibe 1, gehe nach links, weiter mit Z3.
Wenn 1, dann schreibe 0, gehe nach links, weiter mit Z2.
Z3.

Wenn wir als Beschreibung des aktuellen Zustandes der Turingmaschine ein Wort α.z.β verwenden, so daß α der linke beschriftete Teil ist, z die Nr. des zu bearbeitenden Befehls und β der rechte beschriftete Teil, und der Schreib/Lesekopf auf dem linkesten Zeichen von β steht, so sieht eine Beispielrechnung für 5+1 = 6 folgendermaßen aus (Wir ignorieren äußere Leerzeichen):

B.Z1.101 → 1.Z1.01 → 10.Z1.1 → 101.Z1.B → 10.Z2.1 → 1.Z2.00 → B.Z3.110

Der Gesamtzustand einer Turingmaschine ist eindeutig bestimmt durch:

• den Bandinhalt

• die Position des Schreib/Lesekopfes

• die Nr. des aktuellen Befehls.

Wir wollen nun die Turingmaschine formal definieren. Hierbei ist zu beachten, daß die formale Definition zwei Teile hat: 1. Turingmaschinenprogramm und 2. Ausführung. Wenn wir in Zukunft von einer Turingmaschine reden, so meinen wir das Turingmaschinenprogramm.

Definition 80. Eine Turingmaschine (Abkürzung: TM) T ist ein 5-Tupel (Z, A, B, δ, z_{0}) wobei

Z eine endliche Menge von Zuständen
A die Menge der erlaubten Bandsymbole (das Alphabet), wobei Z ∩ A = ∅.
B ein ausgezeichnetes Zeichen in A, (Leerzeichen, blank).
δ ist eine partielle Funktion δ : Z × A → Z × A × {L, R} (Übergangsfunktion).
z_{0} ist der Startzustand.

Die Zeichen L, R sollen die anzuwendende Verschiebung bedeuten. L für “nach links“, R für “nach rechts“. Man beachte, daß δ eine partielle Funktion sein kann, d.h. die Übergangsfunktion kann für bestimmte Zustände/gelesene Zeichen undefiniert sein. Diese Formalisierung sagt noch nichts darüber aus, was eine Turingmaschine tatsächlich tut. Um das zu tun, müssen wir sagen, wie der aktuelle Zustand formalisert wird, und wie T darauf operiert.

Definition 81. Sei T = (Z, A, B, δ, z_{0}) eine TM. Eine Konfiguration ID (instantaneous description) einer Turingmaschine sei ein Wort αqβ ∈ A^{∗}ZA^{∗}. Die Operation von T wird als Funktion δ^{∗} : A^{∗}ZA^{∗} → A^{∗}ZA^{∗} definiert: Sei αqβ ein Wort aus A^{∗}ZA^{∗}. Wenn β das leere Wort ist, so ersetze β durch das Wort B. Sei jetzt β = β_{1}β_{2}, wobei β_{1} das erste Zeichen von β ist und β_{2} der Rest. Betrachte δ(q, β_{1}). Ist δ(q, β_{1}) undefiniert, so ist δ^{∗} undefiniert. Anderenfalls ist δ(q, β_{1}) = (p, Y, M), wobei p der nächste Zustand, Y das zu schreibende Zeichen und M die Bewegungsrichtung ist. Dann ist die neue Konfiguration:

αY pβ_{2} falls M = R

α_{1}pα_{2}Y β_{2}, falls M = L, α ≠ ε, wobei α = α_{1}α_{2}, und α_{2} das letzte Zeichen von α,

pBY β_{2} falls M = L, α = ε.

Die Funktion δ^{∗} nennt man auch operationale Semantik (oder Interpreter). Wenn eine Konfiguration K die Konfiguration K′ nach sich zieht, so schreiben wir auch K ⊢ K′ und nennen K′ den Folgezustand von K. Eine endliche Berechnung mittels T bei Eingabe w ist eine endliche Folge von Konfigurationen K_{1}, K_{2}, …, K_{n}, wobei K_{1} = z_{0}w und K_{i} ⊢ K_{i+1} für alle i, und K_{n} keinen Folgezustand hat. Wenn die Berechnung bei Eingabe w endlich ist, so sagt man auch T terminiert (hält an) bei Eingabe w.

Der beschriftete Teil des Bandes wird auch als Bandinschrift bezeichnet, wobei die Bandinschrift rechts und links keine B’s enthalten darf. D.h. die Bandinschrift ist das Wort, das (von links) mit dem ersten Zeichen ≠ B beginnt und mit dem letzten ≠ B endet.

Vergleicht man diese Definition mit der informellen Beschreibung, so sieht man, daß die Zustände den Befehlsnummern entsprechen, daß der Anfangszustand dem ersten Befehl entspricht, und die Übergangsfunktion δ dem Programm entspricht. Diese Definition ist konsistent mit dem Beispiel bis auf die dort verwendeten trennenden Punkte in der Notation der Konfiguration.

Bemerkung. Die Definition 81 beschreibt das Verhalten einer Turingmaschine als Operation auf Worten. Die obige Darstellung ist recht einfach, hat aber als leichten (formalen) Nachteil, daß es verschiedene Konfigurationen gibt, die man eigentlich als gleich ansehen würde, z.B. würde man BBz1BB als äquivalent zu Bz1B ansehen. Dies hat jedoch keinen Einfluß auf die Wirkungsweise.

Es gibt in der Literatur andere Definitionen des Begriffs Turingmaschine, die sich leicht, aber nur unwesentlich davon unterscheiden.

Definition 82. Sei T = (Z, A, B, δ, z_{0}) eine TM. Dann ist die von T akzeptierte Sprache L(T) folgendermaßen definiert: L(T) = {α ∈ (A\{B})^{∗} | die Turingmaschine hält nach einer endlichen Anzahl von Schritten für die Anfansgkonfiguration z_{0}α}.

Um zu sagen, was berechenbar heißt, definieren wir diesen Begriff für Funktionen A^{∗} → A^{∗}.

Definition 83. Sei A ein Alphabet. Eine partielle Funktion f : (A \ B)^{∗} → (A \ B)^{∗} heißt Turing-berechenbar, wenn es eine Turingmaschine T = (Z, A, B, δ, z_{0}) gibt, so daß gilt: Für alle w ∈ (A \ B)^{∗} für die f(w) definiert ist, hält die Turingmaschine T bei Eingabe z_{0}w nach endlich vielen Schritten an, und die Bandinschrift ist gerade f(w).

Es gibt verschiedene Definitionsvarianten von Turingmaschinen, z.B., unterscheidet man manchmal zwischen akzeptierenden Zuständen und Zuständen, in denen es nicht mehr weitergeht, oder das Band ist nur einseitig unendlich. Alle diese Definitionen haben sich bislang als äquivalent erwiesen, dies gilt auch für alle Verallgemeinerungen, wie z.B. das Einführen mehrerer Bändern (jeweils mit eigenem Schreib/Lesekopf) und auch für die Größe des Alphabets, solange es mehr als 2 Zeichen enthält. Andere Definitionen der Berechenbarkeit, die auf den ersten Blick nichts mit Turingmaschinen zu tun haben, haben sich ebenfalls als äquivalent zur Turing-Berechenbarkeit erwiesen. U.a. sind das:

• Haskell-Programme

• Markov Algorithmen

• Registermaschinen

• Goferprogramme

• λ-Kalkül

• μ-rekursive Funktionen • Postsche Kalküle

• Semi-Thuesysteme

Hierbei nennt man zwei Maschinenmodelle äquivalent, wenn man mit beiden dieselben Berechnungen durchführen kann (wobei man noch Übersetzungen benötigt).

Church’sche These: Alle irgendwie automatisch (mechanisch) berechenbaren Funktionen sind auch berechenbar mittels des λ-Kalküls, und alle Berechenbarkeitsbegriffe sind äquivalent.

Deshalb spricht man statt von Turingberechenbarkeit auch von Berechenbarkeit.

Der Unterschied zwischen partiellen Funktionen und totalen Funktionen ist wesentlich, denn der Berechenbarkeitsbegriff für Turingmaschinen, die auf jeder Eingabe anhalten, ist nicht äquivalent zur (allgemeinen) Berechenbarkeit, er ist echt schwächer. Will man statt den Wert einer Funktion eine Eigenschaft bestimmen, zum Beispiel: Eingabe: eine Zahl n, Frage: ist n eine Primzahl?, so kann man dies ebenfalls als Berechnung einer Funktion deuten: Eingabe ist die Zahl n in irgendeiner Darstellung. Wenn die entsprechende Turingmaschine anhält und die Bandinschrift ε ist, ist es eine Primzahl, anderenfalls nicht. Wenn die Turingmaschine nicht anhält, so kann man keine Aussage machen, d.h. das Resultat ist undefiniert. Im Fall unseres Beispiels der Primzahlen ist es allerdings wünschenswert und auch machbar, daß die Turingmaschine immer anhält (immer entscheidet), und nicht für bestimmte Zahlen nie anhält.

Da die direkte Handhabung der obigen Kodierung in Beweisen mittels und über Turingmaschinen etwas schwerfällig ist, und es andere (äquivalente) Definitionen mit angenehmeren Eigenschaften gibt, deren genauere Betrachtung aber den Rahmen dieses Skripts und Vorlesung sprengen würde, werden wir im folgenden so tun, als wüßten wir wie man es macht und annehmen, daß die Berechnung mittels (alternativ definierter) Turingmaschinen folgende Eigenschaften hat^{2} :

Definition 84. Annahme 1 über Eigenschaften der Turingmaschinen.

1. Wir betrachten eine TM T als partielle Funktion von A^{∗} ∪ {⊥} → A^{∗} ∪ {⊥}, also mit Eingabe und Ausgabe und schreiben T (w) = ⊥ falls die zugehörige Turingmaschine nicht terminiert. Wir definieren T (⊥) = ⊥ für alle Turingmaschinen T.

2. Wir können Turingmaschinen wie Funktionen verknüpfen: T_{1} • T_{2} ist eine Turingmaschine, die die Funktion mit (T_{1} • T_{2})(w) = T_{1}(T_{2}(w)) für alle w ∈ A^{∗} realisiert. Falls T_{2}(⊥) = ⊥, ergibt sich vernünftigerweise (T_{1} • T_{2})(⊥) = T_{1}(T_{2}(⊥)) = T_{1}(⊥) = ⊥.

2 Für Interessierte: das technische Problem unserer einfachen Definition ist, daß man für einen Endzustand

nicht feststellen kann, was die Bandinschrift ist, da man nicht weiß, wie weit sich der Lesekopf von der

Bandinschrift entfernt hat. Um das in den Griff zu kriegen, braucht man entweder Extrasymbole, wie rechte

und linke End-markierungen und evtl. noch weitere Hilfssymbole, oder ein weiteres Leerzeichen C und ein

Schreib- und Eingabeverbot für B, so daß man den bereits benutzten Teil des Bandes erkennen kann.

3. Es gibt eine Turingmaschine T_{COP Y} mit T_{COP Y} (w) = ww.

Definition 85. Sei A ein Alphabet und T und F zwei verschiedene Worte in A^{∗}, und E eine totale Funktion E : A^{∗} → {T, F }. Wir sagen auch: E ist eine Eigenschaft auf A^{∗}. Dann ist E entscheidbar (algorithmisch lösbar), wenn es eine Turingmaschine T_{E} gibt, die für jede Eingabe terminiert und T_{E}(w) = E(w).

Auch der Begriff der Entscheidbarkeit hat sich als unabhängig von der Formalisierung herausgestellt. Entscheidbare Eigenschaften sind im Prinzip dasselbe wie totale berechenbare Funktionen. Im folgenden wollen wir zeigen, daß es nicht möglich ist, mit Hilfe einer Turingmaschine das Halteproblem zu lösen, d.h. zu berechnen, ob eine beliebige Turingmaschine T bei Eingabe w anhält oder nicht.

Definition 86. Annahme 2 über Eigenschaften der Turingmaschinen. Es gibt eine (vernünftige) Kodierung φ von Turingmaschinen als Worte in A^{∗}, so daß φ : {T | T ist T M} → A^{∗} ein Injektion ist.

Die Kodierung des Programms einer Turingmaschine könnte man so machen: Jedes Zeichen wird als ein String von 0’en kodiert, so daß jedes Zeichen durch mehr als eine 0 dargestellt wird. Das Alphabet A = {0, 1, B}, wird so kodiert, daß 0 durch 0, 1 durch 00 und B durch 000 dargestellt wird. Die Zustände werden ebenfalls durchnumeriert und in eindeutiger Weise als Nullen kodiert, L wird durch 0, R durch 00 kodiert. Ein Befehl besteht aus mehreren Fällen, für jedes mögliche gelesene Zeichen eine. Ein einzelner Fall hat die Bestandteile:

• a: das gelesene Zeichen,

• b: das geschriebene Zeichen

• D: Die Bewegungsrichtung (L oder R)

• z: der neue Zustand.

Ein Fall eines Befehl wird dann kodiert als 1φ(a)1φ(b)1φ(D)1φ(z)1. Ein Befehl (entspricht einem Zustand) wird kodiert als 110φ(Fall_{1})0 … 0φ(Fall_{n})011 kodiert, Das ganze Turingmaschinenprogramm wird kodiert als 1110φ(Befehl_{1})0φ(Befehl_{2})0 … 0φ(Befehl_{n})0111

Solche eineindeutigen Kodierungen bezeichnet man auch als Gödelisierung. Falls die entsprechende Kodierung eine natürliche Zahl ist, spricht man auch von Gödelnummer .

Es ist kein Problem, die Turingmaschinen fortlaufend zu numerieren, denn die Menge der Turingmaschinen ist abzählbar. D.h., wir haben T_{i}, i = 1, … ist die Folge aller Turingmaschinen über {0, 1} (siehe Satz 27). Hieraus folgt auch sofort, daß es Funktionen f : IN → IN gibt, die nicht berechenbar sind, denn die Menge der Turingmaschinen ist abzählbar, während die Menge der Funktionen überabzählbar ist (siehe Satz 28).

Wir geben auch ein konkretes Problem an, daß diese unangenehme Eigenschaft hat:

Das Halteproblem ist das Problem eine feste Turingmaschine T_{h} zu entwerfen, die für alle Turingmaschinen T und für alle Eingaben w entscheidet, ob T auf w anhält.

Satz A. Turing Es gibt keine Turingmaschine, die das Halteproblem löst.

Beweis. Wir nehmen an, es gibt ein Programm T_{n}, so daß

T_{n}(i) = 0, wenn T_{i}(i) nicht terminiert, und
T_{n}(i) = 1 wenn T_{i}(i) terminiert.

Wir ändern das Programm T_{n} ab zu einem Programm T_{m}, das, wenn T_{n} mit 0 terminiert, auch mit 0 terminiert, und im Falle, daß T_{n} mit 1 terminiert, eine nichtterminierende Berechnung startet. Es gilt jetzt:

T_{m}(i) = 0 gdw. T_{i}(i) nicht terminiert

T_{m}(i) terminiert nicht gdw. T_{i}(i) terminiert

Betrachten wir jetzt die Selbstanwendung: T_{m}(m). Für diese gilt: T_{m}(m) terminiert gdw. T_{m}(m) nicht terminiert. Das ist ein Widerpsruch. Also gibt es kein Programm T_{n}. ⊓ ⊔

Definition 87. Eine universelle Turingmaschine U ist eine Turingmaschine, die als Eingabe die Kodierung einer Turingmaschine T und einen Eingabestring w, so daß gilt: U(φ(T)w) = T (w).

Mit einigem technischen Aufwand kann man zeigen:

Satz 88. Es gibt eine universelle Turingmaschine U.

Dies bedeutet, daß es eine einzige Turingmaschine gibt, mit der man im Prinzip jede Berechnung ausführen (simulieren) kann. Dies ist auch die theoretische Grundlage für Rechenanlagen, die ja auch ihr Programm im gleichen Speicher wie die Daten haben. Man muß aber beachten, daß Turingmaschinen Idealisierungen von solchen Rechnern sind, da eine konkrete Rechenanlage nur begrenzten Speicher hat.

Andererseits bedeutet dies auch, daß die Nichtberechenbarkeit des Halteproblems auch für alle anderen Programmiersprachen gilt, die so ausdrucksstark wie Turingmaschinen sind.

11 Graphen und Bäume

Definition 89. Eine Inzidenzstruktur ist ein Tripel (E, K, I), wobei E und K disjunkte Mengen sind und I ⊆ E × K. Diese Inzidenzstruktur heißt ungerichteter Graph, wenn für alle k ∈ K : 1 ≤ |{e ∈ E | (e, k) ∈ I}| ≤ 2. Die Menge E sind die Knoten (Ecken, engl: vertex) und K die Kanten (engl: edges) des Graphen. Die Bedingung ist dann, daß auf jeder Kante mindestens ein Knoten liegt, aber nicht mehr als zwei.

Definition 90. Falls e_{1}Ik und e_{2}Ik, bezeichnet man e_{1}, e_{2} als Endknoten der Kante k, man sagt e_{1} und e_{2} sind Nachbarn (oder direkt verbunden). Eine Kante k heißt Schlinge, falls |{e ∈ E | (e, k) ∈ I}| = 1. Eine Kante k heißt Mehrfachkante, falls es ein k′ gibt, so daß die Endknoten von k und k′ übereinstimmen. Ein Graph G heißt schlicht, falls er weder Schlingen noch Mehrfachkanten besitzt.

Bemerkung. Ein schlichter Graph kann auch durch ein Tupel (E, K) repräsentiert werden, wobei K ⊆ P(E) und K ∈ K ⇒ |K| = 2, d.h. die Kanten sind durch ihre Endknoten eindeutig bestimmt. Wir schreiben dann G = G(E, K). Ein Graph definiert eine Äquivalenzrelation der verbundenen Knoten. Diese Relation ist die symmetrische und transitive Hülle der durch die Kanten erzeugten Relation. Einen Repräsentanten dieser Äquivalenzklasse nennt man Zusammenhangskomponente. Wenn alle Knoten verbunden sind, d.h. wenn diese Relation nur eine Äquivalenzklasse hat, dann nennt man den Graph zusammenhängend.

Definition 91. Ein gerichteter Graph (Digraph, directed graph) G ist ein Tupel (E, K) mit K ⊆ E × E. Der zugrundeliegende (ungerichtete) Graph ist das Paar (E, K′) mit K′ = {{e, f} | (e, f) ∈ K}. Wir schreiben dann G = G(E, K). Ist (a, b) ∈ K, so ist a der Anfangsknoten von k und b der Endknoten von k. Man sagt auch a ist direkter Vorgänger von b und b direkter Nachfolger von a. Sei e ∈ E. Die Zahl γ^{+}(e) := |{a | (e, a) ∈ K}| heißt Ausgangsgrad (outdegree) von e. Die Zahl γ^{−}(e) = |{a | (a, e) ∈ K}| heißt Eingangsgrad (indegree) von e. γ^{+}(e) + γ^{−}(e) heißt Eckengrad (degree) von e. Der Knoten e ∈ E heißt Anfangsknoten (Endknoten) von G, falls γ^{−}(e) = 0 (bzw. γ + (e) = 0).

Im folgenden betrachten wir nur gerichtete Graphen im Sinne der Definition 91.

Ein gerichteter Graph definiert eine Präordnung auf seinen Knoten, wenn man die Kanten als erzeugende Relationen der Ordnung ansieht und die transitive Hülle bildet.

Definition 92. Sei G = G(E, K) ein gerichteter Graph. Der Graph G′ = G′(E′, K′) mit E′ ⊆ E und K′ ⊆ K heißt Teilgraph von G. Der Teilgraph W = ({e_{i}|i = 1, …, n + 1}, {(e_{i}, e_{i+1}) | i = 1, …, n}) heißt Weg der Länge n von e_{1} nach e_{2}. W heißt Kreis, falls e_{1} = e_{n}. Wir schreiben W = e_{1} … e_{n} für einen Weg. Sei W = e_{1} … e_{n} ein Weg. Der Knoten e_{i} heißt Nachfolger (bzw. Vorgänger) von e_{j}, falls j < i (bzw. i < j). Im Falle j + 1 = i (bzw. i + 1 = j) spricht man auch von direktem Nachfolger (direkter Vorgänger).

Ein gerichteter Graph ohne Kreise heißt azyklisch, man spricht auch von DAG (directed acyclic graph), die entsprechende Ordnung ist eine irreflexive Ordnung. Ein azyklischer (endlicher) gerichteter Graph hat mindestens eine Quelle und eine Senke, wobei eine Quelle ein minimales Element und eine Senke eine maximales Element in der Ordnung ist (ob maximal oder minimal, hängt an der Richtung: man interpretiert normalerweise eine Ordnung R wie <). Ein gerichteter Graph heißt zusammenhängend, falls der zugrundeliegende Graph zusammenhängend ist. Ein gerichteter Graph heißt stark zusammenhängend, falls es zwischen je zwei Knoten e und f einen Weg von e nach f oder von f nach e gibt.

Ein Graph G(E, K) mit einer Abbildung φ : G → D heißt (knoten-)markierter Graph mit Marken aus D. Wenn man zusätzlich eine Abbildung φ : K → D betrachtet, dann ist der Graph kanten-markiert.

Ein ungerichteter Graph heißt k-färbbar, wenn es eine Knoten-Markierung φ gibt mit Marken aus {1, …, k} und für alle Knoten k_{1} ≠ k_{2} gilt: wenn φ(k_{1}) ≠ φ(k_{2}), dann sind k_{1} und k_{2} nicht direkt mittels einer Kante verbunden. Ein 2-färbbarer Graph heißt auch bipartit.

Definition 93. Ein Graph T = T (E, K) heißt Baum, falls E = ∅ oder

• es gibt genau eine Wurzel e = w(T), das ist ein Knoten e mit γ^{−}(e) = 0,

• für jeden Knoten f ≠ w(T) gilt γ^{−}(f) = 1,

• für alle Knoten f ≠ w(T) gibt es einen Weg von w(T) nach f.

Bemerkung. Die charakterisierende Eigenschaft eines Baumes als Ordnung ist, daß es genau ein maximales Element gibt, und daß für beliebige Knoten a ≠ b mit a < b die Menge {c | a ≤ c ≤ b} linear geordnet ist. Das entspricht der Eigenschaft von Bäumen, daß es entweder genau einen oder keinen Weg zwischen a und b gibt.

Definition 94. Sei T ein Baum. Ein Endknoten von T heißt Blatt. Ein Knoten, welcher kein Endknoten ist, heißt innerer Knoten. Der direkte Vorgänger (bzw. Nachfolger eines Knotens e ∈ E heißt (Vater (Mutter) (bzw. Tochter (Sohn)) von e. Zwei Knoten e, f heißen Schwestern (Brüder), falls sie den gleichen Vater (Mutter) besitzen. Ein Teilbaum T′ eines Baumes T ist ein Untergraph von T, der als Wurzel w eine Tochter von w(T) hat, so daß T′ alle Knoten enthält, die Nachfolger von w bezüglich T sind. D.h. ein Baum ist vollständig bestimmt durch die Wurzel und seine Teilbäume. Ein Knoten e hat Niveau N(e), falls der Weg von w(T) nach e die Länge N(e) besitzt . Der Baum hat die Höhe h(T), wobei h(T) := max{N(e) | e ∈ E}.

Eine Menge von Bäumen bezeichnet man auch als Wald.

Beispiel 31. Betrachte den folgenden Baum.

Dann hat der Baum zwei Teilbäume: {b} und {c, d, e}. a und c sind die inneren Knoten, d und e sind Schwestern (Brüder), a ist die Mutter von b, und b und c sind die Söhne von a. Die Blätter sind b, d und e. Der Knoten a hat Niveau 0, c hat Niveau 1, und d hat Niveau 2. Die Höhe des Baumes ist 2.

Definition 95. Ein Baum der zusätzlich noch eine Ordnung ≺ auf den Knoten besitzt, die für jeden Knoten e eine lineare Ordnung auf allen Söhnen ist, heißt geordneter Baum (planarer Baum).

Beachte: Diese Ordnung hat nichts zu tun mit der Ordnung, die von den gerichteten Kanten erzeugt wird. Wenn man im Beispiel 31 die Ordnung b ≺ c und d ≺ e nimmt, so ergibt sich ein geordneter Baum, und die Abbildung spiegelt die Ordnung wieder.

Definition 96. Sei T = T (E, K) ein geordneter Baum. T heißt binärer Baum, falls jeder Knoten höchstens zwei Töchter besitzt und jede Tochter entweder als linke oder als rechte Tochter gekennzeichnet ist. Ist T ein binärer Baum mit Teilbäumen T_{1} und T_{2} und ist w(T_{1}) linker Sohn und w(T_{2}) rechter Sohn, so heißt T_{1} linker Teilbaum und T_{2} rechter Teilbaum.

Bemerkung: Geordnete Bäume (insbesondere binäre Bäume) spielen eine wesentliche Rolle bei der Darstellung der syntaktischen Struktur von Ausdrücken. Betrachte zum Beispiel den Ausdruck:

exp(a) + bc - sin(d)

Die Blätter korrespondieren mit den Variablen und Konstanten, die inneren Knoten mit den Operatoren.

Geordnete Bäume kann man auch ansehen als präfixabgeschlossene formale Sprachen über {1, …, n}, wobei eine formale Sprache L präfixabgeschlossen ist, wenn mit jedem Wort auch jeder Präfix in L enthalten ist. Im allgemeinen fordert man noch die Lückenlosigkeit von L: Für jedes Wort e.i ∈ L und 1 ≤ j < i ist auch e.j ∈ L.

Definition 97. Ein Baumbereich ist eine formale Sprache über {1, …, n}, die präfixabgeschlossen und lückenlos ist.

Das leere Wort entspricht der Wurzel des Baumes, Nichtleere Worte von L kann man als Baumadressen ansehen. 1.3.1 entspricht dem Knoten, den man auf folgendem Weg erreicht: Starte an der Wurzel, gehe zum ersten Sohn, von da aus gehe zum dritten Sohn, von da aus gehe zum ersten Sohn.

Definition 98. Ein markierter Baum (bewerteter Baum, labelled tree) ist ein Tripel (T, φ, M), wobei T ein Baumbereich, M eine Menge von Markierungen ist, und φ eine Abbildung φ : T → M ist.

Eine Standardoperation für markierte Bäume ist : frontier(T, φ, M) := φ(w(T)), falls w(T) ein Blatt ist frontier(T_{1}, φ, M) … frontier(T_{n}, φ, M), falls T_{1}, …, T_{n} die n Teilbäume von T sind

Diese Funktion sammelt genau die Markierungen der Blätter des Baumes auf.

Es gibt verschiedene Arten, die Knoten eines geordneten Baumes zu linearisieren. bzw. bei einer Verarbeitung zu durchlaufen.

Definition 99. Sei T = T (E, K) ein geordneter Baum.

• Die Postorder von T ist ein Wort in E^{∗} mit

PO(T) := ε, falls T = ∅,
PO(T_{1}) … PO(T_{n})w(T), falls T_{i} der i-te Teilbaum von T ist.

• Die Preorder (Reihenfolge bei Tiefensuche) von T ist ein Wort in E^{∗} mit

PR(T) := ε, falls E = ∅,
w(T)PR(T_{1}) … PR(T_{n}), falls T_{i} der i-te Teilbaum von T ist.

• Die Inorder von T ist ein Wort in E^{∗} mit

IO(T) := ε, falls E = ∅, IO(T_{1})w(T)IO(T_{2}) … IO(T_{n}), falls T_{i} der i-te Teilbaum von T ist. Dies ist

gerade die Reihenfolge von links nach rechts beim Durchlaufen eines binären Baumes.

• Die military order (Reihenfolge bei Breitensuche) von T ist ein Wort in E^{∗} das folgendermaßen definiert ist: Sei w_{k} = x_{1} … x_{n} ein Wort, das alle Knoten von T mit Niveau k in der Links-Rechts-Ordnung enthält, und h die Höhe von T, Dann ist BSO(T) := w_{0}w_{1} … w_{h}

Bemerkung. Die Preorder ist die Ordnung der Knoten, die man beim Durchlauf des Baumes von rechts links nach rechts, oben nach unten, erhält. Preorder, Postorder und Breitensuchordnung hängen nur von der Links-Rechts-Ordnung ab, während Inorder bei binären Bäumen davon abhängt, welche Knoten als rechte und welche als linke Söhne definiert werden.

Beispiel 32.

Postorder: P O(T) = P O(T_{b})P O(T_{c})a = dbgehifca Preorder: P R(T) := abdcegfhi military order: abcdefghi Inorder: dbaegchfi (hier ergibt sich ein Unterschied für lückenlos oder nicht)

Beispiel 33. Kodierung eines Alphabets A mittels eines anderen Alphabets B. Sei φ_{0} : A → B^{+} eine injektive Abbildung. Diese Abbildung kann man eindeutig homomorph fortsetzen zu einem Homomorphismus φ : A^{∗} → B^{∗}. Um eindeutige Kodierbarkeit zu gewährleisten, interessiert man sich für solche Kodierungen, bei denen φ ein Monomorphismus ist. Eine hinreichende Bedingung dafür ist, daß die Menge φ(A) als formale Sprache die Präfixeigenschaft hat. Eine Sprache L die Präfixeigenschaft (auch Fanobedingung genannt), wenn für zwei Worte v, w ∈ L gilt, daß v kein Präfix von w sein kann. Diese Kodierungen lassen sich in Baumform darstellen, so daß ein Dekodierungsalgorithmus direkt mit diesem Baum arbeiten kann. Kodiert man die Zeichen A, B, C zum Beispiel als 00, 01, 1 so erhält man den Baum

Die kodierten Zeichen des Alphabets sind dann gerade die Blätter des Baumes.

12 Kontextfreie Grammatiken und Sprachen

Kontextfreie Grammatiken werden benutzt, um formale Sprachen (z.B. Syntax von Programmiersprachen, Zahldarstellungen, Syntax der Prädikatenlogik) zu definieren.

Definition 100. Eine kontextfreie Grammatik (CFG, context free grammar) ist 4-Tupel G = (N, T, P, σ) mit

1. einer endlichen Menge N von Hilfszeichen (Nonterminals)

2. einer endlichen Menge T von Terminalzeichen (Terminals), das eigentliche Alphabet, so daß N ∩ T = ∅

3. einem ist ein ausgezeichnetes Hilfszeichen (Startzeichen, Axiom) σ ∈ N

4. einer endlichen Menge (Produktionensystem) P ⊆ N × (N ∪ T)

Bemerkung. (A, w) ∈ P heißt Produktion oder Regel von G. statt (A, w) ∈ P schreibt man auch A → w. Die Grammatik heißt kontextfrei, da die Ersetzungen der Nichtterminale unabhängig vom Kontext gemacht werden dürfen.

Beispiel 34. Ein Teil der Syntax von Programmiersprachen:

⟨Ausdruck⟩ ::= ⟨Atom⟩ | ⟨Zahl⟩ | (⟨Ausdrücke⟩)
⟨Ausdrücke⟩ ::= ⟨Ausdruck⟩ | ⟨Ausdruck⟩⟨Ausdrücke⟩
⟨Zahl⟩  ::= ⟨Ziffer⟩ | ⟨Ziffer⟩⟨Zahl⟩
⟨Ziffer⟩  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
⟨Atom⟩  ::= ⟨Buchstabe⟩ | ⟨Buchstabe⟩⟨Zeichen⟩
⟨Buchstabe⟩ ::= A | B | C | D | …
⟨Zeichen⟩  ::= ⟨Ziffer⟩ | ⟨Zahl⟩

Definition 101. Sei G = (N, T, P, σ) eine CFG. Die Relationen ⟹_{G}, ⟹_{G,l}, ⟹_{G,r} in (N ∪ T)^{∗} ×

(N ∪ T)^{∗} werden definiert durch:

1. αAβ ⟹_{G} αwβ für alle α, β ∈ (N ∪ T)^{∗} und Regeln A → w. (αwβ ist direkt ableitbar aus αAβ)

2. αAβ ⟹_{G,r} αwβ für alle α ∈ (N ∪ T)^{∗}, β ∈ T^{∗} und Regeln A → w. (αwβ ist direkt

rechts-ableitbar aus αAβ)

3. αAβ ⟹_{G,l} αwβ für alle α ∈ T^{∗}, β ∈ (N ∪ T)^{∗}, und Regeln A → w. (αwβ ist direkt

links-ableitbar aus αAβ)

Bezeichnet ⟹_{G}^{+}, ⟹_{G,l}^{+} und ⟹_{G,r}^{+} die entsprechenden transitiven Hüllen der Relationen, und ⟹_{G}^{∗},

⟹_{G,l}^{∗} und ⟹_{G,r}^{∗} die entsprechenden reflexiven-transitiven Hüllen, so heißt ψ ableitbar (rechts-

ableitbar, linksableitbar) aus φ, falls φ ⟹_{G}^{∗} ψ (bzw. φ ⟹_{G,r}^{∗} ψ, φ ⟹_{G,l}^{∗} ψ) . Ist φ = σ, so

heißt ψ ableitbar (rechtsableitbar, linksableitbar).

Beispiel 35. Betrachte einen Teil der kontextfreien Grammatik der Aussagenlogik ({V, E}, {A, B, C, ∨, ∧, (,), ¬}, R, E), so daß R aus den folgenden Regeln besteht:

V → A V → B V → C E → V E → (E ∨ E) E → (E ∧ E) E → (¬E)

Dann ist zum Beispiel ((¬A) ∨ A) aus E ableitbar: E ⟹ (E ∨ E) ⟹ ((¬E) ∨ E) ⟹ ((¬A) ∨ E) ⟹ ((¬A) ∨ A).

Definition 102. Sei G = (N, T, P, σ) eine CFG. Ein Ableitungsbaum B von w (derivation tree, parse tree) ist ein markierter Baum, so daß

1. jeder Knoten mit einem Element aus {ε} ∪ N ∪ T markiert ist,

2. Die Wurzel mit s markiert ist,

3. innere Knoten mit Elementen aus N markiert sind,

4. wenn ein Knoten die Markierung A hat und seine Söhne die Markierungen X_{1}, …, X_{k} (in dieser Reihenfolge), so ist A → X_{1} … X_{k} eine Regel in P,

  5. frontier(B) = w

Es gilt: Satz 103. Sei G = (N, T, P, σ) eine CFG. Ein Wort w ∈ (N ∪T)^{∗} ist genau dann ableitbar, wenn es einen Ableitungsbaum für w gibt.

Definition 104. Sei G = (N, T, P, σ) eine CFG. Die von G erzeugte formale Sprache ist definiert durch: L(G) := {w | w ∈ T^{∗}, σ ⟹_{G}^{∗} w} .

Definition 105. Eine formale Sprache L heißt kontextfrei, wenn es eine kontextfreie Grammatik G gibt mit L(G) = L.

Es gibt kontextfreie Sprachen, die nicht regulär sind. Es gibt auch formale Sprachen, die nicht kontextfrei sind. Ein Beispiel ist {a^{n}b^{n}c^{n} | n ≥ 0}.

Die Backus-Naur-Form (BNF) ist eine weit verbreitete Methode, die kontextfreie Syntax höherer Programmiersprachen aufzuschreiben. Metasymbole (Symbole die nicht in der Sprache selbst benutzt werden), sind:⟨, ⟩,::= und |, wobei zum Beispiel ⟨Zahl⟩ ein Nichtterminalsymbol ist, das mittels ::= definiert wird. Das Zeichen | trennt die verschiedenen Alternativen. Die Regel ⟨Ziffer⟩ ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 entspricht 10 verschiedenen Regeln einer CFG. Diese Schreibweise kennt auch Erweiterungen, um eine Syntax kompakter hinschreiben zu können, zum Beispiel, um rekursive Regeln wie ⟨Zahl⟩ ::= ⟨Ziffer⟩ | ⟨Ziffer⟩⟨Zahl⟩ schreibt man manchmal auch ⟨Zahl⟩ ::= ⟨Ziffer⟩^{+}. Erweitert man die Metasyntax, so kann man mehrere Regeln zusammenfassen, wenn diese Regeln nur deshalb dupliziert worden sind, um optionale Strings auszudrücken, z.B.

⟨Zahl mit Vorzeichen⟩ ::= +⟨Zahl⟩ | ⟨Zahl⟩ | − ⟨Zahl⟩

schreibt man manchmal auch als ⟨Zahl mit Vorzeichen⟩ ::= [+|−]⟨Zahl⟩ wobei [,] Ausdrücke einklammern, die man auch weglassen kann.

Es gibt noch andere Formen, diese Syntax zu beschreiben. z.B. die Syntaxdiagramme, wie sie zur Beschreibung von Pascal verwendet werden. Hier werden Regeln in Form von graphischen Darstellungen verwendet. z.B.

Hier bedeuten repeat in ovalen Kästschen: Zeichenkette als Terminalsymbol, rechteckiges Kästschen: Nichtterminalsymbol. Die Pfeile bezeichnen erlaubte Durchlaufrichtungen. Die BNF hierfür wäre z.B.

⟨repeat-expr⟩ ::= repeat ⟨statements⟩ until ⟨expression⟩
⟨statements⟩ ::= ⟨statement⟩ | ⟨statement⟩;⟨statements⟩

Offensichtlich kann eine Programmiersprache mehrere verschiedene CFG’s haben. Deshalb muß man vorsichtig sein, wenn man Eigenschaften der Sprachen mit Hilfe von Eigenschaften der Grammatik definiert. Hierzu gehört die Mehrdeutigkeit einer Grammatik. Diese ist gegeben, wenn es zu einem Wort w mehr als eine Linksableitung gibt (d.h. auch mehr als einen Ableitungsbaum). Eine kontextfreie Sprache L heißt mehrdeutig (inhärent mehrdeutig), falls für alle CFG G mit L(G) = L gilt, daß G mehrdeutig ist. Hier besteht ein Zusammenhang mit der Frage, ob (und wie) man die Bedeutung von Worten einer formalen Sprache anhand einer CFG eindeutig festlegen kann, siehe auch Kapitel 13.

Pragmatisch gilt, daß die zulässigen Programme realer Programmiersprachen im allgemeinen nicht durch eine CFG erzeugt werden, denn bestimmte Programme werden aufgrund von Kontextbedingungen ausgeschlossen. Z.B. müssen Deklarationen oft vor der Benutzung von Variablen gemacht werden, oder Ausdrücke müssen getypt sein (in Gofer). D.h. die CFG ist i.a. nur ein erster Schritt in der Definition der zulässigen Programme.

13 Semantik von formalen Sprachen, interpretierte Systeme

Bisher haben wir formale Sprachen als Mengen uninterpretierter Wörter eingeführt, können aber noch nicht von einer Bedeutung reden. Zum Beispiel kann man nicht so ohne weiteres sagen, daß {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}^{∗} die Menge der natürlichen Zahlen IN_{0} ist. In Programmiersprachen wird ja auch ein Unterschied zwischen dem String “128“ und der Zahl 128 gemacht. Die Bedeutung oder die Interpretation der Zeichen schreibt man normalerweise getrennt zur Definition der Sprache hin. Eine solche Bedeutung nennt man auch Semantik. Eine Interpretation ist nichts anderes als eine Abbildung der Wörter auf ihren Wert (Bedeutung). Deswegen definieren wir:

Definition 106. Ein interpretiertes System besteht aus 3 Komponenten: (L, D, δ). L ist eine Menge von syntaktischen Objekten, D ist eine Menge von Resultaten, und δ : L → D eine partielle Abbildung, die syntaktischen Objekten einen Wert aus D zuordnet. Im allgemeinen macht man die Funktion δ total, indem man das interpretierte System (L, D∪{⊥}, δ′) benutzt, und δ′(p) = ⊥ setzt, wenn δ für p undefiniert ist. Man bezeichnet L als die Syntax, und δ als die Semantik.

Beispiel 36. Berechnungen als interpretierte Systeme: Nimmt man L als Menge von Paaren (P, I), wobei P ein Programm ist, I die Eingabe, und D := Menge der möglichen Resultate, dann definiert man δ(P, I) := R, falls R das Ergebnis der Berechnung ist bei der P mit der Eingabe I versorgt wird. Im Fall einer nicht-terminierenden Berechnung ist δ(P, I) undefiniert, und man definiert dann δ(P, I) := ⊥

Definition 107. Sei Φ := (L, D, δ) ein interpretiertes System. Zwei Objekte p_{1}, p_{2} ∈ L heissen semantisch äquivalent, gdw. δ(p_{1}) = δ(p_{2}).

Bei der Veränderung bzw. Optimierung von Programmen ist es wesentlich, daß die semantische Äquivalenz erhalten bleibt. Allerdings ist die Frage der semantischen Äquivalenz im allgemeinen unentscheidbar, denn anderenfalls könnte man das Halteproblem lösen.

Beispiel 37. Die Menge der Objekte sei {a, b}^{∗}. Die Interpretation eines Wortes sei definiert durch

• I(ε) := 0

• I(a) := 0

• I(b) := 1

• I(uv) := 2 ∗ I(u) + I(v) für u ∈ L und v ∈ {a, b}.

Man sieht: dies ist gerade die Interpretation von Strings über {a, b} als binäre Zahlen, wobei a als 0 und b als 1 interpretiert wird: I(aab) = 1, I(baaa) = 8.

Die Semantik der Aussagenlogik läßt sich hier einordnen: Seien X_{1}, …, X_{n} die vorkommenden Aussagenvariablen. Wir betrachten als Resultatmenge die Menge der Funktionen f : {T, F }^{n} → {T, F }, wobei {T, F } eine Boolesche Algebra mit den Operatoren ∧, ∨, ¬ ist. Dann definiert man

δ(F) := λX_{1}, …, X_{n}.F)

Tautologien sind dann solche Aussageformen, die die konstante Funktion λX_{1}, …, X_{n}.T als Semantik haben. Alle Umformungen, die die Semantik erhalten, sind zulässig. Wenn man Transformationen auf Aussageformen definiert, so kann (und muß) man die Korrektheit dieser Transformationen anhand der Semantik überprüfen: Transformiert man F → G, so bleibt die semantische Äquivalenz erhalten, wenn für alle Interpretationen I gilt: I(F) = I(G). Dies gilt zum Beispiel für die Transformation (A ∨ T) → T, wie man leicht nachprüft.

Die Semantik der Prädikatenlogik erster Stufe läßt sich ebenfalls hier einordnen, ist aber etwas komplizierter (siehe Kapitel 2).

Alle Transformationen auf der syntaktischen Ebene müssen, wenn sie korrekt sein sollen, diese Semantik erhalten. D.h. für eine Transformation G_{1} → G_{2} muß gewährleistet sein, daß I(G_{1}) = I(G_{2}) für alle Interpretationen I gilt. Die erweiterte Ausdruckskraft der Prädikatenlogik gegenüber der Aussagenlogik hat einen Preis: die Überprüfung, ob eine Aussage eine Tautologie ist, erfordert nach obiger Definition i.a. die Überprüfung von unendliche vielen verschiedenen Interpretationen. Es gibt für die Prädikatenlogik Kalküle, die feststellen können, ob eine Aussage eine Tautologie ist. Allerdings kann es passieren, daß diese Kalküle unendlich lange weiterlaufen, falls die zu testende Formel keine Tautologie ist.

Bemerkung. Zur Semantik des λ-Kalküls. Die intuitive Vorstellung, daß der λ-Kalkül eine Semantik hat, wobei die Resultatmenge eine Menge von Elementen, Funktion, Funktionen von Funktionen ... ist, führt bei einer naiven Definition auf Widersprüche (ähnlich zum Russelschen Paradoxon), denn die Resultatsmenge R müßte dann auch alle Funktionen von R → R enthalten. Bekanntlich ist die Kardinalität von R → R echt größer als die Kardinalität von R. Eine genauere (umfangreiche) Betrachtung mit verbandstheoretischen Methoden zeigt, daß man doch “intuitive“ Modelle definieren kann, wobei nicht alle Funktionen aus R → R gebraucht werden.

Übungsaufgabe 108.

1. Verifizieren Sie, daß die Transformationsregel ¬∀x.G → ∃x.¬G korrekt ist .

2. Zeige, daß ∀x.P (x) ∨ ¬P (x) eine Tautologie ist.

14 Notationen von Ausdrücken, Terme

In arithmetischen Ausdrücken, in logischen Aussagen, und in Programmiersprachen verwendet man Ausdrücke, die einen Wert besitzen. Charakteristisch ist, daß man in den Ausdrücken zwischen Operatoren und Argumenten unterscheidet.

Beispiel 38. 1 ∗ 2 + 3 − 4 ist ein arithmetischer Ausdruck mit dem Wert 1. (T ∨ ¬F) ∧ T ist ein logischer Ausdruck mit dem Wert T. (∗ 1 2 3 4) ist ein Lisp-Ausdruck mit dem Wert 24.

Bei diesen Ausdrücken ist zu unterscheiden zwischen ihrer Notation und ihrem Wert, also zwischen der Syntax und der Semantik.

Das wesentliche Ziel bei der Erfindung und Benutzung von Notationen ist es zu erreichen, daß ein Ausdruck einen eindeutigen Wert hat. Andere Kriterien und Zwecke, die eine wesentliche und teilweise konkurrierende Rolle spielen sind: die Notation muß gut leserlich sein und sollte möglichst wenig überflüssige Symbole enthalten. Eine Forderung kann auch sein, daß sie gut von einem Rechner verarbeitet werden kann. Schwierigkeiten die dabei entstehen sind: i) teilweise werden verschiedene Operatoren gleich bezeichnet, z.B. das minus-Zeichen in −1 − 2 , oder ii) ein Operator hat variable Stelligkeit: (∗ 1 2 3 4), oder iii) Operatoren nehmen verschiedene Positionen zu ihren Argumenten ein: (+ 1 2) oder 1 + 2, oder

(IF A THEN B ELSE C) bzw. IFTHENELSE(A, B, C)

Definition 109. Eine Signatur ist ein Paar (F, arity), wobei F eine endliche Menge von Funktionssymbolen und arity eine Funktion arity : F → IN_{0}, die Stelligkeit des Symbols, ist. Funktionssymbole f mit arity(f) = 0 bezeichnet man auch als Konstantensymbole.

Ein Term über der Signatur ist ein Wort aus der Sprache (F ∪ “(“, “)“, “, “)^{∗} , also F angereichert um rechte Klammer, linke Klammer und Komma, wobei Terme folgendermaßen rekursiv definiert werden:

1. ein Konstantensymbol ist ein Term

2. f(t_{1}, …, t_{n}) ist ein Term, wobei f ein Funktionssymbol mit arity(f) = n ist, und t_{1}, …, t_{n} Terme sind.

Ein Beispiel für eine Signatur und die zugehörigen Terme ist die Menge der Funktionssymbole und Terme der Prädikatenlogik.

Definition 110. Eine (universelle, oder allgemeine) Algebra über der Signatur F ist ein Tripel (A, O, φ), wobei A ≠ ∅ eine Menge ist, O eine Menge von Funktionen, φ eine Bijektion von O → F (wir schreiben φ(f) als f_{A}) so daß für jedes f ∈ F mit arity(f) = n, f_{A} eine n-stellige Funktion ist: f_{A} : A^{n} → A.

Offensichtlich gilt für eine Algebra (A, O, φ): Jedem Term kann man einen eindeutigen Wert in A zuweisen durch:

φ(f(t_{1}, …, t_{n})) := f_{A}(φt_{1}, …, φt_{n})

Damit ist für eine Algebra über der Signatur F das System (T , A, φ) ein interpretiertes System, wobei T die Menge der Terme ist.

Verschiedene Notationen werden im allgemeinen dadurch eindeutig, daß man eine Abbildung der Notation auf Terme angibt, und dann erst einen Wert berechnet. Z.B könnte man −1 − 2 eindeutig auf den Term SUBTRACT(NEGATE(1), 2) abbilden.

Definition 111. Notationen

1. Die Notation, die in Definition 109 definiert wird, ist die Standardnotation. Terme werden notiert in der Form f(t_{1}, …, t_{n}) , wobei zu beachten ist, daß f ein Symbol sein muß (d.h. kein Ausdruck sein darf) .

2. Die Notation, die in Lisp verwendet wird, ist die Präfixnotation. Hier wird statt f(t_{1}, …, t_{n}) das Wort (f t_{1} … t_{n}) verwendet. Der Grund liegt darin, daß es auch erlaubt ist Terme für Operatoren einzusetzen und Operatoren an Argumentstellen zu verwenden, und Operatoren variabler Stelligkeit zu benutzen, und somit eine gemischte Notation nicht so ohne weiteres eindeutig wird.

3. Eine Abwandlung der Präfixnotation ist die polnische Notation, (Lukasiewicz-Notation, polnische Präfixnotation), bei der im Gegensatz zur normalen Präfixnotation einfach alle Klammern weggelassen werden. Dies ist nur dann eindeutig möglich, wenn alle Operatoren Symbole sind, die Operatorensymbole eindeutig sind, und eine feste Stelligkeit haben.

4. Die Standardpostfixnotation. Hier wird statt f(t_{1}, …, t_{n}) das Wort (t_{1}, …, t_{n})f verwendet. Diese Notation wird in der Mathematik manchmal verwandt, wenn man Homomorphismen rechts schreibt. Wir haben diese Notation benützt für die Definition der Substitution und der Interpretation.

5. Die Postfixnotation (polnische Postfixnotation, reverse polish). Hier werden in der Standardpostfixnotation einfach alle Klammern weggelassen. Es gelten die gleichen Bemerkungen wie zur Präfixnotation. Diese Notation hat eine Bedeutung in der Informatik, denn der Auswertungsalgorithmus für Terme läßt sich direkt mittels eines Kellers implementieren. In der Mathematik wird diese Notation beispielsweise für die Fakultätsfunktion verwendet 3! = 6.

6. Die Infixnotation. Diese wird im allgemeinen nur für zweistellige Operatoren verwendet. Der Operator wird dann zwischen die Argumente geschrieben. z.B. (1 + 2). Auch hier gilt, daß die Operatoren Symbole sein sollten, damit eine eindeutige Auswertung möglich ist.

7. Will man Notationsformen mischen und/oder möglichst wenige Klammern benutzen, und die Ausdrücke eindeutig lassen, so braucht man Konventionen und Prioritäten von Operatoren. Zum Beispiel ist der Ausdruck (1 + 2 ∗ 3 + 4!) äquivalent zum Term ((1 + (2 ∗ 3)) + (4!)). Hier hat man für die Prioritäten: ! > ∗ > + . Der Term (1 + 2 − 3) wird als ((1 + 2) − 3) interpretiert nach der Konvention links vor rechts.

Es gibt noch andere Notationsformen, die wir hier nicht betrachten, zum Beispiel graphische, wie m^{n}, f_{A}, oder ¯(N).

Übungsaufgabe 112. Programmiere: Wandle arithmetische Ausdrücke mit den Operatoren +, −, ∗ von Infixnotation in Postfixnotation um und werte sie direkt mittels eines Kellers aus.