Exercise 2

K7

Schreiben Sie ein URM Programm für die Funktion

K8

Sei unendlich. Argumentiere:

1. ist semi-entscheidbar gdw für ein injektives t.c. .
2. ist entscheidbar gdw für ein streng monotones t.c. .

(1) ist semi-entscheidbar gdw für ein injektives t.c. .

semi-entscheidbar

Berechenbare Aufzählung (Vorlesung, Folien 16–17)

Sei . Dann ist genau dann c.e., wenn es eine surjektive und t.c. Abbildung gibt:

Proof

: Eine partielle Aufzählung erhalten

Sei p.c. mit . Definiere

dann gilt:

Außerdem:

Ein Programm für berechnet zuerst und gibt bei Terminierung aus. Also ist p.c..

Durch beschränkte Simulation total werden

Fixiere ein und ein URM-Programm für . Definiere

Simuliere höchstens Schritte; gib bei Halten die Ausgabe, sonst zurück. Nach Folien 8–9 ist primitiv-rekursiv und damit t.c..

Eingabe und Schrittzahl gemeinsam durchlaufen

Fixiere wie auf Folie 16 eine primitiv-rekursive Bijektion . Setze

Mit und ist auch t.c..

Jede Ausgabe liegt in :

Da surjektiv ist, durchläuft für alle Paare . Somit

Nach Definition liefert entweder die Ausgabe einer rechtzeitig haltenden Berechnung oder den Ersatzwert . Jede Ausgabe liegt daher in . Wegen und folgt

Jedes Element von wird ausgegeben:

Sei . Wähle , sodass innerhalb von Schritten hält, und wegen der Surjektivität von ein mit . Dann

Also , somit .

: Nach einem Auftreten suchen

Sei t.c. mit . Setze

Berechne und gib beim ersten Treffer den Index zurück. Da jeder Aufruf von terminiert, erreicht die Suche jeden vorhandenen Treffer nach endlich vielen Berechnungen; ohne Treffer läuft sie weiter. Somit ist p.c., und es gilt

Die letzten beiden Äquivalenzen verwenden die Definition des Bildes und die Voraussetzung . Also ist , somit c.e..

Laut Theorem gibt es ein mit t.c. und , d.h. haben wir eine Aufzählung:

für ganz . Definiere als

Totalität und Berechenbarkeit

Da t.c. ist, terminiert die Berechnung von . Sind bereits berechnet, so ist eine bekannte endliche Menge. Weil unendlich ist und gilt, gibt es ein mit .

Berechne und prüfe jeweils die Zugehörigkeit zu . Jeder Aufruf von und jeder Vergleich mit der endlichen Menge terminiert; ein geeigneter Index wird nach endlich vielen Aufrufen erreicht. Damit lässt sich auch berechnen. Induktiv ist überall definiert und t.c..

Injektivität

Nach Konstruktion gilt

Jede neue Ausgabe unterscheidet sich von allen bisherigen. Also ist injektiv.

Die Bildmenge ist ganz

Jede Ausgabe von liegt in , also .

Sei . Solange noch nicht ausgegeben wurde, gilt . Damit erfüllt die Suchbedingung; der kleinste geeignete Index ist also höchstens . Die Suche wählt daher nur Werte aus . Da diese Menge endlich ist und nichts wiederholt, muss erscheinen. Somit .

semi-entscheidbar

Sei t.c. und injektiv mit . Dann ist bijektiv. Setze

Die Urbildsuche ist wegen der Totalität von p.c., mit

Also ist c.e..

(2) ist entscheidbar gdw für ein streng monotones t.c. .

Per Definition von Entscheidbarkeit gilt

Mit können wir eine Aufzählung machen:

Definier als

Totalität und Berechenbarkeit

Da unendlich ist, ist insbesondere nicht leer. Die Suche nach terminiert daher. Sind bereits berechnet, so ist eine bekannte endliche Menge. Wegen der Unendlichkeit von ist auch nicht leer.

Prüfe die Kandidaten der Reihe nach mit und durch Vergleich mit . Da t.c. ist, terminiert jede Prüfung; der kleinste geeignete Kandidat wird nach endlich vielen Prüfungen gefunden. Induktiv ist damit überall definiert und t.c.. Ausgegeben werden die gefundenen Kandidaten, nicht die Werte , die nur die Zugehörigkeit zu anzeigen.

Strenge Monotonie

Bei der Wahl von ist jedes kleinere Element von bereits gewählt: Andernfalls wäre dieses kleinere Element statt das Minimum gewesen. Für gibt es wegen kein kleineres Element von . Nach der Wahl von gilt daher

Da gilt, folgt . Also ist streng monoton steigend und insbesondere injektiv.

Die Bildmenge ist ganz

Nach Definition wird nur bei ein Wert ausgegeben. Somit gilt .

Sei umgekehrt . Würde nie ausgegeben, so bliebe bei jeder Suche ein zulässiger Kandidat. Wegen der Wahl des Minimums wäre dann für alle . Die strenge Monotonie liefert jedoch induktiv

ein Widerspruch. Also erscheint jedes , und es folgt .

Sei t.c. und streng monoton mit . Da die Werte natürliche Zahlen sind, gilt

Insbesondere ist unbeschränkt: Für jedes gilt .

Man definiere als

Wegen existiert das Minimum und . Da jeder Aufruf von terminiert, endet die sequentielle Suche spätestens nach der Berechnung von . Somit ist t.c..

Die Minimalität von und die Monotonie von liefern

Daher gilt . Die Entscheidungsfunktion ist also

Da und t.c. sind, ist auch t.c., somit entscheidbar.

K9

Argumentiere: Wenn und c.e., dann gibt es disjunktive c.e. und s.d.

Hinweis: Zähle simultan und auf und gib nur wenn zum Zeitpunkt gezeigt wird und zu keinem früheren .

Solution

Für folgt aus und c.e., dass es Aufzählungen gibt:

Definiere für :

Bei gleicher Stufe hat Vorrang; bereits zugeordnete Elemente bleiben erhalten.

Die erste Zuordnung bleibt bestehen

Jede Zahl wird der Seite zugeordnet, auf der sie zuerst erscheint, und danach nicht mehr verschoben. So wird die Überschneidung aufgeteilt, ohne Elemente aus zu verlieren.

In Stufe liefern die Aufzählungen die Kandidaten und . Die Mengen und enthalten die bisherigen Zuordnungen.

• Zuerst wird verarbeitet: ist , falls , und sonst leer. Wir fügen also nur dann zu hinzu, wenn es nicht bereits zugeordnet ist.
• Danach wird verarbeitet: Es kommt nur dann zu , wenn es nicht in liegt. Hier steht bewusst die bereits aktualisierte Menge : Erscheint dieselbe neue Zahl auf beiden Seiten in derselben Stufe, erhält den Vorrang.

Beispielsweise können die ersten Stufen so aussehen:

Stufe

In Stufe wechselt keine Zahl die Seite; in Stufe wird die neue Zahl nur zugeordnet. Die Vereinigungen und sammeln schliesslich alle jemals vorgenommenen Zuordnungen.

Wir müssen nie entscheiden, ob eine Zahl später auch auf der anderen Seite erscheint. Geprüft werden nur die bereits bekannten endlichen Mengen.

Induktionshypothese

Für ein festes wird angenommen:

Induktionsanfang

Zu zeigen:

Trivialerweise gilt das.

Induktionsschritt

Unter der Induktionshypothese ist zu zeigen:

Mit folgt:

Abschluss

Setze

Nach Konstruktion gilt und . Induktiv bleiben und disjunkt, da jede Ergänzung die jeweils andere Menge ausschliesst. Beide Folgen wachsen, also gilt auch .

Die Stufen sind effektiv berechenbar. Die Suche nach einer Stufe mit bzw. semi-entscheidet daher bzw. ; beide sind c.e.. Aus der bewiesenen Stufengleichheit folgt

