Theoretische Grundlagen der Informatik: Logik
Zweite schriftliche Leistungskontrolle Wintersemester 2016/2017

Es waren 100 Punkte zu erreichen. Die Bearbeitungszeit betrug 75 Minuten, sowie 15 Minuten Einlesezeit. Es waren keine eigenen Hilfsmittel zugelassen.

Zu den Aufgaben gibt es Musterlösungen.

Dieses Dokument ist eine Abschrift einer Musterlösung mit leichten Korrekturen und Anpassungen an das Format. Das Dokument kann im GitLab der TU Berlin kommentiert und bearbeitet werden.

Aufgabe 1

3 2 3 2 10 Punkte

Es sei \( \sigma \) eine Signatur, \( \mathcal{A} \) eine σ-Struktur und \( A \) das Universum von \( \mathcal{A} \). Weiter seien \( \varphi, \psi \in \text{FO} \left[ \sigma \right] \) und \( \Phi, \Psi \subseteq \text{FO} \left[ \sigma \right] \), wobei \( \Psi \) eine Menge von Sätzen sei.

  1. Geben Sie die Definition einer zu \( \varphi \) passenden Belegung in \( A \) und einer zu \( \varphi \) passenden σ-Interpretation an. Definieren Sie sowohl die Begriffe Belegung und σ-Interpretation als auch passend.
  2. Geben Sie die Definitionen an für: \( \varphi \) ist erfüllbar, \( \Phi \) ist erfüllbar.
  3. Geben Sie die Definition der Modellklasse von \( \Psi \) und der Axiomatisierbarkeit (in der Prädikatenlogik) einer Klasse \( \mathcal{C} \) von σ-Strukturen an.
  4. Geben Sie die Definition für die Äquivalenz von \( \varphi \) und \( \psi \) an.

Lösung zu Aufgabe 1

    1. Eine Belegung in \( A \) ist eine Funktion \( \beta \colon \text{def} \left( \beta \right) \to A \text{ mit } \text{def} \left( \beta \right) \subseteq {\rm V{\small AR }} \). \( \beta \) ist passend für \( \varphi \in \text{FO} \left[ \sigma \right] \), wenn \( \text{frei} \left( \varphi \right) \subseteq \text{def} \left( \beta \right) \).
    2. Eine σ-Interpretation ist ein Paar \(\left( \mathcal{A}, \beta \right) \), bestehend aus einer σ-Struktur \( \mathcal{A} \) und einer Belegung \( \beta \) in \( \mathcal{A} \). \( \mathcal{I} := \left( \mathcal{A}, \beta \right) \) ist passend für \( \varphi \in \text{FO} \left[ \sigma \right] \), wenn \( \beta \) zu \( \varphi \) passt.
  2. Die Formel \( \varphi \) ist erfüllbar, wenn sie ein Modell hat, das heißt eine Interpretation \( \mathcal{I} \) existiert, so dass \( \mathcal{I} \models \varphi \). Analog ist \( \Phi \) erfüllbar, wenn es ein Modell von \( \Phi \) gibt.
    1. Die Modellklasse von \( \Phi \), geschrieben \( \text{Mod} \left( \Phi \right) \), ist die Klasse aller σ-Strukturen \( \mathcal{A} \) mit \( \mathcal{A} \models \Phi \).
    2. Eine Klasse \( \mathcal{C} \) von σ-Strukturen ist axiomatisierbar (in der Prädikatenlogik), oder FO-axiomatisierbar, wenn \( \mathcal{C} = \text{Mod} \left( \Phi \right) \) für eine Menge \( \Phi \subseteq \text{FO} \left[ \sigma \right] \).
  4. Zwei σ-Formeln \( \varphi, \psi \in \text{FO} \left[ \sigma \right] \) sind äquivalent, geschrieben \( \varphi \equiv \psi \), wenn für alle σ-Interpretationen \( \mathcal{I} \) passend zu \( \varphi \) und \( \psi \) gilt \[ \mathcal{I} \models \varphi \iff \mathcal{I} \models \psi . \]

Aufgabe 2

1 1 3 5 10 Punkte

Wir betrachten die Signatur \( \tau = \left\{ +, \cdot, N \right\} \), wobei \( + \) und \( \cdot \) zweistellige Funktionssymbole sind und \( N \) ein einstelliges Relationssymbol ist.

Wir definieren nun die Struktur \( \mathcal{R} = \left( \mathbb{R}, +^\mathcal{R}, \cdot^\mathcal{R}, N^\mathcal{R} \right) \), wobei \( +^\mathcal{R} \) der üblichen Addition und \( \cdot^\mathcal{R} \) der üblichen Multiplikation entspricht, und \( N^\mathcal{R} = \mathbb{N} \) ist.

