Die Logik (griechisch: Denklehre) gilt als Wissenschaft von den Gesetzen und Formen des richtigen menschlichen Denkens. Die sog. traditionelle Logik ist die erste Stufe der Logik des abgeleiteten Wissens. Sie untersucht die allgemeinsten Gesetze der Logik wie die zur Identität, des Widerspruchs, des ausgeschlossenen Dritten, des hinreichenden Grundes, des logischen Schließens, ohne deren Anerkennung ein folgerichtiges Denken nicht möglich ist. Gegenstand der Logik sind Aussagen bzw. Aussageformen und deren Beziehungen zueinander, soweit diese für Wahrheit oder Falschheit relevant sind.

Der eigentliche Schöpfer der Logik als Wissenschaft ist Aristoteles. Er betrachtete als erster Aussageformen wie z. B. „alle A sind B“, wobei A und B als Variablen für Objekte anzusehen sind, kombinierte sie miteinander und zog aus der Gestalt der zusammengesetzten Aussageformen weitere Schlußfolgerungen. Die Aristotelesche Logik blieb bis in das 19. Jh. nahezu unverändert. Mit der fortschreitenden Industrialisierung und der Weiterentwicklung der Naturwissenschaften, insbesondere der Mathematik im 19. Jh., waren strengere Maßstäbe an die Korrektheit des gefundenen Wissens erforderlich. Die moderne Entwicklung der

Logik beginnt im 19. Jh. mit ihrer „Mathematisierung“. Wichtige Vorarbeiten hierzu wurden von G.W. Leibniz, B. Bolzano, G. Boole, A. De Morgan und vor allem von G. Frege geleistet. Auslösend für die moderne Entwicklung der Logik war die enorme Ausweitung naturwissenschaftlichen Denkens und die dadurch schärfer hervorgetretenen unbewältigten Probleme in der Grundlegung der Mathematik. Dabei zutage gekommene Widersprüche erforderten eine gründliche Analyse der verwendeten mathematischen Ausdrucksmittel und Methoden. Die in diesem Zusammenhang gewonnenen Erkenntnisse über die Rolle der Sprache waren nicht nur für die Fundierung der Mathematik bedeutungsvoll, sondern gleichermaßen förderlich für die Entwicklung „intelligenter“ Maschinen. Erst die präzise mathematische Analyse des logischen Schließens erbrachte das notwendige Verständnis der Denkvorgänge, das für den Bau von leistungsfähigen Computern erforderlich ist. Wesentliche Impulse bei der Entwicklung der Logik zu einer mathematischen Disziplin (mathematische Logik) kamen aus der Mathematik selbst.

Nachdem G. Cantor sein Konzept der (naiven) Mengenlehre entwickelt hatte (wonach Mengen Zusammenfassungen wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens sind), das sich hervorragend zur Grundlegung der Mathematik eignete, wurden um die Jahrhundertwende 1900 eine Reihe von Widersprüchlichkeiten in diesem Konzept entdeckt. Die auffälligste war die von B. Russel gefundene, die hier skizziert werden soll:

Wenn die Cantorsche Mengendefinition korrekt ist, dann ließe sich die Menge M aller Mengen X bilden, die sich selbst nicht als Element enthalten; formal ausgedrückt bedeutet dies: ∀X(X ∈ M) ↔ (X ∉ X). Da M selbst eine Menge ist, kann X = M gewählt werden. Dies impliziert: M ∈ M ↔ M ∉ M, was offensichtlich einen Widerspruch darstellt. Damit war zunächst die Cantorsche Mengenlehre gescheitert und das Fundament der Mathematik ins Wanken geraten. In diesem Zusammenhang wird auch von einer Grundlagenkrise der Mathematik gesprochen. Dies löste umfangreiche grundlagentheoretische Analysen innerhalb der Mathematik aus, die zu einer strengen Überprüfung der logischen und mathematischen Hilfsmittel führten. Hieraus entstanden verschiedenartige neue Ansätze für Logik-Kalküle mit streng formalisierten Sprachen, mit möglichst schwachen logischen Voraussetzungen (logische Axiome) und präzise formulierten zulässigen Beweisregeln.

Die schon bis zu einem gewissen Grad entwickelte klassische Aussagen- und Prädikatenlogik ließ unendliche Mengen als existierende mathematische Objekte zu und akzeptierte das Gesetz vom ausgeschlossenen Dritten (≔ jede Aussage ist wahr oder falsch). Spätestens nachdem K. Gödel 1930 seinen Vollständigkeitssatz für die Prädikatenlogik veröffentlicht hatte (Gödelscher Vollständigkeitssatz), war gesichert, daß der Prädikatenkalkül als logisches System eine hervorragende Grundlage für Untersuchungen in der klassischen Mathematik darstellt, die ebenfalls unendliche Mengen als existierende mathematische Objekte und indirekte Beweise, die auf dem Gesetz vom ausgeschlossenen Dritten beruhen, akzeptiert.

