Logik erster Ordnung

Logik erster Ordnung-auch bekannt als Prädikatlogik, Quantifikationslogik, und Prädikat erster Ordnung- ist eine Sammlung von formelle Systeme benutzt in Mathematik, Philosophie, Linguistik, und Informatik. Logik erster Ordnung verwendet Quantifizierte Variablen über nicht logische Objekte und ermöglicht die Verwendung von Sätzen, die Variablen enthalten, sodass man Ausdrücke in der Form "dort existiert x existiert x, so dass x Sokrates ist und x ist a Mann ", wo" es gibt" ist während x ist eine Variable.^[1] Dies unterscheidet es von Aussagelogik, was keine Quantifizierer verwendet oder Beziehungen;^[2] In diesem Sinne ist die Propositionslogik die Grundlage der Logik erster Ordnung.

Eine Theorie zu einem Thema ist normalerweise eine Logik erster Ordnung zusammen mit einem angegebenen Diskursbereich (über die die quantifizierten Variablen reichen), endlich viele Funktionen von dieser Domäne zu sich selbst, endlich viele Prädikate Auf dieser Domäne definiert und eine Reihe von Axiomen, von denen angenommen wird, dass sie sich über sie halten. Manchmal wird "Theorie" in formalerem Sinne als nur eine Reihe von Sätzen in Logik erster Ordnung verstanden.

Das Adjektiv "erster Ordnung" unterscheidet Logik erster Ordnung von Logik höherer Ordnung, in denen Prädikate mit Prädikaten oder Funktionen als Argumente oder in deren Quantifizierung über Prädikate oder Funktionen oder beides zulässig sind.^{[3]: 56} In Theorien erster Ordnung werden Prädikate häufig mit Sätzen verbunden. In tolierten theorien höherer Ordnung können Prädikate als Sets von Sätzen interpretiert werden.

Es gibt viele deduktive Systeme Für Logik erster Ordnung, die beide sind Klang (d. H. Alle nachweisbaren Aussagen sind in allen Modellen der Fall) und Komplett (d. H. Alle Aussagen, die in allen Modellen wahr sind, sind nachweisbar). Obwohl die logische Konsequenz Beziehung ist nur halbkassbarEs wurden viel Fortschritte in erzielt automatisierter Theorem beweisen in Logik erster Ordnung. Logik erster Ordnung erfüllt auch mehrere metallogisch Theoreme, die es für die Analyse in der Analyse zugänglich machen Beweistheorie, so wie die Löwenheim -Skolem -Theorem und die Kompaktheitstheorem.

Logik erster Ordnung ist der Standard für die Formalisierung der Mathematik in Axiomeund wird in der untersucht Grundlagen der Mathematik.Peano -Arithmetik und Zermelo -Fraenkel -Set -Theorie sind Axiomatisierungen von Zahlentheorie und MengenlehreIn Logik erster Ordnung. Keine Theorie erster Ordnung hat jedoch die Stärke, eine Struktur mit einer unendlichen Domäne einzigartig zu beschreiben, wie die natürliche Zahlen oder der echte Linie. Axiomsysteme, die diese beiden Strukturen vollständig beschreiben (dh,, Kategorisch Axiomsysteme) können in stärkeren Logik wie z. Logik zweiter Ordnung.

Die Grundlagen der Logik erster Ordnung wurden unabhängig voneinander entwickelt Gottlob Frege und Charles Sanders Peirce.^[4] Für eine Geschichte der Logik erster Ordnung und wie es dazu kam, formale Logik zu dominieren, siehe José Ferreirós (2001).

Einführung

Während Aussagelogik befasst sich mit einfachen deklarativen Aussagen, logisch erster Ordnung zusätzlich abdeckt Prädikate und Quantifizierung.

Ein Prädikat nimmt eine Entität oder Entitäten in der Diskursbereich und bewertet Stimmt oder FALSCH. Betrachten Sie die beiden Sätze "SOCRATES IS EIN PHILOSOPHER" und "Platon ist ein Philosoph". Im AussagelogikDiese Sätze werden als nicht verwandt angesehen und könnten beispielsweise von Variablen wie bezeichnet werden, z. p und q. Das Prädikat "ist ein Philosoph" tritt in beiden Sätzen auf, die eine gemeinsame Struktur von "haben"a ist ein Philosoph ". Die Variable a wird im ersten Satz als "Sokrates" instanziiert und im zweiten Satz als "Platon" instanziiert. Während die Logik erster Ordnung die Verwendung von Prädikaten ermöglicht, wie z. B. "ist ein Philosoph" in diesem Beispiel, tut dies die Propositionslogik nicht.^[5]

Beziehungen zwischen Prädikaten können verwendet werden Logische Verbindungen. Betrachten Sie zum Beispiel die Formel erster Ordnung ", wenn a ist dann ein Philosoph a ist ein Gelehrter ". Diese Formel ist a bedingt Aussage mit "a ist ein Philosoph "als Hypothese und"a ist ein Gelehrter "als Schlussfolgerung. Die Wahrheit dieser Formel hängt davon ab, von welchem ​​Objekt bezeichnet wird aund über die Interpretationen der Prädikate "ist ein Philosoph" und "ist ein Gelehrter".

Quantifizierer können in einer Formel auf Variablen angewendet werden. Die Variable a in der vorherigen Formel kann beispielsweise für jeden allgemein quantifiziert werden a, wenn a ist dann ein Philosoph a ist ein Gelehrter ". Die Universeller Quantifizierer "Für jeden" in diesem Satz drückt die Idee aus, dass der Anspruch "wenn a ist dann ein Philosoph a ist ein Gelehrter "hält" für alle Entscheidungen von a.

Das Negation des Satzes "für jeden a, wenn a ist dann ein Philosoph a ist ein Gelehrter "ist logisch äquivalent dem Satz", es gibt es a so dass a ist ein Philosoph und a ist kein Gelehrter ". Die Existenzieller Quantifizierer "Es gibt existiert" drückt die Idee aus, dass die Behauptung "a ist ein Philosoph und a ist kein Gelehrter "hält für" etwas Wahl von a.

Die Prädikate "ist ein Philosoph" und "ist ein Gelehrter", jeweils eine einzelne Variable. Im Allgemeinen können Prädikate mehrere Variablen einnehmen. Im Satz erster Ordnung "Sokrates ist der Lehrer von Platon", ist das Prädikat "der Lehrer von" nimmt zwei Variablen.

Eine Interpretation (oder ein Modell) einer Formel erster Ordnung gibt an, was jedes Prädikat bedeutet, und die Entitäten, die die Variablen instanziieren können. Diese Entitäten bilden die Diskursbereich oder Universum, das normalerweise ein nicht leeres Set sein muss. Zum Beispiel in einer Interpretation mit dem Diskursbereich, bestehend aus allen Menschen und dem Prädikat "ist ein Philosoph, der als" der Autor des Autors verstanden wurde Republik", der Satz" es gibt es a so dass a ist ein Philosoph "wird als wahr angesehen, wie von Platon bezeugt.

Syntax

Es gibt zwei wichtige Teile der Logik erster Ordnung. Das Syntax bestimmt, welche endlichen Sequenzen von Symbolen gut geformte Ausdrücke in Logik erster Ordnung erster Ordnung sind, während die Semantik bestimmt die Bedeutungen hinter diesen Ausdrücken.

Alphabet

Im Gegensatz zu natürlichen Sprachen wie Englisch ist die Sprache der Logik erster Ordnung vollständig formal, so dass mechanisch festgelegt werden kann, ob ein bestimmter Ausdruck gut gebildet ist. Es gibt zwei wichtige Arten von wohlgeformten Ausdrücken: Bedingungen, die intuitiv Objekte darstellen, und Formeln, die intuitiv Aussagen ausdrücken, die wahr oder falsch sein können. Die Begriffe und Formeln der Logik erster Ordnung sind Zeichenfolgen von Symbole, wo alle Symbole zusammen die bilden Alphabet der Sprache. Wie mit allem formelle SprachenDie Natur der Symbole selbst liegt außerhalb des Rahmens der formalen Logik; Sie werden oft einfach als Buchstaben und Interpunktionsymbole angesehen.

Es ist üblich, die Symbole des Alphabets in die Teile zu teilen logische Symbole, die immer die gleiche Bedeutung haben und nicht logische Symbole, deren Bedeutung durch Interpretation variiert. Zum Beispiel das logische Symbol ${\ displayStyle \ Land}$ immer repräsentiert "und"; Es wird nie als "oder" interpretiert, was durch das logische Symbol dargestellt wird ${\ displayStyle \ lor}$. Ein nicht logisches Prädikat-Symbol wie Phil (jedochx) könnte interpretiert werden, um "zu bedeuten"x ist ein Philosoph ",", ","x ist ein Mann namens Philip "oder ein anderes unäres Prädikat, abhängig von der vorliegenden Interpretation.

Logische Symbole

Logische Symbole variieren vom Autor, enthalten jedoch normalerweise Folgendes:^[6]

• Quantor Symbole: ∀ zur universellen Quantifizierung und ∃ für die existenzielle Quantifizierung
• Logische Verbindungen: ∧ zum Verbindung, ∨ zum disjunktion, → zum Implikation, ↔ zum zweikonditionell, ¬ zur Negation. Einige Autoren^[7] Verwenden Sie cpq Anstatt von → und epq Anstatt von ↔insbesondere in Kontexten, in denen → für andere Zwecke verwendet wird. Darüber hinaus das Hufeisen ⊃ kann ersetzen →; Die Dreifachstange ≡ kann ersetzen ↔; eine Tilde (~), Np, oder fp kann ersetzen ¬; eine Doppelbalken ${\ displayStyle \ |}$, ${\ displayStyle +}$, oder einpq kann ersetzen ∨; und ein Verstärker &, Kpq, oder der mittlere Punkt ⋅ kann ersetzen ∧, insbesondere wenn diese Symbole aus technischen Gründen nicht verfügbar sind. (Die oben genannten Symbole cpq, Epq, Np, EINpqund kpq werden in verwendet Polnische Notation.))
• Klammern, Klammern und andere Interpunktionsymbole. Die Wahl solcher Symbole variiert je nach Kontext.
• Ein unendlicher Satz von Variablen, oft mit Kleinbuchstaben am Ende des Alphabets bezeichnet x, y, z, .... Einschreibungen werden häufig verwendet, um Variablen zu unterscheiden: x₀, x₁, x₂, ....
• Ein Gleichstellungssymbol (manchmal, Identitätssymbol) = (sehen § Gleichheit und ihre Axiome unter).

Nicht alle diese Symbole sind in Logik erster Ordnung erforderlich. Entweder einer der Quantifizierer zusammen mit Negation, Konjunktion (oder Disjunktion), Variablen, Klammern und Gleichheit ausreicht.

Andere logische Symbole enthalten die folgenden:

• Wahrheitskonstanten: T, V, oder ⊤ für "wahr" und f, o oder ⊥ für "false" (V und O sind aus polnischer Notation). Ohne solche logischen Operatoren von Valenz 0 können diese beiden Konstanten nur mit Quantifizierern ausgedrückt werden.
• Zusätzliche logische Verbindungen wie die Sheffer Schlaganfall, Dpq (Nand) und Exklusiv oder, Jpq.

Nicht logische Symbole

Nicht logische Symbole Prädikate (Beziehungen), Funktionen und Konstanten darstellen. Früher war es Standardpraxis, einen festen, unendlichen Satz nicht-logischer Symbole für alle Zwecke zu verwenden:

• Für jede ganze Zahl n≥ 0, es gibt eine Sammlung von n-Ary, oder n-Platz, Prädikatsymbole. Weil sie repräsentieren Beziehungen zwischen n Elemente werden auch genannt Beziehungssymbole. Für jede Arität nEs gibt eine unendliche Versorgung mit ihnen:

  Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃, ...

• Für jede ganze Zahl n≥ 0, es gibt unendlich viele n-ary Funktionsymbole:

  f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃, ...

Wenn die Arität eines Prädikatsymbols oder eines Funktionsymbols aus dem Kontext klar ist, ist der Superschriften n wird oft weggelassen.

In diesem traditionellen Ansatz gibt es nur eine Sprache der Logik erster Ordnung.^[8] Dieser Ansatz ist immer noch üblich, insbesondere in philosophisch orientierten Büchern.

Eine neuere Praxis besteht darin, verschiedene nicht logische Symbole gemäß der Anwendung zu verwenden, die man im Sinn hat. Daher ist es notwendig geworden, den Satz aller nicht logischen Symbole in einer bestimmten Anwendung zu benennen. Diese Wahl wird über a getroffen Unterschrift.^[9]

Typische Signaturen in der Mathematik sind {1, ×} oder nur {×} für Gruppenoder {0, 1, +, ×, <} für bestellte Felder. Es gibt keine Einschränkungen für die Anzahl der nicht logischen Symbole. Die Signatur kann sein leer, endlich oder unendlich, sogar unzähliger. Unzählige Signaturen treten beispielsweise in modernen Beweisen der Löwenheim -Skolem -Theorem.

Obwohl Unterschriften in einigen Fällen bedeuten könnten, wie nicht-logische Symbole interpretiert werden sollen, Deutung der nicht logischen Symbole in der Signatur sind getrennt (und nicht unbedingt festgelegt). Unterschriften betreffen eher die Syntax als die Semantik.

Bei diesem Ansatz ist jedes nicht logische Symbol eines der folgenden Typen:

• A Prädikatsymbol (oder Beziehungssymbol) mit etwas Wertigkeit (oder Arity, Anzahl der Argumente) größer als oder gleich 0. Diese werden oft durch Großbuchstaben bezeichnet, wie z. P, Q und R. Beispiele:
  • Im P(x), P ist ein Prädikatsymbol der Wertigkeit 1. Eine mögliche Interpretation ist "x ist ein Mann".
  • Im Q(x,y), Q ist ein Prädikatsymbol der Wertigkeit 2. Mögliche Interpretationen einzuschließen "x ist größer als y" und "x ist der Vater von y".
  • Valenzbeziehungen 0 können mit identifiziert werden Aussagenvariablen, was für jede Aussage stehen kann. Eine mögliche Interpretation von R Ist "Sokrates ist ein Mann".
• A Funktionssymbol, mit etwas Valenz größer oder gleich 0. Diese werden oft durch Kleinbuchstaben bezeichnet Römische Buchstaben wie zum Beispiel f, g und h. Beispiele:
  • f(x) kann als "der Vater von interpretiert werden x". Im ArithmetikEs kann für "-x" stehen. Im Mengenlehre, es kann für "das stehen Leistungssatz von x ".
  • In Arithmetik, g(x,y) kann für "stehen"x+y". In der festgelegten Theorie kann es für" die Vereinigung von x und y".
  • Funktionssymbole der Valenz 0 werden aufgerufen Konstante Symbole, und werden oft durch Kleinbuchstaben zu Beginn des Alphabets bezeichnet, z. a, b und c. Das Symbol a kann für Sokrates stehen. In der Arithmetik kann es für 0 stehen. In der festgelegten Theorie kann es für die stehen leeres Set.

Der traditionelle Ansatz kann im modernen Ansatz wiederhergestellt werden, indem einfach die "benutzerdefinierte" Signatur anhand der traditionellen Sequenzen nicht-logischer Symbole bestehen.

Formationsregeln

<Index>  :: = "" | <Index> "'"<Variable>  :: = "x" <Index> <Konstante>  :: = "c" <Index> <Unary -Funktion>  :: = "F1" <Index> <Binärfunktion>  :: = "F2" <Index> <ternäre Funktion>  :: = "F3" <Index> <Unarmes Prädikat>  :: = "P1" <Index> <Binäres Prädikat>  :: = "P2" <Index> <ternäres Prädikat> :: = "p3" <Index> <Begriff>  :: = <Variable>                        | <Konstante>                        | <Unary -Funktion> "(" <Begriff> ")" | <Binärfunktion> "(" <Begriff> "," <Begriff> ")" | <ternäre Funktion> "(" <Begriff> "," <Begriff> "," <Begriff> ")"<Atomformel>  :: = "Wahr" | "Falsch" | <Begriff> "=" <Begriff>                       | <Unarmes Prädikat> "(" <Begriff> ")" | <Binäres Prädikat> "(" <Begriff> "," <Begriff> ")" | <ternäres Prädikat> "(" <Begriff> "," <Begriff> "," <Begriff> ")"<Formel>  :: = <Atomformel>                        | "¬" <Formel>                       | <Formel> "∧" <Formel>                       | <Formel> "∨" <Formel>                       | <Formel> "⇒" <Formel>                       | <Formel> "⇔" <Formel>                       | "(" <Formel> ")" | "∀" <Variable> <Formel>                       | "∃" <Variable> <Formel> 

Das Formationsregeln Definieren Sie die Begriffe und Formeln der Logik erster Ordnung.^[12] Wenn Begriffe und Formeln als Symbole als Zeichenfolgen dargestellt werden, können diese Regeln verwendet werden, um a zu schreiben formelle Grammatik für Begriffe und Formeln. Diese Regeln sind im Allgemeinen kontextfrei (Jede Produktion hat ein einzelnes Symbol auf der linken Seite), außer dass der Satz von Symbolen unendlich sein dürfen und es viele Startsymbole geben Bedingungen.

Bedingungen

Der Satz von Bedingungen ist induktiv definiert Nach den folgenden Regeln:

• Variablen. Jede Variable ist ein Begriff.
• Funktionen. Jeder Ausdruck f(t₁, ...,t_n) von n Argumente (wo jedes Argument t_i ist ein Begriff und f ist ein Funktionssymbol der Wertigkeit n) ist ein Begriff. Insbesondere sind Symbole, die einzelne Konstanten bezeichnen, nulläre Funktionssymbole und somit Begriffe.

Es sind nur Ausdrücke, die durch endlich viele Anträge der Regeln 1 und 2 erhalten werden können. Zum Beispiel ist kein Ausdruck, der ein Prädikatsymbol beinhaltet, ein Begriff.

Formeln

Der Satz von Formeln (auch genannt gut geformte Formeln^[13] oder Wffs) wird durch die folgenden Regeln induktiv definiert:

• Prädikatsymbole. Wenn P ist ein n-ary Prädikatesymbol und t₁, ..., t_n sind dann Begriffe P(t₁, ...,t_n) ist eine Formel.
• Gleichberechtigung. Wenn das Gleichstellungssymbol als Teil der Logik betrachtet wird, und t₁ und t₂ sind Begriffe dann t₁ = t₂ ist eine Formel.
• Negation. Wenn ${\ displayStyle \ varphi}$ ist dann eine Formel ${\ displayStyle \ lnot \ varphi}$ ist eine Formel.
• Binärverbindungen. Wenn ${\ displayStyle \ varphi}$ und ${\ displayStyle \ psi}$ sind dann Formeln (dann (${\ displaystyle \ varphi \ rightarrow \ psi}$) ist eine Formel. Ähnliche Regeln gelten für andere binäre logische Verbindungen.
• Quantifizierer. Wenn ${\ displayStyle \ varphi}$ ist eine Formel und x ist dann eine Variable ${\ displayStyle \ forall x \ varphi}$ (für alle x, ${\ displayStyle \ varphi}$ hält) und ${\ displayStyle \ existiert x \ varphi}$ (Es gibt X so, dass x so existiert ${\ displayStyle \ varphi}$) sind Formeln.

Nur Ausdrücke, die durch endlich viele Anwendungen der Regeln 1–5 erhalten werden können, sind Formeln. Die aus den ersten beiden Regeln erhaltenen Formeln sollen sein Atomformeln.

Zum Beispiel,

$oder$

ist eine Formel, wenn f ist ein unärer Funktionsymbol, P Ein unäres Prädikatsymbol und q Ein ternäres Prädikatsymbol. Jedoch, ${\ displaystyle \ forall x \, x \ rightarrow}$ ist keine Formel, obwohl es sich um eine Reihe von Symbolen aus dem Alphabet handelt.

Die Rolle der Klammern in der Definition besteht darin, sicherzustellen, dass jede Formel nur auf eine Weise erhalten werden kann - indem der induktiven Definition folgt (d. H. Es gibt eine einzigartige Baum analysieren für jede Formel). Diese Eigenschaft ist bekannt als Einzigartige Lesbarkeit von Formeln. Es gibt viele Konventionen dafür, wo Klammern in Formeln verwendet werden. Zum Beispiel verwenden einige Autoren Kolons oder Vollstapfen anstelle von Klammern oder ändern die Orte, an denen Klammern eingefügt werden. Die besondere Definition jedes Autors muss von einem Nachweis einer einzigartigen Lesbarkeit begleitet werden.

Diese Definition einer Formel unterstützt nicht die Definition einer if-then-Else-Funktion ite (c, a, b), wobei "C" eine Bedingung ist, die als Formel ausgedrückt wird, würde das zurückgeben "a", wenn C wahr ist, und "B", wenn es falsch ist. Dies liegt daran, dass sowohl Prädikate als auch Funktionen nur Begriffe als Parameter akzeptieren können, der erste Parameter ist jedoch eine Formel. Einige Sprachen, die auf Logik erster Ordnung basieren, wie z. B. SMT-Lib 2.0, fügen Sie dies hinzu.^[14]

Notationale Konventionen

Aus Gründen der Bequemlichkeit wurden Konventionen über das Vorrang der logischen Operatoren entwickelt, um in einigen Fällen die Notwendigkeit zu vermeiden, Klammern zu schreiben. Diese Regeln ähneln dem Operationsreihenfolge in Arithmetik. Eine gemeinsame Konvention ist:

• ${\ displayStyle \ lnot}$ wird zuerst bewertet
• ${\ displayStyle \ Land}$ und ${\ displayStyle \ lor}$ werden als nächstes bewertet
• Quantifizierer werden als nächstes bewertet
• ${\ displayStyle \ bis}$ wird zuletzt bewertet.

Darüber hinaus kann eine zusätzliche Interpunktion, die von der Definition nicht erforderlich ist, eingefügt werden, um Formeln zu erleichtern. So die Formel

${\ displaystyle \ lnot \ forall xp (x) \ bis \ existiert x \ lnot p (x)}$

könnte geschrieben werden als

${\ displayStyle (\ lnot [\ forall xp (x)]) \ bis \ existiert x [\ lnot p (x)].}$

In einigen Bereichen ist es üblich, die Infix -Notation für binäre Beziehungen und Funktionen anstelle der oben definierten Präfixnotation zu verwenden. Beispielsweise schreibt man in Arithmetik typischerweise "2 + 2 = 4" anstelle von "= ( + (2,2), 4)". Es ist üblich, Formeln in der Infix -Notation als Abkürzungen für die entsprechenden Formeln in der Präfixnotation, vgl. Auch Termstruktur vs. Darstellung.

Die obigen Definitionen verwenden Infix -Notation für binäre Konnektiven wie z. ${\ displayStyle \ bis}$. Eine weniger verbreitete Konvention ist Polnische Notation, in dem man schreibt ${\ displayStyle \ rightarrow}$, ${\ displayStyle \ Wedge}$ und so weiter vor ihren Argumenten als zwischen ihnen. Diese Konvention ist insofern von Vorteil, als alle Zeichensetzung Symbole verworfen werden können. Als solches ist die polnische Notation kompakt und elegant, aber in der Praxis selten verwendet, weil es für Menschen schwer zu lesen ist. In polnischer Notation die Formel

$oder$

wird "∀x∀y → Pfx → pxqfyxz".

Freie und gebundene Variablen

In einer Formel kann eine Variable auftreten frei oder gebunden (oder beides). Intuitiv ist ein variables Auftreten in einer Formel frei, wenn sie nicht quantifiziert ist:^[15] in ∀y P(x, y)das einzige Auftreten von Variablen x ist frei, während das von y ist gebunden. Die freien und gebundenen variablen Ereignisse in einer Formel werden induktiv wie folgt definiert.

Atomformeln

Wenn φ ist dann eine atomare Formel x tritt frei in φ dann und nur dann, wenn x tritt auf in φ. Darüber hinaus gibt es in einer atomaren Formel keine gebundenen Variablen.

Negation

x tritt frei in ¬ aufφ dann und nur dann, wenn x tritt frei in φ. x tritt in ¬ gebundenφ dann und nur dann, wenn x tritt in φ

Binärverbindungen

x tritt frei in (vor (φ → ψ) dann und nur dann, wenn x tritt in beiden frei φ oder ψ. x tritt gebunden in (φ → ψ) dann und nur dann, wenn x tritt in beides gebunden φ oder ψ. Die gleiche Regel gilt für eine andere binäre Binde anstelle von →.

Quantifizierer

x tritt frei in ∀y φ, wenn und nur wenn x in frei auftritt φ und x ist ein anderes Symbol als y. Ebenfalls, x tritt in ∀y φ, dann und nur dann, wenn x ist y oder x tritt in φ. Die gleiche Regel gilt mit ∃ anstelle von ∀.

Zum Beispiel in ∀x ∀y (P(x) → Q(x,f(x),z)), x und y nur gebunden auftreten,^[16] z tritt nur frei und kommt nur frei, und w ist weder weil es in der Formel nicht vorkommt.

Freie und gebundene Variablen einer Formel müssen nicht disjunkt sein: in der Formel P(x) → ∀x Q(x)das erste Ereignis von xals Argument von P, ist frei, während der zweite als Argument von Q, ist gebunden.

Eine Formel in Logik erster Ordnung ohne freie variable Ereignisse wird als a genannt erste Bestellung Satz. Dies sind die Formeln, die genau definiert sein werden Wahrheitswerte unter einer Interpretation. Zum Beispiel, ob eine Formel wie Phil (x) ist wahr, muss davon abhängen, was x repräsentiert. Aber der Satz ∃x Phil (x) wird in einer bestimmten Interpretation entweder wahr oder falsch sein.

Beispiel: Ordnungsgeordnete Abelsche Gruppen

In der Mathematik die Sprache der geordneten Abelsche Gruppen hat ein konstantes Symbol 0, ein unärtetes Funktionsymbol -, ein binäres Funktionsymbol +und ein binäres Beziehungssymbol ≤. Dann:

• Die Ausdrücke +(x, y) und +(x, +(y, - (z))) sind Bedingungen. Diese werden normalerweise als geschrieben als x + y und x + y − z.
• Die Ausdrücke +(x, y) = 0 und ≤ (+(x, +(y, - (z))), +(x, y)) sind Atomformeln. Diese werden normalerweise als geschrieben als x + y = 0 und x + y − z ≤ x + y.
• Der Ausdruck $oder (x, y) = 0)]}$ ist ein Formel, was normalerweise als geschrieben wird als ${\ displaystyle \ forall x \ forall y (x+y \ leq z) \ to \ forall x \ forall y (x+y = 0).}$ Diese Formel hat eine kostenlose Variable, z.

