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

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

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

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

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

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

• $A \rightarrow A$ («Из A следует A»)
• $(A) \lor (\lnot A)$ («A или не-A», Закон исключённого третьего)
• $\neg (P \land \neg P)$.
• $(P \land (P \rightarrow Q)) \rightarrow Q$
• $A \rightarrow (B \rightarrow A)$ (истина следует из чего угодно)
• $A \leftrightarrow \neg\neg 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)$ (коммутативность дизъюнкции относительно конъюнкции)
• $\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 x)(\exists y)P(x,y)$

Пример тавтологии в литературе

Рассмотрим известное из песни высказывание: «В хоккей играют настоящие мужчины, (следовательно)Трус не играет в хоккей».

Формализуем его:

$X$ - играет в хоккей

$M$ - настоящий мужчина

$\lnot X$ - не играет в хоккей

$\lnot M$ - не настоящий мужчина (трус)

Получаем формулу:

$(X \rightarrow M)\rightarrow(\lnot M \rightarrow \lnot X)$

которая является логической тавтологией.

Литература

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

См. также

• Закон двойного отрицания
• Противоречие