http://uxul.de/4DQNJeqOrv/api.php?action=feedcontributions&feedformat=atom&user=Css 2026-05-11T17:30:15Z Benutzerbeiträge MediaWiki 1.31.0 http://uxul.de/4DQNJeqOrv/index.php?title=Registermaschinen&diff=280 2018-12-13T12:08:48Z

<p>Css: /* Beispiele */</p> <hr /> <div>Ein Maschinenmodell das näher an dem ist, was moderne Computer tun, sind '''Registermaschinen'''.<br /> <br /> Statt einem Speicherband hat man mehrere '''Register''', das sind Zahlenvariablen, die natürliche Zahlen beinhalten können, und es gibt Befehle zum Inkrementieren, Dekrementieren, auf null prüfen, und Sprunganweisungen.<br /> <br /> Wir nennen diese Register $R_0, R_1, \ldots$. Üblicherweise nutzen wir ein Register als Eingabe und ein Register als Ausgabe, der Übersichtlichkeit nennen wir sie manchmal $R_{\mbox{in}}$ und $R_{\mbox{out}}$ oder Ähnliches (wie genau man die Register bezeichnet ist ja auch nicht so wichtig).<br /> <br /> Wir werden sie als Programmcode – ähnlich zu Programmiersprachen – mit Sprunganweisungen darstellen.<br /> <br /> Es gibt für jedes Register &lt;code&gt;R[i]&lt;/code&gt; die Programmbefehle &lt;code&gt;R[i]++&lt;/code&gt; und &lt;code&gt;R[i]--&lt;/code&gt;. &lt;code&gt;R[i]++&lt;/code&gt; erhöht das Register 1, &lt;code&gt;R[i]--&lt;/code&gt; senkt es um $1$ ab falls es $&gt;0$ ist, und lässt es gleich, falls es $0$ ist. Weiterhin gibt es Anweisungen &lt;code&gt;if R[i]==0 then goto A&lt;/code&gt;, wobei &lt;code&gt;A&lt;/code&gt; eine Sprungmarke ist. Die Anweisung springt zur betreffenden Sprungmarke, je nach dem, ob das angegebene Register $0$ ist, oder nicht. Sprungmarken notiert man vor dem Befehl, mit einem Doppelpunkt dahinter. Weiterhin gibt es den befehl &lt;code&gt;End&lt;/code&gt;, der das Programm beendet (natürlich könnte man diesen Befehl auch weglassen, und einfach vereinbaren, dass das Programm endet, sobald es hinter die letzte Programmzeile läuft, alles äquivalente Definitionen), und ein unconditionalles &lt;code&gt;goto&lt;/code&gt;, das immer springt.<br /> <br /> === Beispiele ===<br /> <br /> Die folgenden Beispiele brauchen wir auch für später.<br /> <br /> Der folgende Code überprüft, ob $R_0 \ge R_1$, und falls ja, setzt er $R_2$ auf $1$:<br /> <br /> Start: if R[1]==0 then goto Yes<br /> if R[0] == 0 then goto No<br /> R[1]--<br /> R[0]--<br /> goto Start<br /> <br /> No: End<br /> <br /> Yes: R[2]++<br /> End<br /> <br /> Ähnlich kann man prüfen, ob $R_i &gt; R_j$. Wir können also die Kurzschreibweise &lt;code&gt;if R_i &gt; R_j then goto A&lt;/code&gt; einführen, ohne dass das resultierende Maschinenmodell stärker würde.<br /> <br /> Addition geht durch wiederholte Inkrementierung<br /> <br /> Start: if R[1] == 0 then goto Done<br /> R[0]++<br /> R[1]--<br /> goto Start<br /> <br /> Done: End<br /> <br /> Subtraktion analog, wobei man definiert, dass $a-b=0$ für $a&lt;b$<br /> <br /> Start: if R[1] == 0 then goto Done<br /> R[0]--<br /> R[1]--<br /> goto Start<br /> <br /> Done: End<br /> <br /> Wir können nun die Kurzschreibweisen &lt;code&gt;R[i]+=R[j]&lt;/code&gt; und &lt;code&gt;R[i]-=R[j]&lt;/code&gt; einführen, um vom Register &lt;code&gt;R[i]&lt;/code&gt; den Wert von &lt;code&gt;R[j]&lt;/code&gt; abzuziehen. Damit können wir zum Beispiel Multiplikation definieren<br /> <br /> '''TODO''' Das ist falsch, weil R[1] immer dekrementiert wird. Man will R[1] kopieren und dann den kopierten Wert immer addieren. Selbes für Division.<br /> <br /> Start: if R[1] == 0 then goto Done<br /> R[1]--<br /> R[2]+=R[1]<br /> goto Start<br /> <br /> Done: End<br /> <br /> Division die den Rest verwirft können wir analog definieren mittels wiederholter Subtraktion<br /> <br /> Start: if R[1] &gt; R[0] then goto Done<br /> R[0] -= R[1]<br /> R[2]++<br /> goto Start<br /> <br /> Done: End<br /> <br /> Damit können wir auch den Rest der Division berechnen, da dieser einfach &lt;code&gt;a - b * a/b&lt;/code&gt; ist, wobei &lt;code&gt;/&lt;/code&gt; die Division ohne Rest ist.<br /> <br /> === Turingmaschinen sind Register-Mächtig ===<br /> <br /> Dass man jede Registermaschine auch als Turingmaschine umbauen kann, sieht man leicht: Haben wir $n$ Register, so können wir diese einfach eine $n$-Band-Turingmaschine ersetzen, auf der wir die Zahlen unal speichern, und ein bisschen Logik einbauen für den Nullfall.<br /> <br /> === Registermaschinen sind Turing-Mächtig ===<br /> <br /> Wir zeigen, dass Registermaschinen äquivalent zu Zweikellerautomaten sind. Damit ist auch gezeigt, dass sie Turingmächtig sind.<br /> <br /> Sei ein Alphabet ${\cal L}=\{a_1,\ldots,a_n\}$ gegeben, und sei $g(a_i):=i$. Dem Wort $a_{k_1}\ldots a_{k_q}$ ordnen wir eineindeutig die Zahl $\sum\limits_{i=0}^{q-1} n^i \cdot g(a_{k_i})$ zu, dem Wort $\varepsilon$ die Zahl $0$, und nennen diese Funktion auch $g$. Offensichtlich ist damit $g(a_j v) = j + n\cdot g(v)$.<br /> <br /> Das heißt, das erste Zeichen unseres codierten Wortes kriegen wir heraus, indem wir den Modulus des Codes bezüglich $n$ berechnen. Ein weiteres Zeichen anhängen können wir, indem wir den code mit $n$ multiplizieren und das Zeichen aufaddieren. Beide Operationen sind, wie man an obigen Beispielen sieht, in polynomieller Zeit mit Registermaschinen möglich.<br /> <br /> Vergleiche sind ebenfalls möglich. Damit ist es offensichtlich möglich, einen Zweikellerautomaten zu simulieren.<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Grundbegriffe&diff=279 2018-11-04T11:19:38Z

