Zur Prädikatenlogik siehe das zweite Kapitel im Buch Logik für Informatiker von Uwe Schöning.

Die Semantik der Aussagenlogik (und die weiteren Themen im Logikteil) finden sich im Buch Logik für Informatiker von Uwe Schöning.

Wir fassen den Stoff zur Syntax der Semantik sowie zu den darauf basierenden Themen zur strukturellen Rekursion und zur strukturellen Induktion noch einmal zusammen und wiederholen die einzelnen Begriffe. Bei Unklarheiten zu den einzelnen Begriffen, lohnt sich stets ein Blick in den Haupttext oben.

• Syntax der Aussagenlogik
• Strukturelle Rekursion
• Strukturelle Induktion

Im vorherigen Abschnitt haben wir gesehen, wie der Aufbau komplexer Formeln aus einfache(re)n Formeln genutzt werden kann, um Funktionen über die Formelmenge zu definieren. Ähnlich kann man den Aufbau der Formeln nun nutzen, um Eigenschaften von Formeln nachzuweisen. Dies wird als strukturelle Induktion bezeichnet.

Sei für jede Formel \(F \in \mathcal{L}_{AL}\) dazu \(B(F)\) eine Behauptung zu \(F\) (z.B. die Behauptung, dass die Länge von \(F\) stets größer ist als die Anzahl der Operatoren in \(F\)). Wollen wir nun \(B(F)\) für alle Formeln der Aussagenlogik zeigen, so kann dies mittels struktureller Induktion gelingen.

Vielen, die zum ersten Mal mit der strukturellen Induktion in Berührung kommen, ist nicht klar, warum man die Aussage nun für alle Formeln bewiesen hat? Dies wird nachfolgend erklärt. Wem das klar ist (die Begrüundung ist ganz ähnlich wie bei der vollständigen Induktion), der kann den nachfolgenden Absatz überspringen. Im Anschluss kommt dann noch einmal der Beweis für obige Aussage in deutlich knapperer Form.

 
Den in der Definition der Syntax beschriebenen Aufbau komplexer Formeln aus einfache(re)n Formeln kann man nutzen, um Funktionen über die Formelmenge zu definieren und so bspw. eine Funktion \(f\) zu definieren, die jeder Formel \(F\) einen Wert \(f(F)\) zuzuweisen (bspw. die Länge der Formel oder die Anzahl der Junktoren in der Formel). Man nennt dies strukturelle Rekursion).

Ähnlich kann man den Aufbau der Formeln auch nutzen, um Eigenschaften von Formeln nachzuweisen. Dies wird als strukturelle Induktion bezeichnet und wird im nächsten Abschnitt behandelt.

Wenn wir nun mittels struktureller Rekursion eine Funktion definieren wollen, so ist es unser Ziel eine (totale) Funktion \(f: \mathcal{L}_{AL} \rightarrow D\) zu definieren, wobei \(D\) dabei eine beliebige Menge sein kann. \(f\) wird also jeder Formel \(F \in \mathcal{L}_{AL}\) ein Element \(x \in D\) zuweisen. In unserem Fall wird \(D\) meist die Menge \(\mathbb{N}\) der natürlichen Zahlen sein. Um \(f\) nun zu definieren genügt es,

1. \(f(A)\) für jedes \(A \in AS_{AL}\) festzulegen und
2. eine Funktion \(f_\neg : D \rightarrow D\) und für jeden Junktor \(\circ \in \{\vee, \wedge, \Rightarrow, \Leftrightarrow\}\) eine Funktion \(f_\circ: D \times D \rightarrow D\) zu definieren.
   Es ist dann \(f(\neg F) := f_\neg(f(F))\) und z.B. \(f((F \wedge G)) := f_\wedge(f(F), f(G))\) (und analog für die anderen zweistelligen Junktoren).

Informal formuliert ist der Grad einer Formel die Anzahl der Junktoren (bei \(((A \wedge (B \Rightarrow C)) \vee (B \wedge A))\) also \(4\)). Die Tiefe einer Formel ist die Anzahl der Junktoren in der tiefsten Verschachtelung. Führt man noch Strukturbäume ein, so kann man die Tiefe verstehen als die Anzahl der Junktoren auf dem längsten Pfad im Strukturbaum.

