Was genau ist eine Logik?

36

Vielleicht liegt eine Entschuldigung vor, dass ich eine andere Frage zu den Voraussetzungen gestellt habe, aber ich war über die Ausgangspunkte verwirrt. Ich bin auf verschiedene Begriffe gestoßen, wie "Modale Logik", "Zeitliche Logik", "Logik erster Ordnung", "Logik zweiter Ordnung" und "Logik höherer Ordnung".

Was genau bedeutet "Logik" in diesem Zusammenhang? Wie definieren wir das Wort "Logik" konsequent?

Nachdem ich die ersten Seiten einiger Bücher durchgesehen habe, kann ich grob feststellen, dass eine "Logik eine Möglichkeit ist, zu entscheiden, was aus was folgt, und beim Entwerfen von Programmiersprachen von Bedeutung ist, da sie das Entwerfen von Programmen zum automatischen Schließen und Verstehen von Programmen diktiert und erleichtert. Ich möchte den zweiten Punkt etwas ausführlicher zu verstehen.

Kommen wir nun zu diesen Logiken.

Sind alle diese Logiken "zeitliche Logik", "modale Logik", "Logik erster Ordnung", "Logik höherer Ordnung" unabhängig voneinander oder müssen wir einige dieser Logiken verstehen, um einige andere in dieser Gruppe zu verstehen? Kurz gesagt, was sind die Voraussetzungen für sie? (Es wird toll sein, wenn ich auch Vorschläge für einige Materialien bekomme.)

PS: Vielen Dank für Ihre Freundlichkeit

Sheldon Kripke
quelle
17
Komischerweise würde eine solche Frage von jemandem namens Kripke gestellt werden . :-)
David Richerby
1
Ich muss sagen, dass Ihre Reaktion nicht seltsam ist. Ich war selbst ziemlich überrascht, als ich auf eine formale Definition von „Algebra“ stieß.
Diskrete Eidechse
2
@Discretelizard "Algebra" ist wahrscheinlich noch überraschender, da es absolut nichts mit dem zu tun hat, was sie in der High School Algebra nennen.
David Richerby
@DavidRicherby Habe ich auch gemacht, "lineare Algebra" ist nur eine Algebra.
Niklas Rosencrantz
1
@MartinRosenau Warum sollte das Ihrer Meinung nach ein Hindernis sein, um Fuzzy-Logik in einen allgemeinen Logikbegriff einzufügen?
Derek Elkins

Antworten:

39

Grundsätzlich besteht eine Logik aus zwei Dingen.

  • Syntax ist eine Reihe von Regeln, die festlegen, was eine Formel ist und was nicht.
  • Die Semantik ist ein Satz von Regeln, die bestimmen, welche Formeln "wahr" und welche "falsch" sind. Für einen Modelltheoretiker wird dies ausgedrückt, indem Formeln mit den mathematischen Strukturen in Beziehung gesetzt werden, in denen sie wahr sind. Für einen Beweistheoretiker entspricht die Wahrheit der Beweisbarkeit aus einer ausgewählten Menge von Axiomen mit einer ausgewählten Menge von Beweisregeln (Techniken).

Der Unterschied zwischen verschiedenen Logiken liegt am einfachsten in der Wahl der Syntax und der Semantik. Die meisten Logiken sind Erweiterungen der Aussagenlogik oder der Logik erster Ordnung . In gewisser Weise können Sie diese Erweiterungen als "Hinzufügen weiterer Funktionen" zur Logik ansehen. Beispielsweise befassen sich zeitliche Logiken mit Wahrheiten, die sich im Laufe der Zeit ändern können.

φttφt

Da so ziemlich alle Logiken auf Aussagenlogik und Logik erster Ordnung basieren, würde ich empfehlen, diese zuerst zu lernen.

