Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
- П/«)/т(/»)-0.
Последнее заставляет думать, что статистические соображения вряд ли что дают для алгоритма упрощения,
§ 3. Постановка задачи в геометрической форме
Обозначим через Еп множество всех наборов (оіі, ..с?п) из 0 и 1. Его можно рассматривать как множество всех вершин единичного «-мерного куба. Поскольку никаких других, кроме упомянутых, точек мы не рассматриваем, постольку множество Еп будем называть «-мерным кубом, а наборы (сгь ..., ап)~~ вершинами: куба. На рисунках 1—4 изображены проекции, соответственно, 3-мерного, 4-мерного, 5-мерного и 6-мерного кубов на плоскость (на рис. 4 вершины — не наборы, а соответствующие им натуральные числа (см. стр. 10)).
Определение. Пусть Сті, Оі2, ..., Оіг — фиксированная система чисел из 0 и 1 такая, что К и < і2 < ... ...< и^п. Множество всех вершин (ощ а2, ап) жгуба Еп таких, что
называется (« — г)-мерной гранью.
Очевидно, что (п — г)-мерная грань является (п — г)-мерным подкубом куба Еп.
90*
808 ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Пусть 1(хи х2, хп)—произвольная функция алгебры логики. Сопоставим ей подмножество вершип ку-
ба Еп так, что
.(«и е N^
тогда и только тогда, когда
/(«1, Сба, ..., а„) = 1.
Ясно, ЧТО ПО подмножеству исходная функция восстанавливается однозначным образом.
Пример 5. Функции /(я,, х2, а:3), заданной табл, 4, соответствует множество
№, = {(0,0,0), (1,0,0), (1, О, 1), (1, 1,0), (1, 1, 1)),
изображенное на рис. 5.
Возьмем в качестве исходной функции элементарную конъюнкцию К(х 1, ..?„) ранга г, где
К (х1 ?п) =* ? &Х1Г»
Легко видеть, что множество Агя, соответствующее конъюнкции К, представляет собой (п — г) -мерную грань.
Таблица 4
*1 *2 *9 /(Хц хг ж,) X, ж, *1
0 0 0 1 1 0 0 \
0 0 1 0 1 0 1 1
0 1 0 0 1 i 0 1
0 1 1 0 1 1 1 1
Число г будем называть также рангом этой грани. Пример 6. Конъюнкциям
К-1 (дч* х2, — х2 & д,'*,
Кг (ДЧ, Х2, Х3 ) — Хл & X г, К3{х 1, х2, х2) = Хх
Рис. 1
Fiic. 2
Рис. З
310
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Рис. 4
соответствуют грани
лгкг{(0.0-0М1.0.0)}.
ЛЧ = «1.1 0, 0), (1, 0, 1)},
Лгк3={(1, 0, 0), (1,0, 1), (1,1,0), (1,1,1)},
имеющие соответственно ранги 2, 2 и 1. Эти грани являются соответственно (см. рис. 5) одномерной гранью (ребром), одномерной гранью (ребром) и двумерной гранью.
Отметим очевидные свойства введенного соответствия Если
то:
/(*^11 ? • *) ^п) ?? (*^1| • ? •) *^п) V }х (д?!, ..д:«)',
1) N^N„N^N,1
2) А7,=Атг[}Л\.
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 311
И частности, если функция 1(хи ..., #„)’ обладает д. и. ф. 9?, где
т. е. образ конъюнкции Ки принадлежащей д. н. ф. функ-
покрытию множества N1 гранями,
расположенными внутри множества Л^, соответствует д. п. ф. 9} функции /.
Пример 7. Мы видели, что
91! *= Х1Х2Хв V ХАХгХл V Х1Х2Х3 V Х1Х2Хг V Х&гХ^
= Х2Хз V Х1
являются д. н. ф. функции /(^, хг, а:а) (см. табл. 1). Этим д. н. ф. соответствуют два покрытия множества Лтд
Одно из этих покрытий — точечное, второе покрытие состоит из ребра и двумерной грани.
9І = Я, У ..УК,,
то из указанных свойств вытекает, что
Нетрудно видеть, что справедливо и обратное утверждение: всякому
Рис. 5
где
М2 ч. У. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Пусть ъ обозначает ранг грани А^ (он равен рангу конъюнкции К%\' Число г, где
5
\1 г-г = 4л гг
г—1
будем называть рангом покрытия. Теперь мы можем дать формулировку геометрической задачи (задачи о покрытии), эквивалентной задаче о минимизации булевой функции: найти для данного множества N} такое покрытие гранями, принадлежащими А^,
N^ = Мкх I) Атк2 I) ? • ? II ^ка%"
чтобы его ранг г был наименьшим.
Таким образом, можно считать, что задача о минимизации булевой функции имеет две постановки. Одна — в аналитической форме (исходная), вторая — в геометрической форме (задача о покрытии). Б связи с этим употребляются два языка: аналитический и геометрический. В ряде случаев используется также комбинированный язык, в котором, например, конъюнкции «называются» гранями, а д. н. ф. — покрытиями.
§ 4. Сокращенная д. и. ф.
Определение. Грань А^, содержащаяся в называется максимальной (относительно А^), если не существует грани Лтк' такой, что:
1. Лтж е ^ Лг/;
2. Размерность грани больше размерности
гранп Мк.
Пример 8. Пусть /(#!, х2, ж3) — функция, заданная
табл. 1, и
$-1 *^2) *Гз) & #5,
?^2(^11 ^21 *?з) = %1 & ^2»
К&{х 1, #2, %:) = #1*
Тогда грани Nк1 в ЬтКз (см. рис. 5) являются максимальными, а грань #к2 не максимальная для Л^, так как с= Лгк3 и размерность 1УКз больше размерности Л^, Определение. Конъюнкция К, соответствующая максимальной грани Л'к множества Л''/, называется простой импликантой функции /.
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
313
Так как условие /Ук ^ №к> эквивалентно тому, что все множители из К' содержатся в Л”, то в определенном смысле из простой импликанты К функции / нельзя удалить ни одного множителя, иначе мы получим (после удаления множителя) конъюнкцию К\ для которой ЛГк.&Щ.
Отметим очевиДпое утверждение: каждую грань NKt Р!К^А7}, можно расширить до максимальной грапи.
