Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 1

Übungsaufgaben

Aufgabe

Warum ist Mathematik schwierig, obwohl darin doch alles logisch ist?

Aufgabe

Intelligenz wird häufig als „allgemeine Problemlösekompetenz“ bezeichnet. Welche Probleme können Sie lösen, welche nicht?

Aufgabe

Lege in der Skizze für die drei Häuser überschneidungsfrei Wege zu den zugehörigen gleichfarbigen Gartentoren an.

Aufgabe *

Anfang März beträgt die Zeitdifferenz zwischen Deutschland und Paraguay ${}4$ Stunden (in Paraguay wurde es ${}4$ Stunden später hell). Am 25. März 2018 wurde in Deutschland die Uhr von der Winterzeit auf die Sommerzeit umgestellt, die Uhr wurde also um eine Stunde nachts von ${}2$ auf ${}3$ vorgestellt. In der gleichen Nacht wurde die Uhr in Paraguay umgestellt. Wie groß war die Zeitdifferenz nach der Umstellung?

Aufgabe *

In einer psychologischen Längsschnittstudie wird die Entwicklung von Einstellungen und Verhaltensweisen von Personen untersucht. Ein Fallbeispiel: Im Alter von ${}20$ Jahren geht Linda regelmäßig auf Demonstrationen, sie hilft im Eine-Welt-Laden mit, braut ökologisches Bier, kocht Bio-Gemüse und studiert manchmal Soziologie.

Welcher der folgenden Befunde ist nach 10 Jahren am unwahrscheinlichsten?

1. Linda arbeitet für eine Versicherungsagentur.
2. Linda engagiert sich bei Attac und arbeitet für eine Versicherungsagentur.
3. Linda engagiert sich bei Attac.

Aufgabe *

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit ${}V$ (vordere Tafel), ${}M$ (mittlere Tafel) und ${}H$ (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.

Aufgabe

Finde die kleinste Zahl ${}N$ der Form ${}N=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{r}+1$, die keine Primzahl ist, wobei ${}p_{1},p_{2},\ldots ,p_{r}$ die ersten ${}r$ Primzahlen sind.

Aufgabe

Es sei ${}r\in \mathbb {N}$.

a) Finde ${}r$ aufeinander folgende natürliche Zahlen (also ${}n,n+1,\ldots ,n+r-1$), die alle nicht prim sind.

b) Finde unendlich viele solcher primfreien ${}r$-„Intervalle“.

Aufgabe *

Zeige durch Induktion, dass jede natürliche Zahl ${}n\geq 2$ eine Zerlegung in Primzahlen besitzt.

Aufgabe

Berechne den Ausdruck

$n^{2}+n+41$

für ${}n=0,1,2,\ldots$. Handelt es sich dabei um Primzahlen?

Aufgabe *

Es sei ${}n$ eine natürliche Zahl. Wann ist die Zahl ${}n^{2}-1$ eine Primzahl?

Aufgabe

Das Schaubild rechts bezieht sich auf die Goldbachsche Vermutung. Was wird dadurch dargestellt?

Aufgabe

Zeige, dass man jede natürliche Zahl ${}n\geq 12$ als Summe

${}n=a+b\,$

schreiben kann, wobei sowohl ${}a$ als auch ${}b$ zusammengesetzte Zahlen sind.

Aufgabe

Welche Zifferenentwicklung hat eine Mersennesche Primzahl im Dualsystem?

Aufgabe *

Zeige: Ist ${}2^{n}-1$ eine Primzahl, so ist auch ${}n$ eine Primzahl.

In der folgenden Aufgabe wird ein weiteres offenes Problem formuliert. Man mache sich die Wirkungsweise des beschriebenen Algorithmus für die Zahlen bis ${}20$ klar.

Aufgabe

Für positive ganze Zahlen ${}n$ betrachten wir folgenden Algorithmus.

Wenn ${}n$ gerade ist, so ersetze ${}n$ durch die Hälfte.

Wenn ${}n$ ungerade ist, so multipliziere ${}n$ mit ${}3$ und addiere dann ${}1$ dazu.

Frage (Collatz-Problem): Ist es wahr, dass man bei jeder Startzahl ${}n$ früher oder später bei ${}1$ landet?

Aufgabe

Zwei Spieler sitzen an einem runden Tisch und legen abwechselnd eine Münze (alle von der gleichen Größe, die kleiner als die Größe der Tischplatte ist) auf den Tisch, wobei sich die Münzen nicht überdecken dürfen. Es verliert der Spieler, der keine Münze mehr platzieren kann. Entwerfe eine Gewinnstrategie für den Spieler, der anfängt.

Aufgabe

Bei der Fußball-Europameisterschaft 2016 qualifizieren sich die vier besten Drittplatzierten (der Vorrundengruppen A,B,C,D,E,F) für das Achtelfinale, und zwar nach dem Schema

${\text{ Sieger Gruppe }}D{\text{ spielt gegen einen Dritten aus }}(B,E,F),$

