Formale Logik

Semantische Tableaus

Seit den 1980er Jahren hat eine andere Technik zur Bestimmung der Gültigkeit von Argumenten in PC oder LPC aufgrund ihrer einfachen Lernfähigkeit und ihrer einfachen Implementierung durch Computerprogramme an Popularität gewonnen. Ursprünglich vom niederländischen Logiker Evert W. Beth vorgeschlagen, wurde es vom amerikanischen Mathematiker und Logiker Raymond M. Smullyan umfassender entwickelt und veröffentlicht. Ausgehend von der Beobachtung, dass es unmöglich ist, dass die Prämissen eines gültigen Arguments wahr sind, während die Schlussfolgerung falsch ist, versucht diese Methode, die Prämissen so zu interpretieren (oder zu bewerten), dass sie alle gleichzeitig erfüllt sind und die Negation der Schlussfolgerung ist auch zufrieden. Ein Erfolg bei einer solchen Anstrengung würde zeigen, dass das Argument ungültig ist, während ein Versäumnis, eine solche Interpretation zu finden, zeigen würde, dass es gültig ist.

Die Konstruktion eines semantischen Tableaus läuft wie folgt ab: Drücken Sie die Prämissen und die Negation der Schlussfolgerung eines Arguments in PC aus, indem Sie nur Negation (∼) und Disjunktion (∨) als Satzverbindungen verwenden. Beseitigen Sie jedes Auftreten von zwei Negationszeichen in einer Sequenz (z. B. wird ∼∼∼∼∼a zu ∼a). Erstellen Sie nun ein Baumdiagramm, das nach unten verzweigt, sodass jede Disjunktion durch zwei Zweige ersetzt wird, einen für den linken und einen für den rechten. Die ursprüngliche Disjunktion ist wahr, wenn einer der Zweige wahr ist. Die Bezugnahme auf De Morgans Gesetze zeigt, dass eine Negation einer Disjunktion wahr ist, nur für den Fall, dass die Negationen beider Disjunkte wahr sind [dh ∼ (p ∨ q) ≡ (∼p · ∼q)]. Diese semantische Beobachtung führt zu der Regel, dass die Negation einer Disjunktion zu einem Zweig wird, der die Negation jeder Disjunktion enthält:

Betrachten Sie das folgende Argument:

Schreiben:

Streichen Sie nun die Disjunktion aus und bilden Sie zwei Zweige:

Nur wenn alle Sätze in mindestens einem Zweig wahr sind, ist es möglich, dass die ursprünglichen Prämissen wahr und die Schlussfolgerung falsch sind (gleichbedeutend mit der Negation der Schlussfolgerung). Wenn man die Linie in jedem Zweig nach oben bis zum oberen Rand des Baums verfolgt, stellt man fest, dass keine Bewertung von a im linken Zweig dazu führt, dass alle Sätze in diesem Zweig den Wert true erhalten (aufgrund des Vorhandenseins von a und ∼a).. In ähnlicher Weise macht es das Vorhandensein von b und ∼b im rechten Zweig unmöglich, dass eine Bewertung dazu führt, dass alle Sätze des Zweigs den Wert true erhalten. Dies sind alle möglichen Zweige; Daher ist es unmöglich, eine Situation zu finden, in der die Prämissen wahr und die Schlussfolgerung falsch sind. Das ursprüngliche Argument ist daher gültig.

Diese Technik kann erweitert werden, um mit anderen Konnektiven umzugehen:

Darüber hinaus müssen in LPC Regeln zum Instanziieren quantifizierter wffs eingeführt werden. Es ist klar, dass jeder Zweig, der sowohl (∀x) ϕx als auch ∼ϕy enthält, einer ist, in dem nicht alle Sätze in diesem Zweig gleichzeitig erfüllt werden können (unter der Annahme der ω-Konsistenz; siehe Metallogik). Wenn nicht alle Zweige gleichzeitig erfüllt werden können, ist das ursprüngliche Argument gültig.

Spezielle Systeme von LPC

