2. Нормальные формы

Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами.

Алгоритм построения совершенных нормальных форм.

1. Преобразовать формулу к приведенному виду (см. п.1.).

2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности операций конъюнкции и дизъюнкции.

3. Если нормальная форма не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13.

Задание. Построить совершенные нормальные формы формулы .

Решение. Преобразуем формулу к приведенному виду и затем упростим ее.



Полученная формула является КН- и ДН-формой. Обе построенные нормальные формы не являются совершенными. Приведем их к совершенному виду, используя законы склеивания 13.

–СКН-форма.

 





–СДН-форма.

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы. Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.

Задание. Найти интерпретации, на которых формула  )С)) принимает значения 1 и 0.

Решение.

1. Упростим формулу и построим её нормальные формы.

)С))  )С))    )С))  0  С))  С)   (A  B)  (A  C)

2. Построим совершенные нормальные формы.

СКНФ строим из КНФ С).

С)  



СДНФ – из ДНФ (A  B)  (A  C).

(A  B)  (A  C) 

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

A	B	C
1 1 1	1 1 0	1 0 1

Аналогично по СКНФ найдем интерпретации, на которых формула ложна.

A	B	C
0 0 0 0 1	0 0 1 1 0	0 1 0 1 0

Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.

Например, функция f переменных x₁, x₂, x₃, заданная в таблице

x1	x2	x3	f	g	h
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 1 0 0 1 0 1 1	1 0 1 0 0 1 1 0	0 1 1 0 0 1 1 0

Таблица 1.

имеет следующие совершенные нормальные формы:

- СКН-форма;

- СДН-форма.

Упростив любую из этих формул, можно получить простейшую формулу, реализующую данную функцию.