In der intuitionistischen Logik hingegen, die von L.E.G Brower initiiert wurde, werden als existierende Objekte zunächst nur beliebig große natürliche Zahlen anerkannt (z. B. schon die Menge der natürlichen Zahlen selbst ist nicht ad hoc existent). Ein mathematisches Objekt wird in dieser Theorie nur dann als existent angesehen, wenn es sich mit finiten Mitteln aus den schon zuvor vorhandenen Objekten konstruieren oder sich seine Existenz beweisen läßt, wobei die Beweismittel gegenüber der klassischen Logik erheblich eingeschränkt sind. Indirekte Beweise, die auf dem Gesetz vom ausgeschlossenen Dritten basieren, sind z. B. ausgeschlossen. Die in diesen eingeschränkten Rahmen entwickelte Mathematik wird auch konstruktive oder intuitionistische Mathematik genannt. Der positive Beitrag des Intuitionismus zur Grundlagenuntersuchung der Mathematik ist vor allem darin zu sehen, daß eine strenge Abgrenzung der konstruktiven von der nicht-konstruktiven Mathematik erfolgte. Wirklich rechnen (d. h. Probleme algorithmisch „mit Hand“ oder mit Computern bearbeiten) kann man nur im Rahmen der konstruktiven Mathematik.

Wer das Gesetz vom ausgeschlossenen Dritten oder das Prinzip der Zweiwertigkeit (Aussagenkalkül) ablehnt, kommt zu einer anderen Art Logik, in der es mehr als zwei Wahrheitswerte gibt. In diesem Zusammenhang ist die Modallogik, die mehrwertige Logik und in der neueren Zeit die Fuzzy-Logik entstanden.

Aus dem Bedürfnis heraus, den Berechenbarkeitsbegriff zu definieren bzw. zu präzisieren, entstanden unter anderem die rekursiven Funktionen, die aufgrund ihrer Definition offenbar im naiven Sinne berechenbar sind. Da so grundlegende Begriffe wie „berechenbar, entscheidbar, konstruierbar,…“ eng mit dem Begriff der rekursiven Funktion verbunden sind, und viele Probleme einer algorithmischen Lösung bedurften, entstand hieraus im Rahmen der mathematischen Logik eine neue Theorie, die Rekursionstheorie. Sie befaßt sich im weitesten Sinne mit den Eigenschaften der rekursiven Funktionen. Obwohl vielfältige Anstrengungen unternommen worden sind, den Berechenbarkeitsbegriff vollständig zu charakterisieren, ist dies bisher nicht im vollem Umfang gelungen. Klar ist nur, daß alle rekursiven Funktionen berechenbar sind, die Umkehrung konnte nur hypothetisch angenommen werden. Die Churchsche Hypothese, die heute allgemein anerkannt wird, besagt, daß die berechenbaren Funktionen genau die rekursiven sind. Unter dieser zwar unbewiesenen, aber doch sehr vernünftig erscheinenden Hypothese werden häufig weitere Untersuchungen angestellt.

David Hilbert versuchte mit seinem Programm einer finiten Begründung der klassischen Mathematik einen anderen Weg bei der Überwindung der Grundlagenkrise zu gehen. Er setzte sich entschieden für die Beibehaltung der Cantorschen Ideen zur Mengenlehre, jedoch unter modifizierten Bedingungen, ein. Ihm schwebte eine umfassende Axiomatisierung der Geometrie, der Zahlentheorie, der Analysis, der Cantorschen Mengenlehre und weiterer grundlegender Teilgebiete der Mathematik vor. Aus dieser Grundidee, die gewisse Axiome an den Anfang stellt, die Beweismittel präzisiert und nur auf dieser Basis Schlußfolgerungen zuläßt, entstand eine neue Richtung in der mathematischen Logik, die Beweistheorie. Das Hilbertsche Programm, die Mathematik in wesentlichen Teilen vollständig zu axiomatisieren, erwies sich mit dem Erscheinen der Gödelschen Resultate zur Unvollständigkeit der Arithmetik als nicht realistisch. Der Unvollständigkeitssatz besagt im wesentlichen:

Eine widerspruchsfreie und rekursiv axiomatisierbare Theorie T, in der die elementare Peanoarithmetik interpretiert werden kann, ist unvollständig.

