Tautologi (logik)

Den här artikeln handlar om tautologi i formell logik. För annan användning, se Tautologi (disambiguation) .

I matematisk logik är en tautologi (från grekiska : ταυτολογία ) en formel eller ett påstående som är sant i alla möjliga tolkningar . Ett exempel är "x=y eller x≠y". På samma sätt är "antingen är bollen grön eller så är bollen inte grön" alltid sant, oavsett kulans färg.

Filosofen Ludwig Wittgenstein tillämpade termen först på redundanser av propositionell logik 1921, med lån från retorik , där en tautologi är ett upprepande uttalande. I logiken är en formel tillfredsställbar om den är sann under åtminstone en tolkning, och således är en tautologi en formel vars negation är otillfredsställande. Det kan med andra ord inte vara falskt. Det kan inte vara osant.

Otillfredsställande uttalanden, både genom negation och bekräftelse, är formellt kända som motsägelser . En formel som varken är en tautologi eller en motsägelse sägs vara logiskt betingad .

En sådan formel kan göras antingen sann eller falsk baserat på de värden som tilldelats dess propositionella variabler. Den dubbla vändkorsnotationen ⊨ $\displaystyle \vDash S}$ används för att indikera att S är en tautologi. Tautologi symboliseras ibland med "V pq ", och motsägelse med "O pq ". Tee - symbolen $\top$ används ibland för att beteckna en godtycklig tautologi, där den dubbla symbolen $\bot$ ( falsum ) representerar en godtycklig motsägelse; I vilken symbol som helst kan en tautologi ersättas med sanningsvärdet " sant ", som symboliseras till exempel med "1".

Tautologier är ett nyckelbegrepp inom propositionell logik , där en tautologi definieras som en propositionsformel som är sann under varje möjlig boolesk värdering av dess propositionella variabler . En nyckelegenskap för tautologier inom propositionell logik är att det finns en effektiv metod för att testa om en given formel alltid är uppfylld (mots. om dess negation är otillfredsställande).

Definitionen av tautologi kan utvidgas till meningar i predikatlogik , som kan innehålla kvantifierare - ett särdrag som saknas i meningar med propositionell logik. I propositionell logik finns det faktiskt ingen skillnad mellan en tautologi och en logiskt giltig formel. I samband med predikatlogik definierar många författare en tautologi som en mening som kan erhållas genom att ta en tautologi av propositionell logik och enhetligt ersätta varje propositionsvariabel med en första ordningens formel (en formel per propositionsvariabel). Uppsättningen av sådana formler är en riktig delmängd av uppsättningen av logiskt giltiga meningar av predikatlogik (dvs meningar som är sanna i varje modell ).

Historia

Ordet tautologi användes av de gamla grekerna för att beskriva ett uttalande som påstods vara sant bara genom att säga samma sak två gånger, en nedsättande betydelse som fortfarande används för retoriska tautologier . Mellan 1800 och 1940 fick ordet ny betydelse inom logiken, och används för närvarande i matematisk logik för att beteckna en viss typ av satsformel, utan de nedsättande konnotationer som det ursprungligen hade.

År 1800 skrev Immanuel Kant i sin bok Logik :

Identiteten för begrepp i analytiska bedömningar kan vara antingen explicit ( explicita ) eller icke-explicit ( implicita ). I det förra fallet är analytiska satser tautologiska.

Här hänvisar analytisk proposition till en analytisk sanning , ett uttalande på naturligt språk som är sant enbart på grund av de inblandade termerna.

År 1884 föreslog Gottlob Frege i sin Grundlagen att en sanning är analytisk exakt om den kan härledas med hjälp av logik. Han upprätthöll dock en distinktion mellan analytiska sanningar (dvs. sanningar baserade endast på betydelsen av deras termer) och tautologier (dvs. uttalanden som saknar innehåll).

I sin Tractatus Logico-Philosophicus 1921 föreslog Ludwig Wittgenstein att påståenden som kan härledas genom logisk deduktion är tautologiska (tom meningsfulla), såväl som analytiska sanningar. Henri Poincaré hade gjort liknande kommentarer i Science and Hypothesis 1905. Även om Bertrand Russell först argumenterade mot dessa kommentarer av Wittgenstein och Poincaré, och hävdade att matematiska sanningar inte bara var icke-tautologa utan också syntetiska , talade han senare för dem 1918 :

Allt som är ett påstående av logik måste i någon eller annan mening vara som en tautologi. Det måste vara något som har någon speciell kvalitet, som jag inte vet hur man ska definiera, som hör till logiska satser men inte till andra.

