2015-05-13
429
Пусть K(f) - комплекс кубов функции f. Куб u ÎK(f) называется простым импликантом, если K(f) не содержит куба, покрывающего куб u. Простые импликанты обозначаются Z(f). В данном примере Z(f)=(10*, **1).
Теорема. Если С - минимальное покрытие, то С состоит только из простых импликантов, т.е. Сmin£Z(f).
Действительно, если u Î Сmin и не является простым импликантом, т.е. покрывается кубом v ÚK(f), то заменив u на v,получим покрытие меньшего веса, что противоречит минимальности С.
