Logische Theorien - Versionsgeschichte

Css: /* Freie Variablen und geschlossene Aussagen */

2018-08-30T16:28:57Z

‎Freie Variablen und geschlossene Aussagen

Css am 24. August 2018 um 14:45 Uhr

2018-08-24T14:45:27Z

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:22:30Z

‎Theorien, Interpretationen, Modelle

Css: /* Beispiel: Gruppen */

2018-08-17T16:21:29Z

‎Beispiel: Gruppen

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:19:50Z

‎Theorien, Interpretationen, Modelle

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:14:28Z

‎Theorien, Interpretationen, Modelle

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:12:06Z

‎Theorien, Interpretationen, Modelle

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:06:41Z

‎Theorien, Interpretationen, Modelle

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T16:03:49Z

‎Theorien, Interpretationen, Modelle

Css: /* Theorien, Interpretationen, Modelle */

2018-08-17T15:59:24Z

‎Theorien, Interpretationen, Modelle

@@ Zeile 23: / Zeile 23: @@
 == Freie Variablen und geschlossene Aussagen ==
-Wir sagen, dass Quantoren deren Variablen "binden". Eine Variable heißt "frei", solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$
+Wir sagen, dass Quantoren deren Variablen "binden". Eine Variable heißt "frei", solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow {\frak P}(\{x_0,\ldots\})$
 * $\operatorname{FV}(x_i) := \{x_i\}$

@@ Zeile 1: / Zeile 1: @@
 Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische "und" steht, $\vee$, welches für das logische "oder" steht, $\rightarrow$, welches für logische Implikation steht, $\bot$, welches für die immer falsche Aussage, das '''Falsum''', steht, $\forall$, der Allquantor, $\exists$, der Existenzquantor.
@@ Zeile 33: / Zeile 35: @@
 == Theorien, Interpretationen, Modelle ==
 Eine Menge von geschlossenen Formeln heißt '''Theorie'''. Manchmal wird in der Literatur auch eine Menge von Formeln generell als '''Theorie''' bezeichnet. Eine Theorie wird meistens als Axiomensystem benutzt. Beispiele für Theorien ist zum Beispiel die Theorie der Gleichheit $\operatorname{Eq}=\{\forall_x x=x, \forall_x\forall_y x=y \rightarrow y=x, \forall_x\forall_y\forall_z x=y \rightarrow y=z\rightarrow x=z\}$, oder die Gruppentheorie mit dem Relationssymbol $=$, dem zweistelligen Funktionssymbol $\circ$, das man als Infix notiert, der Konstante $e$, und dem einstelligen Funktionssymbol $^{-1}$, das man in Postfix-Notation notiert. Die Theorie enthält die Formeln $\operatorname{Eq}\cup\{ \forall_x a\circ e = a, \forall_x x\circ x^{-1} = e, \forall_x\forall_y\forall_z x\circ(y\circ z) = (x\circ y)\circ z\}$.

← Nächstältere Version		Version vom 17. August 2018, 16:22 Uhr
Zeile 66:		Zeile 66:
	=== Beispiel: Gruppen ===		=== Beispiel: Gruppen ===

−	Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$. Ein anderes Beispiel wäre $(\mathbb{R}\backslash\{0\}, {\frak R})$ mit ${\frak R}(\circ) = (a,b)\mapsto a\cdot b$, ${\frak R}(^-1) = a\mapsto\frac{1}{a}$, ${\frak R}(e) = 1$.	+	Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$. Ein anderes Beispiel wäre $(\mathbb{R}\backslash\{0\}, {\frak R})$ mit ${\frak R}(\circ) = (a,b)\mapsto a\cdot b$, ${\frak R}(^{-1}) = a\mapsto\frac{1}{a}$, ${\frak R}(e) = 1$.

← Nächstältere Version		Version vom 17. August 2018, 16:21 Uhr
Zeile 66:		Zeile 66:
	=== Beispiel: Gruppen ===		=== Beispiel: Gruppen ===

−	Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$.	+	Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$. Ein anderes Beispiel wäre $(\mathbb{R}\backslash\{0\}, {\frak R})$ mit ${\frak R}(\circ) = (a,b)\mapsto a\cdot b$, ${\frak R}(^-1) = a\mapsto\frac{1}{a}$, ${\frak R}(e) = 1$.

