Logik der ersten Ordnung ist ein formelles System, das in Mathematik, Philosophie, Linguistik und Informatik verwendet ist. Es ist auch bekannt als Prädikat-Rechnung der ersten Ordnung, die niedrigere Prädikat-Rechnung, Quantifizierungstheorie und Prädikat-Logik (ein weniger genauer Begriff). Logik der ersten Ordnung ist von der Satzlogik durch seinen Gebrauch von gemessenen Variablen bemerkenswert. Die Logik der ersten Ordnung mit einem angegebenen Gebiet des Gesprächs, über das sich die gemessenen Variablen, ein oder mehr interpretierte Prädikat-Briefe und richtige Axiome erstrecken, die die interpretierten Prädikat-Briefe einschließen, ist eine Theorie der ersten Ordnung.

Die adjektivische "erste Ordnung" unterscheidet Logik der ersten Ordnung von der höherwertigen Logik, in der es Prädikate gibt, die Prädikate oder Funktionen als Argumente haben, oder in dem oder beide des Prädikats quantifiers oder der Funktion quantifiers erlaubt werden. In Theorien der ersten Ordnung werden Prädikate häufig mit Sätzen vereinigt. In interpretierten höherwertigen Theorien können Prädikate als Sätze von Sätzen interpretiert werden.

Es gibt viele deduktive Systeme für die Logik der ersten Ordnung, die gesund sind (alle nachweisbaren Behauptungen sind wahr) und abgeschlossen (alle wahren Behauptungen sind nachweisbar). Obwohl die logische Folge-Beziehung nur halbentscheidbar ist, sind viel Fortschritte im automatisierten Lehrsatz gemacht worden, der sich in der Logik der ersten Ordnung erweist. Logik der ersten Ordnung befriedigt auch mehrere metalogical Lehrsätze, die sie zugänglich der Analyse in der Probetheorie, wie der Löwenheim-Skolem Lehrsatz und der Kompaktheitslehrsatz machen.

Logik der ersten Ordnung ist zu den Fundamenten der Mathematik von großer Bedeutung, weil es die normale formale Logik für axiomatische Systeme ist. Viele allgemeine axiomatische Systeme, wie erste Ordnung Peano arithmetische und axiomatische Mengenlehre, einschließlich der kanonischen Zermelo-Fraenkel Mengenlehre (ZF), können als Theorien der ersten Ordnung formalisiert werden. Keine Theorie der ersten Ordnung hat jedoch die Kraft, um völlig und kategorisch Strukturen mit einem unendlichen Gebiet, wie die natürlichen Zahlen oder die echte Linie zu beschreiben. Kategorische Axiom-Systeme für diese Strukturen können in der stärkeren Logik wie Logik der zweiten Ordnung erhalten werden.

Für eine Geschichte der Logik der ersten Ordnung, und wie es gekommen ist, um die dominierende formale Logik zu sein, sieh José Ferreirós 2001.

Einführung

Während Satzlogikgeschäfte mit einfachen Aussagevorschlägen, Logik der ersten Ordnung zusätzlich Prädikate und Quantifizierung bedeckt.

Ein Prädikat ähnelt einer Funktion, die entweder Wahr oder Falsch zurückkehrt. Denken Sie die folgenden Sätze: "Sokrates ist ein Philosoph" "ist Plato ein Philosoph". In der Satzlogik werden diese als zwei Vorschläge ohne Beziehung, angezeigt zum Beispiel durch p und q behandelt. In der Logik der ersten Ordnung, jedoch, können die Sätze auf eine parallelere Weise mit dem Prädikat Phil (a) ausgedrückt werden, der dass der ein Philosoph vertretene dadurch zu seien Gegenstand behauptet. So, wenn Sokrates dann vertritt, behauptet Phil (a) den ersten Vorschlag, p; wenn stattdessen Plato dann vertritt, behauptet Phil (a) den zweiten Vorschlag, q. Ein Schlüsselaspekt der Logik der ersten Ordnung ist hier sichtbar: Die Schnur "Phil" ist eine syntaktische Entität, die semantische Bedeutung durch das Erklären gegeben wird, dass Phil (a) genau wenn hält eines Philosophen zu sein. Eine Anweisung der semantischen Bedeutung wird eine Interpretation genannt.

Logik der ersten Ordnung erlaubt, über Eigenschaften vernünftig zu urteilen, die durch viele Gegenstände durch den Gebrauch von Variablen geteilt werden. Lassen Sie zum Beispiel Phil (a) behaupten, dass eines Philosophen zu sein, und Schol (a) gelassen hat, behaupten dass eines Gelehrten zu sein. Dann die Formel

:

behauptet dass wenn eines Philosophen zu sein, dann eines Gelehrten zu sein. Das Symbol wird verwendet, um einen bedingten (wenn/dann) Behauptung anzuzeigen. Die Hypothese liegt links vom Pfeil und dem Beschluss nach rechts. Die Wahrheit dieser Formel hängt ab, welcher Gegenstand durch a, und auf den Interpretationen von "Phil" und "Schol" angezeigt wird.

Behauptungen der Form "für jeden a, wenn eines Philosophen zu sein, dann eines Gelehrten zu sein", sowohl den Gebrauch von Variablen als auch den Gebrauch eines quantifier verlangt. Lassen Sie wieder Phil (a) behaupten eines Philosophen zu sein, und lassen Schol (a) behaupten dass eines Gelehrten zu sein. Dann der Satz der ersten Ordnung

:

behauptet das, egal was ein Vertreten, wenn eines Philosophen dann zu sein, Gelehrter ist. Hier, der universale quantifier, drückt die Idee aus, dass der Anspruch in Parenthesen für alle Wahlen von a hält.

Um zu zeigen, dass der Anspruch, "Wenn eines Philosophen zu sein, dann eines Gelehrten zu sein", falsch ist, man sich zeigen würde, gibt es einen Philosophen, der nicht ein Gelehrter ist. Diese Gegenforderung kann mit dem existenziellen quantifier ausgedrückt werden:

:

Hier:

• ist der Ablehnungsmaschinenbediener: Ist wahr, wenn, und nur wenn, mit anderen Worten wenn und nur wenn falsch ist nicht ein Gelehrter zu sein.

• ist der Verbindungsmaschinenbediener: Behauptet dass eines Philosophen und auch nicht eines Gelehrten zu sein.

Die Prädikate Phil (a) und Schol (a) nehmen nur einen Parameter jeder. Logik der ersten Ordnung kann auch Prädikate mit mehr als einem Parameter ausdrücken. Zum Beispiel "gibt es jemanden, der zum Narren gehalten werden kann, kann jedes Mal" als ausgedrückt werden:

:

Hier wird Person (x) interpretiert, um zu bedeuten, dass x eine Person, Zeit (y) ist, um zu bedeuten, dass y ein Moment der Zeit und Canfool (x, y) ist, um zu bedeuten, dass (Person) x in (der Zeit) y zum Narren gehalten werden kann. Für die Klarheit behauptet diese Behauptung, dass es mindestens eine Person gibt, die zu jeder Zeit zum Narren gehalten werden kann, der stärker ist als das Erklären, dass zu jeder Zeit mindestens eine Person besteht, wer zum Narren gehalten werden kann. Das Erklären der Letzteren (dass es immer mindestens eine foolable Person gibt) ist nicht wichtig, ob diese foolable Person immer dasselbe seit allen Momenten der Zeit ist.

Die Reihe des quantifiers ist der Satz von Gegenständen, die verwendet werden können, um sie zu befriedigen. (In den informellen Beispielen in dieser Abteilung wurde die Reihe des quantifiers unangegeben verlassen.) Zusätzlich zum Spezifizieren der Bedeutung von Prädikat-Symbolen wie Person und Zeit muss eine Interpretation einen nichtleeren Satz angeben, der als das Gebiet des Gesprächs oder Weltalls als eine Reihe für den quantifiers bekannt ist. So, wie man sagt, ist eine Behauptung der Form unter einer besonderen Interpretation wahr, wenn es einen Gegenstand im Gebiet des Gesprächs dieser Interpretation gibt, die das Prädikat dass der Interpretationsgebrauch befriedigt, um Bedeutung dem Symbol Phil zuzuteilen.

Syntax

Es gibt zwei Schlüsselteile der ersten Ordnungslogik. Die Syntax bestimmt, welche Sammlungen von Symbolen gesetzliche Ausdrücke in der Logik der ersten Ordnung sind, während die Semantik die Bedeutungen hinter diesen Ausdrücken bestimmt.

Alphabet

Verschieden von natürlichen Sprachen, wie Englisch, ist die Sprache der Logik der ersten Ordnung völlig formell, so dass es mechanisch bestimmt werden kann, ob ein gegebener Ausdruck gesetzlich ist. Es gibt zwei Schlüsseltypen von gesetzlichen Ausdrücken: Begriffe, die intuitiv Gegenstände und Formeln vertreten, die intuitiv Prädikate ausdrücken, die wahr oder falsch sein können. Die Begriffe und Formeln der Logik der ersten Ordnung sind Reihen von Symbolen, die zusammen das Alphabet der Sprache bilden. Als mit allen formellen Sprachen ist die Natur der Symbole selbst außerhalb des Spielraums der formalen Logik; sie werden häufig einfach als Briefe und Zeichensetzungssymbole betrachtet.

Es ist üblich, die Symbole des Alphabetes in logische Symbole zu teilen, die immer dieselbe Bedeutung und nichtlogische Symbole haben, deren sich Bedeutung durch die Interpretation ändert. Zum Beispiel vertritt das logische Symbol immer "und"; es wird als nie interpretiert "oder". Andererseits konnte ein nichtlogisches Prädikat-Symbol wie Phil (x) interpretiert werden, um "x zu bedeuten, ist ein Philosoph" "x ist ein Mann genannt Philip" oder jedes andere unäre Prädikat abhängig von der Interpretation in der Nähe.

Logische Symbole

Es gibt mehrere logische Symbole im Alphabet, die sich durch den Autor ändern, aber gewöhnlich einschließen:

• Die quantifier Symbole und

der