Här hänvisar logisk proposition till en proposition som är bevisbar med hjälp av logikens lagar.

Under 1930-talet utvecklades formaliseringen av propositionell logiks semantik i termer av sanningsuppdrag. Termen "tautologi" började tillämpas på de propositionella formler som är sanna oavsett sanningen eller falskheten i deras propositionella variabler. Vissa tidiga böcker om logik (som Symbolic Logic av CI Lewis och Langford, 1932) använde termen för varje proposition (i vilken formell logik som helst) som är universellt giltig. Det är vanligt i presentationer efter detta (som Stephen Kleene 1967 och Herbert Enderton 2002) att använda tautologi för att hänvisa till en logiskt giltig propositionsformel, men för att upprätthålla en distinktion mellan "tautologi" och "logiskt giltig" i samband med första- orderlogik (se nedan ) .

Bakgrund

Huvudartikel: Propositionell logik

Propositionell logik börjar med propositionella variabler , atomenheter som representerar konkreta propositioner. En formel består av propositionella variabler sammankopplade med logiska bindemedel, byggda på ett sådant sätt att sanningen i den övergripande formeln kan härledas från sanningen eller falskheten i varje variabel. En värdering är en funktion som tilldelar varje propositionsvariabel till antingen T (för sanning) eller F (för falskhet). Så genom att använda propositionsvariablerna A och B , de binära kopplingarna $\lor$ och $\land$ representerar disjunktion respektive konjunktion , och det enära kopplingsmedlet $\lnot$ representerar negation , följande formel kan erhållas: $(A\land B)\lor (\lnot A)\lor (\lnot B)$ .

En värdering här måste tilldela var och en av A och B antingen T eller F. Men oavsett hur denna tilldelning görs kommer den övergripande formeln att bli sann. För om den första konjunktionen $(A\land B)$ inte uppfylls av en viss värdering, så tilldelas en av A och B F, vilket gör att en av följande disjunkter tilldelas T .

Definition och exempel

En formel för propositionell logik är en tautologi om formeln i sig alltid är sann, oavsett vilken värdering som används för propositionsvariablerna . Det finns oändligt många tautologier. Exempel inkluderar:

• $(A\lor \lnot A)$ (" A or not A "), lagen om utesluten mitten . Denna formel har bara en propositionsvariabel, A . Varje värdering för denna formel måste per definition tilldela A ett av sanningsvärdena sant eller falskt , och tilldela $\lnot$ A det andra sanningsvärdet. Till exempel, "Katten är svart eller katten är inte svart".
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)} ($ "om A antyder B , så betyder inte- B inte- A ", och vice versa), som uttrycker kontrapositionslagen . Till exempel, "Om det är en bok, är det blått; om det inte är blått är det inte en bok."
• $\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A} ($ "if inte- A innebär både B och dess negation inte- B , då måste inte- A vara falskt, då måste A vara sant"), vilket är principen som kallas reductio ad absurdum . Till exempel, "Om det inte är blått är det en bok, om det inte är blått är det inte heller en bok, så den är blå."
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\eller \lnot B)} ("$ om inte både A och B , då inte- A eller inte- B ", och vice versa), som är känd som De Morgans lag . "Om det inte är både blått och en bok, så är det antingen inte en bok eller så är det inte blått"
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)} ($ "if A antyder B och B antyder C , sedan antyder A C "), vilket är principen som kallas syllogism . "Om det är en bok, så är det blått och om det är blått, så är det på den hyllan, sedan om det är en bok, så är det på den hyllan."
• $((A\lor B)\land (A\to C)\land (B\to C))\to C$ ("om minst en av A eller B är sann, och var och en antyder C , måste C också vara sann"), vilket är principen som kallas proof by case . "Böcker och blå saker finns på den hyllan. Om det antingen är en bok eller blå så är det på den hyllan."

En minimal tautologi är en tautologi som inte är förekomsten av en kortare tautologi.

• $(A\lor B)\to (A\lor B)$ är en tautologi, men inte en minimal sådan, eftersom den är en instansiering av ${\ displaystil C\to C}$ .

Verifiera tautologier