Die erste Gleichheit sammelt dieselben Elemente: entweder zuerst alle Stufen je Seite oder zuerst beide Seiten je Stufe. Für die zweite Gleichheit: Jedes Element von erscheint irgendwann in einer Aufzählung und wird dann zugeordnet oder liegt bereits auf der anderen Seite. Es geht also keines verloren; hinzugefügt werden nur Elemente aus .

Ist oder , genügt direkt , .

Z2

Zeigen Sie: Wenn c.e. und unendlich, dann hat eine rekursive unendliche Teilmenge.

Z3

ist nicht c.e..

Naive Mengenlehre: Das geordnete Paar

K10

Zeigen Sie:

1. Wenn , dann ist auch .
2. Wenn , dann gilt und .

Hinweis: wurde bereits in der VO gemacht und muss nicht noch einmal bewiesen werden.
Hinweis: Teil b ist sehr leicht und kann ohne Fallunterscheidung bewiesen werden. (Oder auch mit)

(1)

Sei

Zwei Mengen sind gleich, wenn

Daraus folgt, dass

Draus folgt, dass

Es folgt:

In beiden Fällen gilt . Also folgt ohne weitere Voraussetzung:

(2)

Aus folgt

und aus (1) folgt, für , dass .

Ü1

Instruction

Kann man aus

folgern, dass gelten muss? Und/Oder ? ?

Aussagenlogik

K11

Welche der folgenden Formeln sind Tautologien? erfüllbar? Geben Sie für die anderen Formeln eine äquivalente Formel in KNF an.

2. .

   (Implikationen werden von rechts nach links geklammert; ist als Abkürzung für zu lesen, NICHT als , und auch NICHT als ).

3. .

(1)

Tautologie: Nein.
Erfüllbar: Ja.

(2)

Implikationen und Negationen auflösen

Mit lösen wir alle Implikationen auf und lassen mit der Assoziativität überflüssige Klammern weg:

Den gemeinsamen Faktor zusammenfassen

Die ersten beiden Terme enthalten . Wir klammern diesen Faktor aus und stellen daneben:

In Klauseln verteilen

Nun verteilen wir die Disjunktion über die verbleibende Konjunktion:

Die Konjunktion der beiden Klauseln ist eine KNF. Jede Klausel enthält eine Variable und ihre Negation und ist daher immer wahr.

Tautologie: Ja.
Erfüllbar: Ja, unter jeder Belegung.

(3)

Tautology: Ja
Erfüllbar: Ja

(4)

Die äussere Äquivalenz auflösen

Wir kürzen die innere Formel mit ab und lösen zunächst die äussere Äquivalenz auf:

Die innere Formel und ihre Negation umformen

Für erhalten wir unmittelbar eine Konjunktion von Klauseln:

Für ziehen wir die Negation nach innen:

Die Negation in Klauseln verteilen

Die Disjunktion zweier Konjunktionen ergibt vier Klauseln. Zwei davon sind tautologisch:

In die Gesamtformel einsetzen

Nun setzen wir die Klauseln für und ein und verteilen bzw. über die Konjunktionen:

Die letzte Formel ist eine KNF: eine Konjunktion von vier Disjunktionen aus Literalen.

Tautologie: Nein, z.B. ist die Formel für falsch.
Erfüllbar: Ja, z.B. für .

Kompaktheitssatz

Erfüllbare Menge

Wir nennen eine Menge von Formeln erfüllbar, wenn es (mindestens) eine Belegung gibt, die erfüllt, d.h.

Endlich Erfüllbare Menge

Wir nennen eine Menge von Formeln endlich erfüllbar, wenn es zu jeder endlichen Teilmenge von eine Belegung gibt, die erfüllt.

K12+

Zeigen Sie: ist erfüllbar gdw endlich erfüllbar.

(Die Variablenmenge unserer Sprache ist .)
Hinweis:

