Formel bereinigen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe mir folgende Formel einfach mal ausgedacht:
[mm] \forall [/mm] x [mm] \exists [/mm] y ( P(x,y) ) [mm] \vee [/mm] ( [mm] \forall [/mm] z ( P(z) ) )
Ich möchte diese Formel nun bereingen , also in die BNP (berenigte Pränexform ) bringen. (Also alle Quantoren (egal , ob All-oder Existenz vorne )
Ich bin mir ganz sicher, dass das mit dem [mm] \vee [/mm] ein Problem ist. Kann ich einfach den Allquantor z , also [mm] \forall [/mm] z einfach nach vorne bringen ? Obwohl ich merke gerade, dass das mit Oder [mm] \vee [/mm] kein Problem sein müsste, erstens weil es ein oder ist und zweitenst , ist z komplett nur an [mm] \forall [/mm] z gebunden. Das wäre eher ein Problem wenn es durch ein [mm] \wedge [/mm] verknüpft wäre , oder ?
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:36 Mo 17.02.2014 | | Autor: | DieAcht |
Hallo,
> Hallo,
>
> ich habe mir folgende Formel einfach mal ausgedacht:
> [mm]\forall[/mm] x [mm]\exists[/mm] y ( P(x,y) ) [mm]\vee[/mm] ( [mm]\forall[/mm] z ( P(z) )
> )
Deine Abbildung $P$ macht so wie es dort steht für mich
keinen Sinn. Darüber hinaus solltest du dir klar machen,
dass das Ende nicht mehr von $y$ abhängt.
Gruß
DieAcht
|
|
|
| |
|
Hallo,
achso okay, war ja auch nur ausgedacht :D.
Die Frage bleibt aber, ob ich einfach einen Allquantor oder einen Existenzquantor nach vorne schieben kann , wenn zwei Teilterme durch oder / und verknüpft sind. Gibt es da eine Regel ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:52 Di 18.02.2014 | | Autor: | tobit09 |
Hallo pc_doctor!
> Die Frage bleibt aber, ob ich einfach einen Allquantor oder
> einen Existenzquantor nach vorne schieben kann , wenn zwei
> Teilterme durch oder / und verknüpft sind. Gibt es da eine
> Regel ?
Für beliebige Formeln [mm] $F(x,x_1,\ldots,x_n)$ [/mm] und [mm] $G(y,x_1,\ldots,x_n)$ [/mm] mit [mm] $x\not=y$, [/mm] Quantoren [mm] $Q_1,Q_2\in\{\forall,\exists\}$ [/mm] und einen Junktor [mm] $J\in\{\wedge,\vee\}$ [/mm] gilt (unter Beachtung der Konvention, dass Träger von Strukturen stets nichtleer sind) stets die semantische Äquivalenz
[mm] $(Q_1 [/mm] x [mm] F(x,x_1,\ldots,x_n))J(Q_2 [/mm] y [mm] G(y,x_1,\ldots,x_n))\quad\equiv\quad Q_1 [/mm] x [mm] Q_2 [/mm] y [mm] (F(x,x_1,\ldots,x_n) [/mm] J [mm] G(y,x_1,\ldots,x_n))$.
[/mm]
In diesem Sinne ist es also möglich Quantoren nach vorne zu ziehen, wenn es keine "Kollision der Variablenbenennung" gibt.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:19 Di 18.02.2014 | | Autor: | tobit09 |
Hallo!
> Deine Abbildung [mm]P[/mm] macht so wie es dort steht für mich
> keinen Sinn.
P soll keine Abbildung sondern ein Prädikatszeichen in der Prädikatenlogik der ersten Stufe sein.
Allerdings kann es nicht gleichzeitig einstellig und zweistellig sein.
Viele Grüße
Tobias
|
|
|
|
