Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ
БУЛЕВЫХ ФУНКЦИЙ Цель работы: овладение аппаратом булевых функций для решения проблемы выполнимости. Теоретические сведения Введем следующие обозначения . Легко проверить, что , . Теорема 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(x1, x2) = x1 ~ x2 при x1 = 0; x2 = 1. Запишем таблицу истинности функции 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. Популярное:
|
Последнее изменение этой страницы: 2017-03-11; Просмотров: 760; Нарушение авторского права страницы