Direkt zum Inhalt

Lexikon der Mathematik: vollständiges logisches System

ein konsistentes logisches System, für das der Gödelsche Vollständigkeitssatz gilt.

Zu einem logischen System gehört eine Menge Ax von logischen Axiomen, eine Menge von formalen Beweisregeln, die nur die Form, nicht aber den Inhalt der Axiome bzw. der zu beweisenden Aussagen berücksichtigen, und eine Folgerungsrelation ⊨ (logisches Folgern), die aus wahren Voraussetzungen nur wahre Behauptungen produziert. Das formale Beweisen wird durch ⊢ gekennzeichnet.

Ein logisches System heißt vollständig, wenn es konsistent ist (aus inkonsistenten Mengen sind alle Aussagen, insbesondere auch die falschen, beweisbar), und wenn für eine beliebige Menge T von Voraussetzungen und jede Aussage φ gilt:

\begin{eqnarray}T \vdash \varphi \iff T\models \varphi \end{eqnarray}

(Gödelscher Vollständigkeitssatz).

Das formale Beweisen, das nur eine Manipulation von Zeichenreihen zur Folge hat, spiegelt also das inhaltliche Folgern wider. Die Beweisregeln sind so gewählt, daß sie die Gültigkeit vererben, d. h., aus wahren Voraussetzungen sind nur wahre Behauptungen beweisbar, und die Beweisregeln sind in dem Sinne vollständig, daß alle Aussagen, die aus T inhaltlich folgen, auch aus T durch Anwendung der Regeln hergeleitet werden können. In der Prädikatenlogik haben sich die beiden Beweisregeln modus ponens und Generalisierung als ausreichend erwiesen.

Ein formaler Beweis für einen Ausdruck φ aus einer Menge T von Voraussetzungen ist eine endliche Folge (φ1, …, φn) von Ausdrücken, so daß φn = φ gilt, und für jedes φi, i = 1, …, n, eine der folgenden vier Bedingungen erfüllt ist:

  1. φi ∈ Ax (φi ist ein logisches Axiom).
  2. φiT (φi gehört zu den Voraussetzungen).
  3. Es gibt Indizes j, k < i, so daß \({\varphi}_{k}={\varphi}_{j}\to {\varphi}_{i}\)(Anwendung des modus ponens).
  4. Es gibt einen Index j < i, so daß \({\varphi _i} = \forall x{\varphi _j}\) (Anwendung der Generalisierung).

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.