Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
ГЛ. 1. ДИа'ЫиЛШ'ЛВИНШ ИШ’МАЛЬПЫВ Фи^лиш
бых д. н. ф. выделяются минимальные д. н. ф. Весьма трудоемким звеном этого процесса является построение тупиковых д. н. ф. (ветвящаяся часть). Его можно пытаться упростить за счет двух обстоятельств.
а) Заранее удалить часть членов сокращенной д. н. ф., не участвующих в построении тупиковых д. н. ф., и тем самым сократить перебор (просматривая подмножества оставшейся части сокращенной д. н. ф.).
б) Произвести удаление части членов сокращенной д. н. ф. так, чтобы оставшаяся часть позволяла построить хоть одну минимальную д. н. ф. Желательно при втом, чтобы данный шаг осуществлялся однозначным образом.
В данном параграфе будут приведены построения двух таких однозначно определяемых д. п. ф.
Определение. Максимальная грань относительно множества Nf называется ядровой, если существует такая точка а из Nf, что а ^ Nк и ос не принадлежит никакой другой максимальной (относительно Nf) грани.
Пример 16. Рассмотрим функцию /(ж,, х2, ж*) (см. табл. 8). На рис. 20 изображено множество и максимальные грани — ребра Л^, N2. и N3. Легко видеть, что N1 и N3 являются ядровыми гранями, так как точка (0,0,0) покрыта только Л?1} а (1,1,1)— только N3.
Таблица 8
*1 1
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Определение. Множество всех ядровых граней для называется ядром.
Очевидно, ЧТО В предыдущем Примере N3} является ядром. Легко видеть, что ядро входит в каждое неприводимое покрытие. Отсюда следует, что грани, покрываемые ядром, не принадлежат ни одному из неприводимых покрытий.
326 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Определение. Д. н.ф. йкв, получающаяся из сокращенной путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется д. н. ф. Квайна.
Теорема 4 (Квайн [42]). Для каждой функции f(xlt ..., ?n) (/^'0), существует единственная д. н.ф. Квайна.
Определение д. п. ф. Квайна фактически дает основу для формулировки алгоритма, позволяющего строить д. н. ф. Квайна.
Пример 17. Для функции, заданной табл. 8, имеем сокращенную д. н. ф.
Sic = Х1Х2 V Х2Х3 V XtXz.
Ядро {Nj, N3) (см. с. 325) покрывает грань N2, которой соответствует простая имшшканта x2xs. Таким образом, д. н. ф. Квайна имеет вид
х±х2.
Итак, от сокращенной д. н. ф. путем выбрасывания некоторых импликант возможно перейти к однозначно определенной д. н. ф,— д. н. ф. Квайна, которая реализует ту же функцию и содержит все ее тупиковые д. н. ф.
Следующий шаг в направлении продления однозначной части процесса минимизации связан с определением д. п. ф. типа ET.
Определение. Д. н. ф., соответствующая покрытию множества Nf совокупностью всех таких максимальных граней (относительно N}), которые входят по крайней мере в одно из неприводимых покрытий, называется д. н. ф. типа ET и обозначается 91гг.
Очевидно, д. н. ф. 9?et получается логическим суммированием (т. е. дизъюнкцией) всех тупиковых д. н. ф. функции / и последующим приведением подобных членов.
Как вытекает из определения, для каждой функции f(xu аг„) существует единственная д. в. ф. типа ЁТ, ее реализующая. Она получается из сокращенной д. н. ф. удалением некоторых членов.
Определение. Пусть Nf, тогда совокупность П~ всех максимальных граней (относительно Nf), содержащих точку а, называется пучком, проходящим через а.
Определение. Пусть Nf и NkQ некоторая максимальная грань такая, что Точка а называется
ГЛ. 1. ДИЗЪЮНКТИВНУЮ НОРМАЛЬНЫЕ ФОРМЫ 327
регулярной точкой (относ ителъно дг.^ и д^ если существует точка ре N1 \ и Пр? II-.
Пример 18. Для фу НКцИИ ](хх, х2, ж3) (см. табл. 8 и рис. 20) возьмем в кач^стве точкв а верШИНу (0,0, 1)
и максимальную грань Очевидно, а ^ Лг2. Покажем,
что точка а является Ре1^уЛЯрНОй точкой (относительно
Дг2 и N}). Пусть р-(0,0,Н). Мы имеем: П- = Шг, ЛГЛ, Пг = {Лгх} и * 4 1 г/’
П^с=П~.
Определение^ ^ак^имальная грань NKc, для N1 называется регулярной, еслц каждая ее точка является
гулярнои (относительно 2У- _о и дг \ 1
В нашем примере, оч^°идцо ^ будет регулярной гранью а ^ д N3 не являются регуляр^ьши граням и.
гп. Теорема 5 (К). И. Журавлев
[о]). Для, того чтобы просъая тпли_
канта А. функции /не при
жала О.н.ф. типа 2Т неа*хП!)
достаточно, чтобы соо™е> ю
максимальная грань Дк° §ЬМд рег1/
лярной. р
Доказательство. |опйтлп„„ „ ,г г.0
т * ео сходимость. Пусть К — простая импликанта фув*.пии * ™ м ‘
д.н.ф. типа ЕТ, а ^ции К не принадлежит
не является регулярной »"ЧИВДВВв теоремы.
- * ранью. В таком случае суще-
откует точка «, «Е,У,.,%р не р на обозначим через Р., . .р, ТОЧКЕ пз М1,0:кества ЛГ, \ (см. рис. 21).
X/ \Я к« =% (р, (у.
Рис. 21
По условию
поэтому найдутся грани Л’к?, ..., Лу0, ^ответственно принадлежащие пучкам П
\ П
1
с
такие, что
Рц
к
га^Л'к”-
328 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Очевидно,
N ко и ^ ко и • • • I) лгк0- Л^.
Это покрытие позволяет построить неприводимое покрытие множества ЛУ При этом могут выброситься некоторые из граней N гП, ..., Л' 0, в то же время грань Лгк0 обяаа-
