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

                                                   77
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
           1) X 1 X 2 ... X m ∨U 1U 2 ...U n = ∧ (X i ∨U j );
                                              i =1,...,m
                                                    j =1,...,n

           2) ( X 1 ∨ X 2 ∨... ∨ X m )(U 1 ∨U 2 ∨... ∨U n ) = ∨ X i U j ;
                                                             i −1,...,m
                                                                 j =1,...,n


6. С помощью второго дистрибутивного закона преобразовать ДНФ в
   КНФ:
           1) xy ∨ yz ∨ xz ;
           2) xyz ∨ xyz ∨ xyz;
           3) x1 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 ;
      1. Склеивания XK ∨ X K = K ;
      2. Неполного склеивания XK ∨ X K = XK ∨ XK ∨ K ;
      3. Обобщенного склеивания XK 1 ∨ XK 2 = XK 1 ∨ XK 2 ∨ K 1 K 2 ,
из любой ДНФ функции f можно построить ДНФ, которая
а) либо совпадает с минимальной или кратчайшей,
б) либо минимальная (кратчайшая) получается из нее удалением одной или
нескольких элементарных конъюнкций.