ue1
Inhaltsverzeichnis |
Indirekte Beweis
Aufgabe 1
Beweisen Sie indirekt, dass x eine gerade Zahl ist, wenn x^2 mit x\in{\mathbb N} eine gerade Zahl ist.
z.z. Wenn 2\mid x , dann 2\mid x^2 .
Beispiel:
x = 4 \Rightarrow 2\mid 4 x^2 = 16 \Rightarrow 2\mid 16Annahme: Wenn 2\mid x^2 , dann 2\nmid x
Beweis:
x ungerade: x = 2k + 1
x^2 gerade: x = 2z
(2k+1)^2 = 2z4k^2+2k+1 = 2z \Rightarrow linke Seite ist ungerade, rechte Seite ist gerade \unicode{x021AF}
Aufgabe 2
Beweisen Sie die Aussage, wonach aus der Gültigkeit der Aussagen A \Rightarrow B, B \Rightarrow C und \overline{C} die Gültigkeiten von \overline{A} und \overline{B} folgen. Stellen Sie den Sachverhalt in einer Wahrheitstabelle dar.
| A | B | C | \overline{A} | \overline{B} | \overline{C} | A \Rightarrow B | B \Rightarrow C |
|---|---|---|---|---|---|---|---|
| | w | w | w | f | f | f | w | w |
| | w | w | f | f | f | w | w | f |
| | w | f | w | f | w | f | f | w |
| | w | f | f | f | w | w | f | w |
| | f | w | w | w | f | f | w | w |
| | f | w | f | w | f | w | w | f |
| | f | f | w | w | w | f | w | w |
| | f | f | f | w | w | w | w | w |
Die Spalten \overline{C}, A \Rightarrow B und B \Rightarrow C werden nur in Zeile 8 wahr, in denen auch \overline{A} und \overline{B} wahr sind.
Aufgabe 3
Was kann man über die Gültigkeit von A und B schließen, wenn bekannt ist, dass A \Rightarrow B, B \Rightarrow C und C gelten? Verwenden Sie die Tabelle aus der vorhergehenden Aufgabenlösung.
Es gelten entweder beide, keins oder nur B. (Zeile 1, 5 und 7)
Vollständige Induktion
Beweisen Sie die folgenden Beziehungen für Fibonacci-Zahlen nach Definition in obigem Beispiel mittels vollständiger Induktion für n \in \N und n \geq 1
Aufgabe 1
\sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1IA:
$ n = 1 \Rightarrow \sum\limits_{k=1}^{1} F_{k} = F_{3} - 1 \Rightarrow 1 = 1 $
IS:
Wenn \sum\limits_{k=1}^{i} F_{k} = F_{i+2} - 1 gilt (IV), dann gilt auch \sum\limits_{k=1}^{i+1} F_{k} = F_{i+3} - 1 (IB).
\Rightarrow \sum\limits_{k=1}^{i+1} F_{k} = \sum\limits_{k=1}^{i} F_{k} + F_{i+1} = F_{i+2} - 1 + F_{i+1} = F_{i+3} - 1 \BoxAufgabe 2
\sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1IA:
$ n = 1 \Rightarrow \sum\limits_{k=1}^{1} F_{2k} = F_{3} - 1 \Rightarrow 1 = 1 $
IS:
Wenn \sum\limits_{k=1}^{i} F_{2k} = F_{2i+1} - 1 gilt (IV), dann gilt auch \sum\limits_{k=1}^{i+1} F_{2k} = F_{2(i+1)+1} - 1 = F_{2i+3} - 1 (IB).
\Rightarrow \sum\limits_{k=1}^{i+1} F_{2k} = \sum\limits_{k=1}^{i} F_{2k} + F_{2(i+1)} = \sum\limits_{k=1}^{i} F_{2k} + F_{2i+2} = F_{2i+1} - 1 + F_{2i+2} = F_{2i+3} - 1 \BoxAufgabe 3
\sum\limits_{k=1}^{n} F_{2k-1} = F_{2n}IA:
$ n = 1 \Rightarrow \sum\limits_{k=1}^{1} F_{2k-1} = F_{2} \Rightarrow 1 = 1 $
IS:
Wenn \sum\limits_{k=1}^{i} F_{2k-1} = F_{2i} gilt (IV), dann gilt auch \sum\limits_{k=1}^{i+1} F_{2k-1} = F_{2(i+1)}= F_{2i+2} (IB).
\Rightarrow \sum\limits_{k=1}^{i+1} F_{2k-1} = \sum\limits_{k=1}^{i} F_{2k-1} + F_{2(i+1)-1} = \sum\limits_{k=1}^{i} F_{2k-1} + F_{2i+1} = F_{2i} + F_{2i+1} = F_{2i+2} \BoxRelation
Wiederholen Sie die Eigenschaften von Äquivalenzrelationen und geben Sie ein Beispiel an.
Identität
Eindeutige Zuordung eines Elements mit dem gleichen Element der Menge.
Reflexivität
Wenn in einer Relation die Teilmenge I (identische Teilmenge, siehe oben) enthalten ist, ist sie reflexiv.
Symmetrie
wenn aus R (x,y) auch R’ (y,x) gemacht werden kann
Antisymmetrie
wenn für x != y aus (x,y) € R stets (y,x) !€ R folgt. Im Gitternetz: zu jedem Punkt außerhalb der Diagonalen existiert kein Spiegelpunkt.
Beispiel:
a ist Vater von b
keine antisymm: a ist Geschwister von b
Transitivität
wenn (x,y) und (y,z) in Relation stehen, dann muss (x,z) in Relation stehen
B: Ist M die Menge aller Menschen, so ist die Relation “x kennt y” nicht transitiv
Äquivalenzrelation
Besitzt die Eigenschaften reflexiv, symmetrisch und transistiv.
Beispiel:
Die Aussagen “gleichaltrig” oder “gleichgroß” auf der Menge aller Menschen sind Äquivalenzrelationen.
Sei M die Menge der reelen Zahlen und R die Relation “<=”. R ist reflexiv (I durch = enthalten), transitiv (Ordnung 1<=2<=3) aber nicht symmetrisch
Funktionen
Übungsaufgabe partielle Funktion
Die im Folg. definierte Funktion q : \R \mapsto \R ist an der Stelle x=3 undefiniert. Hierfür verwenden wir das Symbol \bot.
q(x)=\begin{cases} \dfrac{35}{x-3}, & \text{wenn }x \neq 3\text{;}\\ \bot, & \text{sonst.} \end{cases}Schreiben Sie ein Programm, das q berechnet.
Aufgabe 2
Geben Sie sich einige Defnitionsbeispiele selbstgewählter Funktionen vor. Achten Sie darauf, dass es sich auch um (echte) partielle Funktionen handeln kann. Außerdem sollten Sie einige abschnittsweise definierte Funktionen, z.Z. Zuzahlungen für Medikamente usw., aufnehmen.
Aufgabe 3
Wiederholen Sie die folgenden Eigenschaften von Funktionen: injektiv, surjektiv und bijektiv. Geben Sie aussagekräftige Beispiele an. Skizzieren Sie folgende Funktionen mittels Abbildungspfeilen aus X in Y : injektiv und surjektiv; injektiv, nicht surjektiv; nicht injektiv, surjektiv; nicht injektiv, nicht surjektiv.
Mengen
Aufgabe 1
Zeigen Sie, dass die Menge \Z eine abzählbar unendliche Menge ist und setzen Sie sich mit der Aussage auseinander, wonach doch \Z eigentlich doppelt so viele Elemente besitzt, wie \N.
Fügt man einer unendlichen Menge neu Elemente zu, wird diese nicht größer.
Bildet man alle ganzen Zahlen auf die natürliche Zahlen ab, so könnte man jede negative ganze Zahl einer geraden natürlichen zuordnen und jede positive einer ungeraden
Platznummer: 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 ...
Element: 0 -1 1 -2 2 -3 3 -4 4 -5 5 -6 ...
Aufgabe 2 (Potenzmenge)
Entwerfen Sie ein Aufbauschema zur systematischen Erzeugung aller Elemente aus \wp(M) für eine gegebene endliche Menge M und wenden Sie es auf einige selbstgewählte Beispiele an.