Propositionalkalkül

Propositionalkalkül ist ein Zweig von Logik. Es heißt auch Aussagelogik, Anweisung Logik, Sential Calculus, Sential Logic, oder manchmal Logik der Nullen-Ordnung. Es beschäftigt sich mit Aussagen (was wahr oder falsch sein kann) und Beziehungen zwischen Vorschlägen, einschließlich der Konstruktion von Argumenten, die auf ihnen basieren. Verbindungsaussagen werden gebildet, indem Aussagen durch Verbindungen durch verbunden sind Logische Verbindungen. Aussagen, die keine logischen Verbindungen enthalten, werden als Atomaussagen bezeichnet.

nicht wie Logik erster Ordnung, Propositionale Logik befasst sich nicht mit nicht logischen Objekten, Prädikate über sie oder Quantifizierer. Die gesamte Maschinerie der Aussagelogik ist jedoch in Logik erster Ordnung und logische höhere Ordnung enthalten. In diesem Sinne ist die Propositionslogik die Grundlage der Logik erster Ordnung und logischer höherer Ordnung.

Erläuterung

Logische Konnektiven finden sich in natürlichen Sprachen. In Englisch zum Beispiel sind einige Beispiele "und" ((Verbindung), "oder" (disjunktion), "nicht" (Negation) und "if" (aber nur, wenn es zur Bezeichnung verwendet wird Material bedingt).

Das Folgende ist ein Beispiel für eine sehr einfache Schlussfolgerung innerhalb des Umfangs der Aussagelogik:

Prämisse 1: Wenn es regnet, ist es bewölkt.

Prämisse 2: Es regnet.

Schlussfolgerung: Es ist bewölkt.

Sowohl Räumlichkeiten als auch die Schlussfolgerung sind Vorschläge. Die Räumlichkeiten werden als selbstverständlich angesehen und mit der Anwendung von Modus Ponens (ein Inferenzregel) folgt die Schlussfolgerung.

Da sich die Propositionslogik nicht mit der Struktur von Aussagen befasst Atomic Aussagen mit Anweisungsbriefen, die als Variablen interpretiert werden, die Aussagen darstellen:

Prämisse 1: ${\ displayStyle p \ bis q}$

Prämisse 2: ${\ displayStyle p}$

Fazit: ${\ displayStyle q}$

Gleiches kann auf folgende Weise prägnant angegeben werden:

${\ displayStyle p \ bis q, p \ vdash q}$

Wann P wird als "es regnet" und interpretiert und Q Als "es ist wolkig", können die obigen symbolischen Ausdrücke genau dem ursprünglichen Ausdruck in der natürlichen Sprache entsprechen. Nicht nur das, sondern sie werden auch einer anderen Schlussfolgerung entsprechen bilden, die auf der gleichen Basis gültig ist, diese Schlussfolgerung ist.

Aussagenlogik kann durch a untersucht werden formelles System in welchem Formeln von a formelle Sprache vielleicht interpretiert zu repräsentieren Aussagen. EIN System von Axiome und Inferenzregeln Ermöglicht bestimmte Formeln ab. Diese abgeleiteten Formeln werden genannt Theoreme und kann als wahre Aussagen interpretiert werden. Eine konstruierte Sequenz solcher Formeln ist als a bekannt Ableitung oder nachweisen und die letzte Formel der Sequenz ist der Satz. Die Ableitung kann als Beweis des vom Theorems dargestellten Satzs interpretiert werden.

Wenn ein formelles System zur Darstellung formaler Logik verwendet wird, sind nur Aussagen Briefe (normalerweise Kapitalrömischbuchstaben wie z. ${\ displayStyle p}$, ${\ displayStyle q}$ und ${\ displayStyle r}$) werden direkt dargestellt. Die Aussagen der natürlichen Sprache, die bei der Interpretation entstehen, liegen außerhalb des Rahmens des Systems, und die Beziehung zwischen dem formalen System und seiner Interpretation liegt ebenfalls außerhalb des formalen Systems selbst.

In klassisch Wahrheitsfunktionale Aussagen LogikFormeln werden als genau eine von zwei möglichen interpretiert Wahrheitswerte, der Wahrheitswert von Stimmt oder der Wahrheitswert von FALSCH.^[1] Das Prinzip der Bivalenz und die Gesetz der ausgeschlossenen Mitte sind bestätigt. Wahrheitsfunktionale Aussagenlogik als solche und Systeme definiert isomorph dafür werden als sein Logik der Nullen-Ordnung. Allerdings sind auch alternative Aussagen Logik möglich. Für mehr siehe Andere logische Berechnungen unter.

Geschichte

Obwohl die Propositionslogik (die mit Propositionalrechnung austauschbar ist) von früheren Philosophen angedeutet worden war, wurde sie zu einer formalen Logik entwickelt (Stoische Logik) durch Chrysippus im 3. Jahrhundert v. Chr.^[2] und von seinem Nachfolger erweitert Stoiker. Die Logik konzentrierte sich auf Aussagen. Dieser Fortschritt war anders als die traditionellen Syllogik -Logik, was sich auf konzentriert hatte Bedingungen. Die meisten der ursprünglichen Schriften gingen jedoch verloren^[3] und die von den Stoikern entwickelte Sätze Logik wurde später in der Antike nicht mehr verstanden. Folglich wurde das System im Wesentlichen von neu erfunden Peter Abelard im 12. Jahrhundert.^[4]

Die Propositionslogik wurde schließlich mit Verwendung verfeinert Symbolische Logik. Der Mathematiker des 17./18. Jahrhunderts Gottfried Leibniz wurde zugeschrieben, der Gründer der symbolischen Logik für seine Arbeit mit dem zu sein Kalkül Ratiocinator. Obwohl seine Arbeit die erste ihrer Art war, war sie der größeren logischen Gemeinschaft unbekannt. Folglich wurden viele der von Leibniz erzielten Fortschritte von Logikanern wie nachgebildet George Boole und Augustus de Morgan- unabhängig von Leibniz.^[5]

Genauso wie die Propositionslogik als Fortschritt der früheren syllogistischen Logik angesehen werden kann, Gottlob Frege's Prädikatlogik kann auch als Fortschritt aus der früheren Aussagelogik angesehen werden. Ein Autor beschreibt die Prädikatlogik als Kombination "die charakteristischen Merkmale der syllogistischen Logik und der Aussagenlogik".^[6] Folglich führte die Prädikat -Logik in einer neuen Ära in der Geschichte der Logik ein; Fortschritte in der Aussagelogik wurden jedoch nach dem Frege, einschließlich natürlicher Abzug, Wahrheitsbäume und Wahrheitstabellen. Der natürliche Abzug wurde von erfunden von Gerhard Gentzen und Jan łukasiewicz. Wahrheitsbäume wurden von erfunden von Evert Willem Beth.^[7] Die Erfindung von Wahrheitstabellen ist jedoch von unsicherer Zuordnung.

Innerhalb von Werken von Frege^[8] und Bertrand Russell,^[9] sind Ideen, die die Erfindung von Wahrheitstabellen beeinflussen. Die tatsächliche tabellarische Struktur (die als Tabelle formatiert wird) selbst wird beides allgemein zugeschrieben Ludwig Wittgenstein oder Emil Post (oder beides unabhängig).^[8] Neben Frege und Russell haben andere, die Ideen vor Wahrheitstabellen hatten, Philo, Boole, zugeschrieben. Charles Sanders Peirce,^[10] und Ernst Schröder. Andere, die der tabellarischen Struktur zugeschrieben wurden Jan łukasiewicz, Alfred North Whitehead, William Stanley Jevons, John Venn, und Clarence Irving Lewis.^[9] Letztendlich sind einige wie John Shoky zu dem Schluss gekommen, dass "es alles andere als klar ist, dass jeder Person den Titel" Erfinder "von Wahrheitstisch erhalten".^[9]

Terminologie

Im Allgemeinen ist ein Kalkül a formelles System das besteht aus einer Reihe von syntaktischen Ausdrücken (gut geformte Formeln), eine angesehene Teilmenge dieser Ausdrücke (Axiome) sowie eine Reihe formaler Regeln, die eine spezifische definieren binäre Beziehung, als interpretiert als interpretiert werden logische Äquivalenz, auf den Raum der Ausdrücke.

Wenn das formale System ein sein soll logisches System, die Ausdrücke sollen als Aussagen und die Regeln interpretiert werden, die bekannt sind Inferenzregeln, sind typischerweise als Wahrheitsprüfung gedacht. In dieser Einstellung können die Regeln, die möglicherweise beinhalten können Axiome, kann dann verwendet werden, um ("inferen") Formeln abzuleiten, die echte Aussagen darstellen - aus angegebenen Formeln, die echte Aussagen darstellen.

Der Satz von Axiomen kann leer sein, eine nicht leere endliche Menge oder ein zäher unendlich unendlicher Satz (siehe Axiomschema). EIN formelle Grammatik definiert rekursiv die Ausdrücke und gut geformten Formeln der Sprache. Zusätzlich a Semantik kann gegeben werden, was die Wahrheit definiert und Bewertungen (oder Interpretationen).

Das Sprache eines Aussagekalküls besteht aus

1. eine Reihe primitiver Symbole, unterschiedlich bezeichnet als Atomformeln, Platzhalter, Aussagebuchstaben, oder Variablen, und
2. eine Reihe von Operatorsymbolen, unterschiedlich interpretiert als logische Operatoren oder Logische Verbindungen.

A gut geformte Formel ist jede atomare Formel oder jede Formel, die durch Bedienungssymbole gemäß den Regeln der Grammatik aus Atomformeln aufgebaut werden kann.

Mathematiker unterscheiden manchmal zwischen Aussagenkonstanten, Aussagenvariablen und Schemata. Aussagenkonstanten repräsentieren einen bestimmten Satz, während die Propositionsvariablen über den Satz aller atomaren Sätze liegen. Schemata reichen jedoch über alle Vorschläge. Es ist üblich, Aussagenkonstanten durch darzustellen A, B, und C, Aussagevariablen von P, Q, und Rund schematische Buchstaben sind häufig griechische Buchstaben, meistens am häufigsten φ, ψ, und χ.

Grundlegendes Konzept

Im Folgenden werden ein Standard -Aussagen berechnet. Es gibt viele verschiedene Formulierungen, die alle mehr oder weniger äquivalent sind, unterscheiden sich jedoch in den Details von:

1. ihre Sprache (d. H. Die besondere Sammlung primitiver Symbole und Bedienersymbole),
2. der Satz von Axiomen oder angesehenen Formeln und
3. Die Satz von Inferenzregeln.

Ein bestimmter Satz kann mit einem Buchstaben als „Supstellungskonstante“ vertreten werden, der analog zur Darstellung einer Zahl durch einen Brief in Mathematik (z. B., a = 5). Alle Aussagen erfordern genau einen von zwei Wahrheitswerten: wahr oder falsch. Zum Beispiel lassen P Sei der Vorschlag, dass es draußen regnet. Dies wird wahr sein (P) Wenn es draußen regnet und sonst falsch (falsch (¬P).

• Wir definieren dann Wahrheitsfunktional Operatoren, beginnend mit Negation. ¬P repräsentiert die Negation von P, was als Verweigerung von betrachtet werden kann P. Im obigen Beispiel, ¬P drückt aus, dass es nicht draußen oder durch eine Standard -Lesart regnet: "Es ist nicht so, dass es draußen regnet." Wann P ist wahr, ¬P ist falsch; und wann P ist falsch, ¬P ist wahr. Als Ergebnis, ¬P hat immer den gleichen Wahrheitswert wie P.
• Die Konjunktion ist ein wahrheitsfunktionaler Bindeffekt, der beispielsweise aus zwei einfacheren Aussagen einen Satz bildet. P und Q. Die Konjunktion von P und Q ist geschrieben P ∧ Qund drückt aus, dass jeder wahr ist. Wir lesen P ∧ Q wie "P und Q". Für zwei beliebige Aussagen gibt es vier mögliche Zuordnungen von Wahrheitswerten:
  1. P ist wahr und Q ist wahr
  2. P ist wahr und Q ist falsch
  3. P ist falsch und Q ist wahr
  4. P ist falsch und Q ist falsch

Die Konjunktion von P und Q ist in Fall 1 wahr und ist ansonsten falsch. Wo P ist der Vorschlag, dass es draußen regnet und Q ist der Vorschlag, dass eine Kältefront über Kansas ist, P ∧ Q ist wahr, wenn es draußen regnet und Es gibt eine Kältefront über Kansas. Wenn es draußen nicht regnet, dann P ∧ q ist falsch; und wenn es keine Kälte über Kansas gibt, dann P ∧ Q ist auch falsch.

• Die Disjunktion ähnelt einer Konjunktion, als sie einen Satz aus zwei einfacheren Aussagen bildet. Wir schreiben es P ∨ Qund es wird gelesen "P oder Q". Es drückt das entweder aus P oder Q ist wahr. Somit in den oben aufgeführten Fällen die Disjunktion von P mit Q gilt in allen Fällen - außer Fall 4. Mit dem obigen Beispiel geht die Disjunktion aus, dass es entweder draußen regnet oder eine kalte Front über Kansas gibt. (Beachten Sie, dass diese Verwendung von Disjunktion der Verwendung des englischen Wortes "oder" ähnelt. Es ähnelt jedoch dem Englisch am ähnlichsten inklusiv "oder", mit der die Wahrheit von mindestens einem von zwei Vorschlägen ausdrückt werden kann. Es ist nicht wie das Englische exklusiv "oder", was die Wahrheit genau eines von zwei Vorschlägen ausdrückt. Mit anderen Worten, das exklusive "oder" ist falsch, wenn beide P und Q sind wahr (Fall 1). Ein Beispiel für das Exklusive oder ist: Sie haben möglicherweise einen Bagel oder ein Gebäck, aber nicht beides. In der natürlichen Sprache wird in der natürlichen Sprache angesichts des geeigneten Kontextes "das Nachtrag", aber nicht beide "weggelassen - aber impliziert. In der Mathematik ist jedoch "oder" immer inklusiv oder; wenn exklusiv oder gemeint ist, wird es angegeben, möglicherweise von "xor".)
• Material bedingt verbindet auch zwei einfachere Aussagen, und wir schreiben P → Q, was gelesen wird "wenn P dann Q". Der Vorschlag links vom Pfeil wird als Antezedenz bezeichnet, und der Satz rechts wird als Konsequenz bezeichnet. (Es gibt keine solche Bezeichnung für Konjunktion oder Disjunktion, da sie sind kommutativ Operationen.) Es drückt das aus Q ist wahr, wann immer P ist wahr. Daher P → Q gilt in jedem Fall oben außer Fall 2, da dies der einzige Fall ist, in dem P ist wahr aber Q ist nicht. Verwenden des Beispiels, wenn P dann Q drückt aus, dass wenn es draußen regnet, es eine Kältefront über Kansas gibt. Das materielle Bedingungen ist oft mit körperlicher Kausalität verwechselt. Das materielle Bedingung bezieht sich jedoch nur zwei Aussagen ihrer Wahrheitswerte-was nicht die Beziehung von Ursache und Wirkung ist. In der Literatur ist es umstritten, ob die materielle Implikation eine logische Verursachung darstellt.
• Biconditional schließt sich zwei einfacheren Aussagen an, und wir schreiben P ↔ Q, was gelesen wird "P dann und nur dann, wenn Q". Es drückt das aus P und Q haben den gleichen Wahrheitswert und in Fällen 1 und 4. 'P is true if and only if Q'Ist wahr und ansonsten falsch.

Es ist sehr hilfreich, sich das anzuschauen Wahrheitstabellen für diese verschiedenen Betreiber sowie die Methode der analytischen Tableaus.

Schließung unter Operationen

Propositionale Logik ist abgeschlossen unter Wahrheitsfunktional Connectives. Das heißt, für jeden Vorschlag φ, ¬φ ist auch ein Vorschlag. Ebenso für alle Vorschläge φ und ψ, φ ∧ ψ ist ein Satz und ähnlich für Disjunktion, bedingte und zweikonditionelle. Dies impliziert, dass zum Beispiel, φ ∧ ψ ist ein Satz, und so kann es mit einem anderen Satz verbunden werden. Um dies darzustellen, müssen wir Klammern verwenden, um anzuzeigen, welcher Vorschlag mit welcher verbunden ist. Zum Beispiel, P ∧ Q ∧ R ist keine gut geformte Formel, weil wir nicht wissen, ob wir uns verbinden P ∧ Q mit R oder wenn wir uns verbinden P mit Q ∧ R. So müssen wir entweder schreiben (P ∧ Q) ∧ R das erstere darstellen oder P ∧ (Q ∧ R) Letzteres darstellen. Durch die Bewertung der Wahrheitsbedingungen sehen wir, dass beide Ausdrücke die gleichen Wahrheitsbedingungen haben (werden in denselben Fällen wahr sein), und darüber hinaus wird jeder Satz, der durch willkürliche Konjunktionen gebildet wird, die gleichen Wahrheitsbedingungen aufweisen, unabhängig vom Ort der Klammern. Dies bedeutet, dass die Konjunktion ist assoziativMan sollte jedoch nicht davon ausgehen, dass Klammern niemals einen Zweck erfüllen. Zum Beispiel der Satz P ∧ (Q ∨ R) Hat nicht die gleichen Wahrheitsbedingungen von (P ∧ Q) ∨ RSie sind also unterschiedliche Sätze, die nur von den Klammern unterschieden werden. Man kann dies durch die oben verwiesene Wahrheitstischmethode überprüfen.

HINWEIS: Für jede willkürliche Anzahl von Propositionskonstanten können wir eine begrenzte Anzahl von Fällen bilden, in denen ihre möglichen Wahrheitswerte aufgeführt sind. Eine einfache Möglichkeit, dies zu generieren, ist durch Wahrheitstabellen, in der man schreibt P, Q, ..., Zfür jede Liste von k Aussagenkonstanten - das heißt, jede Liste von Aussagenkonstanten mit k Einträge. Unter dieser Liste schreibt man 2^k Reihen und unten P Man füllt die erste Hälfte der Reihen mit wahrem (oder t) und der zweiten Hälfte mit falsch (oder f) aus. Unter Q Man füllt ein Viertel der Reihen mit T, dann ein Viertel mit F, dann ein Viertel mit T und das letzte Viertel mit F. Die nächste Spalte wechselt zwischen wahr und falsch für jeden Achtel der Reihen, dann den sechzehnten und so weiter, bis die letzte Aussagekonstante zwischen t und f für jede Zeile variiert. Dadurch wird eine vollständige Auflistung von Fällen oder Wahrheitswertsaufträgen für diese Aussagenkonstanten erfolgt.

Streit

Der Propositionalkalkül definiert dann eine Streit eine Liste von Vorschlägen sein. Ein gültiges Argument ist eine Liste von Vorschlägen, von denen der letzte aus dem Rest folgt - oder impliziert -. Alle anderen Argumente sind ungültig. Das einfachste gültige Argument ist Modus PonensEine Instanz, deren Aussagen die folgende Liste der Aussagen ist:

$oder$

Dies ist eine Liste von drei Vorschlägen, jede Zeile ist ein Vorschlag, und die letzte folgt aus dem Rest. Die ersten beiden Zeilen werden als Räumlichkeiten bezeichnet und die letzte Zeile der Schlussfolgerung. Wir sagen, dass jeder Vorschlag C folgt aus allen Aussagen ${\ displayStyle (p_ {1}, ..., p_ {n})}$, wenn C muss wahr sein, wenn jedes Mitglied des Sets ${\ displayStyle (p_ {1}, ..., p_ {n})}$ ist wahr. In dem obigen Argument für jeden P und Q, wann immer P → Q und P sind unbedingt wahr Q ist wahr. Beachten Sie das, wenn P Stimmt, wir können die Fälle 3 und 4 nicht in Betracht ziehen (aus der Wahrheitstabelle). Wann P → Q ist wahr, wir können Fall 2 nicht berücksichtigen. Dies verlässt nur Fall 1, in dem Q ist auch wahr. Daher Q wird von den Räumlichkeiten impliziert.

Dies verallgemeinert schematisch. So wo φ und ψ kann überhaupt Vorschläge sein,

$oder$

Andere Argumentationsformen sind bequem, aber nicht notwendig. Bei einem vollständigen Satz von Axiomen (siehe unten für einen solchen Satz) sind Modus -Ponens ausreichend, um alle anderen Argumentationsformen in der Aussagenlogik zu beweisen, daher können sie als Ableitung angesehen werden. Beachten Sie, dass dies nicht für die Erweiterung der Aussagelogik auf andere Logik wie möglich gilt Logik erster Ordnung. Logik erster Ordnung erfordert mindestens eine zusätzliche Inferenzregel, um zu erhalten Vollständigkeit.

Die Bedeutung des Arguments in der formalen Logik ist, dass man neue Wahrheiten aus etablierten Wahrheiten erhalten kann. Im ersten Beispiel oben, angesichts der beiden Räumlichkeiten, die Wahrheit von Q ist noch nicht bekannt oder angegeben. Nachdem das Argument vorgenommen wurde, Q wird abgeleitet. Auf diese Weise definieren wir ein Abzugssystem als eine Reihe aller Vorschläge, die aus einem anderen Satz von Sätzen abgeleitet werden können. Zum Beispiel angesichts der Satz von Vorschlägen ${\ displayStyle a = \ {p \ lor q, \ neg q \ land r, (p \ lor q) \ bis r \}}$Wir können ein Abzugssystem definieren, Γ, das ist die Menge aller Aussagen, aus denen folgt A. Wiederholung wird immer angenommen, also ${\ displayStyle p \ lor q, \ neg q \ land r, (p \ lor q) \ bis r \ in \ gamma}$. Auch aus dem ersten Element von A, letztes Element sowie Modus Ponens, R ist eine Folge und so ${\ displayStyle r \ in \ gamma}$. Da wir jedoch nicht ausreichend vollständige Axiome aufgenommen haben, kann nichts anderes abgeleitet werden. Obwohl die meisten in der Propositionslogik untersuchten Abzugssysteme abgeleitet werden können ${\ displayStyle (p \ lor q) \ leftrightarrow (\ neg p \ bis q)}$Dieser ist zu schwach, um einen solchen Satz zu beweisen.

Generische Beschreibung eines Aussagekalküls

A Propositionalkalkül ist ein formelles System ${\ displayStyle {\ mathcal {l}} = {\ mathcal {l}} \ links (\ mathrm {a}, \ \ omega, \ \ mathrm {z}, \ \ mathrm {i} \ rechts)}}}}}}}}}}}$, wo:

