Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
И
Данный алгоритм оказывается эффективным и для примера, рассмотренного нами на стр. 316. Однако уже даже для функций, зависящих от небольшого числа переменных, алгоритм может оказаться весьма трудоемким и практически непригодным. Это связано с рядом обстоятельств: громоздкостью таблицы, сложностью преобразования & V -+? V & и, в конечном счете, большим числом тупиковых д. н. ф. Б заключение приведем пример функции от четырех переменных, имеющей много тупиковых д. н. ф.
Пример 15. Рассмотрим функцию х2, г#, ж4), где
/(*!. хъ, хг, ^) = Х1ХгХ3Хй V X ,Г 2Г3,Г4.
Очевидно, данная функция является симметрической и ее конъюнктивная нормальпая форма имеет вид
/(а?!, Хг, Х3, Хь) = (г( V .га V х3 V г4) (.т, V х2 V г* V г 4)\
что позволяет сразу выписать ее сокращенную д. н. ф.
Яс — х&г V ХхХ5 V Г(Г4 V .Г 3ХЪ V х2х3 V ХгХ 3 V
V V х2х3 V х3Хь V гдг* V г2Г4 V г3г4.
Отсюда видно, что множество Nf имеет 12 максимальных граней, каждая изщоторых двумерная. На рис. 8 изображено расположение граней. Мы имеем сферу, образованную максимальными гранями. Занумеруем
1 1 \ 3 1
4 5 6 7 8 3 \
10 \ 11 V У 11 |
Рис. 8
Рис. О
грани так, как это указано на том же рисунке. Для анализа неприводимых покрытий удобнее использовать развертку сферы на плоскости (см. рис, 9), при этом нужно
21 с. В. Яблоцскйй
иметь в виду, что левый и правый край (помечены штриховкой) должны быть склеены, и вертикальные отрезки сходятся {показано штриховой линией). На развертке грани делятся на верхний слой 1—3, средний пояс 4—0 и ннжний слой 10—12. Далее идет перебор неприводимых покрытий в зависимости от фрагмента этого покрытия
Рис. 10
Рис. 11
в среднем поясе. Такой перебор учитывает возможность продолжения этого фрагмента в пределах верхнего и нижнего слоя. Особенно важно иметь в виду запреты граней (помечается минусом) и необходимость покрыть некоторые вершины (помечается жирной точкой). Для каждого случая подсчитывается число вариантов но формуле а - Ъ • с, где а — число вариантов в среднем поясе, Ь — в верхнем слое и с — в нижнем слое.
1) Ни одна грань из среднего пояса не взята. Для покрытия помеченных точек (см. рис. 10) необходимо взять целиком верхний и нижний слои: а • Ь • с — 1-1*1 = 1.
2) В среднем поясе взята одна грань 4. Для покрытия помеченных точек (см. рис. 11) необходимо взять грани 2, 3 и 11, 12: а * Ъ * с = 6 • 1 • 1 — 6.
3) В среднем поясе взяты две грани рядом — 4 и 5. Для покрытия помеченных точек (см. рис. 12) необходимо взять грани 3 и 11, 12: а • Ъ - с = 6 • 1 • 1 = 6.
т ш , 1
Шя Шт
Рис. 12
шщ
ш |>1 —1
Щ'пШ
Рис. 13
4) В среднем поясе взяты две грани через одну — 4 и 6. Для покрытия помеченных точек (см. рис. 13) необходимо взять грани 3 и 12: а - Ь с~ 61-1 = 6,
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
823
5) В среднем поясе взяты две грани через две — 4 и 7. Для покрытия помеченных точек (см. рис. 14) необходимо взять грани 2 и 12. Чтобы получить неприводимое покрытие, из верхнего слоя можно взять только одну грань 1 или В. Если выбирается грань 1, то из нижнего слоя (грань 10 запрещена) однозначно добавляется грань 11. Наконец, в случае выбора грани 3 из пижпего слоя (грань 11 запрещена) однозначно добавляется грань 10: С‘6-с = 3‘2-1==6.
1 V/','//.'///Л ?V? 1 ? УУ.'уж. . //: 5 ?}
т ш
10 11 №11?/, У//////АУ,
Рис. 14
ш УУ'/ 7/Ґ.У, ш
О
Рис. 15
6) В среднем поясе взяты три грани через одну — 4, 6 и 8. Для покрытия помеченных точек (см. рис. 15) необходимо взять из верхнего слоя любую грань, например, 1. Тогда из нижнего слоя можно взять любую из двух граней 11 и 12 (грань 10 запрещена): а-Ь*с — = 2-3-2 = 12.
7—8) В среднем поясе взяты три грани, из которых две расположены рядом, а третья идет через одну грань (см. рис. 16 и 17). (Оба варианта симметричны, поэтому достаточно разобрать один из них.)
і ш
Ш III Ш
1 1 тм
Рис. 16
V'/'. ’Щ
і 1
Рис. 17
Для покрытия помеченной точки (см. рпс. 16) необходимо взять грань 12. Чтобы получить неприводимое покрытие, можно взять еще только одну грань из верхнего слоя, а именно 1: а ? Ь • с — 6 • 1 ? 1 = 6.
21*
324 Ч. V. ИСИишша шилилиишп л (шти-шишла
9) В среднем поясе ВЗЯТЫ четыре грани (никакие три из них не идут подряд) — 4,5 и 7,8 (см. рис. 18).
Для получения неприводимого покрытия нужно добавить одну произвольную грань из верхнего слоя, например 1. Тогда из нижнего слоя однозначно возьмется еще одна грань 11 (10 и 12 запрещены):
а-&*с=*3-3-1 = 9.
Всего мы получаем 58 неприводимых покрытий и, следовательно, 58 тупиковых д. н. ф. и из них 6 —минимальных.
§ 6. Некоторые однозначно получаемые д. н. ф.
Процесс построения минимальных д. н. ф., исходя из
совершенной д. н. ф., может быть охарактеризован следующей схемой (см. рис. 19).
1 1
о’’’-- У"'/. у/"КУ'-• 7 \.8
\
о
Рис. 18
Тупиковая
д.н.ф.
Тупиковая
д.н.ф.
Тупиковая
д.н.ф.
Совершенная д.н.ф. '
Тупиковая
д.н.ф.
! минимальны? д.н.ф.
Рис. 19
Сначала получают сокращенную д. н. ф, (при этом на данном шаге возможно усложнение д. п. ф.). Далее однозначный процесс переходит в ветвящийся — процесс построения всех тупиковых д. н. ф. и, наконец, из тупико-
