Общезна́чимость — свойство логической формулы, состоящее в том, что эта формула истинна при любой интерпретации входящих в неё нелогических символов, то есть предикатных и пропозициональных переменных. Логические формулы, обладающие этим свойством, называют общезначимыми , или тождественно истинными , или тавтологиями . Всякая общезначимая формула выражает логический закон. Вместо слов «формула A общезначима» часто пишут: ${\displaystyle \vDash A}$ .

Важнейшими видами логических формул являются пропозициональные и предикатные формулы. При классическом понимании логических операций общезначимость пропозициональных формул проверяется путём построения истинностных таблиц : формула общезначима тогда и только тогда, когда при любых истинностных значениях пропозициональных переменных она принимает значение И («истина»). Общезначимость предикатной формулы означает истинность в любой модели. Множество общезначимых предикатных формул неразрешимо , то есть не существует алгоритма , позволяющего для произвольной предикатной формулы выяснить, общезначима ли она (это результат Чёрча). Из теоремы Гёделя о полноте следует, что все общезначимые предикатные формулы и только они выводимы в классическом исчислении предикатов .

Литература

• Н. К. Верещагин , А. Шень . Лекции по математической логике и теории алгоритмов. — МЦНМО, 2002.
• Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, Физматлит, 1987.
• Игошин В.И. Математическая логика и теория алгоритмов. — Academia, 2008.
• Клини С.К. Математическая логика. — М.:Мир, 1973.
• Мендельсон Э. Введение в математическую логику. — М. Наука, 1971.
• Новиков П.С. Элементы математической логики. — М.:Наука, 1973.

См. также

• Логика высказываний
• Логика первого порядка
• Тавтология