Das Sprache von ${\ displaystyle {\ mathcal {l}}}$, auch bekannt als sein Satz von Formeln, gut geformte Formeln, ist induktiv definiert Nach den folgenden Regeln:

1. Basis: Jedes Element des Alpha -Sets ${\ displayStyle \ mathrm {a}}$ ist eine Formel von ${\ displaystyle {\ mathcal {l}}}$.
2. Wenn ${\ displayStyle p_ {1}, p_ {2}, \ ldots, p_ {j}}$ sind Formeln und ${\ displayStyle f}$ ist in ${\ displayStyle \ Omega _ {j}}$, dann ${\ displayStyle \ links (f (p_ {1}, p_ {2}, \ ldots, p_ {j}) \ rechts)}$ ist eine Formel.
3. Geschlossen: Nichts anderes ist eine Formel von ${\ displaystyle {\ mathcal {l}}}$.

Wiederholte Anwendungen dieser Regeln ermöglichen die Konstruktion komplexer Formeln. Zum Beispiel:

• Nach Regel 1, p ist eine Formel.
• Nach Regel 2, ${\ displayStyle \ neg p}$ ist eine Formel.
• Nach Regel 1, q ist eine Formel.
• Nach Regel 2, ${\ displayStyle (\ neg p \ lor q)}}$ ist eine Formel.

