с участием

В булевой логике термин «импликант» имеет либо общее, либо частное значение. В общем использовании это относится к гипотезе импликации ( импликанта ). В конкретном использовании термин продукта (т. е. соединение литералов) P является импликантой булевой функции F , обозначаемой $P\leq F$, если P подразумевает F (т.е. всякий раз, когда P принимает значение 1, то же самое происходит и с F ).Например, импликанты функции

$f(x,y,z,w)=xy+yz+w$

включить условия $xy$, $xyz$, $xyzw$, $w$, а также некоторые другие.

Премьер с участием

Первичная импликанта функции — это импликанта (в указанном выше частном смысле), которую нельзя охватить более общей (более сокращенной, то есть с меньшим количеством литералов ) импликантой. У. В. Куайн определил простую импликанту как минимальную импликанту, то есть удаление любого литерала из P приводит к появлению неимпликанты для F . Существенные основные импликанты (также известные как основные основные импликанты ) — это основные импликанты, которые покрывают результат функции, который не может покрыть ни одна комбинация других простых импликантов.

Используя приведенный выше пример, можно легко увидеть, что, хотя $xy$ (и другие) является основным импликантом, $xyz$ и $xyzw$ нет. Из последнего можно удалить несколько литералов, чтобы сделать его простым:

• $x$, $y$ и $z$ можно удалить, получив $w$.
• Альтернативно, $z$ и $w$ можно удалить, получив $xy$.
• Окончательно, $x$ и $w$ можно удалить, получив $yz$.

Процесс удаления литералов из логического термина называется расширением термина. Расширение на один литерал удваивает количество входных комбинаций, для которых этот термин верен (в бинарной булевой алгебре). Используя приведенный выше пример функции, мы можем расширить $xyz$ к $xy$ или чтобы $yz$ не меняя обложку $f$.

Сумма всех простых импликант булевой функции называется ее полной суммой , минимальной покрывающей суммой или канонической формой Блейка .

См. также

• Алгоритм Куайна – Маккласки
• Карта Карно
• метод Петрика

Внешние ссылки

• Слайды, объясняющие импликанты, основные импликанты и основные основные импликанты
• Примеры поиска существенных простых импликантов с использованием K-карты