www.wikidata.de-de.nina.az

Deduktionstheorem Unter dem Begriff sind zwei eng verwandte Theoreme bekannt die in der mathematischen Logik von Bedeutu

Deduktionstheorem

Unter dem Begriff Deduktionstheorem sind zwei eng verwandte Theoreme bekannt, die in der mathematischen Logik von Bedeutung sind. Eine Variante des Theorems, auch als Folgerungstheorem bekannt, zielt auf den Begriff der semantischen Folgerung ab. Die andere Variante, die innerhalb von Kalkülen Anwendung findet, macht statt der (semantischen) Folgerung die (syntaktische) Ableitung zum Ausgangspunkt. In beiden Fällen wird eine Beziehung zur materialen Implikation hergestellt.

Das Deduktionstheorem für semantische Folgerungen (⊨)

Die semantische Fassung des Deduktionstheorems lautet wie folgt:

Eine Formel ist genau dann eine semantische Folgerung der Formelmenge mit , formal , wenn die Implikation

allgemeingültig, d. h. eine Tautologie, ist (in klassischer Logik ist das genau dann der Fall, wenn die Implikation für jede mögliche Interpretation wahr ist).

Allgemein ist in klassischer Logik eine Formel genau dann eine semantische Folgerung der Formelmenge , d. h. , wenn für jede Interpretation , für die alle Formeln der Formelmenge wahr sind, auch die Formel wahr ist. Das Deduktionstheorem setzt diese allgemeine Definition einer semantischen Folgerung in Beziehung zur Implikation. Es bildet damit einen der wesentlichen Mechanismen, um den semantischen Begriff der Folgerung in Computersystemen durch rein formale Manipulationen handhabbar zu machen (siehe Ableitung in der Informatik). Es ist daher eng verwandt mit dem Widerlegungstheorem.

Das Deduktionstheorem für Ableitungen (⊢)

Im Bereich der Kalküle wird eine andere Definition des Deduktionstheorems verwendet, die sich rein auf der syntaktischen Ebene bewegt. Diese Variante des Deduktionstheorems wurde bereits um 1930 von Jacques Herbrand und (unabhängig von diesem und nahezu gleichzeitig) von Alfred Tarski gefunden und bewiesen. Im Zentrum dieser Definition steht im Gegensatz zur semantischen Folgerung die (syntaktische) Ableitung. Diese wird wie im oben beschriebenen Deduktionstheorem in ein Verhältnis zur Implikation gesetzt:

Wenn

dann

David Hilbert und Paul Bernays formulieren dies so: „Wenn aus einer Formel A eine Formel B in solcher Weise ableitbar ist [...], dann ist die Formel A → B ohne Benutzung der Formel A ableitbar.“

In vielen Kalkülen gilt auch die Umkehrung. Das heißt, ist aus einer Menge die Formel A → B ableitbar, so auch die Formel B unter Zuhilfenahme der zusätzlichen Hypothese A. Gilt in einem Kalkül der Modus ponens, so ist diese Schlussrichtung trivial.

Einzelnachweise

  1. David Hilbert, Paul Bernays: Grundlagen der Mathematik, Band 2, Berlin: 1939, Seite 387.

Siehe auch

Literatur

  • Franz von Kutschera, Alfred Breitkopf: Einführung in die moderne Logik, 8. Aufl. (2007), ISBN 978-3-495-482711, S. 72–75 (Beweis des Deduktionstheorems)
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Unter dem Begriff Deduktionstheorem sind zwei eng verwandte Theoreme bekannt die in der mathematischen Logik von Bedeutung sind Eine Variante des Theorems auch als Folgerungstheorem bekannt zielt auf den Begriff der semantischen Folgerung ab Die andere Variante die innerhalb von Kalkulen Anwendung findet macht statt der semantischen Folgerung die syntaktische Ableitung zum Ausgangspunkt In beiden Fallen wird eine Beziehung zur materialen Implikation hergestellt Inhaltsverzeichnis 1 Das Deduktionstheorem fur semantische Folgerungen 2 Das Deduktionstheorem fur Ableitungen 3 Einzelnachweise 4 Siehe auch 5 LiteraturDas Deduktionstheorem fur semantische Folgerungen BearbeitenDie semantische Fassung des Deduktionstheorems lautet wie folgt Eine Formel B displaystyle B ist genau dann eine semantische Folgerung der Formelmenge T displaystyle T mit T A 1 A 2 A n displaystyle T A 1 A 2 dots A n formal T B displaystyle T models B wenn die Implikation A 1 A 2 A n B displaystyle A 1 land A 2 land dots land A n rightarrow B allgemeingultig d h eine Tautologie ist in klassischer Logik ist das genau dann der Fall wenn die Implikation fur jede mogliche Interpretation wahr ist Allgemein ist in klassischer Logik eine Formel B displaystyle B genau dann eine semantische Folgerung der Formelmenge T displaystyle T d h T B displaystyle T models B wenn fur jede Interpretation I displaystyle I fur die alle Formeln der Formelmenge T displaystyle T wahr sind auch die Formel B displaystyle B wahr ist Das Deduktionstheorem setzt diese allgemeine Definition einer semantischen Folgerung in Beziehung zur Implikation Es bildet damit einen der wesentlichen Mechanismen um den semantischen Begriff der Folgerung in Computersystemen durch rein formale Manipulationen handhabbar zu machen siehe Ableitung in der Informatik Es ist daher eng verwandt mit dem Widerlegungstheorem Das Deduktionstheorem fur Ableitungen BearbeitenIm Bereich der Kalkule wird eine andere Definition des Deduktionstheorems verwendet die sich rein auf der syntaktischen Ebene bewegt Diese Variante des Deduktionstheorems wurde bereits um 1930 von Jacques Herbrand und unabhangig von diesem und nahezu gleichzeitig von Alfred Tarski gefunden und bewiesen Im Zentrum dieser Definition steht im Gegensatz zur semantischen Folgerung die syntaktische Ableitung Diese wird wie im oben beschriebenen Deduktionstheorem in ein Verhaltnis zur Implikation gesetzt Wenn T A B displaystyle T A vdash B dann T A B displaystyle T vdash A rightarrow B David Hilbert und Paul Bernays formulieren dies so Wenn aus einer Formel A eine Formel B in solcher Weise ableitbar ist dann ist die Formel A B ohne Benutzung der Formel A ableitbar 1 In vielen Kalkulen gilt auch die Umkehrung Das heisst ist aus einer Menge die Formel A B ableitbar so auch die Formel B unter Zuhilfenahme der zusatzlichen Hypothese A Gilt in einem Kalkul der Modus ponens so ist diese Schlussrichtung trivial Einzelnachweise Bearbeiten David Hilbert Paul Bernays Grundlagen der Mathematik Band 2 Berlin 1939 Seite 387 Siehe auch BearbeitenModelltheorie Wissensreprasentation mit Logik Negation zu Logik Polaritat siehe Schaltalgebra MetawissenschaftLiteratur BearbeitenFranz von Kutschera Alfred Breitkopf Einfuhrung in die moderne Logik 8 Aufl 2007 ISBN 978 3 495 482711 S 72 75 Beweis des Deduktionstheorems Abgerufen von https de wikipedia org w index php title Deduktionstheorem amp oldid 213360201