Die oben erläuterte LPC kann modifiziert werden, indem der Bereich der WFFs auf verschiedene Weise eingeschränkt oder erweitert wird:

• 1. Teilsysteme von LPC. Einige der wichtigeren Systeme, die durch Einschränkung hergestellt werden, werden hier beschrieben:

  • Es kann erforderlich sein, dass jede Prädikatvariable monadisch ist und dennoch eine unendliche Anzahl von Einzel- und Prädikatvariablen zulässt. Die atomaren wffs sind dann einfach diejenigen, die aus einer Prädikatvariablen gefolgt von einer einzelnen Einzelvariablen bestehen. Ansonsten bleiben die Formationsregeln unverändert, und die Definition der Gültigkeit ist ebenfalls unverändert, obwohl sie auf offensichtliche Weise vereinfacht wird. Dieses System ist als monadische LPC bekannt. Es bietet eine Logik der Eigenschaften, aber nicht der Beziehungen. Ein wichtiges Merkmal dieses Systems ist, dass es entscheidbar ist. (Die Einführung einer einzigen dyadischen Prädikatvariablen würde das System jedoch unentscheidbar machen, und sogar das System, das nur eine einzige dyadische Prädikatvariable und überhaupt keine anderen Prädikatvariablen enthält, hat sich als unentscheidbar erwiesen.)

  • bEin noch einfacheres System kann gebildet werden, indem (1) verlangt wird, dass jede Prädikatvariable monadisch ist, (2) dass nur eine einzelne Einzelvariable (z. B. x) verwendet wird, (3) dass jedes Auftreten dieser Variablen gebunden wird und (1) 4) dass kein Quantifizierer im Rahmen eines anderen auftritt. Beispiele für wffs dieses Systems sind (∀x) [ϕx ⊃ (ψx · χx)] („Was auch immer ϕ ist, ist sowohl ψ als auch χ“); (∃x) (ϕx · ∼ψx) („Es gibt etwas, das ϕ ist, aber nicht ψ“); und (∀x) (ϕx ⊃ ψx) ⊃ (∃x) (ϕx · ψx) („Wenn was ϕ ist, ist ψ, dann ist etwas sowohl ϕ als auch ψ“). Die Notation für dieses System kann vereinfacht werden, indem x überall weggelassen wird und ∃ϕ für „Etwas ist ϕ“, ∀ (ϕ ϕ ψ) für „Was auch immer ϕ ist ψ“ usw. geschrieben wird. Obwohl dieses System selbst rudimentärer ist als das monadische LPC (von dem es ein Fragment ist), können die Formen einer Vielzahl von Schlussfolgerungen darin dargestellt werden. Es ist auch ein entscheidbares System, für das Entscheidungsverfahren elementarer Art gegeben werden können.

• 2.Erweiterungen von LPC. Ausgefeiltere Systeme, in denen ein breiteres Spektrum von Aussagen ausgedrückt werden kann, wurden konstruiert, indem der LPC neue Symbole verschiedener Typen hinzugefügt wurden. Die einfachsten dieser Ergänzungen sind:

  • a.Eine oder mehrere einzelne Konstanten (z. B. a, b,

    ): Diese Konstanten werden als Namen bestimmter Personen interpretiert. formal unterscheiden sie sich von einzelnen Variablen dadurch, dass sie nicht innerhalb von Quantifizierern auftreten können; zB ist (∀x) ein Quantifizierer, (∀a) jedoch nicht.

  • b.Eine oder mehrere Prädikatkonstanten (z. B. A, B,

    ), die jeweils einen bestimmten Grad haben und als Bezeichnung bestimmter Eigenschaften oder Beziehungen angesehen werden.

