Übung01
Aus ProgrammingWiki
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.
- Darstellung ungerader Zahlen durch $2k+1$
- Darstellung gerader Zahlen durch $2k$
Behauptung: Wenn $x² = 2k+1$ dann $x = 2n+1$
Beweis:
$(2k+1)²$ $=4k²+4k+1$
$4k²+4k$ ist def. gerade also darstellbar durch $2n$
$=2n + 1$
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.
| Zeile | $A$ | $B$ | $C$ | $A\rightarrow B$ | $B\rightarrow C$ | $\neg A$ | $\neg B$ | $\neg C$ |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
| 5 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 6 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 7 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
Die Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ treffen in Zeile 8 zu. Da in dieser Zeile auch $\overline{A}$ und $\overline{B}$ wahr sind, ist die Aussage bewiesen.
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.
$A \Rightarrow B$, $B \Rightarrow C$ und $C$ haben in den Zeilen 1, 2 und 4 Gültigkeit. Es ist dabei lediglich ausgeschlossen dass gleichzeitig gilt $\overline{A} \neg B$.
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$$
Zu beweisen ist:
$ \sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1 \Rightarrow \sum\limits_{k=1}^{n} F_{k} + F_{n+1} = F_{n+3} - 1$
- $F_{n+3} = F_{n+1} + F{n+2}$
$\sum\limits_{k=1}^{n} F_{k} + F_{n+1} = F_{n+3} - 1$
$\Rightarrow \sum\limits_{k=1}^{n} F_{k} + F_{n+1} = F_{n+1} + F{n+2} - 1$
$\Rightarrow \sum\limits_{k=1}^{n} F_{k} = F{n+2} - 1$
Aufgabe 2
$$ \sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1$$
Aufgabe 3
$$ \sum\limits_{k=1}^{n} F_{2k-1} = F_{2n}$$
zu beweisen:
$ \sum\limits_{k=1}^{n} F_{2k-1} = F_{2k} \Rightarrow \sum\limits_{k=1}^{n} F_{2k-1} + F_{2k+1} = F_{2k+2} $
- $F_{2k+2} = F_{2k} + F_{2k+1}$
$\sum\limits_{k=1}^{n} F_{2k-1} + F_{2k+1} = F_{2k+2} $
$\Rightarrow \sum\limits_{k=1}^{n} F_{2k-1} + F_{2k+1} = F_{2k} + F_{2k+1}$
$\Rightarrow \sum\limits_{k=1}^{n} F_{2k-1} = F_{2k}$
Relation
Wiederholen Sie die Eigenschaften von Äquivalenzrelationen und geben Sie ein Beispiel an.
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$.
Definition von Abzählbarkeit:
In der Mengenlehre wird eine Menge als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen. Dies bedeutet, dass es eine Bijektion zwischen und der Menge der natürlichen Zahlen gibt, die Menge also „durchnummeriert“ werden kann.
$\Z$ = {... -5, -4, -3, -2, 0, 1, 2, 3, 4, 5, ...}
Die Menge dieser Zahlen kann nun bei 0 gespiegelt werden, wobei die negative Zahl beispielsweise jeweils vor ihrem Betrag eingeordnet wird. Die Menge der Zahlen wird dabei nicht verändert.
$\Z$ = {0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, ...}
Da die umsortierte Menge nun bei 0 beginnt (ein definiertes erstes Element hat), kann jedem Element ein Index zugewiesen werden, wodurch $\Z$ auf $\N$ abgebildet wird, und damit bewiesen dass es sich um eine abzählbar unendliche Menge handelt.
Der Begriff der Abzählbarkeit definiert lediglich die Möglichkeit eine Menge von Zahlen auf die Menge der natürlichen Zahlen abzubilden, sagt jedoch nichts über den Umfang aus. Sowohl $\Z$ als auch $\N$ sind abzählbar unendliche Mengen, haben also keine definierte Anzahl von Elementen, wodurch man eine Aussage wie $\Z$ müsste doppelt soviele Elemente besitzen wie $\N$ nicht treffen kann.
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.
Aufbauschema
Binärcode, wobei jedes Bit für ein Element aus der Menge M steht.
Beispiele:
$M = {a, b, c}$
| $a$ | $b$ | $c$ | $\wp (M)$ |
|---|---|---|---|
| 0 | 0 | 0 | $\{\varnothing \}$ |
| 0 | 0 | 1 | $\{ c\}$ |
| 0 | 1 | 0 | $\{ b\}$ |
| 0 | 1 | 1 | $\{bc\}$ |
| 1 | 0 | 0 | $\{a\}$ |
| 1 | 0 | 1 | $\{ac\}$ |
| 1 | 1 | 0 | $\{ab\}$ |
| 1 | 1 | 1 | $\{abc\}$ |
$\wp (M) = \{\varnothing, c, b, bc, a, ac, ab, abc\}$
