Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

33 Задача нахождения минимального подмножества простых импликантов решается с помощью таблиц, столбцы которых перенумерованы k i , строки простыми импликантами  1, ...,  m . Из примера предыдущей лекции получаем следующую таблицу 7.1 простых импликантов: Таблица 7.1. 0000 0001 0010 1000 1001 1100 1101 00-0   -00-     1-0-     Крестики стоят в тех позициях, где импликант покрывает элементарную конъюнкцию. Правило. Если в столбце имеется лишь один крестик, то соответствующая строка (т.е. импликант) должна быть выбрана обязательно (т.к. только этот импликант покрывает соответствующую конъюнкцию). Множество таких строк (т.е. импликантов) отражает ядро задачи. Далее, вычеркиваем все столбцы, у которых на пересечении с данной строкой есть крестик (т.е. конъюнкция покрывается импликантом). В нашем примере в ядро задачи входят все импликанты. Следовательно, минимальным представлением для функции f(x,y,z,t) является xyt yz xz   , т.е. f x y z t xyt yz xz    ( , , , ) . Возможны следующие варианты: 1) после выделения ядра еще остаются элементарные конъюнкции, подлежащие покрытию; 2) может оказаться, что останутся простые импликанты, которые не покрывают ни одну элементарную конъюнкцию, не покрытую элементами ядра. В первом случае из множества импликантов, не входящих в ядро, требуется выбрать такие, которые покрывают оставшиеся непокрытыми элементарной конъюнкции. Во втором случае импликант является лишним.