Exercise 3

Nochmal Berechenbarkeit

K13

Zeige: Es gibt eine unendliche Menge , die keine unendliche semi-entscheidbare Teilmenge hat.

Hinweis: Das hat eigentlich nichts mit semi-entscheidbar zu tun. Benötigt wird nur: Es gibt nur abzählbar viele unendliche semi-entscheidbare Mengen. Nimm mit und setze fest: und . Sei bis zu einem bereits fixiert. Wähle mit etc.

Alternativer Hinweis (einfacher? schwieriger?): Jede endliche Menge von natürlichen Zahlen lässt sich durch eine einzige natürliche Zahl kodieren, z.B. durch

(Oder, wenn Ihnen das lieber ist, durch .) Sei eine nicht-c.e. Menge, und sei die Menge aller (Codes von) Anfangsabschnitten dieser Menge. Jede unendliche Teilmenge von berechnet ganz und damit auch .

Solution

Es gibt höchstens abzählbar viele unendliche semi-entscheidbare Teilmengen von .

Warum sind es höchstens abzählbar viele?

Für die universelle partiell berechenbare Funktion gilt:

Für jede semi-entscheidbare Menge gilt:

Die Liste enthält somit alle semi-entscheidbaren Mengen, möglicherweise mehrfach. Ihre unendlichen Elemente bilden eine höchstens abzählbare Teilmenge. Wir benötigen keinen Algorithmus, der entscheidet, welche dieser Mengen unendlich sind.

Sei

eine Liste aller unendlichen semi-entscheidbaren Teilmengen von .

Wahl der Zahlen und

Wähle mit ; das ist möglich, da unendlich ist. Für ist bereits gewählt. Aus entfernen wir alle Zahlen bis einschliesslich :

Da ausserhalb der entfernten Zahlen liegt:

Setze und . Beide liegen in und sind grösser als :

Somit erhalten wir

Konstruktion von

Definiere

Für jedes wurde ein gewählt. Da unendlich ist und die paarweise verschieden sind, enthält unendlich viele Elemente:

Die strenge Ordnung garantiert:

Somit ist unendlich.

Keine unendliche semi-entscheidbare Teilmenge

Angenommen, sei unendlich und semi-entscheidbar. Dann:

Widerspruch zu . Also besitzt keine solche Teilmenge.

Aussagenlogik

Aussagenlogische Belegungen

K14

Wahrheitstabellen bieten eine Methode/einen Algorithmus, um zu entscheiden, ob eine Formel eine Tautologie ist.

1. Wenn die Formel verschiedene Aussagenvariablen enthält, wie viele Zeilen hat die komplette Wahrheitstabelle?

2. Wie viele dieser Zeilen reichen aus, um zu beweisen, dass die Formel erfüllbar ist (vorausgesetzt, sie ist erfüllbar)? Dasselbe für „Tautologie“, „nicht erfüllbar“ und „nicht Tautologie“ statt „erfüllbar“.

Bemerkung

„Erfüllbar“ ist „nichtdeterministisch polynomiell“ („NP“): Wenn wir glücklich raten können, können wir in polynomieller Zeit beweisen, dass eine Formel erfüllbar ist. „Erfüllbar“ ist sogar NP-vollständig; daher ist eine der vielen äquivalenten Formulierungen des -Problems:

Gibt es einen (deterministischen) Algorithmus, der in polynomieller Zeit entscheidet, ob eine Formel erfüllbar ist?

(1)

Jede Zeile entspricht einer Belegung der Variablen. Für jede Variable gibt es zwei mögliche Wahrheitswerte, unabhängig von den anderen:

(2)

Sei eine Belegung und der Wahrheitswert der Formel in der zugehörigen Zeile. Wir betrachten, wie viele Zeilen man anhand ihrer Wahrheitswerte überprüfen muss.

Erfüllbar

Eine einzige Zeile mit Wert genügt:

Diese Belegung zeigt unmittelbar, dass die Formel wahr sein kann.

Tautologie

Jede Belegung muss die Formel erfüllen. Daher müssen alle Zeilen den Wert zeigen:

