BuK/IIm11/Studenten/sijeheid/ue1

Wiki-Quelltext dieser Seite.

== Ü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:'''

{| border="1" cellpadding="5" cellspacing="0"
!$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} - 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 ==

<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}
$$
Programm, das $q$ berechnet:

<code id="4f62f4177e158">
(define q
  (lambda (x) 
    (if (= x 3) 
      (q 3) 
      (/ 35 (- x 3))
     )
   )
)
</code>
<run id="4f62f4177e2c2">(q 8)</run>