Открыть главное меню

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

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

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

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

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

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

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

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

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

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

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

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

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

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

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

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

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

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

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

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

 

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

См. такжеПравить

ПримечанияПравить

ЛитератураПравить

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