Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 10

При эхом если множества М1, Мг,..., М„независимые, т. е. все конституенты отличны от пустого множества, то число различных канституент равно 2", и число множеств, об(газованных из этих конституент в виде их объединения, равно 2г (с учетом пустого множества). Введение понятия копституенты позволяет задавать множество М при фиксированных независимых подмножествах М1, Мг, ... ..., М„универсальнога множества 1 в зиле объединения конституент: М = 0 Г'г М,'*'. У 1~1 Каждое фиисираванное множество М; С 1 разбивает пространство на две части: на собственно М; и на М;. При независимых множествах М; б (М;/ 1 = 1, ..., пу пространство разбивается на 2 х 2 х ... х 2 = 2" областей.

Каждая область является перегг рвз сечением и множеств Мг или М;, 1 = 1, ..., и. Сопоставим этой области двоичный вектор (о1, ггг, ..., гг„), в котором ог = 1, если в пересечение С = () М; ' входит М;, и ггг = О, если входит М;, а 1 также десятичный эквивалент и д(С) = ~~1 а; 2' 1. Любое множество М в пространстве 1 можно запать в виде объединения этих областей. Сопоставим множеству М двоичный вектор длины 2", в котором 1-му разряду соответствует область с десятичным эквивалентом, равным 1. Веитор, опрелеляюший множество, представим в виде десятичного эквивалента: г"-1 д(М)= ~~г с; 2', с;=0,1.

гма Следовательно, множество М в пространстве может быть задано в виде соответствуюшего десятичного эививалента. 51 Гл. 1. Основы мноеосорзяныт множесзяе 50 11.6. Аксиомотико теории мнозсесте Рассмотрим, например, в трехмерном пространстве 1 = (Мг, Мг, Мз) множество М(М1, Мг, Мз) с десятичным эквивалентом а(М) = 217.

Имеем 212 = 1.2т+1.2в+0.28+1.24+1.2з+0.22+0.2'+1.2о Множеству М соответствует двоичный вектор (1, 1, О, 1, 1, О, О, 1), определяющий включение областей в множество М (рис. 1.18, а). Кроме диаграммы Эйлера, пространство может быть задано в виде гиперкуба или н-мерного куба (н — размерность простран- ства, равная числу фиксированных множеств). Гиперкубом (н-мерным кубом) называется граф Н, каждан вершина которого взаимно однозначно соответствует области про- странства, и две вершины соединены ребром, если они соответ- вгг11, 3> Рз(1 ыо 11, 3, 4) 100 вуз< (3, 4, Я И 12, 4,31 Рцс.

1.18 ствуют соседним областям (имеющим общую границу). Сопоставленные этим областям двоичные векторы отличаются в одном и только одном разряде. Гцверкуб для рассматриваемого врлыера ззобрааея на рцс. 1.18,6 (вершины, с о ответствую шве воястцту евган ыноаесгва М, заштрцдоввны). Таблцца 1.14 Часто ыяонестзо М задают в виде двоцчиой табзвцы, вандой строае воторой взаимно однозначно соответствуег воястятуецта.

Мновеспю стров таблвцы лняейяо уворядочено во воараствццю десяти оюго зввцвалеята соответстзуюшего ююичвого набора. Столбцам соответствуют ыцонесгва, обраауюшце врострвцство, воследцвй столбец солоставляегся ынааеству М ц едвцица увазывает на здондеице цонсппуентзз в ынонество М. В данном случае змеем табл. 1.14. Аявлитцчесвц ыяонество М задается з виде М = М, и ггГзп 14з и И; и Мз п Мз ц ц Мз и Из и Щ ц Мг и Мз и )И'з ц Мз и Мз и Мз нзц з виде ыографа С ю(У, Яз), Ую(МоР,/з 1,2,3), Яз СУ, я, (~м„ц,ю;), Оз;,цы н,г. з 3 (М, )Д, Ю), (М„М, И), (М, М, М )) (рис.

1.18, е). В рассматриваемой алгебре А = (В(1), О, Й, ) операции являются зависимыми. Действительно, согласно закону де Моргана любое множество из 22 множеств может быть построено и с помощью алгебры А = (В(1), О, ). Равносильными в смысле порождения любого множества из 22 множеств являются алгебры А = = (В(1), 1.1, ), А = (В(1), Г1, ), которые могут быть заменены соответственно алгебрами А = (В(1), 11, '1, 1), А = (В(1), П, '1, 1) согласно формуле М = 1 1 М, где универсум 1 рассматривается как нульместная операция.

