Syntax
- Variabel: $x_i$
- Funktion: $f_i^{(k)}$
- gibt Wert aus dem Universum aus
- $k$ ist Anzahl der Argumente
- Prädikat: $P_i^{(k)}$ (mit $i, k \in \mathbb{N}$)
- gibt true/false (1/0) aus
Freie und gebundene Variablen
Wenn ein $x$ an ein $\exists$ oder $\forall$ gebunden ist, dann ist es gebunden. Sonst frei.
Free
Eine Funktion, die alle freien Elemente findet, also die Semantik weist den Formeln Wahrheitswerte zu. Zum Beispiel:
- In $A \land B$ sind $A$ und $B$ frei.
- In $P(x)$ sind $P$ und $x$ frei.
- In $\forall x P(x)$ ist nur $P$ frei.
Quantoren-Überschreibung
→ der zweite Quantor überschreibt den ersten, z.B. $\forall x \exists x F \equiv \exists xF$
Interpretationen
Definition
$$
\mathcal{A} = (U, \phi, \psi, \xi)
$$
Eine Interpretation weisst allen freien Elementen etwas zu.
Passende Interpretation: jedem freien Element wird ein Wert zugewiesen
Modell: wahre Interpretaion
| Symbol | Name der Komponente | Beschreibung | Mathematische Zuweisung (k) |
|---|---|---|---|
| $U$ | Universum, nicht-leer | Menge | |
| $\phi$ | Funktionen | Weisst Funktionssymbolen eine Funktion zu. | $\phi(f): U^k \to U$ |
| $\psi$ | Prädikate | Bestimmt Bedeutung der Prädikatensymbole | $\psi(P): U^k \to \{0, 1\}$ |
| $\xi$ | Variablen | Bestimmt Werte der Variablen | $\xi(x_i) \in U$ |
Beispiele
Semantik
$$
\mathcal{A}(\forall x~G) = \begin{cases} 1 & \text{falls } \mathcal{A}_{[x \to u]}(G) = 1 \text{ für alle } u \text{ in } U \\ 0 & \text{sonst} \end{cases}
$$
$$
\mathcal{A}(\exists x~G) = \begin{cases} 1 & \text{falls } \mathcal{A}_{[x \to u]}(G) = 1 \text{ für einige } u \text{ in } U \\ 0 & \text{sonst.} \end{cases}
$$
Ersetzungen
PNF (Pränex-Normalform)
Universum als Mengen, Russels Paradox
