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

Übungsaufgaben

Aufgabe

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

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 *

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 *

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

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.

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 *

Erläutere das Prinzip Beweis durch Widerspruch.

Aufgabe *

Erläutere das Beweisprinzip der vollständigen Induktion.

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.

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