ue1
Aus ProgrammingWiki
Inhaltsverzeichnis |
Übung 1
Indirekter Beweis
Aufgabe 1
Beweisen Sie indirekt, dass $x$ eine gerade Zahl ist, wenn $x^2$ mit $x\in{\mathbb N}$ eine gerade Zahl ist.
Lösung:
zu zeigen: Wenn $x^2$ gerade, dann $x$ gerade (Wenn $2 \mid x^2$, dann $2 \mid x$).
Beispiele: $2^2 = 4$ (gerade), $4^2 = 16$ (gerade), $3^2 = 9$ (ungerade)
Annahme: Wenn $2 \mid x^2$, dann $2 \nmid x$.
Beweis:
$x = ungerade = 2k+1$
$x^2 = gerade = 2z$
$\Rightarrow (2k+1)^2 = 4k^2 + 4k + 1 \Rightarrow = ungerade, da +1$
$\Rightarrow \unicode{x021AF}$ Widerspruch, da $x^2$ gleichzeitig gerade und ungerade wäre.
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.
Lösung:
| $A$ | $B$ | $C$ | $A \Rightarrow B$ | $B \Rightarrow C$ | $\overline{C}$ | $\overline{A}$ | $\overline{B}$ |
|---|---|---|---|---|---|---|---|
| w | w | w | w | w | f | f | f |
| w | w | f | w | f | w | f | f |
| w | f | w | f | w | f | f | w |
| w | f | f | f | w | w | f | w |
| f | w | w | w | w | f | w | f |
| f | w | f | w | f | w | w | f |
| f | f | w | w | w | f | w | w |
| f | f | f | w | w | w | w | w |
Nur in Zeile 8 folgen aus der Gültigkeit der Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ die Gültigkeiten von $\overline{A}$ und $\overline{B}$, also wenn $A$, $B$ und $C$ nicht gelten.
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.
Lösung:
Laut den Zeilen 1, 5 und 7 aus der obigen Tabelle folgt, dass, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten, $A$ und $B$ entweder beide gelten, beide nicht gelten oder nur $B$, aber nicht $A$ gilt.
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} - 1$$
IA:
$ 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$
Aufgabe 2
$$ \sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1$$
IA:
$ 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$
Aufgabe 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}$
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} $$ Programm, das $q$ berechnet:
