Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 27 стр.

     Пример 1. Для функции f � �111 011 0 0 � построить несколько ДНФ.
Указать кратчайшую и минимальную среди них.
     Решение. Предварительно построив таблицу истинности для f и
применяя преобразования, получим следующие ДНФ:
            D1 = x y z Ъ x y z Ъ x y z Ъ x y z Ъ x y z; ρD1 = 15;
              D2 = x y Ъ x y z Ъ x y z Ъ x y z;                 ρD2 = 11;
              D3 = x y Ъ x y z Ъ x y;          ρD3 = 7;
              D4 = x y Ъ x z Ъ x y ;          ρD4 = 6;
              D5 = y Ъ x z;        ρD5 = 3.
       Кратчайшей ДНФ является D5 . У нее число логических слагаемых,
т.е. длина S � 2 – наименьшее.
       Минимальной ДНФ является D5 , т.к. �D  min �Di  3.
                                                                      1i5

          Определение 3. ДНФ функции f называется тупиковой, если от-
брасывание любого ее слагаемого или буквы приводит к неэквивалентной
ДНФ.
          Тупиковая ДНФ функции f определяется неоднозначно. Среди ту-
пиковых ДНФ функции f всегда содержится и минимальная.
          Приведем алгоритм построения минимальной ДНФ для функции
 f � x1 , x 2 , ..., x n � .
          Шаг 1. Построить всевозможные э.к. из переменных 1, x1 , x 2 ,..., x n ,
x1 ,..., x n , x1 x 2 , ..., x i x j , ..., x1 x 2 ...x n . ;
          Шаг 2. Из построенных э.к. построить всевозможные ДНФ;
          Шаг 3. Упорядочить множество всех полученных ДНФ на 2-м шаге в
направлении возрастания величин � D ;          i


     Шаг 4. Сравнить таблицы истинности для функции f и для ДНФ,
двигаясь по упорядоченному множеству, полученному на 3-м шаге.
     Первая ДНФ, у которой таблица истинности будет такой, как у
функции f , является минимальной.
     Определение 4. Импликантом функции f называется элементар-
ная конъюнкция K � x i� & x i� & ... & x i , � k � �0,1�, i k � �1, 2 , ..., n� для
                               1          2
                                                           ��
                           1          2                    �


всех k � 1, � такая, что K � f � f .
     Импликант K функции f называется простым импликантом, если
после отбрасывания любой буквы x i� из K получается элементарная
                                                   k
                                                       k




конъюнкция, не являющаяся уже импликантом функции f .

                                              27