Eine weitere mögliche Ergänzung, die eine etwas ausführlichere Erklärung erfordert, besteht aus Symbolen, die für Funktionen stehen sollen. Der Begriff einer Funktion kann für die vorliegenden Zwecke wie folgt ausreichend erklärt werden. Es gibt eine bestimmte Funktion von n Argumenten (oder vom Grad n), wenn es eine Regel gibt, die ein eindeutiges Objekt (den Wert der Funktion genannt) angibt, wenn alle Argumente angegeben werden. Im Bereich der Menschen zum Beispiel ist „die Mutter von -“ eine monadische Funktion (eine Funktion eines Arguments), da es für jeden Menschen ein einzigartiges Individuum gibt, das seine Mutter ist; und im Bereich der natürlichen Zahlen (dh 0, 1, 2,

), "Die Summe von - und -" ist eine Funktion von zwei Argumenten, da es für jedes Paar natürlicher Zahlen eine natürliche Zahl gibt, die ihre Summe ist. Man kann sich vorstellen, dass ein Funktionssymbol aus anderen Namen (seinen Argumenten) einen Namen bildet. Wenn also x und y Zahlen benennen, benennt „die Summe von x und y“ auch eine Zahl, und dies gilt auch für andere Arten von Funktionen und Argumenten.

Damit Funktionen in LPC ausgedrückt werden können, kann Folgendes hinzugefügt werden:

• Eine oder mehrere Funktionsvariablen (z. B. f, g,

  ) oder eine oder mehrere Funktionskonstanten (z. B. F, G,

  ) oder beides, jeweils mit einem bestimmten Grad. Ersteres wird so interpretiert, dass es sich über Funktionen der angegebenen Grade erstreckt, und letzteres als Bezeichnung spezifischer Funktionen dieses Grades.