Problemet med att avgöra om en formel är en tautologi är grundläggande i propositionell logik. Om det finns n variabler som förekommer i en formel så finns det 2 ⁿ distinkta värderingar för formeln. Därför är uppgiften att avgöra om formeln är en tautologi eller inte en ändlig och mekanisk uppgift: man behöver bara utvärdera formelns sanningsvärde under var och en av dess möjliga värderingar. En algoritmisk metod för att verifiera att varje värdering gör att formeln är sann är att göra en sanningstabell som inkluderar alla möjliga värderingar.

Tänk till exempel på formeln

$((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).$

Det finns 8 möjliga värderingar för propositionsvariablerna A , B , C , representerade av de tre första kolumnerna i följande tabell. De återstående kolumnerna visar sanningen i underformlerna i formeln ovan, som kulminerar i en kolumn som visar sanningsvärdet för den ursprungliga formeln under varje värdering.

$A$	$B$	$C$	$A\land B$	$(A\land B)\to C$	$B\to C$	$A\to (B\to C)$	$((A\land B)\to C)\Leftrightarrow (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

Eftersom varje rad i den sista kolumnen visar T , är meningen i fråga verifierad att vara en tautologi.

Det är också möjligt att definiera ett deduktivt system (dvs. bevissystem) för propositionell logik, som en enklare variant av de deduktiva systemen som används för första ordningens logik (se Kleene 1967, avsnitt 1.9 för ett sådant system). Ett bevis på en tautologi i ett lämpligt deduktionssystem kan vara mycket kortare än en fullständig sanningstabell (en formel med n propositionsvariabler kräver en sanningstabell med 2 ⁿ rader, vilket snabbt blir omöjligt när n ökar). Bevissystem krävs också för studiet av intuitionistisk propositionell logik, där metoden med sanningstabeller inte kan användas eftersom lagen om den uteslutna mitten inte antas.

Tautologisk implikation

Huvudartikel: Tautologisk konsekvens

En formel R sägs tautologiskt antyda en formel S om varje värdering som gör att R är sann också gör att S är sann. Denna situation betecknas $R\models S$ . Det motsvarar att formeln $R\to S$ är en tautologi (Kleene 1967 s. 27).

Låt till exempel $S$ vara $A\land (B\lor \lnot B)$ . Då $S$ inte en tautologi, eftersom varje värdering som gör $A$ falsk kommer att göra $S$ falsk. Men varje värdering som gör $A$ sann kommer att göra $S$ sann, eftersom $B\lor \lnot B$ är en tautologi. Låt $R$ vara formeln $A\land C$ . Sedan $R\models S$ , eftersom varje värdering som uppfyller $R$ kommer att göra $A$ sann—och därmed gör $S$ sann.

Det följer av definitionen att om en formel $R$ är en motsägelse, så implicerar $R$ tautologiskt varje formel, eftersom det inte finns någon sanningsvärdering som gör att $R$ är sann, och så definitionen av tautologisk implikation är trivialt tillfredsställd. På liknande sätt, om $S$ är en tautologi, så antyds $S$ tautologiskt av varje formel.

Utbyte

Huvudartikel: Substitutionsinstans

Det finns en allmän procedur, substitutionsregeln , som tillåter att ytterligare tautologier konstrueras från en given tautologi (Kleene 1967, sektion 3). SA . _Antag att S är en tautologi och för varje propositionsvariabel A i S väljs en fast mening SA _Då är meningen som erhålls genom att ersätta varje variabel A i S med motsvarande mening också en tautologi.

Låt till exempel S vara tautologin

$(A\land B)\lor \lnot A\eller \lnot B$ .

Låt S _A vara $C\lor D$ och låt S _B vara $C\to E$ .

Av ersättningsregeln följer att domen

$((C\lor D)\land (C\to E))\eller \lnot (C\lor D)\lor \lnot (C\to E)$

Semantisk fullständighet och sundhet

Ett axiomatiskt system är komplett om varje tautologi är ett teorem (härleds från axiom). Ett axiomatiskt system är sunt om varje teorem är en tautologi.

Effektiv verifiering och det booleska tillfredsställbarhetsproblemet

Problemet med att konstruera praktiska algoritmer för att avgöra om meningar med ett stort antal propositionella variabler är tautologier är ett område av samtida forskning inom området för automatiserad teorembevisande .

Metoden för sanningstabeller som illustreras ovan är bevisligen korrekt – sanningstabellen för en tautologi kommer att sluta i en kolumn med endast T , medan sanningstabellen för en mening som inte är en tautologi kommer att innehålla en rad vars sista kolumn är F , och värdering som motsvarar den raden är en värdering som inte uppfyller den mening som prövas. Denna metod för att verifiera tautologier är en effektiv procedur , vilket innebär att den med obegränsade beräkningsresurser alltid kan användas för att mekanistiskt avgöra om en mening är en tautologi. Detta betyder i synnerhet att uppsättningen av tautologier över ett fast ändligt eller räknebart alfabet är en avgörbar uppsättning .

Som ett effektivt förfarande begränsas dock sanningstabeller av det faktum att antalet värderingar som måste kontrolleras ökar med 2 ^k , där k är antalet variabler i formeln. Denna exponentiella ökning av beräkningslängden gör sanningstabellmetoden oanvändbar för formler med tusentals propositionella variabler, eftersom modern datorhårdvara inte kan exekvera algoritmen under en genomförbar tidsperiod.

Problemet med att avgöra om det finns någon värdering som gör en formel sann är det booleska tillfredsställbarhetsproblemet ; problemet med att kontrollera tautologier är likvärdigt med detta problem, eftersom att verifiera att en mening S är en tautologi motsvarar att verifiera att det inte finns någon värdering som uppfyller ¬ $\displaystyle \lnot S}$ . Det är känt att det booleska tillfredsställbarhetsproblemet är NP komplett , och en allmän uppfattning är att det inte finns någon polynom-tidsalgoritm som kan utföra det. Följaktligen är tautologi co-NP-komplett . Aktuell forskning fokuserar på att hitta algoritmer som fungerar bra på speciella klasser av formler, eller som i genomsnitt avslutas snabbt även om vissa inmatningar kan göra att de tar mycket längre tid.

Tautologier kontra validiteter i första ordningens logik

Den grundläggande definitionen av en tautologi är i kontexten av propositionell logik. Definitionen kan dock utökas till meningar i första ordningens logik . Dessa meningar kan innehålla kvantifierare, till skillnad från meningar av propositionell logik. I samband med första ordningens logik upprätthålls en distinktion mellan logiska validiteter , meningar som är sanna i varje modell, och tautologier (eller tautologiska validiteter ), som är en riktig delmängd av första ordningens logiska validiteter. I samband med propositionell logik sammanfaller dessa två termer.

En tautologi i första ordningens logik är en mening som kan erhållas genom att ta en tautologi av propositionell logik och enhetligt ersätta varje propositionsvariabel med en första ordningens formel (en formel per propositionsvariabel). Till exempel, eftersom $A\lor \lnot A$ är en tautologi av propositionell logik, $(\ forall x(x=x))\lor (\lnot \forall x(x=x))$ är en tautologi i första ordningens logik. På liknande sätt, i ett första ordningens språk med en enär relationssymboler R , S , T , är följande mening en tautologi:

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

Den erhålls genom att ersätta $A$ med ${\displaystyle \exists xRx} ,$ B $\displaystyle B}$ med $\lnot \exists xSx$ , och ${\ displaystyle C}$ med $\forall xTx$ i propositionstautologin $((A\land B)\to C)\Vänsterhögerpil (A\till (B\till C))$ .

