Реферат: Конспект лекций по дискретной математике
2) Можно утверждать, что для любого набора аргументов, на котором функция равна нулю, ее импликанта также равна нулю.
3) Если g(x) и j(x) являются импликантами функции f(x), то их дизъюнкция также является импликантой этой функции.
Простейшими примерами импликант могут служить конъюнктивные термы, входящие в ДНФ данной функции.
Пример : для f3 (x)=V(0,1,4,6,7) (#)
(f=1) _ _ _
импликантами являются х1 х2 х3 ; х1 х2 х3 ; х1 х2 ;...
Произвольная дизъюнкция этих термов также является импликантой функции.
Определение : Простой (первичной) импликантой булевой функции называется конъюнктивный терм, который сам является импликантой этой функции, но никакая его собственная часть уже не является импликантой этой функции.
Под собственной частью терма понимается новый терм, полученный из исходного, путем вычеркивания произвольного числа букв.
Для данного примера функции (#) простыми импликантами являются : _ _ _
х1 х2 х3 ; х1 х2 х3 ; х1 х2 ;...
Множеству простых импликант можно поставить в соответствие множество максимальных кубов.
Определение : Дизъюнкция всех простых импликант булевой функции представляет собой ДНФ этой функции, которая называется сокращенной - СДНФ.
Для функции (#) из приведенного примера
_ _ _ _ _
СДНФ : y= х1 х2 v х1 х2 vх2 х3 v х1 х3
Понятие «сокращенное» присвоено ДНФ в том смысле, что она, как правило, содержит меньшее количество букв и термов по сравнению с КДНФ. Для нашего примера КДНФ содержит 15 букв и 5 термов, а СДНФ - 8 букв и 4 терма.
Аналогия между импликантами и кубическим представлением Булевой функции
Любому кубу из К(f) можно поставить в соответствие конъюнктивный терм который можно рассматривать как импликанту булевой функции .Любой простой импликанте булевой функции соответствует максимальный куб ,и в свою очередь множество всех простых импликант соответствует множеству Z(f) всех максимальных кубов К(f).
Таким образом м?