Wenn ein oder alle a - c zu LPC hinzugefügt werden, müssen die im ersten Absatz des Abschnitts über den unteren Prädikatenkalkül (siehe oben Der untere Prädikatenkalkül) aufgeführten Formationsregeln geändert werden, damit die neuen Symbole aufgenommen werden können wffs. Dies kann wie folgt erfolgen: Ein Term wird zuerst definiert als entweder (1) eine einzelne Variable oder (2) eine einzelne Konstante oder (3) ein beliebiger Ausdruck, der durch Präfixieren einer Funktionsvariablen oder Funktionskonstante vom Grad n zu n Termen gebildet wird (Diese Begriffe - die Argumente des Funktionssymbols - werden normalerweise durch Kommas getrennt und in Klammern eingeschlossen. Formationsregel 1 wird dann ersetzt durch:

• Ein Ausdruck, der aus einer Prädikatvariablen oder Prädikatkonstante des Grades n gefolgt von n Termen besteht, ist ein wff.

Die im Abschnitt über die Axiomatisierung von LPC angegebene axiomatische Basis (siehe oben Axiomatisierung von LPC) erfordert auch die folgende Modifikation: Im Axiomschema 2 darf jeder Term a ersetzen, wenn β gebildet wird, vorausgesetzt, dass keine Variable in der LPC frei ist Term wird in β gebunden. Die folgenden Beispiele veranschaulichen die Verwendung der oben genannten Ergänzungen zu LPC: Die Werte der einzelnen Variablen seien die natürlichen Zahlen. Lassen Sie die einzelnen Konstanten a und b für die Zahlen 2 bzw. 3 stehen; sei A Mittelwert "ist Primzahl"; und lassen Sie F die dyadische Funktion "die Summe von" darstellen. Dann drückt AF (a, b) den Satz „Die Summe von 2 und 3 ist Primzahl“ aus, und (∃x) AF (x, a) drückt den Satz „Es gibt eine Zahl, so dass die Summe davon und 2 Primzahl ist. ”

Die Einführung von Konstanten geht normalerweise mit der Hinzufügung spezieller Axiome zur axiomatischen Basis einher, die diese Konstanten enthalten, um Prinzipien auszudrücken, die für die von ihnen dargestellten Objekte, Eigenschaften, Beziehungen oder Funktionen gelten - obwohl sie keine Objekte, Eigenschaften enthalten, Beziehungen oder Funktionen im Allgemeinen. Es kann zum Beispiel entschieden werden, die Konstante A zu verwenden, um die dyadische Beziehung "ist größer als" darzustellen (so dass Axy "x ist größer als y" bedeutet und so weiter). Diese Beziehung ist im Gegensatz zu vielen anderen transitiv; dh wenn ein Objekt größer als ein zweites ist und dieses zweite wiederum größer als ein drittes ist, dann ist das erste größer als das dritte. Daher könnte das folgende spezielle Axiomschema hinzugefügt werden: Wenn t ₁, t ₂ und t ₃ beliebige Terme sind, dann ist (At ₁ t ₂ · At ₂ t ₃) ⊃ At ₁ t ₃ ein Axiom. Auf diese Weise können Systeme aufgebaut werden, um die logischen Strukturen verschiedener bestimmter Disziplinen auszudrücken. Der Bereich, in dem die meisten Arbeiten dieser Art ausgeführt wurden, ist der der Arithmetik mit natürlichen Zahlen.

PC und LPC werden manchmal zu einem einzigen System kombiniert. Dies kann am einfachsten erfolgen, indem der Liste der LPC-Grundelemente Satzvariablen hinzugefügt werden, eine Formationsregel hinzugefügt wird, die bewirkt, dass eine allein stehende Satzvariable eine wff ist, und "LPC" in Axiomschema 1 gelöscht wird. Dies ergibt als wffs solche Ausdrücke als (p ∨ q) ⊃ (∀x) ϕx und (∃x) [p ⊃ (∀y) ϕxy].

• 3.LPC-mit-Identität. Das Wort "ist" wird nicht immer auf die gleiche Weise verwendet. In einem Satz wie (1) „Sokrates ist stupsnasig“ bezeichnet der Ausdruck vor dem „Ist“ ein Individuum und der darauf folgende Ausdruck steht für eine Eigenschaft, die diesem Individuum zugeschrieben wird. Aber in einem Satz wie (2) "Sokrates ist der athenische Philosoph, der Hemlock getrunken hat", sind die Ausdrücke vor und nach dem "ist" beide Namen Individuen, und der Sinn des gesamten Satzes ist, dass das vom ersten benannte Individuum ist die gleiche Person wie die von der Sekunde benannte Person. Somit kann in 2 "ist" zu "ist das gleiche Individuum wie" erweitert werden, während dies in 1 nicht möglich ist. Wie in 2 verwendet, steht "ist" für eine dyadische Beziehung - nämlich Identität -, die der Satz zwischen den beiden Individuen zu halten behauptet. Ein Identitätssatz ist in diesem Zusammenhang so zu verstehen, dass er nicht mehr als dies behauptet; Insbesondere ist nicht zu behaupten, dass die beiden Namensausdrücke dieselbe Bedeutung haben. Ein viel diskutiertes Beispiel zur Veranschaulichung dieses letzten Punktes ist „Der Morgenstern ist der Abendstern.“ Es ist falsch, dass die Ausdrücke „der Morgenstern“ und „der Abendstern“ dasselbe bedeuten, aber es ist wahr, dass das Objekt, auf das sich das erstere bezieht, dasselbe ist wie das, auf das sich das letztere bezieht (der Planet Venus).

Um das Ausdrücken der Formen von Identitätssätzen zu ermöglichen, wird LPC eine dyadische Prädikatenkonstante hinzugefügt, für die die üblichste Notation = ist (geschrieben zwischen und nicht vor den Argumenten). Die beabsichtigte Interpretation von x = y ist, dass x dasselbe Individuum wie y ist und die bequemste Lesart "x ist identisch mit y" ist. Seine Negation ∼ (x = y) wird üblicherweise als x ≠ y abgekürzt. Zu der zuvor gegebenen Definition eines LPC-Modells (siehe oben Gültigkeit in LPC) wird nun die Regel hinzugefügt (die auf offensichtliche Weise mit der beabsichtigten Interpretation übereinstimmt), dass der Wert von x = y 1 sein soll, wenn dasselbe Mitglied von D wird sowohl x als auch y zugewiesen und ansonsten soll sein Wert 0 sein; Die Gültigkeit kann dann wie zuvor definiert werden. Die folgenden Ergänzungen (oder einige äquivalente) werden zur axiomatischen Basis für LPC vorgenommen: das Axiom x = x und das Axiomschema, wobei a und b einzelne Variablen sind und α und β wffs sind, die sich nur darin unterscheiden, bei eine oder mehrere Stellen, an denen α ein freies Vorkommen von a hat, β ein freies Vorkommen von b hat, (a = b) ⊃ (α ⊃ β) ist ein Axiom. Ein solches System ist als ein niedrigerer Prädikatenkalkül mit Identität bekannt; es kann natürlich auf die anderen oben in „Erweiterungen von LPC“ genannten Arten weiter erweitert werden. In diesem Fall kann jeder Begriff ein Argument von = sein.

Identität ist eine Äquivalenzbeziehung; dh es ist reflexiv, symmetrisch und transitiv. Seine Reflexivität wird direkt im Axiom x = x ausgedrückt, und Theoreme, die seine Symmetrie und Transitivität ausdrücken, können leicht aus der gegebenen Basis abgeleitet werden.

Bestimmte WFFs von LPC mit Identität drücken Aussagen über die Anzahl der Dinge aus, die eine bestimmte Eigenschaft besitzen. "Mindestens eine Sache ist ϕ" könnte natürlich bereits durch (∃x) ϕx ausgedrückt werden; "Mindestens zwei verschiedene (nicht identische) Dinge sind ϕ" kann nun ausgedrückt werden durch (∃x) (∃y) (ϕx · ϕy · x ≠ y); und die Sequenz kann auf offensichtliche Weise fortgesetzt werden. "Höchstens eine Sache ist ϕ" (dh "Keine zwei unterschiedlichen Dinge sind beide ϕ") kann durch die Negation des zuletzt erwähnten wff oder durch sein Äquivalent (∀x) (∀y) [(ϕx ·) ausgedrückt werden. ϕy) ⊃ x = y], und die Sequenz kann wieder leicht fortgesetzt werden. Eine Formel für „Genau eine Sache ist ϕ“ kann erhalten werden, indem die Formeln für „Mindestens eine Sache ist ϕ“ und „Höchstens eine Sache ist ϕ“ zusammengefügt werden. Ein einfacheres wff-Äquivalent zu dieser Konjunktion ist jedoch (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)], was bedeutet: "Es gibt etwas, das ϕ ist, und alles, was ϕ ist, ist das Ding." Der Satz „Genau zwei Dinge sind ϕ“ kann dargestellt werden durch (∃x) (∃y) {ϕx · ϕy · x ≠ y · (∀z) [ϕz ⊃ (z = x ∨ z = y)]}; dh "Es gibt zwei nicht identische Dinge, von denen jedes ϕ ist, und alles, was ϕ ist, ist das eine oder andere davon." Natürlich kann diese Sequenz auch erweitert werden, um für jede natürliche Zahl n eine Formel für „Genau n Dinge sind ϕ“ zu erhalten. Es ist zweckmäßig, die wff für „Genau eine Sache ist ϕ“ auf (∃! X) ϕx abzukürzen. Dieser spezielle Quantifizierer wird häufig als "E-Shriek x" vorgelesen.

