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

У этого термина существуют и другие значения, см. Тавтология.

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

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

Тавтология также является результатом функции идентичности ${\displaystyle \mathrm {id} }$, так что ${\displaystyle \mathrm {id} (x)=x}$.

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

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

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

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

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

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

• Если ${\displaystyle F(X_{1},...,X_{n})}$ - тавтология в исчислении высказываний и ${\displaystyle P_{1},...,P_{n}}$ - предикаты, то ${\displaystyle F(P_{1},...,P_{n})}$ - тавтология в исчислении предикатов
• ${\displaystyle \neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)}$

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

• ${\displaystyle (\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)}$
• ${\displaystyle (\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)}$
• ${\displaystyle Q\leftrightarrow (\exists x)Q}$
• ${\displaystyle Q\leftrightarrow (\forall x)Q}$
• ${\displaystyle (\forall x)P(x)\rightarrow P(y)}$
• ${\displaystyle P(y)\rightarrow (\exists x)P(x)}$
• ${\displaystyle (\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)}$
• ${\displaystyle (\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)}$
• ${\displaystyle (\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)}$

См. также

• Таблица истинности
• Отрицание
• (Закон двойного отрицания)
• Противоречие

Примечания

Литература

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