Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 4 страница

б) Y₂ = ® .

Решение. Используя закон Де Моргана и тождество (1.11), раскрываем скобки и избавляемся от инверсии:

= (A ) ( ) = A .

® = Ú = A Ú ( Ú C).

Ответ. Y_2ДНФ = A Ú Ú C.

Пример 13.2. Пусть задана таблица булевой функции трех переменных. Записать для этой функции СДНФ и СКНФ.

Таблица 13.1.

х 1	х 2	х 2	Y

Решение. Для записи совершенной дизъюнктивной нормальной формы (СДНФ) выбираем те наборы переменных x ₁, x ₂, x ₃, при которых функция Y принимает значение равное 1:

Y_СДНФ = х ₁ Ú х ₂ Ú х ₁ х ₂ Ú х ₂ х ₃.

Соответственно для записи совершенной конъюнктивной нормальной формы (СКНФ) выбираются наборы переменных, при которых функция Y принимает значение равное 0:

СКНФ = (х ₁ Ú x ₂ Ú х ₃) (х ₁ Ú x ₂ Ú ) ( Ú x ₂ Ú ) ( Ú Ú ).

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

Приведем функцию x z Ú x к СДНФ:

x z Ú x = x z Ú x (y Ú ) = x z Ú x y Ú x .

Приведем к СКНФ:

(x Ú z) = (x Ú z) = ( Ú z) (x Ú z) = ( Ú y ) ( Ú z Ú x ) (x Ú z Ú y ) = ( Ú y) ( Ú ) ( Ú z Ú x) ( Ú z Ú ) (x Ú z Ú y) (x Ú z Ú ) = ( Ú y Ú z ) ( Ú Ú z ) (x Ú Ú z) ( Ú Ú z) (x Ú y Ú z) (x Ú Ú z) = ( Ú y Ú z) ( Ú y Ú ) ( Ú Ú z) ( Ú Ú ) (x Ú Ú z) ( Ú Ú z) (x Ú y Ú z) (x Ú Ú z) = ( Ú y Ú z) ( Ú y Ú ) ( Ú Ú ) ( Ú Ú z) (x Ú Ú z) (x Ú y Ú z).

13.2. Способы перехода от нормальных к совершенным нормальным формам

Существует два способа перехода от нормальных к совершенным нормальным формам булевых функций.

1. Аналитический способ.

Данный способ состоит в пошаговом дополнении каждой компоненты, составляющей нормальную форму до полной, т.е. содержащей все возможные переменные. Для СДНФ при этом производится операция последовательного умножения на логическое выражение вида (x_i Ú ), где x_i - одна из переменных набора - x ₁, x ₂, x ₃,..., x_n, которые не входят в рассматриваемую компоненту.

В свою очередь, для СКНФ производится последовательное суммирование с логическим выражением вида x_i .

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

Дата добавления: 2015-10-26