Als Folgerung ergibt sich hieraus sofort die wichtige Erkenntnis: Ist L die Sprache der Arithmetik, ℕ = ⟨N, +, ·, <, 0, 1⟩ das Standardmodell der Arithmetik und T die Menge aller in ℕ gültigen Aussagen aus L, dann ist T offenbar vollständig. Folglich ist T nicht rekursiv axiomatisierbar. Anders ausgedrückt: Ist ∑ eine beliebige rekursive Teilmenge von T, dann gibt es stets eine Aussage ϕ in L, so daß weder ϕ noch ¬ϕ aus ∑ beweisbar sind. Jedes solche System ist also unvollständig und damit schon eine so grundlegende Theorie wie die Arithmetik nicht axiomatisierbar. Analoge Überlegungen gelten erst recht für jedes axiomatische System der Mengenlehre, in dem die Arithmetik interpretierbar ist.

Die von Hilbert entwickelten Methoden der Beweistheorie leben aber fort und haben ihren festen Platz in der Mathematik. Ebenso gewann die axiomatische Methode an Einfluß. Beispielsweise wurde die Mengenlehre mit Erfolg axiomatisch begründet. Die aus heutiger Sicht am besten geeignete Axiomatisierung geht auf Zermelo und Fraenkel zurück, so daß sie häufig ZF-Mengenlehre genannt wird. Mit Hilfe verschiedenartiger Mengen-Modelle wurden Abhängigkeits- und Unabhängigkeitsuntersuchungen vorgenommen. Die bekanntesten Resultate in diesem Zusammenhang sind die Ergebnisse von Gödel und P.J. Cohen zur Unabhängigkeit des Auswahlaxioms und der Kontinuumhypothese von den ZF-Axiomen.

Im Zuge der Axiomatisierung weiterer mathematischer Theorien und der Ausnutzung von Methoden und Ergebnissen der klassischen Prädikatenlogik (elementare Sprachen) zur Untersuchung von Klassen algebraischer Strukturen (auch Modelle genannt) entstand die Modelltheorie, die manchmal auf die verkürzende Formel: Modelltheorie = Algebra + Logik gebracht wird. Dies stimmte allerdings nur in der Anfangsphase der modelltheoretischen Entwicklung. Heute bearbeitet die Modelltheorie mit den Hilfsmitteln der mathematischen Logik Fragestellungen aus praktisch allen Teilgebieten der Mathematik. Klassische Problemstellungen der Modelltheorie sind z. B.:

1. Logik-Kalküle im weitesten Sinne. Hierzu gehören insbesondere die Aussagen- und Prädikaten- logik, die intuitionistische Logik, mehrwertige Logiken, die Beweistheorie, auch Logiken für erweiterte Sprachen,….
2. Modelltheorie.
3. Axiomatische Mengenlehre.
4. Rekursionstheorie.

[2] Börger, E.: Berechenbarkeit, Komplexität, Logik. Vieweg Braunschweig, 1985.

[3] Chang, C.C.; Keisler, H.J.: Model Theory. Studies in Logic and the Foundations of Mathematics, Vol. 73. North-Holland Amsterdam, 1973.

[4] Curry, H.B.; Feys R.: Combinatory Logic. North-Holland Amsterdam, 1968.

[5] Frege, G.: Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Louis Nebert Halle, 1879.

[6] Gottwald, S.: Fuzzy Sets and Fuzzy Logic, Foundations of Application – from a Mathematical Point of View. Vieweg Braunschweig/Wiesbaden, 1993.

[7] Heyting, A.: Intuitionism. An Introduction. North-Holland Amsterdam, 1961.

[8] Hilbert, D.; Bernays, P.: Grundlagen der Mathematik I,II. Springer-Verlag Berlin/Heidelberg, 1934/1939.

[9] Keisler, H.J.: Model Theory for Infinitary Logic. North- Holland Amsterdam, 1971.

[10] Kunen, K.: Set Theory. An Introduction to Independence Proofs. North-Holland Amsterdam, 1980.

[11] Robinson, A.: Non-Standard Analysis. North-Holland Amsterdam, 1966.

[12] Rodgers, Jr.H.: Theory of Recursive Functions and Effective Computability. New York, 1967.

[13] Rosser, J.B.; Turquette, A.R.: Manyvalued Logics. Amsterdam, 1952.

[14] Schütte, K.: Vollständige Systeme modaler und intuitionistischer Logic. Berlin – Heidelberg – New York, 1968.

[15] Schütte, K.: Beweistheorie. Springer Berlin, 1960.

[16] Shelah, S.: Classification Theory (and the Number of Non-Isomorphic Models). Studies in Logic and the Foundations of Mathematics 92, North-Holland Amsterdam, 1990.

[17] Shoenfield, J.R.: Mathematical Logic. Addison Wesley Reading (Massachusetts)/Mendo Park (California)/London, 1967.