Thema1

Aufgabe 01

Beweisen Sie indirekt, dass x eine gerade Zahl ist, wenn x^2 mit x \in \mathbb{N} eine gerade Zahl ist.

Wenn x^2 eine gerade Zahl ist, dann ist x ebenfalls eine gerade Zahl.

Annahme: x ist eine ungerade Zahl \rightarrow Wenn 2|x^2 dann 2|x.

Y = x^2 ist gerade; \overline{Y} = x^2 ist ungerade

Aus +1 folgt, dass x^2 nicht gerade ist, wodurch ein Widerspruch entsteht, da gilt, dass x^2 gerade ist.

Daraus folgt, dass x gerade ist.

Aufgabe 02 + 03

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.

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?

Wenn A \Rightarrow B, B \Rightarrow C und C gelten, dann

• gelten A und \overline{B}, oder
• gelten \overline{A} und B, oder
• gelten sowohl A, als auch B

Aufgabe 04

Beweisen Sie die von Jacques P. M. Binet (1786-1856) im Jahre 1843 F_n = \frac {1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n) für die Fibonacci-Zahlenfolge:

F_n = F_{n-1} + F_{n-2}, mit n \geq 2

mit vollständiger Induktion.

Induktionsanfang:

i = 0

und

i = 1

Induktionsschritt:

Wenn F_n = \frac {1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n) (Induktionsvoraussetzung), dann F_{n+1} = \frac {1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1})

Induktionsbeweis:

Aufgabe 05

Beweisen Sie die folgenden Beziehungen für Fibonacci-Zahlen mit n \in \mathbb{N} und n \geq 1 nach Definition im Beispiel mittels vollständiger Induktion:

1. \sum_{k=1}^n F_k = F_{n+2} - 1
2. \sum_{k=1}^n F_{2k} = F_{2n+1} - 1
3. \sum_{k=1}^n F_{2k-1} = F_{2n}

1.)

IA: n = 1 & \sum_{k=1}^1 F_k = F_{1+2} - 1

IS: Wenn \sum_{k=1}^n F_k = F_{n+2} - 1 (IV), dann \sum_{k=1}^{n+1} F_k = F_{n+3} - 1

IB: \sum_{k=1}^{n+1} F_k = \sum_{k=1}^n F_k + F_{n+1}

= F_{n+2} - 1 + F_{n+1} (IV)

= F_{n+3} - 1 (Def.)

2.)

IA: n = 1 & \sum_{k=1}^n F_{2k} = F_{2n+1} - 1

IS: Wenn \sum_{k=1}^n F_{2k} = F_{2n+1} - 1 (IV), dann \sum_{k=1}^{n+1} F_{2k} = F_{2n+3} - 1

IB: \sum_{k=1}^{n+1} F_{2k} = \sum_{k=1}^n F_{2k} + F_{2(n+1)} = F_{2n+1} - 1 + F_{2n+2} (IV)

= F_{2n+3} - 1 (Def.)

3.)

IA: n = 1 & \sum_{k=1}^1 F_{2-1} = F_{2}

IS: Wenn \sum_{k=1}^n F_{2k-1} = F_{2n} (IV), dann \sum_{k=1}^{n+1} F_{2k-1} = F_{2n+2}

IB: \sum_{k=1}^{n+1} F_{2k-1} = \sum_{k=1}^n F_{2k-1} + F_{2n+1}

= F_{2n} + F_{2n+1} (IV)

= F_{2n+2} (Def.)

Aufgabe 06

Wiederholen Sie die Eigenschaften von Äquivalenzrelationen und gebe Sie ein Beispiel an.

Eine '''Äquivalenzrelation ist eine Relation, die reflexiv, transitiv und symmetrisch ist.

• reflexiv = jedes Objekt ist zu sich selbst äquivalent
• transitiv = Wenn a zu b äquivalent ist, dann ist auch b zu a äquivalent
• symmetrisch = Wenn a zu b und b zu c äquivalent ist, dann ist auch a äquivalent zu c

Beispiel: Bücher und ihre ISB-Nummer

• für jedes Buch x gilt, dass x und x dieselbe ISBN besitzen
• Wenn x und y dieselbe ISBN haben, dann haben auch y und x dieselbe ISBN
• Wenn x und y dieselbe ISBN haben und auch y und z, dann haben x und z auch dieselbe ISBN

Eine Ordnungsrelation ist eine Relation, welche die Kleiner-Gleich-Relation (\leq) verallgemeinert. Das heißt, die Elemente einer Menge können der Größe nach geordnet und verglichen werden.

Aufgabe 07

Schreiben Sie ein Programm, das q berechnet.

$q(x) = \begin{cases} \frac{35}{x-3}, & \text{wenn } x \ne 3, \\ \perp, & \text{sonst}. \end{cases}$

Aufgabe 08

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.B. Briefporto, Zuzahlung für Medikamente, etc., aufnehmen.

$f(x) = \begin{cases} \frac{1}{x-1} + \frac{1}{x-2}, & \text{wenn } x \ne 1 \text{ und } x \ne 2,\\

\perp & \text{sonst}. \end{cases}$

Briefporto: $f(x)=\begin{cases}

               0.75, & \text{ wenn } x \leq 20\text{,}\\
               1.50, & \text{ wenn } 20 < x \leq 50\text{,}\\
               3.45, & \text{ wenn } 50 < x \leq 500\text{,}\\
               7.00, & \text{ wenn } 500 < x \leq 1000\text{,}\\
               16.90, & \text{ wenn } 1000 < x \leq 2000\text{,}\\
               \bot, & \text{ sonst} 

\end{cases}$

Aufgabe 09

Wiederholen Sie die folgenden Eigenschaften von Funktionen: injektiv, surjektiv, bijektiv. Geben Sie aussagekräftige Beispiele an. Skizzieren Sie folgende Funktionen mittels Abbildungspfeilen aus X und Y:

1. injektiv und surjektiv
2. injektiv und nicht surjektiv
3. nicht injektiv und surjektiv
4. nicht injektiv und nicht surjektiv

injektiv (linkstotal): eine Funktion ist injektiv, wenn jeder y-Wert nur maximal einen dazugehörigen x-Wert besitzt

surjektiv (rechtstotal): eine Funktion ist surjektiv, wenn jeder mögliche y-Wert in der Zielmenge angenommen wird

bijektiv (links- und rechtstotal): für jedes x aus X existiert genau ein y aus Y.

Aufgabe 10

Zeigen Sie, dass die Menge \mathbb{Z} eine abzählbar unendliche Menge ist und setzen Sie sich mit der Aussage auseinander, wonach doch \mathbb{Z} eigentlich doppelt so viele Elemente besitzt wie \mathbb{N}.

Aufgabe 11

Entwerfen Sie ein Aufbauschema zu systematischen Erzeugung aller Elemente aus \wp(M) eine gegebene endliche Menge M und wenden Sie es auf einige selbstgewählte Beispiele an.