Logik und insbesondere Aussagenlogik umgeben uns förmlich an den unwahrscheinlichsten Stellen: offensichtlich ja in technischen Geräten, aber selbst der Journalist von der Lokalzeitung um die Ecke kommt um sie nicht d’rum herum.
Und manchmal kann man in dem einen oder dem anderen Artikel lesen, wie besagter Lokaljournalist die Verneinung einer Implikation falsch umgesetzt hat 🙂↕️
Wir nenn die Symbole $0$ und $1$ Wahrheitswerte. Außerdem definieren wir $A$ eine Funktion (kennen wir eigentlich noch nicht, kommt aber im nächsten Kapitel)
$$ A:D\to\{0,1\}. $$$D$ ist dabei die Domäne und eine Teilmenge der atomaren Aussagen $A_n$.
Wir definieren weiterhin $E$ als Menge aller Aussagen, die aus $d\in D$ aufgebaut sind und ein verallgemeinertes $A':E\to\{0,1\}$ zu $A$ wie folgt:
So.. gerade noch $A'$ eingeführt, schon kommt unser Dozent damit an: “Wir wollen von nun an $A$ statt $A'$ als Bezeichnung nutzen”. Machste nix 🤷♂️
Beispiel
Seien $A,B,C$ atomare Formeln mit den Belegungen
Dann kann die Belegung für $(\lnot(A\lor B)\lor(C\land A))$ nach der Definition oben wie folgt
Jetzt kann es doch relativ müßig werden zu prüfen, bei welchen verschiedenen Belegungen eine Aussage wahr oder falsch wird. Um diesen Fall behandeln zu können füren wir die Wahrheitswertetabellen ein.
Dabei Enummerieren wir alle möglichen Belegungen binär, kombinieren also alle möglichen Belegungen, und können dann alle entsprechenden atomaren Formeln auswerten.
Dabei gibt $n^2$ die Anzahl aller Kombinationsmöglichkeiten, wobei $n$ die Anzahl der zu belegenden Variablen ist.
| A(F) | A(G) | A(F$\land G$) | A($F\lor G$) | A($\lnot F$) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Mathematiker sind ja bekanntlich einigermaßen faul und schreiben auch nicht gerne viel. Deswegen hat man sich irgendwann bestimmte Zeichen dafür ausgedacht, ob eine Aussage für eine ganze Menge, einige oder einzelne Elemente gilt:
Da Quantoren immer Teil einer Aussage sind, müssen wir sie logischerweise auch negieren können:
Dabei ist es sehr wichtig auf die Reihenfolge zu achten, in der wir Quantoren lesen und schreiben. Dazu gucken wir und mal folgendes Beispiel an:
$$ \forall n\in\mathbb{N}:\exists m\in\mathbb{N}: m>n. $$Lesen wir einfach von links nach rechts kommen wir auf die Aussage “Für alle natürlichen Zahlen $n$ existiert mindestens eine natürliche Zahl $m$, sodass $m>n$ ist.”
Das diese Aussage stimmt können wir uns einfach überlegen, indem wir uns überlegen wie wir ein größeres natürliches $m$ bekommen können. In unserem Fall können wir einfach $m=n+1$ setzen und haben so eine natürliche Zahl konstruiert, die immer größer als $n$ ist, egal welches $n$ wir gewählt haben.
$$ \exists m\in\mathbb{N}:\forall n\in\mathbb{N}: m>n. $$Lesen wir jetzt aber zuerst den Existenz- und dann den Allquantor lautet die Aussage “Es existiert eine natürliche Zahl $m$, sodass alle natürlichen Zahlen $n$ größer sind als $m$”.
Diese Aussage stimmt nicht, und auch das lässt sich relativ simple zeigen, diesmal über die Kontraposition. Nehmen wir also an die Aussage sei wahr: dann wählen wir $m=1$ und behaupten dieses $m$ sei größer als alle anderen natürlichen Zahlen. Das stimmt offenbar nicht, den schon $n=1$ verletzt hier unsere Voraussetzung $m>n$, denn $1\not>1$.
Letztes mal hatten wir schon kurz über Beweisansätze gesprochen. Heute sprechen wir nochmal über die selben Ansätze, nur diesmal mit Notizen aus der Vorlesung und nicht aus der Übung.
Folgere aus einer Aussage A, über irgendwelche Zwischenschritte, Aussage B
zu zeigen: $\forall n\in\mathbb{N}:n\mod2\ne0:n^2\mod2\ne0$. Mit Worten ausgedrückt: zu zeigen ist, dass das Quadrat aller natürlichen und ungeraden $n$ ebenfalls ungerade ist.
Beweis: Wir gehen jetzt von unserer Voraussetzung ($n$ ist natürlich und ungerade) aus und wollen irgendwie ankommen bei $n^2$ ist ungerade.
Dafür machen wir uns zuerst Gedanken was es heißt, wenn eine Zahl gerade oder ungerade ist. Eine gerade Zahl ist ohne Rest durch zwei teilbar und damit auch ein direktes Vielfaches der zwei.
$$ n_\text{gerade}=2k\mid\text{k\in\mathbb{N}} $$Ungerade Zahlen geteilt durch zwei geben immer Rest eins. Daraus folgern wir
$$ n_\text{ungerade}=2k+1\mid\text{k\mahtbb{N}_0}. $$Darauf bauen wir jetzt unsere Argumentation auf:
$$ \begin{align*} n^2=(2k-1)^2&=4k^2-4k+1 \\ &=\underbrace{2(2k^2-2k)}_{\text{immer gerade}}\underbrace{+1}_{\text{immer ungerade}} \end{align*} $$$(2k-1)^2$ lässt sich also in der Form einer ungeraden natürlichen Zahl schreiben. $\square$
zeige nicht $A\Rightarrow B$, sondern stattdessen $\lnot B\Rightarrow \lnot A$, falls sich die Aussage B einfach verneinen lässt
zu zeigen: $n^2\mod2=0\Rightarrow n\mod2=0$ für $n\in\mathbb{N}$. Ist $n^2$ gerade, dann ist auch $n$ gerade.
Beweis: Wir verneinen als erstes Beide Aussagen und erhalten
Unsere Aussage heißt jetzt also $\lnot B\Rightarrow\lnot A$: ist $n$ ungerade, so ist auch $n^2$ ungerade. Diese Aussage ist wahr und muss nicht mehr bewiesen werden, das haben wir ja oben schon gemacht :)
Gehe davon aus das eine Aussage wahr ist und zeige nur, dass die Negation dieser Aussage zu einem Widerspruch führt.
Für eine einfache Aussage $A$ zeigst du $\lnot A$, für eine komplexere Aussage $A\Rightarrow B$ zeigst du $\lnot(A\land\lnot B).$
zu zeigen: $\forall n\in\mathbb{N}\setminus\{1\}:n$ hat einen Primteiler $\lor n$ ist eine Primzahl.
Beweise: angenommen es existiert so ein $n$ sodass $\exists n\in\mathbb{N}\setminus\{1\}$ mit obigen Voraussetzungen, dann könnten wir so eine Argumentationskette bauen
| Fall 1: $d$ hat Primteiler | Fall 2: $d$ ist Primzahl |
|---|---|
| wir nennen den Primteiler $p | $n$ hat Primteiler |
| $p\min d$ und $d\mid n$ | |
| $p\mid n$ p teilt n, was nicht sein kann |
Last edited: 21.10.2026