Exkurs: Strukturbäume

Statt Formeln als Zeichenketten der Art \((A \wedge B)\) auszudrücken, kann man Formeln auch als Bäume, sogenannte Strukturbäume, ausdrücken. Dies ist für manche Algorithmen hilfreich.

Ein Strukturbaum zu einer Formel \(F\) ist ein Baum, bei dem die inneren Knoten (die Knoten, die keine Blätter sind) Junktoren sind und die Blätter die atomaren (Teil-)Formeln von \(F\).

Im einzelnen:

1. Der Hauptoperator markiert die Wurzel.
2. Teilformeln entsprechen Teilbäumen.
3. Die Reihenfolge der Teilformeln wird beibehalten (linke Teilformel, linkes Kind).
4. Die Aussagesymbole werden dann die Blätter des Baumes.
5. Die Junktoren sind die inneren Knoten. Dabei hat \(\neg\) ein Kind, alle anderen Junktoren haben zwei Kinder.

Ein Beispiel veranschaulicht dies schnell. Sei \(F = ((A \vee C) \wedge \neg B)\), dann ergibt sich als Strukturbaum zu \(F\)

 
Noch ein paar Begrifflichkeiten. Wir hatten bereits den Begriff des Aussagesymbols und den des Junktors (die \(\neg\), \(\vee\) usw.). Weitere gebräuchliche Begriffe sind Alphabet für die Menge der benutzbaren Symbole. Das Alphabet besteht bei uns also aus den Aussagesymbolen, den Junktoren und den Klammern. Weiterhin nennt man eine Formel, die beim Aufbau einer Formel \(F\) verwendet wird, eine Teilformel von \(F\). Außerdem ist \(F\) Teilformel von sich selbst. Den Junktor, der im letzten Konstruktionsschritt verwendet wurde nennt man den Hauptoperator. Nach dem Hauptoperator werden komplexe Formeln oft benannt. Zum Beispiel ist in der Formel \(F = (A \vee (B \wedge C))\) \((B \wedge C)\) eine Teilformel. Der Hauptoperator ist \(\vee\), weswegen \(F\) auch als Disjunktion bezeichnet wird (im Falle von \(\wedge\) spricht man von einer Konjuktion, bei \(\Rightarrow\) von einer Implikation und bei \(\Leftrightarrow\) von einer Biimplikation).

 
Die Aussagenlogik ist eine ganz grundlegende Logik, die quasi als Teillogik in den meisten anderen Logiken enthalten ist. So werden z.B. in der Aussagenlogik einfache Verknüpfungen wie nicht, und und oder eingeführt, die man in den meisten anderen Logiken auch haben möchte. Ferner werden in der Aussagenlogik wichtige Konzepte und Begriffe eingeführt, die dann in andere Logiken übernommen werden. Sie ist daher auch hervorragend zum Einüben dieser Konzepte geeignet. Ferner, und für uns besonders interessant, spielt das Erfüllbarkeitsproblem der Aussagenlogik, d.h. die Frage, gegeben eine Formel der Aussagenlogik, kann diese zu wahr ausgewertet werden, eine zentrale Rolle in der Komplexitätstheorie und wird uns dort wieder begegnen.

