СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

БУЛЕВЫХ ФУНКЦИЙ

Цель работы: овладение аппаратом булевых функций для решения проблемы выполнимости.

Теоретические сведения

Введем следующие обозначения

Легко проверить, что , .

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

(5.1)

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

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

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

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

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

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

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

Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Х_i или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее.

В ЭВМ совершенные формы представляются в виде матрицы размера k´ n, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f.

Пусть х – массив пропозиционных переменных. Предположим, х_i получили некоторые значения и необходимо вычислить значение нормальной формы f. Предлагаются следующие правила:

Эффективность данного алгоритма проявляется также в том, что цикл можно прервать, как только будет найдено необходимое значение i или j.

Например, вычислим значение функции f(x₁, x₂) = x₁ ~ x₂ при x₁ = 0; x₂ = 1. Запишем таблицу истинности функции f:

x₁	x₂	f

Тогда F_СДНФ= ; F_СКНФ= . Поскольку ни одна из строк F_СДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями х_j, то f (0, 1) = 0.

Тоже самое можно определить и по СКНФ, так как первая строка F_СКНФ совпадает со значениями х_j, то f (0, 1) = 0.

Сформулируем законы булевой алгебры и производные от них формулы в терминах булевых функций.

1. X Ù Y º Y Ù X, X Ú Y º YÚ X.

2. (X Ù Y)Ù Z º X Ù (YÙ Z), (XÚ Y)Ú Z º XÚ (YÚ Z).

3. XÙ X º X, XÚ X º X.

4. XÚ (X Y) º X, X (XÚ Y) º X.

5. X Ù (YÚ Z) º (X Ù Y)Ú (X Ù Z), XÚ (YÙ Z) º (XÚ Y)Ù (XÚ Z).

6. XÙ 0 º Л, XÙ 1 º X,

XÚ 0 º X, XÚ 1 º 1.

7. , .

8. .

9. º 0.

10. º 1.

11. .

12. .

13. ,

14. ,

Для преобразования одной совершенной нормальной формы в другую нужно вначале максимально упростить исходную форму, воспользовавшись законами 4, 5, 13, 14. Затем преобразовать упрощенную формулу по свойству взаимной дистрибутивности 5, получив нормальную форму, и развернуть её в требуемую совершенную форму по законам склеивания 13.

⇐ Предыдущая 123 4 Следующая ⇒