Metatheorie: Einführung

Zusammenfassung

Diese Lektion eröffnet die vierte und letzte inhaltliche Einheit des Kurses, die der Metatheorie gewidmet ist. Sie stellt ihre drei Lektionen und den Faden vor, der sie verbindet: Die beiden vorigen Einheiten haben über derselben Sprache zwei Begriffe dessen aufgebaut, was aus gegebenen Prämissen folgt, die Ableitung $\Gamma \vdash \varphi$ und die semantische Folgerung $\Gamma \models \varphi$ , und diese Einheit beweist, dass sie übereinstimmen, zuerst für endlich viele Prämissen (Korrektheit, Lemma von Kalmár und Vollständigkeit), dann für beliebige Prämissen (Kompaktheitssatz und starke Vollständigkeit), und bietet schließlich einen dritten Weg, die Folgerung zu entscheiden, die Resolutionsmethode, von der sie ebenfalls beweist, dass sie korrekt und vollständig ist. Sie erklärt, warum die Kompaktheit vor der starken Vollständigkeit bewiesen wird und nicht umgekehrt; sie zeigt an zwei Beispielen die Fragen, die weder die Suche nach Ableitungen noch die Wahrheitstafel für sich allein beantworten kann; sie legt fest, was aus den drei vorigen Einheiten übernommen wird, und gibt Ratschläge für ihr Studium.

Lernziele

Die Abfolge der drei Lektionen der Einheit beschreiben, erklären, welche Ergebnisse jeder Lektion die nächste verwendet, und begründen, dass die Kompaktheit durch ein semantisches Argument vor der starken Vollständigkeit bewiesen wird.
Die beiden Seiten des Kurses unterscheiden, die Ableitbarkeit $\Gamma \vdash \varphi$ , existenziell und endlich, und die semantische Folgerung $\Gamma \models \varphi$ , universell über unendlich viele Belegungen, und die Korrektheit und die Vollständigkeit in ihren drei Stufen formulieren.
Erklären, warum sich die Übereinstimmung beider Relationen nicht Fall für Fall, sondern nur mit Metatheoremen feststellen lässt, und erkennen, welche Hilfsmittel der vorigen Einheiten (Induktionen, Fallunterscheidung, Deduktionstheoreme, Koinzidenzlemma, konjunktive Formen) jeder Beweis verwenden wird.
Ableitungen über Ableitungen und semantische Argumente der Einheit lesen und dabei bei jedem Schritt unterscheiden, von welcher Relation die Rede ist, und das Studium vom Eingangstest aus planen.

Eingangstest

Bevor man die Einheit durcharbeitet, lohnt es sich, den Ausgangspunkt zu bestimmen. Dieser Test ist eine Selbstüberprüfung: Er wird nicht benotet, und sein einziger Zweck ist es, das Lernen zu leiten. Seine fünfzehn Fragen sind von zweierlei Art. Die ersten sechs betreffen, was die Einheit aus den vorigen als bekannt voraussetzt: die Definition der semantischen Folgerung und ihre Zurückführung auf die Unerfüllbarkeit, den Wert des Peirce-Pfeils, das Koinzidenzlemma, die Endlichkeit der Ableitung und die Fallunterscheidung; wer eine davon falsch beantwortet, sollte vor dem Weitergehen die Lektion wiederholen, die die Frage nennt. Die übrigen neun behandeln der Reihe nach die drei Lektionen dieser Einheit, je drei für jede. Wer nie die Metatheorie eines logischen Systems studiert hat, sollte nicht erwarten, sie richtig zu beantworten, und das macht nichts: Jede Antwort, ob richtig oder nicht, erklärt den Punkt und nennt die Lektion, die ihn behandelt. Dieselben Fertigkeiten werden am Ende, in der Lektion der Zusammenfassung, erneut gemessen.

Eingangstest

Miss vor Beginn der Einheit deinen Ausgangspunkt. Es ist eine kurze Selbsteinschätzung: Sie wird nicht benotet, und das Ergebnis wird nur in deinem Browser gespeichert.

Frage 1Aus früheren EinheitenWas bedeutet $\Gamma \models \varphi$ ?
Dass jede Belegung, die alle Formeln von $\Gamma$ erfüllt, auch $\varphi$ erfüllt.
Dass es eine Ableitung von $\varphi$ aus $\Gamma$ gibt.
Dass irgendeine Belegung zugleich $\Gamma$ und $\varphi$ erfüllt.
Dass $\varphi$ aus irgendeiner Formel von $\Gamma$ allein folgt.
Frage 2Aus früheren EinheitenWelche der folgenden Aussagen ist äquivalent zu $\Gamma \models \varphi$ ?
Dass $\Gamma \cup \{\neg\varphi\}$ unerfüllbar ist.
Dass $\Gamma \cup \{\varphi\}$ erfüllbar ist.
Dass $\Gamma \cup \{\neg\varphi\}$ erfüllbar ist.
Dass $\neg\varphi$ unerfüllbar ist.
Frage 3Aus früheren EinheitenWenn eine Belegung $v$ der Formel $\alpha$ den Wert $1$ gibt, welchen Wert gibt sie $(\alpha \downarrow \beta)$ ?
$0$ , welchen Wert auch immer $\beta$ hat.
Es hängt von $\beta$ ab: Sie hat den Wert $1$ , wenn $\beta$ den Wert $0$ hat.
$1 - v(\beta)$ .
$1$ , weil eine der Komponenten wahr ist.
Frage 4Aus früheren EinheitenDie Variablen von $\varphi$ sind $v_{2}$ und $v_{7}$ . Zwei Belegungen $v$ und $w$ geben $v_{2}$ und $v_{7}$ dieselben Werte und allen übrigen Variablen entgegengesetzte Werte. Wenn $v(\varphi) = 1$ , was lässt sich über $w(\varphi)$ sagen?
Dass $w(\varphi) = 1$ .
Nichts, weil sich $v$ und $w$ auf unendlich vielen Variablen unterscheiden.
Dass $w(\varphi) = 0$ , weil $w$ fast alle Werte von $v$ umkehrt.
Dass $w(\varphi) = 1$ nur dann, wenn $v$ und $w$ auch auf $v_{1}, \ldots, v_{6}$ übereinstimmen.
Frage 5Aus früheren EinheitenSei $\Gamma$ eine unendliche Formelmenge mit $\Gamma \vdash \varphi$ . Was lässt sich sagen?
Dass irgendeine endliche Teilmenge von $\Gamma$ die Formel $\varphi$ ableitet.
Dass $\varphi$ ein Theorem ist.
Dass die Ableitung alle Formeln von $\Gamma$ benutzt.
Nichts ohne den Kompaktheitssatz, weil $\Gamma$ unendlich ist.
Frage 6Aus früheren EinheitenMan weiß, dass $\Gamma \cup \{p\} \vdash \chi$ und dass $\Gamma \cup \{\neg p\} \vdash \chi$ . Was lässt sich mit der Fallunterscheidung schließen?
Dass $\Gamma \vdash \chi$ .
Nichts, solange man nicht weiß, ob $\Gamma$ die Formel $p$ oder die Formel $\neg p$ ableitet.
Dass $\Gamma \vdash (p \leftrightarrow \chi)$ .
Nur dass $\Gamma \cup \{p, \neg p\} \vdash \chi$ .
Frage 7Der Kalkül des Kurses ist korrekt. Was besagt diese Eigenschaft?
Dass für jede Menge $\Gamma$ gilt: Wenn $\Gamma \vdash \varphi$ , dann $\Gamma \models \varphi$ .
Dass, wenn $\Gamma \models \varphi$ , dann $\Gamma \vdash \varphi$ .
Dass es keine Formel $\varphi$ mit $\vdash \varphi$ und $\vdash \neg\varphi$ gibt.
Dass jede wahre Formel ein Theorem ist.
Frage 8Sei $v$ die Belegung, die den Wert $1$ an $p$ und den Wert $0$ an $q$ vergibt. Was besagt das Lemma von Kalmár mit den Variablen $p$ und $q$ für die Formel $(p \leftrightarrow q)$ ?
Dass $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$ .
Dass $\{p, \neg q\} \vdash (p \leftrightarrow q)$ .
Dass $\{p, q\} \vdash \neg(p \leftrightarrow q)$ .
Dass $\vdash \neg(p \leftrightarrow q)$ .
Frage 9Kann ein Deduktionssystem korrekt sein, ohne vollständig zu sein?
Ja: Der Łukasiewicz-Kalkül ohne die Regel EDN ist korrekt und leitet die Tautologie $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ nicht ab.
Nein: Korrektheit und Vollständigkeit lassen sich auseinander erschließen.
Nein: Ein Kalkül, dessen Axiome Tautologien sind, leitet alle Tautologien ab.
Ja, aber nur, wenn der Kalkül widersprüchlich ist.
Frage 10Was besagt der Kompaktheitssatz?
Dass eine Formelmenge genau dann erfüllbar ist, wenn jede ihrer endlichen Teilmengen erfüllbar ist.
Dass eine Formelmenge genau dann erfüllbar ist, wenn jede ihrer Formeln erfüllbar ist.
Dass jede unendliche Formelmenge erfüllbar ist.
Dass eine Menge erfüllbar ist, wenn irgendeine ihrer endlichen Teilmengen es ist.
Frage 11Sei $\Gamma$ eine unendliche Formelmenge mit $\Gamma \models \varphi$ . Was sichert die Kompaktheit zu?
Dass $\Gamma_{0} \models \varphi$ für irgendeine endliche Teilmenge $\Gamma_{0}$ von $\Gamma$ gilt.
Dass $\varphi$ aus irgendeiner Formel von $\Gamma$ allein folgt.
Dass $\varphi$ aus jeder endlichen Teilmenge von $\Gamma$ folgt.
Dass $\varphi$ allgemeingültig ist.
Frage 12Die erste Lektion beweist die Vollständigkeit für endliche Prämissenmengen. Warum genügt die Endlichkeit der Ableitung nicht, um sie auf eine unendliche Menge $\Gamma$ auszudehnen?
Weil die Endlichkeit von $\Gamma \vdash \varphi$ spricht und man $\Gamma \models \varphi$ hat: Nötig ist, dass sich die Folgerung, nicht die Ableitung, auf einen endlichen Teil zurückführen lässt, und das ist die Kompaktheit.
Doch, sie genügt: Wenn $\Gamma \models \varphi$ , liefert die Endlichkeit ein endliches $\Gamma_{0}$ mit $\Gamma_{0} \models \varphi$ .
Weil das Lemma von Kalmár nicht für Formeln mit unendlich vielen Variablen gilt.
Weil die Vollständigkeit für unendliche Prämissenmengen falsch ist.
Frage 13Was ist die Resolvente der Klauseln $\{p, \neg q, r\}$ und $\{q, s\}$ ?
$\{p, r, s\}$ .
$\{p, \neg q, r, q, s\}$ .
$\{p, r\}$ .
Sie haben keine Resolvente, weil sie kein Literal gemeinsam haben.
Frage 14Um durch Resolution zu entscheiden, ob $\{(p \vee q), \neg p\} \models q$ , welche Klauselmenge versucht man zu widerlegen?
$\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$ .
$\{\{p, q\}, \{\neg p\}, \{q\}\}$ .
$\{\{p, q\}, \{\neg p\}\}$ .
$\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$ .
Frage 15Lässt sich die leere Klausel $\Box$ durch Resolution aus der Menge $\{\{p, q\}, \{\neg p, \neg q\}\}$ herleiten?
Nein: Die Menge ist erfüllbar, und die Resolution ist korrekt.
Ja, in einem einzigen Schritt, indem man beide komplementären Paare zugleich eliminiert.
Ja, in zwei Schritten: zuerst nach $p$ und dann nach $q$ .
Nein, weil keine der beiden Klauseln eine Einheitsklausel ist.