Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 89

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 83 84 85 86 87 88 < 89 > 90 91 92 93 94 95 .. 104 >> Следующая

К д
тельно войдет в неприводимое покрытие, так как только она одна покрывает точку а. Мы получаем, что входит в некоторую тупиковую д. н. ф. и, следовательно, в д. п. ф. типа 2Т. Полученное противоречие доказывает, что грань Nк0 — регулярна.
Достаточность. Пусть Ау 0— регулярная грань, докажем, что К° не принадлежит д. н. ф. типа 2Т.
Обозначим через аь ..., а< точки из множества N к<и т. е.
„ {а31 ..ж).
В Силу регулярности Мка найдутся точки р,, ..р( из Nf \ Лу0 такие, что
П-^єП- ПГ,?=Пг;.
а1
00
Возьмем произвольную тупиковую Д. II. ф. 31 функции / и соответствующее ей неприводимое покрытие. Это покрытие
Рис. 22
очевидно, покрывает точки {К, ..., р( соответственно гранями » Лу
(см. рпс. 22). В силу включений (*), эти же грани покрывают точки аи ..., а(, т. е.
и ? * ? У ^У э N к0.
Поэтому грань Луо не принадлежит данному неприводимому покрытию, а простая имшшканта К° — д. н. ф. 91. Теорема полностью доказана.
Данная теорема дает основу для формулировки алгоритма, позволяющего строить д. и. ф. типа 2Т: необходимо из сокращенной д. п.ф. выбросить все конъюнкции, соответствующие регулярным граням.
ГЛ. t. ДНЗЪГОТТКТПСIILIE НОРМАЛЬНЫЕ ФОРМЫ 820
Пример 19. Для функции }(хих2,х3) (см. табл. 8), как видно из предыдущего, имеется одна регулярная грань Л72. Выбросив ее, получим Л', и Л7Э, что дает д. н. ф. Е^гт, совпадающую с единственной тупиковой д. н. ф. этой функции.
Таблица 9
*1 К* *4 { ! х< X, X, *4 1
0 0 0 0 0 1 0 1 1 1 0 1
0 0 0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 1 1 0 0 1 0 1
0 0 1 0 0 I 1 1 0 0 0 1
0 0 1 1 0 1 ! 1 0 1 0 1
0 1 0 0 1 І на оста лькых наборах 0
0 1 1 0 0 1
Возникает вопрос о соотношении д. н. ф. Квапна и д. н. ф. типа ST.
Теорема 6. Д.н.ф. 91ЇТ функции ] получается на
д.н.ф. Квайна 9ЇКВ той же функции путем, быть может, выбрасывания некоторых простых импликант.
№70) (70010) (00010) (00110) (01110)

Щх^х5 Щ Х3 Х5'
(11000) (10000) (00000) (О0100) (01100)
(00001) лу х} х^ xs
L (01001) Рис. 23
Доказательство вытекает пз очевидного факта: каждая максимальная грань, которая поглощается ядром, является регулярной.
Следующий пример показывает, что д. н. ф. 91^ может быть проще, чем Д. Н. ф. №кв.
Пример 20. Возьмем функцию ]{хи х2, х3, х4, г?) (см. табл. 9). На рис. 23 представлено расположение мак-
330 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
симальных граней для Л7/, состоящее из четырех квадратов п двух ребер. Мы имеем для данной функции сокращенную д. н. ф.
91с — tfi.T3.T5 V хгХъХь V х jtf 5 V х&ъХъ V х iXzxЗх4 V XiXsx4я5. Ребро является регулярной гранью, остальные
Рис. 24
грани, очевидно, не будут регулярными, поэтому
31ЕТ = х&ъх5 V ^2.гэ5ь \ хухгхъ Vх^ХзХц V х^зх^х*. В то же время, так как ядро, состояхцее из граней
ЛГ - - , Л7- - V--- ,
*1>’3Х5 *1*Я*5’ *?зс1***4хь’
не покрывает ни одной из максимальных граней, то
= 31с ^
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 331
Таким образом, теперь процесс минимизации можно охарактеризовать схемой (см. рис. 24). Здесь ветвящийся процесс начинается после построения д. н. ф. $1Т. Дальнейшее продолжение однозначной ветви процесса минимизации, разумеется, возможно. Например, можно дойти до д. н. ф. типа 2М (сумма минимальных д. п. ф. с последующим приведением подобных членов). Однако, как мы увидим ниже, это ведет к значительному усложнению алгоритма.
§ 7. Понятие локального алгоритма
Алгоритмы построения д. п. ф. $кв и д. п. ф. обладают определенной спецификой. Они базируются на специальном изучении покрытия IV} системой всех максимальных граней, в результате которого накапливается определенная информация о каждой максимальной грани. Например, выясняется, является ли грань Nк0 ядровой (входит в каждое неприводимое покрытие) или нет; выясняется, является ли грань Ага0 регулярной (не входит ни в одно неприводимое покрытие) или нет. Опираясь на эту информацию, далее осуществляется удаление некоторых максимальных граней. Например, в одном случае — покрываемых ядром, в другом случае — регулярных граней.
Для обобщения данных алгоритмов существенную роль играет понятие окрестности порядка и данной максимальной грани Л^о множества
Определение (индуктивное). Мпожество = называется окрестностью порядка 0 максималь-
ной грани АГя0. Пусть определены окрестности порядков О, 1, ..., и — 1 максимальной грани №ко-Тогда окрестность.
(Л^о} порядка и максимальной грани Nк0 определяется как множество всех максимальных граней из Л7/, имеющих непустое пересечение с гранями из Зи-\(^ке) Очевидно, что
*0 (^К°) “ *^1 (*«.) — ? • • — (-Л'яо) — ? • '
Пример 21. Возьмем функцию, заданную табл. 1, II В качестве К0 КОНЪЮНКЦИЮ (см. рис. 6).
332 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Тогда
“ 1^-цЬ
(лг^х2) “ {^^2 ’ Лх273’ ЛГ,А. ЛГ^]. (ЛГ;1*2 ) =“ ^х, • ^Х»' ^ггх,* Лх^з> ЛГх21'з’ 5«№а)-5*(Щ' “>3-
Здесь
*. (-\;г) <= *1 <= «. (^!,0 с 5° №,0 “
- *« №Л) ” • • •
Обозначим через и0 минимальных! порядок окрестности такой, что
^и0+] (Л^о) “ 5Ыо (Л^).
Легко видеть (см. также предыдущий пример), что
ЗДАко^МЛ!к о)<= ... с 5«0(№к.)-
Предыдущая << 1 .. 83 84 85 86 87 88 < 89 > 90 91 92 93 94 95 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed