Тавтология (логика)

Тавтологией в логике называется тождественно истинное высказывание.

Тот факт, что формула A — тавтология, обозначается $\vDash A$ . В каждом логическом исчислении имеется своё множество тавтологий.

Построение тавтологий

Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности. В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода.
Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.

Примеры тавтологий

Тавтологии исчисления высказываний (и алгебры высказываний)

$A\rightarrow A$ («Из A следует A») — закон тождества
$(A)\lor (\lnot A)$ («A или не-A») — закон исключённого третьего
$\neg (P\land \neg P)$ — закон отрицания противоречия
$\neg \neg P\rightarrow P$ — закон двойного отрицания
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ — закон противоположности
$(P\land Q)\leftrightarrow (Q\land P)$ — коммутативность конъюнкции
$(P\lor Q)\leftrightarrow (Q\lor P)$ — коммутативность дизъюнкции
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ — ассоциативность конъюнкции
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ — ассоциативность дизъюнкции
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\rightarrow (B\rightarrow A)$ (истина следует из чего угодно)
$(A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)$ — правило цепного заключения
$(A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)$ — дистрибутивность конъюнкции относительно дизъюнкции
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — дистрибутивность дизъюнкции относительно конъюнкции
$(P\land P)\leftrightarrow P$ — идемпотентность конъюнкции
$(P\lor P)\leftrightarrow P$ — идемпотентность дизъюнкции
$(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$ — первый закон поглощения
$(P\lor (Q\land P)\leftrightarrow P$ — второй закон поглощения
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ — первый закон де Моргана
$\neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)$ — второй закон де Моргана
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ — закон контрапозиции
Если $\vDash F(X_{1},...,X_{n})$ и $H_{1},...,H_{n}$ — формулы, то $\vDash F(H_{1},...,H_{n})$ (правило подстановки)

Тавтологии исчисления предикатов (и алгебры предикатов)

Если $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)$ (закон де Моргана)

$(\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)$
$(\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)$
$(\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)$

См. также

Примечания

Литература

Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.
Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.