Bleibt eine Zeile ungeprüft, könnte die Formel dort noch falsch sein.

Nicht erfüllbar

Keine Belegung darf die Formel erfüllen. Daher müssen alle Zeilen den Wert zeigen:

Bleibt eine Zeile ungeprüft, könnte die Formel dort noch wahr sein.

Keine Tautologie

Eine einzige Zeile mit Wert genügt:

Diese Belegung ist ein Gegenbeispiel zur Behauptung, dass die Formel immer wahr ist.

Andere Beweise können die Struktur der Formel ausnutzen; die Angaben beziehen sich auf das Überprüfen der Zeilen der Wahrheitstabelle.

K15

Sei . Wie viele Belegungen (der Variablen ) erfüllen die Formel

Solution

Sei die gegebene Formel und eine Belegung mit . Die zugehörige Auswertung von Formeln bezeichnen wir mit . Für jede Implikation gilt:

Sobald eine Variable wahr ist, müssen also alle folgenden wahr sein. Nach einer falschen Variable sind beide Werte möglich:

Gezählt werden die Pfade, nicht die Knoten. Wegen der obigen Ordnung besteht jede erfüllende Belegung aus falschen, gefolgt von wahren Werten:

Die Zahl bestimmt die Belegung eindeutig: Die ersten Variablen sind falsch, alle weiteren wahr. Zum Beispiel:

Jede erfüllende Belegung erscheint genau einmal in dieser Liste. Es gibt eine Belegung für jedes und damit:

Ü2

Ü2

Sei gross, . Geben Sie eine Formel (in den Variablen ) an, die von genau Belegungen erfüllt wird.

Z5

Versuchen Sie, eine möglichst kleine Formel zu finden (mit etwa Symbolen).

Eine Anwendung des aussagenlogischen Kompaktheitssatzes

Graph und Teilgraph

Ein (ungerichteter) Graph ist eine Menge (nicht notwendigerweise endlich!) von „Knoten“ und eine Menge von „Kanten“, wobei eine Kante je zwei Knoten verbindet. Formal ist eine Kante eine Menge von zwei Knoten.

Ein Teilgraph von besteht aus einer Teilmenge der Knoten, wobei je zwei genau dann verbunden sind, wenn sie im ursprünglichen Graph verbunden waren. Formal:

Hier bezeichnet „Teilgraph“ also einen induzierten Teilgraphen.

Färbbarkeit

Ein Graph heisst -färbbar, wenn man seine Knoten mit höchstens Farben färben kann, sodass zwei benachbarte (= verbundene) Knoten immer verschiedene Farben haben.

Wir nennen den Graphen endlich färbbar, wenn es ein gibt, sodass -färbbar ist.

Abzählbarer Graph

Wir nennen abzählbar, wenn die Menge (höchstens) abzählbar ist, also entweder endlich ist oder sich bijektiv auf abbilden lässt.

K16+

1. Zeigen Sie: Der abzählbare Graph ist -färbbar gdw jeder endliche Teilgraph von -färbbar ist.

   Hinweis: Benutze K12, den Kompaktheitssatz für die Aussagenlogik. Übersetze „ ist -färbbar“ in eine Menge von Formeln.

2. Gilt auch: Ein Graph ist endlich färbbar gdw jeder endliche Teilgraph endlich färbbar ist?

   (Bemerkung: Man kann natürlich auch eine unendliche Aussagenlogik definieren, die unendliche (z.B. abzählbare) Formeln zulässt, wobei z.B. wahr ist gdw jedes wahr ist. Wir sehen also, dass diese Logik keinen Kompaktheitssatz hat.)

Bemerkung

Dasselbe gilt auch für beliebige Graphen, dann benötigt man Z4.

(1)

Sei .

Sei eine gültige Färbung. Für jeden endlichen Teilgraphen gilt:

Also ist ebenfalls -färbbar.

Sei jeder endliche Teilgraph von -färbbar. Für jedes und verwenden wir ein eigenes Atom und setzen direkt:

Da abzählbar ist, genügen abzählbar viele Atome.

Warum genügen abzählbar viele Atome?

