Формула алгебры логики называется тождественно истиной, общезначимой или тавтологией,если она принимает значение 1 при всех значениях входящих в неё элементарных переменных.
Будем обозначать тавтологию F, где F - тождественно истинная формула, а -обозначение тавтологии.
Примеры тавтологий: xÚØx и x®(y®x).
Противоречиемили тождественно ложной формулой в алгебре логики называют всякую формулу, которая принимает значение 0 при любых значениях входящих в неё элементарных переменных высказываний.
Пример противоречия: xÙØx.
Формула алгебры логики называется выполнимой,если она принимает значение 1 хотя бы на одном наборе значений входящих в неё элементарных переменных высказываний.
Любая формула, не являющаяся противоречием, является выполнимой (и наоборот).
Проблема разрешимости в алгебре логикисостоит в том, чтобы найти способ, позволяющий для любой формулы алгебры логики определить, является ли она тождественно истиной.
Очевидно, что эта проблема может быть решена путём построения для заданной формулы таблицы истинности. Однако, существует более эффективный способ решения этой проблемы.