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

Элементарной конъюнкцией называется такая формула 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 ₂ х ₃.

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