С.В. Яблонский - Введение в дискретную математику (1060464), страница 48
Текст из файла (страница 48)
и. ф. типа ХТ: необходимо ив сокращенной д, и. ф. выбросить все конъюнкции, соответствующие регулярным граням, гл. ь дпзъкипгтнппык погмлльпыг. богаты 222 Прпмер $9. Для функции г'(хихьх,) (см. табл. 8), как видно пз предыдущего, имеется одна регулярная грань У,, Выбросив ес, получим Ж, 0 Ж„что дает д. и.ф. Э4т, совпадающую с едпиствсвпой тупиковой д. и. ф. этой фуикцпп. Таблица 9 Возппкает вопрос о соотиошеппп д.я.ф. Квайпа и д.и.ф. тнпа ХТ.
Теорема 6. Д. и.ф. 24т фанкиии 1 получается иа д. н. ф, Квойно Я„з той же фанкбии путели быть может, выбрасывания некоторых простых иыпяикант. дтата) аааю) (пюшш испи (аяи) аа~ МИЛ (ааааа Мв вв ав ыяю Рис. 23 Доказательство вытекает пз очевидиого факта: каждая максимальная грань, которая поглощается ядром, является регулярной. Следующий прпмер показывает, что д.
п. ф. Изт может быть проще, чем д. и. ф. Явз. П р и м е р 20. Воаьмем функцию 1(хо хм хи хи х,) (см. табл. 9). На рис. 23 представлено расположение мак- 330 ч. т. Пекотогые НРпложепия к кивеРнетпке симальнык граней для Уь состоящее иэ четырех квадратов и двух ребер, Мы имеем для данной функции сокращенную д. н.
ф. Вх хзУзйз ЧУзУхтз ЧУ Узйз ЧУХ х, ЧУхзУзйз Чх,х х,х. Ребро зз'---- является регулярной гранью остальные Х1ХЗЗЗХЗ Рвс. 24 грани, очевидно, не будут регулярными, поэтому Яхт хзхзхз Ч хзхзхз Ч хзхзх ° Ч У~хзУз Ч УзУзУзхз. В то же время, так как ядро, состоящее иэ граней зу - -, йз- хзхзхзз хзхзхм хзззхзхзз не покрывает ни одной иэ максимальные граней, то Вке - Вх ть язт. 1л.
1. дпзъюиктивныв пОРИАльнык ФОРмы 331 Таким образом, теперь процесс минимизации можно охарактеризовать схемой (см. рис. 24). Здесь ветвящийся процесс начинается после построения д. н.ф. 34т. Дальнейшее продолжение однозначной ветви процесса минимизации, разумеется, возможно. Например, можно дойти до д. н. ф. типа ХМ (сумма минимальных д. н. ф. с последующим приведением подобных членов). Однако, как мы увидим ниже, зто ведет к значительному усложнению алгоритма.
$ 7. Понятие локального алгоритма Алгоритмы построения д. н. ф. Ивз и д. н. ф. 34т обладают определенной спецификой. Они базируются на специальном изучении покрытия У1 системой всех максимальных граней, в результате которого накапливается определенная информация о каждой максимальной грани. Например, выясняется, является ли грань Уке ядровой (входит в каждое неприводимое покрытие) или нет; вы- ЯснЯетсЯ, Явлнетса ли гРань АГл, РегУлЯРной (не входит ни в одно неприводимое покрытие) или нет. Опираясь на зту информацию, далее осуществляется удаление некоторых максимальных граней. Например, в одном случае— покрываемых ядром, в другом случае †. регулярных граней. Для обобщения данных алгоритмов существенную роль играет понятие окрестности порядка и данной максимальной грани Жлз множества Уо О п Р е Д е л е н и е (инДУктивное). Множество Бе(1тле) (1т е) называется окресгиосгью порядка 0 максимальной грани Арлю Пусть определены окрестности порядков О, 1, ..., и — 1 максимальной грани Уиз.Тогда окрестность.
8, (Улз) порядка и максимальной грани Л е определяется как множество всех максимальных граней из Уь имеющих непустое пересечение с гранями на Я 1(1тлз) Очевидно, что 8 (Я )с:;Я (11' )с= ., с=Я ()т )с- Пример 21. Возьмем функцию, заданную табл. 1, и в качестве К' конъюнкцию л,х, (см. рис.
6). 333 ч. ч, некОтОРые пРнложения к кивеРнетпке Тогда Оо(1тй;)- (У-- ( (у--, м- —, ттх1ха ' хвхв' х1хз ' (йГ- —, К--, Ч-, )Ч -, 1Ух, 1, 1хв ' хаза™Рв' х1ха' "аха)' 1У--, У- -, У-, Х -, М, У !,х1хо ~ хахв' «1ха1 х ха хаза~ х х )О гв(У„„), и>З. Здесь ~О()У;айа) «= ~1 (й';,ха) ~= ~а(Л'х- х-) ~= ~в(Л1;.; )- я (йг„- й ) Обоаначим через и, минимальный порядок окрестности такой, что 8хо+1(го~ко) Охо (давка) Легко видеть (см. также предыдущий пример), что ЮО()улв) ~~1(ХКО) ~= "~=8.О("Ко)- ~аз+1 (~ КО) хха ~в1 ~ )хХΠ— сокращенная д.
н. ф. функции (, а й~~, () ... () л'~, — покрытие (максимальнымн 1ранями) множества У,. причем каждая окрестность порядка и (и ) 0) содержит по крайней мере одну точку, не входящу1о в окрестность порядка и — 1, если и~и,-1. Отсюда и. 2". Зафиксируем теперь параметр и и будем изучать покрытие множества У, на основе сведений об ее окрестностях порядка и. Это изучение аналогично попыткам составления плана местности на основе сведений об участках местности, которые человек видит из определенных ее точек. Наши рассмотрения мы начнем с примера, который пояснит смысл локального изучения покрытий.
Пусть Гл. ь дизъюнктивные нОРмальные ФОРмы 333 Определение. Грани гзг э и Лг э называготся свяэКз К1 ными, если существует такое и, что йг эеня (йг э). к~ ~ кг/ Легко видеть, что множество всех граней (йгк,) одноаначным образом разбивается на связные компоненты, т. е. на такие подмножества, в которых каждая пара граней связна, а грани из разных подмножеств не связны. Возникает вопрос, как для произвольной грани Лг э найти компоненту связности, которой она принадлежит. Отметим коныопкциго К" и начнем просмотр коньюнкций в порядке их следования в сокращенной д.
н. ф. Если )«'кэ ан Яг ~Х э'1, то отмечаем конъюнкцию Кэ Кз! м если гзгкэ ФЮг()р э), то конъюнкцию не отмечаем. Затеи Кг! переходим к К', Конъюнкцию К,' отмечаем тогда и только тогда, когда яг(йг э) содержит грани для отмеченных Кэ / конъюнкций, и т. д. В результате этого мы просмотрим всю сокращенную д. н. ф.
и отметим некоторые конъюнкции, Затем начинаем просмотр сокращенной д. н.ф. повторно. Если при этом множество отмеченных конъюнкций возрастает, то начинаем следующий просмотр сокращенной д. н. ф., и т. д. Мы придем к случаю, когда очередной просмотр (а их меньше гп) не увеличит множества отмеченных конъюнкций, тогда выбрасываем все неотмеченные конъюнкции и процесс заканчивается.
Оставшееся множество коныонкцнй и дает искомуго компоненту связности. Мы видим, что сначала идет изучение покрытия при помощи окрестностей г-го порядка, и на основе него делаются отметки копыонкций. Последнее означает, что каждая конъюнкция снабжается одной ячейкой памяти с двумя состояниями (отметки «нет» и отметка «естьэ). Кроме того, нужна еще одна ячейка для выяснения, увеличивает ли очередной просмотр число отметок или пег. В качестве второго параметра возьмем число о — число допустимых ячеек двоичной памяти для каждой конъюнкции.
Фиксируем параметр о. Теперь перейдем к описанию локальных алгоритмов «) [6) над покрытиями максимальными гранями с параметрами и и и. Работа алгоритма разбивается на два этапа. ° ) Здесь мы даем несколько другой заразят этого аовятяя. 334 ч. и. »<екотогыя пгпло<кеш<я к кпввгпгт<!ке 1. Изучение покрытия. В определенном порядке прос»штрпвают сокращенную д. н. ф. и на основе того, что попадает в окрестность Я~(Кк») конъюнкции К', т. е. части сокращенной д. н. ф. и информации, накопленной для копък<пкций из этой окрестности, вычисля<от новые значения т«,, ..., у» ячеек памяти для К". Ирп этом требуется, чтобы это вычисление выполнялось одинаково для любых двух д. н.ф., имеющих конъ<оккцп<о К' и таких, что у них окрестности конъюнкции К' совпадают и яме<от одинаковые значения ячеек памяти для конъ<онкций пз данной окрестности (локальность накопления информации).
При выполнении определенных требований процесс накопления информации оказывается «сходящи»<ся» и тем самым »<ожет быть окончен. В этих случаях мы получаем финальную информацию, аадаваемую значениями ячеек памяти для конъюнкций из сокращенной д. н. ф. 11. Принятие решения. По вычисленным значениям ячеек памяти конъюнкций из Я„(Кк«) определяют возмоя<ность удаления конъ<опкции К'. Эта процедура также осуществляется локальным образом, т.
е. одинакова для любых двух д. н. ф., содеря<ащих К', у которых окрестности К' совпадают и нме<от одинаковые значения ячеек памяти для конъюнкций нз атой окрестности. Легко видеть, что сформулированный выше алгоритм для нахожденвя в сокращенной д.н.ф. компоненты связности, содержащей данную конъюнкцию К', является локальным алгоритмом с параметрами и-1, и=1. В дальнейшем будем предполагать, что 1 такова, что покрытие множества Ж! совокупностью всех ее максимальных граней образует связную компоненту. В противном случае задача минимизации с использованием локальных алгоритмов решается независимо для каждой связной компоненты в отдельности.
Пусть ~(х„ ..., х„) обладает указанным свойством. Нетрудно видеть, что существует локальный алгоритм с параметрами и = 1, и = 2", который позволяет строить минимальную д. н. ф. 1 э т а п. Сопоставим взаимно однозначным образом наборы (а„..., «„) с числами па множества И, 2, ..., 2"): (а„.. ч а.) <(с<„..., а„).
Наядой конъ|опкцпн К' пз сокращенной д. н.ф. для 1 гл. 1, диуьюнктивные нОРмАльные ФОРмы 335 сопоставляем двоичный кортеж (у~ " у;.) где у«1„1 „„) 1 тогда и только тогда, когда К»~ие ... ..., ег„) 1. Очевидно, ф,..., у«„) будет «кодом» грани К'. Затем идет изучение покрытия при помощи окрестностей 1-го порядка, и новые значения (у», ..., у«„) для К' вычисляются как покомпонентные дизъюнкции кортежей для данной окрестности. Этот процесс приведет к тому, что для каждой конъюнкции сокращенной д. н. ф. Мы вычислим двоичный кортеж н он будет одним и тем же для всех конъюнкций — «кодом» функции (например, столбцом, определяющим ее в таблице).
11 этап. Решающее правило определим так: возьмем произвольную минимальную д.н.ф. для ~ и данную коньюнкцию выбрасываем тогда и только тогда, когда она не входит в минимальную д. н. ф. Очевидно, данное решающее правило удовлетворяет требованию локальности и приводит нас к минимальной д. н, ф. Данное обстоятельство означает, что в локальных алгоритмах необходимо вводить ограничения на объем допустимой памяти и. В заключение этого параграфа покажем, что алгоритм Квайна и алгоритм построения д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
