2.8. АЛГЕБРАИЧЕСКИЙ МЕТОД ОБРАЗОВАНИЯ ТУПИКОВЫХ ФОРМ

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

Так, для примера из предыдущего параграфа с учетом обозначений простых импликант в таблице покрытий имеем . Замещая в каждом конъюнктивном члене простые импликанты их символами, получаем выражения четырех тупиковых покрытий в символическом виде

которым соответствуют равносильные тупиковые формы: .

Каждая форма характеризуется числом вхождений переменных, называемых ценой покрытия. Для первой тупиковой формы цена покрытия равна 8, а для трех остальных 11, поэтому первая форма является минимальной.

Алгебраические преобразования упрощаются, если исходить из таблицы покрытий, получаемой после извлечения экстремалей. Тогда результатом таких преобразований являются множества простых импликант, дополняющих совокупность экстремалей до тупиковых покрытий. Сравнивая эти множества по их цене, выбираем минимальные дополнения, которые совместно с множеством экстремалей образуют минимальные покрытия. Так, в рассматриваемом примере после извлечения импликанты F на основе упрощенной таблицы покрытий записываем . Отсюда находим минимальное дополнение которое совместно с экстремалью и дает минимальную форму.