Tautologi (logik)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 november 2018; kontroller kräver 4 redigeringar .

En tautologi i logiken är en identisk sann proposition .

Det faktum att formel A är en tautologi betecknas med . Varje logisk kalkyl har sin egen uppsättning tautologier. $\vDash A$

Konstruktion av tautologier

För att ta reda på om en given formel är en tautologi finns det ett enkelt sätt i propositionalgebra - att bygga en sanningstabell . I propositionskalkyl är tautologier axiom (mer exakt, axiomscheman), såväl som alla formler som kan erhållas från kända tautologier med hjälp av givna slutledningsregler (oftast är dessa Modus ponens och substitutionsregeln ). Att kontrollera om en given formel i propositionskalkylen är en tautologi är mer komplicerat och beror också på systemet av axiom och tillgängliga slutledningsregler.
Problemet med att avgöra om en godtycklig formel i predikatlogik är en tautologi är algoritmiskt oavgörbart.

Exempel på tautologier

Tautologier för propositionskalkyl (och propositionalgebra)

$A\högerpil A$ ("Från A följer A ") - lagen om identitet
$(A)\lor (\linte A)$ (" A or not- A ") - lagen om den uteslutna mitten
$\neg (P\land \neg P)$ - lagen om negation av motsägelse
$\neg \neg P\högerpil P$ - lagen om dubbel negation
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - motsatsernas lag
$(P\land Q)\leftrightarrow (Q\land P)$ — kommutativitet av konjunktion
$(P\lor Q)\leftrightarrow (Q\lor P)$ — kommutativitet av disjunktion
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - associativitet av konjunktionen
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - disjunktionsassociativitet
$(P\land (P\högerpil Q))\högerpil Q$
$A\högerpil (B\högerpil A)$ (sanningen följer av vad som helst)
$(A\högerpil B)\kil (B\högerpil C)\högerpil (A\högerpil C)$ - kedjeregel
$(A\vee B)\kil C\vänsterhögerpil (A\kil C)\vee (B\kil C)$ — Fördelning av konjunktion med avseende på disjunktion
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — Fördelning av disjunktion med avseende på konjunktion
$(P\land P)\leftrightarrow P$ - idempotent konjunktion
$(P\lor P)\leftrightarrow P$ — disjunktionens idempotens
$(P\rightarrow Q)\leftrightarrow (\neg P\eller Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\land (Q\lor P)\leftrightarrow P$ - den första absorptionslagen
$(P\lor (Q\land P)\leftrightarrow P$ - den andra absorptionslagen
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ - De Morgans första lag
$\neg (A\vee B)\vänsterhögerpil (\neg A\kil \neg B)$ - De Morgans andra lag
$(A\högerpil B)\vänsterhögerpil (\neg B\högerpil \neg A)$ - motpositionens lag
Om och är formler, då ( substitutionsregel ) $\vBindstreck F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vBindstreck F(H_{1},...,H_{n})$

Tautologier för predikatkalkylen (och predikatalgebra)

Om är en tautologi i satskalkyl och är predikat, så är en tautologi i predikatkalkyl $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\förall x)P(x)\vänsterhögerpil (\exists x)\neg P(x)$

$\neg (\finns x)P(x)\vänsterhögerpil (\förall x)\neg P(x)$ ( de Morgans lag )

$(\forall x)(P(x)\wedge Q(x))\vänsterhögerpil (\forall x)P(x)\wedge (\forall x)Q(x)$
$(\exists x)(P(x)\vee Q(x))\vänsterhögerpil (\exists x)P(x)\vee (\exists x)Q(x)$
$Q\vänsterhögerpil (\exists x)Q$
$Q\vänsterhögerpil (\förall x)Q$
$(\forall x)P(x)\högerpil P(y)$
$P(y)\högerpil (\finns x)P(x)$
$(\förall x)(\förall y)P(x,y)\vänsterhögerpil (\förall y)(\förall x)P(x,y)$
$(\exists x)(\exists y)P(x,y)\vänsterhögerpil (\exists y)(\exists x)P(x,y)$
$(\exists x)(\forall y)P(x,y)\högerpil (\forall y)(\exists x)P(x,y)$

Se även

Anteckningar

Litteratur

V. Igoshin, matematisk logik och teori om algoritmer. — Akademin, 2008.
Karpov Yu. G. "Theory of Automata". - P., 2003. - S. 49, 60.
Mendelsohn E. "Introduktion till matematisk logik". - M. Nauka, 1971.
V. Igoshin «Problembokverkstad om matematisk logik». - Upplysningen, 1986.