- •Методические материалы к изучению курса «Дискретная математика»
- •Часть IV. Булевы функции
- •Содержание
- •§1. Высказывания и операции над ними.
- •§2. Формулы алгебры логики. Таблицы истинности.
- •§3. Логическое следование и равносильность формул. Связь с булевыми алгебрами.
- •§4. Нормальные формы. Двойственность.
- •4.1. Дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма.
- •4.2. Конъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.
- •§5. Булевы функции и основные их классы. Полином Жегалкина.
- •5.1. Понятие булевой функции и способы её задания.
- •5.3. Полином Жегалкина.
- •5.4. Функциональная полнота.
- •§6. Минимизация булевых функций.
- •6.2. Сокращённая днф. Метод Квайна.
- •§7. Применение к релейно-контактным схемам.
- •Варианты индивидуальных заданий Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Вариант 15
- •Вариант 16
- •Вариант 17
- •Вариант 18
- •Вариант 19
- •Вариант 20
- •Вариант 21
- •Вариант 22
- •Вариант 23
- •Вариант 24
- •Вариант 25
- •Вариант 26
- •Вариант 27
- •Вариант 28
- •Вариант 29
- •Вариант 30
- •Образец выполнения индивидуального задания
- •Литература
5.3. Полином Жегалкина.
Определение 5. Полиномом Жегалкина называется полином вида
с,
(то есть сумма произведений вида ), где суммирование ведётся по некоторому множеству различных наборов (i1, i2, …, ik), в которых все ij также различны.
Любая булева функция единственным образом (с точностью до следования слагаемых) представима в виде полинома Жегалкина.
Для представления булевой функции в виде полинома Жегалкина достаточно:
1. Привести функцию к ДНФ (КНФ).
2. Выразить операции &, , через операции булева кольца по формулам из п.5.2.
Пример 5.3. Найдём полиномы Жегалкина для функций из примера 5.2. Для функции (х&у)(&) имеем
(х&у)(&)=хуху=ху=
=ху(1х)(1у)=ху1хуху=1ху,
то есть (х&у)(&)=1ху (в чём мы уже убеждались). Для функции химеемх=х(1у)=хху, то есть х=хху.
Как видим, для функции хполином Жегалкина содержит произведения переменных. Такие полиномы называютсянелинейными. Полиномы Жегалкина вида c0c1x1c2x2…cnxn называются линейными. Таким образом, линейная функция представима в виде линейного полинома Жегалкина.
Заметим, что если А и В различные конституенты единицы, то они содержат хотя бы одну пару противоположных литер, и тогда АВ=0, АВ=АВ. Поэтому полином Жегалкина удобно получать из СДНФ формулы.
Упражнение 5.4.Построить полиномы Жегалкина для функций упражнения 5.1.
Решение. а) Имеем СДНФf(x,y,z)=zyxz(см. решение упражнения 5.1, а)). Учитывая, что=1х, =1у,=1 zи раскрывая скобки, получаем
zyxz=zyxz=(1х)(1у)z(1х)y(1 z)x(1у)z=
=zхzуz хyzyхyyzхyzxzxуz=yzxyхyz.
То есть zyxz=yzxyхyz. В частности, функция не является линейной.
5.4. Функциональная полнота.
Определение 6. Система булевых функций F=f1, f2, …, fn называется полной, если любая булева функция представима в виде суперпозиции функций из F.
Система булевых функций является полной тогда и только тогда, когда для каждого из классов Поста система содержит функцию, не лежащую в данном классе.
Определение 7. Система булевых функций называется базисом, если она полна, и удаление любой функции из этой системы делает её неполной.
Упражнение 5.5.Проверить полноту следующих систем булевых функций:
а) ,; б),; в); г)&,.
Решение. а) Принадлежность данных функций к каждому из классов Поста сведём в таблицу:
-
P0
P1
S
M
L
xy
+
+
+
В таблице знаком «+» на пересечении строки с указанием функции со столбцом с указанием класса обозначен тот факт, что функция принадлежит соответствующему классу, а знаком «»тот факт, что функция не принадлежит данному классу. В каждом столбце имеется знак «», то есть для любого класса Поста системаF=,содержит функцию, не лежащую в данном классе. Следовательно, система функцийF=,является полной. Она образует базис, так как удаление любой функции из этой системы ведёт к тому, что оставшаяся система является неполной.
§6. Минимизация булевых функций.
6.1. Проблема минимизации булевых функций заключается в том, чтобы для произвольной функции, не являющейся константой 1, получить наиболее простую ДНФ. Прежде, чем приступить к решению проблемы, уточним, что значит «наиболее простая ДНФ».