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

       Легко видеть, что x � � 1 тогда и только тогда, когда x � � .
       Пусть x1 , x 2 , ... , x n – булевы переменные.

      Определение. Формулы алгебры логики вида:
                        x i�11 & x i�22 & ... & x i�nn и x i�11 � x i�22 � ... � x i�nn ,
где i k � �1, 2 , ..., n�, � k � �0,1�, называются соответственно элементарной
конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве бу-
левых переменных �x1 , x 2 , ... , x n �.
      Число логических множителей в э.к. и логических слагаемых в э.д.,
называется рангом э.к. и э.д. соответственно. Считается, что константа
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 & ... & D S ,
      где 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 � будут равносиль-
ные между собой следующие КНФ:

                                           22