Tautologie (Logik) - Tautology (logic)

In der mathematischen Logik ist eine Tautologie (aus dem Griechischen : ταυτολογία ) eine Formel oder Aussage, die in jeder möglichen Interpretation wahr ist . Ein Beispiel ist "x=y oder x≠y". In ähnlicher Weise gilt „entweder der Ball ist grün oder der Ball ist nicht grün“ immer wahr, unabhängig von der Farbe des Balls.

Der Philosoph Ludwig Wittgenstein wandte den Begriff erstmals 1921 auf Redundanzen der Aussagenlogik an, wobei er sich an die Rhetorik anlehnte , wo eine Tautologie eine sich wiederholende Aussage ist. In der Logik ist eine Formel erfüllbar, wenn sie unter mindestens einer Interpretation wahr ist, und somit ist eine Tautologie eine Formel, deren Negation unerfüllbar ist. Mit anderen Worten, es kann nicht falsch sein. Es kann nicht unwahr sein.

Unerfüllbare Aussagen, sowohl durch Negation als auch durch Affirmation, werden formal als Widersprüche bezeichnet . Eine Formel, die weder eine Tautologie noch ein Widerspruch ist, wird als logisch kontingent bezeichnet .

Eine solche Formel kann basierend auf den Werten, die ihren propositionalen Variablen zugewiesen sind, entweder wahr oder falsch gemacht werden. Die Doppeldrehkreuz- Notation wird verwendet, um anzuzeigen, dass S eine Tautologie ist. Tautologie wird manchmal durch „V pq “ und Widerspruch durch „O pq “ symbolisiert . Das T- Symbol wird manchmal verwendet, um eine willkürliche Tautologie zu bezeichnen, wobei das duale Symbol ( falsum ) einen willkürlichen Widerspruch darstellt; in jeder Symbolik kann eine Tautologie für den Wahrheitswert " wahr " ersetzt werden, wie er beispielsweise durch "1" symbolisiert wird. ${\displaystyle \vDash S}$${\displaystyle \top}$${\displaystyle \bot}$

Tautologien sind ein Schlüsselkonzept in der Aussagenlogik , wo eine Tautologie als eine Aussageformel definiert ist, die unter jeder möglichen booleschen Bewertung ihrer Aussagevariablen wahr ist . Eine Schlüsseleigenschaft von Tautologien in der Aussagenlogik ist, dass es eine effektive Methode gibt, um zu testen, ob eine gegebene Formel immer erfüllt ist (äquiv., ob ihre Negation unerfüllbar ist).

Die Definition der Tautologie kann auf Sätze in der Prädikatenlogik ausgedehnt werden , die Quantoren enthalten können – ein Merkmal, das in Sätzen der Aussagenlogik fehlt. Tatsächlich gibt es in der Aussagenlogik keinen Unterschied zwischen einer Tautologie und einer logisch gültigen Formel. Im Kontext der Prädikatenlogik definieren viele Autoren eine Tautologie als einen Satz, der erhalten werden kann, indem man eine Tautologie der Aussagenlogik nimmt und jede Aussagevariable einheitlich durch eine Formel erster Ordnung ersetzt (eine Formel pro Aussagevariable). Die Menge solcher Formeln ist eine echte Teilmenge der Menge logisch gültiger Sätze der Prädikatenlogik (dh Sätze, die in jedem Modell wahr sind ).

Geschichte

Das Wort Tautologie wurde von den alten Griechen verwendet, um eine Aussage zu beschreiben, die nur dadurch bestätigt wurde, dass sie zweimal dasselbe sagte, eine abwertende Bedeutung, die immer noch für rhetorische Tautologien verwendet wird . Zwischen 1800 und 1940 gewann das Wort eine neue Bedeutung in der Logik und wird derzeit in der mathematischen Logik verwendet , um eine bestimmte Art von Aussageformel zu bezeichnen, ohne die abwertende Konnotation, die es ursprünglich besaß.

Immanuel Kant schrieb 1800 in seinem Buch Logik :

Die Identität von Begriffen in analytischen Urteilen kann entweder explizit ( explica ) oder nicht-explizit ( implicita ) sein. Im ersteren Fall sind analytische Sätze tautologisch.

Hier bezieht sich analytische Aussage auf eine analytische Wahrheit , eine Aussage in natürlicher Sprache, die allein aufgrund der verwendeten Begriffe wahr ist.

1884 schlug Gottlob Frege in seinen Grundlagen vor, dass eine Wahrheit genau dann analytisch ist, wenn sie logisch abgeleitet werden kann. Er hielt jedoch eine Unterscheidung zwischen analytischen Wahrheiten (dh Wahrheiten, die nur auf der Bedeutung ihrer Begriffe beruhen) und Tautologien (dh inhaltslosen Aussagen) aufrecht.

In seinem Tractatus Logico-Philosophicus von 1921 schlug Ludwig Wittgenstein vor, dass Aussagen, die durch logische Deduktion abgeleitet werden können, sowohl tautologisch (bedeutungsleer) als auch analytische Wahrheiten sind. Henri Poincaré hatte 1905 in Science and Hypothesis ähnliche Bemerkungen gemacht . Obwohl Bertrand Russell zunächst gegen diese Bemerkungen von Wittgenstein und Poincaré argumentierte und behauptete, mathematische Wahrheiten seien nicht nur nicht-tautolog, sondern synthetisch , sprach er sich später 1918 dafür aus :

Alles, was ein Satz der Logik ist, muss in irgendeiner Weise wie eine Tautologie sein. Es muss etwas sein, das eine besondere Qualität hat, die ich nicht zu definieren weiß, die zu logischen Sätzen gehört, zu anderen aber nicht.

Hier logischer Satz bezieht sich auf einen Satz , dass beweisbar ist , die Gesetze der Logik.

In den 1930er Jahren wurde die Formalisierung der Semantik der Aussagenlogik in Form von Wahrheitszuweisungen entwickelt. Der Begriff "Tautologie" wurde auf diejenigen Aussagenformeln angewendet, die unabhängig von der Wahrheit oder Falschheit ihrer Aussagevariablen wahr sind. Einige frühe Bücher über Logik (wie Symbolic Logic von CI Lewis und Langford, 1932) verwendeten den Begriff für jeden Satz (in jeder formalen Logik), der allgemein gültig ist. In Präsentationen danach (wie Stephen Kleene 1967 und Herbert Enderton 2002) ist es üblich, die Tautologie zu verwenden, um auf eine logisch gültige Aussageformel zu verweisen, aber im Kontext der ersten Bestelllogik (siehe unten ) .

Hintergrund

Aussagenlogik beginnt mit Aussagenvariablen , atomaren Einheiten, die konkrete Aussagen darstellen. Eine Formel besteht aus propositionalen Variablen, die durch logische Verknüpfungen verbunden sind, die so aufgebaut sind, dass die Wahrheit der Gesamtformel aus der Wahrheit oder Falschheit jeder Variablen abgeleitet werden kann. Eine Bewertung ist eine Funktion, die jede Aussagevariable entweder T (für Wahrheit) oder F (für Falsch) zuordnet. Also , indem die Aussagevariablen unter Verwendung von A und B , die binären Konnektive und repräsentiert Disjunktion und Verbindung ist und der unären Binde- darstellt Negation : kann die folgende Formel erhalten werden . ${\displaystyle \lor}$${\displaystyle \land}$${\displaystyle \lnot}$${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$

Eine Bewertung hier muss jedem von A und B entweder T oder F zuordnen. Aber egal, wie diese Zuordnung vorgenommen wird, die Gesamtformel wird wahr. Denn wenn die erste Konjunktion durch eine bestimmte Bewertung nicht erfüllt wird, dann wird einem von A und B F zugewiesen, was dazu führt, dass einer der folgenden Disjunkte T zugewiesen wird. ${\displaystyle (A\land B)}$

Definition und Beispiele

Eine aussagenlogische Formel ist eine Tautologie, wenn die Formel selbst immer wahr ist, unabhängig davon, welche Bewertung für die aussagenlogischen Variablen verwendet wird . Es gibt unendlich viele Tautologien. Beispiele beinhalten:

• ${\displaystyle (A\oder\lnot A)}$(" A oder nicht A "), das Gesetz der ausgeschlossenen Mitte . Diese Formel hat nur eine Aussagevariable, A . Jede Bewertung für diese Formel muss per Definition assign A einer der Wahrheitswerte wahr oder falsch , und assign A den anderen Wahrheitswert. Zum Beispiel "Die Katze ist schwarz oder die Katze ist nicht schwarz".${\displaystyle \lnot}$
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$("Wenn A impliziert B , dann impliziert nicht- B nicht- A " und umgekehrt), was das Gesetz der Kontraposition ausdrückt . Zum Beispiel: "Wenn es ein Buch ist, ist es blau; wenn es nicht blau ist, ist es kein Buch."
• ${\displaystyle ((\not A\to B)\land (\not A\to \lnot B))\to A}$("Wenn nicht- A sowohl B als auch seine Negation not- B impliziert , dann muss nicht- A falsch sein, dann muss A wahr sein"), was das Prinzip ist, das als reductio ad absurdum bekannt ist . Zum Beispiel: "Wenn es nicht blau ist, ist es ein Buch, wenn es nicht blau ist, ist es auch kein Buch, also ist es blau."
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$(„Wenn nicht sowohl A als auch B , dann nicht- A oder nicht- B “ und umgekehrt), was als De Morgansches Gesetz bekannt ist . "Wenn es entweder kein Buch oder nicht blau ist, ist es entweder kein Buch oder es ist nicht blau oder auch nicht."
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}$("Wenn A B impliziert und B impliziert C , dann impliziert A C "), das ist das Prinzip, das als Syllogismus bekannt ist . "Wenn es ein Buch ist, dann ist es blau, wenn es blau ist, steht es in diesem Regal. Wenn es also ein Buch ist, steht es in diesem Regal."
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$("Wenn mindestens eines von A oder B wahr ist und jedes C impliziert , dann muss auch C wahr sein"), das ist das Prinzip, das als Beweis durch Fälle bekannt ist . "Bücher und blaue Dinge sind in diesem Regal. Wenn es entweder ein Buch oder blau ist, ist es in diesem Regal."

Eine minimale Tautologie ist eine Tautologie, die nicht die Instanz einer kürzeren Tautologie ist.

• ${\displaystyle (A\lor B)\to (A\lor B)}$ist eine Tautologie, aber keine minimale, weil sie eine Instanz von .${\displaystyle C\nach C}$

Tautologien überprüfen

Das Problem der Feststellung, ob eine Formel eine Tautologie ist, ist in der Aussagenlogik von grundlegender Bedeutung. Wenn in einer Formel n Variablen vorkommen, gibt es 2 ⁿ unterschiedliche Bewertungen für die Formel. Daher ist die Aufgabe, zu bestimmen, ob die Formel eine Tautologie ist oder nicht, eine endliche und mechanische Aufgabe: Man braucht nur den Wahrheitswert der Formel unter jeder ihrer möglichen Bewertungen zu bewerten . Eine algorithmische Methode, um zu überprüfen, ob jede Bewertung die Formel wahr macht, besteht darin, eine Wahrheitstabelle zu erstellen , die jede mögliche Bewertung enthält.

Betrachten Sie zum Beispiel die Formel

${\displaystyle ((A\land B)\to C)\Linksrightarrow (A\to (B\to C)).}$

Es gibt 8 mögliche Bewertungen für die Aussagenvariablen A , B , C , repräsentiert durch die ersten drei Spalten der folgenden Tabelle. Die verbleibenden Spalten zeigen die Wahrheit von Teilformeln der obigen Formel und gipfeln in einer Spalte, die den Wahrheitswert der ursprünglichen Formel unter jeder Bewertung zeigt.

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C}$	${\displaystyle A\land B}$	${\displaystyle (A\land B)\to C}$	${\displaystyle B\nach C}$	${\displaystyle A\to (B\to C)}$	${\displaystyle ((A\land B)\to C)\Linksrightarrow (A\to (B\to C))}$
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	T	T
T	F	F	F	T	T	T	T
F	T	T	F	T	T	T	T
F	T	F	F	T	F	T	T
F	F	T	F	T	T	T	T
F	F	F	F	T	T	T	T

Da jede Zeile der letzten Spalte T zeigt , wird der fragliche Satz als Tautologie verifiziert.

Es ist auch möglich, ein deduktives System (dh ein Beweissystem) für die Aussagenlogik zu definieren, als eine einfachere Variante der deduktiven Systeme, die für die Logik erster Ordnung verwendet werden (siehe Kleene 1967, Abschnitt 1.9 für ein solches System). Ein Beweis einer Tautologie in einem geeigneten Deduktionssystem kann viel kürzer sein als eine vollständige Wahrheitstabelle (eine Formel mit n Aussagenvariablen erfordert eine Wahrheitstabelle mit 2 ⁿ Zeilen, die mit zunehmendem n schnell undurchführbar wird ). Beweissysteme werden auch für das Studium der intuitionistischen Aussagenlogik benötigt, bei der die Methode der Wahrheitstafeln nicht angewendet werden kann, weil das Gesetz der ausgeschlossenen Mitte nicht vorausgesetzt wird.

Tautologische Implikation

Eine Formel R heißt tautologisch eine Formel S, wenn jede Bewertung, die R wahr macht, auch S wahr macht. Diese Situation wird bezeichnet . Sie entspricht einer Tautologie der Formel (Kleene 1967, S. 27). ${\displaystyle R\models S}$${\displaystyle R\to S}$

Nehmen wir zum Beispiel sein . Dann ist keine Tautologie, denn jede Bewertung, die falsch macht, wird falsch machen . Aber jede Bewertung, die wahr macht , wird wahr, denn es ist eine Tautologie. Sei die Formel . Dann , weil jede Bewertung befriedigend machen echte und macht damit wahr. ${\displaystyle S}$${\displaystyle A\land (B\lor\lnot B)}$${\displaystyle S}$${\displaystyle A}$${\displaystyle S}$${\displaystyle A}$${\displaystyle S}$${\displaystyle B\oder\lnot B}$${\displaystyle R}$${\displaystyle A\land C}$${\displaystyle R\models S}$${\displaystyle R}$${\displaystyle A}$${\displaystyle S}$

Aus der Definition folgt, dass, wenn eine Formel ein Widerspruch ist, tautologisch jede Formel impliziert, weil es keine Wahrheitsbewertung gibt, die bewirkt , dass wahr ist, und so ist die Definition der tautologischen Implikation trivialerweise erfüllt. In ähnlicher Weise ist if eine Tautologie, dann wird tautologisch von jeder Formel impliziert. ${\displaystyle R}$${\displaystyle R}$${\displaystyle R}$${\displaystyle S}$${\displaystyle S}$

Auswechslung

Es gibt ein allgemeines Verfahren, die Substitutionsregel , die es erlaubt, aus einer gegebenen Tautologie zusätzliche Tautologien zu konstruieren (Kleene 1967, Abschnitt 3). Nehmen wir an, S sei eine Tautologie und für jede Aussagevariable A in S wird ein fester Satz S _A gewählt. Dann ist der Satz, der durch Ersetzen jeder Variablen A in S durch den entsprechenden Satz S _{A erhalten} wird, ebenfalls eine Tautologie.

Sei zum Beispiel S die Tautologie

${\displaystyle (A\land B)\lor \lnot A\lor \lnot B}$.

Lassen S _A sein und lassen S _B sein . ${\displaystyle C\lor D}$${\displaystyle C\to E}$

Aus der Substitutionsregel folgt, dass der Satz

${\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}$

Semantische Vollständigkeit und Solidität

Ein axiomatisches System ist vollständig, wenn jede Tautologie ein (aus Axiomen ableitbares) Theorem ist. Ein axiomatisches System ist Klang , wenn jeder Satz eine Tautologie ist.

Effiziente Verifikation und das Boolesche Erfüllbarkeitsproblem

Das Problem der Konstruktion praktischer Algorithmen zur Bestimmung, ob Sätze mit einer großen Anzahl von propositionalen Variablen Tautologien sind, ist ein Gebiet der aktuellen Forschung im Bereich des automatisierten Theorembeweisens .

Die oben dargestellte Methode der Wahrheitstabellen ist nachweislich richtig – die Wahrheitstabelle für eine Tautologie endet in einer Spalte mit nur T , während die Wahrheitstabelle für einen Satz, der keine Tautologie ist, eine Zeile enthält, deren letzte Spalte F ist , und die Die Bewertung, die dieser Zeile entspricht, ist eine Bewertung, die den getesteten Satz nicht erfüllt. Diese Methode zur Verifikation von Tautologien ist ein effektives Verfahren , das heißt, bei unbegrenzten Rechenressourcen kann immer mechanistisch festgestellt werden, ob ein Satz eine Tautologie ist. Dies bedeutet insbesondere, dass die Menge der Tautologien über einem festen endlichen oder abzählbaren Alphabet eine entscheidbare Menge ist .