Beispiel 1. Einfaches Axiomsystem

Lassen $oder$, wo ${\ displayStyle \ mathrm {a}}$, ${\ displayStyle \ Omega}$, ${\ displayStyle \ mathrm {z}}$, ${\ displayStyle \ mathrm {i}}$ werden wie folgt definiert:

• Der Satz ${\ displayStyle \ mathrm {a}}$, die zähnen unendlichen Symbole, die dazu dienen, logische Aussagen darzustellen:

  ${\ displayStyle \ mathrm {a} = \ {p, q, r, s, t, u, p_ {2}, \ ldots \}.}$

• Das funktionell vollständig einstellen ${\ displayStyle \ Omega}$ von logischen Operatoren (logische Verbindungen und Negation) ist wie folgt. Der drei Konnektiven für Konjunktion, Disjunktion und Implikation (Implikation${\ displayStyle \ Wedge, \ lor}$, und →), man kann als primitiv angesehen werden und die anderen beiden können in Bezug auf IT und Negation definiert werden (Negation (¬).^[11] Alternativ können alle logischen Operatoren in Bezug auf a definiert werden Sohle ausreichend Operator, so wie die Sheffer Schlaganfall (NAND). Die zweikonditionelle (${\ displayStyle a \ leftrightarrow b}$) können natürlich in Bezug auf Konjunktion und Implikation als definiert werden ${\ displayStyle (a \ bis b) \ land (b \ bis a)}$.
  Negation und Implikation als die beiden primitiven Operationen eines Aussagenkalküls sind gleichbedeutend mit dem Set des Omega ${\ displayStyle \ Omega = \ Omega _ {1} \ Cup \ Omega _ {2}}$ Partition wie folgt:

  ${\ displayStyle \ Omega _ {1} = \ {\ lnot \},},},}$

  ${\ displayStyle \ Omega _ {2} = \ {\ to \}.}$

• Der Satz ${\ displayStyle \ mathrm {i}}$ (Der Satz von Anfangspunkten des logischen Abzugs, d. H. Logische Axiome) ist das Axiomsystem, das von vorgeschlagen wurde Jan łukasiewiczund verwendet als Vorschlag-Kalkulus-Teil von a Hilbert -System. Die Axiome sind alle Substitutionsinstanzen von:
  • ${\ displayStyle p \ to (q \ bis p)}$
  • ${\ displayStyle (p \ to (q \ to r)) \ to ((p \ to q) \ to (p \ bis r))}$
  • ${\ displayStyle (\ neg p \ to \ neg q) \ to (q \ bis p)}$
• Der Satz ${\ displayStyle \ mathrm {z}}$ von Transformationsregeln (Inferenzregeln) ist die alleinige Regel Modus Ponens (d.h. ${\ displayStyle p}$ und ${\ displayStyle (p \ bis q)}$, schließen ${\ displayStyle q}$). Dann ${\ displayStyle a \ lor b}$ ist definiert als ${\ displayStyle \ neg a \ bis B}$, und ${\ displayStyle a \ Land B}$ ist definiert als ${\ displayStyle \ neg (a \ bis \ neg b)}$.

Dieses System wird in verwendet Metamath set.mm formale Beweisdatenbank.

Beispiel 2. natürliches Abzugssystem

Lassen $oder$, wo ${\ displayStyle \ mathrm {a}}$, ${\ displayStyle \ Omega}$, ${\ displayStyle \ mathrm {z}}$, ${\ displayStyle \ mathrm {i}}$ werden wie folgt definiert:

• Das Alpha -Set ${\ displayStyle \ mathrm {a}}$, ist ein zäher unendlich unendlich symbolischer Satz, zum Beispiel:

  ${\ displayStyle \ mathrm {a} = \ {p, q, r, s, t, u, p_ {2}, \ ldots \}.}$

• Das Omega -Set ${\ displayStyle \ Omega = \ Omega _ {1} \ Cup \ Omega _ {2}}$ Partitionen wie folgt:

  ${\ displayStyle \ Omega _ {1} = \ {\ lnot \},},},}$

  ${\ displayStyle \ Omega _ {2} = \ {\ land, \ lor, \ to, \ leftrightarrow \}.}$

Im folgenden Beispiel eines Aussagenkalkuls sollen die Transformationsregeln als Inferenzregeln eines sogenannten sogenannten interpretiert werden natürliches Abzugssystem. Das hier präsentierte bestimmte System hat keine Anfangspunkte, was bedeutet, dass seine Interpretation für logische Anwendungen seine abgeleitet hat Theoreme aus einem leeren Axiom -Set.

• Der Satz der Anfangspunkte ist leer, das heißt, ${\ displayStyle \ mathrm {i} = \ varnothing}$.
• Die Reihe von Transformationsregeln, ${\ displayStyle \ mathrm {z}}$, wird wie folgt beschrieben:

Unser Aussagekalkül hat elf Inferenzregeln. Diese Regeln ermöglichen es uns, andere wahre Formeln abzuleiten, wenn eine Reihe von Formeln angenommen wird, von denen angenommen wird, dass sie wahr sind. Die ersten zehn geben einfach an, dass wir bestimmte gut geformte Formeln aus anderen wohlgeformten Formeln schließen können. Die letzte Regel verwendet jedoch hypothetisches Denken in dem Sinne, dass wir in der Prämisse der Regel eine (unbewiesene) Hypothese vorübergehend annehmen, um Teil der Reihe von abgeleiteten Formeln zu sein, um festzustellen, ob wir eine bestimmte andere Formel schließen können. Da die ersten zehn Regeln dies nicht tun, werden sie normalerweise als beschrieben als als Nicht-hypothetisch Regeln und der letzte als hypothetisch Regel.

Bei der Beschreibung der Transformationsregeln können wir ein Metallanguage -Symbol einführen ${\ displayStyle \ vdash}$. Es ist im Grunde genommen eine bequeme Kurzschrift, um "schließen" zu sagen. Das Format ist ${\ displaystyle \ gamma \ vdash \ psi}$, in welchem Γ ist ein (möglicherweise leerer) Satz von Formeln, die als Räumlichkeiten bezeichnet werden, und ψ ist eine Formel, die als Schlussfolgerung bezeichnet wird. Die Transformationsregel ${\ displaystyle \ gamma \ vdash \ psi}$ bedeutet das, wenn jeder Vorschlag in Γ ist ein Satz (oder hat den gleichen Wahrheitswert wie die Axiome), dann ψ ist auch ein Satz. Beachten Sie, dass die folgende Regel berücksichtigt wird Konjunktion EinführungWir werden wissen, wann immer Γ Wenn Sie mehr als eine Formel haben, können wir sie immer sicher mithilfe der Konjunktion in eine Formel reduzieren. Kurz gesagt, wir können von diesem Zeitpunkt an repräsentieren Γ als eine Formel anstelle eines Satzes. Eine weitere Auslassung aus Bequemlichkeit ist, wann Γ ist ein leeres Set, in welchem ​​Fall Γ darf nicht erscheinen.

Negation Einführung

Aus ${\ displayStyle (p \ bis q)}$ und ${\ displayStyle (p \ bis \ neg q)}}$, schließen ${\ displayStyle \ neg p}$.

Das ist, ${\ displayStyle \ {(p \ bis q), (p \ to \ neg q) \} \ vdash \ neg p}$.

Negation Eliminierung

Aus ${\ displayStyle \ neg p}$, schließen ${\ displayStyle (p \ bis r)}$.

Das ist, ${\ displayStyle \ {\ neg p \} \ vdash (p \ bis r)}$.

Doppelnegation Eliminierung

Aus ${\ displayStyle \ neg \ neg p}$, schließen p.

Das ist, ${\ displaystyle \ neg \ neg p \ vdash p}$.

Konjunktion Einführung

Aus p und q, schließen ${\ displayStyle (p \ land q)}$.

Das ist, ${\ displaystyle \ {p, q \} \ vdash (p \ land q)}$.

Konjunktion der Eliminierung

Aus ${\ displayStyle (p \ land q)}$, schließen p.

Aus ${\ displayStyle (p \ land q)}$, schließen q.

Das ist, ${\ displayStyle (p \ land q) \ vdash p}$ und ${\ displayStyle (p \ land q) \ vdash q}$.

DISJUNCTION EINLEITUNG

Aus p, schließen ${\ displayStyle (p \ lor q)}$.

Aus q, schließen ${\ displayStyle (p \ lor q)}$.

Das ist, ${\ displayStyle p \ vdash (p \ lor q)}$ und ${\ displayStyle q \ vdash (p \ lor q)}$.

DISJUCTIONIERT -Eliminierung

Aus ${\ displayStyle (p \ lor q)}$ und ${\ displayStyle (p \ bis r)}$ und ${\ displayStyle (q \ bis r)}$, schließen r.

Das ist, ${\ displaystyle \ {p \ lor q, p \ bis r, q \ bis r \} \ vdash r}$.

Biconditionale Einführung

Aus ${\ displayStyle (p \ bis q)}$ und ${\ displayStyle (q \ bis p)}$, schließen ${\ displayStyle (p \ leftrightarrow q)}}$.

Das ist, ${\ displayStyle \ {p \ bis q, q \ to p \} \ vdash (p \ leftrightarrow q)}$.

Biconditionale Eliminierung

Aus ${\ displayStyle (p \ leftrightarrow q)}}$, schließen ${\ displayStyle (p \ bis q)}$.

Aus ${\ displayStyle (p \ leftrightarrow q)}}$, schließen ${\ displayStyle (q \ bis p)}$.

Das ist, ${\ displayStyle (p \ leftrightarrow q) \ vdash (p \ bis q)}$ und ${\ displayStyle (p \ leftrightarrow q) \ vdash (q \ bis p)}$.

Modus Ponens (Bedingte Eliminierung)

Aus p und ${\ displayStyle (p \ bis q)}$, schließen q.

Das ist, ${\ displayStyle \ {p, p \ bis q \} \ vdash q}$.

Bedingter Beweis (Bedingte Einführung)

Von [Akzeptieren p erlaubt einen Beweis von q], schließen ${\ displayStyle (p \ bis q)}$.

Das ist, ${\ displayStyle (p \ vdash q) \ vdash (p \ bis q)}$.

Grundlegende und abgeleitete Argumentationsformen

Name	Sequent	Beschreibung
Modus Ponens	${\ displayStyle ((p \ to q) \ land p) \ vdash q}$	Wenn p dann q; p; deshalb q
Modus Tollens	${\ displayStyle ((p \ bis q) \ land \ neg q) \ vdash \ neg p}$	Wenn p dann q; nicht q; deshalb nicht p
Hypothetischer Syllogismus	${\ displayStyle ((p \ bis q) \ land (q \ bis r)) \ vdash (p \ bis r)}$	Wenn p dann q; wenn q dann r; Daher, wenn p dann r
Disjunktiver Syllogismus	${\ displayStyle ((p \ lor q) \ land \ neg p) \ vdash q}$	Entweder p oder q, oder beides; nicht p; deshalb, q
Konstruktives Dilemma	$oder$	Wenn p dann q; und wenn r dann s; aber p oder r; deshalb q oder s
Destruktives Dilemma	$oder$	Wenn p dann q; und wenn r dann s; aber nicht q oder nicht s; deshalb nicht p oder nicht r
Bidirektionales Dilemma	$oder$	Wenn p dann q; und wenn r dann s; aber p oder nicht s; deshalb q oder nicht r
Vereinfachung	${\ displayStyle (p \ land q) \ vdash p}$	p und q sind wahr; deshalb p ist wahr
Verbindung	${\ displayStyle p, q \ vdash (p \ land q)}$	p und q sind getrennt wahr; Deshalb sind sie gemeinsam wahr
Zusatz	${\ displayStyle p \ vdash (p \ lor q)}$	p ist wahr; Daher die Disjunktion (p oder q) ist wahr
Komposition	$oder$	Wenn p dann q; und wenn p dann r; deshalb wenn p ist dann wahr q und r sind wahr
De Morgans Theorem (1)	${\ displaystyle \ neg (p \ land q) \ vdash (\ neg p \ lor \ neg q)}$	Die Negation von ((p und q) ist äquiv. etwas nicht p oder nicht q))
De Morgans Theorem (2)	${\ displaystyle \ neg (p \ lor q) \ vdash (\ neg p \ land \ neg q)}$	Die Negation von ((p oder q) ist äquiv. etwas nicht p und nicht q))
Kommutierung (1)	${\ displayStyle (p \ lor q) \ vdash (q \ lor p)}$	(p oder q) ist äquiv. zu (q oder p))
Kommutierung (2)	${\ displayStyle (p \ land q) \ vdash (q \ land p)}$	(p und q) ist äquiv. zu (q und p))
Kommutierung (3)	${\ displayStyle (p \ leftrightarrow q) \ vdash (q \ leftrightarrow p)}$	(p ist äquiv. zu q) ist äquiv. zu (q ist äquiv. zu p))
Verband (1)	${\ displayStyle (p \ lor (q \ lor r)) \ vdash ((p \ lor q) \ lor r)}$	p oder (q oder r) ist äquiv. zu (p oder q) oder r
Verband (2)	${\ displayStyle (p \ land (q \ land r)) \ vdash ((p \ land q) \ land r)}}$	p und (q und r) ist äquiv. zu (p und q) und r
Verteilung (1)	${\ displayStyle (p \ land (q \ lor r)) \ vdash ((p \ land q) \ lor (p \ land r))}}$	p und (q oder r) ist äquiv. zu (p und q) oder (p und r))
Verteilung (2)	${\ displayStyle (p \ lor (q \ land r)) \ vdash ((p \ lor q) \ land (p \ lor r))}}$	p oder (q und r) ist äquiv. zu (p oder q) und (p oder r))
Doppelte Negation	${\ displayStyle p \ vdash \ neg \ neg p}$ und ${\ displaystyle \ neg \ neg p \ vdash p}$	p entspricht der Negation von nicht p
Transposition	${\ displayStyle (p \ bis q) \ vdash (\ neg q \ to \ neg p)}$	Wenn p dann q ist äquiv. zu wenn nicht q dann nicht p
Materielle Implikation	${\ displayStyle (p \ bis q) \ vdash (\ neg p \ lor q)}}$	Wenn p dann q ist äquiv. etwas nicht p oder q
Materielle Äquivalenz (1)	${\ displayStyle (p \ leftrightarrow q) \ vdash ((p \ bis q) \ land (q \ bis p))}$	(p IFF q) ist äquiv. zu (if p ist dann wahr q ist wahr) und (wenn q ist dann wahr p ist wahr)
Materielle Äquivalenz (2)	${\ displayStyle (p \ leftrightarrow q) \ vdash ((p \ land q) \ lor (\ neg p \ land \ neg q))}}$	(p IFF q) ist äquiv. entweder (p und q sind wahr) oder (beides p und q sind falsch)
Materielle Äquivalenz (3)	${\ displayStyle (p \ leftrightarrow q) \ vdash ((p \ lor \ neg q) \ land (\ neg p \ lor q))}}$	(p IFF q) ist eindeutig.p oder nicht q ist wahr) und (nicht p oder q ist wahr)
Ausfuhr[12]	${\ displayStyle ((p \ land q) \ bis r) \ vdash (p \ bis (q \ bis r))}$	von (if p und q sind dann wahr r ist wahr) wir können beweisen (wenn q ist dann wahr r ist wahr, wenn p ist wahr)
Einfuhr	${\ displayStyle (p \ to (q \ to r)) \ vdash ((p \ land q) \ bis r)}}$	Wenn p dann wenn q dann r) ist gleichbedeutend mit if p und q dann r
Tautologie (1)	${\ displayStyle p \ vdash (p \ lor p)}$	p ist wahr ist Äquiv. zu p ist wahr oder p ist wahr
Tautologie (2)	${\ displayStyle p \ vdash (p \ land p)}$	p ist wahr ist Äquiv. zu p ist wahr und p ist wahr
Tertium nicht tatur (Gesetz der ausgeschlossenen Mitte)	${\ displayStyle \ vdash (p \ lor \ neg p)}$	p oder nicht p ist wahr
Gesetz der Nicht-Kontrollierung	${\ displaystyle \ vdash \ neg (p \ land \ neg p)}$	p und nicht p ist falsch, ist eine wahre Aussage

Beweise im Aussagenkalkül

Eine der Hauptanwendungen eines Aussagenkalkuls besteht bei der Interpretation für logische Anwendungen darin, die Beziehungen der logischen Äquivalenz zwischen Subjektformeln zu bestimmen. Diese Beziehungen werden anhand der verfügbaren Transformationsregeln bestimmt, von denen Sequenzen genannt werden Ableitungen oder Beweise.

In der zu folgenen Diskussion wird ein Beweis als Folge von nummerierten Linien dargestellt, wobei jede Zeile aus einer einzelnen Formel besteht, gefolgt von a Grund oder Rechtfertigung zur Einführung dieser Formel. Jede Prämisse des Arguments, dh eine Annahme, die als Hypothese des Arguments eingeführt wird, ist zu Beginn der Sequenz aufgeführt und als "Prämisse" anstelle anderer Rechtfertigung gekennzeichnet. Die Schlussfolgerung ist in der letzten Zeile aufgeführt. Ein Beweis ist abgeschlossen, wenn jede Zeile aus den vorherigen durch die korrekte Anwendung einer Transformationsregel folgt. (Für einen kontrastierenden Ansatz siehe Proofbäume).

Beispiel eines Beweises im natürlichen Abzugssystem

• Gezeigt werden A → A.
• Ein möglicher Beweis dafür (der, obwohl gültig, mehr Schritte enthält als notwendig) kann wie folgt angeordnet werden:

Beispiel eines Beweises

Nummer	Formel	Grund
1	${\ displayStyle a}$	Prämisse
2	${\ displayStyle a \ lor a}$	Aus (1) Durch die Einführung der Disjunktion
3	${\ displayStyle (a \ lor a) \ land a}$	Aus (1) und (2) durch Konjunktion Einführung
4	${\ displayStyle a}$	Aus (3) durch Konjunktionsimination
5	${\ displayStyle a \ vdash a}$	Zusammenfassung von (1) durch (4))
6	${\ displayStyle \ vdash a \ to a}$	Aus (5) durch bedingte Beweise

Interpretieren ${\ displayStyle a \ vdash a}$ als "Annahme A, schließen A". Lesen ${\ displayStyle \ vdash a \ to a}$ als "nichts annehmen, schließen Sie das ab A impliziert A", oder" es ist eine Tautologie, die A impliziert A"oder" es ist immer wahr, dass A impliziert A".

Beispiel eines Beweises in einem klassischen Aussagen -Kalkülsystem

Wir beweisen jetzt den gleichen Satz ${\ displayStyle a \ to a}$ im axiomatischen System durch Jan łukasiewicz oben beschrieben, was ein Beispiel für a ist klassische Sätze Kalkülsysteme, oder ein Deduktives System im Hilbert-Stil Für Propositionalkalkül.

Die Axiome sind:

(A1) ${\ displayStyle (p \ bis (q \ bis p))}$

(A2) ${\ displayStyle ((p \ to (q \ to r)) \ to ((p \ to q) \ to (p \ bis r)))}$

(A3) ${\ displayStyle ((\ neg p \ to \ neg q) \ to (q \ bis p))}$

Und der Beweis lautet wie folgt:

