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

Преобразуем эту формулу, используя соответствующие эквивалентности

U º º

Изобразим схему, соответствующую заключительной формуле

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

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

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

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

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

Теорема 4.1. Для всякой формулы U существуют эквивалентные ей КН-форма и ДН-форма.

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

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ в каждой конъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие конъюнкции называются полными.

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ в каждой дизъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие дизъюнкции называются полными.

Теорема 4.2. 1) Всякая элементарная дизъюнкция высказывательных переменных , не являющаяся ТИ-формулой, эквивалентна некоторой СКН-форме от этих высказывательных переменных.

2) Всякая элементарная конъюнкция высказывательных переменных , не являющаяся ТЛ-формулой, эквивалентна некоторой СДН-форме от этих высказывательных переменных.

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

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

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

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

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

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

.

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

() º () º () º º () º () º ()

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

() º () – СКН-форма.

() º ()

) – СДН-форма.

Дата добавления: 2015-06-04