Проблема разрешимости

Все формулы алгебры логики делятся на 3 класса: 1) тождественно истинные; 2) тождественно ложные; 3) выполнимые.

Определение. Формулу A называют выполнимой, если она принимает значение «истина» хотя бы при одном наборе входящих в нее переменных и не является тождественно истинной.

В связи с этим возникает задача: к какому классу относится данная формула? Эта задача носит название проблемы разрешимости.

Проблема разрешимости алгебры логики разрешима, так как для каждой формулы алгебры логики может быть записана таблица истинности, которая дает ответ на поставленный вопрос.