5. Совершенная нормальная форма; распознавание заменимости; примеры.

Рассмотренный способ распознавания заменимости является, конечно, не очень удобным. Но эту проверку мы

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

Например, конъюнктивная нормальная форма

представляет ту же самую истинностную функцию, что и конъюнктивная нормальная форма

Поэтому, налагая дополнительные ограничения, мы будем стараться придать нормальной форме некоторый стандартный вид. И действительно, некоторая нормировка такого рода может быть произведена; правда, при этом заранее должно быть указано, какие дополнительные переменные, кроме входящих в рассматриваемое выражение, должны считаться аргументами соответствующей истинностной функции. Например, для истинностной функции, представленной выражением А, мы получим различные нормальные формы в зависимости от того, будем ли мы рассматривать эту функцию как зависящую только от А или же еще и от дополнительной переменной В. Соображение, наиболее простым способом ведущее нас к нормировке желаемого вида, заключаются в следующем.

Истинностная функция, зависящая от аргументов определяется так, что каждому набору истинностных значений аргументов вновь сопоставляется некоторое истинностное значение. Каждый набор истинностных значений аргументов может быть представлен -членной конъюнкцией, у которой ее член представляет собой либо либо в зависимости от того, какое значение — «истина» или «ложь» — принимает в этом наборе аргумент Действительно, построенная таким образом конъюнкция на рассматриваемом наборе значений принимает значение «истина», а на остальных наборах — значение «ложь». Мы будем говорить, что эта конъюнкция представляет рассматриваемый набор значений аргументов.

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

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

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

Например, для истинностной функции рассматриваемой как функция от аргументов действуя описанным образом, мы получим дизъюнктивную нормальную форму

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

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

Отсюда, в частности, следует, что всякая истинностная функция заданных аргументов может быть представлена при помощи связок и (Разумеется, сказанное справедливо и для тождественно ложной функции, которая может быть представлена посредством выражения )

Число различных истинностных функций, зависящих от аргументов совпадает с числом различных (в указанном смысле слова) построенных из этих переменных совершенных дизъюнктивных нормальных форм, если мы согласимся считать, что нульчленная дизъюнкция представляет тождественно ложную функцию. Каждая из этих нормальных форм представляет собой некоторую поддизъюнкцию той («полной») дизъюнкции, которая содержит в качестве дизъюнктивных членов конъюнкции, представляющие все наборы значений аргументов, и которая представляет тождественно истинную функцию. Эта полная дизъюнкция состоит из членов, и число ее поддизъюнкций (включая и нуль-членную) равно Это и есть число различных истинностных функций, зависящих от аргументов

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

дизъюнкцию, состоящую из всех тех представляющих конъюнкций, которые в исходной дизъюнкции не встречаются.

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

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

Совершенную дизъюнктивную или конъюнктивную нормальную форму заданного выражения логики высказываний мы всегда можем получить, построив сначала описанным ранее способом какую-либо конъюнктивную, соответственно дизъюнктивную нормальную форму, а затем преобразовав ее с помощью правил 1а), б) и 3а), б) в совершенную нормальную форму. Проиллюстрируем этот метод на следующих двух примерах.

Предположим, что нам требуется представить в виде совершенной конъюнктивной нормальной формы истинностную функцию А как функцию двух переменных Заменим, согласно правилу 36),

Применив закон дистрибутивности, мы получим выражение

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

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

А отсюда в свою очередь получается, что всегда заменимо посредством .

Рассмотрим теперь выражение

Ранее мы получили для него дизъюнктивную нормальную форму

Чтобы получить из совершенную дизъюнктивную нормальную форму, применим к первым двум членам дизъюнкции правило 3а); заменим посредством

а затем, по второму закону дистрибутивности (производя одновременно перестановку конъюнктивных членов), - посредством

аналогичным образом преобразуется в

Выполнив в нашем первоначальном выражении эти преобразования и вычеркнув по правилу 1а) повторяющийся дизъюнктивный член мы получим для рассматриваемого нами выражения следующую совершенную дизъюнктивную нормальную форму:

От этой совершенной дизъюнктивной нормальной формы мы можем следующим образом перейтп к совершенной конъюнктивной нормальной форме. Возьмем дыойное отрицание этой формы. К однократному отрицанию пргыеним упоминавшееся выше замечание о том, что отрицание ершенной дизъюнктивной нормальной формы представляется дополнительной дизъюнкцией. Это даст нам для однократного отрицания следующее выражение:

Затем мы возьмем отрицание этого выражения и, применив правила 26), получим совершенною конъюнктивную нормальную форму

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

Этим способом мы можем, например, доказать высказанное ранее утверждение о заменимости выражения

посредством

Действительно, если к каждому из этих двух выражений применить законы дистрибутивности в сочетании с правилами 1б) и 3б), то в обоих случаях мы получим одну и ту же совершенную дизъюнктивную нормальную форму

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

Если выражение заменимо посредством , то переход от можно осуществить применением правил замены и правила или еще короче: всякая заменимость может быть установлена с помощью имеющихся в нашем распоряжении правил замены.

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