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

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

Тавтологией, в логике, называется тождественно истинное высказывание, инвариантное относительно значений своих компонентов.

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

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

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

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

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

  • («Из A следует A»)
  • A или не-A», Закон исключённого третьего)
  • .
  • (истина следует из чего угодно)
  • (закон двойного отрицания)
  • (правило цепного заключения)
  • (дистрибутивность дизъюнкции относительно конъюнкции)
  • (закон де Моргана)
  • (Закон контрапозиции)
  • Если и - формулы, то (правило подстановки)

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

  • Если - тавтология в исчислении высказываний и - предикаты, то - тавтология в исчислении предикатов

(закон де Моргана)

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

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

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

— играет в хоккей

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

— не играет в хоккей

— не настоящий мужчина (трус)

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

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

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

Примечания[править | править вики-текст]

Логотип Викисловаря
В Викисловаре есть статья «тавтология»

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

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