Bsp. Indirekter Beweis gesucht < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Umfrage) Beendete Umfrage  | | Datum: | 16:58 So 18.11.2012 | | Autor: | tobit09 |
Hallo zusammen,
ich suche rein Aussagenlogische Sachverhalte, bei denen ein indirekter Beweis (Beweis durch Widerspruch) möglichst stark vorteilhafter gegenüber einem direkten Beweis ist.
Mit rein Aussagenlogischen Sachverhalten meine ich solche wie folgenden:
Seien A und B Aussagen.
Gelte [mm] $\neg(A\wedge [/mm] B)$. Gelte A.
Dann gilt [mm] $\neg [/mm] B$.
Indirekter Beweis: Angenommen B gilt. Dann gilt, weil A gilt, auch [mm] $A\wedge [/mm] B$. Widerspruch zu [mm] $\neg (A\wedge [/mm] B)$.
Ein direkter Beweis wäre ca. doppelt so lang. (Beweise durch Wahrheitstafeln möchte ich mal außen vor lassen.)
Leider ist das das einzige solche Aussagenlogische Beispiel, das mir einfällt. Hat jemand weitere Ideen?
Viele Grüße
Tobias
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:47 So 18.11.2012 | | Autor: | M.Rex |
Hallo
> Hallo zusammen,
>
>
> ich suche rein Aussagenlogische Sachverhalte, bei denen ein
> indirekter Beweis (Beweis durch Widerspruch) möglichst
> stark vorteilhafter gegenüber einem direkten Beweis ist.
>
> Mit rein Aussagenlogischen Sachverhalten meine ich solche
> wie folgenden:
>
> Seien A und B Aussagen.
> Gelte [mm]\neg(A\wedge B)[/mm]. Gelte A.
> Dann gilt [mm]\neg B[/mm].
>
> Indirekter Beweis: Angenommen B gilt. Dann gilt, weil A
> gilt, auch [mm]A\wedge B[/mm]. Widerspruch zu [mm]\neg (A\wedge B)[/mm].
>
> Ein direkter Beweis wäre ca. doppelt so lang. (Beweise
> durch Wahrheitstafeln möchte ich mal außen vor lassen.)
>
> Leider ist das das einzige solche Aussagenlogische
> Beispiel, das mir einfällt. Hat jemand weitere Ideen?
Ich denke, Widerspruchsbeweise sind der klassische Fall, wenn man Zeigen will, dass eine Aussage nicht gilt.
Der wahrscheinlich bekannteste Beweis dazu ist der Beweis, dass [mm] $\sqrt{2}\notin\mathbb{Q}$
[/mm]
>
>
> Viele Grüße
> Tobias
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:19 So 18.11.2012 | | Autor: | tobit09 |
Hallo Marius,
vielen Dank für deine Antwort!
Mit "rein aussagenlogischen Sachverhalten" meine ich u.a.: Es sollen in den Beispielen nur abstrakte Aussagen und keine Objekte wie Zahlen vorkommen. Ein Beispiel eines solchen Sachverhaltes habe ich ja gegeben. Ich würde mich über weitere Vorschläge dieser Art freuen!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:30 So 18.11.2012 | | Autor: | M.Rex |
> Hallo Marius,
Hallo Tobias
>
>
> vielen Dank für deine Antwort!
>
>
> Mit "rein aussagenlogischen Sachverhalten" meine ich u.a.:
> Es sollen in den Beispielen nur abstrakte Aussagen und
> keine Objekte wie Zahlen vorkommen. Ein Beispiel eines
> solchen Sachverhaltes habe ich ja gegeben. Ich würde mich
> über weitere Vorschläge dieser Art freuen!
Dazu habe ich die Ausgangsfrage mal als Umfrage deklariert.
>
>
> Viele Grüße
> Tobias
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:38 So 18.11.2012 | | Autor: | tobit09 |
> Dazu habe ich die Ausgangsfrage mal als Umfrage
> deklariert.
Danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:22 Mi 28.11.2012 | | Autor: | tobit09 |
Hallo nochmal,
ich würde mich freuen, wenn jemand so kreativ wäre und noch einen aussagenlogischen Sachverhalt finden würde, bei dem ein indirekter Beweis günstiger als ein direkter ist.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:50 Mi 28.11.2012 | | Autor: | Helbig |
> Hallo zusammen,
>
>
> ich suche rein Aussagenlogische Sachverhalte, bei denen ein
> indirekter Beweis (Beweis durch Widerspruch) möglichst
> stark vorteilhafter gegenüber einem direkten Beweis ist.
Gibt es nicht! Wenn man die aussagenlogischen Regeln verwendet ist direkter und indirekter Beweis gleich schwierig. Wenn man den Beweis dagegen in Deutsch faßt, wird es umso schwieriger, je mehr Negationen in den Aussagen vorkommen.
In Deinem Beispiel: (W=wahr, F=falsch)
Gelte A, also A=W
Dann haben wir:
[mm] $\neg(A\land B)\gdw \neg(W\land [/mm] B) [mm] \gdw \neg B\,.$
[/mm]
Beachte: W ist das neutrale Element der Und-Verknüpfung von Aussagen.
Gruß,
Wolfgang
>
> Mit rein Aussagenlogischen Sachverhalten meine ich solche
> wie folgenden:
>
> Seien A und B Aussagen.
> Gelte [mm]\neg(A\wedge B)[/mm]. Gelte A.
> Dann gilt [mm]\neg B[/mm].
>
> Indirekter Beweis: Angenommen B gilt. Dann gilt, weil A
> gilt, auch [mm]A\wedge B[/mm]. Widerspruch zu [mm]\neg (A\wedge B)[/mm].
>
> Ein direkter Beweis wäre ca. doppelt so lang. (Beweise
> durch Wahrheitstafeln möchte ich mal außen vor lassen.)
>
> Leider ist das das einzige solche Aussagenlogische
> Beispiel, das mir einfällt. Hat jemand weitere Ideen?
>
>
> Viele Grüße
> Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:58 Do 29.11.2012 | | Autor: | tobit09 |
Hallo Wolfgang,
danke für deinen interessanten Beitrag!
> Gibt es nicht! Wenn man die aussagenlogischen Regeln
> verwendet ist direkter und indirekter Beweis gleich
> schwierig.
Ich möchte gerne möglichst wenig aussagenlogische Regeln als bekannt voraussetzen.
> In Deinem Beispiel: (W=wahr, F=falsch)
>
> Gelte A, also A=W
>
> Dann haben wir:
>
> [mm]\neg(A\land B)\gdw \neg(W\land B) \gdw \neg B\,.[/mm]
>
> Beachte: W ist das neutrale Element der Und-Verknüpfung
> von Aussagen.
Ich würde deinen Beweis so ausformulieren:
Wir zeigen zunächst [mm] $A\wedge B\gdw [/mm] B$.
Hin-Richtung: Gelte [mm] $A\wedge [/mm] B$. Dann gelten $A$ und $B$.
Rück-Richtung: Gelte $B$. Da auch $A$ gilt, gilt somit [mm] $A\wedge [/mm] B$.
Also ("Einsetzungsregel für äquivalente Aussagen") [mm] $\neg (A\wedge B)\gdw\neg [/mm] B$. Da [mm] $\neg(A\wedge [/mm] B)$ gilt, gilt somit auch [mm] $\neg [/mm] B$.
In diesem Sinne ist auch dieser direkte Beweis schon länger als der indirekte.
> Wenn man den Beweis dagegen in Deutsch faßt,
Ja, so möchte ich das machen.
> wird es umso
> schwieriger, je mehr Negationen in den Aussagen vorkommen.
Vielleicht liefert dies ja einen Ansatz für einen aussagenlogischen Sachverhalt, der sich leichter indirekt als direkt beweisen lässt?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:51 Do 29.11.2012 | | Autor: | Helbig |
> > Gibt es nicht! Wenn man die aussagenlogischen Regeln
> > verwendet ist direkter und indirekter Beweis gleich
> > schwierig.
> Ich möchte gerne möglichst wenig aussagenlogische Regeln
> als bekannt voraussetzen.
Hallo Tobias,
Die lassen sich natürlich auch auf deutsch formulieren. In Deinem Beispiel:
Wenn A und B nicht beide zugleich gelten aber A gilt, dann kann B nicht gelten.
Ist doch auch schön kurz und sollte jeden überzeugen!
Ich glaube einfach nicht, daß es einen aussagenlogischen Satz gibt, für den ein Widerspruchsbeweis einfacher als ein direkter Beweis ist.
Anders sieht es bei prädikatenlogischen Aussagen aus. Aber auch nur, weil deren Regeln nicht so bekannt sind wie die der Aussagenlogik.
Grüße,
Wolfgang
>
>
> > In Deinem Beispiel: (W=wahr, F=falsch)
> >
> > Gelte A, also A=W
> >
> > Dann haben wir:
> >
> > [mm]\neg(A\land B)\gdw \neg(W\land B) \gdw \neg B\,.[/mm]
> >
> > Beachte: W ist das neutrale Element der Und-Verknüpfung
> > von Aussagen.
> Ich würde deinen Beweis so ausformulieren:
>
>
> Wir zeigen zunächst [mm]A\wedge B\gdw B[/mm].
> Hin-Richtung: Gelte
> [mm]A\wedge B[/mm]. Dann gelten [mm]A[/mm] und [mm]B[/mm].
> Rück-Richtung: Gelte [mm]B[/mm]. Da auch [mm]A[/mm] gilt, gilt somit
> [mm]A\wedge B[/mm].
>
> Also ("Einsetzungsregel für äquivalente Aussagen") [mm]\neg (A\wedge B)\gdw\neg B[/mm].
> Da [mm]\neg(A\wedge B)[/mm] gilt, gilt somit auch [mm]\neg B[/mm].
>
>
> In diesem Sinne ist auch dieser direkte Beweis schon
> länger als der indirekte.
>
>
> > Wenn man den Beweis dagegen in Deutsch faßt,
> Ja, so möchte ich das machen.
>
> > wird es umso
> > schwieriger, je mehr Negationen in den Aussagen
> vorkommen.
> Vielleicht liefert dies ja einen Ansatz für einen
> aussagenlogischen Sachverhalt, der sich leichter indirekt
> als direkt beweisen lässt?
>
>
> Viele Grüße
> Tobias
|
|
|
|
![[]](/images/popup.gif){kind=small}
Systeme natürlichen Schließens
