Тема 2.4 Конъюнктивная нормальная форма.

 

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

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

Теорема: Для любой высказывательной формы существуют равносильные ДНФ и КНФ.

Доказательство:

1) по теореме 1 существует Ы* - приведенная равносильная высказывательная форма, т.е. , к Ы* применим первый дистрибутивный закон необходимое число раз, тогда получим приведенную форму, которая будет являться ДНФ, если закон уже применить нельзя. Если невозможно применить первый дистрибутивный закон, то все члены любой конъюнкции в этой форме является либо переменными или отрицаниями переменных.

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

Способы построения ДНФ и КНФ для любой высказывательной формы:

1) составляется Ы* - приведенная высказывательная форма, являющаяся равносильной (т.е. применяется необходимое число раз законы Моргана, импликации)

2) для получения ДНФ к Ы* применяется первый дистрибутивный закон:

для получения КНФ к Ы* применяется второй дистрибутивный закон:

Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

1. различны все члены конъюнкции;

2. различны все члены каждой дизъюнкции;

3. ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;

4. каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид

,

где конъюнкция берется по всем наборам с=(с₁, с₂, …, с_n) из 0 и 1, для которых F(c)=0.

Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x₁, x₂, …, x_n) существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки конъюнктивных членов.

Опишем два способа приведения к совершенным нормальным формам.

1-й способ – аналитический

Приведение к СКНФ. Алгоритм приведения.

1. привести формулу с помощью равносильных преобразований к КНФ.

2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);

3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;

4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;

5. если в какой-нибудь дизъюнкции не содержится переменной x_i из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции;

6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

Полученная формула и является СКНФ данной формулы.

 

Привести следующие формулы к СКНФ с помощью равносильных преобразований:

1. ;

2. .

Решение.

1.

2.

 

2-й способ – табличный.

Составляем таблицу истинности для данной функции.

Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.

 

Построить СКНФ для данных формул логики высказываний.

1. .

2.

Решение.

1. Строим таблицу значений, используя предыдущий пример.

№	x	y	z

Рассматриваем только наборы, на которых формула принимает значение ноль.

СКНФ (0): № 0, 1, 2, 3, 6:

2. Строим таблицу значений, используя предыдущий пример.

№	x	y	F=(x® y)ÙxÙy

СКНФ (0): № 0, 1, 2: