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

Ответ.   Y_1КНФ = (  Ú ) (В Ú );

              Y_1ДНФ = В Ú  Ú .

б) Y₂ =  ® .

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

 = (A ) ( ) = A .

 ®  =  Ú  = A  Ú (  Ú C).

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

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

     Таблица 13.1.

х 1	х 2	х 2	Y
0	0	0	0
1	0	0	1
0	1	0	1
1	1	0	1
0	0	1	0
1	0	1	0
0	1	1	1
1	1	1	0

Решение. Для записи совершенной дизъюнктивной нормальной формы (СДНФ) выбираем те наборы переменных 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 .

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

2. Графический способ.

Наиболее наглядным способом перехода к совершенным нормальным формам являются карты Карно. Ниже представлены карты Карно для двух, трех и четырех переменных соответственно:

Рис. 13.1. Карты Карно

Как видно, карты Карно составляются таким образом, чтобы значение переменных в соседних клетках отличались друг от друга не более чем на единицу.

Алгоритм перехода к СДНФ можно сформулировать следующим образом:

1. Для заданной функции строится карта Карно.

2. В клетках соответствующих компонентам, составляющим ДНФ, ставятся единицы.

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

4. Полученные конъюнкции соединяются символами дизъюнкции.

Для получения с помощью карт Карно СКНФ необходимо проинвертировать исходную БФ.

Затем для полученного инверсного выражения выполняется алгоритм, приведенный для записи СДНФ.

Полученную в пункте 4 вышеуказанного алгоритма СДНФ еще раз инвертируем и получаем в результате искомую СКНФ.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 13.3. Преобразовать в СДНФ и СКНФ следующие переключательные функции:

а) Y = А В Ú С.

Решение. Как видно, исходная функция имеет две составляющие, соединенные между собой символом дизъюнкции. Используя законы и тождества алгебры логики, преобразуем эти составляющие до полных. Согласно тождествам алгебры логики, значение выражения типа В Ú  всегда равно единице, поэтому добавление такого выражения в исходное не изменяет его значения. Применив к полученному выражению распределительный закон, перейдем к записи СДНФ:

А В (С Ú ) = А В С Ú А В ;

С (А Ú ) = С А Ú С  = (С А Ú С ) (В Ú ) = А В С Ú В С Ú А С Ú С.

Ответ: Y_СДНФ = А В С Ú А В  Ú В С Ú А С Ú С.

б) Y = А (В Ú ).

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

А = А Ú В  = (А Ú В) (А Ú ) = (А Ú В Ú С ) Ú (А Ú  Ú С ) = (А Ú В Ú С) (А Ú В Ú ) (А Ú  Ú С) (А Ú  Ú );

В Ú С = В Ú C Ú А  = (А Ú В Ú C) (  Ú В Ú С).

Ответ. Y_СКНФ = (А Ú В Ú С) (А Ú В Ú ) (А Ú  Ú С) (А Ú  Ú ) (  Ú В Ú С).

в) Y = А (  Ú С) (  Ú В Ú С);

Решение. А = А Ú В  = (А Ú В) (А Ú ) = (А Ú В Ú С ) Ú (А Ú  Ú С ) = (А Ú В Ú С) (А Ú В Ú ) (А Ú  Ú С) (А Ú  Ú );

 Ú C =  Ú C Ú А  = (А Ú  Ú С) (  Ú  Ú С);

Ответ. Y_СКНФ = (А Ú В Ú С) (А Ú В Ú ) (А Ú  Ú С) (А Ú  Ú ) (  Ú  Ú С).

г) Y = А Ú С Ú В С;

Решение. С (А Ú ) = А С Ú С;

А (С Ú ) = С А Ú А = (С А Ú А) (В Ú ) = А В С Ú А В  Ú А С Ú А .

Ответ. Y_сднф = А В С Ú А В  Ú А С Ú А  Ú С.

Пример 13.4. Преобразовать с помощью карт Карно переключательную функцию:

а) Y = А В Ú С в СДНФ.

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

 

С\АВ	00	01	11	10
0	0	0	1	0
1	1	1	1	1

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

Y_сднф = А В С Ú А В  Ú В С Ú А С Ú С.

б) Y = (А Ú В Ú С) (А Ú  Ú D) в СКНФ.

Решение. Найдем инверсное значение функции Y:

 =  Ú В .

Построим карту Карно аналогично описанному в предыдущем примере способу.

СD\AB	00	01	11	10
00	1	1	0	0
01	1	0	0	0
11	0	0	0	0
10	0	1	0	0

Полученная карта Карно содержит четыре ненулевых ячейки. После этого запишем выражение, являющееся инверсией СКНФ.

 =  Ú D Ú В  Ú В С .