Дизъюнктивная нормальная форма.

Элементарной конъюнкцией называется такая формула A, которая является конъюнкцией, возможно одночленной, переменных и их отрицаний. Говорят, что формула A находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией, возможно одночленной, элементарных конъюнкций. ДНФ: A = x₁ Ú · x₂ Ú x₁ · .

Теорема о приведении формулы к ДНФ. "A$B, находящаяся в ДНФ, что A Û B. B называется ДНФ А.

Доказательство: В качестве доказательства приводят алгоритм построения ДНФ формулы А.

1. С помощью основных равносильностей, которые позволяют устранить операции импликации и эквивалентности, строят . При этом А₁ не содержит операций импликации и эквивалентности.

Основные равносильности:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8)

2. От А₁ переходят к А₂, в которой отрицание только перед переменной 1) A₁ º A

2)

Полученная А₂ равносильна А и состоит из многочисленных конъюнкций и дизъюнкций. К А₂ применяют формулу дистрибутивности конъюнкции относительно дизъюнкции. Получим А₃, находящуюся в дизъюнктивной нормальной форме.

Рассмотрим конъюнкцию х₁^σ, х₂^σ2, ... , х_n^σn (1).

Конъюнкция (1) называется конституентной единицей.

Теорема.f(х₁, х₂,…, х_n) может быть представлена в виде дизъюнкций конституент 1. На любом наборе f(х₁, х₂,…, х_n)=1 будет равна 1 и только одна конституента. Дизъюнкция конституент равна 1, если 1 равна хотя бы 1 конституента.

Пример

f₁(х₁, х₂, х₃)= _{1 3} Ú ₁ x₂ x₃Ú x₁ x₃Ú x₁x_{2 3}.

f₂(х₁, х₂, х₃)= ₁ x_{2 3} Ú ₁ x₂ x₃Ú x₁ x₃Ú x₁x₂х₃.

Всякую конъюнкцию переменных функций функций, взятых с отрицанием, называют элементарной дизъюнкцией. Дизъюнкцию элементарных конъюнкций называют дизъюнктивной элементарной формой.