Нормальные формы формул логики высказываний
Обновлено: 22.12.2024
Среди всевозможных выражений данной формулы через конъюнкцию, дизъюнкцию и отрицание некоторые играют важную роль как в алгебре высказываний, так и в ее приложениях. Рассмотрение таких выражений, называемых совершенными нормальными формами , и составляет цель настоящего параграфа.
Понятие нормальных форм
Конъюнктивным одночленом от переменных называется конъюнкция этих переменных или их отрицаний. Здесь "или" употребляется в неисключающем смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Приведем несколько примеров конъюнктивных одночленов:
Нормальную форму, представляющую формулу нормальной формой этой формулы .
называются не многочленами, а нормальными формами. На этом аналогия заканчивается. Далее вводятся понятия совершенных нормальных форм — дизъюнктивной и конъюнктивной.
Совершенные нормальные формы
Приведем пример совершенной конъюнктивной нормальной формы от четырех переменных
Вот несколько примеров совершенных дизъюнктивных нормальных форм:
Введем обозначение, которое будет удобно в дальнейшем:
Лемма 5.2. Для всякой формулы алгебры высказываний справедливо разложение
С одной стороны, в правой части доказываемого равенства получим
что представляет собой дизъюнкцию нескольких конъюнктивных одночленов. Каждый конъюнктивный одночлен характеризуется индексным набором нулей и единиц . Если для данного конъюнктивного одночлена набор нулей и единиц таков, что или , или , то согласно определению формулы , введенному в начале пункта, будем иметь или , или или . Но тогда и весь данный конъюнктивный одночлен будет равен нулю и потому на результат дизъюнкции влияния не окажет, а значит, из числа дизъюнктивных "слагаемых" может быть безболезненно исключен. Только один конъюнктивный одночлен окажется не равным нулю — тот, что характеризуется таким набором , который равен взятому в начале набору , т.е. для которого . Только для этого конъюнктивного одночлена будем иметь
Таким образом, конъюнктивный одночлен, соответствующий индексному набору , равен . Этому же значению равна и вся дизъюнкция, потому что, как показано выше, все остальные конъюнктивные одночлены равны нулю.
С другой стороны, формула, стоящая в левой части доказываемого равенства, обратится при в то же самое значение . Набор нулей и единиц был выбран произвольно. Следовательно, формулы в левой и правой частях равносильности действительно равносильны. Лемма доказана.
Представление формул алгебры высказываний совершенными дизъюнктивными нормальными формулами
Доказательство. Существование. Всякая формула обладает указанным в предыдущей лемме разложением. Поскольку формула не тождественно ложна, то существуют такие наборы нулей и единиц, что . Наборы , обращающие формулу нулей и единиц, для которых . Тогда разложение для формулы
Единственность. Предположим, что некоторая формула имеет два представления совершенными дизъюнктивными нормальными формами:
Пусть, например, совершенный конъюнктивный одночлен имеет вид . Придадим переменным значения соответственно. Тогда совершенный конъюнктивный одночлен примет значение 1, и, следовательно, вся совершенная дизъюнктивная нормальная форма, стоящая в левой части равносильности, станет равна единице. Тогда и правая часть данной равносильности обратится в единицу, и для набора значений переменных одна из совершенных элементарных конъюнкций , например , также станет равной единице. Если имеет вид , то доказанное означает, что . Последнее равенство возможно в том и только в том случае, когда , что может быть лишь тогда и только тогда, когда . Следовательно, , т.е. . Таким образом, совершенная элементарная конъюнкция встречается среди совершенных элементарных конъюнкций . Тем же самым способом устанавливается, что любая из совершенных элементарных конъюнкций встречается среди , и обратно, любая из совершенных элементарных конъюнкций встречается среди . Ввиду того что одночлены в данных наборах не повторяются, то и обе части равносильности
отличаются самое большее порядком членов дизъюнкции.
Понятия и теоремы этого пункта носят двойственный характер по отношению к соответствующим понятиям и теоремам предыдущего пункта. Вводится следующее обозначение:
Легко проверяется, что , т.е. ; и .
Аналогично доказательству леммы 5.2 доказывается лемма 5.4.
Лемма 5.4. Для всякой формулы алгебры высказываний справедливо разложение
Подобно теореме 5.3 выводится теорема 5.5.
Доказательство этой теоремы можно восстановить, руководствуясь доказательством теоремы 5.3.
Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
Эти два способа проистекают из двух способов задания формулы алгебры высказываний: с помощью таблицы ее значений или с помощью аналитической формы записи.
и, в свою очередь, описывает следующее правило (алгоритм) отыскания совершенной конъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 0. Для каждого такого набора выписать совершенный дизъюнктивный одночлен, принимающий значение 0 на этом наборе и только на нем. Полученные совершенные дизъюнктивные одночлены соединить знаками конъюнкции.
Пример 5.6. Пусть, например, формула задана следующей таблицей своих значений:
Запишем предыдущую формулу разложения в СДН-форму для случая
Пример 5.7. Для формулы из предыдущего примера найдем ее СКН-форму. Для этого сначала отметим все те наборы значений переменных, на которых она принимает значение 0: . Теперь запишем формулу разложения в СКН-форму для случая
Читайте также: