Тупиковые ДНФ
Зарегистрируйся в два клика и получи неограниченный доступ к материалам,а также
промокод
на новый заказ в Автор24. Это бесплатно.
Пусть булева функция задана совершенной ДНФ:
fx1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁
⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4.
Постанавливая значения переменных на различных наборах, можно убедится, что следующая дизъюнкция простых импликант покрывает все единицы заданной булевой функции.
fx1,x2,x3,x4=x2x4⋁x1x2x3⋁x1x3x4⋁x1x2x3⋁x1x3x4. (*)
Если в этой дизъюнкции мы удалим импликанту x2x4, то дизъюнкция оставшихся импликант снова будет покрывать все единицы функции f. Однако, удаление любой другой импликанты из выражения (*) приведет к получению дизъюнкции, которая не будет покрывать все единицы функции f.
Дизъюнкцию совокупности простых импликант функции fx1,x2,…,xn и такую, что удаление из нее любой импликанты приводит к тому, что дизъюнкция оставшихся импликант не покрывает все единицы функции, называют тупиковой ДНФ функции f
Зарегистрируйся, чтобы продолжить изучение работы
.
Важность понятия тупиковой ДНФ определяется следующим утверждением.
Теорема 2. Любая минимальная ДНФ булевой функции fx1,x2,…,xn является тупиковой ДНФ.
Предположим, что это не так.
Во-первых, предположим, что минимальная ДНФ есть дизъюнкция некоторых элементарных конъюнкций, которые не являются простыми импликантами функции fx1,x2,…,xn. Если данное предположение верно, то каждая такая элементарная конъюнкция имеет собственную часть, которая является простой импликантой функции fx1,x2,…,xn. Заменив в минимальной ДНФ каждую конъюнкцию простой импликантой, мы уменьшим ранг каждого члена этой ДНФ и, следовательно, уменьшим суммарный ранг минимальной ДНФ
50% курсовой работы недоступно для прочтения
Закажи написание курсовой работы по выбранной теме всего за пару кликов. Персональная работа в кратчайшее время!
