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

                                             73
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Число логических множителей в э.к. и логических слагаемых в э.д.,
называется рангом э.к. и э.д. соответственно. Считается, что константа 1
— э.к. нулевого ранга, константа 0 — э.д. нулевого ранга Символ & в э.к.
можно опускать для краткости
     Например,
      K 1 = x1 x 2 x 3 x 4 — э.к. 4-го ранга;
      D1 = x1 ∨ x 2 ∨ x 3 — э.д. 3-го ранга.

      Определение. Дизъюнктивной нормальной формой (ДНФ) называ-
ется произвольная дизъюнкция различных элементарных конъюнкций, т.е.
формула вида
               D = K 1 ∨ K 2 ∨ ... ∨ K S , где K i , i =1, s — э.к.
      Число S называется длиной ДНФ. В случае S =0 ДНФ называется
пустой и полагается равной нулю.

      Определение. Конъюнктивной нормальной формой (КНФ) называ-
ется произвольная конъюнкция различных элементарных дизъюнкций, т.е.
формула вида
                                      K =D1 & D2 & ... & DS ,
      где S — длина КНФ, Di , i =1, s — э.д.
      Имеют место следующие теоремы:
      Теорема 1. Для каждой булевой функции f ( x1 , x 2 , ... , x n ), отличной
от тождественного нуля, существует дизъюнктивная нормальная форма D
такая, что f ( x1 , x 2 , ... , x n ) = D .
      Теорема 2. Для каждой булевой функции f ( x1 , x 2 , ... , x n ), отличной
от тождественной единицы, существует конъюнктивная нормальная форма
K такая, что f ( x1 , x 2 , ... , x n ) =K .
      Представление булевой функции в виде ДНФ и КНФ, вообще говоря,
неоднозначно.
                                                     (       )
      Например, для функции f ( x , y , z ) = x ∨ z ( x → y ) будут равносиль-
ные между собой следующие КНФ:
                                 K 1 = x z ( x ∨ y ),
                            K 2 = x z ( x ∨ y )( y ∨ z ),
                            K 3 = x z ( x ∨ y )( y ∨ z )( x ∨ z ).

     Рассмотрим два способа построения ДНФ и КНФ.
     Способ 1. (Метод эквивалентных преобразований). Пусть булева
функция f ( x1 , x 2 , ... , x n ) задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем: