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

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

Тот факт, что формула A — тавтология, обозначается [math]\displaystyle{ \vDash A }[/math]. В каждом логическом исчислении имеется своё множество тавтологий.

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

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

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

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

[math]\displaystyle{ A \rightarrow A }[/math] («Из A следует A») — закон тождества
[math]\displaystyle{ (A) \lor (\lnot A) }[/math] («A или не-A») — закон исключённого третьего
[math]\displaystyle{ \neg (P \land \neg P) }[/math] — закон отрицания противоречия
[math]\displaystyle{ \neg \neg P \rightarrow P }[/math] — закон двойного отрицания
[math]\displaystyle{ (P \leftrightarrow Q) \leftrightarrow (\neg Q \leftrightarrow \neg P) }[/math] — закон противоположности
[math]\displaystyle{ (P \land Q ) \leftrightarrow (Q \land P) }[/math] — коммутативность конъюнкции
[math]\displaystyle{ (P \lor Q ) \leftrightarrow (Q \lor P) }[/math] — коммутативность дизъюнкции
[math]\displaystyle{ [(P \land Q ) \land R] \leftrightarrow [P \land (Q \land R)] }[/math] — ассоциативность конъюнкции
[math]\displaystyle{ [(P \lor Q ) \lor R] \leftrightarrow [P \lor (Q \lor R)] }[/math] — ассоциативность дизъюнкции
[math]\displaystyle{ (P \land (P \rightarrow Q)) \rightarrow Q }[/math]
[math]\displaystyle{ A \rightarrow (B \rightarrow A) }[/math] (истина следует из чего угодно)
[math]\displaystyle{ (A\rightarrow B)\wedge (B \rightarrow C) \rightarrow (A\rightarrow C) }[/math] — правило цепного заключения
[math]\displaystyle{ (A\vee B)\wedge C \leftrightarrow (A\wedge C)\vee (B\wedge C) }[/math] — дистрибутивность конъюнкции относительно дизъюнкции
[math]\displaystyle{ (A\wedge B)\vee C \leftrightarrow (A\vee C)\wedge (B\vee C) }[/math] — дистрибутивность дизъюнкции относительно конъюнкции
[math]\displaystyle{ (P \land P) \leftrightarrow P }[/math] — идемпотентность конъюнкции
[math]\displaystyle{ (P \lor P) \leftrightarrow P }[/math] — идемпотентность дизъюнкции
[math]\displaystyle{ (P \rightarrow Q) \leftrightarrow (\neg P \lor Q) }[/math]
[math]\displaystyle{ (P \leftrightarrow Q) \leftrightarrow ((P \leftrightarrow Q) \land (Q \leftrightarrow P)) }[/math]
[math]\displaystyle{ (P \land (Q \lor P) \leftrightarrow P }[/math] — первый закон поглощения
[math]\displaystyle{ (P \lor (Q \land P) \leftrightarrow P }[/math] — второй закон поглощения
[math]\displaystyle{ \neg (A\wedge B) \leftrightarrow (\neg A \vee \neg B) }[/math] — первый закон де Моргана
[math]\displaystyle{ \neg (A\vee B) \leftrightarrow (\neg A \wedge \neg B) }[/math] — второй закон де Моргана
[math]\displaystyle{ (A\rightarrow B) \leftrightarrow (\neg B \rightarrow \neg A) }[/math] — закон контрапозиции
Если [math]\displaystyle{ \vDash F(X_1,...,X_n) }[/math] и [math]\displaystyle{ H_1,...,H_n }[/math] — формулы, то [math]\displaystyle{ \vDash F(H_1,...,H_n) }[/math] (правило подстановки)

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

Если [math]\displaystyle{ F(X_1,...,X_n) }[/math] - тавтология в исчислении высказываний и [math]\displaystyle{ P_1,...,P_n }[/math] - предикаты, то [math]\displaystyle{ F(P_1,...,P_n) }[/math] - тавтология в исчислении предикатов
[math]\displaystyle{ \neg (\forall x)P(x) \leftrightarrow (\exists x)\neg P(x) }[/math]

[math]\displaystyle{ \neg (\exists x)P(x) \leftrightarrow (\forall x)\neg P(x) }[/math] (закон де Моргана)

[math]\displaystyle{ (\forall x)(P(x)\wedge Q(x)) \leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x) }[/math]
[math]\displaystyle{ (\exists x)(P(x)\vee Q(x)) \leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x) }[/math]
[math]\displaystyle{ Q \leftrightarrow (\exists x)Q }[/math]
[math]\displaystyle{ Q \leftrightarrow (\forall x)Q }[/math]
[math]\displaystyle{ (\forall x)P(x) \rightarrow P(y) }[/math]
[math]\displaystyle{ P(y) \rightarrow (\exists x)P(x) }[/math]
[math]\displaystyle{ (\forall x)(\forall y)P(x,y) \leftrightarrow (\forall y)(\forall x)P(x,y) }[/math]
[math]\displaystyle{ (\exists x)(\exists y)P(x,y) \leftrightarrow (\exists y)(\exists x)P(x,y) }[/math]
[math]\displaystyle{ (\exists x)(\forall y)P(x,y) \rightarrow (\forall y)(\exists x)P(x,y) }[/math]

См. также

Примечания

Литература

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