${\text{ Sieger Gruppe }}B{\text{ spielt gegen einen Dritten aus }}(A,C,D),$

${\text{ Sieger Gruppe }}C{\text{ spielt gegen einen Dritten aus }}(A,B,F),$

und

${\text{ Sieger Gruppe }}A{\text{ spielt gegen einen Dritten aus }}(C,D,E).$

1. Zeige, dass dies stets durchführbar ist.
2. Bestimme (abhängig von der Reihenfolge der Drittplatzierten) die minimale Anzahl an Möglichkeiten für die Aufteilung der Drittplatzierten.
3. Bestimme (abhängig von der Reihenfolge der Drittplatzierten) die maximale Anzahl an Möglichkeiten für die Aufteilung der Drittplatzierten.

In den folgenden Aufgaben wird an einige wichtige Beweisverfahren erinnert. Überlegen Sie sich typische Beispiele dazu. Inwiefern kommen diese Argumentationsmuster auch im Alltag vor?

Aufgabe *

Erläutere das Prinzip Beweis durch Widerspruch für eine Aussage der Form „Aus ${}A$ folgt ${}B$“.

Aufgabe *

Erläutere das Beweisprinzip der vollständigen Induktion.

Aufgabe

Erläutere das Prinzip Beweis durch Fallunterscheidung.

Aufgabe *

Franziska möchte mit ihrem Freund Heinz Schluss machen. Sie erwägt die folgenden drei Begründungen.

1. „Du hast dich schon am ersten Tag voll daneben benommen. Seitdem ist es von jedem Tag zum nächsten Tag nur noch schlimmer geworden. Du wirst Dich also immer völlig daneben benehmen“.
2. „Wenn ich mit Dir zusammenbleiben würde, so würde ich irgendwann als eine traurige, gelangweilte, vom Leben enttäuschte Person enden, das möchte ich aber auf gar keinen Fall“.
3. „Also, wenn Du mich nicht liebst, will ich Dich sowieso nicht. Wenn Du mich aber liebst, so komme ich zu dem Schluss, dass Du dein Verhalten mit Deinen Gefühlen nicht zur Deckung bringen kannst. Dann bist Du also unreif und dann will ich Dich auch nicht“.

Welche mathematischen Beweisprinzipien spiegeln sich in den drei Begründungen wieder?

Aufgabe *

1. Löse das folgende Minisudoku

   ${\begin{pmatrix}-&-&2&-\\3&-&-&4\\-&-&-&-\\-&4&-&1\end{pmatrix}}.$

2. Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
3. Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?

Aufgabe *

Zeige, dass ${}{\sqrt {2}}$ eine irrationale Zahl ist.

Wie sieht es mit ${}{\sqrt {3}},{\sqrt {4}},{\sqrt {5}},{\sqrt {6}}$ aus?

Aufgabe

Beweise durch Induktion die folgenden Formeln.

1. ${}\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}\,,$

2. ${}\sum _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}\,.$

3. ${}\sum _{i=1}^{n}i^{3}={\left({\frac {n(n+1)}{2}}\right)}^{2}\,.$

Aufgabe

Die Städte ${}S_{1},\ldots ,S_{n}$ seien untereinander durch Straßen verbunden und zwischen zwei Städten gibt es immer genau eine Straße. Wegen Bauarbeiten sind zur Zeit alle Straßen nur in eine Richtung befahrbar. Zeige, dass es trotzdem mindestens eine Stadt gibt, von der aus alle anderen Städte erreichbar sind.

Aufgabe

In der folgenden Argumentation wird durch Induktion bewiesen, dass alle Pferde die gleiche Farbe haben. „Es sei ${}A(n)$ die Aussage, dass je ${}n$ Pferde stets untereinander die gleiche Farbe haben. Induktionsanfang: Wenn nur ein Pferd da ist, so hat dieses eine bestimmte Farbe und die Aussage ist richtig. Für den Induktionsschritt sei vorausgesetzt, dass je ${}n$ Pferde stets untereinander die gleiche Farbe haben. Es seien jetzt ${}n+1$ Pferde gegeben. Wenn man eines herausnimmt, so weiß man nach der Induktionsvoraussetzung, dass die verbleibenden ${}n$ Pferde untereinander die gleiche Farbe haben. Nimmt man ein anderes Pferd heraus, so haben die jetzt verbleibenden Pferde wiederum untereinander die gleiche Farbe. Also haben all diese ${}n+1$ Pferde überhaupt die gleiche Farbe“. Analysiere diese Argumentation.

Aufgabe

Es seien ${}v\geq u\geq 0$ natürliche Zahlen. Zeige, dass

$x=v^{2}-u^{2},\,y=2uv,\,z=u^{2}+v^{2}$

die Gleichung

${}x^{2}+y^{2}=z^{2}\,$

erfüllen.

Aufgabe

Betrachte die „Definition“

Ein Hinz ist ein Kunz, dessen Schlonz ein Ranz ist,

und nehmen wir an, dass es sich um eine sinnvolle Definition handelt. Beantworte folgende Fragen.

1. Welcher Begriff wird neu eingeführt, welche sind schon bekannt?
2. Besitzt jeder Kunz einen Schlonz?
3. Besitzt jeder Hinz einen Schlonz?
4. Ist jeder Hinz ein Kunz?
5. Ist jeder Kunz ein Hinz?
6. Ist der Schlonz von jedem Kunz ein Ranz?
7. Ist der Schlonz von jedem Hinz ein Ranz?
8. Ist jeder Hinz ein Ranz?
9. Kann es einen Schlonz geben, der nicht zu einem Kunz gehört?
10. Wie kann man die Vermutung widerlegen, dass jeder Kunz ein Hinz ist?

Aufgabe

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.

Aufgabe

Wir betrachten eine Maschine, die nach und nach sämtliche Texte ausdruckt und damit auch früher oder später jeden Beweis ausgibt. Welche Eigenschaft eines in der Vorlesung 1 beschriebenen universellen Lösungsverfahrens besitzt diese Maschine nicht?

Aufgabe

Führe folgendes Gedankenexperiment durch: Es sei eine Maschine gegeben, die eine Aussage (eine Vermutung) über die natürlichen Zahlen nach und nach überprüft. Wenn sie alle Zahlen überprüft hätte, stünde die Antwort fest, doch da die Maschine Schritt für Schritt arbeitet, hat sie zu jedem Zeitpunkt immer nur eine endliche Teilmenge der natürlichen Zahlen überprüft und kann so, wenn die Aussage wahr ist, keinen Beweis für die Aussage liefern.

Im Allgemeinen braucht die Rechenmaschine für große Zahlen länger. Die Maschine wird jetzt beschleunigt, sodass sie für große Zahlen immer weniger Zeit braucht.

Die Maschine wird so beschleunigt, dass sie für die Überprüfung der ersten Zahl (also ${}1$) ${}{\frac {1}{2}}$ Sekunden braucht, für die Überprüfung der zweiten Zahl ${}{\frac {1}{4}}$ Sekunden, für die Überprüfung der dritten Zahl ${}{\frac {1}{8}}$ Sekunden. Für die Überprüfung der ${}n$-ten Zahl benötigt die Maschine also genau ${}\left({\frac {1}{2}}\right)^{n}$ Sekunden. Damit ist die Gesamtlaufzeit der Maschine

${\frac {1}{2}}+\left({\frac {1}{2}}\right)^{2}+\left({\frac {1}{2}}\right)^{3}+\ldots .$

Diese Summe ist wohldefiniert, und zwar gleich ${}1$ (im Zweiersystem ist es die Zahl ${}0,111111111\ldots$, deren Wert ${}1$ ist). Nach einer Sekunde hat also die Maschine die unendlich vielen Zahlen durchgearbeitet und überprüft, und damit die Aussage bewiesen oder widerlegt.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Zeige, dass es außer ${}3,5,7$ kein weiteres Zahlentripel der Form ${}p,p+2,p+4$ gibt, in dem alle drei Zahlen Primzahlen sind.

Aufgabe (4 Punkte)

Zeige, dass es unendlich viele Primzahlen gibt, die modulo ${}4$ den Rest ${}3$ besitzen.

Aufgabe (3 Punkte)

Zeige, dass es eine gerade Zahl ${}g$, ${}2\leq g\leq 252$, mit der Eigenschaft gibt, dass es unendlich viele Primzahlen ${}p$ derart gibt, dass auch ${}p+g$ eine Primzahl ist.

Aufgabe (4 Punkte)

Die Räuberbande „Robin Hood“ besteht aus sieben Personen. Sie legt für ihr Diebesgut eine Schatztruhe an, die sie mit verschiedenen Schlössern sichern möchte, wobei die (mehrfachen) Schlüssel an die Mitglieder verteilt werden sollen. Dabei soll erreicht werden, dass je drei Bandenmitglieder allein nicht an den Schatz kommen, dass aber je vier Bandenmitglieder die Truhe aufschließen können. Wie viele Schlösser braucht man dafür und wie müssen die Schlüssel verteilt werden?

Die Aufgabe zum Aufgeben

Lösungen zu der folgenden Aufgabe direkt an den Dozenten. Bis Ende April.

Aufgabe (8 Punkte)

Wir betrachten die Abbildung

$\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4},$

die einem Vierertupel ${}(a,b,c,d)$ das Vierertupel

$(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert )$

zuordnet. Man gebe ein Beispiel für ein Vierertupel ${}(a,b,c,d)$ mit der Eigenschaft an, dass sämliche Iterationen ${}\Psi ^{n}(a,b,c,d)$ für ${}n\leq 25$ nicht das Nulltupel liefern. Überprüfe das Ergebnis auf http://www.vier-zahlen.bplaced.net/raetsel.php .

Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)