Алгебра (В(1), 1.1, '1, 1) в силу равенств М, 0 Мь = М, ~ 'Мь ~ '(М, у) Мь), М ~ Мь = М ~ '(М и Мь) может быть заменена алгеброй вида (В(1), П, '1', 1). Рассмотрим задачу минимизации представления множеств в алгебре Кантора. Пересечение попарно различных множеств ( ) МУ' называется элементарным.

Выражение, задающее множество М в виде объединения различных элементарных пересечений, называется нормальной Яормой Кантора (НФК) множества М. Объединение конституент множества М называется совершенной НФК множества М. Минимальной НФК множества М называется НФК этого множества, имеющая минимальную сложность. Рассмотрим метод Квайна, который будем использовать для получения минимальной НФК множества М. Этот метод заключается в последовательном выполнении таких этапов. 1.

Выделение максимальных интервалов. Ннгнервалом множесозва М называется множество конституент множества М, образующих гиперкуб (некоторой размерности). Очевидно, что мощность интервала равна степени 2 (т. е. 2о, 21 и т. д.). г 1.6. Аксиоматике тиеории множеств 52 Гл. 1. Основы многосортных мноткеств Запишем, например, множество интервалов для рассмотрен- нога выше примера: 1000, 100, 110, 011, 111, -00, 1- О, 11-, — 11). Здесь и далее — означает, что множество, соответствующее этому разряду, в пересечении отсутствует, т. е. по этому множеству после объединения соответствующих констптуент произошло склеивание. Например, интервал -00, соответствующий множеству конституент 000 и 100, получается в результате преобразоваМ1 П Мг Г1 Мз 0 М1 й Мг Г1 Мз — Мг й Мз.

Интервал 1 называется максимальным интервалом 1„„, множества М, если не найдется другого интервала Хд этого множества, содержащего интервал 1, 1„~ 1д. В данном случае имеется четыре максимальных интервала: -00, 1-0, 11-, -11; каждый из них образует гиперкуб размерности 1 (ребро). Пересечение 1 1М; ', соответсхвуюшее максимальному интервалу множества М, называется простиой импликантиой этого множества. Объединение простых импликант множества М называется сокращенной НФК множества М.

Количество первичных термов, образующих простую импликанту, называется рангом простиой импликаиты, а элементарное пересечение — рангом соответствующего интервала. 100 1 о При выделении максимальных интервалов множество интервалов, имеющих один 11а 11- и тот же ранг, разбивают на полов, причем т-й пояс содержит интервалы, которым соот- 011 ветствуют наборы с 1 единицами в каждом. 111 Тогда выделение максимальных интервалов сводится к сравнению элементов только с оРис. 1.1Э седних поясов, номера которых отличаются на единицу. Если построенные интервалы не являются максимальными, то процесс сравнения продолжают. Результаты сравнения для рассматриваемого случая приведены на рис. 1.19. Сокращенная НФК множества М(М1т Мг, Мз) имеет вид М(М1, Мг, Мз) = Мг ПМз11 М1 Г1Мз1-1М1 Г1 Мг1.1 Мг Гт Мз.

Построением сокращенной НФК множества М заканчивается первый этап метода Квайна. Тупиковой НФК множесптва М называется такая НФК этого множества, которая при вычеркивании хотя бы одного первичного терна не определяет М. Минимальной НФК множества М называется НФК этого множества, содержащая минимальное количество первичных термов. Лемма 1.4. Минимальном НФК множества М лвллетисв тиупиковой.

Сложность минимальной НФК множества М нельзя уменьшить вычеркиванием первичного герма. Следовательно, эта форма является тупиковой. Лемма 1.5. Тупиковом НФК множества М состоит из простиых импликанти этого множества. Если хотя бы одно пересечение соответствует интервалу множества М, не являющемуся максимальным, то это пересечение можно заменить простой импликантой вычеркиванием соответствующих первичных термов, не выходя из класса эквивалентных НФК (задающих одно и то же множество) множества М, что противоречит определению тупиковой НФК. Теорема 1.7.

Тупиковые НФКмножестваМ, в том числе и минимальное НФК, содержатсл в сокращенной НФК этого множества. Тупиковая НФК множества М, в том числе и минимальная НФК, состоит согласно лемме 1.5 из простых имцликант. Сокращенная НФК множества М включает все простые импликанты. Следовательно, тупиковая (минимальная) НФК множества М содержится в сокращенной НФК этого множества. Согласно теореме 1.7 построение тупиковой НФК множества М сводится к покрытию двумерной таблицы.