Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Минимальная (относительно Ьв) д. н. ф. является тупиковой.
Среди тупиковых д. н. ф. найдется минимальная (относительно Ь) д. н. ф.
Рассмотрим теперь более сложный пример на построение тупиковых д. н. ф., используя геометрические соображения.
Пример 13. Пусть х2, задана табл. 5.
На рис. 7 изображено множество Nf. В имеются следующие максимальные грани: А76, Лгв, N1 — ребра, А7!, Лг2, ЛГ«, Л* — грани (двухмерные).
Таким образом, покрытию ЛТ и II Л7* и Лт4 и N3 и N4 и Ц А/т соответствует сокращенная д. н. ф.
ГЛ. і. ДИЗЪЮНКТИВНЫЙ fiUFMAJibnma vumu
Таблица 5
*4 >« К* f(x 1, хи xit хл)
0 1 0 0 0
0 1 1 0 0
1 0 0 1 0
1 1 1 0 0
1 1 1 1 0
на остальных наборах 1
Две грани Ni и /V* входят в любое покрытие, так как только они покрывают соответственно точки (0111) и (1011). Для покрытия точки (0000) нужно взять либо грань Nu либо грань Л'г.
а) Взята грань ЛГ1.
Остается покрыть две точки (1100) и (1101), что осуществляется двумя способами; либо взятием ребер Nb и /V7, либо взятием ребра iW Следовательно, получаем два неприводимых покрытия:
Nt U N3 U N\ U N5 U N1f
U Лга U Ni U N,.
б) Взята грань Лг2.
Остается покрыть три точки (1000), (1100) и (1101)—что можно сделать двумя способами; либо взяв ребра Nb и Лтт, либо взяв ребра Ne и N7. Здесь мы имеем еще два неприводимых покрытия:
N2UN3[)NiUNtUN,.
Для построения тупиковых д. н. ф. нужно заметить, что максимальным граням Nu ..Ni соответствуют простые импликанты
Ki'==i3czXi^ l\.2===Xi%2i К3 — х±Xit Ki хг^з,
Кь — Z2X&Xi, Кв = XiXzXs, К-i — XiX3Xi.
Wffl
Рис, 7
818 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Мы имеем:
= ^2^4 V х \Х-ь V л:2л'з V хгхъхк V х&зРъ 9?2 = Яг^4 V ХхХь V Х2Х3 V Х^ХгХз,
Теперь перейдем к построению алгоритма для нахождения всех тупиковых д. о. ф. с использованием геометрических идей.
Алгоритм построения тупиковых Д. II. ф. Мы исходим из покрытия множества А'/ системой всех его максимальных граней
Пусть Nf~i.Pi, ..Рк} и Р0 — любая точка*) такая, что Ра Ф М} (мы считаем, что /^1). Составим таблицу (см. табл. 6), в которой
Очевидно, что первый столбец — нулевой, так как Р0 Аг/, а в каждом столбце, отличном от первого, содержится хотя бы одна единица. Значит, первый столбец отличается от всех остальных.
Для каждого / (0 < / < К) найдем множество Е} всех номеров строк, в которых столбец Р} содержит 1 (отличается от столбца Ра).
Пусть Е]*={е}1, ..Составим выражение
рассматривая символы е как булевы величины. После этого в полученном выражении ликвидируем поглощаемые или дублирующие члены, т. е. совершаем преобразования
х
и произведем преобразование
*) Точка Рс вводится для того, чтобы была видна связь задачи о покрытии с задачей распознавания,
ГЛ. 1. ДИЗ ЬЮНКТШ 511ЫЛ ДиГМАЛ Ы1Ы и; Фигшы Й1У
вида
А • В V А = А,
А\/А=*А.
Мы получим выражение V являющееся частью выражения V &. Каждое слагаемое в V &' будет определять неприводимое покрытие.
Таблица 6
Ро Рг ^7 * * Я
0 А СТ10 °И аи * * ?
Я о А ^0 °Ц °И
. . .
Лг о Ап °7П(> °т1 °7П} атК
Действительно, будем рассматривать номера строк как булевы переменные, а каждое подмножество максимальных граней функции / — как набор значений этих пере-мепных: если грань входит в подмножество, то соответствующая ей переменная равна единице, а если нет, то равна нулю. Тогда выражение
ац V... V См])
равно единице тогда и только тогда, когда в подмножество входит максимальная грань, покрывающая точку а выражение '
х
& {ез1 V -»? \!еп 1ш)
7=1
равно единице тогда и только тогда, когда подмножество максимальных граней покрывает N3. Поэтому подмножество из максимальных граней, соответствующих переменным из одного слагаемого выражения V является покрытием N Более того, поскольку выражение V <&'
о^и -1. V. шшигити ПРИЛОЖЕНИЯ К КИБЕРНЕТИКИ
содержит в качестве слагаемых в точности все свои простые импликанты (ср. со с. 314), а им (как нетрудно заметить) соответствуют неприводимые покрытия Аг/, все неприводимые покрытия (и только они) строятся таким способом.
Таблица 7
0 I II III IV V VI
1 0 1 1 0 0 0 0
2 0 0 1 1 0 0 0
3 0 0 0 1 1 0 0
4 0 0 0 0 1 1 0
5 0 0 0 0 0 1 1
6 0 1 0 0 0 0 1
Пример 14. Рассмотрим функцию }(х{, х2, #3) (см. табл. 1). Для нее множество /V/ состоит из 6 вершин, которые можно занумеровать числами I, II, ..., VI. Максимальными гранями (см. рис. 6) являются ребра, которые занумерованы арабскими цифрами. Составим таблицу (см. табл. 7). Мы имеем
^-{1,6}, 2>, Еш = {2,31,
— {3, 4), Е\ “ {4, 5), Е\1== (3, 6).
Тогда
V & -(1 V 6) (1 V 2) (2 V 3) (3 V 4) (4 V 5) (5 V 6) =?=
_•= (1V 2 • 6) (3 V 2 - 4) (5 V 4 * 6) =*
•=(1-ЗУ2-3-6У1*2-4У2-4-6)(5У4-6) =
= 1- 3- 5У2-3-5-6У1-2-4-5У2-4-5-6У
V 1 *3 • 4 ? С V2 • 3 ? 4 • 6 У 1 • 2 • 4 • 6 У 2 ? 4 • 0'=
?“1'3*5У2*3*5*бУ1*2-4*5У1-3*4'6У2*4-6. Мы получаем пять неприводимых покрытий или иять тупиковых д. ы. ф.:
5?! = Я ^2 V Х2ХЬ V
= 1|5:,У х2х3 V х&ъ V х2Хз>
% == х \Х 2 V X ,^3 V ХУХ2 У Х&ы
й4 —Х&гУ ХгХ& V Х\Х2 V Х2ХЭ,
9^5 = х 1л’3 V хух2 V х2х5.
Две аз них 91, и К5 являются минимальными.
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