Bestimmte Beschreibungen

Wenn eine bestimmte Eigenschaft ϕ zu einem und nur einem Objekt gehört, ist es zweckmäßig, einen Ausdruck zu haben, der dieses Objekt benennt. Eine gebräuchliche Notation für diesen Zweck ist (ιx) ϕx, die als "das, was ϕ ist" oder kurz als "das ϕ" gelesen werden kann. Im Allgemeinen steht (ιa) α für den einzelnen Wert von a, der α wahr macht, wenn a eine einzelne Variable und α eine beliebige wff ist. Ein Ausdruck der Form „das So und So“ wird als eindeutige Beschreibung bezeichnet; und (ιx), bekannt als Beschreibungsoperator, kann als Bildung eines Namens eines Individuums aus einer Satzform angesehen werden. (ιx) ist insofern analog zu einem Quantifizierer, als es, wenn es einem wff α vorangestellt wird, jedes freie Vorkommen von x in α bindet. Eine Neueinstellung gebundener Variablen ist ebenfalls zulässig. im einfachsten Fall können (ιx) ϕx und (ιy) ϕy jeweils einfach als „das ϕ“ gelesen werden.

In Bezug auf die Formationsregeln können bestimmte Beschreibungen in die LPC aufgenommen werden, indem Ausdrücke der Form (ιa) α als Begriffe gelten; Regel 1 'oben in "Extensions of LPC" erlaubt es ihnen dann, in Atomformeln (einschließlich Identitätsformeln) aufzutreten. "Das ϕ ist (dh hat die Eigenschaft) ψ" kann dann ausgedrückt werden als ψ (ιx) ϕx; "Y ist (dasselbe Individuum wie) das ϕ" als y = (ιx) ϕx; "Das ϕ ist (dasselbe Individuum wie) das ψ" als (ιx) ϕx = (ιy) ψy; und so weiter.

Die korrekte Analyse von Sätzen mit bestimmten Beschreibungen war Gegenstand erheblicher philosophischer Kontroversen. Ein weithin akzeptierter Bericht - im Wesentlichen der in Principia Mathematica vorgestellte und als Russells Beschreibungstheorie bekannte - besagt jedoch, dass „Das ϕ ist ψ“ so zu verstehen ist, dass genau eine Sache ϕ ist und diese Sache auch ψ. In diesem Fall kann es durch eine wff von LPC mit Identität ausgedrückt werden, die keine Beschreibungsoperatoren enthält, nämlich (1) (∃x) [ϕx · (∀y) (ϕy ⊃x = y) · ψx]. Analog wird "y ist das ϕ" als "y ist ϕ und nichts anderes ist ϕ" analysiert und daher durch (2) ϕy · (∀x) (ϕx ⊃ x = y) ausgedrückt. "Das ϕ ist das ψ" wird analysiert als "Genau eine Sache ist ϕ, genau eine Sache ist ψ, und was auch immer ϕ ist, ist ψ" und daher ausgedrückt durch (3) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)] · (∃x) [ψx · (∀y) (ψy ⊃ x = y)] · (∀x) (ϕx ⊃ ψx). ψ (ιx) ϕx, y = (ιx) ϕx und (ιx) ϕx = (ιy) ψy können dann als Abkürzungen für (1), (2) bzw. (3) angesehen werden; und durch Verallgemeinerung auf komplexere Fälle können alle wffs, die Beschreibungsoperatoren enthalten, als Abkürzungen für längere wffs angesehen werden, die dies nicht tun.

Die Analyse, die zu (1) als Formel für „Das ϕ ist ψ“ führt, führt zu dem folgenden Ergebnis für „Das ϕ ist nicht ψ“: (4) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ∼ψx]. Es ist wichtig zu beachten, dass (4) nicht die Negation von (1) ist; Diese Negation ist stattdessen (5) ∼ (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ψx]. Der Bedeutungsunterschied zwischen (4) und (5) liegt in der Tatsache, dass (4) nur dann wahr ist, wenn genau eine Sache ϕ ist und diese Sache nicht ψ ist, aber (5) sowohl in diesem Fall als auch in (5) wahr ist auch wenn nichts ϕ ist und wenn mehr als eine Sache ϕ ist. Die Vernachlässigung der Unterscheidung zwischen (4) und (5) kann zu ernsthaften Gedankenverwirrungen führen; In der gewöhnlichen Sprache ist häufig unklar, ob jemand, der leugnet, dass das ϕ ist, einräumt, dass genau eine Sache ist, aber leugnet, dass es ψ ist, oder leugnet, dass genau eine Sache ist.

Die grundlegende Behauptung von Russells Beschreibungstheorie ist, dass ein Satz, der eine bestimmte Beschreibung enthält, nicht als Behauptung über ein Objekt anzusehen ist, dessen Beschreibung ein Name ist, sondern als existenziell quantifizierte Behauptung, die eine bestimmte (ziemlich komplexe) Eigenschaft hat eine Instanz. Formal spiegelt sich dies in den oben beschriebenen Regeln zum Eliminieren von Beschreibungsoperatoren wider.