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

---

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

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

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

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

---