BuK-Übung01
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.
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} - 1Wenn \sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1,
dann gilt auch: \sum\limits_{k=1}^{n+1} F_{k} = F_{n+3} - 1
Für n=1:
\sum\limits_{k=1}^{1} F_{k} = F_{3} - 1 F_{1} = 2 - 1 = 1 \Rightarrow OKIS:
\sum\limits_{k=1}^{n+1} F_{k} = \sum\limits_{k=1}^{n} F_{k} + F_{n+1} F_{n+2} -1 + F_{n+1}= F_{n+3} - 1 // Laut Definition
Aufgabe 2
\sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1Wenn \sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1,
dann gilt auch: \sum\limits_{k=1}^{n+1} F_{2k} = F_{2(n+1)+1} - 1 = F_{2n+3} -1
Für n = 1:
\sum\limits_{k=1}^{1} F_{2k} = F_{3} - 1 1 = 2 - 1 \Rightarrow OKIS:
\sum\limits_{k=1}^{n+1} F_{2k} = \sum\limits_{k=1}^{n} F_{2k} + F_{2(n+1)} = F_{2n+1} - 1 + F_{2n+2} = F_{2n+3} - 1Aufgabe 3
\sum\limits_{k=1}^{n} F_{2k-1} = F_{2n}Wenn \sum\limits_{k=1}^{n} F_{2k-1} = F_{2n},
dann gilt auch \sum\limits_{k=1}^{n+1} F_{2k-1} = F_{2n+2}
Für n = 1:
\sum\limits_{k=1}^{1} F_{2k-1} = F_{2} 1 = 1 \Rightarrow OKIS:
\sum\limits_{k=1}^{n+1} F_{2k-1} = \sum\limits_{k=1}^{n} F_{2k-1} + F_{2(n+1)-1} \Rightarrow F_{2n} + F_{2n+1} \Rightarrow F_{2n+2}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 Definitionsbeispiele 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.
Beispiele:
Kosten für Infopost
q(x)=\begin{cases} (x-20) * 0.352 + 28, & \text{wenn }0 < x \leq 20\text{;}\\ (x-20) * 0.352 + 36, & \text{wenn }20 < x \leq 100\text{;}\\ (x-20) * 0.352 + 73, & \text{wenn }100 < x \leq 1000\text{;}\\ \bot, & \text{sonst.} \end{cases}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.
Erklärung
| Eigenschaft | Beschreibung | Beispiele |
|---|---|---|
| |surjektiv | Jedes Element aus B hat mindestens einen Partner in A | \R \Rightarrow \R_{+}, x \rightarrow x^2 |
| |nicht surjektiv | \R \Rightarrow \R, x \rightarrow x^2 , da z.B. -1 keinen zugehörigen x Wert besitzt | |
| |injektiv | Jedes Element aus B hat höchstens einen Partner in A | \N \Rightarrow \N, x \rightarrow x^2 |
| |nicht injektiv | \Z \Rightarrow \Z, x \rightarrow x^2 , da -1 und 1 das selbe Ergebnis besitzen. | |
| |bijektiv | Jedes Element aus B hat genau einen Partner in A (muss injektiv und surjektiv sein) | \R_{+} \Rightarrow \R_{+}, x \rightarrow x^2 |
| |nicht bijektiv | \R \Rightarrow \R_{+}, x \rightarrow x^2 | |
Bildliche Darstellung
| Funktion X \Rightarrow Y | Darstellung |
|---|---|
| |injektiv,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.
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.
Potenzmenge, ist die Menge aller Teilmengen. P(X) = \{U | U \subset X\} Sie besitzt 2^n Elemente.
- Leere Menge aufnehmen
- Nimm ein Element aus der Menge und füge es jedem Element der vorher gebildeten Menge Hinzu und übernimm die vorher gebildetetn Elemente
Beispiel
\wp(\{a,b,c\})=\{\{\emptyset\},
\wp(\{a,b,c\})=\{\{\emptyset\},\{c\},
\wp(\{a,b,c\})=\{\{\emptyset\},\{c\},\{b\},\{bc\},
\wp(\{a,b,c\})=\{\{\emptyset\},\{c\},\{b\},\{bc\},\{a\},\{ab\},\{ac\},\{abc\}\}