David Richerby
quelle
2
Als Informatiker fand ich die Verbindung zur Typentheorie auch sehr nützlich, um Logik zu lernen. Ein Typensystem kann als alternative Darstellung einer äquivalenten Logik über die Howard-Curry-Korrespondenz betrachtet werden . Ich empfehle Pierces Buch, um loszulegen.
Phs
1
In der Logik steckt mehr als nur Formeln in der Syntax, und die Semantik ist mehr als die bloße Bestimmung der Wahrheit.
Andrej Bauer
Eine formale Perspektive, die in etwa der in dieser Antwort genannten Sichtweise entspricht und versucht, eine einheitliche Definition zu liefern (und die sich mit Fragen der Informatik befasst), ist die Theorie der Institutionen .
Derek Elkins
Nicht so zufällig werden Institutionen in einem Artikel mit dem Titel Was ist eine Logik?
Derek Elkins
@phs Wow ... Ich weiß nicht, wie ich so weit gekommen bin, aber dies ist das erste Mal, dass ich mir überlegt habe, dass das Currying einer Funktion ein Hinweis auf etwas anderes als das Gewürz sein könnte.
Cort Ammon
21

Während Bereiche wie Informatik, Mathematik und Physik relativ gut organisiert sind, hat die Logik eine chaotische Geschichte. Die Organisation ist sehr verwirrend, daher denke ich, dass es wichtig ist, etwas Geschichte zu lesen, um die dichte Struktur des Feldes zu verstehen.

Der Weg, den Sie wählen sollten, hängt von Ihrem Hintergrund und Ihren Zielen ab .

Was ist eine Logik?

  1. Die traditionelle Sichtweise besagt, dass eine Logik ein formales System mit einer formalen Sprache (Syntax), einer Semantik (externe Bedeutung, denke an Interpreter von Programmen) und einem Satz von Regeln ist, um Aussagen von anderen abzuleiten (denke an die Regeln von Kürzungen von Programmen). Eine Logik wird lediglich als bloßes mathematisches Objekt angesehen.

  2. Die moderne Sichtweise besagt, dass eine Logik durch den berühmten Curry-Howard-Isomorphismus ein kohärentes Typensystem ist (Beweise sind Programme und Typen sind Formeln). Genauer gesagt: Ein Inferenzsystem unterliegt dem Cut-Elimination-Theorem und dem Church-Rosser-Theorem / Confluence-Theorem, was impliziert, dass sich das zugrunde liegende Programmiersystem gut verhält.

  3. p,q

    • P,Q.P(x1,...,xn)Q.(x1,...,xn)
    • In der Logik zweiter Ordnung werden Variablen für Prädikate zu Funktionen erster Ordnung. Sie verhalten sich wie Funktionen, die Funktionen erster Ordnung als Argument verwenden. Zum Beispiel können wir Prädikate und Quantifizierung über Prädikaten haben.
    • Gleiche Überlegungen zu dritter Ordnung usw. Logik höherer Ordnung akzeptiert jede Bestellung. Stellen Sie sich Haskell und OCaml vor, deren Funktionen Funktionen von Funktionen von Funktionen usw. als Argument verwenden.
  4. Im Allgemeinen besteht kein Konsens darüber, was eine Logik wirklich ist. Einige Philosophen verwenden Systeme, denen kein kohärentes Programmiersystem zugrunde liegt. Eigentlich würde ich sagen, dass jedes Feld, das Logik verwendet, eine eigene Vorstellung von Logik hat. Und den meisten Mathematikern ist es wahrscheinlich egal, was eine Logik ist.

Die Struktur des Feldes

Die Geschichte von Logic ist zu groß, deshalb werde ich nur die Struktur des Feldes angeben. Das Feld der formalen Logik ist unterteilt in: den philosophischen, mathematischen und rechnerischen Gebrauch. Die formale Logik beginnt im 19. und 20. Jahrhundert.

  • Sie sollten zuerst Aussagenlogik und Logik erster Ordnung studieren . Sie sind die Standard. Sie wurden geschaffen, um der alten Logik der Zeit des antiken Griechenlands einen formalen / mathematischen Bericht zu geben.

    • Modelltheorie (Semantik), Studium mathematischer Strukturen aus der Perspektive der Logik
    • Beweistheorie (Syntax) studiert unabhängig Beweise als mathematisches Objekt.
  • Logik zweiter Ordnung ist eine Erweiterung der Logik erster Ordnung, die eine Erweiterung der Aussagenlogik ist. Es ist besonders interessant, weil Arithmetik in der zweiten Ordnung "lebt" (Prädikate auf Prädikate mit Induktion). Ebenso lebt die Topologie in der "dritten Ordnung" (Prädikate auf Mengen, die als Prädikate selbst angesehen werden können).

  • Dann kam LEJ Brouwer, der die Logik in zwei Teile teilte:

    • EINEIN¬EIN
    • Intuitionistische Logik ist eine Art Logik, die das ausgeschlossene mittlere und alle äquivalenten Gesetze ablehnt (aus technischen und philosophischen Gründen werde ich dies hier nicht erklären).
  • In anderen Zusammenhängen interessierten sich Philosophen für formale Logik und dachten, sie könne philosophische Fragen beantworten (analytische Philosophie). Sie stellten ihre eigenen unabhängigen logischen Systeme her (parakonsistente Logik, Relevanzlogik und modale Logik wie deontische Logik, zeitliche Logik, epistemische Logik, ...). Modale Logik funktioniert nicht mit Wahrheit, sondern mit Modalitäten wie Möglichkeit, Notwendigkeit, Zeit, Wissen. Sie sind alle unabhängig von der obigen Logik.

  • λ

  • Informatiker wollten die Lautstärke von Systemen auf formale Weise verifizieren und beweisen, und es scheint, dass modale Logik relevant ist. Heute verwenden sie zeitliche und modale Logiken, um auf Systemen zu argumentieren (siehe: formale Methoden, Modellprüfung). Systeme werden beispielsweise durch die Automatentheorie modelliert und mit logischen Werkzeugen verifiziert. Es führte zu Linear Temporal Logic (LTL) und Computational Tree Logic (CTL) .

  • Aus der gleichen Motivation heraus wollten Informatiker die Solidität überprüfen und Eigenschaften von Programmen nachweisen. Deshalb haben wir die Hoare-Logik für imperative Programme und allgemeiner die Trennungslogik erfunden .

  • Durch das Studium des Curry-Howard-Isomorphismus entstand eine neue Logik: Lineare Logik, die strukturelle Regeln (Schwächung und Kontraktion) einschränkt, die als Löschung und Vervielfältigung in Beweisen und Programmen gelten. Die potentielle Unendlichkeit der Wahrheit wird aufgeklärt. Es scheint, dass diese Logik eine Verallgemeinerung der klassischen und intuitionistischen Logik ist und eine völlig neue Konzeption der Logik auf der Grundlage von Berechnungen und eines prozeduralen Paradigmas liefert. Es wird hauptsächlich von Informatikern studiert.

  • Die lineare Logik kommt auch von der sogenannten Substrukturlogik, die strukturelle Regeln der Logik ablehnt. Relevante Logik und Affine Logik sind Beispiele für solche Systeme.

Zusammenfassung und Pfadauswahl

  • Jede Logik kann sein: Aussagenlogik, erste Ordnung, zweite Ordnung, dritte Ordnung, ..., höhere Ordnung (jede Erweiterung der vorhergehenden).

  • Wir können Regeln hinzufügen oder entfernen, um Varianten bestehender Systeme zu erstellen:

    • Ausgeschlossen-Mitte entfernen: Intuitionistische Logik
    • Modalitäten hinzufügen: Modal Logics
    • Beschränken Sie Widerspruch und Schwächung: lineare Logik
    • Kontraktion entfernen: Logik affinieren
    • Schwächung beseitigen: relevante Logik
    • Negation anders behandeln: parakonsistente Logik
  • Lernen Sie zuerst Aussagenlogik und Logik erster Ordnung und:

    • Modelltheorie zweiter Ordnung, höhere Ordnung, wenn Sie sich für Mathematik interessieren
    • Beweistheorie, intuitionistische Logik, lineare Logik zweiter Ordnung, wenn Sie sich für die Grundlagen der Informatik interessieren
    • Modal Logics, Hoare Logics, Separation Logics, wenn Sie an der Überprüfung von Systemen und Programmen interessiert sind
    • modale Logik, nicht-klassische Logik im Allgemeinen, wenn Sie sich für Philosophie interessieren

Referenzen (Bücher)