Drücken Sie die folgenden Sachverhalte in \( \text{FO} \left[ \tau \right] \) aus. Achten Sie dabei auf die freien Variablen. Sie brauchen Ihre Lösung nicht zu begründen.

  1. \( x = 0 \).
  2. \( x \geq 0 \).
  3. \( x \) ist eine ganze Zahl.
  4. \( z = | x - y | \).

Lösung zu Aufgabe 2

  1. \( \varphi_0 \left( x \right) := \forall y \left( x \cdot y = x \right) \), alternativ \( \varphi_0 \left( x \right) := \forall y \left( N \left( x \cdot y \right) \right) \).
  2. \( \varphi_{\geq 0} \left( x \right) := \exists y \left( y \cdot y = x \right) \).
  3. \( \varphi_\mathbb{Z} \left( x \right) := N \left( x \right) \lor \exists y \exists z \left( \varphi_0 \left( z \right) \land \left( x + y = z \right) \land N \left( y \right) \right) \).
  4. \( \varphi_{| \cdot |} \left( x, y, z \right) := \varphi_{\geq 0} \left( z \right) \land \left( x = y + z \lor y = x + z \right) \).

Aufgabe 3

3 3 3 3 12 Punkte

Wir betrachten die Signatur \( \sigma = \left\{ E, R, G, B \right\} \), wobei \( E \) ein zweistelliges Relationssymbol und \( R \), \( G \) und \( B \) einstellige Relationssymbole sind. Gegeben sind die folgenden drei σ-Strukturen \( \mathcal{G}_1 \), \( \mathcal{G}_2 \) und \( \mathcal{G}_3 \). Die entsprechenden Interpretationen von \( R \), \( G \) und \( B \) sind Färbungen der Knoten mit den Farben Rot, Grün und Blau.

Geben Sie an auf welchen der drei Strukturen die folgenden Formeln gelten und auf welchen nicht. Sie brauchen Ihre Antworten nicht zu begründen.

\( \mathcal{G}_1 \)

\( R^{\mathcal{G}_1} = \left\{ 2, 4 \right\} \\ G^{\mathcal{G}_1} = \left\{ 6 \right\} \\ B^{\mathcal{G}_1} = \left\{ 1, 3, 5 \right\} \)

\( \mathcal{G}_2 \)

\( R^{\mathcal{G}_2} = \left\{ 6 \right\} \\ G^{\mathcal{G}_2} = \left\{ 1, 4, 7 \right\} \\ B^{\mathcal{G}_2} = \left\{ 2, 3, 5 \right\} \)

\( \mathcal{G}_3 \)

\( R^{\mathcal{G}_3} = \emptyset \\ G^{\mathcal{G}_3} = \left\{ 2, 5, 8 \right\} \\ B^{\mathcal{G}_3} = \left\{ 1, 3, 4, 6, 7 \right\} \)

  1. \( \varphi_1 := \exists x \exists y \left( x \neq y \land \forall z \left( z \neq y \to E \left( x, z \right) \right) \right) \)
  2. \( \varphi_2 := \forall x \forall y \left( E \left( x, y \right) \to \left( \neg \left( R \left( x \right) \land R \left( y \right) \right) \land \neg \left( G \left( x \right) \land G \left( y \right) \right) \right) \right) \land \forall z \left( G \left( z \right) \to \exists x \left( R \left( x \right) \land E \left( x, z \right) \right) \right) \)
  3. \( \varphi_3 := \forall x \forall y \forall z \left( \left( E \left( x, y \right) \land E \left( y, z \right) \land E \left( z, x \right) \right) \to \neg \left( B \left( x \right) \land B \left( y \right) \land B \left( z \right) \right) \right) \)
  4. \( \varphi_4 := \forall y \forall z \left( \left( R \left( y \right) \land E \left( y, z \right) \right) \to B \left( z \right) \right) \land \exists x \left( G \left( x \right) \land \exists y \exists z \left( y \neq z \land E \left( x, y \right) \land E \left( x, z \right) \right) \right) \)

Lösung zu Aufgabe 3

  1. \( \mathcal{G}_1 \nvDash \varphi_1, \mathcal{G}_2 \nvDash \varphi_1, \mathcal{G}_3 \nvDash \varphi_1 \).
  2. \( \mathcal{G}_1 \models \varphi_2, \mathcal{G}_2 \nvDash \varphi_2, \mathcal{G}_3 \nvDash \varphi_2 \).
  3. \( \mathcal{G}_1 \models \varphi_3, \mathcal{G}_2 \models \varphi_3, \mathcal{G}_3 \nvDash \varphi_3 \).
  4. \( \mathcal{G}_1 \nvDash \varphi_4, \mathcal{G}_2 \models \varphi_4, \mathcal{G}_3 \models \varphi_4 \).

