🎓 Ui, schon Prüfungszeit? Hier geht's zur Mathe-Prüfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Kurs

Grundlagen der Logik

1 Einleitung (in Arbeit)

Einer der Grundbausteine, auf denen die modernen Kommunikations- und Informationstechnologien beruhen, ist Logik. Daher ist es höchst empfehlenswert, zumindest einen groben Blick auf die mathematische Logik zu werfen.

In diesem Kurs lernst du, dass eine Aussage nicht zwingend immer nur zum Deutschunterricht oder einer Gerichtsverhandlung gehört. Du untersuchst, ob Kombinationen oder Veränderungen von Aussagen gültig sind. Dieser Kurs bietet dabei nur einen kurzen und einfachen Einstieg in die einfachen Bausteine.

Insbesondere wirst du in diesem Kurs zunächst nur Aussagen kennenlernen, das sind Behauptungen, deren Wahrheitsgehalt feststellbar ist.

In manchen Situationen ist das nicht ausreichend: willst du z.B. feststellen, ob der "Schluss" x<5x<6x<5\Rightarrow x<6 gültig ist, musst du das Konzept der Aussageformen verwenden - du kannst ja nicht feststellen, ob x<5x<5 eine wahre Aussage ist, weil darin die Variable xx enthalten ist.

Eine kurze Einführung in Aussageformen findest du in den letzten Kapiteln des Kurses, eine ausführliche Diskussion dieses Themas in Grundlagen der Mathematik.

Hier lernst du, verschiedene Aussagen zu kombinieren und den Wahrheitsgehalt der Kombination abhängig von den Wahrheitsgehalten der einzelnen Teilaussagen zu bestimmen.

Beachte

(Aussagen-)Logik untersucht nicht den Wahrheitsgehalt einer Aussage direkt, sondern leitet diesen aus bereits erlangtem Wissen ab.

2 Aussagen und Wahrheitwert (in Arbeit)

In der Logik geht es darum, verschiedene Aussagen zu kombinieren.

Daher wird der zentrale Begriff der Aussage erklärt:

Eine (mathematische) Aussage ist eine Behauptung über einen (mathematischen) Sachverhalt, von der feststellbar ist, ob sie wahr oder falsch ist.

Das bedeutet, dass jeder Aussage genau einer der Wahrheitswerte wahr oder falsch zugeordnet werden kann. Dabei kommt es nicht darauf an, dass der Wahrheitswert direkt ersichtlich ist, sondern nur, dass dies prinzipiell möglich ist.

Der Wahrheitswert "wahr" wird mit (w)(w), der Wert "falsch" mit (f)(f) abgekürzt.

Beispiele

  • 1+1=1(w)1+1=1\quad (w)

  • 3+9<4(f)3+9<4\quad (f)

  • f:xx3f:x\mapsto x^3 ist streng monoton steigend (w)(w)

  • 3100>1000163^{100}>1000^{16}

Der vierten Aussage kann man nicht unbedingt direkt einen Wahrheitswert zuordnen. Es ist aber prinzipiell möglich: es ist 3100510473^{100}\approx 5\cdot 10^{47} und 100016=10481000^{16}=10^{48}. Die Aussage ist also falsch.

Ein Gegenbeispiel ist "Pudding schmeckt gut", weil der Wahrheitsgehalt hiervon nicht objektiv bestimmbar ist.

Aussagen werden oft durch Großbuchstaben bezeichnet, also z.B.

A:1+1=2A:\, 1+1=2

3 Nicht (in Arbeit)

Eine Aussage lässt sich einfach verneinen (man sagt auch "negieren"). Sprachlich geschieht das meistens durch das Wort "nicht":

A:A: "Es regnet." wird nach der Verneinung zu ¬A\neg A (oder auch A\overline{A}): "Es regnet nicht."

¬A\neg A nennt man Verneinung oder Negation von AA.

Das, was vorher gegolten hat, gilt jetzt genau nicht mehr. In Zweifelsfällen ist es oft am sichersten, der Aussage AA den Satzteil "Es ist nicht so, dass. . . " voranzustellen.

Dabei gelten die Regeln:

  • Ist AA wahr, so ist ¬A\neg A falsch.

  • Ist AA falsch, so ist ¬A\neg A wahr.

  • ¬(¬A)\neg(\neg A) hat denselben Wahrheitswert wie AA

