Widerspruchsbeweis < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Hallo,
kann mir jemand helfen den indirkten Beweis durch Widerspruch zu verstehen.
Ich würde das gerne anhand der Wahrheitstafel der Implikation diskutieren.
Wenn man also einen Widerspruchbeweis führt (z.B. Wurzel 2 ist eine nicht rationale Zahl), welche Aussagen muss man dann in die Implikation einsetzten.
A | B | A [mm] \Rightarrow [/mm] B
A wäre ja die Negation, also [mm] \wurzel{2} [/mm] ist rational. Wenn ich das jetzt durch richtiges Schließen auf einen Widerspruch führe, welche Wahrheitswerte nehmen dann B und die Gesamtaussage (A [mm] \Rightarrow [/mm] B) an?
Vielen Dank!
Grüße Jan
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:14 Mi 27.09.2006 | | Autor: | Mr_H |
Hi,
wenn du einen Widerspruchsbeweis führen willst, dann musst du dir das so vorstellen, dass du "das Pferd von hinten aufzäumst". Das soll heißen, dass du den Beweis nicht über [mm] $A\Rightarrow [/mm] B$, sondern über die logisch gleichwertige Aussage (Umkehrschluss) [mm] $\neg B\Rightarrow\neg [/mm] A$ führst.
Schreibe dir das einmal in einer Wertetabelle auf und du wirst sehen, dass die Ergebnisse beider logischen Aussagen genau demselben Ergebnis entsprechen.
Im Widerspruchsbeweis machst du dir die Tatsache zunutze, dass die Implikation allein einen Fall hat, der eine falsche Aussage zur Folge hat. (Verwirrend ist meist der Fall $0 [mm] \Rightarrow [/mm] 1$. Das ist halt trivial richtig, ohne generell richtig zu sein.)
Du behauptest, dass [mm] \sqrt{2} [/mm] eben doch Element der rationalen Zahlen ist. Um damit deine ursprüngliche Aussage zu beweisen, musst du den Umkehrschluss nehmen und zeigen, dass aus [mm] $\neg [/mm] B$ zwangsläufig [mm] $\neg [/mm] A$ folgen [mm] \textbf{muss} [/mm] -- Also der logische Umkehrschluss wahr ist. Wenn das der Fall ist, ist aufgrund der logischen Gleichwertigkeit [mm] $(\neg [/mm] B [mm] \Rightarrow \neg [/mm] A) [mm] \gdw [/mm] (A [mm] \Rightarrow [/mm] B)$.
Beide Aussagen sind logisch gleichwertig und du hast deine Aussage $A [mm] \Rightarrow [/mm] B$ bewiesen -- nur hintenrum  .
Kleiner Tipp:
Nimm an, [mm] \sqrt{2} \in \mathbb{Q} [/mm] und schreibe dir auf, wie sich diese rationale Zahl dann zusammensetzen müsste (wie alle rationale Zahlen).
Und dann probiere ein wenig herum.
Gruß
Henning
|
|
|
| |
|
Also das was du erklärst verstehe ich. Ich meine aber, dass die Beweisart die du beschreibst als Kontraposition beschrieben wird. Bei den indirketen Beweisen wird meines Wissnes noch zwischen Kontraposition und Widerspruchsbeweis unterschieden.
Aber gerade bei letzterem habe ich Verständnisprobleme.
Und das (A [mm] \Rightarrow [/mm] B) [mm] \gdw (\neg [/mm] B [mm] \Rightarrow \neg [/mm] A) gilt kann man sich leicht an dem schönen Beispiel klarmachen:
A = Wenn es regnet
B = ist die Straße nass.
Ist die Straße also nihct nass, so regnet es auch nicht.
Ich Danke dir auch wenn mein Hunger noch nicht gestillt ist für deine ausführliche Antwort!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:16 Mi 27.09.2006 | | Autor: | Zaed |
Hallo,
wie kann man die Aussage [mm] \wurzel{2}\in\IQ [/mm] in eine Inklusion packen? Das ist doch lediglich eine einzelne Aussage, oder etwa nicht?
Und mit dem Widerspruch zeigst du eben, dass aus A nicht A folgt, und somit muss A falsch sein, denn A [mm] \Rightarrow \neg [/mm] A ist eben nur für A falsch erfüllt.
mfG Zaed
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:29 Mi 27.09.2006 | | Autor: | Gonozal_IX |
Hallo Bastiane,
es gibt durchaus noch andere Möglichkeiten eines Widerspruchbeweises,
siehe meine Antwort auf die Frage 
Gruß,
Gono.
|
|
|
| |
|
>> Aber gerade bei letzterem habe ich Verständnisprobleme.
>> Und das (A $ [mm] \Rightarrow [/mm] $ B) $ [mm] \gdw (\neg [/mm] $ B $ [mm] \Rightarrow \neg [/mm] $
>> A) gilt kann man sich leicht an dem schönen Beispiel
>> klarmachen:
>> A = Wenn es regnet
>> B = ist die Straße nass.
>> Ist die Straße also nihct nass, so regnet es auch nicht.
>Hehe, aber was ist mit der Tatsache, dass einfach jemand sein Auto auf der >Straße mit dem Gartenschlauch abgespritzt hat? Dann ist die Straße auch >nass, aber es hat nicht geregnet.
Beahcte, dass oben steht, dass die Starße nicht nass also trocken ist. Und wenn die Straße trocken ist regnet es definitiv nicht. Formal: [mm] \neg [/mm] B [mm] \Rightarrow \neg [/mm] A.
Deine Schlussregel wäre aber, B [mm] \Rightarrow [/mm] A, was nur bei der Bijunktion nicht aber bei der Implikation zulässig ist!
|
|
|
| |
|
Hallo Jan,
es gibt durchaus noch mehrere Arten eines Widerspruchbeweises, wenn du z.B. zeigen willst, daß [mm] A \Rightarrow B[/mm] gilt, gibt es zum Einen die Kontraposition, aber auch verschiedene (eigentlich äquivalente) Möglichkeiten:
Vorraussetzung: A ist wahr
Führe [mm] A \wedge \neg B [/mm] zum Widerspruch, dann gilt A [mm] \Rightarrow [/mm] B.
All diese Indirekten Beweise sind aber meist nur verschiedene äquivalente Umformungen zu A [mm] \Rightarrow [/mm] B.
Zur Erinnerung: [mm](A \Rightarrow B) \gdw (\neg B \Rightarrow \neg A) \gdw (\neg (A \wedge \neg B)) \gdw (\neg A \vee B) [/mm]
Gruß,
Gono.
|
|
|
| |
|
>Vorraussetzung: A ist wahr
>Führe $ A [mm] \wedge \neg [/mm] B $ zum Widerspruch, dann gilt A $ [mm] \Rightarrow [/mm] $ B.
Genau der Teil interessiert mich besonders.
Welche Rolle spielt die wahre Voraussetzung? Ich stelle es mir momentan so vor, dass man ja allerlei Widersprüche herleiten kann, aber nur mit der wahren Voraussetzung bekommen sie wirklich Bedeutung für die Mathematik. Ich stelle mir A als einen Haken vor, bzw. als Bindeglied an dem man seinen Widerspruchsbeweis aufhängt.
Kannst du vielleicht noch ein treffende Bsp für einen Beweis geben der in genau dieser Art geführt wurde? Gerne auch Sätze in der natürlichen Sprache ;)...
Grüße Jan
P.S. Muss ich Zitate eigentlich wirklich von Hand einfügen und als solche kennzeichnen oder gibts da idealerweise sogar eine Forenfunktion für?
|
|
|
| |
|
Erstmal vorneweg: Zitieren kannst du (zumindest bei Antworten) indem du auf den Button unter dem Eingabefeld klickst, wo "Zitieren" draufsteht :D
So, dann wollen wir mal
> Welche Rolle spielt die wahre Voraussetzung? Ich stelle es
> mir momentan so vor, dass man ja allerlei Widersprüche
> herleiten kann, aber nur mit der wahren Voraussetzung
> bekommen sie wirklich Bedeutung für die Mathematik. Ich
> stelle mir A als einen Haken vor, bzw. als Bindeglied an
> dem man seinen Widerspruchsbeweis aufhängt.
Ja und Nein.
Es stimmt, daß A sozusagen der "Haken bzw. Bindeglied" ist, allerdings stimmt es nicht, daß du aus einer falschen Voraussetzungen Widersprüche herleiten kannst, da eine Folgerung aus etwas Falschem immer wahr und somit kein Widerspruch ist.
d.h. [mm] (A \Rightarrow B) [/mm] ist insgesamt immer wahr, wenn A falsch ist.
Und "die Voraussetzung A" für einen indirekten Beweis gibt es meines Erachtens nach nicht. Wenn man sich z.B. so einen Beweis wie den mit [mm] \sqrt{2} \in \IQ [/mm] genauer ansieht, wird man sich sein A erst mehr oder weniger im Beweis "konstruieren", d.h. ich führe meine negierte zu beweisende Aussage auf IRGENDEINEN bekannten Widerspruch zurück, oder auf einen Widerspruch in sich selbst.
Leider hab ich auf die schnelle keinen "typischen" indirekten Beweis, wie oben angesprochen (böse Zungen behaupten, die Kontraposition hätte den namen "indirekter Beweis" gar nicht verdient ), da die Beweisideen ja äquivalent sind und man heutzutage viel öfter die Kontraposition als die oben angesprochene Variante findet. D.h. man kann sich durchaus einen solchen Beweis konstruieren, den man aber genausogut auch anders führen könnte. Aber ich werd mich mal auf die Suche machen
Gruß,
Gono.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:24 Fr 02.03.2007 | | Autor: | Ankh |
Der Unterschied zwischen der Kontraposition einerseits, und einem Widerspruchsbeweis (bzw. indirektem Beweis) andererseits ist folgender:
Die Kontraposition einer logischen Formel A [mm] \Rightarrow [/mm] B ist, wie bereits gesagt, die äquivalente Formel [mm] \neg [/mm] B [mm] \Rightarrow \neg [/mm] A. Statt also aus der Voraussetzung A die Behauptung B abzuleiten, kann man genauso gut aus der Negation von B die Negation von A ableiten, und hat somit das gleiche Ergebnis.
Im Gegensatz dazu funktioniert ein indirekter Beweis für A [mm] \Rightarrow [/mm] B wie folgt: Wir setzen A als gegeben voraus und nehmen nun an, B würde nicht gelten. Daraus folgern wir einen Widerspruch, der im Allgemeinen durch zwei beliebige Aussagen der Form C und [mm] \neg [/mm] C repräsentiert wird. Es ist also ein BELIEBIGER Widerspruch gesucht. Es muss NICHT [mm] \neg [/mm] A abgeleitet werden. Das wäre zwar auch ein Widerspruch (zur Voraussetzung A), ist aber nicht notwendig.
Die Kontraposition ist somit ein Spezialfall des indirekten Beweises.
Im Prinzip kann man jeden direkten Beweis auch indirekt führen, aber nicht jeden indirekten direkt. Also ist der indirekte Beweis die stärkere Beweisform.
|
|
|
|
![[aetsch]](/images/smileys/aetsch.gif "[aetsch]"){kind=small}
![[cap]](/images/smileys/cap.gif "[cap]"){kind=small}
