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

Шаблон:Другие значения Тавтологией в логике называется тождественно истинное высказывание.

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

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

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

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

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

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

• $A\to A$ («Из A следует A») — закон тождества
• $(A)\vee (\mathrm{\neg }A)$ («A или не-A») — закон исключённого третьего
• $\mathrm{\neg }(P\wedge \mathrm{\neg }P)$ — закон отрицания противоречия
• $\mathrm{\neg }\mathrm{\neg }P\to P$ — закон двойного отрицания
• $(P\leftrightarrow Q)\leftrightarrow (\mathrm{\neg }Q\leftrightarrow \mathrm{\neg }P)$ — закон противоположности
• $(P\wedge Q)\leftrightarrow (Q\wedge P)$ — коммутативность конъюнкции
• $(P\vee Q)\leftrightarrow (Q\vee P)$ — коммутативность дизъюнкции
• $[(P\wedge Q)\wedge R]\leftrightarrow [P\wedge (Q\wedge R)]$ — ассоциативность конъюнкции
• $[(P\vee Q)\vee R]\leftrightarrow [P\vee (Q\vee R)]$ — ассоциативность дизъюнкции
• $(P\wedge (P\to Q))\to Q$
• $A\to (B\to A)$ (истина следует из чего угодно)
• $(A\to B)\wedge (B\to C)\to (A\to 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\wedge P)\leftrightarrow P$ — идемпотентность конъюнкции
• $(P\vee P)\leftrightarrow P$ — идемпотентность дизъюнкции
• $(P\to Q)\leftrightarrow (\mathrm{\neg }P\vee Q)$
• $(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\wedge (Q\leftrightarrow P))$
• $(P\wedge (Q\vee P)\leftrightarrow P$ — первый закон поглощения
• $(P\vee (Q\wedge P)\leftrightarrow P$ — второй закон поглощения
• $\mathrm{\neg }(A\wedge B)\leftrightarrow (\mathrm{\neg }A\vee \mathrm{\neg }B)$ — первый закон де Моргана
• $\mathrm{\neg }(A\vee B)\leftrightarrow (\mathrm{\neg }A\wedge \mathrm{\neg }B)$ — второй закон де Моргана
• $(A\to B)\leftrightarrow (\mathrm{\neg }B\to \mathrm{\neg }A)$ — закон контрапозиции
• Если $\models F(X_1,...,X_n)$ и $H_1,...,H_n$ — формулы, то $\models F(H_1,...,H_n)$ (правило подстановки)

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга— С. 49, 60.
• Шаблон:Книга
• Шаблон:Книга