Wir werden zunächst die Syntax der Aussagenlogik einführen, d.h. wir werden formal einführen, wie die Formeln der Aussagenlogik eigentlich aussehen dürfen, was wir also hinschreiben dürfen. Im Anschluss werden wir die Semantik der Aussagenlogik einführen, d.h. wir werden definieren, wann eine Formel wahr und wann eine Formel falsch ist und wie wir zu diesen Werten kommen. Nachfolgend geht es dann um Beziehungen zwischen Formeln. Hier führen wir die Begriffe der Folgerbarkeit und der Äquivalenz ein. Es wird dann viel darum gehen Formeln auf diese Eigenschaft zu prüfen und darauf, ob sie wahr gemacht werden können. Wir werden sehen, dass dies zwar gemacht werden kann, aber mit den nahe liegenden Verfahren zu aufwändig ist. Daher werden wir uns noch mit weiteren Verfahren wie z.B. der Resolution beschäftigen.

 
Im Logikteil wollen wir zwei Logiken, die Aussagenlogik und die Prädikatenlogik, betrachten. Logiken spielen in der Informatik bei den verschiedensten Anwendungen eine wichtige Rolle. Mit ihr lassen sich Sachverhalte aus der realen Welt abstrakt ausdrücken (es wird also quasi ein Modell der Welt in der Logik ausgedrückt). In der Logik können dann Schlussfolgerungen gezogen werden und diese können dann wieder als Sachverhalte in der realen Welt interpretiert werden. Ein Grundbaustein der Logik sind die Formeln. Beispielsweise ist \(N \vee \neg R\) eine aussagenlogische Formel, die für „ich bin nass (\(N\)) oder (\(\vee\)) es regnet (\(R\)) nicht (\(\neg\))“ stehen könnte. Wenn man nun wüsste das dieser Sachverhalt und zusätzlich noch \(R\) (es regnet) gilt, könnte man schlussfolgern, dass dann \(N\) gelten muss (ich bin nass). Mit der Logik können wir solche Schlussfolgerungen formalisieren, sie in komplizierteren Kontexten machen und dies auch (in Teilen) automatisieren.

Die Einsatzgebiete der verschiedenen Logiken sind in der Informatik recht vielfältig. So finden sie z.B. Einsatz bei dem Thema künstliche Intelligenz, bei Datenbanken, bei der Beschreibung von technischen Schaltkreisen, in der Software- und Hardwareverifikation, als Grundlage von logikorientierten Programmiersprachen wie beispielsweise Prolog und noch in etlichen Bereichen mehr. In vielen dieser Bereiche ist zudem ein Zusammenspiel von Logik und Automaten von Bedeutung. So werden z.B. in der Verifikation oft die System durch Automaten modelliert und durch eine Formel in einer Logik eine bestimmte Eigenschaft spezifiziert. Die Frage ist dann, ob das Modell die Spezifikation erfüllt. Wir werden nur am Rande und nicht vertiefend auf diese Anwendungsgebiete der Logik eingehen können. In späteren, vertiefenden Veranstaltungen wird einem die Logik aber immer wieder begegnen, so dass ein gutes Grundlagenwissen hierzu sehr nützlich ist.

Oftmals werden in verschiedenen Anwendungs- und Forschungskontexten verschiedene oder spezielle Logiken eingesetzt. Wir behandeln nachfolgend die Aussagenlogik und die Prädikatenlogik.

 
Für die erwähnten Probleme aus \(NP\) des vorherigen Abschnittes wie z.B. das Mengenpartitionsproblem sind keine deterministischen Algorithmen in Polynomialzeit bekannt. Wir würden dies nun gerne zeigen können, d.h. wir würden gerne zeigen können, dass sich das Problem für kein \(k\) in \(O(n^k)\) lösen lässt. Leider fehlen uns hierfür trotz intensiver Forschung die nötigen Techniken. Wir verfolgen daher einen anderen Ansatz. Wir zeigen für ein Problem \(X\) (von dem wir vermuten, dass es nicht in \(P\) ist), dass es bestimmte Eigenschaften hat, so dass, sollte \(X\) doch in \(P\) liegen, sehr unwahrscheinliche Dinge folgen würden.

Reduktionen

Um unser oben beschriebenes Ziel zu erreichen, wollen wir von einem Problem sagen können, dass es zu den schwierigsten Problemen seiner Klasse gehört. Hierzu brauchen wir den Begriff der Reduktion.

