Тавтологией в логике называется тождественно истинное высказывание.
Тот факт, что формула A — тавтология, обозначается . В каждом логическом исчислении имеется своё множество тавтологий.
Тавтология также является результатом функции идентичности , так что .
Построение тавтологий Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности. В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода. Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.
Примеры тавтологий
Тавтологии исчисления высказываний (и алгебры высказываний) («Из A следует A») — закон тождества («A или не-A») — закон исключённого третьего — закон отрицания противоречия — закон двойного отрицания — закон противоположности — коммутативность конъюнкции — коммутативность дизъюнкции — ассоциативность конъюнкции — ассоциативность дизъюнкции
(истина следует из чего угодно)
— правило цепного заключения — дистрибутивность конъюнкции относительно дизъюнкции — дистрибутивность дизъюнкции относительно конъюнкции — идемпотентность конъюнкции — идемпотентность дизъюнкции
— первый закон поглощения — второй закон поглощения — первый закон де Моргана — второй закон де Моргана — закон контрапозиции Если и — формулы, то (правило подстановки)
Тавтологии исчисления предикатов (и алгебры предикатов) Если — тавтология в исчислении высказываний и — предикаты, то — тавтология в исчислении предикатов
(закон де Моргана)
См. также Таблица истинности Отрицание Закон двойного отрицания Противоречие
Примечания
Литература
Категория:Логика Категория:Математическая логика