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   В      В С  .

Теперь, для того чтобы получить СКНФ, достаточно проинвертировать последнее выражение:

Y_СКНФ = (А  В  С  D) (А  В  С  ) (A   C  D) (  B  C  ).