наборов переменных она принимает значение И (истина).
Определение. Формула
называется тождественно-ложной, если для любых наборов переменных она принимает значение Л (ложь).Определение. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.
Проблема разрешимости для логики высказываний заключается в том, чтобы установить, является ли произвольная формула тождественно-истинной.
Теорема 1.1. Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в каждую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание.
Теорема 1.2. Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в каждую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание.