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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Тавтологией в логике называется тождественно истинное высказывание, инвариантное относительно значений своих компонентов. Тот факт, что формула A - тавтология, обозначается \vDash A. В каждом логическом исчислении имеется своё множество тавтологий.

Построение тавтологий[править | править вики-текст]

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

Примеры тавтологий[править | править вики-текст]

Тавтологии исчисления высказываний (и алгебры высказываний)[править | править вики-текст]

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

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

  • (\forall x)(P(x)\wedge Q(x)) \leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)
  • (\exists x)(P(x)\vee Q(x)) \leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)
  • Q \leftrightarrow (\exists x)Q
  • Q \leftrightarrow (\forall x)Q
  • (\forall x)P(x) \rightarrow P(y)
  • P(y) \rightarrow (\exists x)P(x)
  • (\forall x)(\forall y)P(x,y) \leftrightarrow (\forall y)(\forall x)P(x,y)
  • (\exists x)(\exists y)P(x,y) \leftrightarrow (\exists y)(\exists x)P(x,y)
  • (\exists x)(\forall y)P(x,y) \rightarrow (\forall x)(\exists y)P(x,y)

Пример тавтологии в литературе[править | править вики-текст]

Рассмотрим известное из песни высказывание: «В хоккей играют настоящие мужчины, (следовательно)Трус не играет в хоккей».

Формализуем его:

 X - играет в хоккей

 M - настоящий мужчина

 \lnot X - не играет в хоккей

 \lnot M - не настоящий мужчина (трус)

Получаем формулу:

(X \rightarrow M)\rightarrow(\lnot M \rightarrow \lnot X)

которая является логической тавтологией.

Литература[править | править вики-текст]

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

См. также[править | править вики-текст]