1. ${\ displayStyle a \ to ((b \ to a) \ to a)}$ (Instanz von (a1))
2. ${\ displayStyle (a \ to ((b \ to a) \ to a) \ to ((a \ to (b \ to a)) \ to (a \ to a))}$ (Instanz von (a2))
3. ${\ displayStyle (a \ to (b \ to a)) \ to (a \ bis a)}$ (von (1) und (2) durch Modus Ponens)
4. ${\ displayStyle a \ to (b \ to a)}$ (Instanz von (a1))
5. ${\ displayStyle a \ to a}$ (aus (4) und (3) durch Modus ponens)

Solidität und Vollständigkeit der Regeln

Die entscheidenden Eigenschaften dieser Regeln sind, dass sie es sind Klang und Komplett. Informell bedeutet dies, dass die Regeln korrekt sind und keine anderen Regeln erforderlich sind. Diese Ansprüche können wie folgt formeller gemacht werden. Beachten Sie, dass die Beweise für die Klang und Vollständigkeit der Aussagelogik selbst nicht selbst Beweise in der Aussagelogik sind. Dies sind Theoreme in ZFC verwendet als a Metatheorie Eigenschaften der Aussagelogik beweisen.

Wir definieren a Wahrheitsaufgabe Als ein Funktion das kartiert die Aussagevariablen zu Stimmt oder FALSCH. Informell eine solche Wahrheitsaufgabe kann als Beschreibung eines möglichen verstanden werden Zustand (oder mögliche Welt) wo bestimmte Aussagen wahr sind und andere nicht. Die Semantik von Formeln kann dann formalisiert werden, indem sie definieren, für welche "Zustandszustand" sie als wahr angesehen werden, was durch die folgende Definition getan wird.

Wir definieren, wann eine solche Wahrheitsaufgabe A erfüllt ein bestimmtes gut geformte Formel mit den folgenden Regeln:

• A erfüllt die Aussagevariable P dann und nur dann, wenn A(P) = wahr
• A zufrieden ¬φ dann und nur dann, wenn A befriedigt nicht φ
• A zufrieden (φ ∧ ψ) dann und nur dann, wenn A erfüllt beides φ und ψ
• A zufrieden (φ ∨ ψ) dann und nur dann, wenn A erfüllt mindestens einer von beiden φ oder ψ
• A zufrieden (φ → ψ) Wenn und nur wenn es nicht der Fall ist A zufrieden φ aber nicht ψ
• A zufrieden (φ ↔ ψ) dann und nur dann, wenn A erfüllt beides φ und ψ oder befriedigt weder einen von ihnen

Mit dieser Definition können wir jetzt formalisieren, was es für eine Formel bedeutet φ von einem bestimmten Satz impliziert werden S von Formeln. Informell gilt dies, wenn in allen Welten, die angesichts der Formeln möglich sind, möglich sind S die Formel φ auch hält. Dies führt zu der folgenden formalen Definition: Wir sagen, dass ein Satz S von wohlgeformten Formeln semantisch mit sich bringen (oder impliziert) Eine bestimmte wohlgeformte Formel φ Wenn alle Wahrheitsaufträge, die alle Formeln befriedigen S auch zufrieden φ.

Endlich definieren wir syntaktische Entdeckung so dass φ wird syntaktisch durchgesetzt von S Wenn und nur wenn wir es mit den Inferenzregeln ableiten können, die oben in einer begrenzten Anzahl von Schritten vorgestellt wurden. Dies ermöglicht uns, genau zu formulieren, was es bedeutet, dass die Inferenzregeln so gut und abgeschlossen sind:

Solidität: Wenn der Satz gut geformter Formeln S syntaktisch beinhaltet die wohlgeformte Formel φ dann S semantisch mit sich bringen φ.

Vollständigkeit: Wenn der Satz gut geformter Formeln S semantisch beinhaltet die wohlgeformte Formel φ dann S syntaktisch mit sich bringen φ.

Für die oben genannten Regeln ist dies tatsächlich der Fall.

Skizze eines soliden Beweiss

(Für die meisten Logische SystemeDies ist die vergleichsweise "einfache" Beweisrichtung)

Notationale Konventionen: Lassen Sie G Seien Sie eine Variable, die über Sätze Sätze reicht. Lassen A, b und C Bereich über Sätze. Zum "G syntaktisch mit sich bringen A" wir schreiben "G beweist A". Zum "G semantisch mit sich bringen A" wir schreiben "G impliziert A".

Wir wollen zeigen: (A) (G) (wenn G beweist A, dann G impliziert A).

Wir notieren das "G beweist A"hat eine induktive Definition, und das gibt uns die unmittelbaren Ressourcen, um Ansprüche der Form zu demonstrieren", wenn G beweist Adann ... ". Unser Beweis erfolgt also durch Induktion.

Beachten Sie, dass der Basisschritt II für natürlicher Abzug Systeme, weil sie keine Axiome haben. Bei der Verwendung beinhaltet Schritt II, dass jedes der Axiome a (semantisch) ist Logische Wahrheit.

Die Basisschritte zeigen, dass die einfachsten nachweisbaren Sätze von G sind auch impliziert von Gfür jeden G. (Der Beweis ist einfach, da die semantische Tatsache, dass ein Satz eines seiner Mitglieder impliziert, auch trivial ist.) Der induktive Schritt wird systematisch alle weiteren Sätze abdecken, die möglicherweise nachweisbar sind - indem wir jeden Fall berücksichtigen, in dem wir möglicherweise eine logische Schlussfolgerung ziehen könnten Unter Verwendung einer Inferenzregel - und zeigt, dass ein neuer Satz auch logisch impliziert ist, wenn ein neuer Satz nachweisbar ist. (Zum Beispiel könnten wir eine Regel haben, die uns das sagt "A"Wir können ableiten"A oder B". In iii.a wir nehmen das an, wenn A ist nachweisbar, dass es impliziert ist. Wir wissen das auch, wenn A ist dann nachweisbar "A oder B"ist nachweisbar. Wir müssen das dann zeigen"A oder B"Auch ist impliziert. Wir tun dies durch Berufung an die semantische Definition und die Annahme, die wir gerade gemacht haben. A ist nachweisbar von G, wir nehmen an. So ist es auch impliziert von G. Also jede semantische Bewertung, die alle machen G wahr macht A WAHR. Aber jede Bewertungserstellung A wahr macht ""A oder B"wahr, durch die definierte Semantik für" oder ". Also jede Bewertung, die alle macht G wahr macht ""A oder B"wahr. Also"A oder B"ist impliziert.) Im Allgemeinen besteht der induktive Schritt aus einem langen, aber einfachen Fall-für-Fall-Analyse von allen Inferenzregeln, die zeigen, dass jede semantische Implikation "bewahrt".

Durch die Definition der Bekanntheit gibt es keine anderen Sätze, als ein Mitglied von zu sein Gein Axiom oder nach einer Regel; Wenn alle semantisch impliziert sind, ist der Abzugsrechnung solide.

Skizze des Vollständigkeitsbeweiss

(Dies ist normalerweise die viel schwierigere Beweisrichtung.)

Wir nehmen dieselben Notationskonventionen wie oben an.

Wir wollen zeigen: wenn G impliziert A, dann G beweist A. Wir gehen von Schaffung: Wir zeigen stattdessen das, wenn G tut nicht beweisen A dann G tut nicht implizieren A. Wenn wir zeigen, dass es eine gibt Modell wo A hält trotz G wahr sein, dann offensichtlich G impliziert nicht A. Die Idee ist, ein solches Modell aus unserer Annahme herauszubauen, dass G beweist nicht A.

Somit ist jedes System mit Modus -Ponens als Inferenzregel und beweist die folgenden Theoreme (einschließlich Substitutionen davon):

• p → (¬p → q)
• (p → q) → ((¬p → q) → q)
• p → (q → (p → q))
• p → (¬q → ¬ (p → q))
• ¬p → (p → q)
• p → p
• p → (q → p)
• (P → (q → r)) → ((p → q) → (p → r))

Die ersten fünf werden zur Zufriedenheit der fünf Bedingungen in der obigen Stufe III und die letzten drei verwendet, um den Abzugstheorem zu beweisen.

Beispiel

Beispiel Acht Theoreme (einschließlich Substitutionen davon). Von den acht Theoremen sind die letzten beiden zwei der drei Axiome; das dritte Axiom, ${\ displayStyle (\ neg q \ to \ neg p) \ to (p \ to q)}$, kann auch nachgewiesen werden, wie wir jetzt zeigen.

Für den Beweis können wir die verwenden Hypothetischer Syllogismus -Theorem (In der Form, die für dieses axiomatische System relevant ist), da es sich nur auf die beiden Axiome stützt, die sich bereits im obigen Satz von acht Theoremen befinden. Der Beweis lautet dann wie folgt:

1. ${\ displayStyle q \ to (p \ to q)}$ (Instanz des 7. Satzes)
2. ${\ displayStyle (q \ to (p \ to q)) \ to ((\ neg q \ to \ neg p) \ to (q \ to (p \ to q)))}$ (Instanz des 7. Satzes)
3. ${\ displayStyle (\ neg q \ to \ neg p) \ to (q \ to (p \ to q))}$ (aus (1) und (2) durch Modus ponens)
4. ${\ displayStyle (\ neg p \ to (p \ to q)) \ to ((\ neg q \ to \ neg p) \ to (\ neg q \ to (p \ to q)))}$ (Instanz des hypothetischen Syllogismus -Theorems)
5. ${\ displayStyle (\ neg p \ to (p \ to q))}$ (Instanz des 5. Satzes)
6. ${\ displayStyle (\ neg q \ to \ neg p) \ to (\ neg q \ to (p \ to q))}$ (aus (5) und (4) durch Modus ponens)
7. ${\ displayStyle (q \ to (p \ to q)) \ to ((\ neg q \ to (p \ to q)) \ to (p \ to q))}$ (Instanz des 2. Satzes)
8. ${\ displayStyle ((q \ to (p \ to q)) \ to ((\ neg q \ to (p \ to q)) \ to (p \ to q))) \ to ((\ neg q \ bis \ neg p) \ to ((q \ to (p \ to q)) \ to ((\ neg q \ to (p \ to q)) \ to (p \ to q))))}$ (Instanz des 7. Satzes)
9. ${\ displayStyle (\ neg q \ to \ neg p) \ to ((q \ to (p \ to q)) \ bis (\ neg q \ to (p \ to q)) \ to (p \ bis q )))}$ (aus (7) und (8) durch Modus ponens)
10. ${\ displayStyle ((\ neg q \ to \ neg p) \ to ((q \ to (p \ to q)) \ bis (\ neg q \ to (p \ to q)) \ bis (p \ bis q)))) \ bis}$

    ${\ displayStyle (((\ neg q \ to \ neg p) \ to (q \ to (p \ to q))) \ to (\ neg q \ to \ neg p) \ to ((\ neg q \ zu (p \ bis q)) \ bis (p \ bis q))))}$ (Instanz des 8. Satzes)

