Spickzettel
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 hoch n Belegungen wahr ist.