Andere Symbole für die Reduktion sind \(L_1 \leq_{pol} L_2\) oder auch \(L_1 \leq^p_m L_2\). Das \(m\) steht dabei für „many-one“, da man zwei (oder mehr) \(x,y \in L_1\) auf das gleiche \(f(x) = f(y) = u \in L_2\) abbilden darf. (Ebenso darf man zwei (oder mehr) \(x‘,y‘ \not\in L_1\) auf das gleiche \(f(x‘) = f(y‘) = u‘ \not\in L_2\) abbilden.)

 
Hat man eine Reduktion \(f: \{0,1\}^* \rightarrow \{0,1\}^*\) von \(L_1\) auf \(L_2\), so ist das wichtige, dass jedes \(x \in L_1\) (man spricht hier auch von Ja-Instanzen, da dies ein \(x\) ist, bei dem eine Turingmaschine für \(L_1\) (sofern eine existiert) mit ja antworten würde) auf ein \(y \in L_2\) abgebildet wird, also auf eine Ja-Instanz von \(L_2\). Ja-Instanzen werden also auf Ja-Instanzen und Nein-Instanzen auf Nein-Instanzen abgebildet. Die Fragen „Ist \(x \in L_1\)?“ und „Ist \(f(x) \in L_2\)?“ haben also stets die gleiche Antwort. Dies werden wir gleich ausnutzen. Die Abbildung verdeutlicht noch einmal eine Reduktion. Wir haben hier den allgemeinen Fall zweier Sprachen \(A \subseteq \Sigma^*\) und \(B \subseteq \Gamma^*\) skizziert. Man beachte, dass Ja-Instanzen auf Ja-Instanzen und Nein-Instanzen auf Nein-Instanzen abgebildet werden und dass mehrere Ja-Instanzen auf eine Ja-Instanz abgebildet werden können (und genauso mehrere Nein-Instanzen auf eine Nein-Instanz).

Man beachte, dass Ja-Instanzen auf Ja-Instanzen und Nein-Instanzen auf Nein-Instanzen abgebildet werden und dass mehrere Ja-Instanzen auf eine Ja-Instanz abgebildet werden können (und genauso mehrere Nein-Instanzen auf eine Nein-Instanz). Da Ja-Instanzen auf Ja-Instanzen abgebildet werden und Nein-Instanzen auf Nein-Instanzen und da die Reduktion per Definition berechenbar ist lassen sich Reduktionen ausnutzen, um Probleme durch andere zu lösen. Die Kernidee dabei ist, erst die Reduktion zu benutzen und dann das Problem, auf das reduziert wurde, zu lösen (und damit dann auch das ursprüngliche). Der folgende Satz konkretisiert dies.

Der obige Satz erlaubt es ein Problem (das \(L_1\) in obigem Satz) durch ein anderes (das \(L_2\)) zu lösen. Darum auch die Benennung Reduktion. Statt einen Algorithmus für \(L_1\) zu finden und so \(L_1\) zu lösen, nutzt man einen für \(L_2\) und löst so nicht nur \(L_2\), sondern (dank des Reduktionsalgorithmus) auch \(L_1\). Das Problem, \(L_1\) zu lösen, ist also darauf „reduziert“worden, das Problem \(L_2\) zu lösen. Man beachte aber, dass ein Reduktionsalgorithmus auch nichts anderes ist als ein ganz normaler Algorithmus. Die Aufgabe eines Reduktionsalgorithmus ist es aber, eine Probleminstanz in eine andere umzuwandeln. Also z.B. eine Instanz eines Graphenproblems in eine Instanz eines zahlentheoretischen Problems. (Man kann daher eine Reduktion auch als Transformation bezeichnen.)

Wenn wir nun für zwei Probleme \(A\) und \(B\) zeigen, dass \(A \leq_p B\) gilt, so wissen wir, dass \(A\) höchstens so schwierig wie \(B\) ist (höchstens bezieht sich hier auf den polynomiellen Mehraufwand, der hier (im Falle von Problemen in \(P\) und \(NP\)) als akzeptabel angsehen wird). \(A\) kann nämlich nicht schwieriger sein, denn sonst löst man \(A\) einfach indem man erst die Reduktion benutzt und dann \(B\) löst. Daher auch die Notation mit dem Kleiner-Gleich-Zeichen. Reduziert man nun jede Sprache aus \(NP\) auf eine (neue) Sprache \(L\), so ist \(L\) mindestens so schwierig wie ganz \(NP\), denn löst man nun \(L\), so kann man (mittels des Umwegs über die Reduktion) nun jedes Problem aus \(NP\) lösen. Das macht dann \(L \in NP\) sehr unwahrscheinlich, denn dann würde \(P = NP\) gelten, was als sehr unwahrscheinlich angesehen wird, da sich Generationen von Wissenschaftlern mit den verschiedenen Problemen in \(NP\) beschäftigt haben und nie für irgendeines dieser Probleme auf einen Algorithmus in \(P\) gekommen sind. – Es gibt noch weitere gute Gründe, warum \(P = NP\) unwahrscheinlich ist, diese führen hier aber etwas zu weit. Wir merken uns an dieser Stelle, dass es gute Gründe gibt \(P \not= NP\) anzunehmen. Bewiesen ist dies aber nicht!

