Tautologie (logika)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. listopadu 2018; kontroly vyžadují 4 úpravy .

Tautologie v logice je stejně pravdivý problém .

Skutečnost , že formule A je tautologie, je označena . Každý logický kalkul má svou vlastní sadu tautologií. $\vDash A$

Konstrukce tautologií

Chcete-li zjistit, zda je daná formule tautologií, existuje ve výrokové algebře jednoduchý způsob - sestavení pravdivostní tabulky . Ve výrokovém počtu jsou tautologiemi axiomy (přesněji schémata axiomů), stejně jako všechny vzorce, které lze ze známých tautologií získat pomocí daných odvozovacích pravidel (nejčastěji jsou to Modus ponens a substituční pravidlo ). Kontrola, zda je daná formule ve výrokovém počtu tautologií, je složitější a závisí také na systému axiomů a dostupných odvozovacích pravidlech.
Problém určení, zda je libovolná formule v predikátové logice tautologií, je algoritmicky nerozhodnutelný.

Příklady tautologií

Tautologie výrokového počtu (a výrokové algebry)

$A\šipka doprava A$ („Od A následuje A “) - zákon identity
$(A)\lor (\lne A)$ (" A or not- A ") - zákon vyloučeného středu
$\neg (P\land \neg P)$ - zákon negace rozporu
$\neg \neg P\rightarrow P$ - zákon dvojí negace
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - zákon protikladů
$(P\land Q)\leftrightarrow (Q\land P)$ — komutativnost konjunkce
$(P\lor Q)\leftrightarrow (Q\lor P)$ — komutativnost disjunkce
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - asociativnost spojky
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - disjunkční asociativita
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\šipka doprava (B\šipka doprava A)$ (pravda vyplývá z čehokoli)
$(A\šipka doprava B)\klín (B\šipka doprava C)\šipka doprava (A\šipka doprava C)$ - řetězové pravidlo
$(A\vee B)\klín C\vlevopravá šipka (A\klín C)\vee (B\klín C)$ — distributivita konjunkce vzhledem k disjunkci
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — distributivita disjunkce vzhledem ke konjunkci
$(P\land P)\leftrightarrow P$ - idempotentní konjunkce
$(P\lor P)\leftrightarrow P$ — idempotence disjunkce
$(P\rightarrow Q)\leftrightarrow (\neg P\lor Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\land (Q\lor P)\leftrightarrow P$ - první zákon absorpce
$(P\lor (Q\land P)\leftrightarrow P$ - druhý zákon absorpce
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ - De Morganův první zákon
$\neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)$ - Druhý De Morganův zákon
$(A\šipka doprava B)\šipka doleva doprava (\neg B\šipka doprava \neg A)$ - zákon kontrapozice
Jestliže a jsou vzorce, pak ( substituční pravidlo ) $\vDash F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vDash F(H_{1},...,H_{n})$

Tautologie predikátového počtu (a predikátové algebry)

Jestliže je tautologie ve výrokovém počtu a jsou predikáty, pak je tautologie v predikátovém počtu $F(X_{1};...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\šipka doleva doprava (\existuje x)\neg P(x)$

$\neg (\existuje x)P(x)\šipka doleva doprava (\forall x)\neg P(x)$ ( de Morganův zákon )

$(\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$
$(\existuje x)(P(x)\vee Q(x))\leftrightarrow (\existuje x)P(x)\vee (\existuje x)Q(x)$
$Q\leftrightarrow (\existuje x)Q$
$Q\leftrightarrow (\forall x)Q$
$(\forall x)P(x)\šipka doprava P(y)$
$P(y)\šipka doprava (\existuje x)P(x)$
$(\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)$
$(\existuje x)(\existuje y)P(x,y)\šipka doleva doprava (\existuje y)(\existuje x)P(x,y)$
$(\existuje x)(\forall y)P(x,y)\šipka doprava (\forall y)(\existuje x)P(x,y)$

Viz také

Poznámky

Literatura

V. Igoshin, Matematická logika a teorie algoritmů. — Akademie, 2008.
Karpov Yu. G. "Teorie automatů". - P., 2003. - S. 49, 60.
Mendelsohn E. "Úvod do matematické logiky". - M. Nauka, 1971.
V. Igoshin «Problémový knižní seminář o matematické logice». - Osvícení, 1986.