← Nächstältere Version		Version vom 17. August 2018, 16:19 Uhr
Zeile 61:		Zeile 61:

	Sei nun $T$ eine Theorie. Wir schreiben ${\cal M}\models T$, um auszudrücken, dass ${\cal M}\models A$ für alle $A\in T$. Eine Belegung brauchen wir an dieser Stelle nicht mehr beachten, da in einer Theorie alle Formeln geschlossen sind. Ist ${\cal M}\models T$, so heißt $\cal M$ ein '''Modell''' von $T$.		Sei nun $T$ eine Theorie. Wir schreiben ${\cal M}\models T$, um auszudrücken, dass ${\cal M}\models A$ für alle $A\in T$. Eine Belegung brauchen wir an dieser Stelle nicht mehr beachten, da in einer Theorie alle Formeln geschlossen sind. Ist ${\cal M}\models T$, so heißt $\cal M$ ein '''Modell''' von $T$.
		+
		+	Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die "echte" Gleichheit ist. Wir tun das aber nicht.
		+
		+	=== Beispiel: Gruppen ===
		+
		+	Die Modelle der oben definierten Gruppentheorie sind, wenn man $=$ als echte Gleichheit definiert, genau die Gruppen. Ein Beispiel für eine Interpretation wäre $(\mathbb{Z}, {\frak Z})$ mit ${\frak Z}(\circ) = (a,b)\mapsto a+b$, ${\frak Z}(^{-1}) = a\mapsto -a$, ${\frak Z}(e) = 0$.

← Nächstältere Version		Version vom 17. August 2018, 16:14 Uhr
Zeile 59:		Zeile 59:
	* ${\cal M}\models \exists_{x_i} A[\eta]$ genau dann, wenn es ein $o\in D$ gibt, sodass ${\cal M}\models A[\tau]$, wobei $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.		* ${\cal M}\models \exists_{x_i} A[\eta]$ genau dann, wenn es ein $o\in D$ gibt, sodass ${\cal M}\models A[\tau]$, wobei $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.
	* ${\cal M}\models \forall_{x_i} A[\eta]$ genau dann, wenn für alle $o\in D$ gilt ${\cal M}\models A[\tau]$, wobei wieder $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$.		* ${\cal M}\models \forall_{x_i} A[\eta]$ genau dann, wenn für alle $o\in D$ gilt ${\cal M}\models A[\tau]$, wobei wieder $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$.
		+
		+	Sei nun $T$ eine Theorie. Wir schreiben ${\cal M}\models T$, um auszudrücken, dass ${\cal M}\models A$ für alle $A\in T$. Eine Belegung brauchen wir an dieser Stelle nicht mehr beachten, da in einer Theorie alle Formeln geschlossen sind. Ist ${\cal M}\models T$, so heißt $\cal M$ ein '''Modell''' von $T$.