Wir wollen nun obiges mit dem Begriff der \(NP\)-Vollständigkeit formalisieren und dann an Beispielen illustrieren, wie uns dies helfen kann für Probleme zumindest zu zeigen, dass es unter der Annahme \(P \not= NP\) keinen Algorithmus in Polynomialzeit geben kann. Da die Annahme ein recht starkes Fundament hat, ist dies dann schon eine recht starke Aussage.

Definition der \(NP\)-Vollständigkeit

Wir führen den wichtigen Begriff der \(NP\)-Vollständigkeit ein, der in der theoretischen Informatik und der Algorithmik eine fundamentale Bedeutung hat.

Da wir dies nun formal definiert haben, können wir den folgenden wichtigen Satz beweisen:

 
Der letzte Satz rechtfertigt nun gerade die Aussage, dass ein Problem in \(NPC\) (also ein \(NP\)-vollständiges Problem) höchstwahrscheinlich nicht effizient lösbar ist (also in \(P\) ist). Dann würde nämlich \(P = NP\) gelten und damit wären alle Probleme in \(NP\) (darunter auch all die komplizierten aus \(NPC\)) effizient lösbar (in \(P\)), was aller Erfahrung widersprechen würde.

Wir betonen noch einmal, dass es sehr gute Gründe gibt, \(P \not= NP\) anzunehmen und dass es daher eine sehr starke Aussage ist, wenn man sagt, dass ein bestimmter Sachverhalt nur gilt, wenn \(P = NP\) ist. Der Sachverhalt kann dann praktisch ausgeschlossen werden. Trotzdem ist es nicht sicher, dass \(P = NP\) gilt. Man ist sich in dieser Hinsicht allerdings so sicher, dass teilweise Sicherheitsprotokolle auf dieser Annahme basieren.

Unser Ziel ist es nun Probleme als \(NP\)-Vollständig nachweisen zu können. Wir könnten dann immer versuchen einen schnellen Algorithmus für ein neues Problem zu finden und, sollte dies nicht klappen, versuchen zu zeigen, dass das Problem \(NP\)-vollständig ist. Gelingt letzteres, können wir im Allgemeinen aufhören zu versuchen einen schnellen Algorithmus zu finden (und können beginnen andere Ansätze zu verfolgen, z.B. Algorithmen entwickeln, die nur eine fast optimale Lösung liefern und ähnliches). Um dies zu erreichen, zeigen wir zunächst noch zwei weitere wichtige Sätze (mit den obigen sind es dann drei wichtige). Der erste Satz sagt uns etwas über die Transitivität von \(\leq_p\), was man auch interpretieren kann als eine Hintereinanderausführung von Reduktionsalgorithmen. Der zweite Satz sagt uns darauf aufbauend etwas darüber, wie Probleme als \(NP\)-vollständig nachgewiesen werden können.

Aus dem letzten Satz lässt sich ein Verfahren ableiten, wie vorgegangen werden kann, wenn man von einem neuen Problem \(L\) zeigen will, dass es \(NP\)-vollständig ist.

1. Zeige \(L \in NP\).
2. Wähle ein \(L‘ \in NPC\) aus.
3. Gib einen Algorithmus an, der ein \(f\) berechnet, das jede Instanz
   \(x \in \{0,1\}^*\) von \(L‘\) auf eine Instanz \(f(x)\) von \(L\) abbildet (also eine Reduktion).
4. Beweise, dass \(f\) die Eigenschaft \(x \in L‘\) gdw. \(f(x) \in L\)
   für jedes \(x \in \{0,1\}^*\) besitzt.
5. Beweise, dass \(f\) in Polynomialzeit berechnet werden kann.