<p>Css: /* Wort */</p> <hr /> <div>== Alphabet ==<br /> Als '''Alphabet''' bezeichnet man eine Menge von Zeichen. Eine Menge als &quot;Alphabet&quot; zu bezeichnen sagt nichts über diese Menge aus, sondern gibt an, was man vorhat mit der Menge zu tun.<br /> <br /> Beispiele:<br /> <br /> * Das Alphabet für Unalzahlen $\{1\}$<br /> * Das Alphabet der Dualstellen $\{0,1\}$<br /> * Ein Alphabet für einfache mathematische Formeln $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * '''TODO'''<br /> <br /> In den meisten Fällen verwenden wir endliche Alphabete. Es ist aber ohne Weiteres möglich, eine unendliche Menge als Alphabet zu benutzen.<br /> <br /> == Wort ==<br /> <br /> Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einem Alphabet $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.<br /> <br /> Beispiele:<br /> <br /> * Die Wörter über $\{1\}$ sind endliche Folgen von Einsen; sie stellen die Unaldarstellungen von $\mathbb{N}$ dar.<br /> * $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$<br /> * $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jedem Alphabet. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einem Alphabet $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.<br /> * '''TODO'''<br /> <br /> Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.<br /> <br /> == Sprache ==<br /> <br /> Als '''Sprache''' über einem Alphabet $\cal L$ bezeichnet man eine (nicht notwendigerweise endliche) Teilmenge von ${\cal L}^*$.<br /> <br /> Beispiele:<br /> <br /> * Die leere Sprache $\emptyset$ ist Sprache über jedem Alphabet.<br /> * ${\cal L}^+$ und ${\cal L}^*$ sind Sprachen über dem Alphabet $\cal L$.<br /> * Die Menge der syntaktisch korrekten Formeln über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ist eine Sprache. Sie enthält insbesondere zum Beispiel nicht die Zeichenkette $)($.<br /> * Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.<br /> * '''TODO'''<br /> <br /> == Codierung als Zahlen ==<br /> <br /> Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.<br /> <br /> Lemma: Diese Zuordnung ist Bijektiv.<br /> Beweis: Übung.<br /> <br /> Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.<br /> <br /> Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.<br /> <br /> Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Grundbegriffe&diff=278 2018-11-04T10:50:41Z

<p>Css: /* Wort */</p> <hr /> <div>== Alphabet ==<br /> Als '''Alphabet''' bezeichnet man eine Menge von Zeichen. Eine Menge als &quot;Alphabet&quot; zu bezeichnen sagt nichts über diese Menge aus, sondern gibt an, was man vorhat mit der Menge zu tun.<br /> <br /> Beispiele:<br /> <br /> * Das Alphabet für Unalzahlen $\{1\}$<br /> * Das Alphabet der Dualstellen $\{0,1\}$<br /> * Ein Alphabet für einfache mathematische Formeln $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * '''TODO'''<br /> <br /> In den meisten Fällen verwenden wir endliche Alphabete. Es ist aber ohne Weiteres möglich, eine unendliche Menge als Alphabet zu benutzen.<br /> <br /> == Wort ==<br /> <br /> Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einem Alphabet $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.<br /> <br /> Beispiele:<br /> <br /> * Die Wörter über $\{1\}$ sind endliche Folgen von Einsen; sie stellen die Unaldarstellungen von $\mathbb{N}$ dar.<br /> * $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$<br /> * $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jeder Sprache. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einer Sprache $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.<br /> * '''TODO'''<br /> <br /> Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.<br /> <br /> == Sprache ==<br /> <br /> Als '''Sprache''' über einem Alphabet $\cal L$ bezeichnet man eine (nicht notwendigerweise endliche) Teilmenge von ${\cal L}^*$.<br /> <br /> Beispiele:<br /> <br /> * Die leere Sprache $\emptyset$ ist Sprache über jedem Alphabet.<br /> * ${\cal L}^+$ und ${\cal L}^*$ sind Sprachen über dem Alphabet $\cal L$.<br /> * Die Menge der syntaktisch korrekten Formeln über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ist eine Sprache. Sie enthält insbesondere zum Beispiel nicht die Zeichenkette $)($.<br /> * Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.<br /> * '''TODO'''<br /> <br /> == Codierung als Zahlen ==<br /> <br /> Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.<br /> <br /> Lemma: Diese Zuordnung ist Bijektiv.<br /> Beweis: Übung.<br /> <br /> Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.<br /> <br /> Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.<br /> <br /> Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Grundbegriffe&diff=277 2018-11-04T10:46:24Z

<p>Css: /* Wort */</p> <hr /> <div>== Alphabet ==<br /> Als '''Alphabet''' bezeichnet man eine Menge von Zeichen. Eine Menge als &quot;Alphabet&quot; zu bezeichnen sagt nichts über diese Menge aus, sondern gibt an, was man vorhat mit der Menge zu tun.<br /> <br /> Beispiele:<br /> <br /> * Das Alphabet für Unalzahlen $\{1\}$<br /> * Das Alphabet der Dualstellen $\{0,1\}$<br /> * Ein Alphabet für einfache mathematische Formeln $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * '''TODO'''<br /> <br /> In den meisten Fällen verwenden wir endliche Alphabete. Es ist aber ohne Weiteres möglich, eine unendliche Menge als Alphabet zu benutzen.<br /> <br /> == Wort ==<br /> <br /> Als '''Wort''' über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von '''Zeichenketten''' oder '''Strings'''.<br /> <br /> Beispiele:<br /> <br /> * Die Wörter über $\{1\}$ sind endliche Folgen von Einsen; sie stellen die Unaldarstellungen von $\mathbb{N}$ dar.<br /> * $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$<br /> * $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$<br /> * Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jeder Sprache. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einer Sprache $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.<br /> * '''TODO'''<br /> <br /> Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als '''Verkettung''' oder '''Konkatenation'''. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.<br /> <br /> == Sprache ==<br /> <br /> Als '''Sprache''' über einem Alphabet $\cal L$ bezeichnet man eine (nicht notwendigerweise endliche) Teilmenge von ${\cal L}^*$.<br /> <br /> Beispiele:<br /> <br /> * Die leere Sprache $\emptyset$ ist Sprache über jedem Alphabet.<br /> * ${\cal L}^+$ und ${\cal L}^*$ sind Sprachen über dem Alphabet $\cal L$.<br /> * Die Menge der syntaktisch korrekten Formeln über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ist eine Sprache. Sie enthält insbesondere zum Beispiel nicht die Zeichenkette $)($.<br /> * Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.<br /> * '''TODO'''<br /> <br /> == Codierung als Zahlen ==<br /> <br /> Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.<br /> <br /> Lemma: Diese Zuordnung ist Bijektiv.<br /> Beweis: Übung.<br /> <br /> Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.<br /> <br /> Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.<br /> <br /> Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=276 2018-08-30T16:28:57Z

<p>Css: /* Freie Variablen und geschlossene Aussagen */</p> <hr /> <div>Jetzt wird es erstmal etwas technisch …<br /> <br /> Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, 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\})$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.<br /> <br /> Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die &quot;echte&quot; Gleichheit ist. Wir tun das aber nicht.<br /> <br /> === Beispiel: Gruppen ===<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NP&diff=275 2018-08-29T19:40:36Z

