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

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

Примеры элементарных конъюнкций: ;

Теорема 1: Элементарная конъюнкция является тождественно ложной тогда и только тогда, когда существуют переменные высказывания и в элементарной конъюнкции для некоторого i .

Дизъюнктивной нормальной формой (ДНФ) называют формулу логики высказываний, которые представляют собой дизъюнкцию элементарных конъюнкций.

Теорема 2 (критерий ложности): ДНФ тождественно ложна тогда и только тогда, когда в каждую элементарную конъюнкцию входят элементы вида и для некоторого i.

Замечание: i для каждой элементарной конъюнкции свой

Примеры:

1. - ДНФ

2. – ДНФ

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

Примеры элементарных дизъюнкций: ;

Теорема 3: Элементарная дизъюнкция является

тождественно истинной тогда и только тогда, когда существуют переменные высказывания и в элементарной дизъюнкции для некоторого i .

Конъюнктивной нормальной формой (КНФ) называют такую форму логики высказываний, которая представляет собой конъюнкцию элементарных дизъюнкций.

Теорема 4 (критерий истинности): КНФ тождественно истинно тогда и только тогда, когда каждая элементарная дизъюнкция содержит набор переменных и для некоторого i.

Замечание: i для каждой элементарной дизъюнкции свой.

Примеры:

1. - КНФ

2. – КНФ

Две операции конъюнкция и дизъюнкция называются двойственными друг к другу,то есть конъюнкцию можно заменить дизъюнкцией, и наоборот.

Для того чтобы от дизъюнкции перейти к конъюнкции, и наоборот, нужно установить двойное отрицание и одно из них применить вместе с законом де Моргана.

Для того чтобы от ДНФ перейти к КНФ, и наоборот, можно применить законы дистрибутивности.

Пример: Приведите формулу к КНФ и ДНФ:

С помощью равносильных преобразований, используя законы логики

высказываний, получим:

- КНФ.

Перейдем от КНФ к ДНФ, используя закон дистрибутивности конъюнкции относительно дизъюнкции идемпотентностии и законы дополнительности:

– ДНФ

Замечание: Для того чтобы проверить правильно ли привели формулу к КНФ и ДНФ, можно построить таблицы истинности первоначальной и получившихся формул. Последние столбцы таблиц этих формул должны принимать одинаковые значения истинности.