Semantik: Einführung · Topos Uranos

Zusammenfassung

Diese Lektion eröffnet die dritte Einheit des Kurses, die der Semantik gewidmet ist. Sie stellt ihre sechs Lektionen und den Faden vor, der sie verbindet, von der Fortsetzung einer Belegung auf alle Formeln bis zum Normalform-Algorithmus und zu den Schaltungen aus Schaltern; sie verortet die Einheit auf dem Weg des Kurses, nach der Deduktion, die Formeln aus anderen gewann, ohne auf ihre Bedeutung zu achten, und vor der Metatheorie, die die Ableitbarkeit $\Gamma \vdash \varphi$ mit der semantischen Folgerung $\Gamma \models \varphi$ in Beziehung setzen wird; sie erklärt, warum eine einzige Klausel, die des primitiven Junktors, genügt, um der ganzen Sprache Bedeutung zu geben, und warum die Wahrheitswerte mit Polynomen berechnet werden; sie zeigt mit einer Tafel aus vier Zeilen, was die Semantik entscheidet, ohne Ableitungen zu suchen oder Markierungen zu erfinden; sie legt fest, was aus den vorigen Einheiten übernommen wird, und gibt Ratschläge für ihr Studium.

Lernziele

Die Abfolge der sechs Lektionen der Einheit beschreiben und erklären, welche Ergebnisse jeder Lektion die nächste verwendet.
Die Semantik im Verlauf des Kurses verorten, die semantische Folgerung $\Gamma \models \varphi$ von der Ableitbarkeit $\Gamma \vdash \varphi$ unterscheiden und erklären, was die Korrektheit und die Vollständigkeit besagen werden.
Erklären, warum die Zweiwertigkeit und die Wahrheitsfunktionalität es erlauben, allen Formeln mit einer einzigen Klausel Bedeutung zu geben, und mit einer Wahrheitstafel entscheiden, ob ein Schlussschema gültig ist.
Erkennen, was die Einheit aus den vorigen übernimmt, die Zeichen $=$ , $\eqsem$ , $\dashv\vdash$ , $\leftrightarrow$ und $\Leftrightarrow$ unterscheiden 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 vier betreffen, was die Einheit aus der ersten als bekannt voraussetzt: die Definition durch Rekursion und die eindeutige Lesbarkeit, die offiziellen Abkürzungen, die Fälle einer Induktion über die Komplexität und die Substitution einer Teilformel; wer eine davon falsch beantwortet, sollte vor dem Weitergehen die Lektion wiederholen, die die Frage nennt. Die übrigen elf behandeln der Reihe nach die sechs Lektionen dieser Einheit: zwei die erste, zwei die zweite, eine die dritte und je zwei jede der drei letzten. Wer nie die Semantik einer formalen Sprache 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 EinheitenEine Funktion auf den Formeln wird definiert, indem man ihren Wert an jeder Variablen angibt und eine Regel, die den Wert von $\sigI\varphi\psi$ aus $\varphi$ , aus $\psi$ und aus den Werten beider berechnet. Was garantiert, dass so genau eine Funktion definiert ist?
Die eindeutige Lesbarkeit: Jede zusammengesetzte Formel zerfällt auf nur eine Weise in ihre Anfangsscheibe und ihre beiden Komponenten.
Dass die Regel stets $0$ oder $1$ liefert.
Nichts: Man müsste den Wert Formel für Formel prüfen, und da es unendlich viele sind, ist das nicht möglich.
Dass auch die Abkürzungen $\neg$ , $\vee$ und $\wedge$ eindeutig lesbar sind.
Frage 2Aus früheren EinheitenWelche Formel ist, mit den offiziellen Abkürzungen des Kurses, $(\varphi \vee \varphi)$ ?
Dieselbe Zeichenkette wie $\neg\neg\varphi$ .
$\varphi$ selbst, wegen der Idempotenz.
$(\varphi \downarrow \varphi)$ .
Keine: Eine Disjunktion verlangt zwei verschiedene Formeln.
Frage 3Aus früheren EinheitenWelche Fälle muss man behandeln, um durch Induktion über die Komplexität zu beweisen, dass alle Formeln eine gewisse Eigenschaft haben?
Die Variablen und die einzige Bildungsregel, $\sigI\varphi\psi$ , das heißt $(\varphi \downarrow \psi)$ .
Die Variablen, die Negation, die Konjunktion und die Disjunktion.
Nur die Regel $(\varphi \downarrow \psi)$ : Die Variablen sind ein Sonderfall.
Die Variablen und die sechs Junktoren $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ und $\veebar$ .
Frage 4Aus früheren EinheitenWenn man nach der Definition der Lektion über die Induktion die Formel $\alpha$ durch die Formel $\beta$ in $\varphi$ substituiert, welche Vorkommen von $\alpha$ werden geändert?
Alle ihre Vorkommen als Teilformel, gleichzeitig.
Nur das erste, wenn man die Zeichenkette von links nach rechts liest.
Nur die, die man in der abgekürzten Schreibweise sieht.
Die von $\alpha$ und danach die, die in den Kopien von $\beta$ auftreten.
Frage 5Eine Belegung gibt $p$ den Wert $0$ und $q$ den Wert $1$ . Wenn $(\varphi \downarrow \psi)$ genau dann den Wert $1$ hat, wenn $\varphi$ und $\psi$ den Wert $0$ haben, welchen Wert nimmt die Formel $(p \downarrow (q \downarrow p))$ an?
$1$ .
$0$ , weil $q$ den Wert $1$ hat.
Er lässt sich nicht berechnen, ohne die Werte der übrigen Variablen zu kennen.
Er hängt davon ab, wie man die Komponenten gruppiert.
Frage 6Was bedeutet $\not\models \varphi$ ?
Dass eine Belegung $\varphi$ den Wert $0$ gibt: $\varphi$ ist nicht allgemeingültig.
Dass $\varphi$ eine Kontradiktion ist.
Dass keine Belegung $\varphi$ erfüllt.
Dass $\varphi$ im Kalkül des Kurses nicht ableitbar ist.
Frage 7Man weiß, dass $\Gamma \cup \{\varphi\} \models \psi$ : Jede Belegung, die $\Gamma$ und $\varphi$ erfüllt, erfüllt $\psi$ . Was folgt daraus?
$\Gamma \models (\varphi \rightarrow \psi)$ .
$\Gamma \models \psi$ .
$\Gamma \models (\psi \rightarrow \varphi)$ .
$\models (\varphi \rightarrow \psi)$ .
Frage 8Die Formel $(v_{1} \vee \neg v_{1})$ ist allgemeingültig. Welche der folgenden Formeln ist nach dem Satz von der uniformen Substitution allgemeingültig?
$(\neg v_{2} \vee \neg\neg v_{2})$ .
$(v_{1} \vee \neg v_{2})$ .
$(\neg v_{2} \vee \neg v_{3})$ .
Keine: Die uniforme Substitution erlaubt nur, Variablen durch andere Variablen zu substituieren.
Frage 9Welche Formel bezeichnet nach der Konvention des Kurses der Ausdruck $v_{1} \wedge v_{2} \wedge v_{3}$ , ohne Klammern geschrieben?
$((v_{1} \wedge v_{2}) \wedge v_{3})$ .
$(v_{1} \wedge (v_{2} \wedge v_{3}))$ .
Beide Gruppierungen, weil sie dieselbe Zeichenkette sind.
Keine: Ohne Klammern bezeichnet der Ausdruck nichts.
Frage 10Eine Wahrheitsfunktion mit zwei Argumenten ordnet einen Wert, $0$ oder $1$ , jeder der vier Zeilen $(1, 1)$ , $(1, 0)$ , $(0, 1)$ und $(0, 0)$ zu. Wie viele Wahrheitsfunktionen mit zwei Argumenten gibt es?
Frage 11Kann eine nur mit $\wedge$ und $\vee$ aus den Variablen geschriebene Formel den Wert $0$ unter der Belegung haben, die allen Variablen $1$ gibt?
Nein: Jede nur mit $\wedge$ und $\vee$ geschriebene Formel hat unter dieser Belegung den Wert $1$ .
Ja, wenn man genügend Konjunktionen und Disjunktionen verschachtelt.
Ja: Da der Peirce-Pfeil allein genügt, genügen auch die Konjunktion und die Disjunktion.
Das lässt sich nicht wissen, ohne die Tafel jeder Formel zu schreiben.
Frage 12Ein Literal ist eine Variable oder die Negation einer Variablen. Welche der folgenden Formeln ist ein Literal?
$\neg v_{2}$ .
$\neg\neg v_{1}$ .
$(v_{1} \wedge v_{2})$ .
$\top$ .
Frage 13Ist die konjunktive Normalform $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ allgemeingültig?
Nein: Die zweite Klausel enthält kein komplementäres Paar, und die Belegung, die $0$ an $v_{3}$ und $1$ an $v_{2}$ gibt, widerlegt sie.
Ja: Die erste Klausel enthält ein komplementäres Paar, und eine genügt.
Ja, weil sie erfüllbar ist.
Das lässt sich ohne eine Tafel mit acht Zeilen nicht entscheiden.
Frage 14Um eine Formel in disjunktive Normalform zu bringen, distribuiert man die Konjunktion über die Disjunktion. Welche ist die richtige Regel?
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$ .
Frage 15Eine Schaltung hat zwei direkte Schalter, der Hebel $p$ und $q$ , in Reihe verbunden, und dieser Block liegt parallel zu einem direkten Schalter des Hebels $r$ . Welche Formel sagt, wann sie leitet?
$((p \wedge q) \vee r)$ .
$((p \vee q) \wedge r)$ .
$((p \wedge q) \wedge r)$ .
$((p \vee q) \vee r)$ .