Deduktion: Einführung

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.

1. Frage 1Aus früheren EinheitenDie Zeichenkette $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ ist eine zusammengesetzte Formel der Form $\sigI\varphi\psi$. Welches sind ihre Komponenten $\varphi$ und $\psi$?

   $\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ und $\psi = \sigO\sigI$.

   $\varphi = \sigI\sigO\sigI$ und $\psi = \sigO\sigO\sigI\sigO\sigI$.

   Sie lässt zwei Zerlegungen zu, je nachdem, wo man die Zeichenkette nach der Anfangsscheibe schneidet.

   $\varphi$ ist die ganze Zeichenkette, die auf die Anfangsscheibe folgt, und $\psi$ ist die leere Zeichenkette.

2. Frage 2Aus früheren EinheitenIn einem Beweis durch starke Induktion, dass jede natürliche Zahl $n$ eine Eigenschaft $P(n)$ hat, was darf man beim Beweis von $P(n)$ annehmen?

   Dass $P(m)$ für jede natürliche Zahl $m$ kleiner als $n$ gilt.

   Nur dass $P(n - 1)$ gilt.

   Dass $P(m)$ für jede natürliche Zahl $m$ kleiner oder gleich $n$ gilt.

   Nichts, bevor nicht $P(1)$ und $P(2)$ getrennt bewiesen sind.

3. Frage 3Aus früheren EinheitenWelche Formel bezeichnet $(\varphi \rightarrow \psi)$ mit den offiziellen Abkürzungen des Kurses, geschrieben mit dem Peirce-Pfeil und der Negation?

   $\neg(\neg\varphi \downarrow \psi)$.

   $(\neg\varphi \downarrow \psi)$.

   $\neg(\varphi \downarrow \neg\psi)$.

   Keine bestimmte: Es hängt davon ab, wie man sich entscheidet, sie zu lesen.

4. Frage 4Das Schema A1 ist $(\varphi \rightarrow (\psi \rightarrow \varphi))$. Ist die Formel $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ eine Instanz von A1?

   Nein: Das erste und das letzte Vorkommen von $\varphi$ müssten durch dieselbe Formel substituiert werden, und hier sind es $v_{1}$ und $v_{3}$.

   Ja, mit $\varphi := v_{1}$ und $\psi := v_{2}$.

   Ja, denn jede Implikation, deren Konsequens wieder eine Implikation ist, ist eine Instanz von A1.

   Nein, denn die Instanzen eines Schemas dürfen keine Variablen enthalten.

5. Frage 5In einer Ableitung stehen bereits die Zeilen $\psi$ und $(\varphi \rightarrow \psi)$, wobei $\varphi$ und $\psi$ verschiedene Formeln sind. Welche Formel erlaubt der auf diese beiden Zeilen angewandte Modus ponens zu schreiben?

   Keine: Der Modus ponens verlangt das Antezedens $\varphi$, und was man hat, ist das Konsequens.

   $\varphi$.

   $(\psi \rightarrow \varphi)$.

   $\neg\varphi$.

6. Frage 6Man weiß, dass $\{\varphi\} \vdash \psi$, das heißt, dass es eine Ableitung von $\psi$ gibt, deren einzige Prämisse $\varphi$ ist. Was besagt dann das Deduktionstheorem?

   Dass $\vdash (\varphi \rightarrow \psi)$: Die Implikation ist ein Theorem.

   Dass $\vdash \psi$: Die Prämisse kann einfach gestrichen werden.

   Dass $\vdash (\psi \rightarrow \varphi)$.

   Dass $\{\psi\} \vdash \varphi$.

7. Frage 7Was ist ohne weitere Prämissen aus der Menge $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ ableitbar?

   $(\varphi \rightarrow \chi)$.

   $\chi$, durch zweimalige Anwendung des Modus ponens.

   $(\chi \rightarrow \varphi)$.

   $(\varphi \wedge \chi)$.

8. Frage 8Die Regel der Ersetzung der doppelten Negation (EDN) ändert in einer Zeile ein einziges Vorkommen einer Teilformel, und sie wirkt auf die Zeichenkette der Grundsprache. Wie viele Vorkommen der Teilformel $\neg v_{1}$ enthält die Zeichenkette, die $(v_{1} \rightarrow v_{2})$ bezeichnet?

   Zwei.

   Eines, das dem Antezedens entspricht.

   Keines: Die Formel enthält keine Negationen.

   Vier.

9. Frage 9Welche Formel erhält man aus $(\neg\varphi \rightarrow \psi)$ durch Kontraposition, ohne doppelte Negationen hinzuzufügen?

   $(\neg\psi \rightarrow \varphi)$.

   $(\psi \rightarrow \neg\varphi)$.

   $(\varphi \rightarrow \neg\psi)$.

   $(\neg\psi \rightarrow \neg\varphi)$.

10. Frage 10Bezeichnen $(\varphi \vee \psi)$ und $(\neg\varphi \rightarrow \psi)$ dieselbe Formel?

    Nein: Die erste ist $\neg(\varphi \downarrow \psi)$, die zweite $\neg(\neg\neg\varphi \downarrow \psi)$; es sind verschiedene Formeln, die durch Ableitung äquivalent sind.

    Ja, nach der Definition der Implikation.

    Ja, denn beide werden „$\varphi$ oder $\psi$“ gelesen.

    Nein, und auch keine ist aus der anderen ableitbar.

11. Frage 11Man weiß, dass $\varphi \dashv\vdash \varphi'$, das heißt, dass jede aus der anderen ableitbar ist. Was rechtfertigt, dass auch $\neg\varphi \dashv\vdash \neg\varphi'$?

    Ein Satz, die Ersetzung äquivalenter Formeln, der mit dem Deduktionstheorem und der Kontraposition bewiesen wird.

    Keine besondere Rechtfertigung: Es genügt, „beide Seiten“ der Äquivalenz zu negieren.

    Die Definition der Negation, denn $\neg\varphi$ ist $(\varphi \downarrow \varphi)$.

    Nichts, denn es ist nicht wahr: Die Negation kann äquivalente Formeln trennen.

12. Frage 12Aus der Prämissenmenge $\Gamma \cup \{\neg\varphi\}$ werden eine Formel $\chi$ und ihre Negation $\neg\chi$ abgeleitet. Was kann man schließen?

    Dass $\Gamma \vdash \varphi$.

    Dass $\Gamma \vdash \neg\varphi$.

    Dass aus $\Gamma$ jede beliebige Formel ableitbar ist.

    Nichts: Eine Ableitung, die zu einem Widerspruch führt, beweist nichts.

13. Frage 13Zu welcher Formel ist die Negation einer Implikation, $\neg(\varphi \rightarrow \psi)$, äquivalent?

    Zu $(\varphi \wedge \neg\psi)$.

    Zu $(\neg\varphi \rightarrow \neg\psi)$.

    Zu $(\varphi \rightarrow \neg\psi)$.

    Zu $(\neg\varphi \wedge \psi)$.