BuK/IIm13/Studenten/simaknoc/Vorlesung 1

Wiki-Quelltext dieser Seite.

== Indirekter Beweis ==

=== Aufgabe 1 ===

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

z.z. Wenn $x^2$ gerade, dann $x$ gerade. $x \in{\mathbb N}$

Annahme: Wenn $x^2$ gerade, dann $x$ ungerade.

Beiweis

$A$ = $x^2$ ist gerade

$B$ = $x$ ist gerade

{| border="1" cellpadding="5" cellspacing="0"

!$A$
!$B$
!$\overline{A}$
!$\overline{B}$
!$A \Rightarrow B$
!$A \Rightarrow \overline{B}$
!$\neg(A \Rightarrow B)$
!Info
|-
|| W || W || F || F || W || F || F || fällt weg, weil $\overline{B}$ falsch
|-
|| W || F || F || W || F || W || W || 
|-
|| F || W || W || F || W || W || F || fällt weg, weil $A$ falsch
|-
|| F || F || W || W || W || W || F || fällt weg, weil $A$ falsch
|-
|}

In der zweiten Zeile wird der Widerspruch deutlich:

Sowohl die Annahme $A \Rightarrow \overline{B}$ ($x$ ist ungerade, wenn $x^2$ gerade ist)

als auch die Aussage $\neg(A \Rightarrow B)$ (Wenn $x^2$ nicht gerade ist, dann ist $x$ nicht gerade.) 

sind wahr. Damit wäre $x$ gleichzeitig gerade und ungerade, wenn $x^2$ eine gerade Zahl ist.

Damit ist die Annahme falsch und bewiesen, dass $x$ eine gerade Zahl ist, wenn $x^2$ eine gerade Zahl ist.

=== Aufgabe 2 und 3 ===

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 Wahrheitstafel dar.

3) Was kann man aus der Gültigkeit von $A$ und $B$ schließen, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten? 

Verwenden Sie die Tafel aus Aufgabe 2.

{| border="1" cellpadding="5" cellspacing="0"

!Zeile
!$A$
!$B$
!$C$
!$\overline{A}$
!$\overline{B}$
!$\overline{C}$
!$A \Rightarrow B$
!$B \Rightarrow C$
!2
!3
|-
|| 1 || W || W || W || F || F || F || W || W || || x
|-
|| 2 || W || W || F || F || F || W || W || F || || 
|-
|| 3 || W || F || W || F || W || F || F || W || ||
|-
|| 4 || W || F || F || F || W || W || F || W || || 
|-
|| 5 || F || W || W || W || F || F || W || W || || x
|-
|| 6 || F || W || F || W || F || W || W || F || || 
|-
|| 7 || F || F || W || W || W || F || W || W || || x
|-
|| 8 || F || F || F || W || W || W || W || W || x || 
|-
|}

'''Lösung Aufgabe 2:'''

Nur in Zeile 8 gelten sowohl $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$.

Damit geht einher, dass dort $\overline{A}$ und $\overline{B}$ gelten.

'''Lösung Aufgabe 3:'''

In den Zeilen 1,5 und 7 sind die Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gültig.

Die daraus folgenden Gültigkeiten für $A$ und $B$ sind folgende:

* $A$ und $B$ sind gültig
* $A$ gilt nicht, aber $B$ gilt
* $A$ und $B$ gelten beide nicht

Daraus folgt, dass es den Fall $A$ gilt, aber $B$ gilt nicht, nicht geben kann.

== Äquivalenzrelationen ==

Aufgabe: Wiederholen Sie die Eigenschaften von Aquivalenzrelationen und geben Sie ein Beispiel an.

Äquivalenzrelationen besitzen drei Eigenschaften: 

* Reflexivität $a \sim a$ (Jedes Objekt ist zu sich selbst äquivalent.)
* Symmetrie $a \sim b \Rightarrow b \sim a$ (Wenn $a$ äquivalent zu $b$ ist, dann ist auch $b$ äquivalent zu $a$.)
* Transitivität $a \sim b$ und $b \sim c$ $\Rightarrow$ $a \sim c$ (Wenn $a$ äquivalent zu $b$ und $b$ äquivalent zu $c$ ist, dann ist auch $a$ äquivalent zu $c$.)

=== Beispiel ===

Bücheridentifikation anhand der ISBN-Nummern

* reflexiv: Ein Buch hat genau eine ISBN, die sich nicht ändert und eindeutig ist. Daher hat ein Buch a die gleiche ISBN wie Buch a.
* symmetrisch: Wenn Buch a die gleiche ISBN wie Buch b hat, dann hat auch Buch b die gleiche ISBN wie Buch a.
* transitiv: Wenn Buch a die gleiche ISBN wie Buch b hat und Buch b die gleiche ISBN wie Buch c hat, hat auch Buch a die gleiche ISBN wie Buch c.

== Funktionen ==

=== Partielle Funktion ===

$q(x)=\begin{cases}
  \dfrac{35}{x-3},  & \text{wenn }x \neq 3\text{;}\\
  \bot, & \text{sonst.}
\end{cases}
$

Aufgabe: Schreiben Sie ein Programm, das $q$ berechnet.