www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Prädikatenlogik" - Prädikatenlogischer Beweis
Prädikatenlogischer Beweis < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Prädikatenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Prädikatenlogischer Beweis: Frage zu einer Regel
Status: (Frage) beantwortet Status 
Datum: 15:19 Di 08.01.2008
Autor: Ratioanalytics

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

        
Bezug
Prädikatenlogischer Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 19:11 Di 08.01.2008
Autor: Somebody


>
> [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$.


Bezug
        
Bezug
Prädikatenlogischer Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:53 Do 10.01.2008
Autor: Ratioanalytics

Vielen Dank Somebody!

Bezug
                
Bezug
Prädikatenlogischer Beweis: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                        
Bezug
Prädikatenlogischer Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:41 Do 10.01.2008
Autor: Ratioanalytics

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!

Bezug
                                
Bezug
Prädikatenlogischer Beweis: 2. Tautologie
Status: (Antwort) fertig Status 
Datum: 10:32 Fr 11.01.2008
Autor: Somebody


> 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.


Bezug
                                
Bezug
Prädikatenlogischer Beweis: 1. Tautologie
Status: (Antwort) fertig Status 
Datum: 13:19 Fr 11.01.2008
Autor: Somebody


> 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]


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Prädikatenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de