Tautologie (logica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 9 noiembrie 2018; verificările necesită 4 modificări .

O tautologie în logică este o propoziție identic adevărată .

Faptul că formula A este o tautologie se notează cu . Fiecare calcul logic are propriul său set de tautologii. $\vDash A$

Construcția tautologiilor

Pentru a afla dacă o formulă dată este o tautologie, există o modalitate simplă în algebra propozițională - construirea unui tabel de adevăr . În calculul propozițional, tautologiile sunt axiome (mai precis, scheme de axiome), precum și toate formulele care pot fi obținute din tautologii cunoscute folosind reguli de inferență date (cel mai adesea acestea sunt Modus ponens și regula de substituție ). Verificarea dacă o formulă dată în calculul propozițional este o tautologie este mai complicată și depinde, de asemenea, de sistemul de axiome și de regulile de inferență disponibile.
Problema de a determina dacă o formulă arbitrară în logica predicatelor este o tautologie este algoritmic indecidabilă.

Exemple de tautologii

Tautologii ale calculului propozițional (și algebrei propoziționale)

$A\rightarrow A$ („De la A urmează lui A ”) - legea identității
$(A)\lor (\lnu A)$ (" A sau nu- A ") - legea mijlocului exclus
$\neg (P\land \neg P)$ - legea negaţiei contradicţiei
$\neg \neg P\rightarrow P$ - legea dublei negaţii
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - legea contrariilor
$(P\land Q)\leftrightarrow (Q\land P)$ — comutativitatea conjuncției
$(P\lor Q)\leftrightarrow (Q\lor P)$ — comutativitatea disjuncției
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - asociativitatea conjuncţiei
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - asociativitatea disjuncției
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\rightarrow (B\rightarrow A)$ (adevărul decurge din orice)
$(A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)$ - regula lanțului
$(A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)$ — distributivitatea conjuncției în raport cu disjuncția
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — distributivitatea disjuncției în raport cu conjuncția
$(P\land P)\leftrightarrow P$ - conjuncţie idempotentă
$(P\lor P)\leftrightarrow P$ — idempotenta disjunctiei
$(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$ - prima lege a absorbtiei
$(P\lor (Q\land P)\leftrightarrow P$ - a doua lege a absorbtiei
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ - Prima lege a lui De Morgan
$\neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)$ - A doua lege a lui De Morgan
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ - legea contrapoziției
Dacă și sunt formule, atunci ( regula de substituție ) $\vDash F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vLinea F(H_{1},...,H_{n})$

Tautologii ale calculului predicatului (și algebrei predicatelor)

Dacă este o tautologie în calculul propozițional și sunt predicate, atunci este o tautologie în calculul predicatului $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)$

$\neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)$ ( legea lui de Morgan )

$(\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$
$(\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)$
$Q\leftrightarrow (\exists x)Q$
$Q\leftrightarrow (\forall x)Q$
$(\forall x)P(x)\rightarrow P(y)$
$P(y)\rightarrow (\exists x)P(x)$
$(\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)$
$(\există x)(\există y)P(x,y)\leftrightarrow (\există y)(\există x)P(x,y)$
$(\există x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)$

Vezi și

Note

Literatură

V. Igoshin, Logica matematică și teoria algoritmilor. — Academia, 2008.
Karpov Yu. G. „Teoria automatelor”. - P., 2003. - S. 49, 60.
Mendelsohn E. „Introducere în logica matematică”. - M. Nauka, 1971.
V. Igoshin «Cartea-atelier de probleme de logica matematica». - Iluminismul, 1986.