Tautologi (logik)

Tautologi är en benämning på en sats inom satslogiken, som är sann för varje tillordning av sanningsvärden till dess satssymboler. Ludvig Wittgenstein introducerade begreppet 1921 i verket Tractatus Logico-Philosophicus. Negationen av en tautologi är en kontradiktion.

Översikt och definition

Att en sats S i satslogiken är en tautologi, skrivs med symboler: <math>\vDash S</math> . Ett enkelt exempel på en satslogisk tautologi är: <math>A \lor \lnot A</math> , som uttrycker den språkliga satsen: A eller icke-A.

Emil L. Post visade att det satslogiska systemet PS med språket P är semantiskt fullständigt och därmed att varje tautologi S, i det satslogiska språket P är ett teorem i systemet PS, vilket symboliskt kan uttryckas enligt följande: Om <math>\models_{P} S</math>, så <math>\vdash_{PS} S</math>.

Trots att den logiska betydelsen av ordet "tautologi" är helt skild från den äldre rent språkliga betydelsen av ordet, är sammanblandning av de två begreppen vanlig.

Begreppet tautologi är ursprungligen definierat i satslogiken, men har även utvidgats till predikatlogiken, på så sätt att satslogikens satssymboler ersätts med predikatlogiska formler.

Eftersom <math>A \lor \lnot A</math> är en tautologi i satslogiken, så är exempelvis:

<math> (\forall x ( x = x)) \lor (\lnot \forall x (x = x))</math> en tautologi i predikatlogiken.

I satslogiken är alla satslogiskt giltiga formler även tautologier, vilket dock inte gäller i predikatlogiken eller generellt i första ordningens logik. Exempelvis är satsen:

<math>(\forall x Rx) \to \lnot \exists x \lnot Rx</math>

satslogiskt giltig, men inte en tautologi eftersom den motsvaras av den satslogiska satsen

<math>A \to B</math>, som inte är en tautologi.

Exempel på tautologier

De satslogiska konnektiven har följande proritetsordning: <math> \neg , \land , \lor , \rightarrow , \leftrightarrow</math>. A, B och C är satssymboler.

Formel	Naturligt språk	Kommentar
<math>\lnot \lnot A \leftrightarrow A</math>	Negering av icke-A är detsamma som A	Reduktion av dubbel negation
<math>A \lor \lnot A</math>	A eller icke-A	Formeln är ett sätt att uttrycka lagen om det uteslutna tredje.
<math>A \to B \leftrightarrow \lnot B \to \lnot A</math>	Om A implicerar B så implicerar icke-B icke-A, och omvänt.	Formeln uttrycker kontraposition
<math>(\lnot A \to B) \land (\lnot A \to \lnot B) \to A</math>	Om icke-A implicerar både B och dess negation icke-B, så följer att icke-A är falskt, och således att A är sant.	Formeln visar den princip som också kallas reductio ad absurdum.
<math>\lnot(A \land B) \leftrightarrow \lnot A \lor \lnot B</math>	Om inte både A och B, så icke-A eller icke-B, och omvänt.	Formeln uttrycker en av de Morgans lagar.
<math>(A \to B) \land (B \to C) \to (A \to C)</math>	Om A implicerar B och B implicerar C, så implicerar A, C.	Formeln är ett exempel på en syllogism.
<math>(A \lor B) \land (A \to C) \land (B \to C) \to C</math>	Om åtminstone A eller B är sant, och om båda implicerar C, så måste C också vara sant.	Formeln är ett exempel på uteslutningsmetoden.

Se även

• Tautolog implikation
• Satslogik
• Boolesk algebra
• Deduktionsteoremet
• Reductio ad absurdum
• Härledningsbegrepp
• Kontradiktion
• Teorem

Referenser

Källor

• Raymond M. Smullyan, First-Order Logic, Springer-Verlag, Berlin, Heidelberg, New York, 1968.
• Stephen Cole Kleene, Mathematical Logic, Wiley and Sons, New York 1967.
• Geoffrey Hunter, Metalogic, An Introduction to the Metatheory of Standard First-Order Logic, MacMillan, London 1971.