Alla logiska validiteter är inte tautologier i första ordningens logik. Till exempel meningen

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

är sant i vilken första ordningens tolkning, men den motsvarar satssatsen $A\to B$ som inte är en satslogiks tautologi.

Se även

Normala former

• Algebraisk normalform
• Konjunktiv normalform
• Disjunktiv normalform
• Logisk optimering

Relaterade logiska ämnen

• Boolesk algebra
• boolesk domän
• boolesk funktion
• Motsägelse
• Falskt (logik)
• Slutledning
• Lista över logiska symboler

• Logisk syntes
• Logisk konsekvens
• Logisk graf
• Logisk sanning
• Tumlös sanning

Vidare läsning

• Bocheński, JM (1959) Précis of Mathematical Logic , översatt från de franska och tyska utgåvorna av Otto Bird, Dordrecht , Sydholland : D. Reidel .
•   Enderton, HB (2002) A Mathematical Introduction to Logic , Harcourt / Academic Press , ISBN 0-12-238452-0 .
•   Kleene, SC (1967) Mathematical Logic , omtryckt 2002, Dover Publications , ISBN 0-486-42533-9 .
•   Reichenbach, H. (1947). Elements of Symbolic Logic , omtryckt 1980, Dover, ISBN 0-486-24004-5
• Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung", Annalen der Naturphilosophie (Leipzig), v. 14, s. 185–262, omtryckt i engelsk översättning som Tractatus logico-philosophicus , New York City och London , 1922.

externa länkar

• "Tautology" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]