Hierbei zeigen die letzten drei Punkte \(L‘ \leq_p L\). Mit dem letzten Satz folgt daraus und aus den ersten beiden Punkten dann \(L \in NPC\).

Das Problem ist nun, dass, um im zweiten Schritt des Verfahrens ein \(L‘ \in NPC\) auswählen zu können, man erstmal welche haben muss! Je mehr man hier kennt, desto besser ist es später, aber ein erstes brauchen wir und dort werden wir tatsächlich alle Probleme aus \(NP\) auf dieses reduzieren müssen! (Denn für das erste Problem können wir obiges Verfahren noch nicht anwenden, da der zweite Schritt nicht möglich ist.)

Als erstes \(NP\)-vollständige Problem nehmen wir das auch historisch erste \(NP\)-vollständige Problem nämlich das Erfüllbarkeitsproblem der Aussagenlogik \(\texttt{SAT}\) (für Satisfiability).

Hat man nun erstmal ein \(NP\)-vollständiges Problem, so kann man (dem Plan oben entsprechend) nun dieses benutzen, um weitere Probleme als \(NP\)-vollständig nachzuweisen. Der umständliche Weg \emph{alle} \(NP\)-Probleme auf ein neues zu reduzieren entfällt so (bzw. man kriegt dies insb. wegen der Transitivität von \(\leq_p\) geschenkt). Je größer dann der Vorrat an \(NP\)-vollständigen Problemen ist, desto größer ist die Auswahl an Problemen, von denen man eine Reduktion auf ein neues Problem, dessen Komplexität noch unbekannt ist, versuchen kann. (Es gibt natürlich immer die Möglichkeit alle Probleme aus \(NP\) auf ein neues zu reduzieren, aber i.A. wird dies nicht gemacht, sondern wie im Verfahren oben beschrieben vorgegangen.)

Wir wollen neben \(\texttt{SAT}\) noch zwei weitere Probleme als \(NP\)-vollständig voraussetzen. Die Beweise finden sich wieder im Buch von Hopcroft, Ullman und Motwani.

Neben den eben betrachten \(\texttt{Clique}-\) und \(\texttt{Big-Clique}\)-Problem sind auch die anderen im letzten Abschnitt eingeführten \(NP\)-Probleme, das Mengenpartitonsproblem, das Teilsummenproblem und das Färbungsproblem alle \(NP\)-vollständig. Daneben gibt es noch tausende weitere und für keines dieser Probleme ist ein effizienter Algorithmus (d.h. ein Algorithmus, der in Polynomialzeit läuft) bekannt. Dies bestärkt uns in dem Glauben, dass ein Nachweis von \(L \in NPC\) bedeutet, dass \(L\) nicht in \(P\) liegt. Denn wäre es in \(P\), würden all die tausenden von Probleme, für die kein effizienter Algorithmus gefunden werden konnte, plötzlich in \(P\) sein.

Daher kann man nun, gegeben ein Problem für das man einen Algorithmus entwickeln will, dies zunächst versuchen. Fallen einem aber nach einiger Zeit und etlichem Nachdenken stets nur Algorithmen ein, die \emph{im Prinzip den ganzen Suchraum durchgehen}, so ist das Problem vermutlich \(NP\)-vollständig (oder schlimmer). Dies kann man dann versuchen nachzuweisen. Gelingt dies, kann man die Suche nach einem effizienten Algorithmus zugunsten von anderen Ansätzen verwerfen. Möglichkeiten diese Probleme dennoch zu attackieren sind z.B. Einschränkungen der Eingabe zu betrachten (vielleicht braucht man ja nur mit Bäumen zu arbeiten statt mit allgemeinen Graphen), Approximationsalgorithmen zu entwickeln (mit denen man i.A. nicht das Optimum ermittelt, aber vielleicht einen Wert, der gut genug ist), randomisierte Algorithmen zu entwickeln (die manchmal kein Ergebnis liefern) oder Heuristiken zu entwickeln (bei denen sowohl die Laufzeit als auch die Güte des Ergebnisses meist unklar sind). Diese Möglichkeiten sind Inhalt von weiterführenden Veranstaltungen zur Algorithmik.