Die dritte Regel hat den Namen "Gesetz der doppelten Negation".

Beispiele

  • Ist A die wahre Aussage "66 ist durch 33 teilbar", so ist ¬A\neg A die falsche Aussage "Es ist nicht so, dass 66 durch 33 teilbar ist". Das lässt sich auch als "66 ist nicht durch 33 teilbar" formulieren.

  • Die Negation von "55 ist eine gerade Zahl" ist "55 ist eine ungerade Zahl".

  • Ist AA die (falsche) Aussage "Alle Zahlen sind gerade", so ist die Negation von AA zunächst "Es ist nicht so, dass alle Zahlen gerade sind". Das kannst du zu "Es gibt mindestens eine ungerade Zahl" umformulieren. Die Aussage "Alle Zahlen sind ungerade" ist nicht die Negation von AA, was man schon daran merken kann, dass diese Aussage genauso falsch wie AA ist.

4 Und (in Arbeit)

Mehrere Aussagen lassen sich durch ein logisches "Und" (Symbol: \wedge) miteinander verknüpfen. Das logische Und bedeutet dabei eigentlich "und gleichzeitig". Damit der Ausdruck als wahr ausgewertet wird, muss also jede der Aussagen wahr sein.

Anders formuliert: Die Aussageverknüpfung ABA\wedge B ist schon falsch, wenn auch nur eine der beiden Aussagen AA und BB falsch ist.

Die Aussageverknüpfung "Und" heißt auch Konjunktion.

Für AA: "5<75<7" und BB: "55 ist ungerade" kann man ABA\wedge B formulieren als "5 ist kleiner als 77 und ungerade". Da AA und BB wahr sind, ist auch ABA\wedge B wahr.

In der Umgangssprache bezeichnet "und" oft eine zeitliche Abfolge:

"Sie trank ihr Glas leer und ging".

Mathematisch bedeutet ABA\wedge B das gleichzeitige Erfülltsein der beiden Aussagen.

Ist AA eine Aussage, dann ist A¬AA\wedge \neg A immer falsch, weil entweder AA oder ¬A\neg A falsch sein muss.

Weitere Beispiele:

  • NQR\mathbb{N}\subset\mathbb{Q}\subset\mathbb{R} ist die (wahre) Aussage (NQ)(QR)(\mathbb{N}\subset\mathbb{Q})\wedge(\mathbb{Q}\subset\mathbb{R})

  • Analog bedeutet 3<π<43<\pi<4 genauer (3<π)(π<4)(3<\pi)\wedge(\pi<4) - eine wahre Aussage, da beide Teile wahr sind.

  • (1<2)(4<3)(1<2)\wedge(4<3) ist falsch, da der zweite Teil falsch ist.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

ABA\wedge B und BAB\wedge A haben denselben Wahrheitswert

(AB)C(A\wedge B)\wedge C und A(BC)A\wedge (B\wedge C) haben denselben Wahrheitswert. Diese Regel überträgt sich natürlich sofort auf mehr als drei Aussagen: Eine Und-Kombination von mehreren Aussagen ist nur dann wahr, wenn alle Aussagen wahr sind. Ist auch nur eine der Aussagen falsch, ist auch die Kombination falsch.

5 Oder (in Arbeit)

Das logische "Oder" \vee für zwei Aussagen kannst du dir vorstellen als: entweder die eine oder die andere oder beide Aussagen sind erfüllt. Es muss also mindestens eine der beteiligten Aussagen gelten, damit der Ausdruck als wahr gewertet werden kann.

Anders formuliert: die Verknüpfung ABA\vee B ist nur dann falsch, wenn AA und BB beide falsch sind.

Die Aussageverknüpfung "Oder" heißt auch Disjunktion.

(2<3)(4<3)(2<3)\vee (4<3) ist wahr, da der erste Teil wahr ist. Dass der zweite Teil falsch ist, ändert nichts.

Ist AA eine Aussage, dann ist A¬AA\vee \neg A immer wahr, weil entweder AA oder ¬A\neg A wahr sein muss.

Die (nicht ganz so mathematische) Aussage "Sein oder nicht Sein" ist also unproblematisch, weil sie immer wahr ist.

