aber dies ist ein erfreuliches Ereignis, weil das neue Gebäude wesentlich stabiler und besser ist.

Zusammenfassung

Der Begriff der Folgerung (der Implikation) spielt eine Schlüsselrolle für eine korrekte Argumentation. Die Bedeutung der Folgerung A B (A impliziert B) ist, dass, wenn A gilt (wahr ist), auch B gilt. Es darf also nicht passieren, dass bei geltender Implikation A B die Aussage A wahr ist und die Aussage B nicht wahr ist. Alle anderen Situationen sind möglich. Wenn A nicht gilt, stellt die Folgerung A B keine Anforderungen an die Wahrhaftigkeit von B.

Einen direkten Beweis kann man als eine Folge von Implikationen

A B1 B2 ··· Bk Z

betrachten. Wenn alle diese Implikationen gelten, dann gilt auch die Implikation A Z. Wenn der Beweis der Implikation (der Aussage) „A Z“ unser Ziel war, dann sind wir fertig. Wenn wir schon wissen, dass A eine allgemeine Wahrheit in unserer Theorie ist und Z die Aussage ist, deren Wahrhaftigkeit wir beweisen sollen, dann dürfen wir nach der Definition der Implikation aus der Wahrhaftigkeit von

A und A Z

die Gültigkeit unserer Zielbehauptung Z schließen.

Der indirekte Beweis basiert auf der Tatsache, dass die Gültigkeit einer Aussage A und der Implikation Z A die Gültigkeit der Aussage Z fordert. Mit anderen Worten: Die Bedeutungen der Implikationen A Z und Z A sind äquivalent. Mit beiden kann man aus der Gültigkeit der Aussage A die Gültigkeit der Aussage Z schließen. Somit arbeitet das Schema des indirekten Beweises wie folgt: Wir wissen, dass A gilt und wollen die Gültigkeit von Z beweisen. Wir fangen mit Z als dem Gegenteil von Z an und erzeugen eine Folge von Implikationen.

Z B1 B2 ··· Bk U

Damit ist die Implikation Z U bewiesen. Wenn U = A gilt, sind wir fertig und können die Gültigkeit von Z behaupten. Im Allgemeinen muss U nicht identisch mit A sein. Es

307

reicht, wenn U eine unbestrittene Unwahrheit (Unsinn) ist, also eine Behauptung, die im Widerspruch zu irgendwelchen Sätzen (Kenntnissen) unserer Theorie steht.

In vielen Situationen ermöglichen indirekte Beweise eine vereinfachte und damit schnellere Beweisführung. Ohne Gebrauch dieses Instrumentes bei korrekter Argumentation würden wir uns das Leben unnötig schwer machen.

Kontrollfragen

1.Wie viele unterschiedliche Situationen sind möglich und in einer Wahrheitstabelle beschrieben, wenn man drei Aussagen A, B und C betrachtet? Wie groß ist die Wahrheitstabelle bei vier Aussagen? Wie ist es im allgemeinen bei n Behauptungen?

2.Erkläre mit eigenen Worten, wie du systematisch eine Wahrheitstabelle für gegebene Aussagen in beliebiger Anzahl konstruieren kannst.

3.Erkläre die Bedeutung der Implikation. Welche Situationen sind möglich und welche ausgeschlossen?

4.Warum kann man aus der Gültigkeit der Implikationen A B und B C auf die Gültigkeit der Implikation A C schließen?

5.Wie sieht das Schema des direkten Beweises aus?

6.Warum kann man aus der Gültigkeit der Aussage A und der Implikation A Z die Gültigkeit der Aussage Z ableiten?

7.Warum kann man aus der Gültigkeit der Aussage A und der Implikation Z A auf die Gültigkeit der Aussage Z schließen? Erkläre es mit eigenen Worten sowie mit der Wahrheitstabelle für die Behauptungen A und Z!

8.Wie sieht das Schema des indirekten Beweises aus?

9.Wie hängen direkte und indirekte Beweise zusammen?

10.Warum kann es vorteilhaft sein, direkte und indirekte Beweise zur Verfügung zu haben? Gib ein konkretes Beispiel an, für das ein indirekter Beweis einfacher ist und schneller zum Ziel führt als ein direkter Beweis.

Kontrollaufgaben

