Tautologi (logik)

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;
	Denna tabell: visa • redigera

Deduktion
	Tautologi \| Kontradiktion; Sann \| Giltig \| Sund
Modallogik
	Logisk sanning \| Logisk omöjlighet; Nödvändighet \| Möjlighet
	Denna tabell: visa • redigera

För det språkvetenskapliga begreppet, se Tautologi (språkvetenskap).

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: $\vDash S$ . Ett enkelt exempel 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 xRx)\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

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.

Se även

Referenser

Noter

^ Alonzo Church, Introduction to Mathematical Logic. Princeton University Press, 1956.
^ Jean van Heijenoort, From Frege to Gödel, A Source Book in Mathematical Logic, Harvard University Press 1967.
^ Richard von Mises, Positivism: A Study in Human Understanding, Cambridge University Press 1951.
^ 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.

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

[1]

[2]

[3]

[4]