Tautologi (logik)

Från Wikipedia
Hoppa till: navigering, sök
För andra betydelser, se tautologi.
Deduction symbols2.gif
Deduktion
Tautologi | Kontradiktion
Sann | Giltig | Sund
Modallogik
Logisk sanning | Logisk omöjlighet
Nödvändighet | Möjlighet
Härledningsbegrepp
Närliggande begrepp

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

Att en sats S i satslogiken är en tautologi, skrivs med symboler: \vDash S . Ett enkelt exempel på på en satslogisk tautologi är: A \lor \lnot A , 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 \models_{P} S, så \vdash_{PS} S.

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.[3]

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 A \lor \lnot A är en tautologi i satslogiken, så är exempelvis:

 (\forall x ( x = x)) \lor (\lnot \forall x (x = x)) 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:

(\forall x Rx) \to \lnot \exists x \lnot Rx

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

A \to B, som inte är en tautologi.[4]


Exempel på tautologier[redigera | redigera wikitext]

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

Formel Naturligt språk Kommentar
\lnot \lnot A \leftrightarrow A Negering av icke-A är detsamma som A Reduktion av dubbel negation
A \lor \lnot A A eller icke-A Formeln är ett sätt att uttrycka lagen om det uteslutna tredje.
A \to B \leftrightarrow \lnot B \to \lnot A Om A implicerar B så implicerar icke-B icke-A, och omvänt. Formeln uttrycker kontraposition
(\lnot A \to B) \land (\lnot A \to \lnot B) \to A 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.
\lnot(A \land B) \leftrightarrow \lnot A \lor \lnot B Om inte både A och B, så icke-A eller icke-B, och omvänt. Formeln uttrycker en av de Morgans lagar.
(A \to B) \land (B \to C) \to (A \to C)  Om A implicerar B och B implicerar C, så implicerar A, C. Formeln är ett exempel på en syllogism.
(A \lor B) \land (A \to C) \land (B \to C) \to C  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.

Referenser[redigera | redigera wikitext]

Källor[redigera | redigera wikitext]

  • 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.

Noter[redigera | redigera wikitext]

  1. ^ Alonzo Church, Introduction to Mathematical Logic. Princeton University Press, 1956.
  2. ^ Jean van Heijenoort, From Frege to Gödel, A Source Book in Mathematical Logic, Harvard University Press 1967.
  3. ^ Richard von Mises, Positivism: A Study in Human Understanding, Cambridge University Press 1951.
  4. ^ Geoffrey Hunter, Metalogic, An Introduction to the Metatheory of Standard First-Order Logic, MacMillan, London 1971.

Se även[redigera | redigera wikitext]