• Eine Richtung ist trivial.
• Zeige: Wenn eine endlich erfüllbare Formelmenge ist, und , dann ist auch entweder oder endlich erfüllbar (oder beide).
  Meta-Hinweis: Um eine Aussage “Aus folgt ” zuz eigen, ist es oft empfehlenswert, stattdessen die Kontraposition zu zeigen, also “Wenn ” gilt, dann folgt .” Hier ist das besonders empfehlenswert, weil die Aussagen und in unserem Fall sehr ähnliche Struktur haben, und Folgerungen aus sehr leicht in Folgerungen aus übersetzt werden können.
• Nehme an sei endlich erfüllbar. Füge induktiv oder zu der Formelmenge dazu (das ergibt eine Folge von immer größer werdenden Formelmengen) wobei die endliche Erfüllbarkeit erhalten bleibt. Wenn hinzugefügt wird, definiere , ansonsten .

(1)

Nehme an, dass erfüllbar ist, d.h.:

Fixiere ein solches und sei . Trivialerweise gilt dann

(2)

Nehme an, dass endlich erfüllbar ist, d.h.:

Sei eine beliebige endliche Teilmenge. Per Definition von endlicher Erfüllbarkeit gilt dann, dass erfüllbar ist.

(2.1) Wenn

Die äquivalente Kontraposition ist

Nehme die Prämissen an, dann gilt:

Wähle solche endlichen unerfüllbaren Mengen und und entferne die jeweils hinzugefügte Formel:

Dann ist endlich. Angenommen, eine Belegung erfülle jede Formel aus . Für diese Belegung gibt es zwei Fälle:

• Falls : Wegen erfüllt nach unserer Annahme bereits alle Formeln aus ausser möglicherweise . Wegen erfüllt auch . Somit erfüllt dieselbe Belegung jede Formel aus , im Widerspruch zur Unerfüllbarkeit von .
• Falls : Wegen erfüllt nach unserer Annahme bereits alle Formeln aus ausser möglicherweise . Wegen erfüllt auch . Somit erfüllt dieselbe Belegung jede Formel aus , im Widerspruch zur Unerfüllbarkeit von .

Also ist unerfüllbar. Damit besitzt eine endliche unerfüllbare Teilmenge und ist nicht endlich erfüllbar. Die Kontraposition und somit das Lemma sind bewiesen.

(2.2) Induktion

Nehme an, dass endlich erfüllbar ist, und setze .

Induktionshypothese

Für ein fixes, beliebiges wird angenommen:

Induktionsanfang

Zu zeigen für :

Wir definieren und per Annahme ist endlich erfüllbar.

Induktionsschritt

Unter der Induktionshypothese ist zu zeigen, dass so gewählt werden kann, dass

Dies folgt unmittelbar aus Lemma (2.1) mit und der Variablen , da per Induktionshypothese endlich erfüllbar ist.

(2.3)

Sei die in (2.2) konstruierte Folge, für die gilt, dass jedes endlich erfüllbar ist. Weiters sei das im -ten Schritt gewählte Literal, sodass

Definiere die Belegung als

Zu zeigen ist nun, dass

Sei eine beliebige Formel aus . Da nur eine endliche Menge an Variablen enthählt, gibt es ein , sodass alle in vorkommenden Variable in liegen.

Man konstruiere nun eine Menge , die Formel enthält und alle Literal von , also:

Es gilt : Die Formel liegt bereits in , da , und die Literale wurden bis zum -ten Schritt in beigefügt. Weiters ist endlich, da beide Teilmenge der Vereinigung endlich sind, insbesondere:

Da endlich erfüllbar ist und , gibt es eine Belegung , die erfüllt, d.h.:

Betrachte nun den zweite Folgerung für alle . Daher gilt, dass jedes erfüllen muss, also:

• Wenn , dann muss um zu erfüllen.
• Wenn , dann muss sein um zu erfüllen.

Also folgt, dass:

Das gleiche Verhalten hat auch die Belegung , d.h.:

Somit stimmen und auf allen Variablen aus überein, also:

Da beliebig war, erfüllt die Belegung alle Formeln aus , d.h. ist erfüllbar.