В материале [https://dzen.ru/a/YzgeT9bh0iKLgVYv?share_to=link] представлен алгоритм минимизации булевой функции в классе нормальных форм, при этом дизъюнкция простых импликантов представляет собой сокращённую дизъюнктивную нормальную форму, в текущем материале покажем, как определять простые импликанты для произвольной булевой функции.
Напомним несколько определений:
Определение. Булеву функцию G назовем импликантом булевой функции F, если для любых наборов значений аргументов этих функций из равенства G = 1 следует равенство F = 1.
Определение. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.
Пример.
Решение. Построим следующую таблицу истинности:
Из полученной таблицы истинности видно, что элементарные конъюнкции под номерами 1 и 3 являются импликантами, а вторая - нет.
Выясним, какой из импликантов является простым. Дополним таблицу истинности:
То есть отбрасывание переменной y привело к тому, что получившееся выражение также является импликантом, а отбрасывание остальных переменных - получившиеся выражения перестали быть импликантами.
То есть поочередное отбрасывание каждой переменной привело к тому, что получившиеся выражения перестали быть импликантами, то импликант xz является простым.
Упражнение 1. Для булевой функции из таблицы ниже определите все импликанты. Укажите, какие из них являются простыми импликантами.
Пример выполнения практического задания (вариант № 30)
Все возможные импликанты приведены в следующих таблицах:
Упражнение 2. Для булевой функции из таблицы ниже запишите СДНФ. Укажите, какие из элементарных конъюнкций СДНФ являются импликантами (простыми импликантами). Найдите не менее 2 простых импликантов.