Vorlesung 1: Vorbereitungen

Aussagenlogik

Aussage: Satz, der w oder f sein kann

Aussageformen: Variablen für Aussagen, deren Belegung mit w oder f erfolgen kann

Verknüpfung von Aussagen: Konstruktion zusammengesetzer Ausdrücke durch Verwendung von Junktoren

Sprache der aussagenlogischen Ausdrücke

1. Die Zeichen w und f sind aussagenlogische Ausdrücke.

2. Lateinische Kleinbuchstaben (abzählbar unendlich viele) sind aussagenlogische Ausdrücke.

3. Sind A und B aussagenlogische Ausdrücke, so sind es auch (A), \lnot A, A \land B, A \lor B, A \rightarrow B und A \leftrightarrow B

4. Keine anders konstruierten Zeichenketten sind aussagenlogische Ausdrücke.

Junktoren

Achtung!: \Rightarrow (Implikation) und \Leftrightarrow (Äquivalenz) gehören nicht zur Objektsprache, sondern sind wichtige Elemente der Metasprache!

Erfüllbar: Eine Aussagenform ist erfüllbar, wenn sie für mind. eine Belegung aller aussagenlogischen Variablen wahr ist.

Erfüllungsmenge: Alle Belegungstupel, welche die betrachtete Aussagenform wahr werden lassen.

Tautologie: Eine n-stellige Aussagenform heißt allgemeingültig oder Tautologie, wenn sie für alle 2^n Belegungen wahr ist.

To be continued...

Vorlesung 2: Berechenbarkeitsbegriff

Ein Algorithmus ist:

• ein schrittweise ablaufendes Verfahren
• das Eingabedaten zu Ausgabedaten transformiert
• au eine Klasse von Problemen anwendbar
• eindeutig, endlich und terminiert

Berechenbarkeit: Eine Funktion f ist berechenbar, wenn es einen Algorithmus gibt, der für jedes x € D_f den zugehörigen Funktionswert f(x) effektiv ermittelt.

Nicht formalisierbar bzw. nicht effizient:

1. Unzugängliches (wenigstens) für Computer
2. Praktisch Unmögliches

Cantorsches Diagonalisierungsverfahren 1. Art für Abzählbar unendliche Mengen

Cantorsches Diagonalisierungsverfahren 2. Art für Überabzählbar unendliche Mengen

Algorithmen und Programme

• Es gibt höchstens so viele Algorithmen wie Programme.
• Es gibt höchstens abzählbar unendlich viele Programme.
• Also stehen höchstens abzählbar unendlich viele Algorithmen überabzählbar unendlich vielen Wortfunktionen gegenüber.

Fazit (Kardinalzahlargument): Es gibt überabzählbar unendlich viele nicht berechenbare Funktionen bzw. unentscheidbare Prädikate.

Vorlesung 3: Entscheidbarkeit

Entscheidbarkeit

Berechenbarkeit - Funktionen

Entscheidbarkeit - Mengen

Entscheidungsverfahren stoppen in endlicher Zeit und geben wahr oder falsch zurück.

Es gibt überabzählbar viele unlösbare Probleme

Relative Entscheidbarkeit

Eine Menge M_1 ist relativ entscheidbar zu M_2 (M_1 , M_2 \subseteq A^*), wenn die ''charakteristische Funktion XM_1 , M_2 mit

XM_1 , M_2 (w
= wahr, wenn w € M_1
= falsch, wenn w € M_2 \ M_1

eine total berechenbare Funktion ist.

Absolute Entscheidbarkeit

Eine Menge M \subseteq A^* ist (absolut) entscheidbar, wenn M zu A^* relativ entscheidbar ist, d.h. wenn X_M,A^* ,kurz X_M mit

X_M (w)
= wahr, wenn w € M
= falsch, wenn w € A^* \ M

eine total berechenbare Funktion ist.

Mit anderen Worten: M ist entscheidbar, wenn es eine Prozedur chi gibt, die fur jedes eingegebene Wort w aus A� nach endlicher Zeit stoppt und entweder #t (w 2 M) oder #f (w 62 M) ausgibt. > (chi "bin_in_M")

> (chi "bin_nicht_in_M")

1. f