Übungsblatt 1 - Universität Zürich

Universität Zürich, 12. September 2016
Vorkurs Grundlagen für das Mathematikstudium
Übungsblatt 1: Logik und Mengenlehre
Aufgabe 1.
(a) Johannas Katze niest immer bevor es regnet. Heute hat sie geniest. Also wird es regnen,
denkt Johanna. Hat sie recht?
(b) Peter hat gesagt: Vorgestern war ich 10, aber im nächsten Jahr werde ich 13.
Ist das
möglich?
Aufgabe 2. Wir bezeichnen mit Aussagen solche Sätze, von welchen wir sinnvoll (und ein-
deutig!) sagen können, dass sie entweder wahr oder falsch sind. Sind
die Negation von
B,
falls
A
genau dann wahr ist, wenn
B
A, B
Aussagen, so ist
A
falsch ist.
(a) Welche der folgenden Sätze sind Aussagen:
(i) Die Zahl
2
ist ungerade.
(ii) Löse diese Aufgabe!
(iii) Dieser Satz ist falsch.
(iv) Ich sage nie die Wahrheit.
(b) Verneine die folgenden Aussagen (Negation):
(i) Alle Frauen sind schön.
(ii) Der Boden ist vom Regen nass oder jemand hat ihn mit dem Wasserschlauch vollgespritzt.
(iii) Jede Frau und jeder Mann hat schon mindestens einmal im Leben nicht alles vom
Teller aufgegessen.
Aufgabe 3. Seien
X, Y
Mengen und
E
eine "`Eigenschaft"', die von
x∈X
und
y∈Y
Suche Beispiele, die veranschaulichen, dass (a) und (b) nicht dasselbe ausdrücken.
(a)
∀x ∈ X ∃y ∈ Y : E(x, y)
(b)
∃y ∈ Y ∀x ∈ X : E(x, y)
Aufgabe 4. Beweise folgende Identität durch vollständige Induktion:
n
X
k=0
k2 =
n(n + 1)(2n + 1)
, n ∈ N.
6
abhängt.
Aufgabe 5. Dem bekannten französischen Forscher E.R. Reur ist es endlich gelungen, die erste
These der Julirevolution (Alle Menschen sind gleich) wissenschaftlich zu beweisen. Ist nämlich
M
eine Menge mit endlich vielen Elementen, so gilt
a=b
für
a, b ∈ M .
Beweis durch Induktion:
(i) Induktionsanfang: Hat
M
genau ein Element,
M = {a},
so ist die Aussage richtig.
(ii) Induktionsschluss: (α): Die Aussage sei richtig für alle Mengen mit genau
n Elementen.
n + 1 Elementen. Für b ∈
N := M 0 \ {b}. Die
0
Elemente von N sind nach (α) einander gleich. Es bleibt zu zeigen: b = c, wenn c ∈ M .
0
0
Dazu entfernt man ein anderes Element d aus M und weiss dann: b ∈ M \ {d}. Die
Elemente dieser Menge sind nach (α) wiederum einander gleich. Wegen der Transitivität
der Gleichheitsbeziehung folgt dann die Behauptung. (Transitivität: a = b und b = c
implizieren a = c; siehe Äquivalenzrelation am Mittwoch.)
0
(β ): Es sei M eine Menge mit genau
M 0 sei
Was ist falsch an diesem Schluss?
Aufgabe 6. Beweise, dass die Ebene
R2 , die durch endlich vielen Geraden geteilt wird, mit zwei
Farben so eingefärbt werden kann, dass je zwei Teile mit einer gemeinsamen Kante nie von der
gleichen Farbe sind.
Aufgabe 7. Beweise die de Morganschen Regeln für Mengen (Skript S. 9).
Aufgabe 8.
(a) Sei
ak
eine natürliche Zahl für jedes
n
Y
k ∈ N.
Man deniert
ak := a0 · a1 · · · · · an−1 · an .
k=0
Deniere
Qn
k=0 ak rekursiv.
(b) Gib eine rekursive Deniton der Potenzierung an.
(c) Die Tetration
m∗n
ist deniert wie folgt:
m ∗ 1 = m,
m ∗ 2 = mm ,
m
m ∗ 3 = mm . . . .
Gib eine rekursive Denition der Tetration an.
Aufgabe 9. Die Multiplikation ist eine Abkürzung für die mehrfache Addition, beispielsweise ist
3∗4 = 4+4+4.
Sie kann somit rekursiv aus der Addition deniert werden. Ebenso ist die Poten-
zierung eine Abkürzung für die mehrfache Multiplikation, und die Tetration eine Abkürzung für
die mehrfache Potenzierung. Die sogenannte Ackermann-Funktion
1 verallgemeinert dies Opera-
toren:
ack(a, b, 0) = a + b
ack(a, b, 1) = a · b
ack(a, b, 2) = ab
ack(a, b, 3) = a ∗ b
.
.
.
1
Sie wurde 1926 von Wilhelm Ackermann rekursiv deniert und ist von grosser Bedeutung in der theoretischen
Informatik.
Dies ist aber noch keine rekursive Denition, sondern nur eine Beschreibung ihrer Eigenschaften.
Eine vereinfachte rekursive Denition (mit nur 2 statt 3 Einträgen) einer Variante
ack2
der
Ackermann-Funktion ist folgende:
ack2(0, m) = m + 1
ack2(n + 1, 0) = ack2(n, 1)
ack2(n + 1, m + 1) = ack2(n, ack2(n + 1, m)).
Per Salami-Taktik zerlegen wir
ack2
in Scheiben , d.h. Funktionen, die nur noch einen Eintrag
haben:
an (m) = ack2(n, m).
Zeige (einige der) folgende(n) Gleichheiten per Induktion (die Beweise sind jeweils sehr ähnlich):
a1 (m) = m + 2
a2 (m) = 2m + 3
a3 (m) = 2m+3 − 3.
Überlege dir, wie
und
ack2.
a4
aussehen könnte und nde einen allgemeinen Zusammenhang zwischen
Berechne ein paar Werte von
a4 .
ack
Was stellst du fest?
Aufgabe 10. Meiers werden uns heute abend besuchen, kündigt Frau Müller an. Die ganze
Familie, also Herr und Frau Meier mit ihren drei Kindern Franziska, Kathrin und Walter? fragt
Herr Müller bestürzt. Darauf Frau Müller, die keine Gelegenheit vorübergehen lässt, ihren Mann
zu logischem Denken anzuregen: Nun, ich will es dir so erklären: Wenn Herr Meier kommt, dann
bringt er auch seine Frau mit. Mindestens eines der beiden Kinder Walter und Kathrin kommt.
Entweder kommt Frau Meier oder Franziska, aber nicht beide. Entweder kommt Franziska und
Kathrin oder beide nicht. Und wenn Walter kommt, dann auch Kathrin und Herr Meier. So,
jetzt weisst du, wer uns heute abend besuchen wird.
Wer kommt und wer kommt nicht?

Download Report