Transcript
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 de niert
ak := a0 · a1 · · · · · an−1 · an .
k=0 De niere
Qn
k=0 ak rekursiv.
(b) Gib eine rekursive De niton der Potenzierung an. (c) Die Tetration
m∗n
ist de niert wie folgt:
m ∗ 1 = m,
m ∗ 2 = mm ,
m
m ∗ 3 = mm . . . .
Gib eine rekursive De nition 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 de niert 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 de niert und ist von grosser Bedeutung in der theoretischen Informatik.
Dies ist aber noch keine rekursive De nition, sondern nur eine Beschreibung ihrer Eigenschaften. Eine vereinfachte rekursive De nition (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?