← Nächstältere Version		Version vom 17. August 2018, 16:12 Uhr
Zeile 57:		Zeile 57:
	* ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.		* ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.
	* ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.		* ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.
		+	* ${\cal M}\models \exists_{x_i} A[\eta]$ genau dann, wenn es ein $o\in D$ gibt, sodass ${\cal M}\models A[\tau]$, wobei $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.
		+	* ${\cal M}\models \forall_{x_i} A[\eta]$ genau dann, wenn für alle $o\in D$ gilt ${\cal M}\models A[\tau]$, wobei wieder $\tau(j) := \left\{\begin{array}{cl} o & \mbox{ falls } j=i \\ \eta(j) & \mbox{ sonst}\end{array}\right.$.

@@ Zeile 33: / Zeile 33: @@
 == Theorien, Interpretationen, Modelle ==
 Eine Menge von geschlossenen Formeln heißt '''Theorie'''. Manchmal wird in der Literatur auch eine Menge von Formeln generell als '''Theorie''' bezeichnet. Eine Theorie wird meistens als Axiomensystem benutzt. Beispiele für Theorien ist zum Beispiel die Theorie der Gleichheit $\operatorname{Eq}=\{\forall_x x=x, \forall_x\forall_y x=y \rightarrow y=x, \forall_x\forall_y\forall_z x=y \rightarrow y=z\rightarrow x=z\}$, oder die Gruppentheorie mit dem Relationssymbol $=$, dem zweistelligen Funktionssymbol $\circ$, das man als Infix notiert, der Konstante $e$, und dem einstelligen Funktionssymbol $^{-1}$, das man in Postfix-Notation notiert. Die Theorie enthält die Formeln $\operatorname{Eq}\cup\{ \forall_x a\circ e = a, \forall_x x\circ x^{-1} = e, \forall_x\forall_y\forall_z x\circ(y\circ z) = (x\circ y)\circ z\}$.
@@ Zeile 39: / Zeile 41: @@
 Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen "echte" Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.
 Hierbei gibt es aber erstmal eine technische Schwierigkeit: Wir müssen rekursiv Bedeutungen für Formeln definieren, und haben deshalb zwischendurch auch mit offenen Formeln zu tun. Um dieses technische Problem zu lösen, hat eine Interpretation eine '''Belegung'''. Eine Belegung ist eine Funktion $\eta : \mathbb{N}_0\rightarrow D$. Wenn nun die Variable $x_i$ frei in einer Formel vorkommt, "interpretieren" wir sie als das Objekt $\eta(i)$.
@@ Zeile 53: / Zeile 54: @@
 * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.
 * ${\cal M}\models R_i^k(t_1,\ldots,t_k)[\eta]$ genau dann, wenn $({\frak I}_\eta(t_1),\ldots,{\frak I}_\eta(t_k)) \in {\frak I}_\eta(R_i^k)$.

← Nächstältere Version		Version vom 17. August 2018, 16:03 Uhr
Zeile 49:		Zeile 49:
	* Für jedes verwendete Relationssymbol $R_i^n$ soll ${\frak I}_\eta(R_i^n)$ eine $n$-Stellige Relation, also eine Teilmenge von $D^n$, sein.		* Für jedes verwendete Relationssymbol $R_i^n$ soll ${\frak I}_\eta(R_i^n)$ eine $n$-Stellige Relation, also eine Teilmenge von $D^n$, sein.

−	Das Paar $I=(D,{\frak I})$ heißt dann '''Interpretation'''. Wir definieren nun, was es heißt, dass eine Formel unter einer Interpretation gilt. Wir schreiben $I\models F[\eta]$, um auszudrücken, dass eine Formel $F$ in der Interpretation $I$ unter der Belegung $\eta$ gilt.	+	Das Paar ${\cal M}=(D,{\frak I})$ heißt dann '''Interpretation'''. Wir definieren nun, was es heißt, dass eine Formel unter einer Interpretation gilt. Wir schreiben ${\cal M}\models F[\eta]$, um auszudrücken, dass eine Formel $F$ in der Interpretation $\cal M$ unter der Belegung $\eta$ gilt. Das ist wie folgt definiert:
		+
		+	* ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.
		+	* ${\cal M}\models R_i^k(t_1,\ldots,t_k)[\eta]$ genau dann, wenn $({\frak I}_\eta(t_1),\ldots,{\frak I}_\eta(t_k)) \in {\frak I}_\eta(R_i^k)$.

@@ Zeile 43: / Zeile 43: @@
 Hierbei gibt es aber erstmal eine technische Schwierigkeit: Wir müssen rekursiv Bedeutungen für Formeln definieren, und haben deshalb zwischendurch auch mit offenen Formeln zu tun. Um dieses technische Problem zu lösen, hat eine Interpretation eine '''Belegung'''. Eine Belegung ist eine Funktion $\eta : \mathbb{N}_0\rightarrow D$. Wenn nun die Variable $x_i$ frei in einer Formel vorkommt, "interpretieren" wir sie als das Objekt $\eta(i)$.
-Wir definieren nun rekursiv die Funktion ${\frak I}$, die Zeichenketten (Variablen, Termen und Formeln) "echte" Objekte zuordnet:
+Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) "echte" Objekte zuordnet:
-* Für jede Variable $x_i$ soll gelten ${\frak I}(x_i) := \eta(i)$.
+* Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.
-* Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.
+* Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.
-* Für jedes verwendete Relationssymbol $R_i^n$ soll ${\frak I}(R_i^n)$ eine $n$-Stellige Relation, also eine Teilmenge von $D^n$, sein.
+* Für jedes verwendete Relationssymbol $R_i^n$ soll ${\frak I}_\eta(R_i^n)$ eine $n$-Stellige Relation, also eine Teilmenge von $D^n$, sein.