Tautologia (logiikka)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. marraskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Tautologia logiikassa on identtisesti tosi ehdotus . _

Se tosiasia, että kaava A on tautologia, on merkitty . Jokaisella loogisella laskulla on omat tautologiansa. $\vDash A$

Tautologioiden rakentaminen

Jotta saadaan selville, onko annettu kaava tautologia, on olemassa yksinkertainen tapa propositioalgebrassa - rakentaa totuustaulukko . Lauselaskunnassa tautologiat ovat aksioomia (tarkemmin sanottuna aksioomakaavioita) sekä kaikkia kaavoja, jotka voidaan saada tunnetuista tautologioista annettujen päättelysääntöjen avulla (useimmiten nämä ovat Modus ponens ja substituutiosääntö ). Sen tarkistaminen, onko annettu kaava lauselaskussa tautologia, on monimutkaisempaa ja riippuu myös aksioomijärjestelmästä ja käytettävissä olevista päättelysäännöistä.
Ongelma sen määrittämiseksi, onko mielivaltainen kaava predikaattilogiikassa tautologia, on algoritmisesti ratkaisematon.

Esimerkkejä tautologioista

Propositiolaskennan (ja lausealgebran) tautologiat

$A\nuoli oikealle A$ (" A: sta seuraa A ") - identiteetin laki
$(A)\tai (\lnot A)$ (" A vai ei - A ") - poissuljetun keskikohdan laki
$\neg (P\land \neg P)$ - ristiriidan kieltämisen laki
$\neg \neg P\rightarrow P$ - kaksoisnegaation laki
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - vastakohtien laki
$(P\land Q)\leftrightarrow (Q\land P)$ — konjunktion kommutatiivisuus
$(P\tai Q)\vasen oikea nuoli (Q\tai P)$ — disjunktion kommutatiivisuus
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - konjunktion assosiatiivisuus
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - disjunktion assosiatiivisuus
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\nuoli oikealle (B\nuoli oikealle A)$ (totuus seuraa mistä tahansa)
$(A\nuoli oikealle B)\kiila (B\nuoli oikealle C)\nuoli oikealle (A\nuoli oikealle C)$ - ketjusääntö
$(A\vee B)\kiila C\nuoli vasen oikealle (A\kiila C)\vee (B\kiila C)$ — konjunktion jakautuminen disjunktion suhteen
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — disjunktion disjunktio suhteessa konjunktiin
$(P\land P)\leftrightarrow P$ - idempotentti konjunktio
$(P\tai P)\leftrightarrow P$ — disjunktion idempotenssi
$(P\rightarrow Q)\leftrightarrow (\neg P\tai Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\land (Q\tai P)\leftrightarrow P$ - ensimmäinen absorption laki
$(P\lor (Q\land P)\leftrightarrow P$ - absorption toinen laki
${\näyttötyyli \neg (A\kiila B)\vasen oikea nuoli (\neg A\vee \neg B)}$ - De Morganin ensimmäinen laki
$\neg (A\vee B)\nuoli vasemmalle oikealle (\neg A\kiila \neg B)$ - De Morganin toinen laki
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ - vastaasetuksen laki
Jos ja ovat kaavoja, sitten ( korvaussääntö ) $\vDash F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vDash F(H_{1},...,H_{n})$

Predikaattilaskennan (ja predikaattialgebran) tautologiat

Jos on tautologia propositionaalisessa laskennassa ja ovat predikaatteja, niin se on tautologia predikaattilaskussa $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\nuoli vasemmalle oikealle (\exists x)\neg P(x)$

$\neg (\exists x)P(x)\nuoli vasemmalle oikealle (\kaikki x)\neg P(x)$ ( de Morganin laki )

$(\forall x)(P(x)\wedge Q(x))\nuoli vasemmalle oikealle (\forall x)P(x)\kiila (\forall x)Q(x)$
$(\olemassa x)(P(x)\vee Q(x))\nuoli vasemmalle oikealle (\olemassa x)P(x)\vee (\olemassa x)Q(x)$
$Q\vasen oikea nuoli (\olemassa x)Q$
$Q\vasen oikea nuoli (\forall x)Q$
$(\forall x)P(x)\rightarrow P(y)$
$P(y)\nuoli oikealle (\olemassa x)P(x)$
$(\forall x)(\forall y)P(x,y)\nuoli vasen oikealle (\forall y)(\forall x)P(x,y)$
$(\olemassa x)(\olemassa y)P(x,y)\nuoli vasemmalle oikealle (\olemassa y)(\olemassa x)P(x,y)$
$(\olemassa x)(\kaikki y)P(x,y)\nuoli oikealle (\kaikki y)(\exists x)P(x,y)$

Katso myös

Muistiinpanot

Kirjallisuus

V. Igoshin, Matemaattinen logiikka ja algoritmien teoria. – Akatemia, 2008.
Karpov Yu. G. "Automaattiteoria". - P., 2003. - S. 49, 60.
Mendelsohn E. "Johdatus matemaattiseen logiikkaan". - M. Nauka, 1971.
V. Igoshin «Matemaattisen logiikan ongelmakirja-työpaja». - Enlightment, 1986.