<p>Css: </p> <hr /> <div>NP ist die nicht-deterministische Version von P. Die meisten praxisrelevanten Probleme, die sehr schwierig sind, sind in NP. Die meisten Rätsel, zum Beispiel Sudoku, sind in NP.<br /> <br /> [https://en.wikipedia.org/wiki/Cook–Levin_theorem Satz von Levin-Cook]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NP&diff=274 2018-08-29T19:40:09Z

<p>Css: </p> <hr /> <div>NP ist die nicht-deterministische Version von P. Die meisten praxisrelevanten Probleme, die sehr schwierig sind, sind in NP. Die meisten Rätsel, zum Beispiel Sudoku, sind in NP.<br /> <br /> [[https://en.wikipedia.org/wiki/Cook–Levin_theorem Satz von Levin-Cook]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NP&diff=273 2018-08-29T19:35:44Z

<p>Css: Die Seite wurde neu angelegt: „NP ist die nicht-deterministische Version von P. Die meisten praxisrelevanten Probleme, die sehr schwierig sind, sind in NP. Die meisten Rätsel, zum Beispiel…“</p> <hr /> <div>NP ist die nicht-deterministische Version von P. Die meisten praxisrelevanten Probleme, die sehr schwierig sind, sind in NP. Die meisten Rätsel, zum Beispiel Sudoku, sind in NP.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=272 2018-08-29T19:25:09Z

<p>Css: </p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> Beispielsweise sind QuickSort und MergeSort in $P$.<br /> <br /> '''Lemma:''' $L \subseteq P$.<br /> <br /> '''Beweis:''' Werde $K\in L$ von der Maschine $M$ entschieden, und beschränke $g\in{\cal O}(log)$ den Platzverbrauch. Für eine Eingabe $x$ brauchen wir also maximal $g(|x|)$ Speicherziellen. Nun gibt es aber maximal $|{\cal L}|^{g(|x|)}$ verschiedene Möglichkeiten, was auf diesem Band gespeichert sein kann. Aber da $g$ asymptotisch gleich zu $\log$ ist, muss $|{\cal L}|^{g(|x|)}\in{\cal O}(x^k)$ für ein $k$. Da man in einem Durchlauf höchstens alle möglichen Speicherbelegungen durchlaufen kann, ist damit die Laufzeit durch ein Polynom beschränkt.<br /> <br /> '''Lemma:''' $NL \subseteq P$.<br /> <br /> '''Beweis:''' Wir müssen nur alle möglichen Eingaben des Orakelbandes durchprobieren. Diese sind polynomiell viele, und wir können sie in polynomieller Zeit, wie eben gezeigt, überprüfen.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=271 2018-08-29T19:23:59Z

<p>Css: </p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> Beispielsweise sind QuickSort und MergeSort in $P$.<br /> <br /> '''Lemma:''' $L \subseteq P$.<br /> <br /> '''Beweis:''' Werde $K\in L$ von der Maschine $M$ entschieden, und beschränke $g\in{\cal O}(log)$ den Platzverbrauch. Für eine Eingabe $x$ brauchen wir also maximal $g(|x|)$ Speicherziellen. Nun gibt es aber maximal $|{\cal L}|^{g(|x|)}$ verschiedene Möglichkeiten, was auf diesem Band gespeichert sein kann. Aber da $g$ asymptotisch gleich zu $\log$ ist, muss $|{\cal L}|^{g(|x|)}\in{\cal O}(x^k)$ für ein $k$. Da man in einem Durchlauf höchstens alle möglichen Speicherbelegungen durchlaufen kann, ist damit die Laufzeit durch ein Polynom beschränkt.<br /> <br /> '''Lemma:''' $NL \subseteq P$.<br /> <br /> '''Beweis:''' Wir müssen nur alle möglichen Eingaben des Orakelbandes durchprobieren. Diese sind polynomiell viele, und wir können sie in polynomieller Zeit, wie eben gezeigt, überprüfen.<br /> <br /> == Beispiele ==<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=270 2018-08-29T19:22:33Z

<p>Css: </p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> Beispielsweise sind QuickSort und MergeSort in $P$.<br /> <br /> '''Lemma:''' $L \subseteq P$.<br /> <br /> '''Beweis:''' Werde $K\in L$ von der Maschine $M$ entschieden, und beschränke $g\in{\cal O}(log)$ den Platzverbrauch. Für eine Eingabe $x$ brauchen wir also maximal $g(|x|)$ Speicherziellen. Nun gibt es aber maximal $|{\cal L}|^{g(|x|)}$ verschiedene Möglichkeiten, was auf diesem Band gespeichert sein kann. Aber da $g$ asymptotisch gleich zu $\log$ ist, muss $|{\cal L}|^{g(|x|)}\in{\cal O}(x^k)$ für ein $k$. Da man in einem Durchlauf höchstens alle möglichen Speicherbelegungen durchlaufen kann, ist damit die Laufzeit durch ein Polynom beschränkt.<br /> <br /> '''Lemma:''' $NL \subseteq P$.<br /> <br /> '''Beweis:''' '''TODO'''<br /> <br /> <br /> == Beispiele ==<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=269 2018-08-29T19:17:49Z

<p>Css: </p> <hr /> <div>NL ist die nichtdeterministische Variante von L, $\operatorname{NSPACE}(\log)$.<br /> <br /> '''Bemerkung:''' $N\subseteq NL$<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:<br /> <br /> $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $<br /> <br /> Die Frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Ausdruck wahr macht.<br /> <br /> Da wir nichtdeterministisch arbeiten, reicht es, dass wir davon ausgehen, dass auf unserem Orakelband eine solche lösende Belegung gespeichert ist. Zu Überprüfen ob der Ausdruck dann wahr ist ist trivial.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=268 2018-08-29T19:17:12Z

<p>Css: </p> <hr /> <div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$. Für sublinearen Speicherverbrauch vereinbart man, dass die Eingabe in einem eigenen Read-Only-Band übergeben wird, da dieser einem ansonsten schon linear viel zusätzlichen Speicherplatz brächte.<br /> <br /> == Beispiele ==<br /> <br /> === k-Cliquen in Graphen ===<br /> <br /> Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz.<br /> <br /> === Erreichbarkeit in Graphen ===<br /> <br /> Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang,<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=267 2018-08-29T19:14:58Z

<p>Css: </p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> Beispielsweise sind QuickSort und MergeSort in $P$.<br /> <br /> '''Lemma:''' $L \subseteq P$.<br /> '''Beweis:''' <br /> <br /> '''Lemma:''' $NL \subseteq P$.<br /> <br /> '''Beweis:''' '''TODO'''<br /> <br /> <br /> == Beispiele ==<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=266 2018-08-29T18:42:16Z

<p>Css: </p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> '''Bemerkung:''' $N\subseteq NL$<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:<br /> <br /> $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $<br /> <br /> Die Frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Ausdruck wahr macht.<br /> <br /> Da wir nichtdeterministisch arbeiten, reicht es, dass wir davon ausgehen, dass auf unserem Orakelband eine solche lösende Belegung gespeichert ist. Zu Überprüfen ob der Ausdruck dann wahr ist ist trivial.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=265 2018-08-29T18:41:42Z

<p>Css: /* Beispiel */</p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:<br /> <br /> $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $<br /> <br /> Die Frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Ausdruck wahr macht.<br /> <br /> Da wir nichtdeterministisch arbeiten, reicht es, dass wir davon ausgehen, dass auf unserem Orakelband eine solche lösende Belegung gespeichert ist. Zu Überprüfen ob der Ausdruck dann wahr ist ist trivial.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=264 2018-08-29T18:29:56Z

<p>Css: /* Beispiel */</p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:<br /> <br /> $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $<br /> <br /> Die frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Susdruck wahr macht.<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=263 2018-08-29T18:27:32Z

<p>Css: /* Beispiel */</p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:<br /> <br /> $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=262 2018-08-29T18:25:23Z

<p>Css: </p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> == Beispiel ==<br /> <br /> Das 2SAT-Problem ist in NL:<br /> <br /> Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft.<br /> <br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Nichtdeterministische_Turingmaschinen&diff=261 2018-08-29T15:39:25Z

<p>Css: </p> <hr /> <div>Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, dass man mehrere Sprungziele angibt bei jeder Anweisung. Allerdings werden wir dies nicht tun, sondern stattdessen ein ''Orakelband'' verwenden.<br /> <br /> Das Orakelband selbst darf nur einmal gelesen werden, man kann sich auf dem Orakelband nicht hin- und her-bewegen, sondern nur nach rechts.<br /> <br /> Wir haben nun also Maschinen mit zwei Eingaben $M(o,i)$, wobei $o$ das Orakelband ist.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=259 2018-08-29T15:22:56Z

<p>Css: /* Beispiele */</p> <hr /> <div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil es sonst nicht möglich ist, weniger als linear viel Speicher zu brauchen).<br /> <br /> == Beispiele ==<br /> <br /> === k-Cliquen in Graphen ===<br /> <br /> Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz.<br /> <br /> === Erreichbarkeit in Graphen ===<br /> <br /> Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang,<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=258 2018-08-29T15:19:39Z

<p>Css: /* Kapitel 2: Berechenbarkeitstheorie */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Nichtdeterministische Turingmaschinen]]<br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=255 2018-08-27T07:17:39Z

