Formale Systeme < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (Grenzen der Mathematik, Hoffmann, 2011)
Definition 2.5:
Die Menge der aussagenlogischen Formeln über dem Variablenvorrat [mm] $V=\{A_1,A_2,A_3,\ldots\}$ [/mm] ist rekursiv definiert:
[mm] \bullet [/mm] 0 und 1 sind Formeln.
[mm] \bullet [/mm] Jede Variable aus der Menge V ist eine Formel.
[mm] \bullet [/mm] Sind [mm] $\phi$ [/mm] und [mm] $\psi$ [/mm] Formeln, dann sind es auch [mm] $(\neg\phi),(\phi\wedge\psi), (\phi\vee\psi), (\psi\to\psi), (\phi\leftrightarrow\psi), (\phi\nleftrightarrow\psi)$
Definition 2.6:
Sei $\phi$ eine aussagenlogische Formel. $A_1,\ldots,A_n$ bezeichne die in $\phi$ vorkommenden Variablen. Dann heißt jede Abbildung $I:\{A_1,\ldots\,A_n\}\to\{0,1\}$ eine Interpretation von $\phi$.
Definition 2.7:
$\phi$ und $\psi$ seien aussagenlogische Formeln und I eine Interpretation. Die Semantik der Aussagenlogik ist durch die Modellrelation $\models$ gegeben, die induktiv über dem Formelaufbau definiert ist:
$I\models1$
$I\not\models0$
$I \models A_i : \gdw I(A_i)=1$
$I\models(\neg\phi):\gdw I\not\models\phi$
$I\models (\phi\wedge\psi):\gdw I\models\phi$ und $I\models\psi$
usw.
Eine Interpretation I mit $I\models\phi$ heißt Modell für $\phi$.
Hallo zusammen,
meine Fragen beziehen sich auf die Def. 2.7.
$I\models1$ und $I\not\models0$ sind doch erstmal nur Zeichenketten ohne weitere Bedeutung. Wie hat man diese zu interpretieren? Die Zeile $I \models A_i : \gdw I(A_i)=1$ ist für mich, wie ich meine verständlich. Das heißt, nimmt die Funktion I für eine Formel aus der Variablen Menge V den Wert 1 an, dann schreibt man kurz $I \models A_i$.
Mit $I\models(\neg\phi):\gdw I\not\models\phi$ habe ich wieder so meine Schwierigkeiten. Meiner Meinung nach ist zu dem Zeitpunkt nicht klar was $I\not\models\phi$ bedeutet.
Angenommen ich gebe $A_1$ vor, dann ist $\phi = \neg A_1$ auch eine Formel und man könnte $I\models (\neg A_1)$ schreiben und dann sagen es bedeute $I\not\models A_1$. Aber wie dann weiter.
Für mich würde eher folgendes Sinn machen
$I \models A_i : \gdw I(A_i)=1$
$I \models \neg A_i : \gdw I(A_i)=0$
$I\not\models\phi:\gdw I\models(\neg\phi)$
Hat man nun einen Ausdruck $I\not\models\phi$ gegeben und sich fragt was das eigentlich heißt, sieht man es beudeutet $I\models(\neg\phi)$. Hat man die Formel entsprechend runtergebrochen auf den Variablenvorrat V kann man bspw. sagen für $\phi=A_1$ bedeutet $I \models \neg A_1$ soviel wie $I(A_i)=0$. Das man jede Formel in Teile $I\models A_i$ bzw $I\not\models A_i$ aufsplitten kann, liegt ja am induktiven Aufbau der Modellrelation.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:09 Sa 20.08.2022 | | Autor: | tobit09 |
Hallo KarlAugust und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
(Vorweg eine Korrektur zu Hoffmanns Definition 2.6, ohne die Definition 2.7 nicht funktioniert: Hier sollen [mm] $A_1,\ldots,A_n$ [/mm] wohl kaum genau die in [mm] $\phi$ [/mm] vorkommenden Variablen sein, sondern eine Obermenge der in [mm] $\phi$ [/mm] vorkommenden Variablen bilden, d.h. alle in [mm] $\phi$ [/mm] vorkommenden Variablen sollen unter den Variablen [mm] $A_1,\ldots,A_n$ [/mm] sein.)
Das Ziel von Definition 2.7 ist, für alle aussagenlogischen Formeln [mm] $\phi$ [/mm] und zugehörige Interpretationen $I$ festzulegen, ob jeweils [mm] $I\models\phi$ [/mm] gilt oder nicht. Die Eigenschaft [mm] $I\models\phi$ [/mm] kann man sich jeweils vorstellen als "unter der Interpretation $I$ ist [mm] $\phi$ [/mm] wahr".
> [mm]I\models1[/mm] und [mm]I\not\models0[/mm] sind doch erstmal nur
> Zeichenketten ohne weitere Bedeutung. Wie hat man diese zu
> interpretieren?
Die Festlegung [mm] $I\models [/mm] 1$ stellt sicher, dass [mm] $I\models\phi$ [/mm] zumindest für die Formel [mm] $\phi:=1$ [/mm] und alle Interpretationen $I$ von [mm] $\phi$ [/mm] gilt. Die Formel $1$ ist also unter jeder Interpretation stets wahr. (Das ist der Sinn dieser besonderen Formel 1, dass man sie sich stets ohne Ausnahme als wahr vorstellen kann.)
Die Festlegung [mm] $I\not\models [/mm] 0$ meint, dass [mm] $I\models \phi$ [/mm] für die Formel [mm] $\phi:=0$ [/mm] und alle Interpretationen $I$ von [mm] $\phi$ [/mm] NICHT gelten solle. Die Formel 0 ist also sozusagen unter allen Interpretationen stets falsch.
> Mit [mm]I\models(\neg\phi):\gdw I\not\models\phi[/mm] habe ich
> wieder so meine Schwierigkeiten. Meiner Meinung nach ist zu
> dem Zeitpunkt nicht klar was [mm]I\not\models\phi[/mm] bedeutet.
Mit [mm] $I\not\models\phi$ [/mm] meint Hoffmann offenbar die Aussage [mm] "$I\models\phi$ [/mm] gilt NICHT".
> Angenommen ich gebe [mm]A_1[/mm] vor, dann ist [mm]\phi = \neg A_1[/mm] auch
> eine Formel und man könnte [mm]I\models (\neg A_1)[/mm] schreiben
> und dann sagen es bedeute [mm]I\not\models A_1[/mm].
Genau.
> Aber wie dann
> weiter.
[mm] $I\not\models A_1$ [/mm] bedeutet ja [mm] "$I\models A_1$ [/mm] gilt NICHT" und damit [mm] "$I(A_1)=1$ [/mm] gilt NICHT", was wiederum gleichbedeutend ist mit [mm] $I(A_1)=0$.
[/mm]
> Für mich würde eher folgendes Sinn machen
>
> [mm]I \models A_i : \gdw I(A_i)=1[/mm]
> [mm]I \models \neg A_i : \gdw I(A_i)=0[/mm]
>
> [mm]I\not\models\phi:\gdw I\models(\neg\phi)[/mm]
>
> Hat man nun einen Ausdruck [mm]I\not\models\phi[/mm] gegeben und
> sich fragt was das eigentlich heißt, sieht man es
> beudeutet [mm]I\models(\neg\phi)[/mm]. Hat man die Formel
> entsprechend runtergebrochen auf den Variablenvorrat V kann
> man bspw. sagen für [mm]\phi=A_1[/mm] bedeutet [mm]I \models \neg A_1[/mm]
> soviel wie [mm]I(A_i)=0[/mm]. Das man jede Formel in Teile [mm]I\models A_i[/mm]
> bzw [mm]I\not\models A_i[/mm] aufsplitten kann, liegt ja am
> induktiven Aufbau der Modellrelation.
Deine Vorgehensweise wäre auch sinnvoll, wenn man nur für Formeln [mm] $\phi$ [/mm] der Form [mm] $\phi=A_i$ [/mm] oder [mm] $\phi=\neg A_i$ [/mm] festlegen wollte, ob [mm] $I\models\phi$ [/mm] bzw. [mm] $I\not\models\phi$ [/mm] gilt.
Was ist aber z.B. mit der Formel [mm] $\phi:=(A_2\wedge (\neg(A_1\wedge [/mm] 0)))$ unter der Interpretation [mm] $I:\{A_1,A_2\}\to\{0,1\}$ [/mm] mit [mm] $I(A_1)=1$ [/mm] und [mm] $I(A_2)=1$?
[/mm]
Deinem Vorschlag kann ich nicht entnehmen, ob [mm] $I\models\phi$ [/mm] gelten soll oder nicht.
Nach Hoffmanns Vorgehensweise hingegen (unter Berücksichtigung meiner Korrektur zu 2.6) ist das klar:
Nach Definition 2.7 gilt [mm] $I\models A_1$, [/mm] aber NICHT [mm] $I\models [/mm] 0$.
Damit gilt wiederum nach Definition 2.7 NICHT [mm] $I\models (A_1\wedge [/mm] 0)$.
Damit gilt wiederum nach Definition 2.7 [mm] $I\models(\neg(A_1\wedge [/mm] 0))$.
Außerdem gilt nach Definition 2.7 [mm] $I\models A_2$.
[/mm]
Zusammengenommen erhalten wir, dass [mm] $I\models(A_2\wedge (\neg(A_1\wedge [/mm] 0)))$.
Ist damit das Prinzip dieser rekursiven Definition klargeworden?
Wenn nicht, frage gerne nach! 
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
danke für die ausführliche Antwort.
"Vorweg eine Korrektur zu Hoffmanns Definition 2.6, ohne die Definition 2.7 nicht funktioniert..."
Meiner Meinung nach ist die vom Autor gewähle Definition 2.6. korrekt. Wenn ich deinen Einwänden folge komme ich zu dem Schluss, dass $I$ keine Funkion wäre, weil man nicht jeder Variablen des Wertebereichs einen Funktionswert zuordnen kann.
"Das Ziel von Definition 2.7 ist, für alle aussagenlogischen Formeln $ [mm] \phi [/mm] $ und zugehörige Interpretationen $ I $ festzulegen, ob jeweils $ [mm] I\models\phi [/mm] $ gilt oder nicht. Die Eigenschaft $ [mm] I\models\phi [/mm] $ kann man sich jeweils vorstellen als "unter der Interpretation $ I $ ist $ [mm] \phi [/mm] $ wahr". "
Also nehmen wir an die Zeichenkette [mm] $I\models\phi$ [/mm] bedeutet "unter der Interpretation $ I $ ist $ [mm] \phi [/mm] $ wahr" genauso wie [mm] $I\not\models\phi:\gdw$ [/mm] "unter der Interpretation $ I $ ist $ [mm] \phi [/mm] $ falsch" bedeutet. Dann verstehe ich jetzt, dass man die Bedeutung von [mm] $I\models (\neg\phi)$ [/mm] über [mm] $I\not\models\phi$ [/mm] definiert.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:32 Di 23.08.2022 | | Autor: | tobit09 |
Hi KarlAugust,
> "Vorweg eine Korrektur zu Hoffmanns Definition 2.6, ohne
> die Definition 2.7 nicht funktioniert..."
> Meiner Meinung nach ist die vom Autor gewähle Definition
> 2.6. korrekt.
Würde man Hoffmanns Definition 2.6 wörtlich folgen, wäre z.B. [mm] $I\colon\{A_1,A_2\}\to\{0,1\}$ [/mm] mit [mm] $I(A_1)=1$ [/mm] und [mm] $I(A_2)=1$ [/mm] aus meiner vorherigen Antwort KEINE Interpretation der Formel [mm] $(\neg(A_1\wedge [/mm] 0))$, weil [mm] $A_2$ [/mm] nicht unter den in der Formel vorkommenden Variablen ist.
Dann würde der Ausdruck [mm] $I\models (\neg(A_1\wedge [/mm] 0))$ undefiniert bleiben, weil [mm] $I\models\phi$ [/mm] bzw. [mm] $I\not\models\phi$ [/mm] in Definition 2.7 jeweils nur für Interpretationen von [mm] $\phi$ [/mm] festgelegt wird.
Damit bräche dann die rekursive Definition 2.7 zusammen: Um festzulegen, ob [mm] $I\models(A_2\wedge (\neg(A_1\wedge [/mm] 0)))$ gelten soll oder nicht, müssen wir festgelegt haben, ob [mm] $I\models (\neg(A_1\wedge [/mm] 0))$ gilt.
> Wenn ich deinen Einwänden folge komme ich zu
> dem Schluss, dass [mm]I[/mm] keine Funkion wäre, weil man nicht
> jeder Variablen des Wertebereichs einen Funktionswert
> zuordnen kann.
Leider verstehe ich deine Gedanken hier nicht.
Wo siehst du ein Problem?
Warum soll es problematisch sein, jeder Variablen des Definitionsbereichs (du meinst Definitionsbereich statt Wertebereich, oder?) eine der beiden Werte 0 oder 1 zuzuordnen?
> "Das Ziel von Definition 2.7 ist, für alle
> aussagenlogischen Formeln [mm]\phi[/mm] und zugehörige
> Interpretationen [mm]I[/mm] festzulegen, ob jeweils [mm]I\models\phi[/mm]
> gilt oder nicht. Die Eigenschaft [mm]I\models\phi[/mm] kann man sich
> jeweils vorstellen als "unter der Interpretation [mm]I[/mm] ist [mm]\phi[/mm]
> wahr". "
> Also nehmen wir an die Zeichenkette [mm]I\models\phi[/mm] bedeutet
> "unter der Interpretation [mm]I[/mm] ist [mm]\phi[/mm] wahr" genauso wie
> [mm]I\not\models\phi:\gdw[/mm] "unter der Interpretation [mm]I[/mm] ist [mm]\phi[/mm]
> falsch" bedeutet. Dann verstehe ich jetzt, dass man die
> Bedeutung von [mm]I\models (\neg\phi)[/mm] über [mm]I\not\models\phi[/mm]
> definiert.
So kann man sich das vorstellen, genau.
Von einem logischen Standpunkt aus ist die Definition 2.7 maßgeblich; es handelt sich bei den "Erklärungen" mit wahr und falsch nur um Veranschaulichungen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:14 Mi 24.08.2022 | | Autor: | KarlAugust |
"...wäre z.B. $ [mm] I\colon\{A_1,A_2\}\to\{0,1\} [/mm] $ mit $ [mm] I(A_1)=1 [/mm] $ und $ [mm] I(A_2)=1 [/mm] $ aus meiner vorherigen Antwort KEINE Interpretation der Formel $ [mm] (\neg(A_1\wedge [/mm] 0)) $, weil $ [mm] A_2 [/mm] $ nicht unter den in der Formel vorkommenden Variablen ist."
Verstehe jetzt deinen Punkt. Allerdings glaube ich dass das [mm] $\phi$ [/mm] aus "Eine Interpretation I mit $ [mm] I\models\phi [/mm] $ heißt Modell für $ [mm] \phi [/mm] $." nichts mit dem [mm] $\phi$ [/mm] aus dem Formelaufbau zu tun hat. Für dein Bsp. wäre [mm] $\phi:= (A_2\wedge (\neg(A_1\wedge [/mm] 0))) $. Möchte man verifizieren ob die Interpretation von [mm] $\phi$ [/mm] auch ein Modell für [mm] $\phi$ [/mm] ist, setzt man [mm] $\varphi [/mm] = [mm] A_2, \psi [/mm] = [mm] \neg(A_1\wedge [/mm] 0)$, dann muss $I$ keine Interpretation mehr für [mm] $\varphi, \psi$ [/mm] sein um $ [mm] I\models\varphi [/mm] $ und $ [mm] I\models\psi [/mm] $ auswerten zu können.
"Warum soll es problematisch sein, jeder Variablen des Definitionsbereichs (du meinst Definitionsbereich statt Wertebereich, oder?) eine der beiden Werte 0 oder 1 zuzuordnen?"
Ja meine den Definitionsbereich. Dachte wenn nicht jede Variable [mm] $A_1,\ldots A_n$ [/mm] in [mm] $\phi$ [/mm] vorkommt, dann könnte ich keine Funktion über den Definitionsbereich [mm] $A_1,\ldots A_n$ [/mm] bauen, aber das ist klar falsch.
"...es handelt sich bei den "Erklärungen" mit wahr und falsch nur um Veranschaulichungen."
Das sehe ich nicht so, weil man wissen muss was die Zeichenkette [mm] $I\not\models\phi$ [/mm] bedeutet bevor man sie als abkürzende Schreibweise verwenden kann um [mm] $I\models(\neg\phi)$ [/mm] zu definieren.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:49 Di 30.08.2022 | | Autor: | tobit09 |
![[sorry]](/images/smileys/sorry.gif "[sorry]") für meine späte Reaktion.
> "...es handelt sich bei den "Erklärungen" mit wahr und
> falsch nur um Veranschaulichungen."
>
> Das sehe ich nicht so, weil man wissen muss was die
> Zeichenkette [mm]I\not\models\phi[/mm] bedeutet bevor man sie als
> abkürzende Schreibweise verwenden kann um
> [mm]I\models(\neg\phi)[/mm] zu definieren.
Wie gesagt: Mit [mm] "$I\not\models\phi$" [/mm] meint Hoffmann "es gilt NICHT [mm] $I\models\phi$."
[/mm]
Die veranschaulichenden Formulierungen mit wahr und falsch eignen sich nicht als Ersatz für Definition 2.7, weil zunächst noch unklar ist, was Wahrheit/Falschheit aussagenlogischer Formeln unter einer Interpretation heißen soll.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Do 25.08.2022 | | Autor: | KarlAugust |
Danke noch mal für deine Erklärungen. Verstehe die Definition 2.7 jetzt besser. Wird sich in folgenden Kapiteln zeigen wie gut.
|
|
|
|
|
