Prädikatenlogischer Beweis < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe |
[mm] \forall [/mm] y [mm] \forall [/mm] x P²xy [mm] \to \exists [/mm] z Qz
[mm] \exists [/mm] y [mm] (\forall [/mm] x P²xy [mm] \to \exists [/mm] z Qz)
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
1. Zeile Annahme
2. Zeile Zeigezeile
Zwei Fragen:
1. Darf ich hier direkt aus der Annahme die Zeige Zeile zeigen?
Wenn ja, wäre es richtig den Allquantor zu beseitigen und Existenzquantor einzuführen? Aber wie ist das mit der Klammer?
2. Wenn ich nicht sofort aus Annahme die Zeigezeile zeigen darf, wie teile ich die Zeigezeile nochmal auf? Wie ist der Existenzquantor vor der Klammer zu behandeln? Wenn man die Klammer weglässt, steht der Existenzquantor dann sowohl rechts als auch links vom Konditional? Brauche NACHhilfe
Mache mir vielleicht zu genau Gedanken aber ich würde mich freuen mit eurer Hilfe Fehler vermeiden zu können! Vielen Dank
|
|
| |
|
>
> [mm]\forall[/mm] y [mm]\forall[/mm] x P²xy [mm]\to \exists[/mm] z Qz
> [mm]\exists[/mm] y [mm](\forall[/mm] x P²xy [mm]\to \exists[/mm] z Qz)
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> 1. Zeile Annahme
> 2. Zeile Zeigezeile
>
> Zwei Fragen:
> 1. Darf ich hier direkt aus der Annahme die Zeige Zeile
> zeigen?
> Wenn ja, wäre es richtig den Allquantor zu beseitigen und
> Existenzquantor einzuführen? Aber wie ist das mit der
> Klammer?
Ja, dies ist natürlich eine zentrale Frage: welche Regeln der Klammerersparnis denn bei Dir (bei Deinem Professor) gelten. Ich bin der Ansicht, dass die Prämisse 1 die Form [mm] $(\forall [/mm] y [mm] Ay)\rightarrow [/mm] B$ und die Konklusion 2 die Form [mm] $\exists y\left(Ay\rightarrow B\right)$ [/mm] haben, wobei $Ay := [mm] \forall [/mm] x [mm] P^2 [/mm] xy$ und $B := [mm] \exists [/mm] z Qz$.
> 2. Wenn ich nicht sofort aus Annahme die Zeigezeile zeigen
> darf, wie teile ich die Zeigezeile nochmal auf? Wie ist der
> Existenzquantor vor der Klammer zu behandeln?
Weil $B$ von der existenzquantifizierten Variablen $y$ gar nicht abhängt, hat man [mm] $\exists y\big(Ay\rightarrow B)\Leftrightarrow\exists y\big(\neg Ay\vee B\big)\red{\Leftrightarrow} (\exists [/mm] y [mm] \neg Ay)\vee B\Leftrightarrow (\neg \forall [/mm] y [mm] Ay)\vee B\Leftrightarrow (\forall [/mm] y [mm] Ay)\rightarrow [/mm] B$.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:52 Do 10.01.2008 | | Autor: | koepper |
Hallo Ratio,
mit Somebody's letzter Zeile ist dann klar, daß die "Zeigezeile" nicht nur aus der Annahme folgt, sondern sogar äquivalent zu ihr ist.
LG
Will
|
|
|
| |
|
Ich hätte noch ein Frage:
Ich beisse mir seit 2 Tagen an den Beweisen für zwei Tautologien die Zähne aus. Ich weiß enfach nicht wie ich vorgehen soll oder was der richtige Weg ist. Vielleicht könnt ihr mir ein paar Tipps geben?
Es geht um folgende zwei Theoreme die getrennt von einander zu beweisen sind. Beides sind Tautologien:
[mm] \exists [/mm] y ( [mm] \exists [/mm] x P²xy [mm] \gdw [/mm] Qy ) [mm] \gdw \exists [/mm] y [mm] \forall [/mm] x [mm] \exists [/mm] z ((P²xy [mm] \to [/mm]
Qy) [mm] \wedge [/mm] (Qy [mm] \to [/mm] P²zy))
[mm] \exists [/mm] x (Px [mm] \wedge \forall [/mm] (Py [mm] \to [/mm] x=y)) [mm] \gdw \exists [/mm] y [mm] \forall [/mm] x (Px [mm] \gdw [/mm] x=y)
Ich bräuchte einfach nen Ansatz mit dem ich arbeiten kann. Komme aber nie über die 3. oder 4. Zeigezeile raus. Bin froh über Tipps. Am besten noch heute. Morgen zur größten NOT. Danke euch Netten!
|
|
|
| |
|
> Ich hätte noch ein Frage:
> Ich beisse mir seit 2 Tagen an den Beweisen für zwei
> Tautologien die Zähne aus. Ich weiß enfach nicht wie ich
> vorgehen soll oder was der richtige Weg ist. Vielleicht
> könnt ihr mir ein paar Tipps geben?
>
> Es geht um folgende zwei Theoreme die getrennt von einander
> zu beweisen sind. Beides sind Tautologien:
>
> [mm]\exists[/mm] y ( [mm]\exists[/mm] x P²xy [mm]\gdw[/mm] Qy ) [mm]\gdw \exists[/mm] y [mm]\forall[/mm]
> x [mm]\exists[/mm] z ((P²xy [mm]\to[/mm]
> Qy) [mm]\wedge[/mm] (Qy [mm]\to[/mm] P²zy))
>
> [mm]\exists[/mm] x (Px [mm]\wedge \forall[/mm] (Py [mm]\to[/mm] x=y)) [mm]\gdw \exists[/mm] y
> [mm]\forall[/mm] x (Px [mm]\gdw[/mm] x=y)
>
> Ich bräuchte einfach nen Ansatz mit dem ich arbeiten kann.
Zum Beweis von
[mm]\exists x\big(Px \wedge \forall y(Py\Rightarrow x=y)\big)\Leftrightarrow \exists y\forall x(Px\Leftrightarrow x=y)[/mm]
würde ich zuerst die Variablen $x,y$ auf der rechten Seite dieser Bisubjunktion umbenennen
[mm]\exists x\big(Px \wedge \forall y(Py\Rightarrow x=y)\big)\Leftrightarrow \exists x\forall y(Py\Leftrightarrow y=x)[/mm]
Grundlegend muss man sich natürlich klar machen, dass $=$ kein beliebiges zweistelliges Prädikat ist, sondern einige besondere Eigenschaften hat (Reflexivität, Symmetrie, Transitivität, Leibniz-Prinzip).
Weil ich nicht weiss, welche genauen formalen Methoden Du für einen Beweis prädikatenlogischer Aussagen verwenden musst, kann ich im folgenden nur eine saloppe Beweisskizze liefern:
Beweis von [mm] $\Rightarrow$: [/mm] Nach Voraussetzung [mm] $\exists x\big(Px \wedge \forall y(Py\Rightarrow x=y)\big)$ [/mm] gibt es also ein [mm] $x_1$ [/mm] für das [mm] $Px_1$ [/mm] und [mm] $\forall y(Py\Rightarrow x_1=y)$ [/mm] gilt. Zum Beweis der rechten Seite genügt es zu zeigen, dass dieses [mm] $x_1$ [/mm] die Eigenschaft hat, dass [mm] $\forall y(Py\Leftrightarrow y=x_1)$ [/mm] gilt.
Sei also $y$ beliebig. Gilt $Py$, so folgt aus der Voraussetzung [mm] $\forall y(Py\Rightarrow x_1=y)$, [/mm] unter Verwendung der Symmetrie von $=$, dass auch [mm] $y=x_1$. [/mm] Ist andererseits [mm] $y=x_1$, [/mm] so folgt aus [mm] $Px_1$ [/mm] sogleich $Py$ (Leibniz-Prinzip).
Beweis von [mm] $\Leftarrow$: [/mm] Gemäss Voraussetzung [mm] $\exists x\forall y(Py\Leftrightarrow [/mm] y=x)$ existiert ein [mm] $x_1$, [/mm] für das gilt [mm] $\forall y(Py\Leftrightarrow y=x_1)$. [/mm] Wegen [mm] $x_1=x_1$ [/mm] (Reflexivität von $=$) folgt daraus sogleich, dass [mm] $Px_1$ [/mm] gilt. Nun müssen wir nur noch zeigen, dass [mm] $\forall y(Py\Rightarrow x_1=y)$. [/mm] Dies folgt aber, unter Verwendung der Symmetrie von $=$, sogleich aus der stärkeren Aussage [mm] $\forall y(Py\Leftrightarrow y=x_1)$, [/mm] die wir voraussetzen durften.
|
|
|
| |
|
> Ich hätte noch ein Frage:
> Ich beisse mir seit 2 Tagen an den Beweisen für zwei
> Tautologien die Zähne aus. Ich weiß enfach nicht wie ich
> vorgehen soll oder was der richtige Weg ist. Vielleicht
> könnt ihr mir ein paar Tipps geben?
>
> Es geht um folgende zwei Theoreme die getrennt von einander
> zu beweisen sind. Beides sind Tautologien:
>
> [mm]\exists[/mm] y ( [mm]\exists[/mm] x P²xy [mm]\gdw[/mm] Qy ) [mm]\gdw \exists[/mm] y [mm]\forall[/mm]
> x [mm]\exists[/mm] z ((P²xy [mm]\to[/mm]
> Qy) [mm]\wedge[/mm] (Qy [mm]\to[/mm] P²zy))
>
> [mm]\exists[/mm] x (Px [mm]\wedge \forall[/mm] (Py [mm]\to[/mm] x=y)) [mm]\gdw \exists[/mm] y
> [mm]\forall[/mm] x (Px [mm]\gdw[/mm] x=y)
>
> Ich bräuchte einfach nen Ansatz mit dem ich arbeiten kann.
> Komme aber nie über die 3. oder 4. Zeigezeile raus. Bin
> froh über Tipps. Am besten noch heute. Morgen zur größten
> NOT.
Wir wollen also beweisen, dass gilt
[mm]\exists y(\exists x P^2xy\Leftrightarrow Qy)\Leftrightarrow \exists y \forall x \exists z \big((P^2 xy \Rightarrow Qy)\wedge (Qy \Rightarrow P^2 zy)\big)[/mm]
Wieder kann ich nur einen relativ saloppen, hohen Ansprüchen an die Präzision der Notation wohl nicht genügenden Beweis liefern: nimm es einfach als einen "Tipp" (mehr hast Du Dir ja auch nicht gewünscht  )
Beweis [mm] $\Rightarrow$: [/mm] Aufgrund der Voraussetzung [mm] $\exists y(\exists [/mm] x [mm] P^2xy\Leftrightarrow [/mm] Qy)$ gibt es also ein [mm] $y_1$ [/mm] mit der Eigenschaft, dass
[mm]\blue{(1)}\qquad (\exists x P^2 xy_1)\Leftrightarrow Qy_1[/mm]
Es genügt zu zeigen, dass daraus folgt, dass
[mm]\red{(2)}\qquad \forall x\exists z\big((P^2 xy_1\Rightarrow Qy_1)\wedge (Qy_1\Rightarrow P^2 zy_1)\big)[/mm]
Sei $x$ beliebig vorgegeben. Wir unterscheiden zwei Fälle:
1. Fall: [mm] $Qy_1$ [/mm] gilt. Dann folgt aus (1), dass [mm] $\exists [/mm] x [mm] P^2 xy_1$. [/mm] Sei also [mm] $z_1$ [/mm] ein solches $x$, d.h. gelte [mm] $P^2 z_1y_1$. [/mm] Für dieses [mm] $z_1$ [/mm] gilt offenbar
[mm]\red{(3)}\qquad (P^2 xy_1\Rightarrow Qy_1)\wedge (Qy_1\Rightarrow P^2 z_1 y_1)[/mm]
Denn [mm] $P^2 xy_1\Rightarrow Qy_1$ [/mm] gilt, wegen unserer Annahme, dass [mm] $Qy_1$ [/mm] gilt, und $Q [mm] y_1\Rightarrow P^2 z_1 y_1$ [/mm] gilt, weil wir [mm] $z_1$ [/mm] so gewählt haben, dass [mm] $P^2 z_1 y_1$ [/mm] gilt. Damit haben wir, für diesen 1. Fall, (2) gezeigt.
2. Falll: [mm] $Qy_1$ [/mm] gilt nicht. In diesem Falle folgt aus (1), dass es kein $x$ mit [mm] $P^2 xy_1$ [/mm] geben kann. Daher können wir [mm] $z_1$ [/mm] beliebig wählen und behaupten, dass wiederum
[mm]\red{(3')}\qquad (P^2 xy_1\Rightarrow Qy_1)\wedge (Qy_1\Rightarrow P^2 z_1 y_1)[/mm]
gilt. Denn [mm] $P^2 xy_1 \Rightarrow Qy_1$ [/mm] gilt, weil [mm] $P^2 xy_1$ [/mm] falsch sein muss; [mm] $Qy_1\Rightarrow P^2 z_1 y_1$ [/mm] gilt, weil [mm] $Qy_1$, [/mm] gemäss unserer Annahme, falsch ist. Damit haben wir auch für diesen 2. Fall (2) gezeigt.
Nun tief durchatmen und dann die andere Richtung beweisen:
Beweis [mm] $\Leftarrow$: [/mm] Gemäss Voraussetzung existiert also ein [mm] $y_1$ [/mm] mit der Eigenschaft, dass
[mm]\blue{(1)}\qquad \forall x\exists z\big((P^2 xy_1 \Rightarrow Q y_1)\wedge (Q y_1\Rightarrow P^2 z y_1)\big)[/mm]
Es genügt zu zeigen, dass für dieses [mm] $y_1$ [/mm] gilt, dass
[mm]\red{(2)}\qquad (\exists x P^2 xy_1) \Leftrightarrow Q y_1[/mm]
[mm] $\Rightarrow$: [/mm] Angenommen [mm] $\exists [/mm] x [mm] P^2 xy_1$ [/mm] gilt. Sei [mm] $x_1$ [/mm] ein solches $x$, d.h. gelte [mm] $P^2 x_1 y_1$. [/mm] Aus (1) folgt, dass für dieses [mm] $x_1$ [/mm] auch [mm] $P^2 x_1 y_1\Rightarrow [/mm] Q [mm] y_1$ [/mm] gilt, also folgt zusammen mit [mm] $P^2 x_1 y_1$, [/mm] dass in der Tat $Q [mm] y_1$ [/mm] gilt.
[mm] $\Leftarrow$: [/mm] Angenommen [mm] $Qy_1$ [/mm] gilt, dann können wir in (1) $x$ beliebig wählen und erhalten dann die Existenz eines [mm] $z_1$ [/mm] mit der Eigenschaft, dass $Q [mm] y_1\Rightarrow P^2 z_1 y_1$. [/mm] Zusammen mit [mm] $Qy_1$ [/mm] folgt daraus [mm] $P^2 z_1 y_1$. [/mm] Also gilt [mm] $\exists [/mm] x [mm] P^2 [/mm] x [mm] y_1$.
[/mm]
|
|
|
|
