Dr. Jürgen RothFachbereich 6: AbteilungDidaktik der Mathematik
Dr. Jürgen Roth
1.1
Elemente der Algebra
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.2
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Organisatorisches
Informationen und Materialien
http://www.juergen-roth.de Lehre
Abgabe der bearbeiteten Übungsblätter
Bis Donnerstag, 12:00 Uhr in meinem Fach am ENC
Neu: Abgabetermin für das 1. Übungsblatt: Donnerstag, 30.10.2008 bis 12:00 Uhr in mein Fach am ENC
Klausur: Keine Hilfsmittel
„Scheinkriterien“
„Kleiner Schein“ 4 KP30% der erreichbaren BE in den Übungen
40% der in der Klausur am Ende des Semesters erreichbaren BE
„Großer Schein“ 6 KP50% der erreichbarenBE in den Übungen
60% der in der Klausur am Ende des Semesters erreichbaren BE
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.3
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Inhaltsverzeichnis
Elemente der Algebra
1 Programm & Argumentationsgrundlagen
2 Funktionen
3 Lineare Funktionen, Gleichungenund Gleichungssysteme
4 Quadratische Funktionen und Gleichungen
5 Exponentialfunktionen
Dr. Jürgen Roth
1.4
Dr. Jürgen RothFachbereich 6: AbteilungDidaktik der Mathematik
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
1 Pro-gramm& Grund-lagen
1 Programm und Argumentationsgrundlagen
Elemente der Algebra
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.5
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Inhaltsverzeichnis
1 Programm und Argumentationsgrundlagen
1.1 Algebra?!
1.2 Mengen und Aussagenlogik
1.3 Beweistechniken
Dr. Jürgen Roth
1.6
Dr. Jürgen RothFachbereich 6: AbteilungDidaktik der Mathematik
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
1 Pro-gramm& Grund-lagen
1.1 Algebra?!
1 Programm und Argumentationsgrundlagen
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.7
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Algebra?!
al-Kitāb al-muhtasar fī hisāb al-ğabr wa-l-muqābala
„Das umfassende Buch vom Rechnen durch Ergänzung & Ausgleich“
„Algebra“ entstammt obigem Titel des Rechen-Lehrbuchsvon Al-Hwārizmī (Mohammed ben Musa)
persischer Mathematiker ca. 780 – ca. 850 n. Chr.
Bedeutung von al-ğabr
Wörtlich: „Ausüben von Zwang”
in der Gleichungslehre: „Ergänzen” einer Gleichungdurch Addition negativer Glieder auf beiden Seiten
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.8
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Algebra?!
„Der Hauptzweck der Algebra sowie aller Theile der Mathematik besteht darin, den Werth solcher Größen zu bestimmen, die bisher unbekannt gewesen, was aus genauer Erwägung der Bedingungen geschieht. Daher wird die Algebra auch als die Wissenschaft definirt, welche zeigt, wie man aus bekannten Größen unbekannte findet.“
Euler, Leonhard: Vollständige Anleitung zur Algebra. Neue Ausgabe, Reclam Verlag, Leipzig, o. J., S. 217
Leonhard Euler (1707-1783): „Vollständige Anleitung zur Algebra“, 1770
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.9
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Algebra?!
(klassische) Algebra
Lösen allgemeiner algebraischer Gleichungen (reelle oder komplexe Zahlen)
zentrales Resultat: Fundamentalsatz der Algebra
(abstrakte) Algebra
Grundlagendisziplin der modernen Mathematik
algebraische Strukturen (Gruppen, Ringe, Körper)& deren Verknüpfung
Computeralgebra
symbolische Manipulation algebraischer Ausdrücke
sucht effiziente Algorithmen & bestimmt die Komplexität ( CAS)
(elementare) Algebra
Algebra im Sinne der Schulmathematik
Umgang mit
natürlichen, ganzen, gebro-chenen & reellen Zahlen
Termen und Funktionen
Wege zur Lösung einfacher algebraischer Gleichungen
Dr. Jürgen Roth
1.10
Dr. Jürgen RothFachbereich 6: AbteilungDidaktik der Mathematik
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
1 Pro-gramm& Grund-lagen
1.2 Mengen und Aussagenlogik
1 Programm und Argumentationsgrundlagen
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.11
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Was ist eine Menge?
„Unter einer ‚Menge‘ verstehen wirjede Zusammenfassung M von
bestimmten wohlunterschiedenenObjekten m unserer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von M genannt
werden) zu einem Ganzen.“Georg Cantor (in: Beiträge zur Begründung der transfiniten
Mengenlehre (1895 und 1897), Math. Annalen, S. 481)
Bemerkung:Intuitiv kann man sich eine Menge als Zusammenfassung von Objekten (den Elementen der Menge) vorstellen, die durch bestimmte Eigenschaften ausgezeichnet sind.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.12
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beschreibung von Mengen
Beschreibung durch (angedeutete) Aufzählung
Menge der Farben rot, blau, gelb und grün
{rot, blau, gelb, grün}
Menge der Zahlen 1, 2, 3, 4 und 5
{1, 2, 3, 4, 5}
Leere Menge
{} = ∅
Menge N der natürlichen Zahlen
N = {1, 2, 3, 4, 5, …}
Menge N0 der natürlichen Zahlen einschließlich Null
N0 = {0, 1, 2, 3, 4, 5, …}
Menge Z der ganzen Zahlen
Z = {0, 1, –1, 2, –2, 3, –3, 4, –4, 5, –5, …}
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.13
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beschreibung von Mengen
Beschreibung durch charakterisierende Eigenschaft(en)
Menge Q+ der positiven rationalen Zahlen (Bruchzahlen)
Q+ = { | z ∈ N und n ∈ N}
Menge Q der rationalen Zahlen
Q = { | z ∈ Z und n ∈ N}
Menge R der reellen Zahlen
Menge aller Punkte der lückenlos besetzten Zah-lengeraden (Im Wesentlichen.)
nz
nz
…CRQZN
x ∈ M : „x ist Element von M.“x ∉ M : „x ist nicht Element von M.“
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.14
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Aussage, Aussageform
Aussage p
Formulierung, die entweder wahr oder falsch ist.
Beispiele:13 ist eine Primzahl.
(wahr)
4 ist eine Primzahl.
(falsch)
2 + 3 = 5 (wahr)
2 + 3 = 6 (falsch)
Aussageform p(x)
Formulierung, die beim Einsetzen eine Aussage ergibt.
Beispiele:x ist eine Primzahl.
(in R erfüllbar)
2 + x = 5
(in R erfüllbar)
x + x = 2x
(in R allgemeingültig)
x + 1 = x + 2
(in R unerfüllbar)Aussagen?„Schnee ist weiß.“„Alle Kreter lügen.“
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.15
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beschreibung von Mengen
Angabe einer Grundmenge G und einer Aussageform p(x)
Ist P die Menge der Elemente x mit der Eigenschaft p, so schreibt man P = {x | p(x)}.
Dabei bedeutet p(x), dass die Aussage p für x wahr ist.
Beispiele:
P = {n ∈ N | n ist eine Primzahl.} ⊂ N
P ist die Erfüllungsmenge der Aussageform p(n) über der Grundmenge N.
{n ∈ {1, 2, 3, 4} | n ist eine Primzahl} = {2, 3}
{(x, y) ∈ R × R | x2 + y2 = 4} ⊂ R × R
Grundmenge Aussageform p(n)
p(x) ⇔ x ∈ P¬p(x) ⇔ x ∉ P
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.16
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beschreibung von Mengen
Definition:Die Aussageformen p(x) und q(x) heißen äquivalent über der Grundmenge G, wenn gilt
P = {x ∈ G | p(x)} = {x ∈ G | q(x)} = Q.
Man schreibt p(x) ⇔ q(x)
und spricht p(x) genau dann, wenn q(x).
Beispiel:
{x ∈ R | |x| ≤ 2} = {x ∈ R | –2 ≤ x ≤ 2}
also |x| ≤ 2 ⇔ –2 ≤ x ≤ 2
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.17
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Quantoren
Allquantor ∀
Ist die Erfüllungsmenge einer Aussageform p(x) gleich der Grundmenge G, ist die Aussage p(x0) also für jedes Element x0 ∈ G wahr, dann heißt p(x) allgemeingültig über G.
{x ∈ G | p(x)} = G
Man schreibt ∀x∈G p(x)
und spricht „Für alle x ∈ G gilt p(x).“
Existenzquantor ∃
Existiert für eine Aussageform p(x) ein Element x0 der Grundmenge G, so dass die Aussage p(x0) wahr ist, dann heißt p(x) erfüllbar über G.
{x ∈ G | p(x)} ≠ ∅
Man schreibt ∃x∈G p(x)
und spricht „Es existiert ein x ∈ G, so dass gilt p(x).“
Beispiel:∀x∈G x + x = 2x
Beispiel:∃x∈G 2 + x = 5
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.18
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Quantoren
Man darf die Reihenfolge von Quantoren nicht vertauschen!
Beispiel:
∀n∈N ∃m∈N m > n
Für jede natürliche Zahl n gibt es einenatürliche Zahl m die größer als n ist.
Diese Aussage ist sicher wahr. Man wähle etwa m := n + 1.
∃m∈N ∀n∈N m > n
Es existiert eine natürliche Zahl m, so dass für jede natürlichen Zahlen n gilt: m ist größer als n.
Diese Aussage ist falsch, denn es gibt keine natürliche Zahl, die größer als alle anderen natürlichen Zahlen ist. (Gäbe es eine solche Zahl, müsst man nur 1 addieren um zu einer größeren natürlichen Zahl zu kommen.)
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.19
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Präsenzaufgabe
Drücken Sie folgende Aussagen in einfachen Worten aus:
a)
b)
c)
d)
Untersuchen Sie welche der Aussagen jeweils in den Grundmengen G = N, G = Z und G = Q+ wahr ist.
1
1
=⋅∃∀
=⋅∀∃
≤∃∀
≤∀∃
∈∈
∈∈
∈∈
∈∈
yx
yx
yx
yx
xy
yx
xy
yx
GG
GG
GG
GG
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.20
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Junktoren: Operationen für Aussagen
Negation ¬ p (Nicht p.) (Das Gegenteil von p.)
Konjunktion p ∧ q (p und q.) (Sowohl p als auch q.)
Disjunktion p ∨ q (p oder (auch) q) (p oder q oder beide)
Implikation p ⇒ q (Wenn p, dann q.)
Koimplikation p ⇔ q (p genau dann, wenn q.)
Wahrheitstafel
p q ¬ p p ∧ q p ∨ q p ⇒ q ¬ p ∨ q
w w f w w w w
w f f f w f f
f w w f w w w
f f w f f w w
p q ¬ p p ∧ q p ∨ q p ⇒ q ¬ p ∨ q
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.21
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Junktoren: Operationen für Aussagen
Negation ¬ p (Nicht p.) (Das Gegenteil von p.)
Konjunktion p ∧ q (p und q.) (Sowohl p als auch q.)
Disjunktion p ∨ q (p oder (auch) q) (p oder q oder beide)
Implikation p ⇒ q (Wenn p, dann q.)
Koimplikation p ⇔ q (p genau dann, wenn q.)
Wahrheitstafel
p q p ⇒ q q ⇒ p p ⇔ q (p ⇒ q) ∧ (q ⇒ p)
w w w w w w
w f f w f f
f w w f f f
f f w w w w
p q p ⇒ q q ⇒ p p ⇔ q (p ⇒ q) ∧ (q ⇒ p)
w w w
w f f
f w w
f f w
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.22
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Implikation: p ⇒ q
Sprechweisen
Wenn p, dann q.
q, wenn p.
q mindestens dann, wenn p.
p nur dann, wenn q.
p höchstens dann, wenn q.
Aus p folgt q.
q folgt aus p.
p impliziert q.
p ist hinreichend für q.
q ist notwendig für p.
q ist mindestens so wahr wie p.
Beispiel:p : Herr Roth ist
Dozent im Fachbereich 6.
q : Herr Roth ist Dozent der Universität Siegen.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.23
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Sprechweisen
p genau dann, wenn q.
Wenn p, dann q und umgekehrt.
p dann und nur dann, wenn q.
Aus p folgt q und umgekehrt.
p impliziert q und umgekehrt.
p und q implizieren sich gegenseitig.
p ist notwendig und hinreichend für q.
p ist äquivalent zu q.
p ist gleichbedeutend/gleichwertig zu q.
p ist genauso wahr oder falsch wie q.
Beispiel:p : Tobias ist mein
Sohn.
q : Tobias ist der Bruder meiner Tochter Mareike.
Koimplikation: p ⇔ q
Bemerkung:Hier kann
überall p mit qvertauscht
werden.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.24
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Negation von Aussagen
Negation mit Quantoren
¬ ( ∀x∈G p(x) ) ⇔ ∃x∈G ¬ p(x)
¬ ( ∃x∈G p(x) ) ⇔ ∀x∈G ¬ p(x)
Negationen
¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q
¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q
¬ (¬ p) ⇔ p
Wahrheitstafel
p q ¬ p ¬ q p ∧ q ¬ (p ∧ q) p ∨ q ¬ (p ∨ q) ¬ p ∧ ¬ q ¬ p ∨ ¬ q
w w f f w f w f f f
w f f w f w w f f w
f w w f f w w f f w
f f w w f w f w w w
Tertium non datur.Entweder ist p wahr, oder
¬ p ist wahr, eine dritte Möglichkeit gibt es nicht.
p q ¬ p ¬ q p ∧ q ¬ (p ∧ q) p ∨ q ¬ (p ∨ q) ¬ p ∧ ¬ q ¬ p ∨ ¬ q
w w f f w f w f
w f f w f w w f
f w w f f w w f
f f w w f w f w
Alle Grundschullehrkräfte sind Frauen.
Es gibt eine Katze die bellen kann.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.25
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
p q ¬ p ¬ q p ⇒ q ¬ p ∨ q ¬ q ⇒ ¬ p ¬ (p ⇒ q) p ∧ ¬ q
w w f f w w w f f
w f f w f f f w w
f w w f w w w f f
f f w w w w w f f
p q ¬ p ¬ q p ⇒ q ¬ p ∨ q ¬ q ⇒ ¬ p ¬ (p ⇒ q) p ∧ ¬ q
w w f f w w
w f f w f f
f w w f w w
f f w w w w
Einige äquivalente Aussagen
Implikation
(p ⇒ q) ⇔ (¬ p ∨ q)
(p ⇒ q) ⇔ (¬ q ⇒ ¬ p)
Negation
¬ (p ⇒ q) ⇔ (p ∧ ¬ q)
Wahrheitstafel
Beispiele:Wenn Herr Roth kommt, dann ist er pünktlich.
Wenn der Tank leckt, be-kommen Sie einen neuen.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.26
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
p q p ⇒ q q ⇒ p (p ⇒ q) ∧ (q ⇒ p) p ⇔ q
w w w W w w
w f f W f f
f w w F f f
f f w w w w
p q p ⇒ q q ⇒ p (p ⇒ q) ∧ (q ⇒ p) p ⇔ q
w w w w
w f f w
f w w f
f f w w
Es gilt:
(p ⇔ q) ⇔ [(p ⇒ q)∧(q ⇒ p)]
Wahrheitstafel
q ⇒ p ist die Umkehrung von p ⇒ q
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.27
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Kontraposition contra Umkehrung
Eine Implikation p ⇒ q hat immer denselben Wahrheitsgehalt wie ihre Kontraposition ¬ q ⇒ ¬ p . (p ⇒ q) ⇔ (¬ q ⇒ ¬ p)
Achtung: Eine Implikation p ⇒ q und ihre Umkehrung q ⇒ pkönnen unterschiedlichen Wahrheitsgehalt haben.
Beispiel:
p(n): „n ist durch 10 teilbar“
q(n): „n ist durch 5 teilbar“
p(n) ⇒ q(n): „Ist n durch 10 teilbar, dannist n auch durch 5 teilbar“
¬q(n) ⇒ ¬p(n): „Ist n nicht durch 5 teilbar, dannist n auch nicht durch 10 teilbar“
q(n) ⇒ p(n): „Ist n durch 5 teilbar, dannist n auch durch 10 teilbar“ Gegenbeispiel 25
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.28
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
M = N
M ist gleich N.
M und N enthalten dieselben Elemente.
M ⊆ N Teilmenge
M ist Teilmenge von N (oder gleich N).
M enthält nur Elemente von N.
Mögliche Extremfälle:
M = ∅M = N
M ⊂ N echte Teilmenge
M ist echte Teilmenge von N.
M enthält nur Elemente von N, aber nicht alle.
M = N ⇔∀x∈M x∈N ∧ ∀x∈N x∈M
Mengen vergleichen
1
23 4
5 67
8
9 10N
M
M ⊆ N ⇔∀x∈M x∈N
M ⊂ N ⇔∀x∈M x∈N ∧ ∃x∈N x∉M
Venn-Diagramm
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.29
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
M ∪ N Vereinigungsmenge
M vereinigt mit N.
M ∪ N enthält alle Elemente aus M und alle Elemente aus N.
Beispiel: M = {2, 3, 5, 7}; N = {2, 4, 6, 8}
M ∪ N = {2, 3, 4, 5, 6, 7, 8}
M ∩ N Schnittmenge
M geschnitten mit N.
M ∩ N enthält alle Elemente, die sowohl in M als auch in N enthalten sind.
Beispiel: M = {2, 3, 5, 7}; N = {2, 4, 6, 8}
M ∩ N = {2}
M ∪ N
Mengen verknüpfen
23 4
5 67
8
MN
M ∩ N
23 4
5 67
8
MN
M ∪ N = {x∈G | x∈M ∨ x∈N}
M ∩ N = {x∈G | x∈M ∧ x∈N}
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.30
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
M
M\N Restmenge
M ohne N.
M\N enthält alle Elemente aus M, die nicht Element von N sind.
Beispiel: M = {2, 3, 5, 7}; N = {2, 4, 6, 8}
M\N = {3, 5, 7}
M Komplement von M bzgl. G
M ist das Komplement von M bzgl. der Grundmenge G.
M enthält die Elemente der Grund-menge G, die nicht in M enthalten sind.
M = G\M, wenn M ⊆ G.
Beispiel: G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; M = {2, 3, 5, 7} ⇒ M = {1, 4, 6, 8, 9, 10}
M \ N
Mengen verknüpfen
23 4
5 67
8
MN
1
23 45 67
8
9 10
G
M
M\N = {x∈M | x∉N}
M = {x∈G | x∉M}
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.31
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Mengen verknüpfen
Kartesisches Produkt
Sind M1 und M2 zwei nichtleere Mengen (M1, M2 ≠ ∅), dann ist das kartesische Produkt M1 × M2 die Menge aller geordnetenPaare (m1, m2) mit m1 ∈ M1 und m2 ∈ M2.
M1 × M2 = {(m1, m2) | m1 ∈ M1 ∧ m2 ∈ M2}
Sind M1, M2, … , Mn nichtleere Mengen, dann ist das kartesische Produkt M1 × M2 × … × Mn dieser Mengen definiert durch
M1 × M2 × … × Mn = {(m1, m2, … , mn) | ∀k∈{1, 2, … , n} mk ∈ Mk}.
Beispiel:
M1 = {1, 2, 3}, M2 = {a, b}⇒ M1 × M2 = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
Achtung: (a, 1) ∉ M1 × M2
Die Bezeichnung „kartesisch“ geht aufden Mathematiker und Philosophen René Descartes (1596-1650) zurück. Er hat z. B. die Punkte der Ebene durch Paare von Zahlen dargestellt.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.32
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Präsenzübung
Geben Sie folgende Mengen an:
G ∪ M
P ∩ G
G \ N
G \ P
N (bzgl. G als Grundmenge)
G \ (M ∪ N)
P \ G
G ∩ N
M × N
G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
M = {x ∈ G | x ist Primzahl.}
N = {x ∈ G | ∃n∈N x = 2n ∧ x ≠10}
P = {x ∈ Z | |x| = 1}
1
23 4
5 67
8
–1 9 10
G
M
NP
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.33
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Mächtigkeit von Mengen
|M| Mächtigkeit der Menge M
|M| beschreibt die Anzahl der Elemente von M.
Beispiel: M = {0, 1, 2, 3, 4, 5}; N = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
|M| = 6
|N| = 9
Mächtigkeit von Mengen vergleichen
Wenn es gelingt, die Elemente zweier Mengen M und N paarweise einander zuzuordnen, dann sind die Mengen M und N gleichmächtig,also |M| = |N|.
Für M ⊆ N gilt |M| ≤ |N|
1
23 4
5
0M
N
7
89
6
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.34
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Mächtigkeit von Mengen
Welche Menge ist mächtiger, besitzt also mehr Elemente?
Menge der natürlichen Zahlen N
Menge der geraden natürlichen Zahlen G = {n∈N | ∃k∈N n = 2k}.
G ⊂ N,
|G| = |N|Die Menge der geraden natürlichen Zahlen und die Menge der natürlichen Zahlen sind gleichmächtig, weil man die Elemente dieser Mengen paarweise einander zuordnen kann.
Definition:
Einen Menge M heißt endlich, wenn es eine natürliche Zahl n gibt mit |M| = n.
k∈N 1 2 3 4 5 6 7 8 9 …
n = 2k ∈G 2 4 6 8 10 12 14 16 18 …
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.35
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Abzählbare Mengen
Definition:
Einen Menge M heißt unendlich, wenn sie eine echte Teilmenge T besitzt (T ⊂ M), zu der sie gleichmächtig ist, für die also gilt |T| = |M|.
Eine Menge M die gleichmächtig zur Menge der natürlichen Zahlen N ist, für die also gilt |M| = |N|, heißt abzählbar (unendlich).
Welche Menge ist mächtiger, besitzt also mehr Elemente?
Menge der ganzen Zahlen Z
Menge der natürlichen Zahlen N ⊂ Z
|Z| = |N|, die Menge der ganzen Zahlen ist also abzählbar.
k∈N 1 2 3 4 5 6 7 8 9 …
z∈Z 0 1 –1 2 –2 3 –3 4 –4 …
Man schreibtauch |M| = ∞.
|N| = ℵo
ℵo: „Aleph Null“
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.36
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Abzählbare Mengen
Welche Menge ist mächtiger, besitzt also mehr Elemente?
Menge der rationalen Zahlen Q
Menge der natürlichen Zahlen N ⊂ Q
Diagonalverfahren von Cantor
Die Pfeile deuten an, wie die Nummerierung erfolgen soll.
Schon erfasste Zahlenwerden übersprungen.
|Q| = |N|, die Menge der rationalen Zahlen ist also abzählbar.
n∈N 1 2 3 4 5 6 7 8 9 …
q∈Q 0 1 –1 2 –2 1/2 –1/2 1/3 –1/3 …
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.37
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Nicht abzählbare Mengen
Potenzmenge ℘(N) von N
Die Menge ℘(N) aller Teilmengen der natürlichen Zahlen ist nicht abzählbar unendlich.Man sagt auch ℘(N) ist überabzählbar.
Beweis folgt später.
Es gibt also verschiedene Stufen von unendlich! (ℵ0, ℵ1, …)
℘({1}) = {∅, {1}} |℘({1})| = 2 = 21
℘({1, 2}) = {∅, {1}, {2}, {1, 2}} |℘({1, 2})| = 4 = 22
℘({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}|℘({1, 2, 3})| = 8 = 23
℘(N) |℘(N)| = 2ℵ0
Menge der reellen Zahlen R
R ist überabzählbar!
ℵ: „Aleph“|N| = ℵo
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.38
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Mächtigkeit abgeleiteter Mengen
Mächtigkeit des Komplements
Ist G eine endliche Menge und M eine Teilmenge von G, dann gilt: |M| = |G\M| = |G| – |M|
Summenformel
Sind M1 und M2 zwei endliche Mengen, dann gilt:|M1 ∪ M2| = |M1| + |M2| – |M1 ∩ M2|
Produktformel
Sind M1 und M2 zwei nichtleere endliche Mengen, dann gilt:|M1 × M2| = |M1| ⋅ |M2|
Sind M1, M2, … , Mn nichtleere endliche Mengen, dann gilt:|M1 × M2 × … × Mn | = |M1| ⋅ |M2| ⋅ … ⋅ |Mn|
M
1
23 45 67
8
9 10
G
M
M ∪ N
23 4
5 67
8
MN
Dr. Jürgen Roth
1.39
Dr. Jürgen RothFachbereich 6: AbteilungDidaktik der Mathematik
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
1 Pro-gramm& Grund-lagen
1.3 Beweistechniken
1 Programm und Argumentationsgrundlagen
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.40
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beweistechniken für p ⇒ q
Direkter Beweis
Man geht von der Voraussetzung p aus und argumentiert durch eine Kette logischer Schlüsse so lange, bis man bei der Behauptung q ankommt.
Indirekter Beweis
Man nimmt ¬ q an und schließt dann auf ¬ p, man zeigt also in Wirklichkeit die Kontraposition ¬ q ⇒ ¬ p.
Widerspruchsbeweis
Hier führt man die Negation der zu beweisenden Aussagep ⇒ q, also die Aussage p ∧ ¬ q, zum Widerspruch. Man
nimmt also sowohl p als auch ¬ q an und schließt dann solange weiter, bis man auf einen Widerspruch stößt.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.41
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Direkter Beweis
Behauptung 1:
Für natürliche Zahlen n gilt: Ist n ungerade, dann ist auch n2 ungerade.
p(n) ist die Aussage „n ist ungerade“ und q(n) ist die Aussage „n2 ist ungerade“. Zu zeigen ist p(n) ⇒ q(n).
Beweis (direkt):
n ungerade ⇔ ∃k∈N0n = 2k + 1
⇒ n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) +1
⇒ n2 ungerade
Damit ist die Implikation p(n) ⇒ q(n), also die Behauptung bewiesen. #
∈ N0
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.42
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Indirekter Beweis
Behauptung 2 (Umkehrung der Behauptung 1):
Für natürliche Zahlen n gilt: Ist n2 ungerade, dann ist auch n ungerade.
p(n) ist die Aussage „n ist ungerade“ und q(n) ist die Aussage „n2 ist ungerade“. Zu zeigen ist q(n) ⇒ p(n).
Beweis (indirekt):
Aus der Annahme ¬ p(n) ist ¬ q(n) zu folgern. Wir zeigen also die zur Behauptung 2 äquivalente Behauptung ¬ p(n) ⇒ ¬ q(n). Dies bedeutet: Ist n gerade, dann ist auch n2 gerade.
n gerade ⇔ ∃k∈N n = 2k
⇒ n2 = (2k)2 = 4k2 = 2(2k2)
⇒ n2 gerade
Damit ist ¬ p(n) ⇒ ¬ q(n), also auch Behauptung 2 bewiesen. #
∈ N
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.43
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Widerspruchsbeweis
Behauptung 2 (Umkehrung der Behauptung 1):
Für natürliche Zahlen n gilt: Ist n2 ungerade, dann ist auch n ungerade.
p(n) ist die Aussage „n ist ungerade“ und q(n) ist die Aussage „n2 ist ungerade“. Zu zeigen ist q(n) ⇒ p(n).
Widerspruchsbeweis:
Die Negation ¬ (q(n) ⇒ p(n)) der zu beweisenden Aussage, also q(n) ∧ ¬ p(n), das ist die Aussage „n2 ist ungerade und n ist gerade.“ wird zum Widerspruch geführt.
n2 ungerade und n gerade ⇔ ¬(∃i∈N n2 = 2i ) ∧ (∃k∈N n = 2k )
⇒ (∀i∈N n2 ≠ 2i ) ∧ (∃k∈N n2 = (2k)2)
⇒ (∀i∈N n2 ≠ 2i ) ∧ (∃k∈N n2 = 2(2k2))
Widerspruch!
Damit ist (*) falsch und folglich die Behauptung 2 richtig. #
∈ N
(*)
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.44
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Widerspruchsbeweis
Satz:
Die Menge ℘(N) aller Teilmengen von N ist nicht abzählbar.
Beweis (Widerspruchsbeweis):
Annahme: ℘(N) ist abzählbar.
⇒ Man kann die Teilmengen von N durchnummerieren M1, M2, M3, M4, M5, … und damit ℘(N) darstellen als
℘(N) = {M1, M2, M3, M4, M5, …}.
Wir betrachten die Teilmenge M von ℘(N), für die gilt:
M = {n∈N | n∉Mn}
Diese Menge besteht also aus den natürlichen Zahlen, die nicht in der Teilmenge vorkommen, dessen Nummer sie sind.
⇒ ∀n∈N M ≠ Mn
Widerspruch zur Annahme ℘(N) = {M1, M2, M3 , M4, M5, …}
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.45
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Existenz irrationaler Zahlen
Definition:
Eine reelle Zahl x heißt
rational, wenn sie sich in der Form x = mit m ∈ Zund n ∈ N schreiben lässt,
andernfalls irrational.
Satz:
Es gibt keine rationale Zahl x mit x2 = 2.
Beweis (Widerspruchsbeweis):
„Wenn x2 = 2 ist, dann gilt für alle Lösungen x dieser Gleichung x ∉ Q.“
Annahme: p(x) ∧ ¬q(x)
⇒ Es gibt o. B. d. A. einen Bruch mit m, n ∈ Nfür den gilt:
⇒ m2 = 2n2
⇒ m⋅m = 2⋅n⋅n
In der Primfaktorzerlegung von m⋅m tritt die Zahl 2 in einer geraden Anzahl auf, in der von 2⋅n⋅n tritt die Zahl 2 dagegen in einer ungeraden Anzahl auf .
Widerspruch zur Eindeutigkeitder Primfaktorzerlegung!
Dieser Widerspruch zeigt, dass es keine rationale Zahl x mit x2 = 2 geben kann. #
nm
nm
22
=⎟⎠⎞
⎜⎝⎛
nm
o. B. d. A. heißt „ohne Beschränkung der Allgemeinheit“.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.46
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Existenz irrationaler Zahlen
0 1 22
2
Die reellen Zahlen entsprechen eineindeutig den sämtlichen Punkten der Zahlengeraden.Arnold Kirsch
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.47
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beweismethode: Vollständige Induktion
Idee: Man möchte zeigen, dass eine Aussageform p(n) für alle natürlichen Zahlen zu einer wahren Aussage wird: ∀n∈N p(n)
Beispiel: Dreieckszahlen
Satz:
Für alle natürlichen Zahlen n gilt: 1 + 2 + … + n =( )2
1+⋅ nn
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.48
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Schema der vollständigen Induktion
Induktionsanfang: p(1)
Induktionsschritt:∀n∈N p(n) ⇒ p(n + 1)
Induktionsschluss:∀n∈N p(n)
1
2 3 4 5 61 …
n n + 1
⇒
⇒ ⇒ ⇒ ⇒ ⇒ ⇒
∀n∈N p(n)
Zu zeigen: p(n) ist für alle natürlichen Zahlen n wahr.Vorgehensweise:• Beweisen: p(1) ist wahr.• Beweisen: Wenn p(n) für
ein n ∈ N wahr ist, dann ist es auch für n + 1 wahr.
Man geht hier von der Induktionsannahme „p(n) ist wahr“ aus.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.49
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel
Satz:
Für alle natürlichen Zahlen n gilt: 1 + 2 + … + n =
Beweis (vollständige Induktion):
Induktionsanfang p(1):
Induktionsschritt p(n) ⇒ p(n + 1):
1 + 2 + … + n + (n + 1)
Induktionsschluss:
( )2
1+⋅ nn
( )2
1111
+⋅=
( ) ( )[ ]2
111 ++⋅+=
nn
( ) ( )12
1++
+⋅=
−
nnnannahme
Induktions
( ) ( )2
122
1 +⋅+
+⋅=
nnn
( ) ( )2
121 +⋅++⋅=
nnn ( ) ( )2
21 +⋅+=
nn
( )2
1...21
+⋅=+++∀ ∈
nnnn N
#
∑=
+++=n
k
nk1
...21
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.50
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel
Bernoulli‘sche Ungleichung:
Wenn h eine fest gewählte reelle Zahl mit h > 1 ist, dann folgende Ungleichung für alle natürliche Zahlen n richtig:
(1 + h)n ≥ 1 + n ⋅ h
Beweis (vollständige Induktion):
Induktionsanfang p(1): (1 + h)1 ≥ 1 + 1 ⋅ h
Induktionsschritt p(n) ⇒ p(n + 1):
(1 + h)n+1 = (1 + h)n ⋅ (1 + h)
≥ (1 + n ⋅ h) ⋅ (1 + h)
= 1 + h + n ⋅ h + n ⋅ h2
≥ 1 + h + n ⋅ h
= 1 + (n + 1) ⋅ h
Induktionsschluss: ∀n∈N (1 + h)n ≥ 1 + n ⋅ h #
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.51
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Vollständige Induktion
Bemerkung:
Nicht immer liefert ein Induktionsbeweis eine Aussage über alle natürlichen Zahlen.
Manchmal nur über alle natürlichen Zahlen ab einer gewissen Zahl m.
Diese Zahl m übernimmt dann anstelle der 1 die Rolle des Induktionsanfangs.
Induktionsanfang: p(m)
Induktionsschritt: ∀n ∈ {n∈N | n ≥ m} p(n) ⇒ p(n + 1)
Induktionsschluss: ∀n ∈ {n∈N | n ≥ m} p(n)
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.52
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Exkurs: Natürliche Zahlen
Grundlage: Was sind natürliche Zahlen?
Mathematiker gehen bei derartigen Fragen axiomatisch vor. Ein Objekt wird dadurch definiert, dass man angibt, welche Eigenschaften es besitzen soll.
Charakteristische Eigenschaften der Menge N
Es gibt eine kleinste Zahl in N, genannt „Eins“.
Mit n gehört immer auch n + 1 zu N.
Mit n gehört auch n – 1 zu N, wenn n ≠ 1 ist.
Ist m ≠ n, dann ist auch m + 1 ≠ n + 1.
Es gilt das Prinzip der vollständigen Induktion in N.
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.53
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Exkurs: Natürliche Zahlen
Peano-AxiomeEs seien eine Menge N, ein Objekt 1 und eine auf N definierte Abbildung ν gegeben, für die gilt:
(P1) 1 ∈ N.
(P2) Ist n ∈ N, dann ist auch ν (n) ∈ N.
(P3) Ist n ∈ N, dann ist ν (n) ≠ 1.
(P4) Sind n, m ∈ N und ist n ≠ m, dann ist auch ν (n) ≠ ν (m).
(P5) Ist N ⊆ N, 1 ∈ N und folgt aus n ∈ N stets ν (n) ∈ N, dann ist N = N.
Man bezeichnet die Elemente von N als natürliche Zahlen und nennt ν (n) den Nachfolger der natürlichen Zahl n.
Giuseppe Peano (* 27. 08.1858; † 20.04.1932) italienischer Mathematiker
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.54
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Jemand setzt ein Paar Kaninchen in einen Garten, der auf allen Seiten von einer Mauer umgeben ist, um herauszufinden, wie viele Kaninchen innerhalb eines Jahres geboren werden. Wenn angenommen wird, dass jeden Monat jedes Paar ein weiteres Paar erzeugt, und dass Kaninchen zwei Monate nach ihrer Geburt geschlechtsreif sind, wie viele Paare Kaninchen werden dann jedes Jahr geboren?
Aus dem Rechenbuch „Liber Abacci“ (Buch vom Abakus) des italienischen Mathematikers Leonardo von Pisa, besser
bekannt unter dem Namen Fibonacci (filius Bonacci)
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.55
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Hasen-uhr Eltern Kinder Enkel Urenkel
Fibonacci-Paare
Enzensberger: Der Zahlenteufel. Hanser, München, 1997
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.56
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Fibonacci-Folge:
Rekursive Definition der Fibonacci-Folge:
F(1) = 1 ∧ F(2) = 1 ∧ F(n+2) = F(n+1) + F(n)
Behauptung (Formel von Binet):
Das n-te Glied der Fibonacci-Folge gilt:
Präsenzaufgabe:
Beweisen Sie jeweils in Dreiergruppen die Formel von Binetmit Hilfe der vollständigen Induktion.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …
F(n) 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.57
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Formel von Binet:
Beweis (vollständige Induktion):
Induktionsanfang F(1) ∧ F(2):
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅==
11
251
251
5
11)1(F
⎥⎦
⎤⎢⎣
⎡ −−
+⋅=
251
251
5
1
⎥⎦
⎤⎢⎣
⎡⋅=
252
5
1
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.58
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Formel von Binet:
Beweis (vollständige Induktion):
Induktionsanfang F(1) ∧ F(2):
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
1)1( =F
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅==
22
251
251
5
11)2(F
( ) ( )⎥⎦⎤
⎢⎣⎡ −⋅−+⋅⋅= 53
21
5321
5
1
⎥⎦⎤
⎢⎣⎡ +⋅= 5
21
521
5
15
5
1⋅= ( )53
21
521
46
45
521
41
251
:2
+⋅=
+=
++=
⎟⎟⎠
⎞⎜⎜⎝
⎛ +
NR
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.59
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Formel von Binet:
Beweis (vollständige Induktion):
Induktionsanfang F(1) ∧ F(2): F(1) = 1 ∧ F(2) = 1
Induktionsschritt F(n) ∧ F(n+1) ⇒ F(n+2):
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
)()1()2( nFnFnF ++=+
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅+
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
++ nnnn
251
251
5
12
512
51
5
111
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛+
−⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛+
+⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅= 1
251
251
12
512
51
5
1nn
( ) ( )⎥⎥⎦
⎤
⎢⎢⎣
⎡−⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ −−+⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅= 53
21
251
5321
251
5
1nn
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.60
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Formel von Binet:
Beweis (vollständige Induktion):
Induktionsanfang F(1) ∧ F(2): F(1) = 1 ∧ F(2) = 1
Induktionsschritt F(n) ∧ F(n+1) ⇒ F(n+2):
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
)()1()2( nFnFnF ++=+
( ) ( )⎥⎥⎦
⎤
⎢⎢⎣
⎡−⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ −−+⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅= 53
21
251
5321
251
5
1nn
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
22
251
251
251
251
5
1nn
NR
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
++ 22
251
251
5
1nn
1 Pro-gramm& Grund-lagen
3 Lineare Fkt./Glei-chungen
2 Funktio-nen (Fkt.)
Dr. Jürgen Roth
1.61
4 Quadrat. Fkt./Glei-chungen
5 Exponen-tialfkt.
Beispiel: Fibonacci-Zahlen
Formel von Binet:
Beweis (vollständige Induktion):
Induktionsanfang F(1) ∧ F(2): F(1) = 1 ∧ F(2) = 1
Induktionsschritt F(n) ∧ F(n+1) ⇒ F(n+2)
Induktionsschluss:
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=
nn
nF2
512
51
5
1)(
⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟
⎠
⎞⎜⎜⎝
⎛ +⋅=∀ ∈
nn
n nF2
512
51
5
1)(N
#