Проблема разрешения. Нормальные формы формул алгебры высказываний.

Формулы алгебры высказываний подразделяются на типы: выполнимые, тождественно истинные, тождественно ложные.

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

Для обозначения тавтологии используется знак ╞, который ставится перед формулой, являющейся тавтологией.

 

Примерами тавтологий являются формулы:

Определение. Формула алгебры высказываний называется выполнимой, если она принимает значение  хотя бы на одном наборе значений входящих в нее переменных высказываний.

Выполнимыми являются формулы:

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

Тождественно ложными являются формулы:

Можно поставить следующую задачу: указать единый способ (алгоритм), позволяющий для каждой формулы алгебры высказываний выяснить, является ли формула тождественно истинной, выполнимой, тождественно ложной. Поставленная задача, носит название проблемы разрешения.

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

Пример.

Выяснить, какой является формула .

Составим для данной формулы таблицу истинности

 

Данная формула тождественно истинная.

Однако практическое использование таблицы истинности для формулы  при больших  затруднительно.

Существует другой способ, основанный на приведении формул к так называемой «нормальной форме».

Определение. Элементарной конъюнкцией называется конъюнкция переменных высказываний или их отрицаний.

Элементарными конъюнкциями являются формулы:

.

Определение. Элементарной дизъюнкцией называется дизъюнкция переменных высказываний или их отрицаний.

Элементарными дизъюнкциями являются формулы:

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

Например, элементарные дизъюнкции

 являются тождественно истинными, а элементарная дизъюнкция  тождественно истинной не является.

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

Например, элементарные конъюнкции  являются тождественно ложными, а элементарная конъюнкция  тождественно ложной не является.

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

Примерами КНФ являются формулы

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

Примерами ДНФ являются формулы

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