Für jeden Knoten benötigen wir genau Atome. Ist endlich, sind es insgesamt Atome. Andernfalls schreibe :

Jede Zeile ist endlich. Daher können wir alle Atome zeilenweise aufzählen:

Die Menge der Atome ist also höchstens abzählbar.

Sei endlich und die Menge der darin erwähnten Knoten. Dann:

Dabei bezeichnet den induzierten Teilgraphen auf . gibt die Bedingungen vor; liefert die Farben. Wir übersetzen:

Definiere dazu:

Zweiter Fall

Für , und gilt:

Auch Atome, die keinem Paar aus entsprechen, erhalten den Wert .

Diese Belegung erfüllt die Formeln aus :

Damit gilt für die beliebige endliche Teilmenge :

Somit:

Sei nun eine Belegung, die ganz erfüllt. Wir benötigen noch eine Färbung . Für jeden Knoten gilt:

Es können mehrere Atome wahr sein. Wähle für jeden Knoten die kleinste mögliche Farbe:

Für benachbarte Knoten wäre eine gemeinsame Farbe unmöglich:

im Widerspruch zu . Also ist eine gültige -Färbung von .

(1) — Alternative: über zwei Äquivalenzen

Zu zeigen für den abzählbaren Graphen :

Kompaktheitssatz

Übersetzung in Klauseln

Sei . Für jedes Paar verwenden wir ein eigenes Atom:

Da abzählbar und endlich ist, benötigen wir nur abzählbar viele Atome.

Jeder Knoten bekommt mindestens eine Farbe:

Benachbarte Knoten bekommen keine gemeinsame Farbe:

Insgesamt:

Mehrere wahre Farbatome pro Knoten sind erlaubt. Für eine Färbung genügt es, jeweils eine dieser Farben auszuwählen; benachbarte Knoten können dabei nicht dieselbe Farbe erhalten.

Noch zu zeigen

Wenn erfüllbar ist, existiert eine Belegung mit:

Sei diese Belegung. Für jeden Knoten gilt:

Wähle jeweils eine der möglichen Farben:

Für jede Kante gilt:

Angenommen, zwei Nachbarn hätten dieselbe Farbe:

Widerspruch. Also:

Damit ist eine gültige -Färbung von .

Sei eine gültige -Färbung:

Definiere die Belegung durch

Alle übrigen Atome erhalten den Wert .

Für jeden Knoten gilt:

Für jede Kante und jedes gilt:

Damit:

Sei mit . Betrachte die zugehörigen Klauseln:

Dann gilt:

Somit:

Da beliebig war, gilt dies für jeden endlichen Teilgraphen von .

Sei endlich. Sammle alle Knoten, deren Atome in vorkommen:

Dann:

Betrachte den induzierten Teilgraphen und seine Klauselmenge:

Jede Klausel aus gehört zu einem solchen Knoten oder einer solchen Kante, also . Somit:

Da beliebig endlich war, ist endlich erfüllbar.

Insgesamt folgt mit dem Kompaktheitssatz:

(2)

Unterschied zu (1)

Die rechte Seite beider Aussagen unterscheidet sich in der Wahl von :

In (1) ist für alle Teilgraphen gleich; in (2) darf auf der rechten Seite von abhängen.

Die Rolle von in (1)

Für (1) wählen wir zuerst ein beliebiges, festes . Erst danach betrachten wir alle endlichen Teilgraphen:

Für zwei beliebige endliche Teilgraphen und bedeutet die rechte Seite insbesondere:

Beide Färbungen verwenden dasselbe ; die gewählten Funktionen und müssen nicht übereinstimmen.

In (2) kann dagegen jeder Teilgraph seine eigene Schranke haben; eine gemeinsame Schranke folgt daraus nicht.

Nein. Die Hinrichtung gilt durch Einschränken einer Färbung. Gegenbeispiel zur Rückrichtung:

Je zwei verschiedene Knoten sind benachbart.

Voraussetzung erfüllt: Jeder endliche Teilgraph ist endlich färbbar

Sei endlich, mit . Weise jedem Knoten eine eigene Farbe zu:

