Mod-2.51 2x Beweise verstehen und konstruieren Beweise werden in vielen Gebieten der Informatik benötigt * innerhalb von Informatik-Theorien z.B. Komplexität von Aufgaben und Algorithmen * Eigenschaften von modellierten Aufgaben z.B. Falls ein ungerichteter Graph zusammenhängend ist, gibt es mindestens einen Weg von Knoten a nach Knoten b. * Entwurf von Hardware und Software z.B. Diese Synchronisation der "Dining Philosophers" führt nie zur Verklemmung. * Eigenschaften implementierter Software oder Hardware Verifikation von Programmeigenschaften Dieses Thema wird im Buch "Modellierung" im Abschnitt 4.3 behandelt. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 251 Ziele: Beweisen in der Informatik motivieren in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.52 Beispiel 1 Satz 2x.1: Seien A und B zweistellige, antisymmetrische Relationen über der Menge M. Dann ist C = A union B auch eine antisymmetrische Relation. Beweis: Wegen der Definition von antisymmetrisch gilt: Für alle x, y element M gilt: Aus x A y und y A x folgt x = y. Ebenso gilt: Für alle x, y element M gilt: Aus x B y und y B x folgt x = y. Wegen C = A union B sind alle Elemente aus A oder B auch Elemente von C und es gilt: Für alle x, y element M gilt: Aus x C y und y C x folgt x = y. Also ist auch C antisymmetrisch. qed. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 252 Ziele: Beweis verstehen und prüfen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.53 Gegenbeispiel Der Satz 2x.1 Seien A und B zweistellige, antisymmetrische Relationen über der Menge M. Dann ist C = A union B auch eine antisymmetrische Relation. ist nicht korrekt. Man kann ihn durch ein Gegenbeispiel widerlegen: z.B. A = {(a, a), (b, c)}, B = {(d, d), (c, b)}, C = {(a, a), (b, c), (d, d), (c, b)} Der "Beweis" von Satz 2x.1 ist fehlerhaft. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 253 Ziele: Beweis verstehen und prüfen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.54 Beispiel 2 Satz 2x.2: Seien A und B zweistellige, symmetrische Relationen über der Menge M. Dann ist C = A union B auch eine symmetrische Relation. Beweis: Sind A und B leer, dann ist auch C leer und ist gemäß Definition symmetrisch. Ist C nicht leer, dann sei x C y für beliebige x und y. Wegen C = A union B gilt x A y oder x B y. Falls x A y gilt, dann ist auch y A x, weil A symmetrisch ist. Wegen C = A union B ist auch y C x. Falls x B y gilt, dann ist auch y B x, weil B symmetrisch ist. Wegen C = A union B ist auch y C x. Also folgt aus x C y auch y C x. Deshalb ist auch C symmetrisch. qed. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 254 Ziele: Beweis verstehen und prüfen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.55 Eigenschaften von Beweisen Beweise können * korrekt oder fehlerhaft, * verständlich oder unverständlich, * elegant oder umständlich, * wohl-strukturiert oder verschlungen sein. Zur Konstruktion von Beweisen gibt es * Regeln, Methoden, Strukturen, Strategien. Dazu wird in diesem Abschnitt eingeführt. Erst Kapitel 4 liefert die notwendigen Grundlagen der Logik. Das Buch [D. J. Velleman: How to prove it] enthält umfassendes Material zu diesem Thema. Manche Beweise benötigen außerdem eine gute Beweisidee. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 255 Ziele: Ziel dieses Abschnittes erkennen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.56 Form von Satz und Beweis Ein Satz (Theorem) besteht aus Voraussetzungen (Prämissen) und einer Behauptung (Konklusion). Voraussetzungen und Behauptung sind Aussagen. Wenn alle Voraussetzungen wahr sind, dann muss auch die Behauptung wahr sein. Satz 2x.2: Seien A und B zweistellige, symmetrische Relationen über der Menge M. Dann ist C = A union B auch eine symmetrische Relation. Der Beweis eines Satzes muss nachweisen, dass die Behauptung wahr ist und kann dabei verwenden * die Voraussetzungen, * Definitionen oder bekannte Tatsachen, * im Beweis selbst oder anderweitig als wahr bewiesene Aussagen, * Schlussregeln. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 256 Ziele: Grundbegriffe zu Satz und Beweis in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.57 Beweisstruktur Fallunterscheidung Beweise können in Fallunterscheidungen gegliedert sein. Typische Gründe dafür: * Sonderfall abspalten (z.B. leer, nicht leer) * oder in der Voraussetzung (z.B. (x, y) element C = A union B bedeutet (x, y) element A oder (x, y) element B) * und in der Behauptung (Beispiel später) Beweis 2x.2: Sind A und B leer, dann ist auch C leer und ist gemäß Definition leer symmetrisch. nicht leer Ist C nicht leer, dann sei x C y für beliebige x und y. Wegen C = A union B gilt x A y oder x B y. (x, y) element A Falls x A y gilt, dann ist auch y A x, weil A symmetrisch ist. Wegen C = A union B ist auch y C x. (x, y) element B Falls x B y gilt, dann ist auch y B x, weil B symmetrisch ist. Wegen C = A union B ist auch y C x. Also folgt aus x C y auch y C x. Deshalb ist auch C symmetrisch. qed. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 257 Ziele: Beweise durch Fallunterscheidung strukturieren in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.58 Implikation als Behauptung Satz 2x.3: Sei R eine zweistellige Relation über der Menge M. Wenn a R b und b R a mit a notequal b, dann ist R weder eine Halbordnung (HO), noch eine strenge Halbordnung (sHO), noch eine totale Ordnung (tO). Die Behauptung des Satzes hat die Form P impliziert (Q1 und Q2 und Q3) (a R b und b R a mit a notequal b) impliziert (nicht HO und nicht sHO und nicht tO) Hier kann man zwei Techniken zur Gliederung des Beweises anwenden: * Behauptung P impliziert Q: füge P zu den Voraussetzungen und beweise Q. * Behauptung Q1 und Q2 und ...: beweise jedes Qi in einem einzelnen Fall. Damit bekommt der Beweis 2x.3 folgende Struktur: Beweis 2x.3: Wir nehmen an, es gelte P = (a R b und b R a mit a notequal b) Beweis aus Voraussetzung und P folgt nicht HO Beweis aus Voraussetzung und P folgt nicht sHO Beweis aus Voraussetzung und P folgt nicht tO also aus P folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 258 Ziele: Zwei Techniken zur Beweisstrukturierung in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.59 Beweisstruktur ausfüllen Beweis 2x.3: Wir nehmen an, es gelte a R b und b R a mit a notequal b für die zweistellige Relation R über der Menge M. 1. Dann verletzen a R b und b R a die Definition für Antisymmetrie. Also ist R nicht eine Halbordnung. 2. Da R gemäß (1) nicht antisymmetrisch ist, ist R auch nicht eine totale Ordnung. 3. Gemäß Satz 2x.4 (Mod-2.61) ist R nicht eine strenge Halbordnung. Also folgt aus a R b und b R a mit a notequal b, dass R weder eine Halbordnung, noch eine strenge Halbordnung, noch eine totale Ordnung ist. qed. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259 Ziele: Beweisstruktur ausfüllen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.59b Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) Beweisstruktur: (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259b Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59c Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259c Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59d Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) logicalnot sHO logicalnot tO Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO Beweis aus Voraussetzung und Z folgt nicht tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259d Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59e Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) R nicht antisymmetrisch (wg. Def. antisy.) logicalnot sHO logicalnot tO Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO Beweis aus Voraussetzung und Z folgt nicht tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259e Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59f Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) R nicht antisymmetrisch (wg. Def. antisy.) logicalnot sHO R ist nicht Halbordnung (wg. Def. HO) logicalnot tO Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO Beweis aus Voraussetzung und Z folgt nicht tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259f Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59g Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) R nicht antisymmetrisch (wg. Def. antisy.) logicalnot sHO R ist nicht Halbordnung (wg. Def. HO) logicalnot tO R ist nicht totale Ordnung (wg. Def. tO.) Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO Beweis aus Voraussetzung und Z folgt nicht tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259g Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59h Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) R nicht antisymmetrisch (wg. Def. antisy.) logicalnot sHO R ist nicht Halbordnung (wg. Def. HO) logicalnot tO R ist nicht totale Ordnung (wg. Def. tO.) nicht sHO wird separat bewiesen (2x.4) Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO Beweis aus Voraussetzung und Z folgt nicht tO also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259h Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.59i Konstruktionshilfen am Beispiel für Beweis 2x.3 gültige Aussagen: Behauptungen: R element Pow (M multiply M) a R b logicaland b R a logicaland a notequal b arrowright ( logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO) a R b logicaland b R a logicaland a notequal b (wg. Implik. in Beh.) logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO logicalnot HO (3 Fälle wg. Konjunktion) R nicht antisymmetrisch (wg. Def. antisy.) logicalnot sHO R ist nicht Halbordnung (wg. Def. HO) logicalnot tO R ist nicht totale Ordnung (wg. Def. tO.) nicht sHO wird separat bewiesen (2x.4) Beweisstruktur: Wir nehmen an, es gelte Z = (a R b logicaland b R a logicaland a notequal b) Beweis aus Voraussetzung und Z folgt logicalnot HO logicaland logicalnot sHO logicaland logicalnot tO Beweis aus Voraussetzung und Z folgt nicht HO Beweis aus Voraussetzung und Z folgt nicht sHO abschließend Beweistext Beweis aus Voraussetzung und Z folgt nicht tO zusammensetzen also aus Z folgt (nicht HO und nicht sHO und nicht tO) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 259i Ziele: Beweis konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Behauptung vereinfachen, zerlegen, transformieren. * Definitionen zu gültigen Aussagen hinzunehmen. * Weitere gültige Aussagen ableiten. * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.60 Methode: Beweis durch Widerspruch Ein Beweis durch Widerspruch führt häufig zum Ziel, wenn die Behauptung eine Negation ist: Satz: Voraussetzung V. Behauptung nicht P. Man nimmt dann die nicht-negierte Behauptung mit als Voraussetzung auf und leitet mit Schlussregeln daraus einen Widerspruch her, d.h. eine Aussage, die immer falsch ist, z. B. (x element M und x notelement M). Beweis: Aus V und P folgt ein Widerspruch. Also war die Annahme P falsch. Also gilt nicht P. qed. Häufig ist nicht P ein geeignetes Ziel für den Widerspruchsbeweis: Beweis: Aus V und P folgt nicht P. Also gilt (P und nicht P). Also war die Annahme P falsch, also gilt nicht P. qed. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 260 Ziele: Methode Widerspruchsbeweis kennenlernen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.61 Beispiel für Beweis durch Widerspruch Satz 2x.4: Sei R eine zweistellige Relationen über der Menge M. Wenn a R b und b R a mit a notequal b, dann ist R nicht eine strenge Halbordnung. Beweis durch Widerspruch: Sei a R b und b R a mit a notequal b. Wir nehmen an, dass R eine strenge Halbordnung ist. Dann muss R irreflexiv und transitiv sein. Wegen der Transitivität folgt aus a R b und b R a auch a R a und b R b. a R a verletzt jedoch die Definition von Irreflexivität. Also ist die Annahme, dass R eine strenge Halbordnung ist, falsch. Also ist R nicht eine strenge Halbordnung. qed. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261 Ziele: Methode Widerspruchsbeweis anwenden in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-2.61a Satz 2x.5 zur Konstruktion eines Widerspruchsbeweises Satz 2x.5: A, B, C seien Mengen mit A \ B reflexsubset C. Dann gilt: Aus x element A \ C folgt x element B. C A B A \ B A \ C x (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261a Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61b Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B A \ B reflexsubset C Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261b Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61c Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B Implikation A \ B reflexsubset C x element B (es gibt ein x element A \ C) Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. Es gibt ein x element A \ C. Beweise x element B. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261c Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61d Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B Implikation A \ B reflexsubset C x element B zeige Widerspruch (es gibt ein x element A \ C) welchen? x notelement B Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. Es gibt ein x element A \ C. Beweise x element B. Wir nehmen an x notelement B und zeigen einen Widerspruch: (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261d Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61e Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B Implikation A \ B reflexsubset C x element B zeige Widerspruch (es gibt ein x element A \ C) welchen? x notelement B Def. \ x element A x notelement C Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. Es gibt ein x element A \ C. Beweise x element B. Wir nehmen an x notelement B und zeigen einen Widerspruch: Wegen x element A \ C gilt x element A und x notelement C. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261e Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61f Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B Implikation A \ B reflexsubset C x element B zeige Widerspruch (es gibt ein x element A \ C) welchen? x notelement B Def. \ x element A x notelement C x element C Widerspruch! Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. Es gibt ein x element A \ C. Beweise x element B. Wir nehmen an x notelement B und zeigen einen Widerspruch: Wegen x element A \ C gilt x element A und x notelement C. Wegen A \ B reflexsubset C und x notelement B und x element A gilt xelement C. Das ist ein Widerspruch. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261f Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.61i Konstruktion eines Widerspruchsbeweises 2x.5 gültige Aussagen: Behauptungen: A, B, C Mengen x element A \ C arrowright x element B Implikation A \ B reflexsubset C x element B zeige Widerspruch (es gibt ein x element A \ C) welchen? x notelement B Def. \ x element A x notelement C x element C Widerspruch! Beweisstruktur: Für die Mengen A, B, C gilt A \ B reflexsubset C. Es gibt ein x element A \ C. Beweise x element B. Wir nehmen an x notelement B und zeigen einen Widerspruch: Wegen x element A \ C gilt x element A und x notelement C. Wegen A \ B reflexsubset C und x notelement B und x element A gilt xelement C. Das ist ein Widerspruch. Also ist die Annahme x notelement B falsch; es gilt x element B. Also, für Mengen A, B, C mit A \ B reflexsubset C gilt: Aus x element A \ C folgt x element B. q.e.d. (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 261i Ziele: Widerspruchsbeweis schrittweise konstruieren in der Vorlesung: Erläuterungen dazu * Ausgehen von Voraussetzungen und Behauptung. * Implikation zerlegen. * Behauptung negieren und zum Widerspruch führen * Beweis ausformulieren. -------------------------------------------------------------------------------- Mod-2.62 Unendlich viele Primzahlen Satz 2x.6: Es gibt unendlich viele Primzahlen. Beweis durch Widerspruch (nach Euclid) 2x.6: Wir nehmen an, dass es endlich viele Primzahlen gibt, nämlich p1, p2, ..., pn. Sei m = p1p2...pn + 1. m ist nicht durch p1 teilbar, denn m dividiert durch p1 ergibt p2...pn mit Rest 1. Aus demselben Grund ist m nicht durch p2, ..., pn teilbar. Wir verwenden nun die Tatsache, dass jede natürliche Zahl, die größer als 1 ist, entweder eine Primzahl ist oder als Produkt von Primzahlen geschrieben werden kann. m ist größer als 1, also ist m entweder eine Primzahl oder m ist ein Produkt von Primzahlen. Nehmen wir an, m ist eine Primzahl. m ist größer als jede Zahl p1, p2, ..., pn. Also haben wir eine weitere Primzahl gefunden. Das widerspricht der Annahme, dass p1, p2, ..., pn alle Primzahlen sind. Nehmen wir nun an, dass m ein Produkt von Primzahlen ist. Sei q eine dieser Primzahlen. Dann ist q ein Teiler von m. Da p1, p2, ..., pn nicht Teiler von m sind, haben wir eine weitere Primzahl gefunden. Das ist wie oben ein Widerspruch. Die Annahme, dass es endlich viele Primzahlen gibt, hat zum Widerspruch geführt. Also gibt es unendlich viele Primzahlen. qed. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 262 Ziele: Beweisstruktur verstehen in der Vorlesung: * Voraussetzungen und Behauptung des Satzes identifizieren. * Negation der Behauptung als Annahme. * Tatsache über Primzahlen als weitere Voraussetzung verwenden. * Oder in der Voraussetzung führt zu Fallunterscheidung. * Jeder Fall wird einzeln zum Widerspruch geführt. -------------------------------------------------------------------------------- Mod-2.63 Methode: Beweis durch Induktion Beweise durch Induktion sind geeignet für Aussagen der Form Für alle n element Iota N0 gilt P (n) . Ein Beweis durch Induktion hat folgende Struktur: Induktionsanfang:Beweis von P (0) . Induktionsschritt:Sei n element Iota N0 beliebig aber fest. Beweis von Aus P (n) folgt P (n+1). qed. Manchmal reicht im Beweis des Induktionsschrittes P (n) als Vorbedingung nicht aus. Dann kann man in der folgenden Variante P (0), P (1), ..., P (n) verwenden: Variante des Induktionsbeweises: Induktionsanfang: Beweis von P (0) . Induktionsschritt: Sei n element Iota N0 beliebig aber fest. Beweis von Aus [P (0), P (1), ..., P (n)] folgt P (n+1). qed. Zum Beweis von Aussagen der Form Für alle n element Iota N0 , n greaterequal k gilt P (n) beginnt man im Induktionsanfang mit P (k) statt P (0). Statt Beweis durch Induktion sagt man auch Beweis durch vollständige Induktion. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 263 Ziele: Beweismethode Induktion verstehen in der Vorlesung: * Struktur erklären. -------------------------------------------------------------------------------- Mod-2.64 Beispiel für Beweis durch Induktion Satz 2x.7: Für alle n element Iota N0 gilt 20 + 21 + ... + 2n = 2n+1 - 1. Beweis durch Induktion: Induktionsanfang: Für n = 0 gilt 20 = 1 = 21 - 1. Induktionsschritt: Sei n element Iota N0 beliebig aber fest und sei 20 + 21 + ... + 2n = 2n+1 - 1. Dann ist 20 + 21 + ... + 2n + 2n+1 = (20 + 21 + ... + 2n) + 2n+1 = (2n+1 - 1) + 2n+1 = 2 * 2n+1- 1 = 2n+2 - 1 qed. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 264 Ziele: Beispiel zur Beweismethode Induktion in der Vorlesung: * Beispiel nachvollziehen. -------------------------------------------------------------------------------- Mod-2.65 Zusammenfassung Satzform: Voraussetzungen V. Behauptung B. Beweismethoden: Direkter Beweis: Aus V und bewiesenen Tatsachen mit Schlussregeln B nachweisen. Widerspruchsbeweis: Nicht B annehmen. Aus V und nicht B einen Widerspruch ableiten. Also gilt B. Induktionsbeweis von Behauptung B = Für alle n element Iota N0 gilt P (n): Induktionsanfang: Beweis von P (0), Induktionsschritt: Beweis von Aus P (n) folgt P (n+1) Techniken: Fallunterscheidung bei Sonderfällen, V1 oder V2, B1 und B2 Wenn B = P impliziert Q, dann aus V und P die Behauptung Q folgern. Viele weitere Strategien, Techniken und Beispiele im Buch von Velleman, z.B. Wenn B = P impliziert Q, dann aus V und nicht Q die Behauptung nicht P folgern. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 265 Ziele: Methoden und Techniken anwenden können in der Vorlesung: Zum Üben ermuntern. --------------------------------------------------------------------------------