Aussagenlogik, Formel,Prädikat < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:12 Sa 27.04.2013 | | Autor: | Lu- |
| Aufgabe | 1)Gibt es eine Signatur [mm] \sigma, [/mm] sodass =++ eine [mm] \sigma [/mm] Formel ist?
Wahr oder falsch?
2) Wenn [mm] \wedge [/mm] < 0 1 eine [mm] \sigma [/mm] Formel ist, dann ist auch =01 eine [mm] \sigma- [/mm] Formel.
3) Wenn [mm] \phi [/mm] eine aussagenlogische Tautologie ist,
dann gibt es eine Belegung [mm] \beta [/mm] der aussagenlogischen Prädikate, sodass [mm] \overline{\beta} (\phi)=1 [/mm] ist
[mm] 4.\sigma_N [/mm] ist die Signatir mit [mm] \sigma_N^{op}= \{ 0,1,+, *\} [/mm] wobei 0 und 1 nullstellig sind und +,* zweistellig. [mm] \IN [/mm] steht sowohl für die natürlichen Zahlen als auch die [mm] \sigma_N [/mm] Struktur [mm] (\IN, [/mm] 0,1,+,*)
Gilt die [mm] \sigma_N [/mm] Formel [mm] \neg\exists v_0 \exists v_1 \exists v_2 \neg =+v_0 +v_1 v_2 +++v_0 v_1 v_2 [/mm] für die natürlichen Zahlen (d.h. [mm] \IN \models \phi) [/mm] |
1)
JA:
Da + rechts am Rand steht muss es 0 stellig sein.
= ist immer 2 stellig als Metalogisches Symbol.
Also ist dies eine [mm] \sigma-Formel.Und [/mm] es muss eine Signatur geben in der dies erfüllt ist:
z.B.:
Signatur [mm] \sigma [/mm] = [mm] \{ +\}
[/mm]
wobei + interpretiert wird als 0 stellige funktion 1. Und nicht konvetionell als Addition. (was ja in dem Abstraktheitsgrad indem wir uns befinden möglich ist)
2)
Nein:
Signatur ist hier [mm] \sigma [/mm] = [mm] \{<,0,1\}
[/mm]
[mm] \wedge [/mm] ist immer zweistellig oder? [mm] \wedge [/mm] gehört ja nicht in die Signatur sondern getrennt als metalogisches Symbol aufzufassen.
1 steht ganz rechts in der Formel ist also 0 stellig.
Sodass =01 eine [mm] \sigma- [/mm] Formel ist, muss die Stelligkeit 0 sein von der Funktion/Relation 0.
In der [mm] \sigma [/mm] Formel [mm] \wedge [/mm] < 0 1 kann aber auch 0 als 1 stellig intrepretiert werden und < als 0 stellig.
So würde [mm] \wedge [/mm] noch immer zweistellig sein.
3)
Ja
Def.:
Aussagenlogische Prädikate sind Prädikate mit stelligkeit 0.
R [mm] \subseteq \{ () \}
[/mm]
R ist leere Menge (falsch) oder 0 Tupel (wahr)
[mm] \overline{\beta} (R)=\begin{cases} 1, & \mbox{falls } () \in R^M \ \\ 0, & \mbox{sonst} \end{cases}
[/mm]
M.. [mm] \sigma-STruktur
[/mm]
Ein allgemeingültiger aussagenlogischer Satz heißt Tautologie.
Allgemeinlogisch heißt für alle [mm] \sigma- [/mm] Strukturen und alle Belegungen ist [mm] \overline{\beta}(\phi)=1
[/mm]
4. Ist hier nicht ein + zuviel?
Ich denke man wollte raus auf [mm] \forall (v_0, v_1, v_2) [/mm] : [mm] v_0 +(v_1 [/mm] + [mm] v_2)= (v_0+v_1)+v_2
[/mm]
Aber da ist doch ein + in der first order Sprache zu viel?
Darf man hier von der Addition (für diese das Assoziativgesetzt gilt) ausgehen? Oder muss man wieder abstrakter denken?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 So 28.04.2013 | | Autor: | tobit09 |
Hallo Lu-,
> 1)Gibt es eine Signatur [mm]\sigma,[/mm] sodass =++ eine [mm]\sigma[/mm]
> Formel ist?
> 1)
> JA:
![[ok]](/images/smileys/ok.gif "[ok]")
> Da + rechts am Rand steht muss es 0 stellig sein.
> = ist immer 2 stellig als Metalogisches Symbol.
> Also ist dies eine [mm]\sigma-Formel.Und[/mm] es muss eine Signatur
> geben in der dies erfüllt ist:
> z.B.:
> Signatur [mm]\sigma[/mm] = [mm]\{ +\}[/mm]
> wobei + interpretiert wird als 0
> stellige funktion 1. Und nicht konvetionell als Addition.
> (was ja in dem Abstraktheitsgrad indem wir uns befinden
> möglich ist)
Das Beispiel [mm] $\sigma=\{+\}$ [/mm] mit + nullstelliges Funktionssymbol genügt völlig.
> Wahr oder falsch?
> 2) Wenn [mm]\wedge[/mm] < 0 1 eine [mm]\sigma[/mm] Formel ist, dann ist auch
> =01 eine [mm]\sigma-[/mm] Formel.
> 2)
> Nein:
> Signatur ist hier [mm]\sigma[/mm] = [mm]\{<,0,1\}[/mm]
Wir wissen nur [mm] "$\subseteq$", [/mm] nicht "$=$".
> [mm]\wedge[/mm] ist immer zweistellig oder? [mm]\wedge[/mm] gehört ja nicht
> in die Signatur sondern getrennt als metalogisches Symbol
> aufzufassen.
Genau.
> 1 steht ganz rechts in der Formel ist also 0 stellig.
> Sodass =01 eine [mm]\sigma-[/mm] Formel ist, muss die Stelligkeit 0
> sein von der Funktion/Relation 0.
> In der [mm]\sigma[/mm] Formel [mm]\wedge[/mm] < 0 1 kann aber auch 0 als 1
> stellig intrepretiert werden und < als 0 stellig.
> So würde [mm]\wedge[/mm] noch immer zweistellig sein.
Genau.
Gib zum Widerlegen eine konkrete Signatur [mm] $\sigma$ [/mm] an, so dass <01 eine [mm] $\sigma$-Formel [/mm] ist, =01 jedoch nicht.
> 3) Wenn [mm]\phi[/mm] eine aussagenlogische Tautologie ist,
> dann gibt es eine Belegung [mm]\beta[/mm] der aussagenlogischen
> Prädikate, sodass [mm]\overline{\beta} (\phi)=1[/mm] ist
Hier muss ich ein wenig passen, denn ich habe dein Skript gerade nicht zur Hand und weiß nicht, was man unter einer einem aussagenlogischen Satz und einer Belegung von Prädikaten versteht.
> 3)
> Ja
> Def.:
> Aussagenlogische Prädikate sind Prädikate mit stelligkeit
> 0.
> R [mm]\subseteq \{ () \}[/mm]
> R ist leere Menge (falsch) oder 0
> Tupel (wahr)
> [mm]\overline{\beta} (R)=\begin{cases} 1, & \mbox{falls } () \in R^M \ \\ 0, & \mbox{sonst} \end{cases}[/mm]
>
> M.. [mm]\sigma-STruktur[/mm]
>
> Ein allgemeingültiger aussagenlogischer Satz heißt
> Tautologie.
> Allgemeinlogisch heißt für alle [mm]\sigma-[/mm] Strukturen und
> alle Belegungen ist [mm]\overline{\beta}(\phi)=1[/mm]
> [mm]4.\sigma_N[/mm] ist die Signatir mit [mm]\sigma_N^{op}= \{ 0,1,+, *\}[/mm]
> wobei 0 und 1 nullstellig sind und +,* zweistellig. [mm]\IN[/mm]
> steht sowohl für die natürlichen Zahlen als auch die
> [mm]\sigma_N[/mm] Struktur [mm](\IN,[/mm] 0,1,+,*)
> Gilt die [mm]\sigma_N[/mm] Formel [mm]\neg\exists v_0 \exists v_1 \exists v_2 \neg =+v_0 +v_1 v_2 +++v_0 v_1 v_2[/mm]
> für die natürlichen Zahlen (d.h. [mm]\IN \models \phi)[/mm]
> 4. Ist hier nicht ein + zuviel?
> Ich denke man wollte raus auf [mm]\forall (v_0, v_1, v_2)[/mm] :
> [mm]v_0 +(v_1[/mm] + [mm]v_2)= (v_0+v_1)+v_2[/mm]
> Aber da ist doch ein + in
> der first order Sprache zu viel?
So sehe ich das auch.
> Darf man hier von der Addition (für diese das
> Assoziativgesetzt gilt) ausgehen? Oder muss man wieder
> abstrakter denken?
Ich denke: Dass die gewöhnliche Addition natürlicher Zahlen assoziativ ist, darfst du schon als bekannt voraussetzen. Es bleibt also zu überlegen, dass [mm] $M\models\phi$ [/mm] für eine [mm] $\sigma$-Struktur [/mm] M genau dann gilt, wenn die Verknüpfung $+^M$ auf $M$ assoziativ ist. Wenn man möchte, kann man dazu schrittweise die Definition von [mm] $M\models \phi$ [/mm] durchgehen. Sobald man etwas Erfahrung hat, lässt man solche Überlegungen weg.
Viele Grüße
Tobias
|
|
|
|
