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

Тавтологией в логике называется тождественно истинное высказывание.

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

Тавтология также является результатом функции идентичности , так что .

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

править

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

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

править

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

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

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

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

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

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

См. также

править

Примечания

править

Литература

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