Die Axiome für geordnete Abelsche Gruppen können als Sätze in der Sprache ausgedrückt werden. Zum Beispiel wird das Axiom angibt, dass die Gruppe kommutativ ist ${\ displayStyle (\ forall x) (\ forall y) [x+y = y+x].}$

Semantik

Ein Deutung einer Sprache erster Ordnung weist jedem nicht-logischen Symbol (Prädikatsymbol, Funktionsymbol oder konstanter Symbol) in dieser Sprache eine Bezeichnung zu. Es bestimmt auch a Diskursbereich Das gibt den Bereich der Quantifizierer an. Das Ergebnis ist, dass jedem Term ein Objekt zugewiesen wird, das ihm darstellt, jedem Prädikat eine Eigenschaft von Objekten zugewiesen und jedem Satz ein Wahrheitswert zugewiesen wird. Auf diese Weise bietet eine Interpretation den Begriffen, Prädikaten und Formeln der Sprache eine semantische Bedeutung. Das Studium der Interpretationen formaler Sprachen wird genannt formelle Semantik. Was folgt, ist eine Beschreibung des Standards oder Tarskian Semantik für Logik erster Ordnung. (Es ist auch möglich zu definieren Spielsemantik für Logik erster Ordnung, aber abgesehen davon, dass das erforderlich ist Axiom der Wahl, Game Semantics stimmen mit Tarskian Semantics für Logik erster Ordnung zu, sodass die Spielsemantik hier nicht ausgearbeitet wird.)

Strukturen erster Ordnung

Die häufigste Art, eine Interpretation anzugeben (insbesondere in der Mathematik), besteht darin, a zu spezifizieren Struktur (auch a genannt Modell; siehe unten). Die Struktur besteht aus einem Diskursbereich D und eine Interpretationsfunktion I Abbildung nicht logischer Symbole zu Prädikaten, Funktionen und Konstanten.

Die Diskursdomäne D ist eine nicht leere Reihe von "Objekten" irgendeiner Art. Bei einer Interpretation wird eine Formel erster Ordnung zu einer Aussage zu diesen Objekten. zum Beispiel, ${\ displayStyle \ existiert xp (x)}$ stellt die Existenz eines Objekts in an in D für das das Prädikat P ist wahr (oder genauer gesagt, für das das Prädikat dem Prädikatsymbol zugewiesen wurde P durch die Interpretation ist wahr). Zum Beispiel kann man nehmen D der Satz von sein Ganzzahlen.

Nicht logische Symbole werden wie folgt interpretiert:

• Die Interpretation eines n-ary -Funktionsymbol ist eine Funktion von Dⁿ zu D. Wenn beispielsweise die Diskursdomäne der Satz von Ganzzahlen ist, ist ein Funktionssymbol f von Arity 2 kann als die Funktion interpretiert werden, die die Summe seiner Argumente angibt. Mit anderen Worten das Symbol f ist mit der Funktion verbunden ${\ displayStyle i (f)}$ was in dieser Interpretation Addition ist.

• Die Interpretation eines konstanten Symbols (ein Funktionssymbol von Arity 0) ist eine Funktion von D⁰ (Ein Set, dessen einziges Mitglied das leere ist Tupel) zu D, was einfach mit einem Objekt in identifiziert werden kann D. Zum Beispiel kann eine Interpretation den Wert zuweisen ${\ displayStyle i (c) = 10}$ zum konstanten Symbol ${\ displayStyle c}$.

• Die Interpretation eines n-artiges Prädikatsymbol ist ein Satz von n-Tupel von Elementen von DDas Prädikat ist wahr, die Argumente zu geben. Zum Beispiel eine Interpretation ${\ displayStyle i (p)}$ eines binären Prädikatsymbols P Kann die Menge von Zahlenpaaren sein, so dass der erste kleiner als der zweite ist. Nach dieser Interpretation das Prädikat P wäre wahr, wenn sein erstes Argument weniger als sein zweites Argument ist. Äquivalent können Prädikatsymbole zugewiesen werden Boolesche Funktionen aus Dⁿ zu ${\ displayStyle \ {\ mathrm {true, false} \}}$.

Bewertung der Wahrheitswerte

Eine Formel bewertet bei einer Interpretation und a Variable Zuordnung μ mit jeder Variablen ein Element der Diskursdomäne. Der Grund, warum eine variable Zuordnung erforderlich ist, besteht darin, Formeln mit freien Variablen Bedeutungen zu geben, wie z. ${\ displayStyle y = x}$. Der Wahrheitswert dieser Formel ändert sich, je nachdem, ob x und y bezeichnen die gleiche Person.

Zunächst kann die variable Zuordnung μ auf alle Terme der Sprache erweitert werden, mit dem Ergebnis, dass jeder Begriff auf ein einzelnes Element der Diskursdomäne abbildet. Die folgenden Regeln werden verwendet, um diese Zuordnung zu treffen:

• Variablen. Jede Variable x bewertet μ(x)
• Funktionen. Gegebene Begriffe ${\ displayStyle t_ {1}, \ ldots, t_ {n}}$ das wurden auf Elemente bewertet ${\ displayStyle d_ {1}, \ ldots, d_ {n}}$ des Diskurses und a n-ary Funktionsymbol f, der Begriff ${\ displayStyle f (t_ {1}, \ ldots, t_ {n})}$ bewertet ${\ displayStyle (i (f)) (d_ {1}, \ ldots, d_ {n})}$.

Als nächstes wird jeder Formel ein Wahrheitswert zugewiesen. Die induktive Definition, die verwendet wird, um diese Zuordnung zu machen T-Schema.