1.Seien A, B und C drei Behauptungen. Wir wissen, dass folgende Implikationen gelten.

(i)A B, B C, C A, A C.

(ii)A B, B C, C A, C B, A C.

(iii)B C, B A, C B, C A, C A, A C

Bestimme für alle drei Fälle (i), (ii) und (iii), welche der acht Situationen möglich und welche ausgeschlossen sind!

Tabelle 2.10

Welche der 36 Implikationen X Y für X , Y {A, B,C, A, B,C} gelten und welche gelten nicht?

3.Betrachten wir die folgenden drei Aussagen: A bedeutet: „Es ist unter −20◦C.“

B bedeutet: „Die Kleinvögel frieren.“ C bedeutet: „Die Kleinvögel singen.“

Jetzt wissen wir, dass die Implikationen A B und B C gelten. Wir stellen fest, dass die Kleinvögel singen. Was kann man daraus schließen?

4.In der Tabelle 2.11 fehlen in der ersten Zeile drei Implikationen. Kannst du sie bestimmen?

309

Tabelle 2.11

Jetzt stellen wir fest, dass C gilt. Was kann man daraus schließen? Und was würde man schließen, wenn C gelten würde?

5.Sei A die Behauptung „3x −6 = 5x −10“ und sei B die Behauptung „x = 2“. Beweise die Gültigkeit der Implikation A B.

6.Beweise für A und B aus Kontrollaufgabe 5 mit einem indirekten Beweis die Behauptung

„Wenn 3x −6 = 5x −10 gilt, dann gilt x = 2.“

7.Beweise mit einem direkten Beweis die folgende Behauptung: „Wenn die linearen Gleichungen

2x + y = 0

7x −2y = −11

gelten, dann gilt x = −1 und y = 2“. Dabei darfst du alle dir bekannten Umformungen von Gleichungen und linearen Gleichungssystemen als gültige Behauptungen (Sätze) deiner Theorie verwenden.

8. Sei

ax + by = c dx + ey = f

die allgemeine Darstellung eines Systems von zwei linearen Gleichungen und zwei Unbekannten x und y. Beweise mittels des direkten Beweises, dass die Gültigkeit dieser zwei Gleichungen die Gültigkeit der folgenden Gleichung impliziert:

y = a f + de . ac + db

9.Kannst du die Formel für die Berechnung des Wertes der Unbekannten x im Falle der Gültigkeit des Gleichungssystems in Kontrollaufgabe 8 überprüfen?

10. Beweise, dass „wenn ax2 −c = 0 und ac > 0 gelten, dann gilt x { ac , − ac }.“

11.Nehmen wir an, dass x2 + bx + c = 0 und b2 − 4c ≥ 0 gelten. Beweise, dass dann die Lösungen x1, x2 der quadratischen Gleichung die Gleichungen

b = −x1 −x2 c = x1 ·x2

erfüllen. Dabei kannst du folgende zwei Sätze als gültig in deiner Theorie betrachten:

(i)Zwei Polynome sind nur dann gleich, wenn alle ihre Koeffizienten gleich sind.

(ii)Wenn x1 und x2 die Nullstellen eines quadratischen Polynoms p(x) sind (Lösungen der entsprechenden quadratischen Gleichung), dann gilt: p(x) = (x −x1) ·(x −x2).

12.Beweise die folgende Aussage: Wenn die Behauptung „p teilt a und p teilt b“ gilt, dann gilt auch die Behauptung „p teilt 5a −3b“.

13.Beweise die folgende Aussage: Wenn die Zahl a die Zahl b teilt, dann teilt das GGT(a, b) die Zahl b.

14.(Knobelaufgabe) Beweise, dass für beliebige positive ganze Zahlen a und b die Zahl GGT(a, b) die kleinste positive ganze Zahl in der unendlichen Menge {a ·x + b ·y | x, y Z} ist.

15.Beweise mittels eines indirekten Beweises die folgende Behauptung: „Wenn 5 die Zahl x2 teilt, dann teilt 5 auch x“.

√

16. Beweise, dass 5 keine rationale Zahl ist.

17. Finde die kleinste Zahl j, so dass die folgende Implikation nicht für alle x Z+ gilt:

„Wenn j die Zahl x2 teilt, dann teilt j auch die Zahl x.“

18. Nehmen wir an, dass wir in unserer Theorie schon bewiesen haben: