Aussagenlogik und Beweisprinzipien – Mathe Studium 1. Semester Arbeitsblatt zum Herunterladen als PDF

Entscheiden Sie bei jedem Satz, ob er eine Aussage im Sinne der Logik ist. Falls ja, geben Sie den Wahrheitswert an und begründen Sie ihn kurz.

a) „Die Zahl \(91\) ist eine Primzahl.“
b) „Für alle reellen Zahlen \(x\) gilt \(x^2\ge0\).“
c) „Bitte schließen Sie die Tür.“
d) „\(x+3=7\)“

Gegeben sind die Aussagen \(A\) und \(B\). Stellen Sie die Wahrheitstafel für \(\neg A\wedge B\), \(A\Rightarrow\neg B\) und \(A\Leftrightarrow B\) auf.

a) Füllen Sie die vier Zeilen \((A,B)=(w,w),(w,f),(f,w),(f,f)\) für \(\neg A\wedge B\) aus.
b) Dasselbe für \(A\Rightarrow\neg B\).
c) Dasselbe für \(A\Leftrightarrow B\). Welche der drei Aussagen ist in genau einer Zeile wahr?

Bestimmen Sie den Wahrheitswert der Implikationen und begründen Sie mit der Definition (nur „wahr \(\Rightarrow\) falsch“ ist falsch).

a) „Wenn \(2+2=5\), dann ist \(3\) gerade.“
b) „Wenn \(4\) gerade ist, dann ist \(7\) eine Primzahl.“
c) „Wenn \(5\) eine Primzahl ist, dann ist \(5\) durch \(2\) teilbar.“
d) „\(3<2\Rightarrow 1=1\)“

Verneinen Sie mit den Regeln von De Morgan. Formulieren Sie das Ergebnis ohne „es ist nicht der Fall, dass“.

a) „\(x>2\) und \(x\) ist gerade.“
b) „\(x\le1\) oder \(x\ge5\).“
c) „Wenn \(x\) durch \(6\) teilbar ist, dann ist \(x\) durch \(3\) teilbar.“
d) „\(0<x<4\)“

Verneinen Sie die Aussagen und entscheiden Sie, ob die ursprüngliche Aussage (über \(\mathbb R\) bzw. \(\mathbb N\)) wahr ist.

a) \(\forall x\in\mathbb R:\ x^2>0\)
b) \(\exists n\in\mathbb N:\ n^2=2n\)
c) \(\forall x\in\mathbb R\ \exists y\in\mathbb R:\ x+y=0\)
d) \(\exists y\in\mathbb R\ \forall x\in\mathbb R:\ x+y=0\)

Bilden Sie zu jeder Implikation die Umkehrung und die Kontraposition und geben Sie jeweils den Wahrheitswert an (für ganze Zahlen \(n\) bzw. reelle Zahlen \(x\)).

a) „Wenn \(n\) durch \(4\) teilbar ist, dann ist \(n\) gerade.“
b) „Wenn \(x>3\), dann ist \(x^2>9\).“
c) „Wenn \(n\) eine Primzahl ist, dann ist \(n\) ungerade.“

Der Server im Rechenzentrum der Universität öffnet die Tür, wenn die Aussage \(Z=(K\wedge P)\vee S\) wahr ist. Dabei bedeutet \(K\): „gültige Chipkarte“, \(P\): „richtige PIN“, \(S\): „Sicherheitsdienst bestätigt“.

a) Wie viele Zeilen hat die Wahrheitstafel für \(Z\)? Stellen Sie sie vollständig auf.
b) In wie vielen Zeilen öffnet die Tür?
c) Ein Student hat die Karte, kennt aber die PIN nicht, und der Sicherheitsdienst ist nicht da. Öffnet die Tür?
d) Formulieren Sie die Negation \(\neg Z\) mit De Morgan.

Die Universitätsbibliothek formuliert Regeln über die Menge \(S\) aller Studierenden. Sei \(L(s)\): „\(s\) hat ein Buch ausgeliehen“ und \(M(s)\): „\(s\) hat eine Mahnung“.

a) Schreiben Sie in Quantorenschreibweise: „Jede Person mit Mahnung hat ein Buch ausgeliehen.“
b) Bilden Sie die Negation formal und in Worten.
c) Formulieren Sie: „Es gibt jemanden, der ein Buch ausgeliehen hat, aber keine Mahnung.“ Ist das die Negation von a)?
d) Wie lautet die Kontraposition von a)?

Entscheiden Sie mit einer Wahrheitstafel, ob die Aussage eine Tautologie ist. Notieren Sie dazu die Wertefolgen beider Seiten in der Reihenfolge der Zeilen ww, wf, fw, ff.

a) \((A\Rightarrow B)\Leftrightarrow(\neg B\Rightarrow\neg A)\)
b) \((A\Rightarrow B)\Leftrightarrow(B\Rightarrow A)\)
c) \(\neg(A\Rightarrow B)\Leftrightarrow(A\wedge\neg B)\)
d) \((A\vee B)\Rightarrow(A\wedge B)\)

Beweisen Sie direkt. Gehen Sie von der Definition „gerade: \(n=2k\)“ bzw. „ungerade: \(n=2k+1\)“ mit \(k\in\mathbb Z\) aus.

a) Das Produkt zweier ungerader Zahlen ist ungerade.
b) Die Summe von drei aufeinanderfolgenden ganzen Zahlen ist durch \(3\) teilbar.
c) Das Quadrat einer ungeraden Zahl hat bei Division durch \(8\) den Rest \(1\).

Beweisen Sie durch Kontraposition, indem Sie zuerst die Kontraposition aufschreiben.

a) Ist \(n^2\) gerade, so ist \(n\) gerade.
b) Gilt \(3\mid n^2\), so gilt \(3\mid n\).
c) Ist \(a\cdot b\) ungerade, so sind \(a\) und \(b\) beide ungerade.

Beweisen Sie durch Widerspruch.

a) \(\sqrt3\) ist irrational.
b) Es gibt keine kleinste positive reelle Zahl.
c) Es gibt keine ganzen Zahlen \(x,y\) mit \(x^2-4y=2\).

Welche Behauptungen sind falsch? Widerlegen Sie falsche Behauptungen durch ein Gegenbeispiel und begründen Sie wahre kurz.

a) Für alle \(n\in\mathbb N\) ist \(n^2+n+41\) eine Primzahl.
b) Für alle reellen \(a,b\) gilt \((a+b)^2=a^2+b^2\).
c) Jede Primzahl größer als \(2\) ist ungerade.
d) Für alle \(x\in\mathbb R\) gilt \(\sqrt{x^2}=x\).

Eine Folge \((a_n)\) konvergiert gegen \(a\), wenn \(\forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n\ge N:\ |a_n-a|<\varepsilon\).

a) Bilden Sie die Negation dieser Aussage formal.
b) Formulieren Sie sie in Worten.
c) Zeigen Sie mit der Negation, dass \(a_n=(-1)^n\) nicht gegen \(a=1\) konvergiert.
d) Mit welchem \(\varepsilon\) zeigen Sie, dass \(a_n=(-1)^n\) gegen keinen Wert \(a\) konvergiert?

Auf einer Insel sagt jeder Bewohner entweder immer die Wahrheit (Ritter) oder immer die Unwahrheit (Lügner). Sie treffen zwei Bewohner \(X\) und \(Y\). \(X\) sagt: „Mindestens einer von uns beiden ist ein Lügner.“

a) Sei \(R_X\): „\(X\) ist Ritter“, \(R_Y\): „\(Y\) ist Ritter“. Schreiben Sie die Aussage von \(X\) logisch auf.
b) Untersuchen Sie den Fall „\(X\) ist Lügner“ und führen Sie ihn zum Widerspruch.
c) Bestimmen Sie, was \(X\) und \(Y\) sind.
d) Was folgt, wenn \(X\) stattdessen sagt: „Wir sind beide Lügner“?

Ein Prozessor-Entwickler baut aus Gattern die Schaltung \(Q=(A\vee B)\wedge\neg(A\wedge B)\). Dabei steht w für Strom an und f für Strom aus.

a) Ergänzen Sie die Tabelle.
b) Welche gängige Verknüpfung ist \(Q\)?
c) Zeigen Sie mit De Morgan: \(Q\equiv(A\vee B)\wedge(\neg A\vee\neg B)\).
d) Wie viele Zeilen hätte die Wahrheitstafel einer Schaltung mit \(8\) Eingängen?

In einer Übung zeigt Ihr Tutor, dass die Zahl \(n^3-n\) für alle ganzen Zahlen \(n\) durch \(6\) teilbar ist. Sie sollen den Beweis Schritt für Schritt führen.

a) Zerlegen Sie \(n^3-n\) in drei Faktoren.
b) Begründen Sie, dass unter drei aufeinanderfolgenden ganzen Zahlen mindestens eine durch \(2\) und genau eine durch \(3\) teilbar ist (Fallunterscheidung nach dem Rest von \(n\) modulo \(3\)).
c) Schließen Sie, dass \(6\mid n^3-n\) gilt.
d) Prüfen Sie die Aussage für \(n=7\) und \(n=-4\).

Zeigen Sie in mehreren Schritten, dass \(\log_2 3\) irrational ist.

a) Nehmen Sie an, \(\log_23=\frac pq\) mit natürlichen Zahlen \(p,q\ge1\). Was folgt für \(2^{p/q}\)?
b) Leiten Sie \(2^p=3^q\) her.
c) Führen Sie diese Gleichung mit Hilfe der Teilbarkeit zum Widerspruch.
d) Wie heißt der Beweistyp, und warum genügt die Annahme „\(p,q\ge1\)“?

Ihre Prüfungsordnung enthält die Regeln: (R1) Wer Analysis 1 nicht bestanden hat, darf Analysis 2 nicht belegen. (R2) Wer Analysis 2 belegt, hat Lineare Algebra 1 bestanden. (R3) Lena hat Lineare Algebra 1 nicht bestanden. Sei \(A_1\): „Analysis 1 bestanden“, \(A_2\): „Analysis 2 belegt“, \(L\): „Lineare Algebra 1 bestanden“.

a) Schreiben Sie R1 bis R3 mit \(\neg\) und \(\Rightarrow\) auf.
b) Folgern Sie mit der Kontraposition von R2, ob Lena Analysis 2 belegt hat.
c) Kann man aus den Regeln schließen, ob Lena Analysis 1 bestanden hat?
d) Wie lautet die Regel, wenn R2 durch die Umkehrung ersetzt wird? Ändert sich b)?

Ein Student „beweist“: Sei \(a=b\). Dann gilt \(a^2=ab\), also \(a^2-b^2=ab-b^2\), also \((a+b)(a-b)=b(a-b)\). Kürzen ergibt \(a+b=b\), mit \(a=b\) also \(2b=b\) und somit \(2=1\).

a) Welche der Umformungen sind korrekte Folgerungen?
b) Finden Sie den fehlerhaften Schritt und begründen Sie ihn.
c) Wie ändert sich der Beweis, wenn man zusätzlich \(a\ne b\) fordert?
d) Warum ist „Rückwärtsrechnen aus der Behauptung“ riskant? Geben Sie ein Beispiel.

Das Schubfachprinzip lautet: Verteilt man \(n+1\) Objekte auf \(n\) Fächer, so enthält mindestens ein Fach zwei Objekte. An einer Hochschule studieren 1 466 Personen. Jede Person hat an einem von 365 Tagen des Jahres Geburtstag.

a) Beweisen Sie das Schubfachprinzip durch Widerspruch.
b) Zeigen Sie, dass an mindestens einem Tag mindestens fünf Personen Geburtstag haben.
c) Zeigen Sie: Unter je 13 ganzen Zahlen gibt es zwei, deren Differenz durch 12 teilbar ist.
d) Gilt die Aussage aus c) auch für 12 Zahlen? Geben Sie ein Gegenbeispiel an.