Теорема о тождественной ложности формулы логики высказываний.

Для того чтобы формула пропозициональной логики была тождественно ложной (невыполнимой), необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала, по крайней мере, одно элементарное высказывание вместе со своим отрицанием.

Из этих теорем вытекает определенный метод решения основной задачи логики высказываний.

Если мы хотим определить, является ли формула F общезначимой, достаточно построить эквивалентную ей КНФ и проверить на наличие контрарных элементарных высказываний каждую элементарную дизъюнкцию.

Если мы хотим определить, является ли формула F невыполнимой, достаточно построить эквивалентную ей ДНФ и проверить на наличие контрарных элементарных высказываний каждую элементарную конъюнкцию.

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

Интересный прием здесь – неполная формализация - не используются все 16 переменных и явно не формализуются естественные ограничения о том, что один человек не может одновременно ехать в несколько городов, и что в одном городе не будут отдыхать несколько друзей.