Semantik von Prädikatenlogik

Question

1-

Wir betrachten die Signatur $$\tau=\left(K^{2}\right)$$ und die Strukturen $$\mathcal{N}=\left(\mathbb{N}, K^{N}\right), \mathcal{Z}=\left(\mathbb{Z}, K^{Z}\right)$$ und $$\mathcal{R}=\left(\mathbb{R}, K^{R}\right)$$ zu $$tau,$$ die jeweils den natürlichen, ganzen und reellen Zahlen mit der zugehörigen, kleiner als" Relation entsprechen. Das heißt zum Beispiel $$K^{\mathcal{N}}=\{(a, b) \in \mathbb{N} \times \mathbb{N} | a<b\}$$
Bestimmen Sie für jede der folgenden geschlossenen Formeln und jede der obigen Strukturen, ob die Struktur ein Modell für die Formel ist. Schreiben und begründen Sie also z.B.$$\mathcal{N} \bmod e l s \varphi_{1}$$ bzw. $$\mathcal{N} \not=\varphi_{1}$$
$$ \varphi_{1}=\exists x\left(\forall x^{\prime}\left(\neg x=x^{\prime} \rightarrow K\left(x, x^{\prime}\right)\right)\right) $$
2. $$\varphi_{2}=\forall x\left(\exists x^{\prime}\left(K\left(x, x^{\prime}\right)\right) \wedge \exists x^{\prime \prime}\left(K\left(x^{\prime \prime}, x\right)\right)\right)$$
$$ \begin{array}{l} {\varphi_{3}=\forall x\left(\exists x^{\prime}\left(K\left(x, x^{\prime}\right) \wedge \neg\left(\exists x^{\prime \prime}\left(K\left(x, x^{\prime \prime}\right) \wedge K\left(x^{\prime \prime}, x^{\prime}\right)\right)\right)\right)\right)} \\ {\varphi_{4}=\forall x\left(\forall x^{\prime}\left(K x^{\prime \prime}\left(\left(K\left(x, x^{\prime}\right) \wedge K\left(x^{\prime}, x^{\prime \prime}\right)\right) \rightarrow K\left(x, x^{\prime \prime}\right)\right)\right)\right)} \end{array} $$

Kann mir da jemand weiterhelfen, wie das funktioniert?

2.

1. $$\psi_{1}=\forall x\left(\exists x^{\prime}\left(R\left(x, x^{\prime}\right) \wedge \neg R\left(x^{\prime}, x\right)\right)\right)$$
2 $$\psi_{2}=\exists x(R(x, x)) \wedge \forall x\left(\forall x^{\prime}\left(\neg R\left(x, x^{\prime}\right) \leftrightarrow R\left(x^{\prime}, x\right)\right)\right)$$
3. $$\Psi_{3}=\exists x\left(\forall x^{\prime \prime}\left(R\left(x, x^{\prime \prime}\right) \vee x=x^{\prime \prime} \vee \exists x^{\prime}\left(x=x^{\prime}\right)\right)\right)$$
$$\psi_{4}=\exists x\left(\exists x^{\prime}\left(\exists x^{\prime \prime}\left(\left(x=x^{\prime}\right) \wedge \neg\left(x=x^{\prime \prime}\right) \wedge\left(R\left(x, x^{\prime}\right) \rightarrow\left(x^{\prime}=x^{\prime \prime}\right)\right)\right)\right)\right)$$
Bearbeiten Sie zu jeder Formel $$\psi_{i}$$die folgenden Aufgaben:
Falls möglich, geben Sie eine Welt $$W_{i}=\left(\mathcal{S}_{i}, \alpha_{i}\right)$$ zu $$\sigma$$ an, die ein Modell der Formel ist. Falls möglich, geben Sie eine Welt $$W_{i}^{\prime}=\left(\mathcal{S}_{i}^{\prime}, \alpha_{i}^{\prime}\right)$$ zu $$\sigma$$ an, die kein Modell der Formel ist.

Danke

Answer 1

So prüfst du, ob eine Struktur ein Modell der Formel ∃ x φ(x)ist:

1. Wähle einen Wert für x
2. Ersetze in φ(x) jedes freie Auftreten von x durch diesen Wert
3. Prüfe ob aus φ(x) dadurch eine wahre Aussage wurde
   • Falls ja, dann ist die Struktur ein Modell
   • Falls nein, dann
     • gehe zurück zu 1 falls du noch nicht alle möglichen Werte für x geprüft hast
     • ist die Struktur kein Modell falls du schon alle möglichen Werte für x geprüft hast

So prüfst du, ob eine Struktur ein Modell der Formel ∀ x ψ(x)ist:

1. Wähle einen Wert für x
2. Ersetze in ψ(x) jedes freie Auftreten von x durch diesen Wert
3. Prüfe ob aus ψ(x) dadurch eine wahre Aussage wurde
   • Falls nein, dann ist die Struktur kein Modell
   • Falls ja, dann
     • gehe zurück zu 1 falls du noch nicht alle möglichen Werte für x geprüft hast
     • ist die Struktur kein Modell falls du schon alle möglichen Werte für x geprüft hast

Beispiel. ∃x(∀x′(¬x=x′→K(x,x′))) mit (ℕ, <).

1. Ich wähle x = 0.

2. Dann ist

        φ = ∀x′(0 ≠ x′ → 0 < x')

2.1 Ich wähle x' = 0.

2.2 Dann ist

       ψ = 0 ≠ 0 → 0 < 0

2.3 Die Aussage 0 ≠ 0 → 0 < 0 ist wahr. Es wurden noch nicht alle x' ∈ℕ geprüft. Also zurück zu 2.1

2.1 Ich wähle x' = 1

2.2 Dann ist

      ψ = 0 ≠ 1 → 0 < 1

2.3 Die Aussage 0 ≠ 1 → 0 < 1 ist wahr. Es wurden noch nicht alle x' ∈ℕ geprüft. Also zurück zu 2.1

Und so weiter.