Aufgabe 4

8 2 5 9 24 Punkte

Wir betrachten das Spiel \( \mathcal{G} := \left( \mathcal{A}, \Omega \right) \), wobei die Arena \( \mathcal{A} = \left( V, V_0, E \right) \) gegeben ist durch den folgenden Graphen und es gilt \( \Omega = \emptyset \), Falsifizierer gewinnt also jede unendliche Partie.

Wie üblich werden werden die Knoten auf denen Verifiziererin am Zug ist als Kreise dargestellt.

\( \mathcal{A} \)

  1. Bestimmen Sie die Gewinnregionen \( W_\text{Ver} \) und \( W_\text{Fal} \). Sie brauchen Ihre Antwort nicht zu begründen.
  2. Ist \( \mathcal{G} \) fundiert, ist es determiniert? Begründen Sie Ihre Antworten.
  3. Geben Sie eine positionale Gewinnstrategie für Verifiziererin im Spiel \( \left( V, V_0, E, 9, \Omega \right) \) an.
  4. Sei \( \mathcal{G}^\prime := \left( V^\prime, V^\prime_0, E^\prime, \Omega^\prime \right) \) ein Spiel und \( W_\text{Ver}^\prime \) die Gewinnregion der Verifiziererin. Zeigen Sie, dass für jedes \( v \in V_0^\prime \setminus W_\text{Ver}^\prime \) gilt \( vE^\prime \cap W_\text{Ver}^\prime = \emptyset \).

Lösung zu Aufgabe 4

  1. \( W_\text{Ver} = \left\{ 3, 4, 8, 9 \right\} \) und \( W_\text{Fal} = \left\{ 1, 2, 5, 6, 7, 10 \right\} \).
  2. Das Spiel \( \mathcal{G} \) ist nicht fundiert, es existieren gerichtete Kreise in \( \mathcal{A} \), so zum Beispiel der Kreis \( \left( 1, 5, 10, 7, 2, 1 \right) \). Allerdings ist \( \mathcal{G} \) determiniert, da \( W_\text{Ver} \cup W_\text{Fal} = V \).
  3. Es gilt \( V_0 = \left\{ 1, 3, 7, 9 \right\} \) und \( V_0 \setminus W_\text{Ver} = \left\{ 1, 7 \right\} \). Wir definieren die Abbildung \( f \colon V_0 \to V \) wie folgt.
    • Für die Knoten 1, 3 und 7 sind die Nachfolger eindeutig bestimmt und wir setzen \( f \left( 1 \right) := 5 \), \( f \left( 3 \right) := 8 \) und \( f \left( 7 \right) := 2 \).
    • Für den Knoten 9 setzen wir \( f \left( 9 \right) := 4 \).
    Damit sind alle Knoten in \( V_0 \) von \( f \) abgedeckt und es gilt \( v \in V_0 \cap W_\text{Ver} \Rightarrow f \left( v \right) \in W_\text{Ver} \), \( f \) ist also eine positionale Gewinnstrategie für Verifiziererin.
  4. Sei \( v \in V_0^\prime \setminus W_\text{Ver}^\prime \). Angenommen es existiert ein \( u \in vE^\prime \cap W_\text{Ver}^\prime \), dann existiert per Definition eine Gewinnstrategie \( f \) für Verifiziererin, sodass sie das Spiel von der Startposition \( u \) aus gewinnt. Wir definieren nun eine neue Strategie \( f^\prime \colon V_0^\prime \to V^\prime \) wie folgt. \[ f^\prime\left( x \right) := \begin{cases} u, & x = u, \\ f\left( x \right), & \text{sonst.} \end{cases} \] Damit ist \( f^\prime \) eine Gewinnstrategie für Verifiziererin im Spiel mit der Startposition \( v \), dies ist aber ein Widerspruch zu der Annahme \( v \in V_0^\prime \setminus W_\text{Ver}^\prime \).

Aufgabe 5

