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

5. Пусть X 1 ,..., X m , U 1 ,..., U n – произвольные формулы алгебры логики.
   Доказать следующие эквивалентности:
         1) X 1 X 2 ... X m  U1U 2 ...U n  
                                                  i1,..., m
                                                             ( X i  U j );
                                                   j 1,..., n

         2) ( X 1 ∨ .X 2 ∨ ... ∨ X m )(U 1 ∨ U 2 ∨ ... ∨ U n ) = ∨ X iU j .
                                                                              i-1,...,m
                                                                              j=1,...,n

6. С помощью второго дистрибутивного закона преобразовать ДНФ в
   КНФ:
         1) xy � yz � xz ;
         2) xyz � xyz � xyz;
         3) x 1 x 2 � x 2 x 3 � x 4 x 3 � x 2 .


      5.3 Классификация ДНФ. Минимизация булевых функций

     Проблема минимизации булевых функций состоит в том, чтобы по-
строить ДНФ, у которой число вхождений минимально по сравнению со
всеми другими ДНФ, реализующими булеву функцию.
     Определение 1. ДНФ функции f называется кратчайшей, если она
имеет наименьшую длину среди всех эквивалентных ей ДНФ.
     Определение 2. ДНФ функции f называется минимальной, если
она имеет наименьшее число вхождений – букв x i� среди всех эквива-            i



лентных ДНФ.
                                        S
      Обозначим через � D � � � � K i � – сумму рангов э.к., входящих в
                                       i �1

ДНФ. Число � D называется сложностью ДНФ. Тогда ДНФ, у которой
сумма рангов � D минимальна среди всех ее ДНФ, является минимальной.
      Способ построения минимальной ДНФ дает следующая теорема.
      Теорема. С помощью равносильных преобразований, применяя фор-
мулы:
      1. Поглощения K 1 � K 1 K 2 � K 1 ;
      2. Склеивания XK  XK = K ;
      3. Неполного склеивания XK  XK  XK  XK  K ;
      4. Обобщенного склеивания XK 1 � XK 2 � XK 1 � XK 2 � K 1 K 2 ,
из любой ДНФ функции f можно построить ДНФ, которая
а) либо совпадает с минимальной или кратчайшей,
б) либо минимальная (кратчайшая) получается из нее удалением одной или
нескольких элементарных конъюнкций.
                                                   26