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

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

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

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

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

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

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

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

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

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

$\mathrm{\neg <!--\; \neg \; -->}(\mathrm{\exists <!--\; \exists \; -->}x)P(x)\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\forall <!--\; \forall \; -->}x)\mathrm{\neg <!--\; \neg \; -->}P(x)$$\neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)$  (закон де Моргана)

• $(\mathrm{\forall <!--\; \forall \; -->}x)(P(x)\wedge <!--\; \wedge \; -->Q(x))\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\forall <!--\; \forall \; -->}x)P(x)\wedge <!--\; \wedge \; -->(\mathrm{\forall <!--\; \forall \; -->}x)Q(x)$$(\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$ 
• $(\mathrm{\exists <!--\; \exists \; -->}x)(P(x)\vee <!--\; \vee \; -->Q(x))\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\exists <!--\; \exists \; -->}x)P(x)\vee <!--\; \vee \; -->(\mathrm{\exists <!--\; \exists \; -->}x)Q(x)$$(\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)$ 
• $Q\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\exists <!--\; \exists \; -->}x)Q$$Q\leftrightarrow (\exists x)Q$ 
• $Q\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\forall <!--\; \forall \; -->}x)Q$$Q\leftrightarrow (\forall x)Q$ 
• $(\mathrm{\forall <!--\; \forall \; -->}x)P(x)\to <!--\; \to \; -->P(y)$$(\forall x)P(x)\rightarrow P(y)$ 
• $P(y)\to <!--\; \to \; -->(\mathrm{\exists <!--\; \exists \; -->}x)P(x)$$P(y)\rightarrow (\exists x)P(x)$ 
• $(\mathrm{\forall <!--\; \forall \; -->}x)(\mathrm{\forall <!--\; \forall \; -->}y)P(x,y)\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\forall <!--\; \forall \; -->}y)(\mathrm{\forall <!--\; \forall \; -->}x)P(x,y)$$(\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)$ 
• $(\mathrm{\exists <!--\; \exists \; -->}x)(\mathrm{\exists <!--\; \exists \; -->}y)P(x,y)\leftrightarrow <!--\; \leftrightarrow \; -->(\mathrm{\exists <!--\; \exists \; -->}y)(\mathrm{\exists <!--\; \exists \; -->}x)P(x,y)$$(\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)$ 
• $(\mathrm{\exists <!--\; \exists \; -->}x)(\mathrm{\forall <!--\; \forall \; -->}y)P(x,y)\to <!--\; \to \; -->(\mathrm{\forall <!--\; \forall \; -->}y)(\mathrm{\exists <!--\; \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.