11. ${\ displayStyle ((\ neg q \ to \ neg p) \ to (q \ to (p \ to q))) \ to (\ neg q \ to \ neg p) \ to ((\ neg q \ to (p \ bis q)) \ bis (p \ bis q)))}$ (aus (9) und (10) durch Modus ponens)
12. ${\ displayStyle (\ neg q \ to \ neg p) \ to ((\ neg q \ to (p \ to q)) \ to (p \ to q))}$ (aus (3) und (11) durch Modus ponens)
13. ${\ displayStyle ((\ neg q \ to \ neg p) \ to ((\ neg q \ to (p \ to q)) \ to (p \ to q))) \ to (((\ neg q \ zu (\ neg q q \) zu \ neg p) \ to (\ neg q \ to (p \ to q)) \ to ((\ neg q \ to \ neg p) \ to (p \ to q)))}$ (Instanz des 8. Satzes)
14. ${\ displayStyle ((\ neg q \ to \ neg p) \ to (\ neg \ to (p \ to q))) \ to ((\ neg q \ to \ neg p) \ bis (p \ bis q ))}$ (aus (12) und (13) durch Modus ponens)
15. ${\ displayStyle (\ neg q \ to \ neg p) \ to (p \ to q)}$ (aus (6) und (14) durch Modus ponens)

Überprüfung der Vollständigkeit für das klassische Aussagen -Kalkülsystem

Wir überprüfen nun, dass das zuvor beschriebene klassische Aussagen -Kalkülsystem tatsächlich die erforderlichen acht oben genannten Theoreme beweisen kann. Wir verwenden mehrere Lemmas, die bewährt sind hier:

(DN1) ${\ displaystyle \ neg \ neg p \ bis p}$ - Doppelte Negation (eine Richtung)

(DN2) ${\ displayStyle p \ to \ neg \ neg p}$ - Doppelnegation (eine andere Richtung)

(HS1) ${\ displayStyle (q \ bis r) \ bis ((p \ to q) \ to (p \ bis r))}$ - eine Form von Hypothetischer Syllogismus

(HS2) ${\ displayStyle (p \ bis q) \ bis (q \ bis r) \ bis (p \ bis r))}$ - Eine andere Form des hypothetischen Syllogismus

(TR1) ${\ displayStyle (p \ bis q) \ to (\ neg q \ to \ neg p)}$ - Transposition

(TR2) ${\ displayStyle (\ neg p \ bis q) \ bis (\ neg q \ bis p)}}$ - Eine andere Form der Transposition.

(L1) ${\ displayStyle p \ to ((p \ to q) \ to q)}$

(L3) ${\ displayStyle (\ neg p \ bis p) \ bis p}$

Wir verwenden auch die Methode der Hypothetischer Syllogismus Metatheorem als Kurzform für mehrere Beweisschritte.

• P → (¬p → q) - Beweis:
  1. ${\ displayStyle p \ to (\ neg q \ bis p)}$ (Instanz von (a1))
  2. ${\ displayStyle (\ neg q \ bis p) \ bis (\ neg p \ to \ neg \ neg q)}}$ (Instanz von (tr1))
  3. ${\ displayStyle p \ to (\ neg p \ to \ neg \ neg q)}$ (aus (1) und (2) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
  4. ${\ displayStyle \ neg \ neg q \ bis q}$ (Instanz von (dn1))
  5. $oder$ (Instanz von (hs1))
  6. ${\ displayStyle (\ neg p \ to \ neg \ neg q) \ to (\ neg p \ to q)}$ (von (4) und (5) unter Verwendung von Modus Ponens)
  7. ${\ displayStyle p \ to (\ neg p \ to q)}$ (aus (3) und (6) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
• (P → q) → ((¬p → q) → q) - Beweis:
  1. ${\ displayStyle (p \ bis q) \ to (\ neg q \ to p) \ to (\ neg q \ to q))}$ (Instanz von (hs1))
  2. ${\ displayStyle (\ neg q \ bis q) \ bis q}$ (Instanz von (l3))
  3. ${\ displayStyle ((\ neg q \ to q) \ to q) \ to (((\ neg q \ to p) \ to (\ neg q \ to q)) \ to ((\ neg q \ bis p) \ bis q))}$ (Instanz von (hs1))
  4. ${\ displayStyle ((\ neg q \ to p) \ to (\ neg q \ to q)) \ to ((\ neg q \ to p) \ to q)}$ (aus (2) und (3) durch Modus ponens)
  5. ${\ displayStyle (p \ bis q) \ bis (\ neg q \ bis p) \ bis q)}$ (aus (1) und (4) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
  6. ${\ displayStyle (\ neg p \ bis q) \ bis (\ neg q \ bis p)}}$ (Instanz von (TR2))
  7. ${\ displayStyle ((\ neg p \ to q) \ to (\ neg q \ to p)) \ to (((\ neg q \ to p) \ to q) \ to ((\ neg p \ bis q) \ bis q))}$ (Instanz von (hs2))
  8. ${\ displayStyle ((\ neg q \ bis p) \ bis q) \ bis ((\ neg p \ bis q) \ bis q)}$ (von (6) und (7) unter Verwendung von Modus Ponens)
  9. ${\ displayStyle (p \ bis q) \ bis (\ neg p \ to q) \ bis q)}$ (aus (5) und (8) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
• P → (q → (p → q)) - Beweis:
  1. ${\ displayStyle q \ to (p \ to q)}$ (Instanz von (a1))
  2. ${\ displayStyle (q \ to (p \ to q)) \ to (p \ to (q \ to (p \ to q)))}$ (Instanz von (a1))
  3. ${\ displayStyle p \ to (q \ to (p \ to q))}$ (aus (1) und (2) unter Verwendung von Modus -Ponens)
• p → (¬q → ¬ (p → q)) - Beweis:
  1. ${\ displayStyle p \ to ((p \ to q) \ to q)}$ (Instanz von (l1))
  2. ${\ displayStyle ((p \ bis q) \ bis q) \ to (\ neg q \ to \ neg (p \ to q))}$ (Instanz von (tr1))
  3. ${\ displayStyle p \ to (\ neg q \ to \ neg (p \ to q))}$ (aus (1) und (2) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
• ¬p → (p → q) - Beweis:
  1. ${\ displayStyle \ neg p \ to (\ neg q \ to \ neg p)}$ (Instanz von (a1))
  2. ${\ displayStyle (\ neg q \ to \ neg p) \ to (p \ to q)}$ (Instanz von (A3))
  3. ${\ displayStyle \ neg p \ to (p \ to q)}$ (aus (1) und (2) unter Verwendung des hypothetischen Syllogismus -Metatheorems)
• P → P - Beweis in der Beweisbeispiel oben
• P → (q → P) - Axiom (A1)
• (P → (Q → R)) → ((P → Q) → (P → R)) - Axiom (A2)

Ein weiterer Umriss für einen vollständigen Beweis

Wenn eine Formel a ist Tautologiedann gibt es a Wahrheitstabelle dafür, was zeigt, dass jede Bewertung den Wert für die Formel ergibt. Betrachten Sie eine solche Bewertung. Zeigen Sie durch mathematische Induktion auf der Länge der Subformulas, dass die Wahrheit oder Falschheit der Subformula aus der Wahrheit oder Falschheit (gegebenenfalls für die Bewertung) jeder Aussagevariablen in der Subformula folgt. Kombinieren Sie dann die Zeilen der Wahrheitstabelle jeweils zusammen mit der Verwendung "(" ("(" ("(" (P ist wahr impliziert S) impliziert ((P ist falsch impliziert S) impliziert S) ". Wiederholen Sie dies weiter, bis alle Abhängigkeiten von aussagekräftigen Variablen beseitigt wurden. Das Ergebnis ist, dass wir die angegebene Tautologie bewiesen haben. Da jede Tautologie nachweisbar ist, ist die Logik vollständig.

Interpretation eines Wahrheitsfunktional-Calculus

Ein Interpretation eines Wahrheitsfunktional-Calculus ${\ displaystyle {\ mathcal {p}}}$ ist ein Abtretung zu jedem Aussagensymbol von ${\ displaystyle {\ mathcal {p}}}$ von dem einen oder anderen (aber nicht beides) der Wahrheitswerte Wahrheit (T) und Falschheit (F) und eine Aufgabe an die Bindeymbole von ${\ displaystyle {\ mathcal {p}}}$ ihrer üblichen Wahrheitsbedeutungen. Eine Interpretation eines Wahrheitsfunktional-Aussagekalküls kann auch in Bezug auf von ausgedrückt werden Wahrheitstabellen.^[13]

Zum ${\ displayStyle n}$ unterschiedliche sätzeale Symbole gibt es ${\ displayStyle 2^{n}}$ unterschiedliche mögliche Interpretationen. Für ein bestimmtes Symbol ${\ displayStyle a}$Zum Beispiel gibt es ${\ displayStyle 2^{1} = 2}$ Mögliche Interpretationen:

1. ${\ displayStyle a}$ wird zugewiesen T, oder
2. ${\ displayStyle a}$ wird zugewiesen F.

Für das Paar ${\ displayStyle a}$, ${\ displayStyle B}$ es gibt ${\ displayStyle 2^{2} = 4}$ Mögliche Interpretationen:

1. Beide sind zugewiesen T,
2. Beide sind zugewiesen F,
3. ${\ displayStyle a}$ wird zugewiesen T und ${\ displayStyle B}$ wird zugewiesen F, oder
4. ${\ displayStyle a}$ wird zugewiesen F und ${\ displayStyle B}$ wird zugewiesen T.^[13]

Seit ${\ displaystyle {\ mathcal {p}}}$ hat ${\ displayStyle \ Aleph _ {0}}$, das ist, Renumerabel Viele spizierende Symbole, gibt es ${\ displayStyle 2^{\ Aleph _ {0}} = {\ mathfrak {c}}}$, und deshalb Unbezählte viele deutliche mögliche Interpretationen von ${\ displaystyle {\ mathcal {p}}}$.^[13]

Interpretation eines Satzes der Wahrheitsfunktionalaussagelogik

Wenn φ und ψ sind Formeln von ${\ displaystyle {\ mathcal {p}}}$ und ${\ displaystyle {\ mathcal {i}}}$ ist eine Interpretation von ${\ displaystyle {\ mathcal {p}}}$ Dann gelten die folgenden Definitionen:

• Ein Satz der Aussagelogik ist wahr unter einer Interpretation ${\ displaystyle {\ mathcal {i}}}$ wenn ${\ displaystyle {\ mathcal {i}}}$ weist den Wahrheitswert zu T zu diesem Satz. Wenn ein Satz ist Stimmt unter einer Interpretation wird diese Interpretation als a genannt Modell von diesem Satz.
• φ ist Falsch unter einer Interpretation ${\ displaystyle {\ mathcal {i}}}$ wenn φ ist nicht wahr unter ${\ displaystyle {\ mathcal {i}}}$.^[13]
• Ein Satz der Aussagelogik ist Logisch gültig Wenn es bei jeder Interpretation wahr ist.

  ${\ displayStyle \ Models}$ φ bedeutet, dass φ ist logisch gültig.

• Ein Satz ψ von Propositionallogik ist a semantische Konsequenz eines Satzes φ Wenn es keine Interpretation gibt, unter der φ ist wahr und ψ ist falsch.
• Ein Satz der Aussagelogik ist konsistent Wenn es unter mindestens einer Interpretation wahr ist. Es ist inkonsistent, wenn es nicht konsistent ist.

Einige Konsequenzen dieser Definitionen:

• Für eine bestimmte Interpretation ist eine bestimmte Formel entweder wahr oder falsch.^[13]
• Keine Formel ist unter derselben Interpretation sowohl wahr als auch falsch.^[13]
• φ ist falsch für eine bestimmte Interpretation IFF ${\ displayStyle \ neg \ phi}$ gilt für diese Interpretation; und φ ist unter einer Interpretation IFF wahr ${\ displayStyle \ neg \ phi}$ ist unter dieser Interpretation falsch.^[13]
• Wenn φ und ${\ displayStyle (\ phi \ bis \ psi)}$ sind beide unter einer bestimmten Interpretation wahr, dann ψ ist unter dieser Interpretation wahr.^[13]
• Wenn ${\ displayStyle \ models _ {\ mathrm {p}} \ phi}$ und ${\ displaystyle \ models _ {\ mathhrm {p}} (\ phi \ to \ psi)}$, dann ${\ displaystyle \ models _ {\ mathhrm {p}} \ psi}$.^[13]
• ${\ displayStyle \ neg \ phi}$ ist wahr unter ${\ displaystyle {\ mathcal {i}}}$ IFF φ ist nicht wahr unter ${\ displaystyle {\ mathcal {i}}}$.
• ${\ displayStyle (\ phi \ bis \ psi)}$ ist wahr unter ${\ displaystyle {\ mathcal {i}}}$ IFF entweder φ ist nicht wahr unter ${\ displaystyle {\ mathcal {i}}}$ oder ψ ist wahr unter ${\ displaystyle {\ mathcal {i}}}$.^[13]
• Ein Satz ψ der Aussagelogik ist eine semantische Folge eines Satzes φ IFF ${\ displayStyle (\ phi \ bis \ psi)}$ ist Logisch gültig, das ist, ${\ displayStyle \ phi \ models _ {\ mathrm {p}} \ psi}$ IFF ${\ displaystyle \ models _ {\ mathhrm {p}} (\ phi \ to \ psi)}$.^[13]

Alternative Kalkül

Es ist möglich, eine andere Version des Aussagenkalkuls zu definieren, die den größten Teil der Syntax der logischen Operatoren mittels Axiome definiert und nur eine Inferenzregel verwendet.

Axiome

Lassen φ, χ, und ψ stehen für gut geformte Formeln. (Die wohlgeformten Formeln selbst würden keine griechischen Buchstaben enthalten, sondern nur Kapitalbriefe, Bindeoperatoren und Klammern.) Dann sind die Axiome wie folgt:

Axiome

Name	Axiomschema	Beschreibung
Dann-1	${\ displayStyle \ phi \ to (\ chi \ to \ phi)}$	Hypothese hinzufügen χ, Implikation Einführung
Dann 2	${\ displayStyle (\ phi \ to (\ chi \ to \ psi) \ to ((\ phi \ to \ chi) \ to (\ phi \ to \ psi)}}}}}$	Hypothese verteilen ${\ displayStyle \ phi}$ über Implikation
UND 1	${\ displaystyle \ phi \ land \ chi \ to \ phi}$	Konjunktion beseitigen
UND 2	${\ displaystyle \ phi \ land \ chi \ to \ chi}$
Und-3	${\ displaystyle \ phi \ to (\ chi \ to (\ phi \ land \ chi))}$	Konjunktion einführen
OR-1	${\ displaystyle \ phi \ to \ phi \ lor \ chi}$	Disjunktion einführen
OR-2	${\ displaystyle \ chi \ to \ phi \ lor \ chi}$
Or-3	${\ displayStyle (\ phi \ to \ psi) \ to ((\ chi \ to \ psi) \ to (\ phi \ lor \ chi \ to \ psi)})})}}$	Disjunktion beseitigen
Nicht 1	${\ displayStyle (\ phi \ to \ chi) \ to ((\ phi \ to \ neg \ chi) \ to \ neg \ phi)}}$	Negation einführen
Nicht-2	${\ displayStyle \ phi \ to (\ neg \ phi \ to \ chi)}$	Negation beseitigen
Nicht 3	${\ displaystyle \ phi \ lor \ neg \ phi}$	Ausgeschlossene mittlere, klassische Logik
IFF-1	${\ displayStyle (\ phi \ leftrightarrow \ chi) \ to (\ phi \ to \ chi)}$	Äquivalenz beseitigen
IFF-2	${\ displayStyle (\ phi \ leftrightarrow \ chi) \ to (\ chi \ to \ phi)}$
IFF-3	${\ displayStyle (\ phi \ to \ chi) \ to ((\ chi \ to \ phi) \ to (\ phi \ leftrightarrow \ chi))}$	Äquivalenz einführen