Ich persönlich empfehle, Referenzen nach Möglichkeit zu mischen.

  • Mathematische Logik (Chiswell & Hodges) : Ein sehr kurzes und einfaches Buch für den Anfang.
  • Ein erster Kurs in Logik (Hedman) : Ein bisschen wie oben, aber mehr Details und Berechenbarkeit berücksichtigen.
  • Handbuch für praktische Logik und automatisiertes Schließen (Harrison) : Wenn Sie verstehen möchten, wie einige logikbezogene Konzepte in der Praxis implementiert werden. Mehr auf automatisiertes Denken ausgerichtet.
  • Logik in der Informatik (Huth & Ryan) : sehr klar und orientiert an Informatikern (Überprüfung von Programmen und Systemen, Hoare-Logik, praktische Anwendung der Modallogik, zeitliche Logik, Modellprüfung).
  • Einführung in die Beweislehre (Buss) : Eine Einführung in die Beweislehre. Es sollte besser sein, dies nach einer allgemeinen Logik zu lesen.

Referenzen (Wikipedia)

Boris E.
quelle
Nun, das ist sehr ... umfassend, würde ich sagen. Vielen Dank, dass Sie sich die Zeit genommen haben, dies zu schreiben!
Diskrete Eidechse
5
Das sieht sehr umfassend aus, aber ich würde Curry-Howard wirklich nicht als das zweite, was Sie über Logik sagen, an jemanden weitergeben, der gerade lernt, was es ist. Wenn Sie nicht gerade Typentheorie studieren, ist Curry-Howard nicht "die moderne Definition von Logik". Es ist nur etwas, was manche Leute mit Logik machen.
David Richerby
2
@DavidRicherby Ok. Ich verstehe, aber ich denke, Curry-Howard ist für Informatiker wichtig genug (auch, weil wir uns in cs.stackexchange befinden). Es ist nicht wirklich eine moderne Definition von Logik, aber ich denke, es ist für einige Informatiker. Was eine Logik wirklich ist, kann sowieso subjektiv sein. Ich weiß, dass es nicht immer eine gute Idee ist, das Originalplakat so vielen Dingen auszusetzen, aber ich erwarte nicht wirklich ein vollständiges Verständnis, sondern ein umfassendes Panorama der Zweige von Logic (ein bisschen voreingenommen von CS), die als eine Referenz, um zu wissen, welche Art von Logik existiert und wo sie verwendet wird.
Boris E.
Ich hatte den Eindruck , dass höhere Ordnung Logik in Haskell wäre Typ Betreiber , anstatt Funktionen , die Funktionen als Eingabe nehmen könnte.
Martin
@martin Hm ... Es war nur eine einfache Analogie, um die Idee des Mechanismus zu erfassen, aber es sollte nicht zu ernst genommen werden. Ich wollte die Idee der "höheren Ordnung" beschreiben und nicht genau die "Logik höherer Ordnung" (unter Berücksichtigung des Hintergrunds des ursprünglichen Posters).
Boris E.
0

Alle diese Logiken gehören zur mathematischen Logik .

Mathematische Logik wird häufig in die Bereiche Mengenlehre, Modelltheorie, Rekursionstheorie und Beweistheorie unterteilt. Diese Bereiche teilen grundlegende Ergebnisse zur Logik, insbesondere zur Logik erster Ordnung, und zur Definierbarkeit. In der Informatik (insbesondere in der ACM-Klassifikation) umfasst die mathematische Logik zusätzliche Themen, die in diesem Artikel nicht näher erläutert werden. siehe dazu Logik in der Informatik .

Außerdem kann dieser Artikel hilfreich sein , wenn Sie die Logik allgemein kennenlernen möchten .

Logik, die ursprünglich "das Wort" oder "was gesprochen wird" bedeutet, aber "Denken" oder "Vernunft" bedeutet, ist ein Thema, das sich mit den allgemeinsten Gesetzen der Wahrheit befasst, und wird nun allgemein als systematisches Studium angesehen der Form der gültigen Schlussfolgerung. Eine gültige Folgerung ist eine, bei der ein spezifisches logisches Unterstützungsverhältnis zwischen den Annahmen der Folgerung und ihrer Schlussfolgerung besteht.

Oh mein Gott
quelle
4
Hmm, ich bin mir nicht sicher, ob das hier sehr hilfreich ist. Würden Sie sagen, dass Davids Posten Ihren überholt? Wenn nein, warum? Versuchen Sie, das zu erweitern.
Diskrete Eidechse
@OmG: Können Sie eine Liste von Materialien empfehlen, aus denen Sie lernen können?
Sheldon Kripke