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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

()~() ~

~ () ~ () ~

~ () ~ ()

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

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

() ~ () ~

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

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

Теорема 4.3 (о разложении булевых функций). Любую булеву функцию можно представить в виде

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

Из этой теоремы непосредственно следует представление булевой функции в виде СДН-формы.

Теорема 4.4. Всякая булева функция (кроме 0) имеет единственную СДН-форму

.

С помощью принципа двойственности легко доказать представление функции СКН-формой.

Теорема 4.5. Всякая булева функция (кроме 1) имеет единственную СКН-форму

.

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

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

Таблица 1.

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

- СКН-форма;

- СДН-форма.

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

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы.

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

Варианты заданий

1. Преобразовать формулы к дизъюнктивной и конъюнктивной нормальным формам:

а) (((A ® B) ® (C ® ØA)) ® (ØB ® ØC));

б) (((((A ® B) ® ØA) ® ØB) ® ØC) ® C);

в) ((A ® (B ® C)) ® ((A ® ØC) ® (A ® ØB))).

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

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

4. Привести к совершенной дизъюнктивной нормальной форме, то есть найти СДНФ, эквивалентную данной формуле:

а) ((ØA ® ØB) ® ((B Ù С) ® (A Ù С);

б) (((А ® B) ®ØA) ® (A ® (B Ù A)))

в) (Ø((A Ù B) ® ØA) Ù Ø((A Ù B) ® ØB)).

5. Привести к совершенной конъюнктивной нормальной форме, то есть найти СКНФ, эквивалентную данной формуле:

а) ((С ® A) ® (Ø(B Ú С) ® A));

б) (Ø((A Ù B) ® A) Ú (A Ù (B Ú С)));

в) (Ø(A Ù (B Ú С)) ® ((A Ù B) Ú С)).

6. Построить формулу U такую, чтобы данная формула была тождественно истиной:

а) (((U Ù Q) ® ØR) ® ((R ® ØQ) ® U));

б) (((R ® (ØQ Ù R)) ® U) ® (U Ù (R ® Q) Ù R)).

7. Для функций g и h, определённых в таблице 1, найти СКН - и СДН – формы и простейшие формулы, реализующие эти функции.

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

где x₁ и x₂ - одноимённые разряды 1-го и 2-го слагаемых; e₁ - единица переноса из младшего разряда; e₂ – единица переноса в старший разряд суммы; å - результат суммирования.

9. Построить формулу от трёх переменных, которая истинна в том и только в том случае, когда ровно две переменные ложны.

10. Построить формулу от трёх переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.

11. По СКНФ формулы U построить:

а) СДНФ двойственной формулы U^*;

б) СКНФ формулы ØU;

в) СДНФ формулы ØU.

12. По СДНФ формулы U и СДНФ формулы B построить:

а) СКНФ и СДНФ формулы (U Ú B);

б) СКНФ и СДНФ формулы (U Ù B);

в) СКНФ и СДНФ формулы (U ® B).

Поиск по сайту: