1.2 Проблема разрешения

Будем называть формулу тождественно истинной, если она при всех значениях входящих в нее переменных высказываний принимает значение И. Примерами тождественно истинных формул являются формулы:

1) Х ;

2) Х → (Y → X)

3) X & ( X → Y) → Y

Будем называть формулу выполнимой, если она принимает значение И при некоторых значениях входящих в нее переменных высказываний. Выполнимыми являются формулы:

1) Х

2) Х

3) X →

Будем называть формулу невыполнимой или тождественно ложной, если она при всех значениях входящих в нее переменных принимает значение Л. Отрицание тождественно истинной формулы будет, очевидно, тождественно ложной формулой и обратно.

Можно поставить следующую задачу: указать единый способ, позволяющий для каждой формулы выяснить, является она тождественно истинной или нет. Имея такой способ, мы одновременно получим также и способ узнавать, будет ли данная формула выполнимой или нет. В самом деле, имея возможность конечным числом действий проверить, является ли произвольная формула тождественно истинной или нет, мы можем для произвольной формулы Х решить вопрос, является ли тождественно истинной формулой или нет. Еслиоказалась тождественно истинной, то это значит, что Х тождественно ложная и следовательно, невыполнимая; если Х не является тождественно истинной, то, значит, Х не является тождественно ложной и, следовательно, будет выполнимой.

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

Пусть Х ….) - формула алгебры высказываний, содержащая элементарные высказывания,…. Эти формула определяет некоторую функцию переменных,…, причем как переменные,…, так и функцияX могут принимать лишь два значения; число возможных комбинаций значений переменных иконечно и равно в точности. Для каждой такой комбинации мы можем узнать значение формулы Х, подставив вместо….их значения и вычислив затем значение формулы Х, что, как мы знаем, достигается конечным числом действий. Узнав значение формулы Х для каждой комбинации значений переменных…, мы выясним, является ли она тождественно истинной или нет.

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

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

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

Теорема 1. Чтобы элементарная сумма была тождественно истинной, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть некоторая переменная, а другое — ее отрицание.

Условие достаточно. В самом деле, если такая пара слагаемых найдется, то сумма имеет вид:

Х ˅ ˅Y ˅ Z ˅ …

(слагаемых Y, Z, ... может и не быть). Но сумма X ˅ X тождественно истинна, поэтому и вся рассматриваемая нами сумма тождественна истинна, каковы бы ни были слагаемые У, Z, ...

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

Аналогично доказывается

Теорема 2.Чтобы элементарное произведение было тождественно ложным, необходимо и достаточно, чтобы в нем содержалась хоть одна пара множителей, из которых один является отрицанием другого. Формула, равносильная данной формуле и представляющая собой сумму элементарных произведений, называется дизъюнктивной нормальной формой данной формулы. Как мы уже говорили, все логические операции можно свести к трем: &, V и, Предположим, что формулы, для которых мы будем определять нормальные формы, содержат только эти операции. Знак - можно предполагать отнесенным только к элементарным высказываниям.

Как мы видели выше, с формулой, составленной из переменных и их отрицаний при помощи операций & и V, можно производить такие же преобразования, как с алгебраическими выражениями. Можно, следовательно, Раскрыть все скобки и представить всякую такую фор- мулу в виде суммы элементарных произведений. Таким образом, доказано, что для любой формулы существует дизъюнктивная нормальная форма.

Пример. Найдем дизъюнктивную нормальную форму формулы

Х & () & (U ˅ V)

Приведем эту формулу сначала к виду, в котором отрицание относится только к элементарным высказываниям:

X & (Y ˅ ) & (U ˅ V)

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

(XY ˅ X) (U ˅ V)

И далее

XYU ˅ XYV ˅ XU ˅ XV

Полученная формула является дизъюнктивной нормальной формой исходной формулы.