Als effizientes Verfahren sind Wahrheitstabellen jedoch dadurch eingeschränkt, dass die Anzahl der zu überprüfenden Bewertungen mit 2 ^k ansteigt , wobei k die Anzahl der Variablen in der Formel ist. Dieses exponentielle Wachstum der Berechnungslänge macht die Wahrheitstabellenmethode für Formeln mit Tausenden von Aussagenvariablen unbrauchbar, da moderne Computerhardware den Algorithmus nicht in einem praktikablen Zeitraum ausführen kann.

Das Problem zu bestimmen, ob es eine Bewertung gibt, die eine Formel wahr macht, ist das Boolesche Erfüllbarkeitsproblem ; das Problem, Tautologien zu überprüfen, ist diesem Problem äquivalent, da die Überprüfung, dass ein Satz S eine Tautologie ist, der Überprüfung entspricht, dass es keine Bewertung gibt, die . Es ist bekannt, dass das Boolesche Erfüllbarkeitsproblem NP-vollständig ist , und es wird allgemein angenommen, dass es keinen Polynomialzeitalgorithmus gibt, der es ausführen kann. Folglich ist die Tautologie co-NP-vollständig . Die aktuelle Forschung konzentriert sich darauf, Algorithmen zu finden, die bei speziellen Formelklassen gut funktionieren oder im Durchschnitt schnell terminieren, obwohl einige Eingaben dafür sorgen können, dass sie viel länger dauern. ${\displaystyle \lnot S}$

Tautologien versus Gültigkeiten in der Logik erster Ordnung

Die grundlegende Definition einer Tautologie erfolgt im Kontext der Aussagenlogik. Die Definition lässt sich jedoch auf Sätze in der Logik erster Ordnung erweitern . Diese Sätze können im Gegensatz zu Sätzen der Aussagenlogik Quantoren enthalten. Im Kontext der Logik erster Ordnung wird zwischen logischen Gültigkeiten , Sätzen, die in jedem Modell wahr sind, und Tautologien , die eine echte Teilmenge der logischen Gültigkeiten erster Ordnung sind, unterschieden. Im Kontext der Aussagenlogik fallen diese beiden Begriffe zusammen.

Eine Tautologie in der Logik erster Ordnung ist ein Satz, der erhalten werden kann, indem man eine Tautologie der Aussagenlogik nimmt und jede Aussagevariable einheitlich durch eine Formel erster Ordnung ersetzt (eine Formel pro Aussagevariable). Weil zum Beispiel eine Tautologie der Aussagenlogik ist, ist es eine Tautologie der Logik erster Ordnung. In ähnlicher Weise ist in einer Sprache erster Ordnung mit einem einären Relationssymbol R , S , T der folgende Satz eine Tautologie: ${\displaystyle A\oder\lnot A}$${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$

${\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx) ).}$

Es wird durch Ersetzen mit , mit und mit in der propositionalen Tautologie erhalten . ${\displaystyle A}$${\displaystyle \exists xRx}$${\displaystyle B}$${\displaystyle \lnot \exists xSx}$${\displaystyle C}$${\displaystyle \forall xTx}$${\displaystyle ((A\land B)\to C)\Linksrightarrow (A\to (B\to C))}$

Nicht alle logischen Gültigkeiten sind Tautologien in der Logik erster Ordnung. Zum Beispiel der Satz

${\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx}$

ist in jeder Interpretation erster Ordnung wahr, entspricht aber dem Aussagensatz, der keine Tautologie der Aussagenlogik ist. ${\displaystyle A\nach B}$

Siehe auch

Normalformen

• Algebraische Normalform
• Konjunktive Normalform
• Disjunktive Normalform
• Logikoptimierung

Verwandte logische Themen

Verweise

Weiterlesen

• Bocheński, JM (1959) Précis of Mathematical Logic , übersetzt aus der französischen und deutschen Ausgabe von Otto Bird, Dordrecht , Südholland : D. Reidel .
• Enderton, HB (2002) Eine mathematische Einführung in die Logik , Harcourt / Academic Press , ISBN  0-12-238452-0 .
• Kleene, SC (1967) Mathematical Logic , Nachdruck 2002, Dover Publications , ISBN  0-486-42533-9 .
• Reichenbach, H. (1947). Elemente der Symbolischen Logik , Nachdruck 1980, Dover, ISBN  0-486-24004-5
• Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung", Annalen der Naturphilosophie (Leipzig), V. 14, S. 185–262, Nachdruck in englischer Übersetzung als Tractatus logico-philosophicus , New York City und London , 1922.

Externe Links

• "Tautologie" , Enzyklopädie der Mathematik , EMS Press , 2001 [1994]