12 9 21 Punkte
  1. Sei \( \sigma := \left\{ E \right\} \) eine Signatur mit einem zweistelligen Relationssymbol. Wir betrachten die folgenden beiden schlaufenfreien Graphen mit ungerichteten Kanten.

    \( \mathcal{A} \)

    \( \mathcal{B} \)

    Geben Sie eine Gewinnstrategie für Herausforderer im EF-Spiel \( \mathfrak{B}_4 \left( \mathcal{A}, \mathcal{B} \right) \) an. Geben Sie außerdem eine trennende Formel \( \psi \) an. Begründen Sie Ihre Antworten.
  2. Sei \( \sigma \) eine Signatur und \( \mathcal{C} \) eine Klasse von σ-Strukturen. Angnommen für alle \( m \geq 1 \) existieren zwei σ-Strukturen \( \mathcal{A}_m \) und \( \mathcal{B}_m \), so dass
    • \( \mathcal{A}_m \in \mathcal{C}, \mathcal{B}_m \notin \mathcal{C} \) und
    • \( \mathcal{A}_m \equiv_m \mathcal{B}_m \).
    Zeigen Sie, dass es dann keinen Satz \( \varphi \in \text{FO}\left[ \sigma \right] \) gibt, der \( \mathcal{C} \) definiert, das heißt es gibt kein \( \varphi \in \text{FO}\left[ \sigma \right] \) mit \( \text{Mod}\left( \varphi \right) = \mathcal{C} \).

Lösung zu Aufgabe 5

  1. Herausforderer spielt auf 4 paarweise nicht benachbarte Knoten, zum Beispiel auf \( u_1, u_3, u_7, u_9 \). In \( \mathcal{A} \) gibt es keine 4 paarweise nicht benachbarten Knoten, also gewinnt Herausforderer. Eine trennende Formel ist \[ \psi = \exists x_1 \exists x_2 \exists x_3 \exists x_4 \bigwedge_{i = 1}^4 \bigwedge_{j = i + 1}^4 \left( x_i \neq x_j \land \neg E \left( x_i, x_j \right) \right). \]
  2. Angenommen es gäbe ein \( \varphi \in \text{FO}\left[ \sigma \right] \) mit \( \mathcal{C} = \text{Mod}\left( \varphi \right) \). Sei \( m := qr \left( \varphi \right) \). Dann ist \( \mathcal{A}_m \in \mathcal{C} \) und somit \( \mathcal{A}_m \models \varphi \). Da aber \( \mathcal{A}_m \equiv_m \mathcal{B}_m \) gilt auch \( \mathcal{B}_m \models \mathcal{C} \), im Widerspruch zu \( \mathcal{B}_m \notin \mathcal{C} \).

Aufgabe 6

2 12 9 23 Punkte
  1. Geben Sie die Definition für Axiome im Sequenzenkalkül an.
  2. Beweisen Sie mit dem prädikatenlogischen Sequenzenkalkül, dass selbstinverse Funktionen surjektiv sind. Das heißt, zeigen Sie die Gültigkeit der Sequenz \[ \forall x f \left( f \left( x \right) \right) = x \Rightarrow \forall y \exists x f \left( x \right) = y. \] Bitte bedenken Sie, dass Sie im Sequenzenkalkül pro Ableitungsschritt nur eine Regel anwenden dürfen. Bitte geben Sie in jedem Schritt den Namen der angewendeten Regel an. Nutzen Sie die Übersicht zu den Regeln des Sequenzenkalküls. Falls Sie eine der Substitutionsregeln \( \left( S \Rightarrow \right) \) oder \( \left( \Rightarrow S \right) \) verwenden, dann geben Sie bitte an, was \( \psi \left( x \right) \) im Kontext dieser Regel ist.
  3. Zeigen oder widerlegen Sie die Korrektheit der Regel \( \frac{ \displaystyle \Phi \Rightarrow \Delta}{ \displaystyle \Phi, \psi \Rightarrow \Delta} \).

Lösung zu Aufgabe 6

  1. Eine Sequenz \( \Phi \Rightarrow \Delta \) ist ein Axiom genau dann, wenn \( \Phi \cap \Delta \neq \emptyset \).
  2. Ein Beweisraum für die angegebene Sequenz ist der folgende.
    1. Regel
      Ableitungsschritt
    2. \( f \left( f \left( c \right) \right) = c \)
      \( \Rightarrow \)
      \( f \left( f \left( c \right) \right) = c \)
    3. \( \left( \forall \Rightarrow \right) \)
      \( \forall x f \left( f \left( x \right) \right) = x \)
      \( \Rightarrow \)
      \( f \left( f \left( c \right) \right) = c \)
    4. \( \left( \Rightarrow \exists \right) \)
      \( \forall x f \left( f \left( x \right) \right) = x \)
      \( \Rightarrow \)
      \( \exists x \left( f \left( x \right) = c \right) \)
    5. \( \left( \Rightarrow \forall \right) \)
      \( \forall x f \left( f \left( x \right) \right) = x \)
      \( \Rightarrow \)
      \( \forall y \exists x \left( f \left( x \right) = y \right) \)
  3. Diese Regel ist korrekt. Angenommen \( \Phi \Rightarrow \Delta \) ist gültig. Sei \( \mathcal{I} \) eine Interpretation mit \( \mathcal{I} \models \Phi \cup \left\{ \psi \right\} \). Dann gilt insbesondere \( \mathcal{I} \models \Phi \). Aus der Gültigkeit von \( \Phi \Rightarrow \Delta \) folgt, dass es ein \( \delta \in \Delta \) gibt mit \( \mathcal{I} \models \delta \). Dies zeigt die Gültigkeit von \( \Phi, \psi \Rightarrow \Delta \).