• Die logischen Bindewörter: für die Verbindung, für die Trennung, für die Implikation, für biconditional, für die Ablehnung. Gelegentlich werden andere logische verbindende Symbole eingeschlossen. Einige Autoren, verwenden oder Cpq, statt, und, oder Epq, statt besonders in Zusammenhängen, wo zu anderen Zwecken verwendet wird. Außerdem kann das Hufeisen ersetzen; die dreifache Bar, kann und eine Tilde (~) ersetzen, Np oder Fpq, kann ersetzen; oder Apq kann ersetzen; und &, oder Kpq, kann besonders ersetzen, wenn diese Symbole aus technischen Gründen nicht verfügbar sind.
• Parenthesen, Klammern und andere Zeichensetzungssymbole. Die Wahl solcher Symbole ändert sich abhängig vom Zusammenhang.
• Ein unendlicher Satz von Variablen, die häufig durch Kleinbuchstaben am Ende des Alphabetes x, y, z, … angezeigt sind. Subschriften werden häufig verwendet, um Variablen zu unterscheiden: x, x, x, ….
• Ein Gleichheitssymbol (manchmal, Identitätssymbol) =; sieh die Abteilung auf der Gleichheit unten.

Es sollte bemerkt werden, dass nicht alle diese Symbole erforderlich sind - genügen nur ein der quantifiers, Ablehnung und Verbindung, Variablen, Klammern und Gleichheit. Es gibt zahlreiche geringe Schwankungen, die zusätzliche logische Symbole definieren können:

• Manchmal werden die Wahrheitskonstanten T, Vpq, oder, für "den wahren" und F, Opq, oder, für "den falschen" eingeschlossen. Ohne irgendwelche solche logischen Maschinenbediener der Wertigkeit 0 können diese zwei Konstanten nur mit quantifiers ausgedrückt werden.
• Manchmal werden zusätzliche logische Bindewörter, wie der Schlag von Sheffer, Dpq (NAND), und exklusiv oder, Jpq eingeschlossen.

Nichtlogische Symbole

Die nichtlogischen Symbole vertreten Prädikate (Beziehungen), Funktionen und Konstanten auf dem Gebiet des Gesprächs. Es hat gepflegt, Standardpraxis zu sein, um einen festen, unendlichen Satz von nichtlogischen Symbolen zu allen Zwecken zu verwenden. Eine neuere Praxis soll verschiedene nichtlogische Symbole gemäß der Anwendung verwenden, die man im Sinn hat. Deshalb ist es notwendig geworden, den Satz aller in einer besonderen Anwendung verwendeten nichtlogischen Symbole zu nennen. Diese Wahl wird über eine Unterschrift gemacht.

Die traditionelle Annäherung soll nur einen, unendlich, Satz von nichtlogischen Symbolen (eine Unterschrift) für alle Anwendungen haben. Folglich unter der traditionellen Annäherung gibt es nur eine Sprache der Logik der ersten Ordnung. Diese Annäherung ist noch besonders in philosophisch orientierten Büchern üblich.

1. Für jede ganze Zahl n  0 gibt es eine Sammlung von n-stufigen, oder N-Platz, Prädikat-Symbole. Weil sie Beziehungen zwischen n Elementen vertreten, werden sie auch Beziehungssymbole genannt. Für jeden arity n haben wir eine unendliche Versorgung von ihnen:
2. :P, P, P, P, …
3. Für jede ganze Zahl n  0 gibt es ungeheuer viele n-stufige Funktionssymbole:
4. :f, f, f, f, …

In der zeitgenössischen mathematischen Logik ändert sich die Unterschrift durch die Anwendung. Typische Unterschriften in der Mathematik sind {1, ×} oder gerade {×} für Gruppen, oder {0, 1, +, ×..., t) n Argumente (wo jedes Argument t ein Begriff ist und f ein Funktionssymbol der Wertigkeit n ist), ist ein Begriff. Insbesondere Symbole, die individuelle Konstanten anzeigen, sind 0-ary Funktionssymbole, und sind so Begriffe.

Nur Ausdrücke, die durch begrenzt viele Anwendungen von Regeln 1 und 2 erhalten werden können, sind Begriffe. Zum Beispiel ist kein Ausdruck, der ein Prädikat-Symbol einschließt, ein Begriff.

Formeln

Der Satz von Formeln (hat auch gut gebildete Formeln oder wffs genannt), wird durch die folgenden Regeln induktiv definiert:

1. Prädikat-Symbole. Wenn P ein n-stufiges Prädikat-Symbol ist und t..., t Begriffe dann P sind (t..., t) ist eine Formel.
2. Gleichheit. Wenn das Gleichheitssymbol als ein Teil der Logik betrachtet wird, und t und t Begriffe sind, dann ist t = t eine Formel.
3. Ablehnung. Wenn φ eine Formel ist, dann ist φ eine Formel.
4. Binäre Bindewörter. Wenn φ und ψ Formeln sind, dann (φ ψ) ist eine Formel. Ähnliche Regeln gelten für andere binäre logische Bindewörter.
5. Quantifiers. Wenn φ eine Formel ist und x eine Variable ist, dann und sind Formeln.

Nur Ausdrücke, die durch begrenzt viele Anwendungen von Regeln 1-5 erhalten werden können, sind Formeln. Wie man sagt, sind die bei den ersten zwei Regeln erhaltenen Formeln Atomformeln.

Zum Beispiel,

:

ist eine Formel, wenn f ein unäres Funktionssymbol, P ein unäres Prädikat-Symbol und Q ein dreifältiges Prädikat-Symbol ist. Andererseits, ist nicht eine Formel, obwohl es eine Reihe von Symbolen vom Alphabet ist.

Die Rolle der Parenthesen in der Definition soll sicherstellen, dass jede Formel nur auf eine Weise durch den folgenden die induktive Definition erhalten werden kann (mit anderen Worten, gibt es einen einzigartigen Syntaxanalyse-Baum für jede Formel). Dieses Eigentum ist als einzigartige Lesbarkeit von Formeln bekannt. Es gibt viele Vereinbarung dafür, wo Parenthesen in Formeln verwendet werden. Zum Beispiel verwenden einige Autoren Doppelpunkte oder Schlusspunkte statt Parenthesen, oder ändern die Plätze, in die Parenthesen eingefügt werden. Die besondere Definition jedes Autors muss durch einen Beweis der einzigartigen Lesbarkeit begleitet werden.

Diese Definition einer Formel unterstützt das Definieren einer Funktion nicht, "wenn dann sonst" ite (c, a, b), wo "c" eine Bedingung ausgedrückt als eine Formel ist, die "a" zurückgeben würde, wenn c, und "b" wahr ist, wenn es falsch ist. Das ist, weil sowohl Prädikate als auch Funktionen nur Begriffe als Rahmen akzeptieren können, aber der erste Parameter ist eine Formel. Einige Sprachen haben auf Logik der ersten Ordnung, wie SMT-BEFREIUNGSKAMPF 2.0 gebaut, fügen Sie das hinzu.

Vereinbarung von Notational

Für die Bequemlichkeit ist Vereinbarung über die Priorität der logischen Maschinenbediener entwickelt worden, um das Bedürfnis zu vermeiden, Parenthesen in einigen Fällen zu schreiben. Diese Regeln sind der Ordnung von Operationen in der Arithmetik ähnlich. Eine allgemeine Tagung ist:

• wird der erste bewertet

• und werden folgender bewertet
• Quantifiers werden folgender bewertet

• wird letzt bewertet.

Außerdem kann durch die Definition nicht erforderliche Extrazeichensetzung eingefügt werden, um Formeln leichter zu machen, zu lesen. So die Formel

:

könnte als geschrieben werden

:

In einigen Feldern ist es üblich, klammerlose Darstellung für binäre Beziehungen und Funktionen statt der Präfix-Notation zu verwenden, die oben definiert ist. Zum Beispiel, in der Arithmetik, schreibt man normalerweise "2 + 2 = 4" statt "= (+ (2,2), 4)". Es ist üblich, Formeln in der klammerlosen Darstellung als Abkürzungen für die entsprechenden Formeln in der Präfix-Notation zu betrachten.

Die Definitionen über der klammerlosen Gebrauch-Darstellung für binäre Bindewörter solcher als. Eine weniger allgemeine Tagung ist polnische Notation, in der, und so weiter vor ihren Argumenten aber nicht zwischen ihnen schreibt. Diese Tagung erlaubt allen Zeichensetzungssymbolen, verworfen zu werden. Polnische Notation ist kompakt und elegant, aber in der Praxis selten verwendet, weil es für Menschen hart ist, es zu lesen. In der polnischen Notation, die Formel

:

wird

Freie und bestimmte Variablen

In einer Formel kann eine Variable frei oder bestimmt vorkommen. Intuitiv ist eine Variable in einer Formel frei, wenn sie nicht gemessen wird: In ist Variable x frei, während y gebunden wird. Die freien und bestimmten Variablen einer Formel werden induktiv wie folgt definiert.

1. Atomformeln. Wenn φ eine Atomformel dann x ist, ist in φ frei, wenn, und nur wenn x in φ vorkommt. Außerdem gibt es keine bestimmten Variablen in jeder Atomformel.
2. Ablehnung. x ist in φ frei, wenn, und nur wenn x in φ frei ist. x wird in φ gebunden, wenn, und nur wenn x in φ gebunden wird.
3. Binäre Bindewörter. x ist darin frei (φ ψ), wenn, und nur wenn x entweder in φ oder in ψ frei ist. x wird darin gebunden (φ ψ), wenn, und nur wenn x entweder in φ oder in ψ gebunden wird. Dieselbe Regel gilt für jedes andere binäre Bindewort im Platz dessen.
4. Quantifiers. x ist in y φ frei, wenn, und nur wenn x in φ und x frei ist, ein verschiedenes Symbol von y ist. Außerdem wird x in y φ gebunden, wenn, und nur wenn x y oder x ist, in φ gebunden wird. Dieselbe Regel hält mit im Platz dessen.

Zum Beispiel in x sind y (P (x) Q (x, f (x), z)), x und y gebundene Variablen, z ist eine freie Variable, und w ist kein, weil es in der Formel nicht vorkommt.

Freikeit und Bestimmtkeit können auch zu spezifischen Ereignissen von Variablen in einer Formel spezialisiert werden. Zum Beispiel, in, ist das erste Ereignis von x frei, während das zweite gebunden wird. Mit anderen Worten ist der x darin frei, während darin gebunden wird.

Eine Formel in der Logik der ersten Ordnung ohne freie Variablen wird einen Satz der ersten Ordnung genannt. Das sind die Formeln, die bestimmte Wahrheitswerte unter einer Interpretation haben werden. Zum Beispiel, ob eine Formel wie Phil (x) wahr ist, muss davon abhängen, was x vertritt. Aber der Satz wird entweder wahr oder in einer gegebenen Interpretation falsch sein.

Beispiele

Gruppen von Abelian

In der Mathematik hat die Sprache von befohlenen abelian Gruppen ein unveränderliches Symbol 0, ein unäres Funktionssymbol − ein binäres Funktionssymbol + und ein binäres Beziehungssymbol . Dann:

• Die Ausdrücke + (x, y) und + (x, + (y, − (z))) sind Begriffe. Diese werden gewöhnlich als x + y und x + y &minus geschrieben; z.
• Die Ausdrücke + (x, y) = 0 und  (+ (x, + (y, − (z))), + (x, y)) sind Atomformeln.

:These werden gewöhnlich als x + y = 0 und x + y  z  x + y geschrieben.

• Der Ausdruck ist eine Formel, die gewöhnlich als geschrieben wird

Das Lieben der Beziehung

Es gibt 10 verschiedene Formeln mit 8 verschiedenen Bedeutungen, dieser Gebrauch die Lieben-Beziehung Lxy ("x liebt y.") und der quantifiers  und :

|rowspan = "2" |

|rowspan = "2" || -|| }\

Die logischen matrices vertreten die Formeln für den Fall, dass es fünf Personen gibt, die (vertikale Achse) lieben und (horizontale Achse) geliebt werden können. Abgesehen von den Sätzen 6 und 9/10 sind sie Beispiele. Z.B tritt der Matrixdarstellen-Satz 5 "b ein liebt sich."; der Matrixdarstellen-Satz-7/8 tritt "c ein liebt b."

Es ist wichtig und aufschlussreich, um Satz 1, und 3 zu unterscheiden: In beiden Fällen wird jeder geliebt; aber im ersten Fall wird jeder von jemandem im zweiten Fall geliebt jeder wird von derselben Person geliebt.

Einige Sätze beziehen einander - z.B ein, wenn 3 auch 1 wahr ist, ist aber nicht umgekehrt wahr. (Sieh Diagramm von Hasse)

Semantik

Eine Interpretation einer Sprache der ersten Ordnung teilt eine Denotation allen nichtlogischen Konstanten auf dieser Sprache zu. Es bestimmt auch ein Gebiet des Gesprächs, das die Reihe des quantifiers angibt. Das Ergebnis besteht darin, dass jeder Begriff ein Gegenstand zugeteilt wird, den er vertritt, und jeder Satz ein Wahrheitswert zugeteilt wird. Auf diese Weise stellt eine Interpretation semantische Bedeutung den Begriffen und Formeln der Sprache zur Verfügung. Die Studie der Interpretationen von formellen Sprachen wird formelle Semantik genannt.

Das Gebiet des Gesprächs D ist ein nichtleerer Satz von "Gegenständen" von einer Art. Intuitiv ist eine Formel der ersten Ordnung eine Behauptung über diese Gegenstände; zum Beispiel, setzt die Existenz eines Gegenstands x solch fest, dass das Prädikat P, wo verwiesen, darauf wahr ist. Das Gebiet des Gesprächs ist der Satz von überlegten Gegenständen. Zum Beispiel kann man nehmen, um der Satz von Zahlen der ganzen Zahl zu sein.

Die Interpretation eines Funktionssymbols ist eine Funktion. Zum Beispiel, wenn das Gebiet des Gesprächs aus ganzen Zahlen besteht, kann ein Funktionssymbol f arity 2 als die Funktion interpretiert werden, die die Summe seiner Argumente gibt. Mit anderen Worten wird das Symbol f mit der Funktion I (f) vereinigt, der, in dieser Interpretation, Hinzufügung ist.

Die Interpretation eines unveränderlichen Symbols ist eine Funktion vom Satz-D des eines Elements bis D, der einfach mit einem Gegenstand in D identifiziert werden kann. Zum Beispiel kann eine Interpretation den Wert dem unveränderlichen Symbol zuteilen.

Die Interpretation eines n-stufigen Prädikat-Symbols ist eine Reihe von N-Tupeln von Elementen des Gebiets des Gesprächs. Das bedeutet, dass, in Anbetracht einer Interpretation, eines Prädikat-Symbols und n Elemente des Gebiets des Gesprächs, man erzählen kann, ob das Prädikat auf jene Elemente gemäß der gegebenen Interpretation zutrifft. Zum Beispiel kann eine Interpretation I (P) eines binären Prädikat-Symbols P der Satz von Paaren von solchen ganzen Zahlen sein, dass der erste weniger ist als das zweite. Gemäß dieser Interpretation würde das Prädikat P wahr sein, wenn sein erstes Argument weniger ist als das zweite.

Strukturen der ersten Ordnung

Die allgemeinste Weise, eine Interpretation (besonders in der Mathematik) anzugeben, soll angeben eine Struktur (hat auch ein Modell genannt; sieh unten). Die Struktur besteht aus einem nichtleeren Satz D, der das Gebiet des Gesprächs und einer Interpretation I der nichtlogischen Begriffe der Unterschrift bildet. Diese Interpretation ist selbst eine Funktion:

• Jedes Funktionssymbol f arity n wird eine Funktion I (f) von dazu zugeteilt. Insbesondere jedes unveränderliche Symbol der Unterschrift wird eine Person im Gebiet des Gesprächs zugeteilt.
• Jedes Prädikat-Symbol P arity n wird eine Beziehung I (P) oder, gleichwertig, eine Funktion von dazu zugeteilt. So wird jedes Prädikat-Symbol durch eine GeBoolean-schätzte Funktion auf D interpretiert.

Einschätzung von Wahrheitswerten

Eine Formel bewertet zum wahren oder falschen gegeben eine Interpretation und eine variable Anweisung μ, der ein Element des Gebiets des Gesprächs mit jeder Variable vereinigt. Der Grund, dass eine variable Anweisung erforderlich ist, soll Bedeutungen Formeln mit freien Variablen, solcher als geben. Der Wahrheitswert dieser Formel ändert sich je nachdem, ob x und y dieselbe Person anzeigen.

Erstens kann die variable Anweisung μ zu allen Begriffen der Sprache mit dem Ergebnis erweitert werden, das jeder Begriff zu einem einzelnen Element des Gebiets des Gesprächs kartografisch darstellt. Die folgenden Regeln werden verwendet, um diese Anweisung zu machen:

1. Variablen. Jede Variable x bewertet zu μ (x)
2. Funktionen. Gegebene Begriffe, die zu Elementen des Gebiets des Gesprächs und einem n-stufigen Funktionssymbol f, der Begriff bewertet worden sind, bewerten dazu.

Dann wird jede Formel ein Wahrheitswert zugeteilt. Die induktive Definition, die verwendet ist, um diese Anweisung zu machen, wird das T-Diagramm genannt.

1. Atomformeln (1). Eine Formel wird der Wert wahr oder falsch je nachdem vereinigt, ob, wo die Einschätzung der Begriffe sind und die Interpretation dessen ist, der durch die Annahme eine Teilmenge dessen ist.
2. Atomformeln (2). Eine Formel wird wahr zugeteilt, wenn und zu demselben Gegenstand des Gebiets des Gesprächs bewerten (sieh die Abteilung auf der Gleichheit unten).
3. Logische Bindewörter. Eine Formel in der Form,

\psi </Mathematik>, wird usw. gemäß der Wahrheitstabelle für das fragliche Bindewort, als in der Satzlogik bewertet.

1. Existenzieller quantifiers. Eine Formel ist gemäß der M wahr, und wenn dort eine Einschätzung der Variablen besteht, die sich nur von der Bewertung der Einschätzung von x und solch unterscheidet, dass φ gemäß der Interpretation M und die variable Anweisung wahr ist. Diese formelle Definition gewinnt die Idee, die wenn und nur wahr ist, wenn es eine Weise gibt, einen Wert für solchen x zu wählen, dass φ (x) zufrieden ist.
2. Universaler quantifiers. Eine Formel ist gemäß der M wahr, und wenn φ (x) für jedes durch die Interpretation zusammengesetzte Paar M und eine variable Anweisung wahr ist, die sich von nur auf dem Wert von x unterscheidet. Das gewinnt die Idee, die wahr ist, wenn jede mögliche Wahl eines Werts für x φ (x) veranlasst, wahr zu sein.

Wenn eine Formel freie Variablen nicht enthält, und auch ein Satz ist, dann betrifft die anfängliche variable Anweisung seinen Wahrheitswert nicht. Mit anderen Worten ist ein Satz gemäß der M wahr, und wenn, und nur wenn gemäß der M und jeder anderen variablen Anweisung wahr ist.

Es gibt eine zweite einheitliche Methode zum Definieren von Wahrheitswerten, der sich auf variable Anweisungsfunktionen nicht verlässt. Statt dessen in Anbetracht einer Interpretation M fügt ein erster zur Unterschrift eine Sammlung von unveränderlichen Symbolen, ein für jedes Element des Gebiets des Gesprächs in der M hinzu; sagen Sie, dass für jeden d im Gebiet das unveränderliche Symbol c befestigt wird. Die Interpretation wird erweitert, so dass jedes neue unveränderliche Symbol seinem entsprechenden Element des Gebiets zugeteilt wird. Man definiert jetzt Wahrheit für gemessene Formeln syntaktisch wie folgt:

1. Existenzieller quantifiers (Stellvertreter). Eine Formel ist gemäß der M wahr, wenn es einen d im Gebiet des solchen Gesprächs gibt, der hält. Hier ist das Ergebnis, gegen c jedes freie Ereignis von x in φ auszuwechseln.
2. Universaler quantifiers (Stellvertreter). Eine Formel ist gemäß der M wahr, wenn, für jeden d im Gebiet des Gesprächs, gemäß der M wahr ist.

Diese abwechselnde Annäherung gibt genau dieselben Wahrheitswerte allen Sätzen als die Annäherung über variable Anweisungen.

Gültigkeit, satisfiability, und logische Folge

Wenn ein Satz φ zum Wahren unter einer gegebenen Interpretation M bewertet, sagt man, dass M φ befriedigt; das wird angezeigt. Ein Satz ist satisfiable, wenn es eine Interpretation gibt, unter der es wahr ist.

Satisfiability von Formeln mit freien Variablen ist mehr kompliziert, weil eine Interpretation selbstständig den Wahrheitswert solch einer Formel nicht bestimmt. Die allgemeinste Tagung besteht darin, dass, wie man sagt, eine Formel mit freien Variablen durch eine Interpretation zufrieden ist, wenn die Formel wahr rücksichtslos bleibt, welche Personen vom Gebiet des Gesprächs seinen freien Variablen zugeteilt werden. Das hat dieselbe Wirkung, sagend dass eine Formel zufrieden ist, ob, und nur wenn sein universaler Verschluss zufrieden ist.

Eine Formel ist logisch gültig (oder einfach gültig), wenn es in jeder Interpretation wahr ist. Diese Formeln spielen eine Rolle, die der Tautologie in der Satzlogik ähnlich ist.

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

Algebraizations

Eine abwechselnde Annäherung an die Semantik der Logik der ersten Ordnung geht über die abstrakte Algebra weiter. Diese Annäherung verallgemeinert die Algebra von Lindenbaum-Tarski der Satzlogik. Es gibt drei Weisen, gemessene Variablen von der Logik der ersten Ordnung zu beseitigen, die das Ersetzen quantifiers mit anderen variablen verbindlichen Begriff-Maschinenbedienern nicht einschließen:

• Algebra von Cylindric, durch Alfred Tarski und seine Mitarbeiter;
• Algebra von Polyadic, durch Paul Halmos;
• Prädikat functor Logik, hauptsächlich wegen Willard Quines.

Diese Algebra sind alle Gitter, die richtig die Zwei-Elemente-Algebra von Boolean erweitern.

Tarski und Givant (1987) haben gezeigt, dass das Bruchstück der Logik der ersten Ordnung, die keinen Atomsatz hat, der im Rahmen mehr als drei quantifiers liegt, dieselbe ausdrucksvolle Macht wie Beziehungsalgebra hat. Dieses Bruchstück ist von großem Interesse, weil es für die Arithmetik von Peano und den grössten Teil axiomatischen Mengenlehre einschließlich des kanonischen ZFC genügt. Sie beweisen auch, dass die Logik der ersten Ordnung mit einem primitiven befohlenen Paar zu einer Beziehungsalgebra mit zwei bestellten Paar-Vorsprung-Funktionen gleichwertig ist.

Theorien der ersten Ordnung, Modelle und elementare Klassen

Eine Theorie der ersten Ordnung besteht aus einer Reihe von Axiomen in einer besonderen Unterschrift der ersten Ordnung. Der Satz von Axiomen ist häufig begrenzt oder rekursiv enumerable, in welchem Fall die Theorie wirksam genannt wird. Einige Autoren verlangen Theorien, auch alle logischen Folgen der Axiome einzuschließen.

Wie man

sagt, ist eine Struktur der ersten Ordnung, die alle Sätze in einer gegebenen Theorie befriedigt, ein Modell der Theorie. Eine elementare Klasse ist der Satz aller Strukturen, die eine besondere Theorie befriedigen. Diese Klassen sind ein Hauptthema der Studie in der Mustertheorie.

Viele Theorien haben eine beabsichtigte Interpretation, ein bestimmtes Modell, das beachtet wird, wenn man die Theorie studiert. Zum Beispiel besteht die beabsichtigte Interpretation der Arithmetik von Peano aus den üblichen natürlichen Zahlen mit ihren üblichen Operationen. Jedoch zeigt der Löwenheim-Skolem Lehrsatz, dass die meisten Theorien der ersten Ordnung auch anderen, Sondermodelle haben werden.

Eine Theorie entspricht, wenn es nicht möglich ist, einen Widerspruch von den Axiomen der Theorie zu beweisen. Eine Theorie ist abgeschlossen, wenn, für jede Formel in seiner Unterschrift, entweder diese Formel oder seine Ablehnung eine logische Folge der Axiome der Theorie sind. Der Unvollständigkeitslehrsatz von Gödel zeigt, dass wirksame Theorien der ersten Ordnung, die einen genügend Teil der Theorie der natürlichen Zahlen einschließen, nie sowohl konsequent als auch abgeschlossen sein können.

Leere Gebiete

Die Definition verlangt oben, dass das Gebiet des Gesprächs jeder Interpretation ein nichtleerer Satz sein muss. Es gibt Einstellungen wie einschließliche Logik, wo leere Gebiete erlaubt werden. Außerdem, wenn eine Klasse von algebraischen Strukturen eine leere Struktur einschließt (zum Beispiel, gibt es einen leeren poset), diese Klasse kann nur eine elementare Klasse in der Logik der ersten Ordnung sein, wenn leere Gebiete erlaubt werden oder die leere Struktur von der Klasse entfernt wird.

Es gibt mehrere Schwierigkeiten mit leeren Gebieten jedoch:

• Viele allgemeine Regeln der Schlussfolgerung sind nur gültig, wenn das Gebiet des Gesprächs erforderlich ist, nichtleer zu sein. Ein Beispiel ist die Regel feststellend, dass das einbezieht, wenn x nicht eine freie Variable in φ ist. Diese Regel, die verwendet wird, um Formeln in die prenex normale Form zu stellen, ist in nichtleeren Gebieten gesund, aber ungesund, wenn das leere Gebiet erlaubt wird.
• Die Definition der Wahrheit in einer Interpretation, die eine variable Anweisungsfunktion verwendet, kann mit leeren Gebieten nicht arbeiten, weil es keine variablen Anweisungsfunktionen gibt, deren Reihe leer ist. (Ähnlich kann man nicht Interpretationen unveränderlichen Symbolen zuteilen.) Verlangt diese Wahrheitsdefinition, dass man eine variable Anweisungsfunktion auswählen muss (μ oben), bevor Wahrheitswerte für sogar atomare Formeln definiert werden können. Dann wird der Wahrheitswert eines Satzes definiert, um sein Wahrheitswert unter jeder variablen Anweisung zu sein, und es wird bewiesen, dass dieser Wahrheitswert nicht abhängt, welche Anweisung gewählt wird. Diese Technik arbeitet nicht, wenn es keine Anweisungsfunktionen überhaupt gibt; es muss geändert werden, um leere Gebiete anzupassen.

So, wenn das leere Gebiet erlaubt wird, muss es häufig als ein spezieller Fall behandelt werden. Die meisten Autoren schließen jedoch einfach das leere Gebiet definitionsgemäß aus.

Deduktive Systeme

Ein deduktives System wird verwendet, um auf einer rein syntaktischen Basis zu demonstrieren, dass eine Formel eine logische Folge einer anderen Formel ist. Es gibt viele solche Systeme für die Logik der ersten Ordnung, einschließlich Hilbert-artiger deduktiver Systeme, natürlichen Abzugs, der folgenden Rechnung, der Gemälde-Methode und Entschlossenheit. Diese teilen das allgemeine Eigentum, dass ein Abzug ein begrenzter syntaktischer Gegenstand ist; das Format dieses Gegenstands und die Weise, wie es gebaut wird, ändern sich weit. Diese begrenzten Abzüge selbst werden häufig Abstammungen in der Probetheorie genannt. Sie werden auch häufig Beweise genannt, aber werden verschieden von natürlicher Sprache mathematische Beweise völlig formalisiert.

Ein deduktives System ist gesund, wenn eine Formel, die im System abgeleitet werden kann, logisch gültig ist. Umgekehrt ist ein deduktives System abgeschlossen, wenn jede logisch gültige Formel ableitbar ist. Alle in diesem Artikel besprochenen Systeme sind sowohl Ton als auch abgeschlossen. Sie teilen auch das Eigentum, dass es möglich ist effektiv nachzuprüfen, dass ein angeblich gültiger Abzug wirklich ein Abzug ist; solche Abzug-Systeme werden wirksam genannt.

Ein Schlüsseleigentum von deduktiven Systemen besteht darin, dass sie rein syntaktisch sind, so dass Abstammungen nachgeprüft werden können, ohne jede Interpretation zu denken. So ist ein gesundes Argument in jeder möglichen Interpretation der Sprache trotzdem richtig, ob diese Interpretation über die Mathematik, Volkswirtschaft oder ein anderes Gebiet ist.

Im Allgemeinen ist die logische Folge in der Logik der ersten Ordnung nur halbentscheidbar: Wenn ein Satz logisch einen Satz B dann einbezieht, kann das entdeckt werden (zum Beispiel, durch das Suchen nach einem Beweis, bis einer, mit einem wirksamen, gesunden, ganzen Probesystem gefunden wird). Jedoch, wenn A B nicht logisch einbezieht, bedeutet das nicht, dass logisch die Ablehnung von B einbezieht. Es gibt kein wirksames Verfahren, das, gegeben Formeln A und B, immer richtig entscheidet, ob logisch B einbezieht.

Regeln der Schlussfolgerung

Eine Regel der Schlussfolgerung stellt fest, dass, in Anbetracht einer besonderen Formel (oder Satz von Formeln) mit einem bestimmten Eigentum als eine Hypothese, eine andere spezifische Formel (oder Satz von Formeln) als ein Beschluss abgeleitet werden kann. Die Regel ist gesund (oder Wahrheitsbewahrung), wenn es Gültigkeit im Sinn dass bewahrt, wann auch immer jede Interpretation die Hypothese befriedigt, dass Interpretation auch den Beschluss befriedigt.

Zum Beispiel ist eine allgemeine Regel der Schlussfolgerung die Regel des Ersatzes. Wenn t ein Begriff ist und φ eine Formel ist, die vielleicht die Variable x enthält, dann ist φ [t/x] (hat häufig φ [x/t] angezeigt), das Ergebnis, alle freien Beispiele von x durch t in φ zu ersetzen. Die Ersatz-Regel stellt fest, dass für jeden φ und jeden Begriff t man φ [t/x] aus φ schließen kann vorausgesetzt, dass keine freie Variable von t bestimmt während des Ersatz-Prozesses wird. (Wenn eine freie Variable von t bestimmt wird, dann wechselt man gegen t x aus es ist zuerst notwendig, die bestimmten Variablen von φ zu ändern, um sich von den freien Variablen von t zu unterscheiden.)

Um zu sehen, warum die Beschränkung bestimmter Variablen notwendig ist, betrachten Sie die logisch gültige Formel φ als gegeben durch, in der Unterschrift dessen (0,1, +, ×, =) der Arithmetik. Wenn t der Begriff "x + 1 ist" ist die Formel φ [t/y], der in vielen Interpretationen falsch sein wird. Das Problem besteht darin, dass die freie Variable x t bestimmt während des Ersatzes geworden ist. Der beabsichtigte Ersatz kann durch die Umbenennung der bestimmten Variable x φ zu etwas anderem erhalten werden, z sagen, so dass die Formel nach dem Ersatz ist, der wieder logisch gültig ist.

Die Ersatz-Regel demonstriert mehrere allgemeine Aspekte von Regeln der Schlussfolgerung. Es ist völlig syntaktisch; man kann erzählen, ob es ohne Bitte an eine Interpretation richtig angewandt wurde. Es hat (syntaktisch definierte) Beschränkungen an, wenn es angewandt werden kann, der respektiert werden muss, um die Genauigkeit von Abstammungen zu bewahren. Außerdem, wie häufig der Fall ist, sind diese Beschränkungen wegen Wechselwirkungen zwischen freien und bestimmten Variablen notwendig, die während syntaktischer Manipulationen der an der Interferenzregel beteiligten Formeln vorkommen.

Hilbert-artige Systeme und natürlicher Abzug

Ein Abzug in einem Hilbert-artigen deduktiven System ist eine Liste von Formeln, von denen jede ein logisches Axiom, eine Hypothese ist, die für die Abstammung in der Nähe angenommen worden ist, oder folgt aus vorherigen Formeln über eine Regel der Schlussfolgerung. Die logischen Axiome bestehen aus mehreren Axiom-Schemas von logisch gültigen Formeln; diese umfassen einen bedeutenden Betrag der Satzlogik. Die Regeln der Schlussfolgerung ermöglichen die Manipulation von quantifiers. Typische Hilbert-artige Systeme haben eine kleine Anzahl von Regeln der Schlussfolgerung zusammen mit mehreren unendlichen Schemas von logischen Axiomen. Es ist üblich, nur Modus ponens und universale Generalisation als Regeln der Schlussfolgerung zu haben.

Natürliche Abzug-Systeme ähneln Hilbert-artigen Systemen, in denen ein Abzug eine begrenzte Liste von Formeln ist. Jedoch haben natürliche Abzug-Systeme keine logischen Axiome; sie ersetzen, indem sie zusätzliche Regeln der Schlussfolgerung hinzufügen, die verwendet werden kann, um die logischen Bindewörter in Formeln im Beweis zu manipulieren.

Folgende Rechnung

Die folgende Rechnung wurde entwickelt, um die Eigenschaften von natürlichen Abzug-Systemen zu studieren. Anstatt mit einer Formel auf einmal zu arbeiten, verwendet es Folgen, die Ausdrücke der Form sind

:

wo A..., A, B..., B Formeln sind und das Drehkreuz-Symbol als Zeichensetzung verwendet wird, um die zwei Hälften zu trennen. Intuitiv, eine Folge drücken die Idee aus, die einbezieht.

Gemälde-Methode

Verschieden von den gerade beschriebenen Methoden sind die Abstammungen in der Gemälde-Methode nicht Listen von Formeln. Statt dessen ist eine Abstammung ein Baum von Formeln. Um zu zeigen, dass eine Formel A nachweisbar ist, versucht die Gemälde-Methode zu demonstrieren, dass die Ablehnung von A unsatisfiable ist. Der Baum der Abstammung hat an seiner Wurzel; die Baumzweige in einem Weg, der die Struktur der Formel widerspiegelt. Zum Beispiel, um sich zu zeigen, ist das unsatisfiable verlangt Vertretung, dass C und D jeder unsatisfiable sind; das Entsprechen zu einem sich verzweigenden Punkt im Baum mit dem Elternteil und den Kindern C und D.

Entschlossenheit

Die Entschlossenheitsregel ist eine einzelne Regel der Schlussfolgerung, die, zusammen mit der Vereinigung, gesund und für die Logik der ersten Ordnung abgeschlossen ist. Als mit der Gemälde-Methode wird eine Formel durch die Vertretung bewiesen, dass die Ablehnung der Formel unsatisfiable ist. Entschlossenheit wird im automatisierten Lehrsatz-Beweis allgemein verwendet.

Die Entschlossenheitsmethode arbeitet nur mit Formeln, die Trennungen von Atomformeln sind; willkürliche Formeln müssen zuerst zu dieser Form durch Skolemization umgewandelt werden. Die Entschlossenheitsregel stellt fest, dass aus den Hypothesen und der Beschluss erhalten werden kann.

Nachweisbare Identität

Die folgenden Sätze können "Identität" genannt werden, weil das Hauptbindewort in jedem der biconditional ist.

::::::

: (wo frei in nicht vorkommen muss)

: (wo frei in nicht vorkommen muss)

Gleichheit und seine Axiome

Es gibt mehrere verschiedene Vereinbarung, um Gleichheit (oder Identität) in der Logik der ersten Ordnung zu verwenden. Die allgemeinste Tagung, die als Logik der ersten Ordnung mit der Gleichheit bekannt ist, schließt das Gleichheitssymbol als ein primitives logisches Symbol ein, das immer als die echte Gleichheitsbeziehung zwischen Mitgliedern des Gebiets des Gesprächs interpretiert, solch wird, dass "zwei" gegebenes Mitglieder dasselbe Mitglied sind. Diese Annäherung fügt auch bestimmte Axiome über die Gleichheit zum deduktiven verwendeten System hinzu. Diese Gleichheitsaxiome sind:

1. Reflexivity. Für jede Variable x, x = x.
2. Ersatz für Funktionen. Für alle Variablen x und y und jedes Funktionssymbol f,
3. :x = y  f (..., x...) = f (..., y...).
4. Ersatz für Formeln. Für irgendwelche Variablen x und y und jede Formel φ (x), wenn φ' durch das Ersetzen einer Zahl von freien Ereignissen von x in φ mit y, solch erhalten wird, dass diese freie Ereignisse von y, dann bleiben
5. :x = y  (φ  φ ').

Das sind Axiom-Schemas, von denen jedes einen unendlichen Satz von Axiomen angibt. Das dritte Schema ist als das Gesetz von Leibniz, "der Grundsatz von substitutivity", "der indiscernibility von identicals", oder "das Ersatzeigentum" bekannt. Das zweite Schema, das Funktionssymbol f einschließend, ist (gleichwertig zu) ein spezieller Fall des dritten Schemas, mit der Formel

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

Viele andere Eigenschaften der Gleichheit sind Folgen der Axiome oben zum Beispiel:

1. Symmetrie. Wenn x = y dann y = x.
2. Transitivity. Wenn x = y und y = z dann x = z.

Logik der ersten Ordnung ohne Gleichheit

Eine abwechselnde Annäherung denkt, dass die Gleichheitsbeziehung ein nichtlogisches Symbol ist. Diese Tagung ist als Logik der ersten Ordnung ohne Gleichheit bekannt. Wenn eine Gleichheitsbeziehung in die Unterschrift eingeschlossen wird, müssen die Axiome der Gleichheit jetzt zu den Theorien unter der Rücksicht, wenn gewünscht, hinzugefügt werden, anstatt als Regeln der Logik betrachtet zu werden. Der Hauptunterschied zwischen dieser Methode und Logik der ersten Ordnung mit der Gleichheit ist, dass eine Interpretation jetzt zwei verschiedene Personen als "gleich" interpretieren kann (obwohl, nach dem Gesetz von Leibniz, diese genau dieselben Formeln unter jeder Interpretation befriedigen werden). D. h. die Gleichheitsbeziehung kann jetzt durch eine willkürliche Gleichwertigkeitsbeziehung auf dem Gebiet des Gesprächs interpretiert werden, das in Bezug auf die Funktionen und Beziehungen der Interpretation kongruent ist.

Wenn dieser zweiten Tagung, der Begriff gefolgt wird, den normales Modell verwendet wird, um auf eine Interpretation zu verweisen, wo keine verschiedenen Personen a und b = b befriedigen. In der Logik der ersten Ordnung mit der Gleichheit werden nur normale Modelle betrachtet, und also gibt es keinen Begriff für ein Modell außer einem normalen Modell. Wenn die Logik der ersten Ordnung ohne Gleichheit studiert wird, ist es notwendig, die Behauptungen von Ergebnissen wie der Löwenheim-Skolem Lehrsatz zu amendieren, so dass nur normale Modelle betrachtet werden.

Die Logik der ersten Ordnung ohne Gleichheit wird häufig im Zusammenhang der Arithmetik der zweiten Ordnung und den anderen höherwertigen Theorien der Arithmetik verwendet, wo die Gleichheitsbeziehung zwischen Sätzen von natürlichen Zahlen gewöhnlich weggelassen wird.

Das Definieren der Gleichheit innerhalb einer Theorie

Wenn eine Theorie eine binäre Formel A hat (x, y), der reflexivity und das Gesetz von Leibniz befriedigt, wie man sagt, hat die Theorie Gleichheit, oder ist eine Theorie mit der Gleichheit. Die Theorie kann alle Beispiele der obengenannten Schemas als Axiome, aber eher als ableitbare Lehrsätze nicht haben. Zum Beispiel, in Theorien ohne Funktionssymbole und eine begrenzte Zahl von Beziehungen, ist es möglich, Gleichheit in Bezug auf die Beziehungen, durch das Definieren der zwei Begriffe s und t zu definieren, um gleich zu sein, wenn Beziehung durch das Ändern s zu t in einem Argument unverändert ist.

Einige Theorien erlauben andere Ad-Hoc-Definitionen der Gleichheit:

• In der Theorie von teilweisen Ordnungen mit einem Beziehungssymbol  konnte man s = t definieren, um eine Abkürzung für s  t t  s zu sein.
• In der Mengenlehre mit einer Beziehung kann man s = t definieren, um eine Abkürzung für x (s x t x) x (x s x t) zu sein. Diese Definition der Gleichheit befriedigt dann automatisch die Axiome für die Gleichheit. In diesem Fall sollte man das übliche Axiom von extensionality, durch ersetzen, d. h. wenn x und y dieselben Elemente haben, dann gehören sie denselben Sätzen.

Eigenschaften von Metalogical

Eine Motivation für den Gebrauch der Logik der ersten Ordnung, aber nicht höherwertigen Logik, ist, dass Logik der ersten Ordnung viele metalogical Eigenschaften hat, die stärkere Logik nicht hat. Diese Ergebnisse betreffen allgemeine Eigenschaften der Logik der ersten Ordnung selbst, aber nicht Eigenschaften von individuellen Theorien. Sie stellen grundsätzliche Werkzeuge für den Aufbau von Modellen von Theorien der ersten Ordnung zur Verfügung.

Vollständigkeit und Unentscheidbarkeit

Der Vollständigkeitslehrsatz von Gödel, der von Kurt Gödel 1929 bewiesen ist, stellt fest, dass es gesunde, ganze, wirksame deduktive Systeme für die Logik der ersten Ordnung, und so die erste Ordnung gibt, wird logische Folge-Beziehung durch begrenzten provability gewonnen. Naiv hängt die Behauptung, dass eine Formel φ logisch eine Formel ψ einbezieht, von jedem Modell von φ ab; diese Modelle werden im Allgemeinen willkürlich großen cardinality sein, und so kann logische Folge nicht durch die Überprüfung jedes Modells effektiv nachgeprüft werden. Jedoch ist es möglich, alle begrenzten Abstammungen aufzuzählen und nach einer Abstammung von ψ von φ zu suchen. Wenn ψ durch φ logisch einbezogen wird, wird solch eine Abstammung schließlich gefunden. So ist erste Ordnung logische Folge halbentscheidbar: Es ist möglich, eine wirksame Enumeration aller Paare von Sätzen (φ,ψ) solch zu machen, dass ψ eine logische Folge von φ ist.

Verschieden von der Satzlogik ist Logik der ersten Ordnung unentscheidbar (obwohl halbentscheidbar), vorausgesetzt, dass die Sprache mindestens ein Prädikat von arity mindestens 2 (anders hat als Gleichheit). Das bedeutet, dass es kein Entscheidungsverfahren gibt, das bestimmt, ob willkürliche Formeln logisch gültig sind. Dieses Ergebnis wurde unabhängig von Alonzo Church und Alan Turing 1936 und 1937 gegründet, beziehungsweise eine negative Antwort auf Entscheidungsproblem gebend, der von David Hilbert 1928 aufgestellt ist. Ihre Beweise demonstrieren eine Verbindung zwischen der Unlösbarkeit des Entscheidungsproblems für die Logik der ersten Ordnung und der Unlösbarkeit des stockenden Problems.

Es gibt Systeme, die schwächer sind als volle Logik der ersten Ordnung, für die die logische Folge-Beziehung entscheidbar ist. Diese schließen und monadische Satzlogikprädikat-Logik ein, die Logik der ersten Ordnung ist, die auf unäre Prädikat-Symbole und keine Funktionssymbole eingeschränkt ist. Die Bernays-Schönfinkel Klasse von Formeln der ersten Ordnung ist auch entscheidbar.

Der Löwenheim-Skolem Lehrsatz

Der Löwenheim-Skolem Lehrsatz zeigt, dass, wenn eine Theorie der ersten Ordnung von cardinality λ ein unendliches Modell dann hat, es Modelle jedes unendlichen cardinality größer oder gleich λ hat. Eines der frühsten Ergebnisse in der Mustertheorie, es deutet an, dass es nicht möglich ist, countability oder uncountability auf einer Sprache der ersten Ordnung zu charakterisieren. D. h. es gibt keine Formel der ersten Ordnung φ (x) solch, dass eine willkürliche Struktur M befriedigt φ, wenn, und nur wenn das Gebiet des Gesprächs der M (oder im zweiten Fall zählbar, unzählbar ist).

Der Löwenheim-Skolem Lehrsatz deutet an, dass unendliche Strukturen kategorisch axiomatized in der Logik der ersten Ordnung nicht sein können. Zum Beispiel gibt es keine Theorie der ersten Ordnung, deren nur Modell die echte Linie ist: Jede Theorie der ersten Ordnung mit einem unendlichen Modell hat auch ein Modell von cardinality, der größer ist als das Kontinuum. Da die echte Linie unendlich ist, ist jede durch die echte Linie zufriedene Theorie auch durch einige Sondermodelle zufrieden. Wenn der Löwenheim-Skolem Lehrsatz auf Mengenlehren der ersten Ordnung angewandt wird, sind die nichtintuitiven Folgen als das Paradox von Skolem bekannt.

Der Kompaktheitslehrsatz

Der Kompaktheitslehrsatz stellt fest, dass eine Reihe von Sätzen der ersten Ordnung ein Modell hat, wenn, und nur wenn jede begrenzte Teilmenge davon ein Modell hat. Das deutet dass an, wenn eine Formel eine logische Folge eines unendlichen Satzes von Axiomen der ersten Ordnung ist, dann ist es eine logische Folge von einer begrenzten Zahl jener Axiome. Dieser Lehrsatz wurde erst von Kurt Gödel demzufolge des Vollständigkeitslehrsatzes bewiesen, aber viele zusätzliche Beweise sind mit der Zeit erhalten worden. Es ist ein Hauptwerkzeug in der Mustertheorie, eine grundsätzliche Methode zur Verfügung stellend, um Modelle zu bauen.

Der Kompaktheitslehrsatz hat eine Begrenzungswirkung, auf der Sammlungen von Strukturen der ersten Ordnung elementare Klassen sind. Zum Beispiel deutet der Kompaktheitslehrsatz an, dass jede Theorie, die willkürlich große begrenzte Modelle hat, ein unendliches Modell hat. So ist die Klasse aller begrenzten Graphen nicht eine elementare Klasse (dasselbe hält für viele andere algebraische Strukturen).

Es gibt auch feinere Beschränkungen der Logik der ersten Ordnung, die durch den Kompaktheitslehrsatz einbezogen werden. Zum Beispiel, in der Informatik, können viele Situationen als ein geleiteter Graph von Staaten (Knoten) und Verbindungen (geleitete Ränder) modelliert werden. Bestätigung solch eines Systems kann Vertretung verlangen, dass kein "schlechter" Staat von jedem "guten" Staat erreicht werden kann. So bemüht man sich zu bestimmen, ob die guten und schlechten Staaten in verschiedenen verbundenen Bestandteilen des Graphen sind. Jedoch kann der Kompaktheitslehrsatz verwendet werden, um zu zeigen, dass verbundene Graphen nicht eine elementare Klasse in der Logik der ersten Ordnung sind, und es keine Formel φ (x, y) der Logik der ersten Ordnung in der Unterschrift von Graphen gibt, die die Idee ausdrückt, dass es einen Pfad von x bis y gibt. Zusammenhang kann in der Logik der zweiten Ordnung, jedoch, aber nicht mit nur dem existenziellen Satz quantifiers ausgedrückt werden, weil auch Kompaktheit genießt.

Der Lehrsatz von Lindström

Pro Lindström hat gezeigt, dass die metalogical Eigenschaften gerade besprochen wirklich Logik der ersten Ordnung im Sinn charakterisieren, dass keine stärkere Logik auch jene Eigenschaften (Ebbinghaus und Flum 1994, Kapitel XIII) haben kann. Lindström hat eine Klasse von abstrakten logischen Systemen und eine strenge Definition der Verhältniskraft eines Mitgliedes dieser Klasse definiert. Er hat zwei Lehrsätze für Systeme dieses Typs eingesetzt:

• Ein logisches System, das die Definition von Lindström befriedigt, die Logik der ersten Ordnung enthält und sowohl den Löwenheim-Skolem Lehrsatz als auch den Kompaktheitslehrsatz befriedigt, muss zur Logik der ersten Ordnung gleichwertig sein.
• Ein logisches System, das die Definition von Lindström befriedigt, die eine halbentscheidbare logische Folge-Beziehung hat und den Löwenheim-Skolem Lehrsatz befriedigt, muss zur Logik der ersten Ordnung gleichwertig sein.

Beschränkungen

Obwohl Logik der ersten Ordnung genügend ist, um viel Mathematik zu formalisieren, und in der Informatik und den anderen Feldern allgemein verwendet wird, hat es bestimmte Beschränkungen. Diese schließen Beschränkungen auf sein Ausdrucksvolles und Beschränkungen der Bruchstücke von natürlichen Sprachen ein, die es beschreiben kann.

Ausdrucksvolles

Der Löwenheim-Skolem Lehrsatz zeigt dass, wenn eine Theorie der ersten Ordnung ein unendliches Modell hat, dann hat es unendliche Modelle jedes cardinality. Insbesondere keine Theorie der ersten Ordnung mit einem unendlichen Modell kann kategorisch sein. So gibt es keine Theorie der ersten Ordnung, deren nur Modell den Satz von natürlichen Zahlen als sein Gebiet hat, oder dessen nur Modell den Satz von reellen Zahlen als sein Gebiet hat. Viele Erweiterungen der Logik der ersten Ordnung, einschließlich der infinitary Logik und höherwertigen Logik, sind im Sinn ausdrucksvoller, dass sie wirklich kategorischen axiomatizations der natürlichen Zahlen oder reellen Zahlen erlauben. Dieses Ausdrucksvolle kommt an Metalogical-Kosten jedoch: Durch den Lehrsatz von Lindström können der Kompaktheitslehrsatz und der Löwenheim-Skolem Lehrsatz nach unten in keiner Logik stärker halten als erste Ordnung.

Das Formalisieren von natürlichen Sprachen

Logik der ersten Ordnung ist im Stande, viele einfache quantifier Aufbauten auf natürlicher Sprache, wie "jede Person zu formalisieren, die in Leben von Perth in Australien lebt". Aber es gibt viele mehr komplizierte Eigenschaften der natürlichen Sprache, die in (der einzeln sortierten) Logik der ersten Ordnung nicht ausgedrückt werden kann. "Jedes logische System, das als ein Instrument für die Analyse der natürlichen Sprache passend ist, braucht eine viel reichere Struktur als Prädikat-Logik der ersten Ordnung" (Tonleiter 1991, p. 75).

Beschränkungen, Erweiterungen und Schwankungen

Es gibt viele Schwankungen der Logik der ersten Ordnung. Einige von diesen sind im Sinn unwesentlich, dass sie bloß Notation ändern, ohne die Semantik zu betreffen. Andere ändern die ausdrucksvolle Macht bedeutsamer, durch das Verlängern der Semantik durch zusätzlichen quantifiers oder andere neue logische Symbole. Zum Beispiel, infinitary Logik erlauben Formeln der unendlichen Größe, und modale Logik fügt Symbole für die Möglichkeit und Notwendigkeit hinzu.

Eingeschränkte Sprachen

Logik der ersten Ordnung kann auf Sprachen mit weniger logischen Symbolen studiert werden, als es oben beschrieben wurde.

• Weil als ausgedrückt werden kann, und als, jeder der zwei quantifiers ausgedrückt werden kann und fallen gelassen sein kann.
• Seitdem kann als ausgedrückt werden und kann als ausgedrückt werden, entweder oder kann fallen gelassen sein. Mit anderen Worten ist es genügend zu haben und, oder und als die einzigen logischen Bindewörter.
• Ähnlich ist es genügend, nur und als logische Bindewörter zu haben, oder nur den Schlag von Sheffer (NAND) oder den Pfeil von Peirce (NOCH) Maschinenbediener zu haben.
• Es ist möglich, Funktionssymbole und unveränderliche Symbole völlig zu vermeiden, sie über Prädikat-Symbole auf eine passende Weise umschreibend. Zum Beispiel, anstatt ein unveränderliches Symbol zu verwenden, kann man ein Prädikat (interpretiert als) verwenden, und jedes Prädikat solcher als damit ersetzen. Eine Funktion, die durch ein Prädikat interpretiert als ähnlich ersetzt wird. Diese Änderung verlangt das Hinzufügen von zusätzlichen Axiomen zur Theorie in der Nähe, so dass Interpretationen der verwendeten Prädikat-Symbole die richtige Semantik haben.

Beschränkungen wie diese sind als eine Technik nützlich, um die Anzahl von Interferenzregeln oder Axiom-Schemas in deduktiven Systemen zu vermindern, der zu kürzeren Beweisen von Metalogical-Ergebnissen führt. Die Kosten der Beschränkungen sind, dass es schwieriger wird, Behauptungen der natürlichen Sprache im formellen System in der Nähe auszudrücken, weil die logischen in den Behauptungen der natürlichen Sprache verwendeten Bindewörter durch ihre (längeren) Definitionen in Bezug auf die eingeschränkte Sammlung von logischen Bindewörtern ersetzt werden müssen. Ähnlich können Abstammungen in den beschränkten Systemen länger sein als Abstammungen in Systemen, die zusätzliche Bindewörter einschließen. Es gibt so einen Umtausch zwischen der Bequemlichkeit des Arbeitens innerhalb des formellen Systems und der Bequemlichkeit, Ergebnisse über das formelle System zu beweisen.

Es ist auch möglich, den arities von Funktionssymbolen und Prädikat-Symbolen in genug ausdrucksvollen Theorien einzuschränken. Man kann im Prinzip völlig mit Funktionen von arity dispensieren, der größer ist als 2 und Prädikate von arity, der größer ist als 1 in Theorien, die eine zusammenpassende Funktion einschließen. Das ist eine Funktion von arity 2, der Paare von Elementen des Gebiets nimmt und ein befohlenes Paar zurückgibt, das sie enthält. Es ist auch genügend, zwei Prädikat-Symbole von arity 2 zu haben, die Vorsprung-Funktionen von einem befohlenen Paar zu seinen Bestandteilen definieren. In jedem Fall ist es notwendig, dass die natürlichen Axiome für eine zusammenpassende Funktion und seine Vorsprünge zufrieden sind.

Vielsortierte Logik

Gewöhnliche Interpretationen der ersten Ordnung haben ein einzelnes Gebiet des Gesprächs, über das sich alle quantifiers erstrecken. Vielsortierte Logik der ersten Ordnung erlaubt Variablen, verschiedene Sorten zu haben, die verschiedene Gebiete haben. Das wird auch getippte Logik der ersten Ordnung und die Sorten genannt Typen genannt (als im Datentyp), aber es ist nicht dasselbe als Typ-Theorie der ersten Ordnung. Vielsortierte Logik der ersten Ordnung wird häufig in der Studie der Arithmetik der zweiten Ordnung verwendet.

Wenn es nur begrenzt viele Sorten in einer Theorie gibt, kann vielsortierte Logik der ersten Ordnung auf die einzeln sortierte Logik der ersten Ordnung reduziert werden. Man führt in die einzeln sortierte Theorie ein unäres Prädikat-Symbol für jede Sorte in der vielsortierten Theorie ein, und fügt ein Axiom hinzu sagend, dass diese unären Prädikate das Gebiet des Gesprächs verteilen. Zum Beispiel, wenn es zwei Sorten gibt, fügt man Prädikat-Symbole und und das Axiom hinzu

:.

Dann wird von der Element-Zufriedenheit als Elemente der ersten Sorte und Elemente gedacht, die als Elemente der zweiten Sorte befriedigen. Man kann über jede Sorte messen, indem man das entsprechende Prädikat-Symbol verwendet, um die Reihe der Quantifizierung zu beschränken. Zum Beispiel, um zu sagen, gibt es ein Element der ersten Sorte-Zufriedenheitsformel φ (x), man schreibt

:.

Zusätzlicher quantifiers

Zusätzlicher quantifiers kann zur Logik der ersten Ordnung hinzugefügt werden.

• Manchmal ist es nützlich zu sagen, dass "P (x) für genau einen x hält", der als x P (x) ausgedrückt werden kann. Diese Notation, genannt Einzigartigkeitsquantifizierung, kann genommen werden, um eine Formel wie x (P (x) y (P (y) (x = y))) abzukürzen.
• Die Logik der ersten Ordnung mit zusätzlichem quantifiers hat neuen quantifiers Qx..., mit Bedeutungen solcher als "es gibt viele solche x dass...". Siehe auch das Ausbreiten quantifiers und den Mehrzahlquantifiers von George Boolos und anderen.
• Begrenzte quantifiers werden häufig in der Studie der Mengenlehre oder Arithmetik verwendet.

Logik von Infinitary

Logik von Infinitary erlaubt ungeheuer lange Sätze. Zum Beispiel kann man einer Verbindung oder Trennung von ungeheuer vielen Formeln oder Quantifizierung ungeheuer viele Variablen erlauben. Ungeheuer lange Sätze entstehen in Gebieten der Mathematik einschließlich der Topologie und Mustertheorie.

Logik von Infinitary verallgemeinert Logik der ersten Ordnung, um Formeln der unendlichen Länge zu erlauben. Der allgemeinste Weg, auf den Formeln unendlich werden können, ist durch unendliche Verbindungen und Trennungen. Jedoch ist es auch möglich, verallgemeinerte Unterschriften zuzulassen, in denen Funktion und Beziehungssymbolen erlaubt wird, unendlichen arities zu haben, oder in dem quantifiers ungeheuer viele Variablen binden kann. Weil eine unendliche Formel durch eine begrenzte Schnur nicht vertreten werden kann, ist es notwendig, eine andere Darstellung von Formeln zu wählen; die übliche Darstellung in diesem Zusammenhang ist ein Baum. So werden Formeln im Wesentlichen mit ihren Syntaxanalyse-Bäumen, aber nicht mit den Schnuren identifiziert, die grammatisch analysieren werden.

Die meistens studierte infinitary Logik wird L angezeigt, wo α und β jeder entweder Grundzahlen oder das Symbol  sind. In dieser Notation ist gewöhnliche Logik der ersten Ordnung L.

In der Logik wird L, den willkürlichen Verbindungen oder den Trennungen erlaubt, wenn man Formeln baut, und es gibt eine unbegrenzte Versorgung von Variablen. Mehr allgemein ist die Logik, die Verbindungen oder Trennungen mit weniger erlaubt als κ Bestandteile, als L bekannt. Zum Beispiel erlaubt L zählbare Verbindungen und Trennungen.

Der Satz von freien Variablen in einer Formel von L kann jeden cardinality ausschließlich weniger haben als κ, noch nur begrenzt können viele von ihnen im Rahmen jedes quantifier sein, wenn eine Formel als eine Subformel von einem anderen erscheint. In anderer infinitary Logik kann eine Subformel im Rahmen ungeheuer vieler quantifiers sein. Zum Beispiel, in L, kann ein einzelner universaler oder existenzieller quantifier willkürlich viele Variablen gleichzeitig binden. Ähnlich erlaubt die Logik L gleichzeitige Quantifizierung über weniger als λ Variablen, sowie Verbindungen und Trennungen der Größe weniger als κ.

Nichtklassische und modale Logik

• Logik der ersten Ordnung von Intuitionistic verwendet intuitionistic aber nicht klassische Satzrechnung; zum Beispiel braucht ¬¬φ nicht zu φ gleichwertig zu sein.
• Modale Logik der ersten Ordnung erlaubt, andere mögliche Welten sowie diese abhängig wahre Welt zu beschreiben, die wir bewohnen. In einigen Versionen ändert sich der Satz von möglichen Welten, abhängig von der möglicher Welt man bewohnt. Modale Logik hat modale Extramaschinenbediener mit Bedeutungen, die informell als zum Beispiel charakterisiert werden können, "ist es notwendig, dass φ" (wahr in allen möglichen Welten) und "es dass φ" (wahr in etwas möglicher Welt) möglich ist. Mit der Standardlogik der ersten Ordnung haben wir ein einzelnes Gebiet, und jedes Prädikat wird eine Erweiterung zugeteilt. Mit der ersten Ordnung modale Logik haben wir eine Bereichsfunktion, die jede mögliche Welt sein eigenes Gebiet zuteilt, so dass jedes Prädikat eine Erweiterung nur hinsichtlich dieser möglichen Welten bekommt. Das erlaubt uns Musterfällen, wo, zum Beispiel, Alex ein Philosoph ist, aber ein Mathematiker gewesen sein könnte, und überhaupt nicht bestanden haben könnte. In der ersten möglichen Welt P ist (a) wahr, im zweiten P ist (a) falsch, und in der dritten möglichen Welt gibt es nicht im Gebiet überhaupt.
• erste Ordnung krause Logik ist Erweiterungen der ersten Ordnung der krausen Satzlogik aber nicht klassischen Satzrechnung.

Höherwertige Logik

Die charakteristische Eigenschaft der Logik der ersten Ordnung ist, dass Personen gemessen werden können, aber nicht Prädikate. So

:

ist eine gesetzliche Formel der ersten Ordnung, aber

:

ist nicht in den meisten Formalisierungen der Logik der ersten Ordnung. Logik der zweiten Ordnung erweitert Logik der ersten Ordnung durch das Hinzufügen des letzten Typs der Quantifizierung. Andere höherwertige Logik erlaubt Quantifizierung über noch höhere Typen als Logikerlaubnisse der zweiten Ordnung. Diese höheren Typen schließen Beziehungen zwischen Beziehungen, Funktionen von Beziehungen bis Beziehungen zwischen Beziehungen und anderen Gegenständen des höheren Typs ein. So beschreibt das "erste" in der Logik der ersten Ordnung den Typ von Gegenständen, die gemessen werden können.

Verschieden von der Logik der ersten Ordnung, für die nur eine Semantik studiert wird, gibt es mehrere mögliche Semantik für die Logik der zweiten Ordnung. Die meistens verwendete Semantik für die zweite Ordnung und höherwertige Logik ist als volle Semantik bekannt. Die Kombination von zusätzlichem quantifiers und der vollen Semantik für diese quantifiers macht höherwertige Logik stärker als Logik der ersten Ordnung. Insbesondere die (semantische) logische Folge-Beziehung für die zweite Ordnung und höherwertige Logik ist nicht halbentscheidbar; es gibt kein wirksames Abzug-System für die Logik der zweiten Ordnung, die gesund und unter der vollen Semantik abgeschlossen ist.

Die Logik der zweiten Ordnung mit der vollen Semantik ist ausdrucksvoller als Logik der ersten Ordnung. Zum Beispiel ist es möglich, Axiom-Systeme in der Logik der zweiten Ordnung zu schaffen, die einzigartig die natürlichen Zahlen und die echte Linie charakterisieren. Die Kosten dieses Ausdrucksvollen sind, dass zweite Ordnung und höherwertige Logik weniger attraktive metalogical Eigenschaften haben als Logik der ersten Ordnung. Zum Beispiel werden der Löwenheim-Skolem Lehrsatz und Kompaktheitslehrsatz der Logik der ersten Ordnung falsch, wenn verallgemeinert, für die höherwertige Logik mit der vollen Semantik.

Automatisierter Lehrsatz, der sich erweist und formelle Methoden

Automatisierter Lehrsatz, der sich erweist, bezieht sich auf die Entwicklung von Computerprogrammen, die suchen und Abstammungen (formelle Beweise) von mathematischen Lehrsätzen finden. Entdeckung von Abstammungen ist eine schwierige Aufgabe, weil der Suchraum sehr groß sein kann; eine erschöpfende Suche jeder möglichen Abstammung ist theoretisch möglich, aber für viele Systeme von Interesse in der Mathematik rechenbetont unausführbar. So werden komplizierte heuristische Funktionen entwickelt, um zu versuchen, eine Abstammung in kürzerer Zeit zu finden, als eine blinde Suche.

Das zusammenhängende Gebiet der automatisierten Probeüberprüfung verwendet Computerprogramme, um zu überprüfen, dass von den Menschen geschaffene Beweise richtig sind. Verschieden vom komplizierten automatisierten Lehrsatz provers können Überprüfungssysteme klein genug sein, dass ihre Genauigkeit sowohl mit der Hand als auch durch die automatisierte Softwareüberprüfung überprüft werden kann. Diese Gültigkeitserklärung des Beweises verifier ist erforderlich, um Vertrauen zu geben, dass jede Abstammung etikettiert als "richtig" wirklich richtig ist.

Ein Beweis verifiers, wie Metamath, beharrt darauf, eine ganze Abstammung, wie eingegeben, zu haben. Andere, wie Mizar und Isabelle, nehmen eine gut formatierte Probeskizze (der noch sehr lang und ausführlich sein kann) und füllen Sie die fehlenden Stücke aus, indem Sie einfache Probesuchen tun oder bekannte Entscheidungsverfahren anwenden: Die resultierende Abstammung wird dann durch einen kleinen Kern"Kern" nachgeprüft. Viele solche Systeme sind in erster Linie für den interaktiven Gebrauch von menschlichen Mathematikern beabsichtigt: Diese sind als Probehelfer bekannt. Sie können auch formelle Logik verwenden, die stärker ist als Logik der ersten Ordnung wie Typ-Theorie. Weil sich eine volle Abstammung jedes nichttrivialen Ergebnisses in einer ersten Ordnung, die deduktives System äußerst sein wird, nach einem Menschen sehnt zu schreiben, werden Ergebnisse häufig als eine Reihe von Lemmata formalisiert, für die Abstammungen getrennt gebaut werden können.

Automatisierter Lehrsatz provers wird auch verwendet, um formelle Überprüfung in der Informatik durchzuführen. In dieser Einstellung wird Lehrsatz provers verwendet, um die Genauigkeit von Programmen und der Hardware wie Verarbeiter in Bezug auf eine formelle Spezifizierung nachzuprüfen. Weil solche Analyse zeitraubend und so teuer ist, wird sie gewöhnlich für Projekte vorbestellt, in denen eine Funktionsstörung ernste menschliche oder finanzielle Folgen haben würde.

Siehe auch

• ACL2 - eine rechenbetonte Logik für das Applicative allgemeine Lispeln.
• Equiconsistency
• Erweiterung durch Definitionen
• Herbrandization
• Prenex normale Form
• Skolem normale Form
• Tisch von Logiksymbolen
• Wahrheitstabelle
• Typ (Mustertheorie)

Referenzen

• Peter Andrews. 2002. Eine Einführung in die Mathematische Logik- und Typ-Theorie: Zur Wahrheit Durch den Beweis. 2. Hrsg. Berlin: Kluwer Akademische Herausgeber, die von Springer verfügbar sind.
• Jeremy Avigad, Kevin Donnelly, David Gray, Paul Raff, 2007. "Ein formell nachgeprüfter Beweis des Primzahl-Lehrsatzes", ACM Transaktionen auf der Rechenbetonten Logik, v. 9 n. 1.
• Jon Barwise, 1977. "Eine Einführung in die Logik der ersten Ordnung", in
• Jon Barwise und John Etchemendy, 2000. Sprachbeweis und Logik. Stanford, Kalifornien: CSLI Veröffentlichungen (Verteilt von der Universität der Chikagoer Presse).
• Józef Maria Bocheński, 2007. Ein Précis der Mathematischen Logik. Übersetzt aus den französischen und deutschen Ausgaben von Otto Bird. Dordrecht, das Südliche Holland:D. Reidel.
• José Ferreirós. Die Straße zur Modernen Logik - Eine Interpretation. http://jstor.org/stable/2687794 Meldung von Symbolischer Logik, Band 7, Ausgabe 4, 2001, Seiten 441-484. DOI 10.2307/2687794. JStor
• L. T. F. Gamut, 1991. Logik, Sprache, und Bedeutung, Band 2: Intensional Logische und Logikgrammatik. Chicago: Universität der Chikagoer Presse. Internationale Standardbuchnummer 0-226-28088-8.
• David Hilbert und Wilhelm Ackermann 1950. Grundsätze der Mathematischen Logik (englische Übersetzung). Chelsea. 1928 die erste deutsche Ausgabe war betitelter Grundzüge der theoretischen Logik.
• Wilfrid Hodges, 2001, "Klassische Logik I: Die Erste Ordnungslogik," in Lou Goble, Hrsg., Dem Handbuch von Blackwell zur Philosophischen Logik. Blackwell.
• Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas. 1994. Mathematische Logik. Berlin, New York: Springer-Verlag. Die zweite Ausgabe. Studententexte in der Mathematik. Internationale Standardbuchnummer 978-0-387-94258-2.

.

Links

• Enzyklopädie von Stanford der Philosophie: "Klassische Logik - durch Stewart Shapiro. Deckel-Syntax, Mustertheorie und metatheory für die Logik der ersten Ordnung im natürlichen Abzug-Stil.
• forall x: Eine Einführung in die formale Logik, durch P.D. Magnus, bedeckt formelle Semantik und Probetheorie für die Logik der ersten Ordnung.
• Metamath: Ein andauerndes Online-Projekt, Mathematik als eine riesige Theorie der ersten Ordnung, mit der Logik der ersten Ordnung und der axiomatischen Mengenlehre ZFC wieder aufzubauen. Principia Mathematica hat sich modernisiert.
• Podnieks, Karl. Einführung in die mathematische Logik.
• Mathematik von Cambridge Zeichen von Tripos (Schriftsatz durch John Fremlin). Diese Zeichen bedecken einen Teil einer vorigen Mathematik von Cambridge Kurs von Tripos, der Studentenstudenten (gewöhnlich) innerhalb ihres dritten Jahres unterrichtet ist. Der Kurs wird "Logik, Berechnung und Mengenlehre" betitelt und bedeckt Ordnungszahlen und Kardinäle, Posets und das Lemma von zorn, Satzlogik, Prädikat-Logik, Mengenlehre und Konsistenz-Probleme, die mit ZFC und anderen Mengenlehren verbunden sind.