Mathematische Logik
Aufgabe der mathematischen Logik ist es ein Grundlage für die präzise Formulierung mathematischer Aussagen und Beweise zu schaffen.
Gewöhnlich wird die klassische Aussagenlogik mit den zwei Wahrheitswerten, "wahr" oder "falsch" verwendeteinen Drittes gibt es nicht (tertium non datur; Gesetz vom ausgeschlossenen Dritten). In der mehrwertigen Logik kann es zwischen "wahr" und "falsch" auch eine oder mehrere Zwischenwerte geben "teils..teils?.
Aussagen werden verknüpft durch Junktoren. Hierzu zählen die einstellige Verknüpfung "nicht?(\(neg\)?) und die zweistelligen Verknüpfungen "und" (\(wedge \)), "oder" (\(vee \)) und "wenn...dann" (?). Damit lassen sich aus gegebenen Aussagen neue Aussagen zusammensetzen und mit einer Wahrheitswertetafel auf ihren Wahrheitswert hin überprüfen. Man kann die Aussagelogik auch mit einer einzigen Verknüpfung aufbauen, den von Henry Maurice Sheffer und zuvor schon von Charles Sanders Peirce eingeführten Junktoren "nicht zugleich ... und "" (NAND oder |) oder "wedernoch" (NOR oder \(nabla\)).
| a | \(neg\) a |
| W | F |
| F | W |
Für die Negation gilt: Ist a wahr so ist \(neg\) a falsch und umgekehrt.
|
a |
b |
ab |
|
W |
W |
W |
|
W |
F |
F |
|
F |
W |
F |
|
F |
F |
F |
Die Aussage "a und b" (a \(wedge \) b) ist nur dann wahr, wenn a wahr ist und b wahr ist.
|
a |
b |
a \(vee \) b |
|
W |
W |
W |
|
W |
F |
W |
|
F |
W |
W |
|
F |
F |
F |
Die Aussage "a oder b" (a V b) ist nur dann falsch, wenn a falsch ist und b falsch ist.
|
a |
b |
ab |
|
W |
W |
W |
|
W |
F |
F |
|
F |
W |
W |
|
F |
F |
W |
Die Aussage "aus a folgt b" oder "wenn a dann b" (ab) ist nur dann falsch,wenn a wahr ist und b falsch.
Zusammenhang mit NAND und NOR:
| \(neg\) a | a|a | a\(nabla\)a |
| a \(vee \) b | (a|b)|(a|b) | (a\(nabla\)a)\(nabla\)(b\(nabla\)b) |
| a \(vee \) b | (a|a)|(b|b) | (a\(nabla\)b)\(nabla\)(a\(nabla\)b) |
| ab | a|(a|b) | (b\(nabla\)(a\(nabla\)b)) \(nabla\) (b\(nabla\)(a\(nabla\)b)) |
Durch Kombination dieser Verknüpfungen lassen sich weitere Sätze herleiten.
Da die Aussagelogik zum Formulieren mathematischer Sätze nicht ausreicht, wird sie zur Prädikatenlogik (erster Stufe) erweitert, bei der es zusätzlich Subjekte, Prädikate und Quantoren gibt. Auch diese kann selbst noch erweitert werden (höhere Stufen).
Logische Betrachtungen wurden erstmals von Aristoteles angestellt, man bezeichnet die klassische Logik des Schließens daher auch als aristotelische Logik. Diese wird aber nicht zur mathematischen Logik gerechnet, da sie deren formalen Ansprüchen noch nicht gerecht wird. Die eigentliche mathematische Logik beginnt erst Mitte des 19. Jahrhunderts mit den Arbeiten von George Boole und Augustus de Morgan und wird später vor allem durch Gottlob Frege (1879), Bertrand Russell und Alfred North Whitehead (1910) ausgebaut.
Das Ziel, die gesamte Mathematik auf eine widerspruchsfreie und vollständige logische Basis zu stellen, gelingt aber nicht. Kurt Gödel konnte 1931 zeigen, dass es in einem widerspruchsfreien, die Arithmetik umfassenden Axiomensystem stets Aussagen gibt, die sich mit den gebotenen Mittel des Systems weder beweisen noch wiederlegen lassen
(1. Gödelscher Unvollständigkeitssatz). Ferner benötigt man zum Nachweis der Widerspruchsfreiheit eines Axiomensystems selbst stets Mittel, die über das Axiomensystem hinaus gehen (2. Gödelscher Unvollständigkeitssatz).
Zur mathematischen Logik werden u.a. die folgenden Teilgebiete gezählt:
- Die Mengenlehre, in der die konkreten mathematischen Inhalte formalisiert werden, um neue Aussagen durch logische Schlüsse und bekannten Aussagen zu beweisen.
- Die Beweistheorie, die sich mit formalen Beweisen und logischen Deduktionen beschäftigt.
- Die Modelltheorie, die für gegebene Axiomensysteme konkrete Modelle konstruiert und damit deren Widerspruchsfreiheit garantiert.
- Die Rekursionstheorie, die die Berechenbarkeit von mathematischen Objekten auslotet, die algorithmische Lösbarkeit mathematischer Probleme.