(3<2)(22>5)(3<2)\vee (2^2>5) ist falsch, weil beide Klammern falsch sind.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

ABA\vee B und BAB\vee A haben denselben Wahrheitswert

(AB)C(A\vee B)\vee C und A(BC)A\vee (B\vee C) haben denselben Wahrheitswert. Diese Regel überträgt sich natürlich sofort auf mehr als drei Aussagen: eine Oder-Verknüpfung ist wahr, wenn mindestens eine der Aussagen wahr ist. Anders formuliert: eine Oder-Verknüpfung ist nur dann falsch, wenn alle Aussagen falsch sind.

6 Wahrheitswerttabellen (in Arbeit)

Um dir einen Überblick über die Bedeutung von Aussagekombinationen zu verschaffen, sind Wahrheitswerttabellen ein gutes Mittel.

Dazu schreibst du (möglichst systematisch) alle möglichen Wahrheitswerte der beteiligten Aussagen in eine Spalte und untersuchst den Wahrheitswert einer Kombination.

Je nach Anzahl der Aussagen musst du eine passende Anzahl von Fällen unterscheiden. Bei einer Aussage sind es zwei (es gibt ja nur (w)\left(w\right) und (f) \left(f\right)\ ), bei zwei Aussagen vier, bei drei Aussagen acht und allgemein bei nn Aussagen 2n2^n.

Das ist die einfachste Tabelle, die für ¬A\neg A:

AA

¬A\neg A

ww

ff

ff

ww

In der linken Spalte stehen die beiden Möglichkeiten der Wahrheitswerte von AA, in der rechten die entsprechenden von ¬A\neg A.

Wahrheitswerttabellen haben aber den Vorteil, dass man mehrere Kombinationen gleichzeitig untersuchen kann. Das wird sofort mit "Und" und "Oder" ausprobiert:

AA

BB

ABA\wedge B

ABA\vee B

ww

ww

ww

ww

ww

ff

ff

ww

ff

ww

ff

ww

ff

ff

ff

ff

Links sind alle Kombinationen der möglichen Wahrheitswerte von AA und BB aufgeschrieben, in der Spalten unter ABA\wedge B und ABA\vee B stehen die entsprechenden Wahrheitswerte der Verknüpfungen.

7 Äquivalenz (in Arbeit)

Man nennt zwei logische Ausdrücke AA und BB äquivalent (Schreibweise: ABA\Leftrightarrow B), wenn beide wahr oder beide falsch sind.

Zwei Aussageverknüpfungen nennt man äquivalent, wenn der Wahrheitswert der Verknüpfungen für jede Kombination der Wahrheitswerte der einzelnen beteiligten Aussagen gleich ist. Als Schreibweise wird wieder \Leftrightarrow verwendet.

Die Äquivalenz von Aussageverknüpfungen kannst du mit Wahrheitswerttabellen nachweisen. Wenn du alle Möglichkeiten der einzelnen Wahrheitswerte auflistest und die fraglichen Ausdrücke immer denselben Wahrheitswert haben, sind sie äquivalent.

Eine andere Möglichkeit ist die Verwendung von logischen Regeln wie den de Morganschen Regeln oder der Distributivgesetze.

Beispiel: ((A¬B)(¬AB))(AB)(¬A¬B))\left((A\wedge \neg B)\vee(\neg A\wedge B)\right)\Leftrightarrow\left(A\vee B)\wedge(\neg A\vee \neg B)\right)

Als Abkürzung kann man C:(A¬B)(¬AB)C:\Leftrightarrow (A\wedge\neg B)\vee(\neg A\wedge B) und D:(AB)(¬A¬B)D:\Leftrightarrow (A\vee B)\wedge(\neg A\vee\neg B) verwenden, du musst also CDC\Leftrightarrow D nachweisen.

AA

BB

A¬BA\wedge \neg B

¬AB\neg A\wedge B

C\color{red}{C}

ABA\vee B

¬A¬B\neg A\vee \neg B

D\color{red}{D}

ww

ww

ff

ff

f\color{red}{f}

ww

ff

f\color{red}{f}

ww

ff

ww

ff

w\color{red}{w}

ww

ww

w\color{red}{w}

ff

ww

ff

ww

w\color{red}{w}

ww

ww

w\color{red}{w}

