BuK/IIm11/BuK-Übung01

Wiki-Quelltext dieser Seite.

== 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.

=== 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.

=== 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.

== 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$$

Wenn $ \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 OK$

IS:

$ \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

<div align="right">$\square $</div>

=== Aufgabe 2 ===

$$ \sum\limits_{k=1}^{n} F_{2k} =  F_{2n+1} - 1$$

Wenn $ \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 OK $

IS:

$ \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} - 1 $

<div align="right">$\square $</div>

=== Aufgabe 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 OK$

IS:

$ \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}$

<div align="right">$\square$</div>

== Relation ==

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

== Funktionen ==

<language>Scheme</language>
=== Ü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.



<code id="4f66e9a340b6f">
(define inf 
  (lambda () 
    (inf)))

(define q 
  (lambda (x) 
    (if (= x 3) 
      (inf) 
      (/ 35 (- x 3)))))
</code>

<run id="4f66e9a340bd7">(q 5)</run>

=== 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$.

=== 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.