Die Farbschranke hängt von und damit vom gewählten Teilgraphen ab; sie ist nicht für alle Teilgraphen gleich.

Für wählen wir als Farbmenge, ohne eine Farbe zu verwenden: ist die leere Funktion. So müssen wir nicht voraussetzen, dass Farben zugelassen sind.

Für jede Kante gilt:

Im leeren Fall gilt insbesondere:

Der leere Graph ist also ebenfalls -färbbar.

Schlussfolgerung falsch: ist nicht endlich färbbar

Wir nehmen zum Widerspruch an:

Nach Definition bedeutet das:

Wir fixieren ein solches und eine solche Färbung . Dabei ist unendlich, aber die Farbmenge endlich. Für alle Knoten zusammen stehen also nur diese Farben zur Verfügung:

Eine Färbung könnte dagegen unendlich viele Farben verwenden. Zum Beispiel ist eine gültige Färbung unseres Graphen, aber keine Färbung mit einer endlichen Farbmenge .

Dann ist auch jeder Teilgraph mit diesen Farben färbbar. Betrachte den Teilgraphen auf den ersten Knoten:

Für sind dies vier paarweise benachbarte Knoten und drei verfügbare Farben:

Dieser Teilgraph ist endlich färbbar, aber nicht mit nur Farben. Damit widerlegt er die angenommene -Färbbarkeit von .
Für die angenommene Färbung müsste gelten:

Widerspruch. Also genügt keine endliche Anzahl von Farben für .

Zur Bemerkung: Kompaktheit und der Graph aus (2)

Sei der obige vollständige Graph auf . Das Atom bedeutet wieder: Knoten hat Farbe . Wir lassen abzählbare Konjunktionen und Disjunktionen zu und setzen:

Die erste Menge enthält eine unendliche Formel: Ein muss für alle Knoten funktionieren.

Jede endliche Teilmenge ist erfüllbar

Sei endlich. Ihre endlich vielen Kantenklauseln erwähnen nur endlich viele Knoten. Weise diesen Knoten paarweise verschiedene Farben zu und allen übrigen Knoten Farbe .

Es werden insgesamt nur endlich viele Farben verwendet. Daher ist die unendliche Formel wahr, falls sie in liegt. Auch jede Kantenklausel in ist wahr: Ihre beiden Knoten haben verschiedene Farben. Somit ist erfüllbar.

Die ganze Menge ist nicht erfüllbar

Angenommen, eine Belegung erfüllt . Dann liefert die unendliche Formel ein festes , sodass jeder Knoten mindestens eine Farbe aus hat. Wähle für jeden Knoten eine solche Farbe. Die Kantenklauseln verhindern, dass zwei benachbarte Knoten dieselbe gewählte Farbe haben:

Das widerspricht dem obigen Gegenbeispiel: ist nicht endlich färbbar.

Jede endliche Teilmenge ist also erfüllbar, selbst aber nicht. Damit scheitert Kompaktheit in dieser unendlichen Aussagenlogik.

Zur Bemerkung: Einfacheres Gegenbeispiel zur Kompaktheit

Wir lassen abzählbare Disjunktionen als Formeln zu und betrachten:

Jede endliche Teilmenge ist erfüllbar

Sei endlich. Da nur endlich viele Negationen enthält, gibt es ein mit . Setze:

Die Disjunktion und alle Negationen in sind damit wahr. Also ist erfüllbar.

Die ganze Menge ist nicht erfüllbar

Das widerspricht der Forderung, auch die Disjunktion in zu erfüllen.

Somit ist jede endliche Teilmenge von erfüllbar, aber selbst nicht. Der Kompaktheitssatz gilt daher für diese unendliche Aussagenlogik nicht. Dies ist ein separates Gegenbeispiel zur Bemerkung, nicht das graphentheoretische Gegenbeispiel zu (2).

Aussagenlogische Resolution

Ü3

Ü3

Wir betrachten diese Formeln:

Anmerkung: „“ bindet stärker als die anderen Junktoren. Daher ist z.B. als zu lesen.

• Welche der Formeln sind in CNF (= konjunktive Normalform = Konjunktion von Klauseln), welche in DNF (= disjunktive Normalform)?
• Geben Sie zu den Formeln, die nicht in CNF sind, eine äquivalente Formel in CNF an.
• Schreiben Sie jede CNF, die Sie in dieser Aufgabe gefunden haben, als Menge von Klauseln an. (Klausel = Menge von Literalen.)

K17

1. Der besseren Lesbarkeit halber schreiben wir statt , statt , etc. Sei

   Finden Sie eine möglichst kleine Menge , die unter Resolution abgeschlossen ist.

2. Dasselbe noch einmal für die unendliche Menge

   Ausnahmsweise betrachten wir hier nicht nur , sondern auch .

   (Was heisst hier „möglichst klein“?)

(1)

Closed Under Resolution

Initialisierung

Resolution über

Keine Klausel enthält , also gibt es keine Resolution über :

Resolution über

Die einzige Resolution über ergibt:

Wir fügen diese Klausel hinzu:

Resolution über

In enthalten zwei Klauseln und zwei Klauseln . Ihre Resolventen sind:

Nach dem Hinzufügen dieser Klauseln:

Resolution über

Keine Klausel enthält . Daher gibt es keine Resolution über :

Abgeschlossenheit

Wir prüfen erneut: Für und gibt es weiterhin keine Resolventen. Für ergeben sich genau die vier bereits berechneten Klauseln, und alle liegen in .

Für gibt es nun zwei weitere Klauseln mit . Alle Resolventen über sind:

Alle möglichen Resolventen liegen somit bereits in : Die Menge ist unter Resolution abgeschlossen.

Minimalität

Resolutionsabschluss

heisst Resolutionsabschluss von .

• Obermenge: enthält alle Klauseln aus .
• Abgeschlossenheit: Jeder definierte Resolvent von Klauseln aus liegt wieder in .
• Minimalität: Jede abgeschlossene Obermenge von enthält : „Kleinste“ bezieht sich auf die Inklusion .

Im Satz ist die kleinste unter Resolution abgeschlossene Obermenge von . steht dort für eine beliebige abgeschlossene Obermenge von ; insbesondere gilt . In unserer Rechnung ist der Kandidat für :

Wir prüfen die drei Eigenschaften:

Jeder Schritt behält die bisherigen Klauseln:

ist abgeschlossen

Nach der obigen Prüfung liegen alle Resolventen von Klauseln aus wieder in .

ist die kleinste abgeschlossene Obermenge

Sei eine beliebige unter Resolution abgeschlossene Menge. Da jeder Schritt nur Resolventen bereits vorhandener Klauseln hinzufügt, gilt:

Setzen wir , erhalten wir . Für die andere Inklusion setzen wir im Satz . Die ersten beiden Teile zeigen, dass die Voraussetzungen erfüllt:

Zusammen:

Also ist die kleinste unter Resolution abgeschlossene Obermenge von .

Lösung (2)

Resolutionsabschluss

Die kleinste unter Resolution abgeschlossene Obermenge von ist

Obermenge

Für jedes gilt . Daher:

Abgeschlossenheit

Komplementäre Literale treten nur auf, wenn der Endindex einer Klausel der Anfangsindex der anderen ist. Für ergibt die Resolution über :

Andere Resolventen entstehen nicht. Somit ist unter Resolution abgeschlossen.

Minimalität

Sei unter Resolution abgeschlossen. Wir zeigen durch Induktion nach :

Für liegt die Klausel bereits in . Für gilt nach Induktionsannahme und wegen :

Also gilt . „Möglichst klein“ bedeutet hier: ist bezüglich der Inklusion die kleinste abgeschlossene Obermenge, nicht eine endliche Menge.

Eindeutige Lesbarkeit von aussagenlogischen Formeln

(Diese Aufgabe hat eine lange Angabe, ist aber nicht schwer.)

Aussagenlogische Formeln sind induktiv aus Variablen, und durch diverse Junktoren aufgebaut. Es ist klar, dass eine Formel „eindeutig lesbar“ ist, aber der exakte Beweis ist etwas umständlich (dafür, dass die Aussage so offensichtlich ist).