ff

ff

ff

ff

f\color{red}{f}

ff

ww

f\color{red}{f}

Also sind die Ausdrücke äquivalent.

Diese Verknüpfung ist also genau dann wahr, wenn eine der Aussagen AA und BB wahr sind, aber nicht beide.

Diese Verknüpfung hat den Namen "exklusives Oder" (nicht mit "Oder" verwechseln!)

8 Einfache Äquivalenzen (in Arbeit)

Jetzt kannst du einfache Regeln aufstellen. ww soll dabei eine wahre, ff eine falsche Aussage bedeuten.

Idempotenz

AAAA\wedge A\Leftrightarrow A und AAAA\vee A\Leftrightarrow A

Absorbtion

AwAA\wedge w\Leftrightarrow A und AwwA\vee w\Leftrightarrow w

AffA\wedge f\Leftrightarrow f und AfAA\vee f\Leftrightarrow A

Diese Regeln kannst du direkt einsehen, aber auch zur Übung mit einer Wahrheitswerttabelle beweisen.

Diese Regeln kennst du schon, sie sind hier nur zur Vollständigkeit noch einmal aufgeschrieben:

Kommutativgesetze

ABBAA\vee B \Leftrightarrow B \vee A und ABBAA\wedge B \Leftrightarrow B \wedge A

Assoziativgesetze

(AB)CA(BC)(A\wedge B)\wedge C \Leftrightarrow A \wedge (B\wedge C) und (AB)CA(BC)(A\vee B)\vee C \Leftrightarrow A \vee (B\vee C)

Weitere Regeln

A¬AwA\vee \neg A \Leftrightarrow w

A¬AfA\wedge \neg A \Leftrightarrow f

9 De Morgansche Regeln (in Arbeit)

Was bedeutet es, wenn man eine "Und"-Aussage negiert? Probiere das an einem Beispiel aus und nimm die Gleichung (x1)(x2)=0(x-1)(x-2)=0. Dann haben wir zwei Aussagen:

AA: 11 ist eine Lösung der Gleichung

BB: 22 ist eine Lösung der Gleichung

Dann ist - da AA und BB beide wahr sind, ABA\wedge B auch wahr.

Was würde es bedeuten, wenn ABA\wedge B falsch wäre? Dann müsste entweder 11 keine Lösung sein oder 22 ist keine Lösung.

Also könnten AA und BB nicht gleichzeitig gelten - daher muss mindestens eine der Aussagen falsch sein. Nach den Regeln der Negation heißt das, dass entweder ¬A\neg A oder ¬B\neg B wahr sein muss, also ¬A¬B\neg A \vee \neg B.

Das ist eine der de Morganschen Regeln:

¬(AB)\neg(A \wedge B) ist gleichbedeutend mit (¬A)(¬B)(\neg A)\vee (\neg B).

Dafür benutzt man auch das Zeichen \Leftrightarrow (die genaue Bedeutung wird im Abschnitt über Äquivalenz erklärt):

¬(AB)(¬A)(¬B)\neg(A\wedge B)\Leftrightarrow(\neg A)\vee(\neg B)

Die andere de Morgansche Regel ist

¬(AB)(¬A)(¬B)\neg(A\vee B)\Leftrightarrow(\neg A)\wedge(\neg B)

Diese Regel kann man so erklären: wenn ABA\vee B falsch ist, dann müssen ¬A\neg A und ¬B\neg B wahr sein.

Zu kompliziert gedacht? Dafür haben wir ja die Möglichkeit, die Äquivalenz der Ausdrücke mit Wahrheitswerttabellen nachzuprüfen:

AA

BB

ABA\wedge B

¬(AB)\color{red}{\neg(A\wedge B)}

¬A\neg A

¬B\neg B

(¬A)(¬B)\color{red}{(\neg A)\vee(\neg B)}

ww

ww

ww

f\color{red}{f}

ff

ff

f\color{red}{f}

ww

ff

ff

w\color{red}{w}

ff

ww

w\color{red}{w}

ff

ww

ff

w\color{red}{w}

ww

ff

w\color{red}{w}

ff

ff

ff

w\color{red}{w}

ww

ww

w\color{red}{w}

Da die roten Spalten übereinstimmen, sind die beiden Ausdrücke äquivalent.

10 Distributivgesetze (in Arbeit)

Ähnlich wie bei den Zahlen das Distributivgesetz a(b+c)=(ab)+(ac)a\cdot(b+c)=(a\cdot b)+(a\cdot c) gilt, gibt es auch für die Logik-Verknüpfungen "Und" und "Oder" je ein Distributivgesetz:

A(BC)(AB)(AC)A\wedge(B\vee C)\Leftrightarrow(A\wedge B)\vee(A\wedge C)

A(BC)(AB)(AC)A\vee(B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee C)

Sicher weißt du schon, wie du die Gültigkeit der Regeln nachprüfen kannst. Es geht natürlich mit einer Wahrheitswerttabelle! Da es drei Aussagen sind, musst du 23=82^3=8 Fälle unterscheiden. Das kannst du in einer Aufgabe nachrechnen.

Diesmal kannst du aber auch anders überlegen und dir dabei die schon bewiesenen Regeln zunutze machen. Los geht es mit

A(BC)(AB)(AC)A\wedge(B\vee C)\Leftrightarrow(A\wedge B)\vee(A\wedge C)

  • Wenn AA wahr ist, dann ist die linke Seite nach dem Absorptionsgesetz äquivalent zu BCB\vee C. Aber auch rechts kann man nach dem Absorptionsgesetz ABA\vee B zu BB und ACA\vee C zu CC zusammenziehen, also ist die rechte Seite auch zu BCB\vee C äquivalent.

  • Wenn AA falsch ist, dann ist sicher die linke Seite falsch, und weil dann auch ABA\wedge B und ACA\wedge C falsch sind, ist es auch die rechte Seite.

Ganz ähnlich beweist du das zweite Distributivgesetz

A(BC)(AB)(AC)A\vee(B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee C)

  • Wenn AA wahr ist, dann ist die linke Seite wahr, und weil dann auch ABA\vee B und ACA\vee C wahr sind, ist es auch die rechte Seite.

  • Wenn AA falsch ist, ist nach dem Absorptionsgesetz die linke Seite äquivalent zu BCB\wedge C. Aus dem gleichen Grund ist ABA\vee B zu BB und ACA\vee C zu CC äquivalent, also ist die rechte Seite genau wie die linke zu BCB\wedge C äquivalent.

11 Implikation (in Arbeit)

Sind AA und BB Aussagen, so definiert man die Implikation ABA\Rightarrow B durch ¬AB\neg A \vee B.

Die Idee dabei ist so: die Implikation soll bedeuten, dass aus der Aussage AA die Aussage BB folgt, d.h. wenn AA wahr ist, soll auch BB wahr sein. Ist AA falsch, gibt es keine Bedingung an BB.

Das bedeutet, dass die Wahrheitswerttabelle von ABA\Rightarrow B so aussieht:

AA

BB

ABA\Rightarrow B

ww

ww

ww

ww

ff

ff

ff

ww

ww

ff

ff

ww

Die ersten beiden Zeilen sagen "Wenn AA wahr ist, ist auch BB wahr und nicht etwa falsch". Die unteren beiden Zeilen sagen "Wenn AA falsch ist, kann BB wahr oder falsch sein, beides ist OK".

Was hat das denn nun mit ¬AB\neg A \vee B zu tun?

Eine Möglichkeit ist es, eine Wahrheitswerttabelle dazu aufzustellen und zu sehen, dass die Aussageverknüpfungen wirklich äquivalent sind. Eine andere ist die Benutzung der de Morganschen Regeln und der Distributivgesetze.

Einfache Beispiele

(Aw)w(A\Rightarrow w)\Leftrightarrow w

(wA)A(w\Rightarrow A)\Leftrightarrow A

(Af)¬A(A\Rightarrow f)\Leftrightarrow \neg A

(fA)w(f\Rightarrow A)\Leftrightarrow w

Zusammenhang mit der Äquivalenz

Die Idee ist, dass zwei Aussageverknüpfungen äquivalent sind, wenn jeweils eine aus der anderen folgt:

(AB)((AB)(BA))(A\Leftrightarrow B) \Leftrightarrow \Big( (A\Rightarrow B) \wedge (B\Rightarrow A)\Big)

12 Aufgaben 1

13 Aufgaben 2

Laden


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?