Тавтологией в логике называется тождественно истинное высказывание.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 9 ноября 2018 года; проверки требуют 11 правок.
У этого термина существуют и другие значения, см. Тавтология.
Тот факт, что формула A — тавтология, обозначается . В каждом логическом исчислении имеется своё множество тавтологий.
Тавтология также является результатом функции идентичности, так что .
Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности. В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода. Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.
Примеры тавтологий
Тавтологии исчисления высказываний (и алгебры высказываний)
Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008.
Карпов Ю. Г. «Теория автоматов». — П., 2003.— С. 49, 60.
Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.
Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.
This article uses material from the Wikipedia Русский article Тавтология (логика), which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Если не указано иное, содержание доступно по лицензии CC BY-SA 4.0. Images, videos and audio are available under their respective licenses. ®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Русский (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.