![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Специальные представления булевых функцийДизъюнктивные и конъюнктивные нормальные формы алгебры высказываний.Для каждой функции логики высказываний можно составить таблицу истинности. Обратная задача тоже всегда разрешима. Введем несколько определений. Элементарными конъюнкциями (конъюнктами) называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций. Элементарными дизъюнкциями (дизъюнктами) называются дизъюнкции переменных с отрицаниями или без них. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций. Для каждой функции алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Алгоритм построения ДНФ: 1. Перейти к булевым операциям, используя формулы эквивалентных преобразований. 2. Перейти к формулам с тесными отрицаниями, то есть к формуле, в которой отрицания располагаются не выше, чем над переменными – применить законы де Моргана. 3. Раскрыть скобки – применить законы дистрибутивности. 4. Повторяющиеся слагаемые взять по одному разу – закон идемпотентности. 5. Применить законы поглощения и полупоглощения. Пример 6. Найти ДНФ формулы: В алгебре Буля справедлив принцип двойственности. Он заключается в следующем. Функция Пример 7. Найти функцию, двойственную к Среди элементарных функций алгебры логики 1 двойственна 0 и наоборот, х двойственна х, Если в формуле F1 представляющей функцию на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F*, представляющую функцию Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме: Пример 8. Найти КНФ формулы: Воспользовавшись результатом примера 6, имеем Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.В каждом из типов нормальных форм (дизъюнктивных и конъюнктивных) можно выделить класс совершенных форм СДНФ и СКНФ. Совершенной элементарной конъюнкцией называется логическое произведение всех переменных с отрицанием или без них, причем, каждая переменная входит в произведение только один раз. Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, т.е. добавлением для отсутствующей переменной xi множится Пример 9. Найти СДНФ для ДНФ примера 6 Совершенной элементарной дизъюнкцией называется логическая сумма всех переменных с отрицаниями или без них, причем, каждая переменная входит в сумму только один раз. Всякую КНФ можно привести к СКНФ, добавляя член конъюнкции, не содержащий какой – либо переменной Xi конъюнкцией Пример 10 . Привести КНФ к СКНФ: Для построения СКНФ можно воспользоваться схемой Пример 11. Найти СКНФ для формулы примера 6. Всякая функция Т.к. СДНФ и СКНФ определены формулами однозначно, их можно строить по таблице истинности формулы. Для построения СДНФ необходимо выделить строки, в которых F принимает значение 1 и записать для них совершенные элементарные конъюнкции. Если значение переменной в нужной строке таблицы истинности равно единице, то в совершенном конъюнкте она берется без отрицания, если нулю – то с отрицанием. Затем совершенные конъюнкты (их число равно числу единиц в таблице) соединяются знаками дизъюнкции. Для построения СКНФ по таблице истинности необходимо выделить в ней строки, где F=0, и записать совершенные элементарные дизъюнкции, после чего соединить их знаками конъюнкции. Если в требуемой строке таблицы истинности (F=0) значение переменной соответствует нулю, то в совершенном дизъюнкте она берется без отрицания, если единице – то с отрицанием. Пример 12. Найти СДНФ и СКНФ по таблице истинности для формулы примера 6. В таблице 14 приведено лишь конечное значение F=10101101. В справедливости этого утверждения следует убедиться самостоятельно, построив развернутую таблицу истинности.
Таблица 14
СДНФ = СКНФ = Как видно из примеров 9, 10, 11, 12 значения СДНФ и СКНФ, полученные различными способами, для заданной функции Дата добавления: 2014-01-03; Просмотров: 1949; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Читайте также:
|