ue1

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < sijeheid

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:

ABCA \Rightarrow BB \Rightarrow C\overline{C}\overline{A}\overline{B}
| wwwwwfff
| wwfwfwff
| wfwfwffw
| wfffwwfw
| fwwwwfwf
| fwfwfwwf
| ffwwwfww
| fffwwwww

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: