Vorlesung 1

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

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.

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.