Regeln des prädikatenlogischen Sequenzenkalküls

\[ \left( \neg \Rightarrow \right) \frac{\Phi \Rightarrow \Delta, \psi}{\Phi, \neg \psi \Rightarrow \Delta} \]
\[ \left( \Rightarrow \neg \right) \frac{\Phi, \psi \Rightarrow \Delta}{\Phi \Rightarrow \Delta, \neg \psi} \]
\[ \left( \land \Rightarrow \right) \frac{\Phi, \psi, \varphi \Rightarrow \Delta}{\Phi, \psi \land \varphi \Rightarrow \Delta} \]
\[ \left( \Rightarrow \land \right) \frac{\Phi \Rightarrow \Delta, \psi \qquad \Phi \Rightarrow \Delta, \varphi}{\Phi \Rightarrow \Delta, \psi \land \varphi} \]
\[ \left( \lor \Rightarrow \right) \frac{\Phi, \varphi \Rightarrow \Delta \qquad \Phi, \psi \Rightarrow \Delta}{\Phi, \varphi \lor \psi \Rightarrow \Delta} \]
\[ \left( \Rightarrow \lor \right) \frac{\Phi \Rightarrow \Delta, \varphi, \psi}{\Phi \Rightarrow \Delta, \varphi \lor \psi} \]
\[ \left( \to \Rightarrow \right) \frac{\Phi \Rightarrow \Delta, \varphi \qquad \Phi, \psi \Rightarrow \Delta}{\Phi, \varphi \to \psi \Rightarrow \Delta} \]
\[ \left( \Rightarrow \to \right) \frac{\Phi, \varphi \Rightarrow \Delta, \psi}{\Phi \Rightarrow \Delta, \varphi \to \psi} \]
\[ \left( \forall \Rightarrow \right) \frac{\Phi, \psi \left( t \right) \Rightarrow \Delta}{\Phi, \forall x \psi \left( x \right) \Rightarrow \Delta} \]
\[ \left( \Rightarrow \forall \right) \frac{\Phi \Rightarrow \Delta, \psi \left( c \right)}{\Phi \Rightarrow \Delta, \forall x \psi \left( x \right)} \] Wobei \( c \) ein nicht in \( \Phi \), \( \Delta \) oder \( \psi \left( x \right) \) vorkommendes Konstantensymbol ist.
\[ \left( \exists \Rightarrow \right) \frac{\Phi, \psi \left( c \right) \Rightarrow \Delta}{\Phi, \exists x \psi \left( x \right) \Rightarrow \Delta} \] Wobei \( c \) ein nicht in \( \Phi \), \( \Delta \) oder \( \psi \left( x \right) \) vorkommendes Konstantensymbol ist.
\[ \left( \Rightarrow \exists \right) \frac{\Phi \Rightarrow \Delta, \psi \left( t \right)}{\Phi \Rightarrow \Delta, \exists x \psi \left( x \right)} \]
\[ \left( S \Rightarrow \right) \frac{\Phi, \psi \left( t \right) \Rightarrow \Delta}{\Phi, t \doteq t^\prime, \psi \left( t^\prime \right) \Rightarrow \Delta} \]
\[ \left( \Rightarrow S \right) \frac{\Phi \Rightarrow \Delta, \psi \left( t \right)}{\Phi, t \doteq t^\prime \Rightarrow \Delta, \psi \left( t^\prime \right)} \]
\[ \left( = \right) \frac{\Phi, t = t \Rightarrow \Delta}{\Phi \Rightarrow \Delta} \]
In den Regeln stehen \( t \) und \( t^\prime \) für einen beliebigen Term und \( t \doteq t^\prime \) bedeutet, dass wir \( t = t^\prime \) oder \( t^\prime = t \) verwenden können.