С.В. Яблонский - Введение в дискретную математику (1060464), страница 45
Текст из файла (страница 45)
Следовательно, число проверок ие болев Х Е в (К1) + 21 л (Я') ~', (л + 2) 2". 1 1 Общее число вариантов упорядочения, как это следует из замечания, равно (н1)' и (н1)а в~(н[)з" ~(нл) ~21 ль1вл» Таким образом, число проверок для всех вариантов не более, чем 2злл 1ов л 3 что значительно меньше, чем21", т. е. этот алгоритм лучше, чем алгоритм перебора всех д.
н. ф. В то же время трудоемкость алгоритма с испольаованпем процедуры упрощений остается весьма зиачктельной. Остается обсудить еще одну возмон1пость, влияющую на эффективность алгоритма — случайность выбора упорядочения, играющую роль при решении серии задач на минимизацию булевых функций. Разобьем все вышеуказанные упорядочения на вблагоприятныез и внеблагоприятные», смотря ~о тому, дает или нет алгоритм упро- гл. 1. длзъю1п1тнвнын нОРмлльнык ФОРмы 3О7 щения минимальную д. н. ф. Тогда отношение числа благоприятных упорядочений к числу всех рассматриваемых упорядочений равно вероятности построения минимальной д.
н. ф. при случайном выборе порядка. Можно было бы попытаться оценить это отношение. Однако мы не будем этого делать ввиду того, что данная величина связана с конкретным алгорптмом, и ее оценка мало что будет говорить о трудоемкости других алгоритмов, Вместо этого мы возьмем в качестве меры трудоемкости алгоритма родственную характеристику — отношение числа )1Щ минимальных д. п. ф.
функции ) к числу т(1) ее тупиковых д.н.ф., т, е. величину 11(/)/т(~). Оказывается, что сущестзу1от функции с большим числом тупиковых д. н. ф. при относительно малом числе минимальных д. н. ф. Можно показать, что существует последовательность функций (1 ), для которой (2) )1(1.)й (1 ) О. Последнее ааставляет думать, что статистические сообра- женяя вряд ли что дают для алгоритма упрощения. $ 3. Постановка задачи в геометрической форме Обозначим через Е" 11по>кество всех наборов (а„ ..., а„) из О и 1. Его поясно рассматривать как множество всех вершин единичного и-мерпого куба. Поскольку никаких других, кроме упомянутых, точек мы не рассматриваем, постольку мпожество Е" будем называть п-мерным кубом, а наборы (а„..., а„) — вершинами куба. На рисунках 1 — 4 изобрангепы проекции, соответственно, З-мерного, 4-мерного, 5-мерного и б-мерного кубов на плоскость (на рис.
4 вершины — не наборы, а соответствующие им натуральные числа (см. стр. 10)). Определение. Пусть о,, о1,, ..., о1,— фиксированная система чисел из О и 1 такая, что 1< 1,(11(... ... ( 1, ~ и. Множество всех вершин (а„а,, ..., а ) куба Е" таких, что а;, о...а,,=о1,, ...,а,„о1,, называется (н — т) -мерной гранью. Очевидно, что (и — г)-мерная грань является (л — г)- мерным подкубом куба Е". боб ч. 7.
некОтОРые пРкложения к киееРнетике Пусть у(хо х„..., х„]-произвольная функция алгебры логики. Сопоставим ей подмножество У~ вершин куба Е" так, что (а„пв, „а )ж Уг тогда и только тогда, когда 1(ан па, ..., а„) 1. Ясно, что по подмножеству Уг исходная функция восстанавливается однозначным образом. Пример 5. Функции Дхо х„ х,), заданной табл. 4, соответствует множество )У, - ((О, О, О), (1, О, О), (1, О, 1), (1, 1, О), (1, 1, 1)), изображенное на рис.
5. Рнс. 1 Возьмем в качестве исходной функции влементарную конъюнкцию К(хо ..., х.) ранга г, где вг вв К (х„ ..., х„) х<, л, ... йх,в, Легко видеть, что множество Уа, соответствующее конъюнкции К, представляет собой (я — г)-мерную грань. Таблнав 4 Число г будем называть также рангом этой грани.
Пример 6. Конъюнкциям К,(х„х„х,) хатха, К, (х„хз, хв) = х, А х „ Кв (хо хвз М ~ хв 310 ч. ч некОтОРые ПРичожения к кнвеРнетикн соответствуют грани Фн, — ((О, О, О), (1, О, О)), йг1г, ((1, О, О), (1, О, 1)), Ила ((1,0,0), (1,0,1), (1,1,0), (1, 1,1)), имеющие соответственно ранги 2, 2 и 1. Этн грани являются соответственно (см.
рис. 5) одномерной гранью (ребром), одномерной гранью (ребром) и двумерной гранью. Отметим очевидныо свойства введенного соответствия 1 Уь Если Дхо ..., х„) я(хо ..., х„)11Ь(х„..., х„), Гл. 1. дизъюнктнвные ЕОРмАльные ФОРмы вц В частности, если функция 7'(хо ..., х„'1 обладает д. к. ф.
Я, где Я-К,Ч...ЧК„ то из указанных свойств вытекает, что йгк1 с- Хг (1 = 1, 2, ..., г), т. е. образ конъюнкции Кь принадлежащей д. н. ф. функцпп 1, является гранью, расположен- х ной внутри множества Х„и )У1- Л1К1 () йГКз () . 0 й1К,1 т.
е. д. н.ф. функции Г соответствует покрытие множества У, гранями 1'1'К1, ..., Ук,. з Нетрудно видеть, что справедливо и обратное утверждение: всякому Ркс. а покрытию множества й1, гранями, расположенными внутри множества 1111, соответствует д.н.ф. Я функции 1. Пример 7. Мы видели, что й1, х,хьт, Ч х,х т, Ч х,х,х, Ч х,х,х, Чх,х,х„ Из=к,хзЧх, являются д. н. ф. Функции 1(хо хм х,) (см. табл. 1). Этим д. н. ф.
соответствуют два покрытия множества 11',: й11 )ук () )пк () 1укз () й1к (~ )укы )у/-)у з())у 11 кз где ~'к, - ((О, О, О)), ~'к, - ((1, О, 0))1 Л'к, = ((1, 0 1)), 1г к = ((1, 1, 0)) й7» — ((1, 1, 1)), У „ — ((О, О, 0), (1, О, 0)), ! У, = ((1, О, 0), (1, О, 1), (1, 1, 0), (1, 1, 1)). Одно из зтпх покрытий — точечное, второе покрытие состоят из ребра и двумерной грани. 312 ч. у. ВекотоРые ПРиложенкя 11 к вегивтике Пусть г, обозначает ранг грани Мкг (ок равен рангу кокъгоикции Кг). Число т, где г =Х т1$ будем называть рангом покрытия.
Теперь мы можем дать формулировку геометрической задачи (задачи о покрытпп), эквивалентной задаче о мииимиаации булевой функции: найти для данного множества У, таков покрытие гранями, принадлежащими Кн ~1- ~к, () ~лг () " () ~к чтобы его ранг г был каимееыппм. Таким образом, мо1кко считать, что задача о мииимизации булевой функции имеет две постановки. Одна— в аналитической форме (исходиая), вторая — в геометрической форме (задача о покрытии). В связи с этим употребляются два языка: аналитический и геометрический.
В ряде случаев используется также комбинировавный язык, в котором, например, коиъювкции «яазываютсяг гранями, а д. и. ф. — покрытиями. 3 4. Сокращенная д. и. ф. Определение. Грань У», содержащаяся в Р«'и называется максимальной (откосительео У,), если ие существует грани Ук такой, что: $. г"т'к ~ Фк ~ Ы Жд 2. Размерность грани Ук. больше раамерпости грани У».
Пример 8. Пусть 1(хо хм х,) — Функция, заданная табл. 1, и Х (хь х«хз) = х«8г ха К,(х„х„х,) = х, бгх«, К, (х„х„х,) Тогда грани Ук, иск«(см. рис. 5) являются максимальными, а гравь Мкг ие максимальная для Ун так как Укг~ Л'кз и РазмеРность РРЕ« больше РазмеРности Фк. О п р е д е л е к и е. Конъюнкция К, соответствующая максимальеой гРани У, множества Уь называетсЯ пРостой илпликантой функции 1.
гл. $. дизъюнктивные нОРмАльные ФОРмы 313 Так как условие ггкс:-ук зквивалеитио тому, что все множители из К' содержатся в К, то в определенном смысле из простой иьшлпканты К функции Г' нельзя удалить ни одного множителя, иначе мы получим (после удаления множителя) коиъюнкцпю К', для которой 'гк (~"-йгь Отметим очевидное утверждение: каждую грапь Кю ӄ— Уь можно расширить до максимальной грани.
Пусть Х О Л ''' У О к,' к,' ''' к,„ — список всех максимальных граней множества Уо Нетрудно впдеть, что )у,=йг,()й „() ...()й „, к, кз ''' к,„' так как У „с=У~(~ 1, ..., т) и каждая точка из У~ и< принадлежит некоторой максимальной гранп. Последнее равенство зквпвалектно следующему: Кп~Кп~ ~Ко Определение. Д.н.ф., являющаяся дпзъюнкцпсй всех простых лмпликант функции (, называется сокращен- ной д.
и. ф, Итак, р(с = К, "Ч К"., Ч ... ~~ К,"„ есть сокращенная д. н. ф. функции 1. Как зто вытекает пз предыдущих рассмотрений, она однозначно определяется по функции г' и реалкзует функцпю ~. Пример 9. Для фуикцпи ~, задапвой табл. 4, имеем следующее покрытие, состоящее пз всех максимальных граней (см. пример 6) йг,-)ук, )) укз. Ему соответствует сокращенная д. и. ф. 3)с = хз Й х, ~/ х,. Геометрический подход вместе с тем дает и способ построепия сокращеиной д. и. ф. Одвако желательно иметь также и аналитическое решение, 3$4 Ч.
Ч. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИВЕРНЕТИКИ Алгоритм построения сокращенной д. н. ф. Воаьмем для функции Дх„..., х„) любую конъюнктивную нормальную форму (например, совершенную к. н. ф.). Затем проиаводим раскрытие скобок, т. е. преобразование типа б»Ч- Чд». После этого в полученном выражении удаляем нулевые члены и ликвидируем поглощаемые и дублирующие члены, т. е.
совершаем преобразования вида К»К, Ч К» К„ Е»ЧЕ»-Е». В результате этого мы придем к сокращенной д. н. ф. е» Действительно, иа любой простой импликантых, 8,... 1 е~ ... 8»х, функции 1 в каждую диаъюнкцию исходной 3' конъюнктивной нормальной формы должен входить хотя бы один ив членов х~,', ..., х~„" (иначе, положив х» О„ ..., х», п„мы обратили бы в нуль все члены видах,, ..., х,,а ватам смогли бы подобрать значения остальных переменных так, чтобы некоторая дизъюнкция, не содержащая х,, ..., х, ~то»ке обратилась бы в нуль; но тогда ва этом наборе значений переменных х„..., х„функция ~ обратилась бы в нуль, а простая импликанта х, Ь ...
Ь х, обратилась бы в единицу, что невоаможно). Поэтому после раскрытия скобок будут получены все простые пмпликанты (конъюнкции, не содержащие части сомножителей, получиться не могут, так как соответствующие им грани уже не содержатся в А»», т. е. каждая такая конъюнкция хотя бы в одном случае равна единице, когда функция 1 равна нулю).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
