Wie lautet der erste Satz, die Annahme des Widerspruchsbeweises für diese logische Aussage?

Question

Aufgabe:

Gib an: Den ersten Schritt, d.h. die erste Zeile, eines Beweises per Widerspruch und Kontraposition  für die
Aussage:

$$((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\longrightarrow (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))$$

Problem/Ansatz:

Für die Kontraposition ist es ja relativ klar:
$$Zu\quad zeigen\quad sei:\\ \neg (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\longrightarrow \neg ((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))$$

Aber wie mache ich dies bei dem Widerspruchsbeweis?

Ich ist ja eigentlich zu zeigen A=>nicht B?

Könnte mir Jemand helfen? Es ist sehr .

Answer 1

A → B   Ξ   ¬ (A ∧ ¬B)

dann ergibt sich aus der Annahme ¬B unter der Voraussetzung A ein Widerspruch.

Wenn jemand eine bessere Idee für eine Formalisierung des Begriffs "Widerspruchsbeweis" hat, würde mich das auch interessieren.

Gruß Wolfgang

Comments

Hallo Wolfgang,
danke für die schnelle Antwort.

A → B  Ξ  ¬ (A ∧ ¬B) Hier hast du die Definition der Implikation, dann der doppelten Negation und dann die De morganschen Regeln genutzt.

Die Frage wäre nur, was daran der Widerspruch ist? Ist ja immerhin Äquivalent.

Ich dachte eigentlich man geht von etwas wahren aus und versucht damit die negierte Lösung zu zeigen?

Die Andere Frage wäre, wie ich es dort oben anwende?

Was wäre A und was B?

Liebe Grüße Sabina

---

Hallo Sabina.

Die Frage wäre nur, was daran der Widerspruch ist?

A → B  soll durch Widerspruch bewiesen werden,

unter der Voraussetzung A soll die Behauptung B gelten

Wenn man nun unter der Annahme, dass B nicht gilt [¬B], zeigt, dass das zusammen mit A  [A∧¬B]  nicht wahr sein kann [¬ (A ∧ ¬B)], hat man doch bewiesen, dass ¬B  falsch und damit B wahr sein muss. Man hat also die Annahme ¬B zu einem Widerspruch geführt.

Was wäre A und was B?

Bei dir wäre in deiner 1. Zeile A alles vor → und B alles nach →

---

Also ist meine Annahme zum Widerspruch 
$$\neg (((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\quad \wedge \quad \neg (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x)))\\ \Leftrightarrow \\ \neg ((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\quad \vee \quad (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))$$

Und dies wäre dann auch die erste Zeile eines Widerspruchsbeweises?

---

Ich finde die Fragestellung in der Aufgabe einfach so komisch:

"Gib an: Den ersten Schritt, d.h. die erste Zeile, eines Beweises per Widerspruch und Kontraposition  für die Annahme..."

Wie würdest du dies bei dem Widerspruchsbeweis machen?

---

die 1. Zeile ist richtig

die Annahme, die zum Widerspruch geführt  wird, ist nur die 2. Zeile

die letzte Zeile verstehe ich nicht

---

$$((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\longrightarrow (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\\ \\ Negation:\\ \neg ((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\longrightarrow (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\\ \Leftrightarrow \quad Implikation\\ \neg (\neg (\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\quad \vee \quad (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\\ \Leftrightarrow \quad De\quad Morgan\\ ((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\quad \wedge \quad \neg (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\\ \\ \\$$

Dann wäre also meine Erste Zeile (um die Aufgabe oben zu erfüllen)

$$Widerspruchsannahme:\\ ((\forall x\epsilon Z.{ P }_{ 1 }(y-1)\vee { P }_{ 2 }(y))\wedge (\forall z\epsilon Z.{ P }_{ 2 }(z)\rightarrow { P }_{ 2 }(z-1)))\quad \wedge \quad \neg (\forall x\epsilon Z.{ P }_{ 1 }(x)\vee { P }_{ 2 }(x))\\ \\ \\$$ ?

---

Wäre damit die Aufgabe beantwortet?

---

Ja, das ist richtig

---

Das ist die "Widerspruchsannahme"!

Für die 1. Zeile des Beweises musst du wohl noch ein  ¬  vor das Ganze setzen.

Man will ja beweisen, dass die WA falsch ist.

---

Das ist die "Widerspruchsannahme"!

Für die 1. Zeile des Beweises musst du wohl noch ein  ¬  vor das Ganze setzen.

Man will ja beweisen, dass die WA falsch ist.

https://de.wikibooks.org/wiki/Mathe_f%C3%BCr_Nicht-Freaks:_Direkter_und_indirekter_Beweis

So habe ich es gemacht.

Ich habe die Negation der eigentlichen Annahme angenommen.

Nun verwirrst du mich erneut :()

Ist die Annahme nicht die erste Zeile des Beweises?

---

Du verwirrst dich selbst:

Ich habe die Negation der eigentlichen Annahme angenommen.

die Annahme ist  A ∧ ¬B

du beweist, dass diese Annahme falsch ist, also  ¬(A ∧ ¬B)

---

die Annahme ist  A ∧ ¬B

du beweist, dass diese Annahme falsch ist, also  ¬(A ∧ ¬B)

Ok kurz zum Verständnis für mich, denn ich kann dir nicht folgen.

Du sagst, die Annahme ist A ∧ ¬B <=> ¬(A → B)?
Nun sagst du, ich müsse die Negation der (eh schon negierten Ausgangsformel annehmen, also ¬¬(A → B) <=> (A → B).

Bitte könntest du es einmal vormachen?
Ich flippe hier gerade aus, weil wir uns im Kreis drehen und ich nun nichts mehr verstehe. xD

Wenn ich beweisen soll, dass n gerade ist, muss ich doch n ungerade annehmen?
Was du mir jetzt zeigst ist, n ist gerade, also nimm n gerade an.

---

Ich möchte dich wirklich nicht stören, aber du schreibst es zu kompliziert, beziehungsweise zu wirr, sodass ich nicht hinterherkomme :()

Es tut mir leid

---

Tut mir auch leid, aber deine Vorstellungen von einem Widerspruchsbeweis sind sehr wirr!

Schreib doch einfach

Annnhame:  A ∧ ¬B

zu zeigen:   ¬ (A ∧ ¬B)

Dabei setzt du für A und B  die Terme aus der Fragestellung so ein, wie ich sie oben beschrieben habe:

in deiner 1. Zeile A alles vor dem (großen) → und B  alles nach diesem →

wenn das zu "kompliziert und wirr" ist, kann ich dir leider nicht weiter helfen!

---

Moin ich würde mich hier gerne einmal einmischen.

@ Wolfgang, ich denke es ist für die Dame deshalb so verständlich weil du genau dies hier sagst.

Annahme: A ∧ ¬B <=> ¬(A->B)

Zu zeigen: ¬ (A ∧ ¬B) <=> (A->B)

Wenn wir davon ausgehen, dass mit Widerspruch gezeigt werden soll (A->B), dann ist es wirr.

Was du ja hier doch sagen willst ist: Negiere die eigentliche Annahme und zeige damit die eigentliche Annahme:)

Von daher wäre es klüger gewesen, es mit Worten zu sagen anstatt mit umgeformten Formeln um sich zu hauen, sodass Jemand auch gleich im Wiki hätte lesen können.

Die Antwort auf die Ausgangsfrage kann man also nur beantworten, wenn man weiß was die erste Zeile in solch einen Beweis sein sollte und dies ist meiner Meinung nach die Annahme, also ¬(A->B), oder?

---

@gabba

Wenn wir davon ausgehen, dass mit Widerspruch gezeigt werden soll (A->B), dann ist es wirr.

Genau das soll gezeigt werden und dann ist die zum Widerspruch zu führende Annahme A ∧ ¬B

und äquivalent  A→B zu zeigen:  ¬(A ∧ ¬B)

deshalb weise ich das entschieden zurück!

---

Du verstehst nicht:) Ich greife dich doch nicht an, du schreibst doch hoffentlich das richtige. Ich spreche hier nur aus der Sicht eines in der Mathematik unerfahrenen.

Verstehst du? Das was du schreibst ist für uns, normalerweise Hilfesuchende, zu wirr.

Hat also nicht mit der Richtigkeit deiner Aussage zu tun, nur das wir es nicht richtig verstehen, da wir nicht das Verständnis dafür haben.

Erkläre einen 6 Klässler Differenzialgleichungen, der guckt dich auch mit große Augen an.

Also wir fassen noch einmal zusammen:

Man hat eine Aussage die man über einen indirekten Beweis zeigen will, dafür muss diese negiert werden, denn wir wollen das FALSCHE annehmen um daraus das ehemals richtige zu zeigen, sehe ich das richtig?

Die Ausgangsfrage wäre damit allerdings immer noch offen, aber vlt hilft dies:

"A proof by contradiction must start with the negation of the formula to be proved. The formula to be proved is of the form A→B: its negation will be A∧¬B."

---

und dies ist meiner Meinung nach die Annahme, also ¬(A->B), oder?

Wenn ein indirekter Beweis nicht formal formuliert wird, geht man für

A → B   von der Annahme ¬B (unter der Voraussetzung A) aus und führt das zum Widerspruch.

Genau das kommt zum Ausdruck, wenn man als Annahme A∧¬B statt  ¬(A->B)  schreibt.

mit

A → B  Ξ  ¬ (A ∧ ¬B) Hier hast du die Definition der Implikation...

zeigt Sabina, das sie mit dem "um sich hauen mit Formeln" keine Probleme hatte.

---

ok, also wäre dann mit der ersten Zeile das A∧¬B gemeint? Also die Annahme?

---

Wie gabba gesagt hat:

Die Antwort auf die Ausgangsfrage kann man also nur beantworten, wenn man weiß was die erste Zeile in solch einen Beweis sein sollte...

Woher soll man wissen, was die meinen?

Wenn schon, dann 1. Zeile

Annahme: A∧¬B

sonst steht das   A∧¬B   ziemlich sinnlos rum :-)

Deshalb machst du mit meinem obigen Vorschlag in meinem letzten Kommentar vor gabba

Annahme: A∧¬B    [ von mir aus auch  ¬ (A → B)  ]

zu zeigen:  ¬ (A ∧ ¬B)

nichts falsch.