Tautológia (logika)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. november 9-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A tautológia a logikában egy ugyanolyan igaz állítás .

Azt a tényt, hogy az A képlet tautológia, jelöli . Minden logikai számításnak megvan a maga tautológiája. $\vDash A$

Tautológiák felépítése

Annak megállapítására, hogy egy adott képlet tautológia-e, van egy egyszerű módszer a propozíciós algebrában – igazságtáblázat felépítése . A propozíciós számításban a tautológiák axiómák (pontosabban axióma sémák), valamint minden olyan képlet, amely adott következtetési szabályok (leggyakrabban a Modus ponens és a helyettesítési szabály ) segítségével ismert tautológiákból nyerhető . Annak ellenőrzése, hogy a propozíciós számításban egy adott formula tautológia-e, bonyolultabb, és az axiómarendszertől és a rendelkezésre álló következtetési szabályoktól is függ.
Algoritmikusan eldönthetetlen az a probléma, hogy meghatározzuk, hogy egy tetszőleges formula az predikátumlogikában tautológia-e.

Példák tautológiákra

A propozíciószámítás (és a propozíciós algebra) tautológiái

$A\jobbra nyíl A$ ("A-ból A következik " ) - az azonosság törvénye
$(A)\vagy (\lnem A)$ (" A vagy nem- A ") - a kizárt középső törvénye
$\neg (P\land \neg P)$ - az ellentmondás tagadásának törvénye
$\neg \neg P\rightarrow P$ - a kettős tagadás törvénye
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - az ellentétek törvénye
$(P\land Q)\leftrightarrow (Q\land P)$ — a kötőszó kommutativitása
$(P\vagy Q)\leftrightarrow (Q\vagy P)$ — a diszjunkció kommutativitása
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - a kötőszó asszociativitása
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - diszjunkciós asszociativitás
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\jobbra nyíl (B\jobbra nyíl A)$ (az igazság mindenből következik)
$(A\jobbra nyíl B)\ék (B\jobbra C)\jobbra (A\jobbra C)$ - láncszabály
$(A\vee B)\ék C\balra jobbra nyíl (A\wedge C)\vee (B\ék C)$ — a konjunkció eloszlása a diszjunkció tekintetében
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — a diszjunkció megoszlása a konjunkcióhoz képest
$(P\land P)\leftrightarrow P$ - idempotens kötőszó
$(P\vagy P)\leftrightarrow P$ — a diszjunkció idempotenciája
$(P\rightarrow Q)\leftrightarrow (\neg P\vagy Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\land (Q\vagy P)\leftrightarrow P$ - az abszorpció első törvénye
$(P\lor (Q\land P)\leftrightarrow P$ - az abszorpció második törvénye
${\megjelenítési stílus \neg (A\ék B)\bal jobbra nyíl (\neg A\vee \neg B)}$ - De Morgan első törvénye
$\neg (A\vee B)\balra jobbra nyíl (\neg A\ék \neg B)$ - De Morgan második törvénye
$(A\jobbra nyíl B)\balra jobbra (\neg B\jobbra \neg A)$ - ellentét törvénye
Ha és képletek, akkor ( helyettesítési szabály ) $\vDash F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vDash F(H_{1},...,H_{n})$

A predikátumszámítás (és a predikátumalgebra) tautológiái

Ha tautológia a propozíciós kalkulusban és predikátumok, akkor tautológia az állítmányszámításban $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\bal jobbra nyíl (\exists x)\neg P(x)$

$\neg (\exists x)P(x)\balra jobbra nyíl (\all x)\neg P(x)$ ( de Morgan törvénye )

$(\forall x)(P(x)\wedge Q(x))\balra jobbra nyíl (\forall x)P(x)\wedge (\forall x)Q(x)$
$(\exists x)(P(x)\vee Q(x))\balra jobbra nyíl (\exists x)P(x)\vee (\exists x)Q(x)$
$Q\bal jobbra nyíl (\exists x)Q$
$Q\leftrightarrow (\forall x)Q$
$(\forall x)P(x)\jobbra P(y)$
$P(y)\jobbra nyíl (\exists x)P(x)$
$(\forall x)(\forall y)P(x,y)\bal jobbra nyíl (\forall y)(\forall x)P(x,y)$
$(\exists x)(\exists y)P(x,y)\balra jobbra nyíl (\exists y)(\exists x)P(x,y)$
$(\exists x)(\forall y)P(x,y)\jobbra nyíl (\forall y)(\exists x)P(x,y)$

Lásd még

Jegyzetek

Irodalom

V. Igoshin, Matematikai logika és algoritmusok elmélete. – Akadémia, 2008.
Karpov Yu. G. "Az automaták elmélete". - P., 2003. - S. 49, 60.
Mendelsohn E. "Bevezetés a matematikai logikába". - M. Nauka, 1971.
V. Igoshin «Problémakönyv-műhely a matematikai logikáról». - Felvilágosodás, 1986.