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
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:
- 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
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