eindeutigkeitRelation,Belegung < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:52 Mo 04.04.2016 | | Autor: | sissile |
| Aufgabe | Aussagenlogik:(http://www.logic.univie.ac.at/~muellem3/aussagenlogik.pdf) Seite 2
Definition: Eine Funktion [mm] \beta: [/mm] Var [mm] \rightarrow \{0,1\} [/mm] heißt aussagenlogische Belegung
Definition: Wir definieren eine Relation [mm] \models [/mm] durch folgende Festsetzung. Nämlich, [mm] \models [/mm] ist die Relation zwischen belegungen und Formeln, so daß für alle Belegungen [mm] \beta [/mm] und alle Formeln [mm] \psi, \chi [/mm] und alle Variablen X gelte
(a) [mm] \beta \models [/mm] X genau dann wenn [mm] \beta(X)=1
[/mm]
(b) [mm] \beta \models \neg \psi [/mm] genau dann wenn [mm] \beta \not\models \psi
[/mm]
(c) [mm] \beta \models (\psi \wedge \chi) [/mm] genau dann wenn [mm] \beta \models \psi [/mm] oder [mm] \beta \models \chi
[/mm]
ÜE: Zeigen Sie, daß es genau eine solche Relation [mm] \models [/mm] gibt. |
Hallo,
Ich bin dem mündlichen Hinweis gefolgt die Relation rekursiv zu definieren:
Ich definiere [mm] R(\beta, \phi) [/mm] - mit [mm] \beta [/mm] eine aussagenlogische Belegung und [mm] \phi [/mm] eine aussagenlogische Formel - rekursiv über die Länge des 2.ten Arguments(was ich darf weger der Eindeutigkeit der aussagenlogischen Formeln).
[mm] \phi [/mm] habe Länge 1: [mm] \phi=X [/mm] mit [mm] X\in [/mm] Var
[mm] R(\beta, \phi):= \begin{cases} 1, & \mbox{für } \beta(X)=1 \\ 0, & \mbox{sonst } \end{cases}
[/mm]
Annahme: Für [mm] \phi [/mm] mit Länge höchstens n schon definiert.
Habe [mm] \phi [/mm] Länge n+1:
Fall 1) [mm] \phi= \neg \psi [/mm] mit [mm] \psi [/mm] einer Formel
[mm] R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=0 \\ 0, & \mbox{für } R(\beta, \psi)=1 \end{cases}
[/mm]
da [mm] R(\beta, \psi) [/mm] nach I.Annahme schon definiert macht die Definition Sinn.
Fall 2) [mm] \phi= (\psi \wedge \chi) [/mm] mit [mm] \psi, \chi [/mm] Formeln
[mm] R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=1=R(\beta,\chi) \\ 0, & \mbox{für } R(\beta, \chi) \not= R(\beta, \psi) \end{cases}
[/mm]
Da [mm] R(\beta, \chi) [/mm] sowie [mm] R(\beta, \psi) [/mm] nach I.Annahme schon definiert macht die Definition Sinn.
Wie ich aber nun zeige, dass dies die einzige Relation ist mit den drei Eigenschaften weiß ich nicht.
LG,
sissi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:40 Di 05.04.2016 | | Autor: | sissile |
Ich habe einen Fehler im Fall 1) editiert & würde gerne die Fälligkeit um paar tage verlängern - da es ein Thema ist wo vlt. nicht jeder Interesse hat!
LG,
Sissi
|
|
|
| |
|
Hallo,
Eindeutigkeit zeigst du natürlich mit Induktion nach der Länge der Formel. Das ist rein mechanisch - du löst einfach die Rekursion wieder auf. Allerdings ist bei der Definition in Fall 2) ein Fehler.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:24 Mi 06.04.2016 | | Autor: | sissile |
Hallo,
danke für dein Post!
Fall 2) [mm] \phi= (\psi \wedge \chi) [/mm] mit [mm] \psi, \chi [/mm] Formeln
$ [mm] R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=1 \mbox{und} R(\beta,\chi)=1 \\ 0, & \mbox{sonst} \end{cases} [/mm] $
Frage: Muss ich aber nun nicht noch meine definierte Rekursion mit der definition zusammenbringen? Also das meine soeben definiere Relation auch [mm] \models [/mm] ist?
Mein versuch zur Eindeutigkeit mit Induktion nach der Länge:
1. Die Behauptung gilt für jede Variable.
[mm] R(\beta, [/mm] X)=1 für [mm] \beta(X)=1 [/mm] für X eine Variable
Hängt das dann von der Belegung ab oder wie?
2. Wenn die Behauptung für [mm] \psi [/mm] gilt, so auch für [mm] \neg \psi.
[/mm]
[mm] R(\phi, \neg \psi) [/mm] ist durch [mm] R(\beta, \psi) [/mm] eindeutig bestimmt nach der Definition der Rekursion.
3. Wenn die behauptung für [mm] \psi [/mm] und [mm] \chi [/mm] gilt, so auch für [mm] (\psi \wedge \chi)
[/mm]
[mm] R(\beta, \phi) [/mm] ist wieder durch die Werte von [mm] R(\beta, \phsi) [/mm] und [mm] R(\beta, \chi) [/mm] eindeutig bestimmt nach der Definition der Rekursion.
LG,
sissi
|
|
|
| |
|
> Hallo,
> danke für dein Post!
>
> Fall 2) [mm]\phi= (\psi \wedge \chi)[/mm] mit [mm]\psi, \chi[/mm] Formeln
> [mm]R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=1 \mbox{und} R(\beta,\chi)=1 \\ 0, & \mbox{sonst} \end{cases}[/mm]
>
> Frage: Muss ich aber nun nicht noch meine definierte
> Rekursion mit der definition zusammenbringen? Also das
> meine soeben definiere Relation auch [mm]\models[/mm] ist?
Naja, deine Relation erfüllt doch per Definition die geforderten Eigenschaften von [mm] $\beta$ [/mm] - oder meinst du etwas anderes?
> Mein versuch zur Eindeutigkeit mit Induktion nach der
> Länge:
> 1. Die Behauptung gilt für jede Variable.
Formuliere erst einmal präzise, welche Behauptung wir per Induktion beweisen wollen. Und dann ist es auch sehr leicht.
> [mm]R(\beta,[/mm] X)=1 für [mm]\beta(X)=1[/mm] für X eine Variable
> Hängt das dann von der Belegung ab oder wie?
> 2. Wenn die Behauptung für [mm]\psi[/mm] gilt, so auch für [mm]\neg \psi.[/mm]
>
> [mm]R(\phi, \neg \psi)[/mm] ist durch [mm]R(\beta, \psi)[/mm] eindeutig
> bestimmt nach der Definition der Rekursion.
> 3. Wenn die behauptung für [mm]\psi[/mm] und [mm]\chi[/mm] gilt, so auch
> für [mm](\psi \wedge \chi)[/mm]
> [mm]R(\beta, \phi)[/mm] ist wieder durch
> die Werte von [mm]R(\beta, \phsi)[/mm] und [mm]R(\beta, \chi)[/mm] eindeutig
> bestimmt nach der Definition der Rekursion.
>
> LG,
> sissi
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:52 So 17.04.2016 | | Autor: | sissile |
Hallo;)
> Formuliere erst einmal präzise, welche Behauptung wir per Induktion beweisen wollen. Und dann ist es auch sehr leicht.
Behauptung: Es gibt genau eine Relation R zwischen Belegungen und Formeln die die drei Eigenschaften erfüllt:
-) [mm] \phi \in [/mm] Var:$ [mm] R(\beta, \phi):= \begin{cases} 1, & \mbox{für } \beta(X)=1 \\ 0, & \mbox{sonst } \end{cases} [/mm] $
-) [mm] \phi= \neg \psi: [/mm] $ [mm] R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=0 \\ 0, & \mbox{für } R(\beta, \psi)=1 \end{cases} [/mm] $
-) [mm] \phi=( \psi \wedge \chi): [/mm] $ [mm] R(\beta, \phi):=\begin{cases} 1, & \mbox{für } R(\beta, \psi)=1 \mbox{und} R(\beta,\chi)=1 \\ 0, & \mbox{sonst} \end{cases} [/mm] $
Bew. per induktion über Formeln:
> 1. Die Behauptung gilt für jede Variable.
Durch Eigenschaft 1 ist R eindeutig bestimmt.
> 2. Wenn die Behauptung für $ [mm] \psi [/mm] $ gilt, so auch für $ [mm] \neg \psi. [/mm] $
$ [mm] R(\beta, \neg \psi) [/mm] $ ist durch $ [mm] R(\beta, \psi) [/mm] $ eindeutig
bestimmt nach Eigenschaft 2 und für $ [mm] R(\beta, \psi) [/mm] $ ist R eine eindeutige Relation da [mm] \psi [/mm] weniger Stellen als [mm] \neg \psi [/mm] hat.
> 3. Wenn die behauptung für $ [mm] \psi [/mm] $ und $ [mm] \chi [/mm] $ gilt, so auch
> für $ [mm] (\psi \wedge \chi) [/mm] $
[mm] R(\beta, (\psi \wedge \chi)) [/mm] ist nach Eigenschaft 3 durch [mm] R(\beta, \chi) [/mm] und [mm] R(\beta, \psi) [/mm] eindeutig bestimmt. Und für [mm] R(\beta, \chi) [/mm] und [mm] R(\beta, \psi) [/mm] ist R eine eindeutige Relation da [mm] \chi [/mm] und [mm] \psi [/mm] weniger Stellen als [mm] (\psi \wedge \chi) [/mm] hat.
Kann man das so sagen?
LG,
sissi
|
|
|
| |
|
Im Prinzip ist das so genau richtig. Aber eigentlich braucht man für Induktion eine Aussage über natürliche Zahlen. Logisch etwas einwandfreier wäre es also so: Seien $R,R'$ zwei Relationen, die den Anforderungen genügen. Per Induktion zeigt man die Aussage: Für alle $n$ gilt: Ist [mm] $\psi$ [/mm] eine Formel der Länge $n$, so gilt [mm] $R(\beta,\psi)\iff R'(\beta,\psi)$. [/mm] Und das geht dann genau so, wie du es hier machen wolltest.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:58 Mo 18.04.2016 | | Autor: | sissile |
Danke**
LG,
sissi
|
|
|
|
