Spickzettel
Inhaltsverzeichnis |
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
| | | Negation | Konjunktion | Disjunktion | Subjunktion | Bijunktion | |
| | | nicht | und | oder | wenn ... dann ... | ... genau dann, wenn ... | |
| | A | B | \lnot A | A \land B | A \lor B | A \rightarrow B | A \leftrightarrow B |
| | w | w | f | w | w | w | w |
| | w | f | f | f | w | f | f |
| | f | w | w | f | w | w | f |
| | f | f | w | f | f | w | w |
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
Algorithmen
Ein Algorithmus ist:
- ein schrittweise ablaufendes Verfahren
- das Eingabedaten zu Ausgabedaten transformiert
- au eine Klasse von Problemen anwendbar
- eindeutig, endlich und terminiert
Berechenbarkeit
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:
- Unzugängliches (wenigstens) für Computer
- 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
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 für jedes eingegebene Wort w aus A^* nach endlicher Zeit stoppt und entweder #t (w € M) oder #f (w € M) ausgibt.
> (chi "bin_in_M")\#t
> (chi "bin_nicht_in_M")\#f
Aufzählbarkeit
Eine Menge M \subseteq A^* heißt (rekursiv) aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion f : \mathbb{N} \mapsto M gibt, oder es gilt M = \empty Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M.
Semi-Entscheidbarkeit
Eine Menge M \subseteq A^* ist semi-entscheidbar, wenn die partielle Funktion X'_M : A^* \to { wahr } mit
X'_M (w) = wahr, wenn w€M \bot, sonst
berechenbar ist.
Sätze
Vereinigung: Die Vereinigungsmenge M_1 \cup M_2 zweier aufzählbarer Mengen M_1, M_2 \subseteq A^* ist eine aufzählbare Menge.
Durchschnitt: Die Durchschnittsmenge M_1 \cap M_2 zweier aufzählbar unendlicher Mengen M_1, M_2 \subseteq A^* ist eine aufzählbare Menge.