Алгоритм 1

Работа алгоритма состоит из трех этапов.

Этап 1. Умножение логических скобок с использованием закона дистрибутивности.

Этап 2. Упрощение полученной на этапе 1 д.н.ф. с использованием правил , , (устранение повторяющихся конъюнкций и замена не элементарных конъюнкций на элементарные).

Этап 3. Устранение элементарных поглощений с применением равенства .

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

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

Алгоритм 2. Алгоритм основан на построении на каждом шаге так называемой «тупиковой» конъюнкции для и отбора среди построенных «тупиковых» конъюнкций допустимых конъюнкций.

Определение. Э.к. являетсятупиковой для конъюнкцией, если она неприводимая для и не существует неприводимой для конъюнкции такой, что .

Утверждение 4. Если э.к. является максимальной для , то она является тупиковой для .

Доказательство. Пусть э.к. является максимальной для . Предположим, что не является тупиковой для . Тогда найдется неприводимая конъюнкция такая, что . Отсюда и из того, что , следует, что . Таким образом, - неприводимая и допустимая конъюнкция для , т.е. максимальная конъюнкция для . Противоречие. Утверждение доказано.

Обратное утверждение не верно (тупиковая конъюнкция может не быть допустимой).

В силу утверждения 4 задача построения максимальных конъюнкций есть задача построения допустимых тупиковых конъюнкций.

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

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

Шаг 1. Возьмем первую по порядку переменную в . Пусть это будет . Удалим из все дизъюнкции, содержащие . Из остальных дизъюнкций удалим переменные, встречающиеся в и переменную . Полученную в результате КНФ обозначим через . Положим = и построим вершину первого яруса первой ветви вида . Возможны три следующих случая.

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

2) Не все скобки вычеркнуты, но вычеркнуты все переменные в скобках, тогда – тупиковая конъюнкция, не являющаяся допустимой. Первая ветвь построена. На данном шаге не найдена максимальная конъюнкция.

3) Если не все скобки вычеркнуты и в невычеркнутых скобках остались невычеркнутые переменные, то повторяем итерацию. На второй итерации будет построена вершина , где - конъюнкция ранга 2 вида ; - первая по порядку переменная в ; КНФ получена из удалением скобок, содержащих , и удалением из оставшихся скобок переменной и переменных, встречающихся в скобке, из которой была выбрана переменная . Процесс построения первой ветви продолжаем до тех пор пока не возникнет один из случаев 1 или 2.

Шаг . Пусть на шаге построена ветвь с висячей вершиной , где .

Если и не является переменной с максимальным номером, то строится ветвь, исходящая из вершины первого яруса, где следует за в в соответствии с установленным порядком (рассуждения те же, что и в шаге 1, с заменой на ).

Если и является переменной с максимальным номером, то алгоритм заканчивает работу.

Если , то возвращаемся на предыдущий ярус (ярус с номером ) в вершину построенной ветви, где .

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

Если в нет переменных, следующих за , и , то возвращаемся на ярус с номером построенной ветви в вершину , где и берем переменную , следующую за переменной в . Очевидно такая переменная найдется, так как по построению следует за в . Строим ветвь, исходящую из вершины ( рассуждения те же, что и в шаге 1, с заменой на и на ).

Если же в нет переменных, следующих за и , то строится ветвь, исходящая из вершины первого яруса вида , где следует за в (рассуждения те же, что и в шаге 1, с заменой на ).

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

Пусть функция задана на множестве и принимает значения 0 и 1. Множество разбивается на два подмножества и (=), на которых функция принимает соответственно значение 1 и 0. На наборах из \функция не определена.

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

Будем говорить, что д.н.ф. реализует частичную функцию , если , =.

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

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

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

Действительно, пусть , . Обозначим через , , множество пар вида , где . Паре из поставим в соответствие э.д. =, где - номера тех разрядов, в которых различаются наборы и . Набору поставим в соответствие монотонную булеву функцию , которая реализуется к.н.ф. .

Утверждение 5. Э.к. является максимальной для тогда и только тогда, когда можно указать , , такое, что э.к. является максимальной для и при координата с номером набора равна .

Дата добавления: 2014-01-11