• Atomformeln (1). Eine Formel ${\ displayStyle p (t_ {1}, \ ldots, t_ {n})}$ ist verknüpft der Wert wahr oder falsch, je nachdem, ob ${\ displayStyle \ Langle v_ {1}, \ ldots, v_ {n} \ rangle \ in i (p)}$, wo ${\ displayStyle v_ {1}, \ ldots, v_ {n}}$ sind die Bewertung der Begriffe ${\ displayStyle t_ {1}, \ ldots, t_ {n}}$ und ${\ displayStyle i (p)}$ ist die Interpretation von ${\ displayStyle p}$, was durch Annahme eine Teilmenge von ist ${\ displayStyle d^{n}}$.
• Atomformeln (2). Eine Formel ${\ displayStyle t_ {1} = t_ {2}}$ wird wahr zugewiesen, wenn ${\ displayStyle t_ {1}}$ und ${\ displayStyle t_ {2}}$ Bewerten Sie das gleiche Objekt des Diskursbereichs (siehe Abschnitt über Gleichheit unten).
• Logische Verbindungen. Eine Formel in der Form ${\ displayStyle \ neg \ varphi}$, ${\ displaystyle \ varphi \ rightarrow \ psi}$usw. wird nach dem bewertet Wahrheitstabelle für den fraglichen Bindesprung, wie in der Aussagelogik.
• Existenzielle Quantifizierer. Eine Formel ${\ displayStyle \ existiert x \ varphi (x)}$ ist wahr nach M und ${\ displayStyle \ mu}$ Wenn es eine Bewertung gibt ${\ displayStyle \ mu '}$ der Variablen, die sich nur unterscheiden ${\ displayStyle \ mu}$ in Bezug auf die Bewertung von x und so dass φ gemäß der Interpretation wahr ist M und die variable Zuordnung ${\ displayStyle \ mu '}$. Diese formale Definition erfasst die Idee, dass ${\ displayStyle \ existiert x \ varphi (x)}$ ist wahr, wenn und nur wenn es eine Möglichkeit gibt, einen Wert für einen Wert zu wählen x so dass φ (x) ist befriedigt.
• Universelle Quantifizierer. Eine Formel ${\ displaystyle \ forall x \ varphi (x)}$ ist wahr nach M und ${\ displayStyle \ mu}$ Wenn φ (x) gilt für jedes Paar, das durch die Interpretation komponiert wurde M und eine variable Zuordnung ${\ displayStyle \ mu '}$ Das unterscheidet sich von ${\ displayStyle \ mu}$ Nur für den Wert von x. Dies erfasst die Idee, dass ${\ displaystyle \ forall x \ varphi (x)}$ ist wahr, wenn jede mögliche Wahl eines Wertes für x Ursachen φ (x) wahr sein.

Wenn eine Formel keine freien Variablen enthält, ist auch ein Satz, dann wirkt sich die anfängliche Variablenzuordnung nicht auf den Wahrheitswert aus. Mit anderen Worten, ein Satz ist wahr nach M und ${\ displayStyle \ mu}$ Wenn und nur wenn es nach wie vor ist M und jede andere variable Zuordnung ${\ displayStyle \ mu '}$.

Es gibt einen zweiten gemeinsamen Ansatz, um Wahrheitswerte zu definieren, die nicht auf variablen Zuweisungsfunktionen beruhen. Stattdessen bei einer Interpretation M, einer fügt zuerst die Signatur eine Sammlung konstanter Symbole hinzu, eine für jedes Element des Diskursbereichs in M; Sag das für jeden d In der Domäne das konstante Symbol c_d Ist repariert. Die Interpretation wird so erweitert, dass jedes neue konstante Symbol seinem entsprechenden Element der Domäne zugeordnet ist. Man definiert nun die Wahrheit für quantifizierte Formeln syntaktisch wie folgt:

• Existenzielle Quantifizierer (alternativ). Eine Formel ${\ displayStyle \ existiert x \ varphi (x)}$ ist wahr nach M Wenn es etwas gibt d im Bereich des Diskurses so, dass ${\ displayStyle \ varphi (c_ {d})}$ hält. Hier ${\ displayStyle \ varphi (c_ {d})}$ ist das Ergebnis des Ersatzes c_d für jedes freie Ereignis von x in φ.
• Universelle Quantifizierer (alternativ). Eine Formel ${\ displaystyle \ forall x \ varphi (x)}$ ist wahr nach M Wenn für jeden d im Bereich des Diskurses, ${\ displayStyle \ varphi (c_ {d})}$ ist wahr nach M.

Dieser alternative Ansatz gibt allen Sätzen genau die gleichen Wahrheitswerte wie der Ansatz über variable Zuordnungen.

Gültigkeit, Erfüllbarkeit und logische Konsequenz

Wenn ein Satz φ zu bewertet Stimmt unter einer bestimmten Interpretation Mman sagt das M zufrieden φ; Dies wird bezeichnet^[17] ${\ displayStyle m \ vdash \ varphi}$. Ein Satz ist erfüllbar Wenn es eine Interpretation gibt, unter der es wahr ist.

Die Erfüllbarkeit von Formeln mit freien Variablen ist komplizierter, da eine eigene Interpretation nicht den Wahrheitswert einer solchen Formel bestimmt. Die häufigste Konvention ist, dass eine Formel mit freien Variablen durch eine Interpretation erfüllt sein soll, wenn die Formel wahr bleibt, unabhängig davon, welche Personen aus der Diskursdomäne ihren freien Variablen zugeordnet sind. Dies hat den gleichen Effekt wie zu sagen, dass eine Formel nur dann zufrieden ist Universeller Schließung ist befriedigt.

Eine Formel ist Logisch gültig (oder einfach gültig) Wenn es in jeder Interpretation wahr ist.^[18] Diese Formeln spielen eine ähnliche Rolle wie Tautologien in der Aussagelogik.

Eine Formel φ ist a logische Konsequenz einer Formel ψ, wenn jede Interpretation, die ψ wahr macht, auch φ wahr macht. In diesem Fall sagt man, dass φ durch ψ logisch impliziert wird.

Algebraisierungen

Ein alternativer Ansatz zur Semantik der Logik erster Ordnung verläuft über Zusammenfassung Algebra. Dieser Ansatz verallgemeinert die Lindenbaum -Tarski -Algebren von Aussagen Logik. Es gibt drei Möglichkeiten, quantifizierte Variablen aus Logik erster Ordnung zu beseitigen, bei denen Quantifizierer nicht durch andere variable Bindungsbegriffer ersetzt werden: Operatoren:

• Zylinderalgebra, durch Alfred Tarski und Kollegen;
• Polyadische Algebra, durch Paul Halmos;
• Prädikatfunk -Logikhauptsächlich aufgrund Willard Quine.

Diese Algebren sind alle Gitter das erweitert die richtige Zwei-Element-Boolesche Algebra.

Tarski und Givant (1987) zeigten, dass das Fragment der Logik erster Ordnung, das keine atomarer Satz Im Bereich von mehr als drei Quantifizierungen zu liegen, hat die gleiche ausdrucksstarke Kraft wie Beziehungalgebra.^{[19]: 32–33} Dieses Fragment ist von großem Interesse, weil es ausreicht für Peano -Arithmetik Und die meisten Axiomatische Set -Theorie, einschließlich der Kanonisch ZFC. Sie beweisen auch diese Logik erster Ordnung mit einem primitiven geordnetes Paar entspricht einer Beziehungalgebra mit zwei geordneten Paaren Projektionsfunktionen.^{[20]: 803}

Theorien, Modelle und Elementarklassen erster Ordnung erster Ordnung

A Theorie erster Ordnung einer bestimmten Signatur ist ein Satz von Axiome, die Sätze sind, die aus Symbolen aus dieser Signatur bestehen. Der Satz von Axiomen ist oft endlich oder rekursiv aufgezähltIn welchem ​​Fall wird die Theorie genannt Wirksam. Einige Autoren verlangen Theorien, dass sie auch alle logischen Konsequenzen der Axiome einbeziehen. Es wird angesehen, dass die Axiome innerhalb der Theorie und von ihnen andere Sätze, die innerhalb der Theorie enthalten, abgeleitet werden.

Eine Struktur erster Ordnung, die alle Sätze in einer bestimmten Theorie erfüllt Modell der Theorie. Ein Grundklasse ist die Menge aller Strukturen, die eine bestimmte Theorie erfüllen. Diese Klassen sind ein Hauptstudium in Studie in Modelltheorie.

Viele Theorien haben eine beabsichtigte Interpretation, ein bestimmtes Modell, das beim Studium der Theorie berücksichtigt wird. Zum Beispiel die beabsichtigte Interpretation von Peano -Arithmetik besteht aus dem üblichen natürliche Zahlen mit ihren üblichen Operationen. Das Löwenheim-Skolem-Theorem zeigt jedoch, dass die meisten Theorien erster Ordnung auch andere haben werden. Nicht standardmäßige Modelle.

Eine Theorie ist konsistent Wenn es nicht möglich ist, einen Widerspruch aus den Axiomen der Theorie zu beweisen. Eine Theorie ist Komplett Wenn für jede Formel in ihrer Signatur entweder diese Formel oder ihre Negation eine logische Folge der Axiome der Theorie ist. Gödels Unvollständigkeitstheorem zeigt, dass effektive Theorien erster Ordnung, die einen ausreichenden Teil der Theorie der natürlichen Zahlen enthalten, niemals konsistent und vollständig sein können.

Leere Domänen

Die obige Definition erfordert, dass der Diskursbereich einer Interpretation nicht leer sein muss. Es gibt Einstellungen wie z. inklusive Logik, wo leere Domänen erlaubt sind. Wenn eine Klasse von algebraischen Strukturen eine leere Struktur enthält (z. B. gibt es eine leere Poset) Diese Klasse kann nur eine Elementarklasse in Logik erster Ordnung sein, wenn leere Domänen zulässig sind oder die leere Struktur aus der Klasse entfernt wird.

Es gibt jedoch mehrere Schwierigkeiten mit leeren Domänen:

• Viele häufige Inferenzregeln sind nur gültig, wenn die Diskursdomäne nicht leer sein muss. Ein Beispiel ist die Regel, die besagt, dass ${\ displaystyle \ varphi \ lor \ existiert x \ psi}$ impliziert ${\ displayStyle \ existiert x (\ varphi \ lor \ psi)}$ Wenn x ist keine freie Variable in ${\ displayStyle \ varphi}$. Diese Regel, die verwendet wird, um Formeln in einzulegen Prenex normale Form, ist in nicht leeren Domänen solide, aber unangemessen, wenn die leere Domäne zulässig ist.
• Die Definition der Wahrheit in einer Interpretation, bei der eine Funktion variabler Zuweisung verwendet, kann nicht mit leeren Domänen funktionieren, da es keine variablen Zuweisungsfunktionen gibt, deren Bereich leer ist. (In ähnlicher Weise kann man konstante Symbole Interpretationen nicht zuweisen.) Diese Wahrheitsdefinition erfordert, dass man eine variable Zuordnungsfunktion (μ oben) auswählen muss, bevor Wahrheitswerte für selbstatomare Formeln definiert werden können. Dann wird der Wahrheitswert eines Satzes unter einer variablen Zuordnung als Wahrheitswert definiert, und es wird bewiesen, dass dieser Wahrheitswert nicht von der Auswahl der Zuordnung abhängt. Diese Technik funktioniert nicht, wenn überhaupt keine Zuordnungsfunktionen vorhanden sind. Es muss geändert werden, um leere Domänen aufzunehmen.

Wenn die leere Domäne zulässig ist, muss sie oft als Sonderfall behandelt werden. Die meisten Autoren schließen die leere Domäne jedoch per Definition einfach aus.

Deduktive Systeme

A deduktives System wird verwendet, um rein syntaktisch zu demonstrieren, dass eine Formel eine logische Folge einer anderen Formel ist. Es gibt viele solcher Systeme für Logik erster Ordnung, einschließlich Deduktive Systeme im Hilbert-Stil, natürlicher Abzug, das Sequent Calculus, das Tableaux -Methode, und Auflösung. Diese teilen die gemeinsame Eigenschaft, dass ein Abzug ein endliches syntaktisches Objekt ist. Das Format dieses Objekts und die Art und Weise, wie es konstruiert wird, variiert stark. Diese endlichen Abzüge selbst werden oft genannt Ableitungen in der Proof -Theorie. Sie werden auch oft genannt Beweise, sind aber im Gegensatz zu natürlicher Sprache vollständig formalisiert Mathematische Beweise.

Ein deduktives System ist Klang Wenn eine Formel, die im System abgeleitet werden kann, logisch gültig ist. Umgekehrt ist ein deduktives System Komplett Wenn jede logisch gültige Formel abgeleitet ist. Alle in diesem Artikel diskutierten Systeme sind sowohl solide als auch vollständig. Sie teilen auch die Eigenschaft, dass es möglich ist, effektiv zu überprüfen, ob ein angeblich gültiger Abzug tatsächlich ein Abzug ist. Solche Abzugssysteme werden genannt Wirksam.

Eine wichtige Eigenschaft deduktiver Systeme ist, dass sie rein syntaktisch sind, so dass Ableitungen ohne Berücksichtigung einer Interpretation verifiziert werden können. Somit ist ein solides Argument in jeder möglichen Interpretation der Sprache korrekt, unabhängig davon, ob es in dieser Interpretation um Mathematik, Wirtschaft oder einen anderen Bereich geht.

Im Allgemeinen beträgt die logische Konsequenz in der Logik erster Ordnung nur halbkassbar: Wenn ein Satz A logisch einen Satz B impliziert, kann dies entdeckt werden (beispielsweise durch die Suche nach einem Beweis, bis einer mit einem effektiven, soliden, soliden, vollständigen Beweissystem gefunden wird). Wenn A jedoch logisch nicht b impliziert, bedeutet dies nicht, dass A logisch die Negation von B. impliziert. Es gibt keine wirksame Prozedur, die bei den Formeln A und B immer richtig entscheidet, ob A logisch B. impliziert. B.

Inferenzregeln

A Inferenzregel Gibt an, dass bei einer bestimmten Formel (oder einer Reihe von Formeln) mit einer bestimmten Eigenschaft als Hypothese eine andere spezifische Formel (oder eine Reihe von Formeln) als Schlussfolgerung abgeleitet werden kann. Die Regel ist solide (oder Wahrheitsvorsorge), wenn sie die Gültigkeit in dem Sinne bewahrt, dass diese Interpretation auch die Schlussfolgerung erfüllt, wenn eine Interpretation die Hypothese erfüllt.

Zum Beispiel ist eine gemeinsame Regel der Inferenz die Substitutionsregel. Wenn t ist ein Begriff und φ ist eine Formel, die möglicherweise die Variable enthält xdann φ [t/x] ist das Ergebnis des Ersetzens aller freien Instanzen von x durch t in φ. Die Substitutionsregel besagt, dass für jeden φ und jeden Term t, man kann φ schließen [[t/x] von φ vorgesehen, dass keine freie Variable von t wird während des Substitutionsprozesses gebunden. (Wenn eine freie Variable von t wird gebunden und dann ersetzen t zum x Es ist zunächst erforderlich, die gebundenen Variablen von φ zu ändern, um sich von den freien Variablen von zu unterscheiden t.))

Betrachten Sie die logisch gültige Formel φ angegeben durch, um zu sehen, warum die Einschränkung der gebundenen Variablen erforderlich ist ${\ displayStyle \ existiert x (x = y)}$, in der Signatur von (0,1,+, ×, =) der Arithmetik. Wenn t ist der Begriff "x + 1", die Formel φ [t/y] ist ${\ displayStyle \ existiert x (x = x+1)}$, was in vielen Interpretationen falsch sein wird. Das Problem ist, dass die freie Variable x von t wurde während der Substitution gebunden. Der beabsichtigte Ersatz kann durch Umbenennen der gebundenen Variablen erhalten werden x von φ zu etwas anderem, sagen wir z, damit die Formel nach Substitution ist ${\ displayStyle \ existiert z (z = x+1)}$, was wieder logisch gültig ist.

Die Substitutionsregel zeigt mehrere gemeinsame Aspekte von Inferenzregeln. Es ist völlig syntaktisch; Man kann feststellen, ob es ohne Auslegung ohne Berufung korrekt angewendet wurde. Es hat (syntaktisch definiert) Einschränkungen, wenn es angewendet werden kann, die respektiert werden müssen, um die Richtigkeit von Ableitungen zu erhalten. Darüber hinaus sind diese Einschränkungen, wie es oft der Fall ist, aufgrund von Wechselwirkungen zwischen freien und gebundenen Variablen erforderlich, die während syntaktischer Manipulationen der an der Inferenzregel beteiligten Formeln auftreten.

Systeme im Hilbert-Stil und natürlicher Abzug

Ein Abzug in einem deduktiven System im Hilbert-Stil ist eine Liste von Formeln, von denen jeder a ist logisches Axiom, Eine Hypothese, die für die abgeleitete Ableitung angenommen wurde oder aus früheren Formeln über eine Inferenzregel folgt. Die logischen Axiome bestehen aus mehreren Axiomschemata von logisch gültigen Formeln; Diese umfassen eine erhebliche Menge an Propositionslogik. Die Inferenzregeln ermöglichen die Manipulation von Quantifizierern. Typische Systeme im Hilbert-Stil haben eine kleine Anzahl von Inferenzregeln sowie mehrere unendliche Schemata logischer Axiome. Es ist üblich, nur zu haben Modus Ponens und Universelle Verallgemeinerung als Inferenzregeln.

Natürliche Abzugssysteme ähneln Systeme im Hilbert-Stil, da ein Abzug eine endliche Liste von Formeln ist. Natürliche Abzugssysteme haben jedoch keine logischen Axiome; Sie kompensieren durch das Hinzufügen zusätzlicher Inferenzregeln, die verwendet werden können, um die logischen Verbindungen in Formeln im Beweis zu manipulieren.

Sequent Calculus

Der Sequent Calculus wurde entwickelt, um die Eigenschaften natürlicher Abzugssysteme zu untersuchen.^[21] Anstatt mit einer Formel gleichzeitig zu arbeiten, verwendet sie Fortsetzungen, die Ausdrücke der Form sind

${\ displayStyle a_ {1}, \ ldots, a_ {n} \ vdash b_ {1}, \ ldots, b_ {k},},}$

wo ein₁, ..., EIN_n, B₁, ..., B_k sind Formeln und das Drehkreuzsymbol ${\ displayStyle \ vdash}$ wird als Zeichensetzung verwendet, um die beiden Hälften zu trennen. Intuitiv drückt eine Sequent die Idee aus, dass ${\ displayStyle (a_ {1} \ land \ cdots \ land a_ {n})}$ impliziert ${\ displayStyle (b_ {1} \ lor \ cdots \ lor b_ {k})}$.

Tableaux -Methode

Ein Tableaux -Beweis für die Aussagen Formel ((a ∨ ¬b) ∧ b) → a.

Im Gegensatz zu den gerade beschriebenen Methoden sind die Ableitungen in der TableAUx -Methode keine Listen von Formeln. Stattdessen ist eine Ableitung ein Baum von Formeln. Um zu zeigen, dass eine Formel A nachweisbar ist, versucht die Tableaus -Methode zu demonstrieren, dass die Verneinung von A nicht zufriedenstellbar ist. Der Baum der Ableitung hat ${\ displayStyle \ lnot a}$ an seiner Wurzel; Der Baum ist in einer Weise, die die Struktur der Formel widerspiegelt. Zum Beispiel, um das zu zeigen ${\ displayStyle c \ lor d}$ ist nicht zufriedenstellbar, dass C und D jeweils unbefriedigbar sind. Dies entspricht einem Verzweigungspunkt im Baum mit Eltern ${\ displayStyle c \ lor d}$ und Kinder C und D.

Auflösung

Das Auflösungsregel ist eine einzige Regel der Inferenz, die zusammen mit Vereinigung, ist solide und vollständig für Logik erster Ordnung. Wie bei der Tableaux -Methode wird eine Formel beweisen, indem zeigt, dass die Negation der Formel nicht zufrieden ist. Die Auflösung wird üblicherweise im automatisierten Theorem -Beweis verwendet.

Die Auflösungsmethode funktioniert nur mit Formeln, bei denen Atomformeln abfällt. willkürliche Formeln müssen zuerst durch diese Form konvertiert werden Skolemisierung. Die Auflösungsregel besagt, dass aus den Hypothesen ${\ displayStyle a_ {1} \ lor \ cdots \ lor a_ {k} \ lor c}$ und ${\ displayStyle b_ {1} \ lor \ cdots \ lor b_ {l} \ lor \ lnot c}$, der Abschluss $oder$ kann erhalten werden.

Nachweisbare Identitäten

Es können viele Identitäten bewiesen werden, die Äquivalenzen zwischen bestimmten Formeln festlegen. Diese Identitäten ermöglichen die Umständungsformeln durch Verschieben von Quantifizierern in anderen Konnektiven und sind nützlich, um Formeln in einzulegen Prenex normale Form. Einige nachweisbare Identitäten umfassen:

${\ displaystyle \ lnot \ forall x \, p (x) \ leftrightarrow \ existiert x \, \ lnot p (x)}$

${\ displaystyle \ lnot \ exists x \, p (x) \ leftrightarrow \ forall x \, \ lnot p (x)}$

$oder$

${\ displaystyle \ existiert x \, \ existiert y \, p (x, y) \ leftrightarrow \ existiert y \, \ existiert x \, p (x, y)}$

$oder$

$oder$

$oder$ (wo ${\ displayStyle x}$ darf nicht frei auftreten in ${\ displayStyle p}$)

${\ displayStyle p \ lor \ forall x \, q (x) \ leftrightarrow \ forall x \, (p \ lor q (x))}}$ (wo ${\ displayStyle x}$ darf nicht frei auftreten in ${\ displayStyle p}$)

Gleichheit und seine Axiome

Es gibt verschiedene Konventionen für die Verwendung von Gleichheit (oder Identität) in Logik erster Ordnung. Die häufigste Konvention, bekannt als Logik erster Ordnung mit Gleichheit, enthält das Gleichheitssymbol als primitives logisches Symbol, das immer als reale Gleichheitsbeziehung zwischen den Mitgliedern des Diskurses interpretiert wird, so dass die "zwei" gegebenen Mitglieder das gleiche Mitglied sind. Dieser Ansatz fügt auch bestimmte Axiome über Gleichheit zum deduktiven System hinzu. Diese Gleichheit Axiome sind:^{[22]: 198–200}

• Reflexivität. Für jede Variable x, x = x.
• Substitution für Funktionen. Für alle Variablen x und y, und jedes Funktionssymbol fAnwesend

  x = y → f(..., x, ...) = f(..., y, ...).

• Substitution für Formeln. Für alle Variablen x und y und jede Formel φ (x), wenn φ 'erhalten wird, indem eine beliebige Anzahl freier Vorkommen von ersetzt wird x in φ mit y, so dass diese freien Ereignisse von bleiben y, dann

  x = y → (φ → φ ').

Diese sind Axiomschematajeweils spezifiziert ein unendlicher Satz von Axiomen. Das dritte Schema ist bekannt als Leibnizs Gesetz, "Das Prinzip der Substitutivität", "die Individualität identischer" oder "die Ersatzeigenschaft". Das zweite Schema, das das Funktionsymbol betrifft f, ist (gleichwertig) ein Sonderfall des dritten Schemas unter Verwendung der Formel

x = y → (f(..., x, ...) = z → f(..., y, ...) = z).

Viele andere Eigenschaften der Gleichheit sind Konsequenzen der oben genannten Axiome, zum Beispiel:

• Symmetrie. Wenn x = y dann y = x.^[23]
• Transitivität. Wenn x = y und y = z dann x = z.^[24]

Logik erster Ordnung ohne Gleichheit

Ein alternativer Ansatz betrachtet die Gleichstellungsbeziehung als ein nicht logisches Symbol. Diese Konvention ist als bekannt als als Logik erster Ordnung ohne Gleichheit. Wenn eine Gleichheitsbeziehung in die Signatur enthalten ist, müssen die Axiome der Gleichheit nun zu den betrachteten Theorien hinzugefügt werden, falls gewünscht, anstatt als Logikregeln angesehen zu werden. Der Hauptunterschied zwischen dieser Methode und der Logik erster Ordnung mit Gleichheit besteht darin, dass eine Interpretation jetzt zwei unterschiedliche Individuen als "gleich" interpretieren kann (obwohl dies nach Leibnizs Gesetz genau dieselben Formeln in jeder Interpretation erfüllt). Das heißt, die Gleichstellungsbeziehung kann nun von einem willkürlichen interpretiert werden Äquivalenzbeziehung Auf dem Diskursbereich dh das ist kongruent in Bezug auf die Funktionen und Beziehungen der Interpretation.

Wenn diese zweite Konvention befolgt wird, ist der Begriff Normales Modell wird verwendet, um sich auf eine Interpretation zu beziehen, bei der keine unterschiedlichen Individuen a und b erfüllen a = b. In der Logik erster Ordnung mit Gleichheit werden nur normale Modelle berücksichtigt, und so gibt es keinen Begriff für ein anderes Modell als ein normales Modell. Wenn Logik erster Ordnung ohne Gleichheit untersucht wird, muss die Ergebnisse der Ergebnisse wie die geändert werden Löwenheim -Skolem -Theorem so dass nur normale Modelle berücksichtigt werden.

Logik erster Ordnung ohne Gleichheit wird häufig im Kontext von verwendet Arithmetik zweiter Ordnung und andere Arithmetische Theorien höherer Ordnung, bei denen die Gleichstellungsbeziehung zwischen natürlichen Zahlen normalerweise weggelassen wird.

Gleichheit innerhalb einer Theorie definieren

Wenn eine Theorie eine binäre Formel hat A(x,y) das Reflexivität und Leibnizs Gesetz erfüllt, soll die Theorie Gleichheit haben oder eine Theorie mit Gleichheit sein. Die Theorie hat möglicherweise nicht alle Fälle der obigen Schemata als Axiome, sondern als abgeleitbare Theoreme. In Theorien ohne Funktionsymbole und einer begrenzten Anzahl von Beziehungen ist es beispielsweise möglich zu definieren Gleichheit in Bezug auf die Beziehungen durch Definition der beiden Begriffe s und t gleich sein, wenn eine Beziehung durch Änderung unverändert bleibt s zu t in jedem Argument.

Einige Theorien erlauben andere ad hoc Definitionen der Gleichheit:

• In der Theorie von Teilaufträge Mit einem Beziehungssymbol ≤ könnte man definieren s = t Abkürzung sein s ≤ t ∧ t ≤ s.
• In der festgelegten Theorie mit einer Beziehung ∈ kann man definieren s = t Abkürzung sein ∀x (s ∈ x ↔ t ∈ x) ∧ ∀x (x ∈ s ↔ x ∈ t). Diese Definition der Gleichheit erfüllt dann automatisch die Axiome für die Gleichheit. In diesem Fall sollte man das übliche ersetzen Axiom der Verlängerung, was als angegeben werden kann als $oder$mit einer alternativen Formulierung $oder$, was sagt das, wenn es setzt x und y haben die gleichen Elemente, dann gehören sie auch zu denselben Sätzen.

Metallogische Eigenschaften

Eine Motivation für die Verwendung der Logik erster Ordnung und nicht für die Logik erster Ordnung und nicht für die Logik erster Ordnung und nicht für Logik höherer Ordnung, ist diese Logik erster Ordnung viele hat viele metallogisch Eigenschaften, die stärkere Logiken nicht haben. Diese Ergebnisse betreffen die allgemeinen Eigenschaften der Logik erster Ordnung selbst und nicht die Eigenschaften einzelner Theorien. Sie bieten grundlegende Werkzeuge für die Konstruktion von Modellen erster Ordnung Theorien erster Ordnung.

Vollständigkeit und Unentschlossenheit

Gödels Vollständigkeitstheorem, bewiesen von Kurt Gödel Im Jahr 1929 legt fest, dass es fundierte, vollständige, effektive deduktive Systeme für die Logik erster Ordnung gibt, und daher wird die logische Konsequenzbeziehung erster Ordnung durch endliche Vorbereitung erfasst. Naiv, die Aussage, dass eine Formel φ logischerweise eine Formel ψ impliziert, hängt von jedem Modell von φ ab; Diese Modelle werden im Allgemeinen von willkürlich großer Kardinalität sein, und daher kann die logische Konsequenz nicht effektiv überprüft werden, indem jedes Modell überprüft wird. Es ist jedoch möglich, alle endlichen Ableitungen aufzuzählen und nach einer Ableitung von ψ aus φ zu suchen. Wenn ψ durch φ logisch impliziert wird, wird eine solche Ableitung schließlich gefunden. Somit ist die logische Konsequenz erster Ordnung halbkassbar: Es ist möglich, eine wirksame Aufzählung aller Sätzepaare (φ, ψ) so zu erstellen, dass ψ eine logische Folge von φ ist.

nicht wie AussagelogikLogik erster Ordnung ist unentscheidbar (Obwohl halbkindlich), sofern die Sprache mindestens ein Prädikat von Arity mindestens 2 (außer Gleichheit) hat. Dies bedeutet, dass es keine gibt Entscheidungsverfahren Dies bestimmt, ob willkürliche Formeln logisch gültig sind. Dieses Ergebnis wurde unabhängig von Alonzo -Kirche und Alan Turing In den Jahren 1936 bzw. 1937 geben Sie die negative Antwort auf die Entscheidungsproblem posiert von David Hilbert und Wilhelm Ackermann Im Jahr 1928 zeigen ihre Beweise einen Zusammenhang zwischen der Unlösbarkeit des Entscheidungsproblems für die Logik erster Ordnung und der Unlösbarkeit der Problem stoppen.

Es gibt Systeme, die schwächer sind als die volle Logik erster Ordnung, für die die logische Konsequenzbeziehung logisch ist. Dazu gehören die Propositionslogik und Monadische Prädikatlogik, die Logik erster Ordnung ist, die auf unäre Prädikatsymbole und keine Funktionsymbole beschränkt ist. Andere Logik ohne Funktionsymbole, die lichtbar sind, sind die Bewachter Fragment der Logik erster Ordnung sowie Zwei-Variable-Logik. Das Bernays -Schönfinkel -Klasse von Formeln erster Ordnung ist ebenfalls entzündbar. Logik erster Ordnung erster Ordnung werden ebenfalls im Rahmen untersucht Beschreibung Logik.

Der Löwenheim -Skolem -Theorem

Das Löwenheim -Skolem -Theorem zeigt das, wenn eine Theorie erster Ordnung von Kardinalität λ hat ein unendliches Modell, dann hat es Modelle jeder unendlichen Kardinalität größer oder gleich λ. Eines der frühesten Ergebnisse in ModelltheorieDies impliziert, dass es nicht möglich ist, zu charakterisieren Zählbarkeit oder Unzählbarkeit in einer Sprache erster Ordnung mit einer zählbaren Signatur. Das heißt, es gibt keine Formel erster Ordnung φ (x) so dass eine willkürliche Struktur m φ erfüllt, wenn und nur wenn der Diskursbereich von m zählbar ist (oder im zweiten Fall unzähliger).

Das Löwenheim -Skolem -Theorem impliziert, dass unendliche Strukturen nicht sein können kategorisch Axiomatisiert in Logik erster Ordnung. Zum Beispiel gibt es keine Theorie erster Ordnung, deren einziges Modell die reale Zeile ist: Jede Theorie erster Ordnung mit einem unendlichen Modell hat auch ein Modell der Kardinalität, das größer ist als das Kontinuum. Da die reale Linie unendlich ist, ist jede Theorie, die von der realen Linie erfüllt ist Nicht standardmäßige Modelle. Wenn der Theorem von Löwenheim-Skolem auf festgelegte Theorien erster Ordnung angewendet wird, werden die nicht intuitiven Konsequenzen als bezeichnet als Skolems Paradoxon.

Der Kompaktheitstheorem

Das Kompaktheitstheorem Gibt an, dass eine Reihe von Sätzen erster Ordnung ein Modell hat, wenn und nur dann eine endliche Teilmenge davon ein Modell.^[25] Dies bedeutet, dass, wenn eine Formel eine logische Folge eines unendlichen Satzes von Axiomen erster Ordnung ist, eine logische Folge einer endlichen Anzahl dieser Axiome ist. Dieser Satz wurde von Kurt Gödel als Folge des Vollständigkeitssatzes zuerst bewiesen, aber im Laufe der Zeit wurden viele zusätzliche Beweise erhalten. Es ist ein zentrales Instrument in der Modelltheorie, das eine grundlegende Methode zum Konstruktion von Modellen bietet.

Der Kompaktheitstheorem hat einen begrenzenden Effekt, welcher Sammlungen von Strukturen erster Ordnung Elementarklassen sind. Zum Beispiel impliziert der Kompaktheitstheorem, dass jede Theorie mit willkürlich großen endlichen Modellen ein unendliches Modell hat. Somit die Klasse aller endlichen Grafiken ist keine Elementarklasse (dasselbe gilt für viele andere algebraische Strukturen).

Es gibt auch subtilere Einschränkungen der Logik erster Ordnung, die durch den Kompaktheitstheorem impliziert werden. Zum Beispiel können in der Informatik viele Situationen als modelliert werden gerichteter Graph von Zuständen (Knoten) und Verbindungen (gerichtete Kanten). Die Überprüfung eines solchen Systems kann zeigen, dass kein "schlechter" Zustand aus einem "guten" Zustand erreicht werden kann. So versucht man festzustellen, ob die guten und schlechten Zustände unterschiedlich sind verbundene Komponenten der Grafik. Der Kompaktheitstheorem kann jedoch verwendet werden, um zu zeigen, dass angeschlossene Graphen keine Elementarklasse in Logik erster Ordnung sind und es keine Formel φ gibt (x,y) der Logik erster Ordnung in der Logik der Grafiken, das drückt die Idee aus, dass es einen Weg gibt x zu y. Verbundenheit kann in ausgedrückt werden in Logik zweiter Ordnungjedoch, aber nicht nur mit existenziellen Mengenquantifizierern als ${\ displaystyle \ sigma _ {1}^{1}}$ genießt auch Kompaktheit.

Lindströms Satz

Per Lindström zeigten, dass die gerade diskutierten metallogischen Eigenschaften tatsächlich die Logik erster Ordnung in dem Sinne charakterisieren, dass keine stärkere Logik auch diese Eigenschaften haben kann (Ebbinghaus und Flum 1994, Kapitel XIII). Lindström definierte eine Klasse abstrakter logischer Systeme und eine strenge Definition der relativen Stärke eines Mitglieds dieser Klasse. Er gründete zwei Theoreme für Systeme dieser Art:

• Ein logisches System, das die Definition von Lindström erfüllt, die Logik erster Ordnung enthält und sowohl den Löwenheim-Skolem-Theorem als auch das Kompaktheitstheorem erfüllt, muss der Logik erster Ordnung gleich sein.
• Ein logisches System, das die Definition von Lindström erfüllt, die eine halbkindliche logische Konsequenzbeziehung aufweist und den Löwenheim-Skolem-Theorem erfüllt, muss der Logik erster Ordnung entsprechen.

Einschränkungen

Obwohl die Logik erster Ordnung ausreicht, um einen Großteil der Mathematik zu formalisieren und in Informatik und anderen Bereichen üblicherweise verwendet wird, hat sie bestimmte Einschränkungen. Dazu gehören Einschränkungen der Ausdruckskraft und Einschränkungen der Fragmente natürlicher Sprachen, die sie beschreiben können.

Beispielsweise ist die Logik erster Ordnung unentscheidbar, was bedeutet, dass ein solider, vollständiger und beendiger Entscheidungsalgorithmus für die Bekanntheit unmöglich ist. Dies hat zur Untersuchung interessanter lehender Fragmente wie C geführt₂: Logik erster Ordnung mit zwei Variablen und der Quantifizierer zählen ${\ displayStyle \ existiert ^{\ Geq n}}$ und ${\ displayStyle \ existiert ^{\ leq n}}$.^[26]

Ausdruckskraft

Das Löwenheim -Skolem -Theorem zeigt, dass eine Theorie erster Ordnung ein unendliches Modell erscheint, sie unendliche Modelle für jede Kardinalität hat. Insbesondere kann keine Theorie erster Ordnung mit einem unendlichen Modell sein Kategorisch. Daher gibt es keine Theorie erster Ordnung, deren einziges Modell die natürliche Zahlen als Domäne hat oder deren einziges Modell die reelle Zahlen als Domäne hat. Viele Erweiterungen der Logik erster Ordnung, einschließlich unendlicher Logik und Logik höherer Ordnung, sind in dem Sinne, dass sie kategoriale Axiomatisierungen der natürlichen Zahlen oder realen Zahlen ermöglichen, ausdrucksstarker. Diese Ausdruckskraft ist jedoch metallogisch kosten: von Lindströms SatzDer Kompaktheitstheorem und der Abwärts-Theorem von Löwenheim-Skolem können in keiner Logik stärker sein als erster Ordnung.

Formalisierung natürlicher Sprachen

Logik erster Ordnung ist in der Lage, viele einfache Quantifiziererkonstruktionen in der natürlichen Sprache zu formalisieren, wie "jeder Mensch, der in Perth in Australien lebt". Daher wird die Logik erster Ordnung als Grundlage für die Grundlage verwendet Wissensrepräsentationssprachen, wie zum Beispiel Fo (.).

Dennoch gibt es komplizierte Merkmale der natürlichen Sprache, die in Logik erster Ordnung nicht ausgedrückt werden können. "Jedes logische System, das als Instrument für die Analyse der natürlichen Sprache geeignet ist, benötigt eine viel reichhaltigere Struktur als Prädikat-Logik erster Ordnung."^[27]

Einschränkungen, Erweiterungen und Variationen

Es gibt viele Variationen der Logik erster Ordnung. Einige davon sind in dem Sinne, dass sie die Notation lediglich verändern, ohne die Semantik zu beeinflussen. Andere verändern die ausdrucksstarke Kraft deutlicher, indem sie die Semantik durch zusätzliche Quantifizierer oder andere neue logische Symbole erweitern. In unendlichen Logiken ermöglichen die unendliche Logik Formeln von unendlicher Größe, und modale Logiken fügen Symbole für Möglichkeiten und Notwendigkeit hinzu.

Eingeschränkte Sprachen

Logik erster Ordnung kann in Sprachen mit weniger logischen Symbolen untersucht werden als oben beschrieben.

• Da ${\ displayStyle \ existiert x \ varphi (x)}$ kann ausgedrückt werden als ${\ displaystyle \ neg \ forall x \ neg \ varphi (x)}$, und ${\ displaystyle \ forall x \ varphi (x)}$ kann ausgedrückt werden als ${\ displayStyle \ neg \ existiert x \ neg \ varphi (x)}$, einer der beiden Quantifizierer ${\ displayStyle \ existiert}$ und ${\ displayStyle \ forall}$ kann fallen gelassen werden.
• Seit ${\ displaystyle \ varphi \ lor \ psi}$ kann ausgedrückt werden als ${\ displayStyle \ lnot (\ lnot \ varphi \ land \ lnot \ psi)}$ und ${\ displaystyle \ varphi \ land \ psi}$ kann ausgedrückt werden als ${\ displayStyle \ lnot (\ lnot \ varphi \ lor \ lnot \ psi)}$, entweder ${\ displayStyle \ vee}$ oder ${\ displayStyle \ Wedge}$ kann fallen gelassen werden. Mit anderen Worten, es reicht aus zu haben ${\ displayStyle \ neg}$ und ${\ displayStyle \ vee}$, oder ${\ displayStyle \ neg}$ und ${\ displayStyle \ Wedge}$, als einzige logische Konnektiv.
• Ebenso reicht es aus, nur zu haben ${\ displayStyle \ neg}$ und ${\ displayStyle \ rightarrow}$ als logische Verbindungen oder nur die haben Sheffer Schlaganfall (Nand) oder die Peirce Pfeil (Noch) Operator.
• Es ist möglich, Funktionsymbole und konstante Symbole vollständig zu vermeiden und sie über Prädikatsymbole auf angemessene Weise neu zu schreiben. Zum Beispiel anstatt ein konstantes Symbol zu verwenden ${\ displayStyle \; 0}$ Man kann ein Prädikat verwenden ${\ displayStyle \; 0 (x)}$ (Interpretiert als ${\ displayStyle \; x = 0}$ ) und jedes Prädikat ersetzen wie z. ${\ displayStyle \; p (0, y)}$ mit ${\ displayStyle \ forall x \; (0 (x) \ rightarrow p (x, y))}$. Eine Funktion wie z. ${\ displayStyle f (x_ {1}, x_ {2}, ..., x_ {n})}$ wird in ähnlicher Weise durch ein Prädikat ersetzt ${\ displayStyle f (x_ {1}, x_ {2}, ..., x_ {n}, y)}$ Interpretiert als ${\ displayStyle y = f (x_ {1}, x_ {2}, ..., x_ {n})}$. Diese Änderung erfordert das Hinzufügen zusätzlicher Axiome in die jeweilige Theorie, so dass die Interpretationen der verwendeten Prädikatsymbole die richtige Semantik aufweisen.^[28]

Einschränkungen wie diese sind als Technik nützlich, um die Anzahl der Inferenzregeln oder Axiomschemata in deduktiven Systemen zu verringern, was zu kürzeren Beweisen metallogischer Ergebnisse führt. Die Kosten für die Einschränkungen sind, dass es schwieriger wird, natürliche Aussagen im vorliegenden System auszudrücken, da die in den natürlichen Sprachanweisungen verwendeten logischen Konnektiven durch ihre (längeren) Definitionen in Bezug auf die eingeschränkte Sammlung von ersetzt werden müssen Logische Verbindungen. In ähnlicher Weise können Ableitungen in den begrenzten Systemen länger sein als Ableitungen in Systemen, die zusätzliche Konnektiven enthalten. Es gibt daher einen Kompromiss zwischen der einfachen Arbeit innerhalb des formalen Systems und der einfachen Nachweis von Ergebnissen über das formale System.

Es ist auch möglich, die Arten von Funktionssymbolen und Prädikatsymbolen in ausreichend ausdrucksstarken Theorien einzuschränken. Man kann im Prinzip vollständig mit Funktionen der Arität von mehr als 2 und Prädikaten der Arität größer als 1 in Theorien, die a Paarungsfunktion. Dies ist eine Funktion von Arity 2, die Elementpaare der Domäne annimmt und eine zurückgibt geordnetes Paar sie enthalten. Es reicht auch aus, zwei Prädikatsymbole von Arity 2 zu haben, die Projektionsfunktionen von einem geordneten Paar zu seinen Komponenten definieren. In beiden Fällen ist es notwendig, dass die natürlichen Axiome für eine Paarungsfunktion und ihre Projektionen erfüllt sind.

Viele sortierte Logik

Gewöhnliche Interpretationen erster Ordnung haben einen einzelnen Diskursbereich, über den alle Quantifizierer reichen. Logik erster Ordnung ermöglicht Variablen unterschiedlich zu haben Sorts, die unterschiedliche Domänen haben. Dies wird auch genannt Tippte Logik erster Ordnungund die Art genannt Typen (wie in Datentyp), aber es ist nicht dasselbe wie erster Ordnung Typentheorie. Viele sortierte Logik erster Ordnung werden häufig in der Untersuchung von verwendet Arithmetik zweiter Ordnung.^[29]

Wenn es in einer Theorie nur endlich viele Arten gibt, kann eine Logik erster Ordnung erster Ordnung auf eine Logik erster Ordnung erster Ordnung reduziert werden.^{[30]: 296–299} Man stellt in die einsortierte Theorie ein einheitliches Prädikat-Symbol für jede Sorte in der vielen sortierten Theorie ein und fügt ein Axiom hinzu, dass diese unären Prädikate den Diskursbereich aufteilt. Wenn es beispielsweise zwei Arten gibt, fügt man Prädikat -Symbole hinzu ${\ displayStyle p_ {1} (x)}$ und ${\ displayStyle p_ {2} (x)}$ und das Axiom

$oder$.

Dann befriedigend die Elemente ${\ displayStyle p_ {1}}$ werden als Elemente der ersten Art und Elemente befriedigt, die befriedigt werden ${\ displayStyle p_ {2}}$ als Elemente der zweiten Art. Man kann über jede Sortierung über das entsprechende Prädikatsymbol quantifizieren, um den Quantifizierungsbereich zu begrenzen. Zum Beispiel zu sagen, dass es ein Element der ersten Sorte gibt, die die Formel φ erfüllen (x) schreibt man

${\ displayStyle \ existiert x (p_ {1} (x) \ land \ varphi (x))}$.

Zusätzliche Quantifizierer

Zusätzliche Quantifizierer können zur Logik erster Ordnung hinzugefügt werden.

• Manchmal ist es nützlich zu sagen "P(x) hält genau einen x", was ausgedrückt werden kann als ∃!x P(x). Diese Notation, genannt Einzigartigkeitsquantifizierung, kann genommen werden, um eine Formel wie abzukürzen, z. ∃x (P(x) ∧∀y (P(y) → (x = y))).
• Logik erster Ordnung mit zusätzlichen Quantifizierern hat neue Quantifizierer QX, ..., mit Bedeutungen wie "Es gibt viele x so dass ... ". Auch sehen Verzweigungsquantifizierer und die Pluralquantifizierer von George Boolos und andere.
• Begrenzte Quantifizierer werden oft in der Untersuchung der festgelegten Theorie oder der Arithmetik verwendet.

Infinitarische Logik

Die unendliche Logik ermöglicht unendlich lange Sätze. Zum Beispiel kann man eine Konjunktion oder Disjunktion unendlich viele Formeln oder eine Quantifizierung über unendlich viele Variablen ermöglichen. Unendlich lange Sätze entstehen in Bereichen Mathematik, einschließlich Topologie und Modelltheorie.

Die unendliche Logik verallgemeinert die Logik erster Ordnung, um Formeln der unendlichen Länge zu ermöglichen. Die häufigste Art und Weise, wie Formeln unendlich werden können, sind unendliche Konjunktionen und Unterbrechungen. Es ist jedoch auch möglich, verallgemeinerte Signaturen zuzulassen, in denen Funktionen und Beziehungssymbole unendliche Arten haben oder in denen Quantifizierer unendlich viele Variablen binden können. Da eine unendliche Formel nicht durch eine endliche Zeichenfolge dargestellt werden kann, ist es notwendig, eine andere Darstellung von Formeln auszuwählen. Die übliche Darstellung in diesem Zusammenhang ist ein Baum. So werden Formeln im Wesentlichen mit ihren analysierten Bäumen und nicht mit den analysierten Saiten identifiziert.

Die am häufigsten untersuchten unendlichen Logiken werden bezeichnet L_αβ, wo α und β jeweils sind Kardinalzahlen oder das Symbol ∞. In dieser Notation ist die gewöhnliche Logik erster Ordnung erster Ordnung L_ωω. In der Logik L_∞ω, willkürliche Konjunktionen oder Disjunktionen sind beim Erstellen von Formeln zulässig, und es gibt eine unbegrenzte Versorgung mit Variablen. Allgemeiner ist die Logik, die Konjunktionen oder Ableitungen mit weniger als κ -Bestandteilen erlaubt, als bekannt als L_κω. Zum Beispiel, L_ω1ω Genehmigung zählbar Konjunktionen und Ableitungen.

Der Satz freier Variablen in einer Formel von L_κω Kann jede Kardinalität streng weniger als κ haben, doch nur endlich viele von ihnen können im Rahmen eines Quantifizierers sein, wenn eine Formel als Subformel eines anderen erscheint.^[31] In anderen unendlichen Logiken kann eine Subformulierung im Bereich unendlich vieler Quantifizierer liegen. Zum Beispiel in L_κoleEin einzelner universeller oder existenzieller Quantifizierer kann willkürlich viele Variablen gleichzeitig binden. Ebenso die Logik L_κλ Ermöglicht die gleichzeitige Quantifizierung über weniger als λ -Variablen sowie Konjunktionen und Disjunktionen der Größe weniger als κ.

Nicht klassische und modale Logik

• Intuitionistische Logik erster Ordnung Verwendet eher intuitionistische als klassische Aussagenrechnung; Zum Beispiel muss ¬? nicht φ gleichwertig sein.
• Erste Bestellung Modale Logik Ermöglicht es einem, andere mögliche Welten sowie diese bedingend wahre Welt zu beschreiben, in der wir leben. In einigen Versionen variiert die mögliche Welten je nach möglicher Welt. Modale Logik hat zusätzliche Modale Operatoren mit Bedeutungen, die informell charakterisiert werden können, wie beispielsweise "es ist notwendig, dass φ" (in allen möglichen Welten wahr) und "es ist möglich, dass φ" (in einer möglichen Welt wahr). Bei der Standard-Logik erster Ordnung haben wir eine einzelne Domäne und jedem Prädikat wird eine Erweiterung zugewiesen. Mit modaler Logik erster Ordnung haben wir a Domänenfunktion Das weist jeder möglichen Welt ihre eigene Domäne zu, so dass jedes Prädikat nur relativ zu diesen möglichen Welten eine Erweiterung erhält. Dies ermöglicht es uns, Fälle zu modellieren, in denen Alex beispielsweise ein Philosoph ist, aber möglicherweise ein Mathematiker war und möglicherweise überhaupt nicht existiert hat. In der ersten möglichen Welt P(a) ist in der zweiten wahr P(a) ist falsch und in der dritten möglichen Welt gibt es keine a überhaupt in der Domäne.
• Fuzzy Logics erster Ordnung sind Erweiterungen erster Ordnung von Supositional Fuzzy Logics als klassisch Propositionalkalkül.

FixPoint -Logik

FixPoint Logic erweitert die Logik erster Ordnung, indem der Schließ unter den geringsten festen Punkten positiver Operatoren hinzugefügt wird.^[32]

Logik höherer Ordnung

Das charakteristische Merkmal der Logik erster Ordnung ist, dass Individuen quantifiziert werden können, aber nicht Prädikate. Daher

${\ displayStyle \ existiert a ({\ text {Phil}} (a))}$

ist eine rechtliche Formel erster Ordnung, aber

${\ displayStyle \ existiert {\ text {Phil}} ({\ text {Phil}} (a))}$

ist nicht in den meisten Formalisierungen der Logik erster Ordnung. Logik zweiter Ordnung Erweitert die Logik erster Ordnung, indem die letztere Quantifizierungsart hinzugefügt wird. Sonstiges Logik höherer Ordnung Quantifizierung über noch höher ermöglichen Typen als Logik der zweiten Ordnung erlaubt. Diese höheren Typen umfassen Beziehungen zwischen Beziehungen, Funktionen von Beziehungen zu Beziehungen zwischen Beziehungen und anderen höheren Objekten. Somit beschreibt die "erste" Logik erster Ordnung die Art der Objekte, die quantifiziert werden können.

Im Gegensatz zur Logik erster Ordnung, für die nur eine Semantik untersucht wird, gibt es mehrere mögliche Semantik für die Logik zweiter Ordnung. Die am häufigsten verwendete Semantik für die Logik zweiter Ordnung und höherer Ordnung ist bekannt als vollständige Semantik. Die Kombination von zusätzlichen Quantifizierern und der vollständigen Semantik für diese Quantifizierer macht eine Logik höherer Ordnung stärker als Logik erster Ordnung. Insbesondere ist die (semantische) logische Konsequenzbeziehung für die Logik zweiter Ordnung und höherer Ordnung nicht halbkindlich; Es gibt kein effektives Abzugssystem für die Logik zweiter Ordnung, die unter vollem Semantik solide und vollständig ist.

Logik der zweiten Ordnung mit vollständiger Semantik ist ausdrucksstärker als Logik erster Ordnung. Zum Beispiel ist es möglich, Axiomsysteme in Logik zweiter Ordnung zu erstellen, die die natürlichen Zahlen und die reale Linie eindeutig charakterisieren. Die Kosten dieser Ausdruckskraft sind, dass Logik zweiter Ordnung und höherer Ordnung weniger attraktive metallogische Eigenschaften als Logik erster Ordnung aufweisen. Zum Beispiel werden der Theorem von Löwenheim-Skolem und die Kompaktheit der Logik erster Ordnung falsch, wenn sie mit vollem Semantik auf Logik höherer Ordnung verallgemeinert wurden.

Automatisierte Theoremprobe und formale Methoden

Automatisierter Theorem beweisen Bezieht sich auf die Entwicklung von Computerprogrammen, die Ableitungen (formale Beweise) mathematischer Theorems durchsuchen und finden.^[33] Das Finden von Ableitungen ist eine schwierige Aufgabe, weil die Suchraum kann sehr groß sein; Eine umfassende Suche nach jeder möglichen Ableitung ist theoretisch aber möglich, aber rechnerisch unmöglich für viele Systeme von Interesse an Mathematik. So kompliziert Heuristische Funktionen sind entwickelt, um zu versuchen, in kürzerer Zeit eine Ableitung zu finden als eine blinde Suche.

Der damit verbundene Bereich der automatisierten Beweisüberprüfung Verwendet Computerprogramme, um zu überprüfen, ob von Menschen erstellte Beweise korrekt sind. Im Gegensatz zu komplizierten automatisierten Theorem -Provers können Überprüfungssysteme so gering sein, dass ihre Richtigkeit sowohl von Hand als auch durch automatisierte Softwareüberprüfung überprüft werden kann. Diese Validierung des Beweisprüfers ist erforderlich, um das Vertrauen zu geben, dass jede als "korrekte" gekennzeichnete Ableitung tatsächlich korrekt ist.

Einige Beweisprüfungen wie z. Metamath, bestehen darauf, eine vollständige Ableitung als Eingabe zu haben. Andere, wie z. Mizar und IsabelleNehmen Sie eine gut formatierte Proof-Skizze (die möglicherweise noch sehr lang und detailliert sein kann) und füllen Sie die fehlenden Teile aus, indem Sie einfache Beweisanfragen durchführen oder bekannte Entscheidungsverfahren anwenden: Die resultierende Ableitung wird dann durch einen kleinen Kernkern überprüft. Viele solcher Systeme sind in erster Linie für den interaktiven Einsatz durch menschliche Mathematiker bestimmt: Diese sind als bekannt als Proof Assistenten. Sie können auch formale Logik verwenden, die stärker sind als Logik erster Ordnung, wie z. B. Typtheorie. Weil eine vollständige Ableitung eines nicht trivialen Ergebniss zu einem deduktiven System erster Ordnung extrem lang sein wird, wenn ein Mensch schreiben kann,^[34] Die Ergebnisse werden häufig als eine Reihe von Lemmas formalisiert, für die Ableitungen separat konstruiert werden können.

Automatisierte Theoremprover werden ebenfalls verwendet, um implementiert zu werden formelle Überprüfung in Informatik. In dieser Einstellung werden Theorem -Prover verwendet, um die Richtigkeit von Programmen und Hardware wie z. Prozessoren in Bezug auf a Formale Spezifikation. Da eine solche Analyse zeitaufwändig und somit teuer ist, ist sie normalerweise für Projekte reserviert, bei denen eine Fehlfunktion schwerwiegende menschliche oder finanzielle Folgen haben würde.

Für das Problem von Modellprüfung, effizient Algorithmen sind bekannt sich entscheiden Ob eine Finite-Struktur der Eingabe zusätzlich zu einer Formel erster Ordnung erfüllt wird, zusätzlich zu Rechenkomplexität Grenzen: Siehe Modellprüfung § Logik erster Ordnung erster Ordnung.

Siehe auch

Anmerkungen

Verweise

• Rautenberg, Wolfgang (2010), Eine kurze Einführung in die mathematische Logik (3. Aufl.), New York, NY: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Andrews, Peter B. (2002); Eine Einführung in die mathematische Logik und Typtheorie: zur Wahrheit durch Beweise, 2. Aufl., Berlin: Kluwer Academic Publishers. Erhältlich bei Springer.
• Avigad, Jeremy; Donnelly, Kevin; Gray, David; und Raff, Paul (2007); "Ein formell verifizierter Beweis des Primzahl Theorems", ACM -Transaktionen zur Rechenlogik, vol. 9 Nr. 1 doi:10.1145/1297658.1297660
• Barwise, Jon (1977). "Eine Einführung in die Logik erster Ordnung". In Barwise, Jon (Hrsg.). Handbuch der mathematischen Logik. Studien zur Logik und die Grundlagen der Mathematik. Amsterdam, NL: North-Holland (veröffentlicht 1982). ISBN 978-0-444-86388-1.
• Monk, J. Donald (1976). Mathematische Logik. New York, NY: Springer New York. doi:10.1007/978-1-4684-9452-5. ISBN 978-1-4684-9454-9.
• Barwise, Jon; und Etchemendy, John (2000); Sprachnachweis und Logik, Stanford, CA: CSLI -Veröffentlichungen (verteilt von der University of Chicago Press)
• Bocheński, Józef Maria (2007); Eine Précis mathematischer Logik, Dordrecht, NL: D. Reidel, übersetzt aus den französischen und deutschen Ausgaben von Otto Bird
• Ferreirós, José (2001); Der Weg zur modernen Logik - eine Interpretation, Bulletin der symbolischen Logik, Band 7, Ausgabe 4, 2001, S. 441–484, doi:10.2307/2687794, JStor 2687794
• Gamut, L. T. F. (1991),, Logik, Sprache und Bedeutung, Band 2: Intensionale Logik und logische Grammatik, Chicago, Illinois: University of Chicago Press, ISBN 0-226-28088-8
• Hilbert, David; und Ackermann, Wilhelm (1950); Prinzipien der mathematischen Logik, Chelsea (englische Übersetzung von Grundzüge der Theoretischen Logik, 1928 Deutsche Erstausgabe)
• Hodges, Wilfrid (2001); "Klassische Logik I: Logik erster Ordnung", in Goble, Lou (Hrsg.); Der Blackwell -Leitfaden zur philosophischen Logik, Blackwell
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; und Thomas, Wolfgang (1994); Mathematische Logik, Bachelortexte in Mathematik, Berlin, DE/New York, NY: Springer-Verlag, Zweite Ausgabe, ISBN978-0-387-94258-2
• Tarski, Alfred und Givant, Steven (1987); Eine Formalisierung der festgelegten Theorie ohne Variablen. Vol.41 der American Mathematical Society Colloquium Publications, Providence RI: American Mathematical Society, ISBN978-0821810415

Externe Links

• "Prädikatrechnung", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Stanford Encyclopedia of Philosophy: Shapiro, Stewart; "Klassische Logik". Deckt Syntax, Modelltheorie und Metatheorie für Logik erster Ordnung im natürlichen Abzugsstil ab.
• Magnus, P. D.; Forall X: Eine Einführung in die formale Logik. Deckt formale Semantik und Proof-Theorie für Logik erster Ordnung ab.
• Metamath: Ein laufendes Online-Projekt zur Rekonstruktion der Mathematik als riesige Theorie erster Ordnung mit Logik erster Ordnung und die Axiomatische Set -Theorie ZFC. Principia Mathematica modernisiert.
• Podnieks, Karl; Einführung in die mathematische Logik
• Cambridge Mathematical Tripos Notizen (TypeSet von John Fremlin). Diese Notizen decken einen Teil einer Vergangenheit ab Cambridge Mathematical Tripos Der Kurs, der (normalerweise) im dritten Jahr an Studenten unterrichtet wurde. Der Kurs trägt den Titel "Logik, Berechnung und Set -Theorie" und deckt Ordinale und Kardinäle, Posets und Zorns Lemma, Propositionslogik, Prädikatlogik, festgelegte Theorie und Konsistenzprobleme im Zusammenhang mit ZFC und anderen festgelegten Theorien ab.
• Baumschutzgenerator kann Formeln der Logik erster Ordnung durch die validieren oder ungültig machen Semantische Tableaux Methode.