Tautologi (logik)

Deduktion
Tautologi | Kontradiktion Sann | Giltig | Sund
Modallogik
Logisk sanning | Logisk omöjlighet Nödvändighet | Möjlighet

Härledningsbegrepp
Medför - Följer av Bevis – Bevisbarhet Giltig - Giltighet Sund - Sundhet Konsekvent - Konsekvens Fullständig – Fullständighet Teorem Tautologi Kontradiktion Konträra satser Deduktion - Härledbarhet
Närliggande begrepp
Implikation Logisk sanning Sanning Motsägelse

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]

Översikt och definition

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

${\displaystyle (\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:

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

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

${\displaystyle A\to B}$, som inte är en tautologi.[4]

Exempel på tautologier

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

Formel	Naturligt språk	Kommentar
${\displaystyle \lnot \lnot A\leftrightarrow A}$	Negering av icke-A är detsamma som A	Reduktion av dubbel negation
${\displaystyle A\lor \lnot A}$	A eller icke-A	Formeln är ett sätt att uttrycka lagen om det uteslutna tredje.
${\displaystyle 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
${\displaystyle (\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.
${\displaystyle \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.
${\displaystyle (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.
${\displaystyle (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.

Se även

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

Referenser

Noter

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.

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.