logisches Schließen, Prädikate < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe noch eine Frage in Bezug auf Prädikatenlogik und dem logischen Schließen.
Ich habe folgende Aufgabe: Zeigen Sie, daß die Formel
( [mm] \exists [/mm] y [mm] \forall [/mm] x P(x, y)) [mm] \wedge \neg (\exists [/mm] x [mm] \forall [/mm] y P(x, y))
unerfüllbar ist.
Ich weiß, daß ich die Instantiierungsregeln, [mm] \wedge-Einführung [/mm] bzw. Elimination anwenden muß, weiß aber leider nicht wie und wann bzw.
wie ich die Beweisführung durchführen muß?
Kann mir da vielleicht jemand weiterhelfen?
LG und danke,
RoterBlitz
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:12 Fr 28.01.2005 | | Autor: | Bastiane |
Hallo RoterBlitz!
> Ich habe folgende Aufgabe: Zeigen Sie, daß die Formel
> ( [mm]\exists[/mm] y [mm]\forall[/mm] x P(x, y)) [mm]\wedge \neg (\exists[/mm] x
> [mm]\forall[/mm] y P(x, y))
> unerfüllbar ist.
>
> Ich weiß, daß ich die Instantiierungsregeln,
> [mm]\wedge-Einführung[/mm] bzw. Elimination anwenden muß, weiß aber
> leider nicht wie und wann bzw.
> wie ich die Beweisführung durchführen muß?
Mit Unerfüllbarkeit habe ich schon mal was zu tun gehabt, aber die Instantiierungsregeln und was du noch meinst, kenne ich nicht. Vielleicht kann ich dir helfen, wenn du mir kurz beschreibst, was das ist - aber versprechen kann ich dir nichts. ![[sorry]](/images/smileys/sorry.gif "[sorry]")
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
> Hallo RoterBlitz!
Hallo, Bastiane!
danke für Deine Bemühungen!! 
Anbei einige Definitionen die für die Lösung - so denke ich - einzusetzen sind:
1. [mm] \exists [/mm] -Instantiierungsreglen:
Definition: [mm] \exists [/mm] x F
F {x/c}
dh. es wird jedes x durch eine neue Konstante c ersetzt
Beispiel: [mm] \exists [/mm] x Politiker(x) wird zu Politiker(NN)
2. Modus Ponens:
F [mm] \to [/mm] G
G
F
Beispiel: Wenn es regnet -> wird die Straße naß
Es regnet.
Die Straße wird naß
3. Modus Tollens:
[mm] A\to [/mm] B
[mm] \neg [/mm] B
[mm] \neg [/mm] A
Beispiel: wenn es regnet, wird die Straße naß.
Die straße wird nicht naß.
Es regnet nicht.
4. [mm] \wedge [/mm] - Einführung:
F, G
F [mm] \wedge [/mm] G
Die [mm] \wedge [/mm] Einführung besagt, daß aus der Gültigkeit von zwei Formeln deren Konjunktion geschlossen werden kann.
[mm] \5. [/mm] wedge - Elimination:
F [mm] \wedge [/mm] G
F
Beispiel: Firma (AG) [mm] \wedge [/mm] Mag(NN, AG) daraus folgt:
Firma (AG) oder eben Mag (NN, AG)
Mittels [mm] \wedge [/mm] Elimination aus einer Konjunktion kann auf ein Konjunktionsglied geschlossen werden.
Liebe Grüße und nochmals danke
RoterBlitz
> > Ich habe folgende Aufgabe: Zeigen Sie, daß die Formel
>
> > ( [mm]\exists[/mm] y [mm]\forall[/mm] x P(x, y)) [mm]\wedge \neg (\exists[/mm] x
>
> > [mm]\forall[/mm] y P(x, y))
> > unerfüllbar ist.
> >
> > Ich weiß, daß ich die Instantiierungsregeln,
> > [mm]\wedge-Einführung[/mm] bzw. Elimination anwenden muß, weiß
> aber
> > leider nicht wie und wann bzw.
> > wie ich die Beweisführung durchführen muß?
>
> Mit Unerfüllbarkeit habe ich schon mal was zu tun gehabt,
> aber die Instantiierungsregeln und was du noch meinst,
> kenne ich nicht. Vielleicht kann ich dir helfen, wenn du
> mir kurz beschreibst, was das ist - aber versprechen kann
> ich dir nichts.
>
> Viele Grüße
> Bastiane
>
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:33 Mi 02.02.2005 | | Autor: | RoterBlitz |
Hallo, nochmal!
Ich habe mittlerweile einen Hinweis bekommen, daß wie folgt bewiesen werden kann, daß die folgende Formel nicht erfüllbar ist - mithilfe der Interpretation:
[mm] (\exists [/mm] y [mm] \forall [/mm] x P(x, y)) [mm] \wedge \neg (\forall [/mm] x [mm] \exists [/mm] y P(x, y))
Man nehme an, es gibt eine Interpretation I mit einem zugehörigen Universum [mm] U_I, [/mm] welche die Formel erfüllt.
Dann ist der links der Konjunktion stehende Teil der Formel unter I wahr dh. für ein bestimmtes Element a aus [mm] U_I [/mm] hat [mm] \forall [/mm] x P(x, y) unter jeder Variablenbelegung [mm] \alpha [/mm] - welche der Variablen y den Wert a zuordnent, den Wahrheitswert true dh.
[mm] \forall [/mm] x P(x, a) ist wahr. Tja, dann geht das ähnlich mit dem x und der VAriablenbelegung [mm] \beta [/mm] weiter...
Kennt sich vielleicht jemand damit näher aus, damit die oben beschriebene Vorgehensweise auch ich verstehe?
LG und danke,
RoterBlitz
> > Hallo RoterBlitz!
>
> Hallo, Bastiane!
>
> danke für Deine Bemühungen!!
>
> Anbei einige Definitionen die für die Lösung - so denke ich
> - einzusetzen sind:
>
> 1. [mm]\exists[/mm] -Instantiierungsreglen:
> Definition: [mm]\exists[/mm] x F
> F {x/c}
>
> dh. es wird jedes x durch eine neue Konstante c ersetzt
>
> Beispiel: [mm]\exists[/mm] x Politiker(x) wird zu Politiker(NN)
>
> 2. Modus Ponens:
> F [mm]\to[/mm] G
> G
> F
>
> Beispiel: Wenn es regnet -> wird die Straße naß
> Es regnet.
> Die Straße wird naß
>
> 3. Modus Tollens:
> [mm]A\to[/mm] B
> [mm]\neg[/mm] B
> [mm]\neg[/mm] A
>
> Beispiel: wenn es regnet, wird die Straße naß.
> Die straße wird nicht naß.
> Es regnet nicht.
>
> 4. [mm]\wedge[/mm] - Einführung:
>
> F, G
> F [mm]\wedge[/mm] G
>
> Die [mm]\wedge[/mm] Einführung besagt, daß aus der Gültigkeit von
> zwei Formeln deren Konjunktion geschlossen werden kann.
>
> [mm]\5.[/mm] wedge - Elimination:
> F [mm]\wedge[/mm] G
> F
>
> Beispiel: Firma (AG) [mm]\wedge[/mm] Mag(NN, AG) daraus folgt:
> Firma (AG) oder eben Mag (NN, AG)
>
>
> Mittels [mm]\wedge[/mm] Elimination aus einer Konjunktion kann auf
> ein Konjunktionsglied geschlossen werden.
>
> Liebe Grüße und nochmals danke
>
> RoterBlitz
>
>
>
>
> > > Ich habe folgende Aufgabe: Zeigen Sie, daß die Formel
>
> >
> > > ( [mm]\exists[/mm] y [mm]\forall[/mm] x P(x, y)) [mm]\wedge \neg (\exists[/mm] x
>
> >
> > > [mm]\forall[/mm] y P(x, y))
> > > unerfüllbar ist.
> > >
> > > Ich weiß, daß ich die Instantiierungsregeln,
> > > [mm]\wedge-Einführung[/mm] bzw. Elimination anwenden muß, weiß
>
> > aber
> > > leider nicht wie und wann bzw.
> > > wie ich die Beweisführung durchführen muß?
> >
> > Mit Unerfüllbarkeit habe ich schon mal was zu tun gehabt,
>
> > aber die Instantiierungsregeln und was du noch meinst,
>
> > kenne ich nicht. Vielleicht kann ich dir helfen, wenn du
>
> > mir kurz beschreibst, was das ist - aber versprechen kann
>
> > ich dir nichts.
> >
> > Viele Grüße
> > Bastiane
> >
> >
> >
>
>
|
|
|
|
![[winken]](/images/smileys/winken.gif "[winken]"){kind=small}
,
