Математическая логика и теория алгоритмов. Стенюшкина В.А. - 9 стр.

        Нормальная форма

        2.1  Конъюнктивная                          нормальная           форма.          Дизъюнктивная
        нормальная форма
                                                                              x, σ = 1,
       Пусть x – двоичная переменная. Введем обозначение x σ = 
                                                                              x, σ = 0.
Тогда функции и x1σ ∧ ...∧ x n σ , x1σ ∨ ...∨ x n σ , где (σ1,…,σn) – двоичный набор, а
                            1            n      1              n



x1,…, xn – двоичные переменные (не обязательно различные) называются соот-
ветственно элементарной конъюнкцией, элементарной дизъюнкцией.

        Пример–Пусть             (σ1,    σ2,        σ3)=(0,1,1). x1 σ1 ∧ x 2 σ 2 ∧ x 3 σ 3 x1 ∧ x 2 ∧ x 3 -
Тогда
      элементарная конъюнкция.
      Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция
элементарных конъюнкций.

        Пример - ( x1 ∧ x2 ) ∨ ( x1 ∧ x2 ) - дизъюнктивная нормальная форма.

      Конъюнктивной нормальной формой (КНФ) называется конъюнкция
элементарных дизъюнкций.
      Путем тождественных преобразований любую булеву функцию можно
привести к дизъюнктивной или конъюнктивной нормальным формам. Если ис-
ходная функция содержит только основные связки ( , ∧, ∨, →, ↔), то сначала
нужно элиминировать связки с помощью равенств:
               x → y = x ∨ y, x ↔ y = ( x ∧ y ) ∨ ( x ∧ y ) = ( x ∨ y ) ∧ ( x ∧ y );
        затем продвинуть знак отрицания к переменным с учетом равенств

                                   x ∧ y = x ∨ y , x ∨ y = x ∧ y;

       устранить двойное отрицание, x = x. так как , Затем, используя одно
из равенств: x∧(y∨z)=(x∧y)∨(x∧z),          x∨(y∧z)=(x∨y)∧(x∨z) непо-
средственно получить дизъюнктивную или конъюнктивную нормальную фо-
рму.
       Пример – Дана булева функция: ( x1 → x 2 ) ↔ x3 .
       Выполним последовательно указанные преобразования:

               ( x1 → x 2 ) ↔ x 3 = (( x 1 ∨ x 2 ) ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) =
        (( x1 ∧ x 2 ) ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) = ( x 2 ∨ x 3 ) ∧ (( x 1 ∨ x 2 ) ∨ x 3 ) =
                           ( x1 ∨ x 3 ) ∧ ( x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ).
        Получена конъюнктивная нормальная форма.