Logik¶
Die (Aussagen-)Logik ist für sämtliche Teilbereiche der Mathematik von grundlegender Bedeutung.
Satz und Aussage¶
Lässt sich einem Satz ein Wahrheitswert ( oder ) eindeutig zuordnen, so wird dieser Satz zu einer Aussage.
Als Darstellungsform für den Wahrheitswert von Aussagen wählt man häufig so genannte „Wahrheitstafeln“. Dabei werden spaltenweise die Wahrheitswerte der in der Kopfzeile angegebenen Aussage(n) aufgelistet.
Beispiele:
- Der Satz „“ ist eine wahre Aussage.
- Der Satz „“ ist eine falsche Aussage.
- Der Satz „“ ist eine wahre Aussage.
- Der Satz „“ ist keine Aussage, da ihm kein Wahrheitswert zugeordnet werden kann.
Ein Satz ist auch dann eine Aussage, wenn sein Wahrheitswert zum gegebenen Zeitpunkt nicht feststellbar ist. Beispielsweise handelt es sich bei dem Satz „Am 3. April 1650 regnete es in Berlin.“ ebenfalls um eine Aussage, auch wenn sich ihr Wahrheitswert mit großer Wahrscheinlichkeit nicht mehr feststellen lässt.
Negation einer Aussage
Durch Verneinen einer Aussage entsteht eine Aussage , die Negation der Aussage genannt wird. Da der konkrete Wahrheitswert einer negierten Aussage stets vom Wahrheitswert der eigentlichen Aussage abhängt, hat die entsprechende Wahrheitstafel zwei Spalten.
Die Negation einer wahren Aussage ist falsch, die einer falschen ist wahr; insbesondere entspricht die doppelte Negation einer Aussage der ursprünglichen Aussage .
Beispiele:
- : „Die Geraden und schneiden sich.“
- : „Die Geraden und schneiden sich nicht.“
- : „Es ist nicht wahr, dass die Geraden und sich nicht schneiden.“
Verknüpfungen von Aussagen¶
Mit Hilfe von Bindewörtern wie „und“, „oder“, „genau dann, wenn“ usw. lassen sich mehrere (Teil-)Aussagen zu einer zusammengesetzten Aussage verknüpfen. In der Logik lassen sich mit Hilfe der folgenden Aussage-Funktionen zwei (oder mehrere) Aussagen zu einer neuen Aussage formen.
Die Konjunktion
Verknüpft man zwei Aussagen und durch das Wort „und“, so entsteht die Konjunktion der Aussagen und , symbolisch mit bezeichnet.
Eine Konjunktion zweier Aussagen ist somit nur wahr, wenn beide (Teil-)Aussagen wahr sind.
Beispiele:
- Die Konjunktion der wahren Aussage „ ist eine gerade Zahl“ mit der falschen Aussage „ ist durch teilbar“ ist die falsche Aussage : „ ist eine gerade Zahl und durch teilbar“.
- Die falsche Aussage „Der Mars ist ein Gasplanet und hat eine größere Masse als die Erde“ ist eine Konjunktion der falschen Aussagen „Der Mars ist ein Gasplanet“ und „Der Mars hat eine größere Masse als die Erde“.
Die Adjunktion
Verknüpft man zwei Aussagen und durch das Wort „oder“, so entsteht die Adjunktion der Aussagen und , symbolisch mit bezeichnet.
Die Adjunktion ist somit wahr, wenn eine der beiden Aussagen wahr ist (oder beide wahr sind).
Beispiele:
- Die Adjunktion der wahren Aussage und der falschen Aussage ist die wahre Aussage .
- Die wahre Aussage: „Entweder ist die Erde ein Würfel oder die Sonne ist ein Stern“ ist eine Adjunktion der falschen Aussage: „Die Erde ist ein Würfel“ und der wahren Aussage: „Die Sonne ist ein Stern“.
Die Implikation
Verknüpft man zwei Aussagen und durch das Wort „dann“, so entsteht die Implikation der Aussagen und , symbolisch mit bezeichnet.
Die Implikation ist wahr, wenn beide Aussagen und wahr sind oder wenn die erste Aussage falsch ist.[1] Formal erhält man eine identische Wahrheitstafel, wenn man die Implikation bildet.[2][3]
Beispiele:
- Die Aussage „Wenn ist, dann ist “ ist wahr, obwohl sie eine Implikation zweier falscher (Teil-)Aussagen ist.
- Die Implikation der wahren Aussage „Die Lichtgeschwindigkeit beträgt annähernd “ und der falschen Aussage „Die Schallgeschwindigkeit ist größer als die Lichtgeschwindigkeit“ ist die falsche Aussage „Die Schallgeschwindigkeit beträgt mehr als „.
Äquivalenz zweier Aussagen
Verknüpft man zwei Aussagen und durch die Wortkombination „dann, und nur dann“, so entsteht die Äquivalenz der Aussagen und , symbolisch mit bezeichnet.
Die Äquivalenz zweier Teilaussagen ist nur wahr, wenn entweder beide Teilaussagen wahr oder beide falsch sind.[4]
Beispiele:
- Die wahre Aussage „Im rechtwinkligen Dreieck gilt der Höhensatz“ äquivalent verknüpft mit der falschen Aussage „Im rechtwinkligen Dreieck sind alle Seiten gleich lang“ ergibt die falsche Aussage „Im rechtwinkligen Dreieck sind dann und nur dann alle Seiten gleich lang, wenn der Höhensatz gilt“.
- Die Äquivalenzverknüpfung der falschen Aussage „Das Kilogramm ist eine Längeneinheit“ mit der wahren Aussage „Tausend Meter ergeben einen Kilometer“ ist die falsche Aussage „Das Kilogramm ist dann und nur dann eine Längeneinheit, wenn tausend Meter einen Kilometer ergeben“.
Kontravalenz zweier Aussagen
Verknüpft man zwei Aussagen und durch das Wort „entweder oder“ im ausschließenden Sinn, so entsteht die Kontravalenz der Aussagen und , mit mit bezeichnet.
Die Kontravalenz zweier Teilaussagen ist nur dann wahr, wenn genau eine der beiden (Teil-)Aussagen wahr ist. Damit ist sie formal, wie ihr Name bereits andeutet, mit der Negation der Äquivalenz identisch.
Beispiel:
- Verknüpft man die wahre Aussage „Der Zug fährt nach München“ kontravalent mit der falschen Aussage „Der Zug fährt nach Frankfurt“, so ergibt sich die wahre Aussage „Der Zug fährt entweder nach München oder nach Frankfurt“.
Regeln zu den Aussagenverknüpfungen
Zwischen den Aussagen beziehungsweise ihren Verknüpfungen sind folgende Äquivalenzen definiert, von denen einige eine formale Ähnlichkeit mit den Regeln für das Rechnen mit Zahlen haben:
- Kommutativgesetz:
- Assoziativgesetz:
- Distributivgesetz:
Hinzu kommen folgende Regeln, die bisweilen für Beweisverfahren sowie in der Informatik nützlich sind:
- Regeln von de Morgan:
- Absorptionsgesetz:
- Idempotenzgesetz:
- Komplementgesetz:
Dabei wird die Verknüpfung auch „Tautologie“ genannt; sie ist stets wahr.[5]
Variablen, Terme und Aussageformen¶
Eine Variable ist ein Symbol für ein beliebiges Element aus einer vorgegebenen Grundmenge. Darüber hinaus gelten für das Rechnen mit Variablen keine besonderen Regeln oder Gesetze.
Ein Term ist eine Bezeichnung zum einen für ein einzelnes mathematisches Objekt (beispielsweise ), zum anderen auch für eine Aneinanderreihung mehrerer Konstanten, Variablen, Klammern und Rechenoperatoren (beispielsweise ).[6] Terme enthalten allerdings kein Relationszeichen, sie sind somit weder wahr noch falsch.
Eine Aussageform enthält neben (mindestens) einer Variablen und (mindestens) einem Term stets ein Relationszeichen – beispielsweise oder . Um allerdings einer Aussageform auch einen Wahrheitswert zuordnen zu können, müssen zunächst alle auftretenden Variablen durch konkrete Elemente aus der Grundmenge ersetzt werden. Ebenso wie Aussagen lassen sich mehrere Aussageformen durch logische Verknüpfungen zu neuen Aussageformen kombinieren.
Die Abhängigkeit einer Aussageform von einer oder mehreren Variablen wird in der Form ausgedrückt. Dabei lassen sich Aussageformen in drei Arten unterteilen:
- Wird eine von einer Variablen abhängige Aussageform für jedes beliebige aus einer Grundmenge erfüllt, so bezeichnet man die Aussageform als allgemeingültig bezüglich .
- Existiert mindestens ein aus der Grundmenge , das die Aussageform erfüllt, so bezeichnet man die Aussageform als erfüllbar bezüglich .
- Existiert kein aus der Grundmenge , das die Aussageform erfüllt, so bezeichnet man die Aussageform als unerfüllbar bezüglich .
Aussageformen werden insbesondere in der Algebra als Gleichungen und Ungleichungen behandelt.
‚Für alle‘ und ‚Es gibt‘
Aussageformen können – neben dem Einsetzen von konkreten Objekten für die auftretenden Variablen – auch auf eine zweite Art und Weise zu Aussagen gemacht werden: Der Quantifizierung.
Eine allgemeine Aussageform wird zu einer „Existenz-Aussage“, wenn folgende Forderung erfüllt ist:
„Es existiert (mindestens) ein Element aus der Grundmenge „, für das die Aussageform wahr ist.“
Verkürzend kann eine Existenz-Aussage mit Hilfe des so genannten „Existenz-Quantors“ formuliert werden: Anstelle von „Es existiert (mindestens) ein “ kann auch kurz geschrieben werden.
Eine allgemeine Aussageform wird zu einer „Universal-Aussage“, wenn folgende Forderung erfüllt ist:
„Für jedes Element aus der Grundmenge “ ist die Aussageform wahr.“
Verkürzend kann eine Universal-Aussage mit Hilfe des so genannten „All-Quantors“ formuliert werden: Anstelle von „Für alle “ kann auch kurz geschrieben werden.
Während eine Existenz-Aussage wahr ist, wenn die zugrunde liegende Aussageform auch nur für ein konkretes erfüllt wird, so kann im umgekehrten Fall eine Universal-Aussage bereits durch den Existenz-Nachweis eines einzigen „Gegenbeispiels“ als falsch widerlegt werden.[7][8]
Direkte und indirekte Beweise¶
Die formalen Regeln der Logik können auch genutzt werden, um mittels bereits als wahr nachgewiesener Aussageformen Schlussfolgerungen auf neue Gesetzmäßigkeiten ziehen zu können. Auf diese Art gewonnene Lehrsätze (auch „Theoreme“ oder kurz „Sätze“ genannt) stellen das Grundgerüst der mathematischen Theorie dar.
Neben bereits bekannten Lehrsätzen werden auch so genannte Definitionen genutzt, um neue Sätze beweisen zu können. Beim Definieren wird ein Begriff durch die Festlegung wesentlicher, gemeinsamer Merkmale eindeutig bestimmt und von anderen Begriffen unterschieden. Definitionen sind weder wahr noch falsch, sie dienen vielmehr als Abkürzungen für unhandliche Formulierungen. Als Definitionszeichen für mathematische Terme verwendet man das Zeichen , eine Kurzschreibweise für „ist nach Definition gleich“.
Für die eigentlichen „Beweise“ sind u.a. folgende aussagenlogische Schlussregeln möglich:
- Schlussfolgerung aus einer Implikation:
- Gilt eine Aussage und ist die Implikation wahr, so ist auch eine wahre Aussage. Kurz formuliert ist somit der aussagenlogische Ausdruck allgemeingültig.
- Schlussfolgerung aus einer Negation:
- Der aussagenlogische Ausdruck ist allgemeingültig. Eine Aussage kann somit bewiesen werden, indem man die Negation der Aussage widerlegt.
Bei direkten Beweisen wird, ausgehend von gültigen Voraussetzungen und unter Verwendung von zulässigen Schlussregeln, nach endlich vielen Schritten direkt auf die Behauptung gefolgert. Bei indirekten Beweisen hingegen wird die Negation der Behauptung zu den Voraussetzungen hinzugenommen.
Die vollständige Induktion
Die vollständige Induktion ist ein häufig genutztes Verfahren zum direkten Beweisen einer Aussage. Die logische Schlussfolgerung beruht dabei auf drei Schritten:
- Mit dem „Induktionsanfang“ wird gezeigt, dass eine Aussageform für ein (beliebig wählbaren) Wert gültig ist.
- Die „Induktionsannahme“ besteht darin, dass die Aussageform für ein bestimmtes gültig ist.
- Mit dem „Induktionsschluss“, einem „Beweis im Beweis“, wird gezeigt, dass aus der Gültigkeit der Aussage auch die Gültigkeit der Aussage folgt, in Kurzschreibweise .
Beispiel:
Mit Hilfe der vollständigen Induktion soll bewiesen werden, dass für alle natürlichen Zahlen gilt:
- Induktionsanfang: Für gilt:
- Induktionsannahme: Für eine beliebige Zahl gilt die Aussageform
- Induktionsschluss:
Aus der Richtigkeit der Aussageform für folgt somit auch die Richtigkeit der Annahme für . Somit ist die Aussageform für alle wahr.
Anmerkungen:
[1] | Der letztere Fall wird bisweilen auch als „Ex falso quodlibet“ bezeichnet – aus einer falschen Annahme folgt Beliebiges. |
[2] | Die vorschnelle Annahme, dass aus auch folge, ist hingegen falsch. Ein anschauliches Beispiel hierfür ist die Aussage „Wenn es regnet, dann ist es bewölkt.“ Die Aussage würde lauten „Wenn es nicht regnet, dann ist es nicht bewölkt“, was offensichtlich falsch ist. Die Aussage „Wenn es nicht bewölkt ist, dann regnet es nicht“ ist hingegen richtig. Man sagt daher auch, dass notwendig für sei und dass hinreichend für sei. |
[3] | Es existiert sogar eine dritte Darstellungsweise der Implikation, und zwar . Dies lässt anhand der Wahrheitstabelle der Adjunktion überprüfen, indem man für die jeweils entgegengesetzten Wahrheitswerte annimmt und das Ergebnis der so gebildeten Adjunktion mit der Wahrheitstabelle der Implikation vergleicht. |
[4] | Formal erhält man eine identische Wahrheitstafel, wenn man die beiden Implikationen und bildet und durch eine Konjunktion miteinander verknüpft. Es gilt also: |
[5] | Das Gegenteil der Tautologie, die Aussage , heißt Kontradiktion; sie ist für jede beliebige Aussagen stets falsch. |
[6] | Setzt man für die in Termen auftretenden Variablen konkrete mathematische Objekte des Grundbereichs ein, so ergibt sich ein neuer mathematischer Ausdruck; beispielsweise ergibt der Term für den Wert . |
[7] | In Zusammenhang mit den Quantoren und
stellt der folgende Doppelpunkt : eine Kurzschreibweise für „so dass
gilt:“ beziehungsweise „gilt:“ dar. |
[8] | Auch kombinierte Quantifizierungs-Aussagen sind möglich, beispielsweise „Für jeden Menschen existiert ein Tag , so dass die Aussageform erfüllt ist: hat am Tag Geburtstag“. Als Kurzform kann für diese (wahre) Aussage geschrieben werden. |
Hinweis
Zu diesem Abschnitt gibt es Übungsaufgaben.