<p>Css: /* Kapitel 1: Automaten */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Nichtdeterministische Turingmaschinen]]<br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Landau-Notation&diff=249 2018-08-25T19:07:51Z

<p>Css: </p> <hr /> <div>Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren vor, dass Dinge für kleine Eingaben andere Eigenschaften haben als für größere Eingaben. Deshalb behilft man sich, indem man nur das ''asymptotische'' Verhalten betrachtet.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal O}(g)$, wenn eine Konstante $0&lt;c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $|f(x)| &lt; c\cdot |g(x)|$ gilt.<br /> <br /> Oft schreibt man, zum Beispiel in der Numerik, $f={\cal O}(g)$ statt $f\in{\cal O}(g)$.<br /> <br /> Beispiele:<br /> <br /> * Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.<br /> * Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.<br /> * Jedes Polynom $p$ ist in ${\cal O}(e^x)$.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon&gt;0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $|f(n)|\le\varepsilon |g(n)|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Landau-Notation&diff=248 2018-08-25T19:07:29Z

<p>Css: </p> <hr /> <div>Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren vor, dass Dinge für kleine Eingaben andere Eigenschaften haben als für größere Eingaben. Deshalb behilft man sich, indem man nur das ''asymptotische'' Verhalten betrachtet.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal O}(g)$, wenn eine Konstante $0&lt;c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $|f(x)| &lt; c\cdot |g(x)|$ gilt.<br /> <br /> Oft schreibt man, zum Beispiel in der Numerik, $f={\cal O}(g)$ statt $f\in{\cal O}(g)$.<br /> <br /> Beispiele:<br /> <br /> * Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.<br /> * Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.<br /> * Jedes Polynom $p$ ist in ${\cal O}(e^x)$.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon&gt;0$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $|f(x)|\le\varepsilon |g(x)|$. Das heißt, $f$ wird beliebig klein gegenüber $g$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Landau-Notation&diff=247 2018-08-25T19:06:36Z

<p>Css: </p> <hr /> <div>Beim Vergleichen von Laufzeiten und Speicherplatz ist es oft nicht sinnvoll, diese bis auf lineare Faktoren genau anzugeben. Insbesondere kommt es des Öfteren vor, dass Dinge für kleine Eingaben andere Eigenschaften haben als für größere Eingaben. Deshalb behilft man sich, indem man nur das ''asymptotische'' Verhalten betrachtet.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal O}(g)$, wenn eine Konstante $0&lt;c\in\mathbb{R}$ existiert, sodass für hinreichend groß gewähltes $x$ stets $|f(x)| &lt; c\cdot |g(x)|$ gilt.<br /> <br /> Oft schreibt man, zum Beispiel in der Numerik, $f={\cal O}(g)$ statt $f\in{\cal O}(g)$.<br /> <br /> Beispiele:<br /> <br /> * Seien $p$ und $q$ Polynome, und $\deg p \le \deg q$. Dann ist $p\in{\cal O}(q)$. Deshalb schreibt man meistens nur die höchste Potenz hin, also zum Beispiel ${\cal O}(x^4)$.<br /> * Funktionen in ${\cal O}(1)$ sind ab hinreichend großer Eingabe durch eine Konstante beschränkt.<br /> * Jedes Polynom $p$ ist in ${\cal O}(e^x)$.<br /> <br /> Seien $f$ und $g$ zwei Funktionen von $\mathbb{R}$ nach $\mathbb{R}$. Wir sagen $f\in{\cal o}(g)$, wenn für alle $\varepsilon$ ein $N$ existiert, sodass für alle $n\ge N$ gilt $|f(x)|\le\varepsilon g(x)$. Das heißt, $f$ wird beliebig klein gegenüber $g$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=246 2018-08-24T14:45:27Z

<p>Css: </p> <hr /> <div>Jetzt wird es erstmal etwas technisch …<br /> <br /> Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.<br /> <br /> Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die &quot;echte&quot; Gleichheit ist. Wir tun das aber nicht.<br /> <br /> === Beispiel: Gruppen ===<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=245 2018-08-24T14:38:28Z

<p>Css: /* Kapitel 1: Automaten */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Minimierung von deterministischen endlichen Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Nichtdeterministische Turingmaschinen]]<br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=244 2018-08-24T14:38:17Z

<p>Css: /* Kapitel 1: Automaten */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Minimierung von deterministischen endlichen Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> * [[Die Chomsky-Hierarchie]] (evtl.)<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Nichtdeterministische Turingmaschinen]]<br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=243 2018-08-24T14:35:51Z

<p>Css: </p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> '''Lemma:''' $NL \subseteq P$.<br /> <br /> '''Beweis:''' '''TODO'''<br /> <br /> <br /> == Beispiele ==<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=P&diff=242 2018-08-24T14:34:35Z

<p>Css: Die Seite wurde neu angelegt: „P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meiste…“</p> <hr /> <div>P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.<br /> <br /> == Beispiele ==<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=NL&diff=241 2018-08-24T13:55:53Z

<p>Css: Die Seite wurde neu angelegt: „NL ist die nichtdeterministische Variante von NL. '''TODO''' Kategorie:TODO“</p> <hr /> <div>NL ist die nichtdeterministische Variante von NL.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Nichtdeterministische_Turingmaschinen&diff=240 2018-08-24T13:53:05Z

<p>Css: </p> <hr /> <div>Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, dass man mehrere Sprungziele angibt bei jeder Anweisung. Allerdings werden wir dies nicht tun, sondern stattdessen ein ''Orakelband'' verwenden.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Nichtdeterministische_Turingmaschinen&diff=239 2018-08-24T13:50:49Z

<p>Css: Die Seite wurde neu angelegt: „Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, da…“</p> <hr /> <div>Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, dass man mehrere Sprungziele angibt bei jeder Anweisung. Allerdings werden wir dies nicht tun, sondern stattdessen ein ''Orakelband'' verwenden.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=238 2018-08-24T13:48:58Z

<p>Css: /* Kapitel 3: Komplexitätstheorie */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Die Produktkonstruktion]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Minimierung von deterministischen endlichen Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> * [[Die Chomsky-Hierarchie]] (evtl.)<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Nichtdeterministische Turingmaschinen]]<br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=237 2018-08-24T13:39:58Z

<p>Css: Die Seite wurde neu angelegt: „Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil…“</p> <hr /> <div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil es sonst nicht möglich ist, weniger als linear viel Speicher zu brauchen).<br /> <br /> == Beispiele ==<br /> <br /> === Erreichbarkeit in Graphen ===<br /> <br /> '''TODO'''<br /> <br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=236 2018-08-24T13:32:05Z

<p>Css: /* Kapitel 3: Komplexitätstheorie */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Die Produktkonstruktion]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Minimierung von deterministischen endlichen Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> * [[Die Chomsky-Hierarchie]] (evtl.)<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Hauptseite&diff=235 2018-08-24T13:31:11Z

<p>Css: /* Kapitel 3: Komplexitätstheorie */</p> <hr /> <div>&lt;strong&gt;MediaWiki wurde installiert.&lt;/strong&gt;<br /> <br /> $\sum\limits_{i=1}^\infty i=-\frac{1}{12}$<br /> <br /> Hilfe zur Benutzung und Konfiguration der Wiki-Software findest du im [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents Benutzerhandbuch].<br /> <br /> == Index ==<br /> <br /> === Kapitel 0: Einführung ===<br /> * [[Grundbegriffe]]<br /> * [[Logarithmus]]<br /> * [[Landau-Notation]]<br /> <br /> === Kapitel 1: Automaten ===<br /> * [[Deterministische Endliche Automaten]]<br /> * [[Die Produktkonstruktion]]<br /> * [[Nichtdeterministische Endliche Automaten]]<br /> * [[Minimierung von deterministischen endlichen Automaten]]<br /> * [[Reguläre Ausdrücke]]<br /> * [[Pumping Lemma]]<br /> * [[Kellerautomaten]]<br /> * [[Die Chomsky-Hierarchie]] (evtl.)<br /> <br /> === Kapitel 2: Berechenbarkeitstheorie ===<br /> * [[Deterministische Turingmaschinen]]<br /> * [[Zweikellerautomaten]]<br /> * [[Registermaschinen]]<br /> * [[Die Universelle Registermaschine]]<br /> * [[Das Halteproblem]]<br /> * [[Entscheidbarkeit]]<br /> * [[Orakel]]<br /> <br /> === Kapitel 3: Komplexitätstheorie ===<br /> <br /> * [[Zeit- und Platzklassen]]<br /> * [[L]]<br /> * [[NL]]<br /> * [[P]]<br /> * [[NP]]<br /> * [[LINSPACE]]<br /> * [[PSPACE]]<br /> * [[Die Klasse NP]]<br /> <br /> === Kapitel 4: Logik ===<br /> <br /> * [[Logische Theorien]]<br /> * [[Klassische Modelle]]<br /> * [[Logische Komplexität]]<br /> * [[Der Satz von Fagin]]<br /> * [[Der Kalkül des natürlichen Schließens]]<br /> * [[Der Vollständigkeitssatz]] (evtl.)<br /> * [[Der Unvollständigkeitssatz]] (evtl.)<br /> * [[Intuitionistische Logik und Kripkemodelle]] (evtl.)<br /> <br /> == Starthilfen ==<br /> <br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Liste der Konfigurationsvariablen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki-FAQ]<br /> * [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce Mailingliste neuer MediaWiki-Versionen]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Übersetze MediaWiki für deine Sprache]<br /> * [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Erfahre, wie du Spam auf deinem Wiki bekämpfen kannst]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Zeit-_und_Platzklassen&diff=234 2018-08-23T16:04:37Z

<p>Css: /* Polynomielle Zeit */</p> <hr /> <div>Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.<br /> <br /> Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).<br /> <br /> == Algorithmen ==<br /> <br /> Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach &quot;ist ${\cal O}(f)$&quot;, wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.<br /> <br /> Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(|x|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.<br /> <br /> Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.<br /> <br /> Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.<br /> <br /> == Sortierung von Listen ==<br /> <br /> Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.<br /> <br /> '''TODO'''<br /> <br /> == Klassen ==<br /> <br /> Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben, wie wir beim Sortieren von Listen gesehen haben.<br /> <br /> Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.<br /> <br /> Mit $\operatorname{DTIME}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine in ${\cal O}(f)$ schritten lösen lassen.<br /> <br /> Mit $\operatorname{DSPACE}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine unter Platzbedarf ${\cal O}(f)$ lösen lassen.<br /> <br /> <br /> == Polynomielle Zeit ==<br /> <br /> Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$.<br /> <br /> <br /> Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Zeit-_und_Platzklassen&diff=233 2018-08-23T15:53:04Z

<p>Css: /* Polynomielle Zeit */</p> <hr /> <div>Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.<br /> <br /> Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).<br /> <br /> == Algorithmen ==<br /> <br /> Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach &quot;ist ${\cal O}(f)$&quot;, wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.<br /> <br /> Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(|x|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.<br /> <br /> Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.<br /> <br /> Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.<br /> <br /> == Sortierung von Listen ==<br /> <br /> Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.<br /> <br /> '''TODO'''<br /> <br /> == Klassen ==<br /> <br /> Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben, wie wir beim Sortieren von Listen gesehen haben.<br /> <br /> Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.<br /> <br /> Mit $\operatorname{DTIME}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine in ${\cal O}(f)$ schritten lösen lassen.<br /> <br /> Mit $\operatorname{DSPACE}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine unter Platzbedarf ${\cal O}(f)$ lösen lassen.<br /> <br /> <br /> == Polynomielle Zeit ==<br /> <br /> Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE}(x^n)$.<br /> <br /> <br /> Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Zeit-_und_Platzklassen&diff=232 2018-08-23T15:49:57Z

<p>Css: /* Polynomielle Zeit */</p> <hr /> <div>Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.<br /> <br /> Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).<br /> <br /> == Algorithmen ==<br /> <br /> Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach &quot;ist ${\cal O}(f)$&quot;, wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.<br /> <br /> Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(|x|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.<br /> <br /> Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.<br /> <br /> Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.<br /> <br /> == Sortierung von Listen ==<br /> <br /> Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.<br /> <br /> '''TODO'''<br /> <br /> == Klassen ==<br /> <br /> Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben, wie wir beim Sortieren von Listen gesehen haben.<br /> <br /> Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.<br /> <br /> Mit $\operatorname{DTIME}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine in ${\cal O}(f)$ schritten lösen lassen.<br /> <br /> Mit $\operatorname{DSPACE}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine unter Platzbedarf ${\cal O}(f)$ lösen lassen.<br /> <br /> <br /> == Polynomielle Zeit ==<br /> <br /> Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE(x\mapsto x^n)}$.<br /> <br /> <br /> Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Zeit-_und_Platzklassen&diff=231 2018-08-23T15:44:56Z

<p>Css: </p> <hr /> <div>Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.<br /> <br /> Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).<br /> <br /> == Algorithmen ==<br /> <br /> Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach &quot;ist ${\cal O}(f)$&quot;, wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.<br /> <br /> Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(|x|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.<br /> <br /> Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.<br /> <br /> Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.<br /> <br /> == Sortierung von Listen ==<br /> <br /> Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.<br /> <br /> '''TODO'''<br /> <br /> == Klassen ==<br /> <br /> Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben, wie wir beim Sortieren von Listen gesehen haben.<br /> <br /> Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.<br /> <br /> Mit $\operatorname{DTIME}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine in ${\cal O}(f)$ schritten lösen lassen.<br /> <br /> Mit $\operatorname{DSPACE}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine unter Platzbedarf ${\cal O}(f)$ lösen lassen.<br /> <br /> <br /> == Polynomielle Zeit ==<br /> <br /> Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.<br /> <br /> '''TODO'''<br /> <br /> [[Kategorie:TODO]]</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=230 2018-08-17T16:22:30Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.<br /> <br /> Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die &quot;echte&quot; Gleichheit ist. Wir tun das aber nicht.<br /> <br /> === Beispiel: Gruppen ===<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=229 2018-08-17T16:21:29Z

<p>Css: /* Beispiel: Gruppen */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.<br /> <br /> Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die &quot;echte&quot; Gleichheit ist. Wir tun das aber nicht.<br /> <br /> === Beispiel: Gruppen ===<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=228 2018-08-17T16:19:50Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.<br /> <br /> Oft fordert man noch, dass ${\frak I}_\eta(=) = \{(x,x)\mid x\in D\}$ die &quot;echte&quot; Gleichheit ist. Wir tun das aber nicht.<br /> <br /> === Beispiel: Gruppen ===<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=227 2018-08-17T16:14:28Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.<br /> <br /> 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$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=226 2018-08-17T16:12:06Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$ die Belegung ist, die mit $\eta$ übereinstimmt, bis auf an der Stelle $i$.<br /> * ${\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 &amp; \mbox{ falls } j=i \\ \eta(j) &amp; \mbox{ sonst}\end{array}\right.$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=225 2018-08-17T16:06:41Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> Jetzt wird es erstmal etwas technisch …<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.<br /> * ${\cal M}\models A\wedge B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ und ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\vee B[\eta]$ genau dann, wenn ${\cal M}\models A[\eta]$ oder ${\cal M}\models B[\eta]$.<br /> * ${\cal M}\models A\rightarrow B[\eta]$ genau dann, wenn aus ${\cal M}\models A[\eta]$ folgt ${\cal M}\models B[\eta]$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=224 2018-08-17T16:03:49Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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:<br /> <br /> * ${\cal M}\not\models \bot[\eta]$ – $\cal M$ erfüllt die immer falsche Aussage nicht.<br /> * ${\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)$.</div>

Css http://uxul.de/4DQNJeqOrv/index.php?title=Logische_Theorien&diff=223 2018-08-17T15:59:24Z

<p>Css: /* Theorien, Interpretationen, Modelle */</p> <hr /> <div>Wir definieren zunächst, was eine '''Theorie''' ist. Gegeben sind zunächst die logischen Zeichen $\wedge$, welches für das logische &quot;und&quot; steht, $\vee$, welches für das logische &quot;oder&quot; 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.<br /> <br /> Außerdem gegeben seien unendlich viele $n$-stellige Relationssymbole $R_0^n, R_1^n, R_2^n, \ldots$, wobei $n\in\mathbb{N}_1$; unendlich viele $n$-stellige Funktionssymbole $f_0^n, f_1^n, f_2^n, \ldots$, wobei $n\in\mathbb{N}_0$; und unendlich viele Variablensymbole $x_0, x_1, x_2, \ldots$.<br /> <br /> Wir arbeiten nun mit dem Alphabet das all diese Symbole enthält, also einem unendlichen Alphabet, in diesem Fall. Nun wollen wir die Sprache der korrekt geformten Aussagen der Logik 1. Stufe definieren. Zunächst definieren wir die Sprache $\operatorname{Ter}$ der '''Terme''':<br /> <br /> * Alle Variablensymbole sind Terme: für alle $i$ ist $x_i \in \operatorname{Ter}$.<br /> * Sind $t_1, \ldots, t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $f_i^k(t_1,\ldots,t_k)\in\operatorname{Ter}$, das heißt, man darf einem Funktionssymbol so viele Terme übergeben, wie es Stellen hat.<br /> <br /> Nun können wir die Sprache $\operatorname{For}$ der '''Formeln''' definieren:<br /> <br /> * Es ist $\bot\in\operatorname{For}$: Die immer-falsche Aussage ist eine Formel.<br /> * Sind $t_1,\ldots,t_k\in\operatorname{Ter}$, so ist für alle $i$ auch $R_i^k(t_1,\ldots,t_k)\in\operatorname{For}$, das heißt, man darf einem Relationssymbol so viele Terme übergeben, wie es Stellen hat.<br /> * Sind $A, B\in\operatorname{For}$, so sind auch $A\wedge B, A\vee B, A\rightarrow B\in\operatorname{For}$.<br /> * Ist $A\in\operatorname{For}$, so sind für alle $i$ auch $\forall_{x_i} A, \exists_{x_i} A\in\operatorname{For}$.<br /> <br /> Dies war eine sehr technische Definition, die zwar immer funktioniert, aber nicht sehr praktisch zu benutzen ist. In den meisten Fällen schreiben wir nicht $f_i^n$ und $R_i^n$, sondern haben andere, konkretere Funktions- und Relationssymbole. Beispielsweise ist $+$ ein zweistelliges Funktionssymbol, das man zusätzlich üblicherweise als Infix notiert, und $\le$ ist ein zweistelliges Relationssymbol, das man ebenfalls als Infix notiert. Solange klar ist, wie man alles in die formale Schreibweise überführt, sind solche Kurzschreibweisen aber kein Problem, und werden in der Regel ohne größeren Kommentar übernommen.<br /> <br /> Ein Spezialfall sind nullstellige Funktionssymbole, die wir ja definiert haben. Diese bezeichnet man auch als '''Konstanten'''. Beispielsweise ist die $0$ in vielen Theorien eine solche Konstante.<br /> <br /> == Freie Variablen und geschlossene Aussagen ==<br /> <br /> Wir sagen, dass Quantoren deren Variablen &quot;binden&quot;. Eine Variable heißt &quot;frei&quot;, solange sie nicht gebunden wird. Man kann dies rekursiv definieren durch die Funktion $\operatorname{FV} : (\operatorname{Ter}\cup\operatorname{For})\rightarrow \{x_0,\ldots\}$<br /> <br /> * $\operatorname{FV}(x_i) := \{x_i\}$<br /> * $\operatorname{FV}(f_i^k(t_1,\ldots,t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j) = \operatorname{FV}(t_1) \cup \ldots \cup \operatorname{FV}(t_k)$<br /> * $\operatorname{FV}(\bot) := \emptyset$<br /> * $\operatorname{FV}(R_i^k(t_1,\ldots, t_k)) := \bigcup\limits_{j=1}^k\operatorname{FV}(t_j)$<br /> * $\operatorname{FV}(A\wedge B) = \operatorname{FV}(A\vee B) = \operatorname{FV}(A\rightarrow B) := \operatorname{FV}(A)\cup\operatorname{FV}(B)$<br /> * $\operatorname{FV}(\exists_x A) = \operatorname{FV}(\forall_x A) := \operatorname{FV}(A)\backslash\{x\}$<br /> <br /> Diese Funktion deckt alle Möglichkeiten, wie eine Formel gebildet werden kann, ab. Sie gibt genau die Variablen zurück, die nicht irgendwann von einem Quantor gebunden werden. Eine Formel $Q$ heißt '''geschlossen''', wenn $\operatorname{FV}(Q)=\emptyset$.<br /> <br /> == Theorien, Interpretationen, Modelle ==<br /> <br /> 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\}$.<br /> <br /> Bisher reden wir wiederum nur über Sprachen. Zwar haben Formeln eindeutig die Intention, etwas zu bedeuten, aber was das genau ist, wissen wir noch nicht: Bisher haben wir nur '''Syntax'''. Was wir nun brauchen, ist '''Semantik''': Wir definieren, was eine Formel &quot;heißen&quot; soll.<br /> <br /> Zunächst definieren wir, was eine '''Interpretation''' ist. Intuitiv ordnen wir hier einfach Funktionssymbolen und Relationssymbolen &quot;echte&quot; Funktionen und Relationen zu. Zunächst haben wir einen '''Träger''' $D$, das ist die Menge der Objekte, über die wir reden können.<br /> <br /> <br /> 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, &quot;interpretieren&quot; wir sie als das Objekt $\eta(i)$.<br /> <br /> Wir definieren nun rekursiv die Funktion ${\frak I}_\eta$, die Zeichenketten (Variablen, Termen und Formeln) &quot;echte&quot; Objekte zuordnet:<br /> <br /> * Für jede Variable $x_i$ soll gelten ${\frak I}_\eta(x_i) := \eta(i)$.<br /> * Für jedes verwendete Funktionssymbol $f_i^n$ soll ${\frak I}_\eta(f_i^n)$ eine $n$-Stellige Funktion $D^n\rightarrow D$ sein.<br /> * 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.<br /> <br /> 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.</div>

Css