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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

    Литература

    • Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
    • Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
    • Мендельсон Э. «Введение в математическую логику». М. Наука, 1971.
    • Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.