Mit „eindeutig lesbar“ ist gemeint: Sei eine aussagenlogische Formel. Dann gilt genau einer der folgenden Fälle:

• ist eine aussagenlogische Variable.
• ist .
• ist .
• ist für eine eindeutige aussagenlogische Formel .
• ist für zwei eindeutige aussagenlogische Formeln und .
• ist für zwei eindeutige aussagenlogische Formeln und .
• ist für zwei eindeutige aussagenlogische Formeln und .
• ist für zwei eindeutige aussagenlogische Formeln und .

Bemerkung

Wenn wir Formeln ohne Klammern definieren, haben wir natürlich keine Eindeutigkeit: könnte dann entweder als gelesen werden oder als .

Alternativ zu Klammern kann man auch Präfix-Notation verwenden: Aus den Formeln und kann man die Formel bilden, etc. Hier kann man analog die eindeutige Lesbarkeit zeigen.

K18

Beweisen Sie:

1. Jede aussagenlogische Formel hat gleich viele öffnende wie schliessende Klammern. Ausserdem hat jeder Anfangsteil mindestens so viele öffnende wie schliessende Klammern.

2. Kein echter Anfangsteil einer Formel ist wieder Formel.

3. Aussagenlogische Formeln sind eindeutig lesbar.

Hinweis: Induktion „nach Formelaufbau“, oder, wenn Sie das noch nicht kennen: Zeigen Sie mit Induktion nach , dass für alle Formeln der Länge gilt: (1)–(3).

(1)

Für eine Symbolfolge sei

Wir zeigen durch Induktion nach Formelaufbau:

Induktion nach Formelaufbau

Sei die obige Eigenschaft. Wir zeigen für die einfachsten Formeln und für jeden weiteren Aufbauschritt:

Jede Formel entsteht durch endlich viele solcher Schritte. Daher gilt für jede Formel.

Induktionsanfang

Für enthalten und seine Anfangsteile keine Klammern:

Induktionsschritt

Sei . Nach Induktionsannahme gilt für jede Teilformel und jeden ihrer Anfangsteile :

Ganze Formel:

Die äusseren Klammern tragen und bei; jede ganze Teilformel trägt bei:

Anfangsteile:

Der leere Anfangsteil und die ganze Formel erfüllen die Behauptung:

Für einen nichtleeren echten Anfangsteil ist die äussere öffnende Klammer enthalten, die äussere schliessende aber nicht. Je nachdem, wo endet, gilt:

Dabei dürfen und auch leer sein. Die äussere öffnende Klammer trägt bei; die Junktoren tragen bei. Nach Induktionsannahme gilt somit:

Für nichtleere echte Anfangsteile gilt also sogar . Zusammen mit folgt für jeden Anfangsteil .

(2)

Sei ein echter Anfangsteil einer Formel.

(3)

Form der Formel

Die Fälle sind am Anfang unterscheidbar:

Negation

Für die Negation:

Zwei mögliche Zerlegungen

Für zweistellige Junktoren seien zwei mögliche Zerlegungen derselben Formel gegeben; wir nehmen nicht an, dass sie verschieden sind:

Die Gleichheit bedeutet: Beide Seiten sind dieselbe Symbolfolge, nicht nur Formeln mit demselben Wahrheitswert. Die zwei Schreibweisen bezeichnen mögliche Zerlegungen dieser einen Formel.

Zerlegung von

Eine Zerlegung ist:

Gibt es eine zweite Zerlegung , so zeigen wir im Folgenden, dass auch sie , und erfüllen muss.

Wir zeigen, dass die Zerlegungen übereinstimmen:

Erste Teilformel

Beide Teilformeln beginnen unmittelbar nach der gleichen öffnenden Klammer und bestehen daher bis zum Ende der kürzeren Teilformel aus denselben Symbolen:

Wir prüfen die beiden Fälle mit (2):

Die äussere Zerlegung ist eindeutig; induktiv gilt dasselbe für die kürzeren Teilformeln.