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

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

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