Prädikatenlogik Termstruktur < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:57 So 11.01.2015 | | Autor: | Steffi88 |
| Aufgabe | Sei T = (L, Σ) die Theorie mit L = L(≤; S; 0) und
Σ = [mm] $\{\sigma_{lin}, \forall x(0\le x), \forall x(x < S(x)), \forall x\forall y\exists z(x < y \rightarrow x < z \wedge z < y)\}$,
[/mm]
wobei der Satz [mm] \sigma_{lin} [/mm] ausdrücke, dass ≤ eine totale Ordnung ist. Dabei verwenden wir die Schreibweise t < t' als Abkürzung für t ≤ t' ∧ ¬t = t'.
(a) Beschreiben Sie die Termstruktur von T.
(b) Folgern Sie aus (a), dass die Termstruktur von T kein Modell von T ist.
(c) Wird die Termstruktur ein Modell von T, wenn man den letzten Satz von Σ weglässt? |
Hallo zusammen,
frohes neues Jahr euch allen (nachträglich) :)
Ich habe bald eine Klausur in Logik und stolpere bei alt Klausuren immer wieder über eine ähnliche Aufgabe (obige)... Leider verstehe ich diese überhaupt nicht und finde auch nichts dazu in unsere Script... Das ist zwar eh etwas spärlich ausgefallen, steht aber normal schon alles drin, bzw sollte... Habe auch keine Lösungen zu den Klausuren, deshalb hoffe ich das mir hier einer helfen kann.
Ist "Theorie" und "Sprache" nicht eigentlich das selbe, bzw. die Theorie ist eben ein teil der ganzen Sprache?
Was genau bedeutet denn beschreiben sie die Termstruktur? Die Struktur ist doch in den Klammer gegeben, oder soll man dies irgendwie anders strukturiert aufschreiben?
Wie ihr seht, hatten wir das nicht so in der Uni... (oder ich habe es nicht mitbekommen :) )
Wäre super wenn mir hier jemand helfen könnte, kam bisher auf jeder Altklausur eine ähnliche Frage dran und das sind dann fast schon sichere Punkte :D
Danköööö
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:38 So 11.01.2015 | | Autor: | tobit09 |
Hallo Steffi88!
(Ich habe deine Formel hinter dem [mm] $\Sigma=$ [/mm] so editiert, dass man sie lesen kann. Wenn du mit der Maus darüber fährst, siehst du, was du für eine korrekte Darstellung eingeben musst.)
> Sei T = (L, Σ) die Theorie mit L = L(≤; S; 0) und
> Σ = [mm]\{\sigma_{lin}, \forall x(0\le x), \forall x(x < S(x)), \forall x\forall y\exists z(x < y \rightarrow x < z \wedge z < y)\}[/mm],
>
> wobei der Satz [mm]\sigma_{lin}[/mm] ausdrücke, dass ≤ eine
> totale Ordnung ist. Dabei verwenden wir die Schreibweise t
> < t' als Abkürzung für t ≤ t' ∧ ¬t = t'.
> (a) Beschreiben Sie die Termstruktur von T.
> (b) Folgern Sie aus (a), dass die Termstruktur von T kein
> Modell von T ist.
> (c) Wird die Termstruktur ein Modell von T, wenn man den
> letzten Satz von Σ weglässt?
> Ich habe bald eine Klausur in Logik und stolpere bei alt
> Klausuren immer wieder über eine ähnliche Aufgabe
> (obige)...
Stammt sie vom gleichen Dozenten, der deine aktuelle Vorlesung hält?
Möglicherweise verwendet der Ersteller der Altklausur andere Notationen als dein Dozent?
Falls ihr z.B. den Begriff einer Termstruktur nicht hattet, wird er bestimmt auch nicht in der Klausur vorausgesetzt.
Möglicherweise sind die aktuellen (leichteren) Übungsaufgaben ein besserer Hinweis auf das, was dran kommen könnte.
> Leider verstehe ich diese überhaupt nicht und
> finde auch nichts dazu in unsere Script... Das ist zwar eh
> etwas spärlich ausgefallen, steht aber normal schon alles
> drin, bzw sollte...
Falls das Skript öffentlich zugänglich ist: Könntest du es bitte verlinken?
> Ist "Theorie" und "Sprache" nicht eigentlich das selbe,
Nein, keineswegs.
Diese Grundbegriffe musst du natürlich in der Klausur beherrschen.
Arbeite ihre Definitionen und grundlegenden Beispiele nach.
> bzw. die Theorie ist eben ein teil der ganzen Sprache?
Nicht wirklich.
Sei L eine Sprache (der Prädikatenlogik der ersten Stufe).
Eine L-Theorie definiert man üblicherweise als eine Menge von $L$-Sätzen.
(Der Autor der Aufgabenstellung scheint hingegen unter einer Theorie ein Paar [mm] $(L,\Sigma)$ [/mm] zu verstehen, wobei $L$ eine Sprache und [mm] $\Sigma$ [/mm] eine Menge von $L$-Sätzen ist.
Daher ist es am besten, du verlinkst euer Skript, damit man auf eure Konventionen eingehen kann.)
> Was genau bedeutet denn beschreiben sie die Termstruktur?
Nun gilt es, den Begriff der Termstruktur nachzuschlagen, um ihn dann auf das Beispiel der Aufgabenstellung anzuwenden.
Wenn ihr diesen Begriff nicht hattet, wird er wohl kaum in der Klausur vorausgesetzt.
> Die Struktur ist doch in den Klammer gegeben, oder soll man
> dies irgendwie anders strukturiert aufschreiben?
Hinter dem [mm] $\Sigma=$ [/mm] ist keine Struktur angegeben, sondern eine Menge von vier L-Sätzen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:51 Mo 12.01.2015 | | Autor: | Steffi88 |
Danke erstmal fpr deine Antwort!!
Wir haben kein wirkliches Script, aber er orientiert sich an diesem hier:
http://www.math.uni-heidelberg.de/logic/md/lehre/mathlogik.pdf
Dort steht auch ein kleiner Absatz über Termstruktur, werde aber nicht wirklich so ganz schlau draus :/
Ja, die Klausuren sind alle vom selben Dozenten :D, deshalb wäre es natürlich super wenn ich die Aufgabe verstehen würde!!
Danke schonmal
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:16 Mo 12.01.2015 | | Autor: | tobit09 |
> Wir haben kein wirkliches Script, aber er orientiert sich
> an diesem hier:
>
> http://www.math.uni-heidelberg.de/logic/md/lehre/mathlogik.pdf
Danke!
> Dort steht auch ein kleiner Absatz über Termstruktur,
Ich nehme mal an, du meinst Abschnitt 4.8.1.
> werde aber nicht wirklich so ganz schlau draus :/
Kannst du etwas näher eingrenzen, was dir daran unklar ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:48 Mo 12.01.2015 | | Autor: | tobit09 |
> Sei T = (L, Σ) die Theorie mit L = L(≤; S; 0) und
> Σ = [mm]\{\sigma_{lin}, \forall x(0\le x), \forall x(x < S(x)), \forall x\forall y\exists z(x < y \rightarrow x < z \wedge z < y)\}[/mm],
>
> wobei der Satz [mm]\sigma_{lin}[/mm] ausdrücke, dass ≤ eine
> totale Ordnung ist. Dabei verwenden wir die Schreibweise t
> < t' als Abkürzung für t ≤ t' ∧ ¬t = t'.
> (a) Beschreiben Sie die Termstruktur von T.
> (b) Folgern Sie aus (a), dass die Termstruktur von T kein
> Modell von T ist.
> (c) Wird die Termstruktur ein Modell von T, wenn man den
> letzten Satz von Σ weglässt?
(b) und (c) lassen sich leider erst dann bearbeiten, wenn (a) gelöst ist.
Ich schlage zunächst zwei Vorübungen vor:
Vorübung 1:
Gib eine beliebige $L$-Struktur an.
Diese Vorübung dient dazu, den Begriff der L-Struktur zu sichern und damit die Voraussetzung für die Vorübung 2 zu schaffen.
Vorübung 2:
Gib ein Modell von T an (d.h. gib eine L-Struktur [mm] $\mathfrak{A}$ [/mm] an, so dass [mm] $\mathfrak{A}\models [/mm] T$ gilt).
Diese Vorübung hat mehrere Zwecke:
- Den Begriff des Modells sichern.
- Eine Anschauung der allgemeinen Bedeutung von [mm] $\mathfrak{A}\models [/mm] T$ sichern.
- Mit den Formeln aus der Definition von [mm] $\Sigma$ [/mm] vertraut werden.
- Man wird ein Modell von T benötigen, um später zu verifizieren, dass die Termstruktur von T wie behauptet aussieht.
Mit der eigentlichen Aufgabe (a) kannst du recht stumpf beginnen, indem du der Beschreibung in Abschnitt 4.8.1 des Skriptes folgst:
1. Bestimme die Menge K aller konstanten L-Terme.
2. Bestimme die im Skript erklärte Äquivalenzrelation auf K, nach der je zwei L-Terme s und t genau dann äquivalent sind, wenn [mm] $T\vdash [/mm] s=t$ gilt.
(Nach dem Vollständigkeitssatz ist die syntaktische Aussage [mm] $T\vdash [/mm] s=t$ äquivalent zur semantischen Aussage [mm] $T\models [/mm] s=t$. Du kannst dir also aussuchen, welche der beiden Varianten du verwenden möchtest.)
3. Bestimme zu jedem Term s die Äquivalenzklasse [mm] $\overline{s}$.
[/mm]
4. Bestimme die Menge A der Äquivalenzklassen. Sie wird der Individuenbereich (Träger) der Termstruktur.
5. Bestimme die Interpretationen der Zeichen [mm] $\le,S,0$ [/mm] in der Termstruktur.
Der schwierigsten Teile sind 2. und der [mm] "$\le$-Teil" [/mm] von 5.
Mir ist klar, dass du nicht alles selbstständig schaffen wirst.
Aber zumindest die Vorübung 1 und der 1. Schritt der eigentlichen Aufgabe sollten machbar sein.
Lass uns auch an deinen Überlegungen zu den weiteren Teilen teilhaben.
Dass du zunächst die vorkommenden Grundbegriffe anhand der Definitionen und Beispiele aus Vorlesung/Skript verstehen musst, versteht sich eigentlich von selber.
Konkrete Fragen zu Unklarheiten kannst du natürlich gerne stellen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:45 Di 13.01.2015 | | Autor: | Steffi88 |
Vielen Dank, werde mich an den Vorübungen versuchen. Leider habe ich so viele Sachen zu lernen das es zeitlich eng wird :)
Deshalb mein versuch eine "fast" sichere Aufgabe "vorzubereiten" um die Punkte einzusacken. Aber ob ich da selber noch drauf komme :*/
Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:19 Mi 14.01.2015 | | Autor: | Steffi88 |
soooo,
also zu den Vorübungen :)
Wenn man eine Formel wie z.B. F = [mm] \forall [/mm] x P(x, f(x)) hat, wäre z.B. eine passende Struktur:
[mm] U_{A} [/mm] = [mm] \IN,
[/mm]
[mm] P_{A}(x, [/mm] y) = (x < y)
[mm] f_{A}(x) [/mm] = x + 1
F gilt für A welches ja soviel bedeutet wie: für alle natürlichen Zahlen n ist n kleiner als sein Nachfolger n + 1. Da es immer wahr ist, ist es auch direkt ein Modell von F.
Sooo weit so gut, ist auch soweit verständlich, aber leider nicht anwendbar auf die komplexe Formel in meiner Aufgabe :/
Gibt es da noch einen Tipp :D
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:51 Do 15.01.2015 | | Autor: | oyram |
Ich sitze an derselben Aufgabe...
Da die Theorie keine konstanten Terme hat, ist [mm] K_T [/mm] schonmal leer. Einzige Relation ist kleinergleich, einzige Funktion ist Nachfolger und einzige Konstante ist 0.
Hab ich das jetzt vollkommen falsch verstanden?
Ich dachte, die Termstruktur sei jetzt:
[mm] A_T [/mm] = (<=;S;0)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:37 Do 15.01.2015 | | Autor: | tobit09 |
Hallo oyram und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Da die Theorie keine konstanten Terme hat,
Doch. Die Sprache L aus der Aufgabenstellung hat z.B. die konstanten Terme 0 und S(S(S(0))).
> ist [mm]K_T[/mm] schonmal
> leer.
Folgerichtig.
> Einzige Relation ist kleinergleich, einzige Funktion
> ist Nachfolger und einzige Konstante ist 0.
[mm] $\le$ [/mm] ist ein zweistelliges Relations-Zeichen (=Prädikats-Zeichen), $S$ ist ein einstelliges Funktionszeichen und 0 ist eine Konstante.
Die Anschauung, dass [mm] $\le$ [/mm] für "kleinergleich" und $S$ für "Nachfolger" steht, kann helfen, muss aber natürlich nicht für jede L-Struktur passen.
> Ich dachte, die Termstruktur sei jetzt:
> [mm]A_T[/mm] = (<=;S;0)
Ich kann überhaupt keine L-Struktur aus deiner Angabe herauslesen.
Weder weiß ich, was du für das Universum (=Träger) der Termstruktur hältst, noch weiß ich, wie die Interpretationen der Zeichen [mm] $\le$, [/mm] $S$ und $0$ in der Termstruktur lauten sollen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:09 Do 15.01.2015 | | Autor: | tobit09 |
> also zu den Vorübungen :)
>
> Wenn man eine Formel wie z.B. F = [mm]\forall[/mm] x P(x, f(x)) hat,
> wäre z.B. eine passende Struktur:
> [mm]U_{A}[/mm] = [mm]\IN,[/mm]
> [mm]P_{A}(x,[/mm] y) = (x < y)
> [mm]f_{A}(x)[/mm] = x + 1
Du betrachtest also L=L(P,f) mit einem zweistelligen Prädikatszeichen P und einem einstelligen Funktionszeichen f.
Dann ist die von dir oben erklärte Struktur in der Tat ein Modell von F.
> Sooo weit so gut, ist auch soweit verständlich, aber
> leider nicht anwendbar auf die komplexe Formel in meiner
> Aufgabe :/
Welche Formel meinst du mit "die komplexe Formel"?
Vielleicht folgende?
[mm] $\forall x\forall y\exists [/mm] z(x < y [mm] \rightarrow [/mm] x < z [mm] \wedge [/mm] z < y)$
Diese Formel ist logisch äquivalent zu:
[mm] $\forall x\forall [/mm] y [mm] (x
In Worten:
Für alle x und y mit x<y existiert ein z mit $x<z<y$.
Anschaulich bedeutet $x<z<y$ dabei: "z liegt zwischen x und y".
Grob gesagt besagt die Formel, dass zwischen je zwei "Punkten" stets ein weiterer "Punkt" liegt.
> Gibt es da noch einen Tipp :D
"Zwischen je zwei Punkten liegt ein weiterer Punkt" sollte dich an dichte lineare Ordnungen erinnern.
Kennst du eine dichte lineare Ordnung?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:44 Do 15.01.2015 | | Autor: | tobit09 |
Da ich vom morgigen Freitag bis Sonntag voraussichtlich nicht im Matheraum sein kann, verrate ich hier ausnahmsweise Teile der Lösung.
> Vorübung 2:
>
> Gib ein Modell von T an (d.h. gib eine L-Struktur
> [mm]\mathfrak{A}[/mm] an, so dass [mm]\mathfrak{A}\models T[/mm] gilt).
Ein Modell von T ist gegeben durch die L-Struktur [mm] $\mathfrak{A}$ [/mm] mit Universum (=Träger) [mm] $\IQ_{\ge0}=\{q\in\IQ\;|\;q\ge0\}$ [/mm] und folgenden Interpretationen der Zeichen aus $L$:
[mm] $\le^\mathfrak{A}$ [/mm] sei die gewöhnliche [mm] $\le$-Ordnung [/mm] (eingeschränkt) auf [mm] $\IQ_{\ge0}$.
[/mm]
[mm] $S^\mathfrak{A}(q):=q+1$ [/mm] für alle [mm] $q\in\IQ$.
[/mm]
[mm] $0^\mathfrak{A}$ [/mm] sei die rationale Zahl 0.
Macht euch klar, dass [mm] $\mathfrak{A}$ [/mm] tatsächlich ein Modell von T ist.
> Mit der eigentlichen Aufgabe (a) kannst du recht stumpf
> beginnen, indem du der Beschreibung in Abschnitt 4.8.1 des
> Skriptes folgst:
>
> 1. Bestimme die Menge K aller konstanten L-Terme.
[mm] $K=\{0,S(0),S(S(0)),S(S(S(0))),S(S(S(S(0)))),\ldots\}=\{S^n(0)\;|\;n\in\IN_0\}$,
[/mm]
wobei [mm] $S^n(0)$ [/mm] eine Kurzschreibweise für "$S(S(S...(S(S(0))...))$ mit $n$ vielen S" sei.
> 2. Bestimme die im Skript erklärte Äquivalenzrelation
> auf K, nach der je zwei L-Terme s und t genau dann
> äquivalent sind, wenn [mm]T\vdash s=t[/mm] gilt.
> (Nach dem Vollständigkeitssatz ist die syntaktische
> Aussage [mm]T\vdash s=t[/mm] äquivalent zur semantischen Aussage
> [mm]T\models s=t[/mm]. Du kannst dir also aussuchen, welche der
> beiden Varianten du verwenden möchtest.)
Für [mm] $n,m\in\IN_0$ [/mm] gilt
[mm] $T\vdash S^n(0)=S^m(0)$
[/mm]
genau dann, wenn schon $n=m$ gilt.
Überlegt dazu:
- Es gilt [mm] $T\vdash S^n(0)=S^n(0)$ [/mm] für alle [mm] $n\in\IN_0$.
[/mm]
- Für [mm] $n\not=m$ [/mm] gilt [mm] $T\not\models S^n(0)=S^m(0)$. [/mm] (Betrachtet dazu das Modell von $T$ aus der Vorübung 2.)
> 3. Bestimme zu jedem
konstanten
> Term s die Äquivalenzklasse
> [mm]\overline{s}[/mm].
[mm] $\overline{S^n(0)}=\{S^n(0)\}=:a_n$ [/mm] für alle [mm] $n\in\IN_0$
[/mm]
> 4. Bestimme die Menge A der Äquivalenzklassen. Sie wird
> der Individuenbereich (Träger) der Termstruktur.
[mm] $A=\{\{S^n(0)\}\;|\;n\in\IN_0\}=\{a_n\;|\;n\in\IN_0\}$
[/mm]
> 5. Bestimme die Interpretationen der Zeichen [mm]\le,S,0[/mm] in
> der Termstruktur.
[mm] $a_n\le^\mathfrak{A}a_m\iff n\le [/mm] m$ für alle [mm] $n,m\in\IN_0$
[/mm]
[mm] $S^\mathfrak{A}(a_n)=a_{n+1}$ [/mm] für alle [mm] $n\in\IN_0$
[/mm]
[mm] $0^\mathfrak{A}=a_0$.
[/mm]
Eure Aufgaben sind nun:
- Begründet diese Überlegungen.
- b) und c).
Viel Erfolg!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:42 Sa 17.01.2015 | | Autor: | Steffi88 |
Hi Tobi,
vielen Dank für deine Hilfe!!! Habe es noch nicht 100% verstanden, ca 80% :D Werde mir deine Schritte noch einmal anschauen und versuchen bei anderen Aufgaben so vorzugehen, dann sollte das klappen :)
|
|
|
|