• Axiom Dann 2 kann als "Verteilungseigenschaft der Implikation in Bezug auf die Implikation" angesehen werden.
• Axiome UND 1 und UND 2 entsprechen "Konjunktionsimination". Die Beziehung zwischen UND 1 und UND 2 spiegelt die Kommutativität des Konjunktionsbetreibers wider.
• Axiom Und-3 entspricht "Konjunktionseinführung".
• Axiome OR-1 und OR-2 entsprechen "Disjunktion Einführung". Die Beziehung zwischen OR-1 und OR-2 spiegelt die Kommutativität des Disjunktionerbetreibers wider.
• Axiom Nicht 1 entspricht "Reductio ad absurdum".
• Axiom Nicht-2 sagt: "Alles kann aus einem Widerspruch abgeleitet werden."
• Axiom Nicht 3 wird genannt "Tertium Nicht-Tatur"(Latein: "Ein Drittel ist nicht gegeben") und spiegelt die semantische Bewertung von Aussagenformeln wider: Eine Formel kann einen Wahrheitswert entweder wahr oder falsch haben. Es gibt keinen dritten Wahrheitswert, zumindest nicht in der klassischen Logik. Intuitionistische Logiker Akzeptieren Sie das Axiom nicht Nicht 3.

Inferenzregel

Die Inferenzregel ist Modus Ponens:

${\ displaystyle \ phi, \ \ phi \ to \ chi \ vdash \ chi}$.

Meta-Inferenzregel

Lassen Sie eine Demonstration durch eine Sequenz dargestellt, mit Hypothesen links von der Drehkreuz und die Schlussfolgerung rechts vom Drehkreuz. Dann ist die Abzugstheorem kann wie folgt angegeben werden:

Wenn die Sequenz

${\ displaystyle \ phi _ {1}, \ \ phi _ {2}, \ ..., \ \ phi _ {n}, \ \ chi \ vdash \ psi}$

wurde nachgewiesen, dann ist es auch möglich, die Sequenz zu demonstrieren

${\ displayStyle \ phi _ {1}, \ \ phi _ {2}, \ ..., \ \ phi _ {n} \ vdash \ chi \ to \ psi}$.

Dieser Abzugstheorem (DT) ist nicht selbst mit Propositionalkalkül formuliert: Es ist kein Satz des Sätzerechnung, sondern ein Satz über die Propositionalkalkül. In diesem Sinne ist es a Meta-Theorem, vergleichbar mit Theoreme über die Klanglosigkeit oder Vollständigkeit des Aussagenkalkuls.

Andererseits ist DT so nützlich, um den syntaktischen Beweisprozess zu vereinfachen, dass es als eine andere Inferenzregel betrachtet und verwendet werden kann, die mit den Modus -Ponens begleitet werden. In diesem Sinne entspricht DT dem Natürlichen bedingter Beweis Inferenzregel, die Teil der ersten Version des in diesem Artikel eingeführten Aussagenkalkuls ist.

Das Gegenteil von DT ist ebenfalls gültig:

Wenn die Sequenz

${\ displayStyle \ phi _ {1}, \ \ phi _ {2}, \ ..., \ \ phi _ {n} \ vdash \ chi \ to \ psi}$

wurde nachgewiesen, dann ist es auch möglich, die Sequenz zu demonstrieren

${\ displaystyle \ phi _ {1}, \ \ phi _ {2}, \ ..., \ \ phi _ {n}, \ \ chi \ vdash \ psi}$

Tatsächlich ist die Gültigkeit des Gegenteils von DT im Vergleich zu DT nahezu trivial:

Wenn

${\ displayStyle \ phi _ {1}, \ ..., \ \ phi _ {n} \ vdash \ chi \ to \ psi}$

dann

1: ${\ displaystyle \ phi _ {1}, \ ..., \ \ phi _ {n}, \ \ chi \ vdash \ chi \ to \ psi}$

2: ${\ displayStyle \ phi _ {1}, \ ..., \ \ phi _ {n}, \ \ chi \ vdash \ chi}$

und aus (1) und (2) können abgeleitet werden

3: ${\ displayStyle \ phi _ {1}, \ ..., \ \ phi _ {n}, \ \ chi \ vdash \ psi}$

mittels Modus ponens, q.e.d.

Das Gegenteil von DT hat starke Auswirkungen: Es kann verwendet werden, um ein Axiom in eine Inferenzregel umzuwandeln. Zum Beispiel das Axiom und 1,,

${\ displayStyle \ vdash \ phi \ wedge \ chi \ to \ phi}$

kann mithilfe des Gegenteils des Abzugstheorems in die Inferenzregel umgewandelt werden

${\ displayStyle \ phi \ wedge \ chi \ vdash \ phi}$

welches ist Konjunktion der Eliminierung, Eine der zehn Inferenzregeln, die in der ersten Version (in diesem Artikel) des Aussagenkalkuls verwendet wurden.

Beispiel eines Beweises

Das Folgende ist ein Beispiel für eine (syntaktische) Demonstration, die nur Axiome umfasst Dann-1 und Dann 2:

Beweisen: ${\ displayStyle a \ to a}$ (Reflexivität der Implikation).

Nachweisen:

