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

                                                78
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________


     Пример 1. Для функции f =(111 011 0 0) построить несколько ДНФ.
Указать кратчайшую и минимальную среди них.
     Решение. Предварительно построив таблицу истинности для f и
применяя преобразования, получим следующие ДНФ:
             D1 = x y z ∨ x y z ∨ x y z ∨ x y z ∨ x y z; ρ D =15;                    1


                D2 = x y ∨ x y z ∨ x y z ∨ x y z;                     ρ D =11;
                                                                        2


                D3 = x y ∨ x y z ∨ x y ;         ρ D =7; 3


                D4 = x y ∨ x z ∨ x y ;          ρD =6;
                                                 4


                D5 = y ∨ x z ;        ρ D =3.
                                        5


       Кратчайшей ДНФ является D5 . У нее число логических слагаемых,
т.е. длина S =2 — наименьшее.
       Минимальной ДНФ является D5 , т.к. ρ D =min ρ D =3 .
                                                                            1≤i ≤5       i


          Определение 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}, ik ∈{1, 2 , ..., n} для
                                  1         2                    σρ
                              1         2                        ρ


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



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