1. ${\ displayStyle (a \ to ((b \ to a) \ to a) \ to ((a \ to (b \ to a)) \ to (a \ to a))}$

   Axiom Dann 2 mit ${\ displayStyle \ phi = a, \ chi = b \ to a, \ psi = a}$

2. ${\ displayStyle a \ to ((b \ to a) \ to a)}$

   Axiom Dann-1 mit ${\ displayStyle \ phi = a, \ chi = b \ bis a}$

3. ${\ displayStyle (a \ to (b \ to a)) \ to (a \ bis a)}$

   Aus (1) und (2) durch Modus -Ponens.

4. ${\ displayStyle a \ to (b \ to a)}$

   Axiom Dann-1 mit ${\ displayStyle \ phi = a, \ chi = b}$

5. ${\ displayStyle a \ to a}$

   Aus (3) und (4) durch Modus -Ponens.

Äquivalenz zu Gleichungslogik

Der vorhergehende alternative Kalkül ist ein Beispiel für a Abzugssystem im Hilbert-Stil. Bei Aussagensystemen sind die Axiome Begriffe, die mit logischen Konnektiven gebaut wurden, und die einzige Inferenzregel sind Modus -Ponens. Gleichungslogik als informell in der High School -Algebra standardmäßig verwendeten Logik ist eine andere Art von Kalkül als Hilbert -Systeme. Seine Theoreme sind Gleichungen und seine Inferenzregeln drücken die Eigenschaften der Gleichheit aus, nämlich dass es sich um eine Kongruenz zu Bedingungen handelt, die Substitution zulässt.

Klassischer Sätze wie oben beschrieben sind gleichwertig zu boolsche Algebra, während Intuitionistische Aussagenkalkül ist äquivalent zu Heying Algebra. Die Äquivalenz wird durch Translation in jede Richtung der Theoreme der jeweiligen Systeme gezeigt. Theoreme ${\ displayStyle \ phi}$ der klassischen oder intuitionistischen Aussagen werden als Gleichungen übersetzt ${\ displayStyle \ phi = 1}$ von booleschen bzw. heyting algebra. Umgekehrt Theoreme ${\ displayStyle x = y}$ von Booleschen oder Heyting -Algebra werden als Theoreme übersetzt ${\ displayStyle (x \ bis y) \ land (y \ bis x)}$ des klassischen bzw. intuitionistischen Kalküls, für das ${\ displayStyle x \ äquiv y}$ ist eine Standardabkürzung. Im Falle einer Booleschen Algebra ${\ displayStyle x = y}$ kann auch als übersetzt werden ${\ displayStyle (x \ land y) \ lor (\ neg x \ land \ neg y)}$Aber diese Übersetzung ist falsch intuitionistisch.

Sowohl in Booleschen als auch in Heyting -Algebra, Ungleichheit ${\ displayStyle x \ leq y}$ kann anstelle von Gleichheit verwendet werden. Die Gleichheit ${\ displayStyle x = y}$ ist als ein Paar von Ungleichheiten ausdrucksvoll ${\ displayStyle x \ leq y}$ und ${\ displayStyle y \ leq x}$. Umgekehrt die Ungleichheit ${\ displayStyle x \ leq y}$ ist ausdrücklich wie die Gleichheit ${\ displaystyle x \ land y = x}$, oder as ${\ displayStyle x \ lor y = y}$. Die Bedeutung der Ungleichheit für Systeme im Hilbert-Stil ist, dass es dem Abzug des letzteren entspricht oder mit sich bringen Symbol ${\ displayStyle \ vdash}$. Eine Ereignis

${\ displaystyle \ phi _ {1}, \ \ phi _ {2}, \ \ dots, \ \ phi _ {n} \ vdash \ psi}$

wird in der Ungleichheitsversion des algebraischen Rahmens als übersetzt

$oder$

Umgekehrt die algebraische Ungleichheit ${\ displayStyle x \ leq y}$ wird übersetzt als die Entzündung

${\ displaystyle x \ \ vdash \ y}$.

Der Unterschied zwischen Implikation ${\ displayStyle x \ bis y}$ und Ungleichheit oder mit sich bringen ${\ displayStyle x \ leq y}$ oder ${\ displaystyle x \ \ vdash \ y}$ ist, dass ersterer der Logik intern ist, während letzteres extern ist. Die interne Implikation zwischen zwei Begriffen ist ein weiterer Begriff derselben Art. Die Entschlossenheit als externe Implikation zwischen zwei Begriffen drückt eine Metatruth außerhalb der Sprache der Logik aus und gilt als Teil der Metallanguage. Selbst wenn die untersuchte Logik intuitionistisch ist, wird die Entnahme normalerweise klassisch als zweiwertig verstanden: entweder die linke Seite beinhaltet oder ist weniger oder gleichermaßen auf die rechte Seite oder nicht.

Ähnlich, aber komplexere Übersetzungen zur und von algebraischen Logik sind für natürliche Abzugssysteme wie oben und für die beschrieben möglich Sequent Calculus. Die mit den letzteren mit zwei Werten bewertet werden, aber eine aufschlussreichere Interpretation ist als Set, deren Elemente als abstrakte Beweise verstanden werden können, die als Morphismen von a organisiert sind Kategorie. In dieser Interpretation entspricht die Schnittregel des Sequent Calculus der Zusammensetzung in der Kategorie. Boolesche und Heyting -Algebren geben dieses Bild als besondere Kategorien ein, die höchstens einen Morphismus pro Homset haben, d. H. Ein Beweis pro Beinigung, der der Idee entspricht, dass das Existenz von Beweisen alles ist, was zählt: Jeder Beweis und es gibt keinen Sinn, sie zu unterscheiden .

Grafische Berechnung

Es ist möglich, die Definition einer formalen Sprache aus einer Reihe von endlichen Sequenzen über eine endliche Basis zu verallgemeinern, um viele andere Sätze mathematischer Strukturen einzubeziehen, solange sie durch endliche Materialien aus endlichen Materialien aufgebaut werden. Darüber hinaus eignen sich viele dieser Familien formeller Strukturen besonders gut für die Logik.

Zum Beispiel gibt es viele Familien von Grafiken Das sind nahe genug Analoga formaler Sprachen, dass das Konzept eines Kalküls ganz einfach und auf natürliche Weise auf sie erweitert wird. Viele Arten von Grafiken entstehen als Grafiken analysieren In der syntaktischen Analyse der entsprechenden Familien von Textstrukturen. Die Erfordernisse der praktischen Berechnung in formalen Sprachen erfordern häufig, dass Textzeichenfolgen konvertiert werden Zeigerstruktur Die Darstellungen von Parse-Graphen, nur als Überprüfung, ob Zeichenfolgen gut geformte Formeln sind oder nicht. Sobald dies erledigt ist, gibt es viele Vorteile, die durch die Entwicklung des grafischen Analogon des Kalküls auf Saiten gewonnen werden müssen. Die Zuordnung von Saiten zu analysieren Graphen heißt Parsing und die inverse Kartierung von analysebildeten Diagrammen zu Saiten wird durch eine Operation erreicht, die genannt wird durchqueren der Graph.

Andere logische Berechnungen

Die Propositionalkalkül ist ungefähr die einfachste Art von logischer Berechnung in der aktuellen Verwendung. Es kann auf verschiedene Arten erweitert werden. (Aristotelischer "syllogistischer" Kalkül, was in der modernen Logik größtenteils ersetzt ist, ist in etwas Ein einfacheres-aber in anderer Hinsicht komplexer-als ein Propositionalrechnung.) Der unmittelbarste Weg, um einen komplexeren logischen Kalkül zu entwickeln, besteht darin, Regeln einzuführen, die für feinkörnigere Details der verwendeten Sätze empfindlich sind.

Logik erster Ordnung (a.k.a. Prädikat-Logik erster Ordnung) ergibt Bedingungen, Variablen, Prädikate, und Quantifiziereralle behalten die Regeln der Aussagenlogik mit einigen neuen eingeführt. (Zum Beispiel können wir von "Alle Hunde sind Säugetiere" schließen ", wenn Rover ein Hund ist, dann ist Rover ein Säugetier".) Mit den Werkzeugen der Logik erster Ordnung ist es möglich, eine Reihe von Theorien zu formulieren, entweder mit explizit oder nach Inferenzregeln, die selbst als logische Berechnung behandelt werden können. Arithmetik ist das bekannteste von diesen; Andere umfassen Mengenlehre und Mereologie. Logik zweiter Ordnung und andere Logik höherer Ordnung sind formale Erweiterungen der Logik erster Ordnung. Somit ist es sinnvoll, die Aussagenlogik als zu beziehen "Logik der Nulle-Ordnung"beim Vergleich mit diesen Logik.

Modale Logik bietet auch eine Vielzahl von Schlussfolgerungen, die nicht in der Propositionalrechnung erfasst werden können. Zum Beispiel von "notwendigerweise von" p"Wir können das schließen p. Aus p Wir können schließen: "Es ist möglich, dass p". Die Übersetzung zwischen modaler Logik und algebraischen Logik betrifft die klassische und intuitionistische Logik, jedoch mit der Einführung eines unären Operator Interpretation der Notwendigkeit (für boolesche Algebra ist dies überflüssig, da die Notwendigkeit der De Morgan -Dual der Möglichkeit ist). Der erste Operator erhalten 0 und Disjunktion, während der zweite 1 und die Konjunktion aufbewahrt.

Viele bewertete Logik Sind diejenigen, die zulassen, dass Sätze andere Werte haben als Werte als Stimmt und FALSCH. (Zum Beispiel, weder und beide sind Standard "zusätzliche Werte"; "Continuum Logic" ermöglicht jedem Satz eine unendliche Anzahl von "Grad der Wahrheit" zwischen einer unendlichen Anzahl Stimmt und FALSCH.) Diese Logik erfordern häufig Kalkulationsgeräte, die sich stark von der Aussagekalkül unterscheiden. Wenn die Werte eine booleale Algebra bilden (die mehr als zwei oder sogar unendlich viele Werte aufweist), reduziert sich viele bewertete Logik auf klassische Logik. Viele bewertete Logiken sind daher nur von unabhängigem Interesse, wenn die Werte eine Algebra bilden, die nicht booleschen ist.

Löser

Lösungen für die Aussage -Logikformeln zu finden ist eine NP-Complete Problem. Es gibt jedoch praktische Methoden (z. B.,, DPLL -Algorithmus, 1962; Chaff -Algorithmus, 2001), die für viele nützliche Fälle sehr schnell sind. Jüngste Arbeiten haben die erweitert Sa LOLVER Algorithmen für die Arbeit mit Vorschlägen, die enthalten arithmetische Ausdrücke; Dies sind die SMT -Löser.

Siehe auch

Höhere logische Ebenen

• Logik erster Ordnung
• Second-order propositional logic
• Logik zweiter Ordnung
• Logik höherer Ordnung

verwandte Themen

Verweise

Weitere Lektüre

• Brown, Frank Markham (2003), Boolesche Argumentation: Die Logik der Booleschen Gleichungen, 1. Ausgabe, Kluwer Academic Publishers, Norwell, MA. 2. Auflage, Dover Publications, Mineola, NY.
• Chang, C.C. und Keisler, H.J. (1973), Modelltheorie, North-Holland, Amsterdam, Niederlande.
• Kohavi, Zvi (1978), Wechsel und endliche Automatentheorie, 1. Ausgabe, McGraw -Hill, 1970. 2. Auflage, McGraw -Hill, 1978.
• Korfhage, Robert R. (1974), Diskrete Rechenstrukturen, Academic Press, New York, NY.
• Lambek, J. und Scott, P. J. (1986), Einführung in die kategoriale Logik höherer Ordnung, Cambridge University Press, Cambridge, Großbritannien.
• Mendelson, Elliot (1964), Einführung in die mathematische LogikD. Van Nostrand Company.

Verwandte Werke

• Hofstadter, Douglas (1979). Gödel, Escher, Bach: Ein ewiges goldenes Geflecht. Grundbücher. ISBN 978-0-465-02656-2.

Externe Links

• Klement, Kevin C. (2006), "Propositionale Logik", in James Fieser und Bradley Dowden (Hrsg.), Internet -Enzyklopädie der Philosophie, Eprint.
• Formale Prädikatrechnungenthält eine systematische formale Entwicklung nach dem Sinne von Alternative Kalkül
• Forall X: Eine Einführung in die formale Logik, von P.D. Magnus deckt formelle Semantik ab und Beweistheorie für sententiale Logik.
• Kapitel 2 / Aussagelogik aus Logik in Aktion
• Aussage -Sequent -Kalkül -Prover auf Projekt Nayuki. (Hinweis: Implikation kann in der Form eingegeben werden ! X | yund eine Sequent kann eine einzelne Formel sein, mit der > und keine Kommas haben)
• Aussagelogik - eine generative Grammatik