Текст книги "Дискретная математика. Краткий курс. Учебное пособие"

1.12. Многочлены алгебры множеств

Множества с операциями пересечения, объединения и дополнения, удовлетворяющие абстрактным законам, введенным в главе 1, параграф 1.8, образуют алгебраическую систему, называемую алгеброй множеств. Эта алгебра является булевой алгеброй и поэтому часто использует идеи и терминологию булевой алгебры, однако следует отметить, что эта терминология не вполне стандартизирована, что иногда приводит к различным названиям одних и тех же понятий. Рассмотрим некоторые понятия более подробно.

Пусть имеется n переменных, каждая из которых определяет некоторое множество. Выражением алгебры множеств Е (или формулой) называется выражение, составленное из этих переменных, соединенных при помощи операций объединения, пересечения и дополнения, например

Е1 = A ∩ (BС ∩ С)С ∪ (A ∩ BС ∩ СC)С,

Е2 = A ∩ (BС ∩ С) ∪ (A ∩ BС ∩ СC),

Е3 = (A ∩ BС ∩ С) ∪ (A ∩BС ∩ СC),

Е4 = (AC ∪ BC) ∩ (AC ∪ BC ∪ С) ∩ (BC ∪ С),

Е5 = (AC ∪ B ∪ С) ∩ (A ∪ BC ∪ С) ∩ (AC ∪ BC ∪ С)

являются выражениями из трех переменных А, В и С.

Литералом называется переменная или дополнение переменной, например А, АС, ВС и т. д. Произведением называется литерал или пересечение двух или более литералов, таких что ни одна пара из них не содержит одной и той же переменной. Например, BС ∩ С, A ∩ BС ∩ СC, А, СC являются произведениями, а выражения A ∩ BС ∩ АС и A ∩ BС ∩ BС – нет. Заметим, что любое пересечение литералов всегда приводится либо к Ø, либо к произведению. Так, например A ∩ BС ∩ АС= Ø, потому что A ∩ АС= Ø (по закону дополнения), а пересечение A ∩ BС ∩ BС= A ∩ BС, потому что BС ∩ BС= BС (по закону идемпотентности).

Если при n переменных произведение состоит из n литералов, то его называют фундаментальным произведением (некоторые авторы называют любое произведение фундаментальным произведением).

Выражение, представляющее собой объединение различных произведений, если в нем нет ни одного произведения, которое включается в другое произведение, называют суммой произведений, или нормальной формой объединения пересечений, или многочленом в нормальной форме. Из предыдущего примера Е1 является просто выражением, Е2 и Е3 – выражениями в нормальной форме объединения пересечений.

Если выражение состоит из объединения фундаментальных произведений, то такое выражение называют полной нормальной формой объединения пересечений, или многочленом в канонической форме. Многочлен Е3 кроме того, что он имеет нормальную форму объединения пересечений, является еще и многочленом имеющим полную нормальную форму объединения пересечений.

Аналогично если при n переменных объединение состоит из n литералов, то его называют фундаментальным объединением, и если заменить операции объединения на операции пересечения, а операции пересечения на операции объединения, то можно получить нормальную форму пересечения объединений и полную нормальную форму пересечения объединений. Выражение Е4 имеет нормальную форму пересечения объединений, а Е5 – полную нормальную форму пересечения объединений.

Любое выражение может быть преобразовано к эквивалентному выражению, имеющему нормальную форму. Одно из отличий нормальной формы в том, что в таком выражении операция дополнения применяется только к переменным. Чтобы избавиться от дополнений, применяемых к выражениям, надо применять закон де Моргана.

Алгоритм 1.1 для преобразования выражения к нормальной форме объединения пересечений.

Пусть имеется исходное выражение алгебры множеств Е.

Шаг 1. Используя законы де Моргана и инволюции, приведем каждую скобку, к которой применяется операция дополнения, к виду, в котором операция дополнения применяется только к переменным.

Шаг 2. Используя закон дистрибутивности объединения относительно пересечения, раскроем скобки, содержащие объединения литералов относительно операций пересечения.

Шаг 3. Используя законы ассоциативности, дополнения и идемпотентности, преобразуем каждое пересечение литералов либо в Ø, либо в произведение.

Шаг 4. Используя законы поглощения и тождества, упростим выражение Е, и если оно состоит из объединения пересечений, то нормальная форма получена, если же нет, то переходим к шагу 2.

Пример 1.7

Применим данный алгоритм для преобразования к нормальной форме следующего выражения:

Е = ((А ∩ ВС) ∪ (В ∩ СС)С) ∩ (((В ∩С) ∪ (АС ∩ С))С ∪ (А ∩ В)).

Шаг 1. Используя законы Де Моргана и инволюции, получим

Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((ВС ∪ СС) ∩ (А ∪ СС) ∪ (А ∩ В)).

Шаг 2. Используя закон дистрибутивности, раскроем скобки в правой части выражения:

Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ ∩ СС) ∪ (СС ∩ СС) ∪ (А ∩ В)).

Шаг 3. Преобразуем пересечение литералов в произведение:

Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ ∪ СС ∪ (А ∩ В)).

Шаг 4. Поскольку ВС включается в А ∩ ВС, то А ∩ ВС поглощается, также СС включается в ВС ∩ СС и А ∩ СС, поэтому оба эти пересечения поглощаются и выражение Е принимает следующий вид:

Е = (ВС ∪ С) ∩ ((А ∩ ВС) ∪ СС ∪ (А ∩ В)).

Здесь снова надо раскрывать скобки, поэтому переходим к шагу 2.

Шаг 2. Раскроем скобки и получим:

Е = (А ∩ ВС ∩ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ ВС) ∪ (А ∩ ВС ∩ ∩ С) ∪ (С ∩ СС) ∪ (А ∩ В ∩ С).

Шаг 3. Преобразуем пересечение литералов в произведение:

Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ Ø ∪ (А ∩ ВС ∩ С) ∪ Ø ∪ (А ∩ ∩ В ∩ С).

Шаг 4. Пересечение А ∩ ВС включается в А ∩ ВС ∩ С, поэтому последнее поглощается и нормальная форма для Е имеет вид

Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).

1.13. Полные нормальные формы

Следует отметить, что терминология этого раздела не стандартизирована, так по аналогии с булевой алгеброй полные нормальные формы иногда называют совершенными нормальными формами. Рассмотрим выражение Е = Е(x1, x2, … xn), состоящее из объединения произведений, т. е. представленное в нормальной форме. Если каждое произведение состоит точно из n литералов, то такое выражение называется полной нормальной формой объединения пересечений.

Теорема 1.2. Любое выражение алгебры множеств может быть преобразовано к эквивалентному ему выражению в полной нормальной форме, и такое представление является единственным.

В предыдущем разделе было показано, как преобразовать любое выражение алгебры множеств к эквивалентному выражению в нормальной форме. Далее рассмотрим алгоритм, позволяющий трансформировать это выражение в эквивалентное ему выражение в полной нормальной форме. Идея этого алгоритма состоит в том, что если какое-то произведение Р в выражении Е не содержит i-й переменной, то ее можно вести в Е, образуя произведение Р∩(xi∪xic) при i < n.

Алгоритм 1.2 для преобразования выражения к полной нормальной форме объединения пересечений.

Шаг 1. Пусть имеется выражение Е = Е(x1, x2, …xn), представленное в нормальной форме. Найдем произведение Р в выражении Е, которое не содержит i-й переменной, и образуем произведение Р∩(xi∪xic). Это не нарушает эквивалентности выражения, поскольку (xi∪xic) = U, а Р ∩ U = Р. Удалим повторяющиеся произведения (это возможно, поскольку Р ∪ Р = Р).

Шаг 2. Повторяем шаг 1 до тех пор, пока каждое произведение в Е не станет фундаментальным произведением, т. е. каждое произведение не будет включать в себя все n переменных.

Пример 1.8. Применим данный алгоритм для выражения Е в нормальной форме, полученного в примере 1.7, чтобы преобразовать его к полной нормальной форме.

Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).

Шаг 1. Находим произведение А ∩ ВС, которое не содержит переменной С, и образуем произведение (А ∩ ВС) ∩ (С ∪ СС), получим

Е = (А ∩ ВС) ∩ (С ∪ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С) = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).

Шаг 2. Поскольку в Е имеется произведение ВС ∩ СС, которое не содержит переменной А, то снова переходим к шагу 1 и образуем произведение (ВС ∩ СС) ∩ (А ∪ АС),

Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∩ (А ∪ АС) ∪ ∪ (А ∩ В ∩ С).

После раскрытия скобок в Е образуется два одинаковых фундаментальных произведения А ∩ ВС ∩ СС. Одно из них необходимо удалить. Теперь Е представлено в полной нормальной форме:

Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (А ∩ ∩ В ∩ С).

Таким образом, если имеется выражение, представленное в нормальной форме, то данный алгоритм позволяет алгебраическими преобразованиями привести его к полной нормальной форме. Однако этот способ не единственный. Для этой же цели можно также использовать и диаграммы Венна.

Рассмотрим пример. Пусть имеется разбиение множества U, показанное на рис. 1.10. Выделим множество, которое задается формулой (нормальной формой объединения пересечений) А ∪ (ВС ∩ С). Она задает объединение двух множеств: А = {4, 5, 6, 7} и множества, представляющего собой пересечение множеств ВС и С, т. е. множества ВС ∩ С = {1, 5}. Поэтому множество А ∪ (ВС ∩ С) = {1, 4, 5, 6, 7}. На рис. 1.12 это множество заштриховано. Из диаграммы видно, что множество А ∪ (ВС ∩ С) задается объединением пяти фундаментальных произведений: множеству {4} соответствует фундаментальное произведение А ∩ ВС ∩ СС, множеству {6} – А ∩ В ∩ СС, множеству {7} – А ∩ В ∩ С, множеству {5} – А ∩ ВC ∩ С и множеству {1} – АC ∩ ВС ∩ С. Объединение этих фундаментальных произведений и дает полную нормальную форму

(А ∩ ВС ∩ СС) ∪ (А ∩ В ∩ СС) ∪ (А ∩ В ∩ С) ∪ (А ∩ ВС ∩ ∩ С) ∪ (АС ∩ ВС ∩ С).

Рис. 1.12

Заметим, что для любого множества существует не только единственная полная нормальная форма объединения пересечений, но и единственная полная нормальная форма пресечения объединений. Эту форму также можно найти двумя способами. Так, для множества из предыдущего примера А ∪ (ВС ∩ С) раскроем скобки и получим выражение в нормальной форме пересечения объединений (А ∪ ВС) ∩ (А ∪ С). В первой скобке нет переменной С, а во второй переменной В. Поскольку выражение (С ∩ СС) = Ø, то следующее выражение эквивалентно исходному

((А ∪ ВС) ∪ (С ∩ СС)) ∩ ((А ∪ С) ∪ (В ∩ ВС)) = (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С) = (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С).

Последнее выражение и будет полной нормальной формой пересечения объединений для исходной формулы.

Найти данное выражение можно также и при помощи диаграммы Венна. Поскольку в исходное множество {1, 4, 5, 6, 7} не вошли элементы {0, 2, 3 }, то необходимо образовать пересечение таких объединений, которые не содержат эти три множества. Объединение А ∪ В ∪ С не содержит элемента {0}, объединение А ∪ ВС ∪ С не содержит элемента {2} и объединение А ∪ ВС ∪ СС не содержит элемента {3}. Отсюда, образовав из них пересечение, можно получить полную нормальную форму пересечения объединений

(А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС).

Более подробно эти формы будут рассмотрены в упражнениях.

1.14. Определение минимальных форм

Множество можно задавать различными формулами. Хотя эти формулы выглядят по-разному, но все они эквивалентны в том смысле, что они определяют одни и те же элементы данного множества. Например, пусть имеются два выражения в нормальной форме:

Е1 = (В ∩ С) ∪ (АС ∩ СС),

Е2 = (В ∩ С) ∪ (АС ∩ В) ∪ (АС ∩ ВС ∩ СС).

Эти формулы эквивалентны, что нетрудно проверить, если преобразовать каждую из них к полной нормальной форме, которая и для Е1 и для Е2 одна и та же:

(А ∩ В ∩ С) ∪ (АС ∩ В ∩ С) ∪ (АС ∩ В ∩ СС) ∪ (АС ∩ ВС ∩ СС).

Для того чтобы определить, какая из эквивалентных формул «проще», введем следующие обозначения. Пусть Е – выражение в нормальной форме и пусть L(E) – количество литералов в этом выражении (считаются все вхождения) и F(E) – количество произведений, из которых образовано Е. Так, для Е1 значение L(E1) = 2 + 2 = 4 и F(E1) = 2, а L(Е2) = 2 + 2 + 3 = 7 и F(E2) = 3.

Пусть Е1 и Е2 эквивалентные выражения в нормальной форме. Тогда Е1 проще Е2 если

L(E1) < L(Е2) и F(E1) < L(Е2) или

L(E1) < L(Е2) и F(E1) < L(Е2).

Выражение Е, представленное в нормальной форме, называется минимальным, если не существует никакого другого эквивалентного ему выражения, которое проще, чем Е. Следует заметить, что может существовать более одного эквивалентного минимального выражения.

Произведение Р называется простым импликантом, для выражения Е, если

Р ∪ Е = Е

и нет никакого другого произведения, содержащегося в Р, которое обладает этим свойством. Например, пусть

Е = (А ∩ С) ∪ (ВС ∩ С) ∪ (АС ∩ В ∩ С).

Можно показать, что выражение

(АС ∩ В) ∪ Е = Е, но АС ∪ Е ≠ Е и В ∪ Е ≠ Е.

Поэтому АС ∩ В является простым импликантом Е.

Теорема 1.3. Любое выражение Е, представленное в минимальной форме, является объединение простых импликантов Е.

Методы определения минимальных форм обычно базируются на алгоритмах, которые позволяют находить простых импликантов и выбирать из них те, которые и дают выражения в минимальной форме. Для определения простых импликантов имеется метод соседства (его также называют методом консенсуса), который состоит в следующем. Пусть Pi и Pj – такие два произведения, что одно из них содержит литерал Х, а другое ХС (т. е. какая-то переменная в одно произведение входит без дополнения, а в другое с дополнением и других переменных с этим свойством в данных произведениях нет). Тогда соседством Pi и Pj будет называться произведение (без повторений), составленное из литералов Pi и Pj, из которых удалены Х и ХС, а сами Pi и Pj называются соседними. Соседство не определено, если Pi = X и Pj = XC.

Из определения соседства следует следующее утверждение:

если S является соседством Pi и Pj, то тогда

Pi ∪ Pj ∪ S = Pi ∪ Pj.

Пример 1.9. Найти соседство S для P1 и Р2.

1) P1 = (А ∩ В) и Р2 = (ВС ∩ СС), удалим В и ВС и образуем пересечение P1 и Р2 получим S = А ∩ СС.

2) P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ СС, удалим С и СС, получим без повторений S = АС ∩ ВС.

3) P1 = В и Р2 = ВС ∩ СС, удаление В и ВС дает S = СС.

4) P1 = АС ∩ ВС ∩ С и Р2 = В ∩ С ∩ D, удаление ВС и В дает S = АС ∩ С ∩ D.

5) P1 = АС ∩ ВС ∩ С и Р2 = В ∩ СС, здесь две переменные В и С имеют дополнения и поэтому P1 и Р2 не имеют соседства.

6) P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ С, здесь нет переменой без дополнения и с дополнением и поэтому P1 и Р2 также не имеют соседства.

Метод соседства позволяет находить все простые импликанты для любой формулы в нормальной форме.

Алгоритм 1.3 для нахождения простых импликантов (метод соседства).

Пусть имеется исходное выражение алгебры множеств Е, представленное в нормальной форме.

Шаг 1. Используя закон поглощения, удалим произведение Pi, которое включается в себя произведение Pj.

Шаг 2. Если имеются два соседних произведения Pi и Pj, то добавим к Е соседство S, которое они определяют.

Шаг 3. Повторяем шаг 1 и шаг 2, пока они могут быть применены.

Теорема 1.4. Когда метод соседства прекращает работу, тогда выражение Е представляет собой объединение простых импликантов.

Пример 1.10

Найти все простые импликанты для выражения Е

Е = (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (АС ∩ ВС ∩ С) ∪ ∪ (А ∩ В ∩ С)

(удалено АС ∩ ВС ∩ С, поглощаемое AC ∩ С)

= (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)

(для соседних произведений (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) добавлено (ВС ∩ СС))

= (ВС ∩ СС) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ ∪ (А ∩ В ∩ С)

(удалены (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) поглощаемые (ВС ∩ СС))

= (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)

(для соседних произведений (ВС ∩ СС) и (AC ∩ С) добавлено (AC ∩ ВС))

= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С)

(для соседних произведений (AC ∩ С) и (А ∩ В ∩ С) добавлено (В ∩ С))

= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С) ∪ (В ∩ С)

(удалено (А ∩ В ∩ С), поглощаемое (В ∩ С))

= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).

Поскольку ни одного нового импликанта образовать нельзя, алгоритм прекращает свою работу и Е представлено в виде объединения четырех простых импликантов

E = (AC ∩ ВС), (ВС ∩ СС), (AC ∩ С) и (В ∩ С).

Хотя метод соседства и дает все простые импликанты, он не отвечает на вопрос, как для данного выражения выглядит эквивалентная ему минимальная форма и тем более сколько для него имеется эквивалентных минимальных форм. Чтобы найти минимальную форму, применим следующий алгоритм.

Алгоритм 1.4 для нахождения минимальной формы в выражении, представляющем собой объединение простых импликантов.

Пусть имеется исходное выражение алгебры множеств Е, представленное в нормальной форме в виде объединения всех простых импликантов Е.

Шаг 1. Представим каждый простой импликант в виде объединения фундаментальных произведений (используя алгоритм преобразования выражения к полной нормальной форме объединения пересечений).

Шаг 2. Последовательно удалим из Е каждый такой имликант, все фундаментальные произведения которого имеются среди фундаментальных произведений остающегося выражения.

Пример 1.11. Применим этот алгоритм для выражения, полученного в примере 1.10:

Е = (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).

Выразим каждый простой импликант в виде объединения фундаментальных произведений:

AC ∩ ВС= (АС ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ СС),

ВС ∩ СС = (АС ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ СС),

AC ∩ С = (АС ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С),

В ∩ С = (А ∩ В ∩ С) ∪ (АС ∩ В ∩ С).

Удалим импликант AC ∩ ВС, поскольку его фундаментальное произведение (АС ∩ ВС ∩ С) входит в выражение для третьего импликанта, а (АС ∩ ВС ∩ СС) входит в выражение для второго импликанта. Из оставшихся трех импликантов ни один этим свойством не обладает, поэтому алгоритм прекращает свою работу и минимальная форма для Е выглядит следующим образом:

Е = (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).

Заметим также, что метод соседних произведений можно использовать и при эквивалентных преобразованиях выражений, чтобы уменьшить число произведений, входящих в упрощаемый многочлен. Это можно сделать при помощи следующих правил, называемых правилами соседства:

(А ∩ В) ∪ (АС ∩ С) ∪ (В ∩ С) = (А ∩ В) ∪ (АС ∩ С),

(А ∪ В) ∩ (АС ∪ С) ∩ (В ∪ С) = (А ∪ В) ∩ (АС ∪ С).

Доказательство этих правил, использующее граф, рассмотрено далее.

1.15. Представление формул алгебры множеств графами

Многочлену в полной нормальной форм можно взаимно однозначно поставит в соответствие неориентированный двудольный граф. Как следует из параграфа 1.13, каждое множество имеет единственную полную нормальную форму объединения пересечений, а также единственную полную нормальную форму пресечения объединений. Отсюда следует, что каждому множеству можно поставить в соответствие единственный граф, задаваемый полной нормальной формой объединения пересечений, и единственный граф, задаваемый полной нормальной формой пересечения объединений. Заметим, что существуют множества, для которых эти графы могут быть изоморфны. Из сказанного также следует, что имеются задачи, связанные с множествами, которые можно решить методами теории графов.

Сначала необходимо определить понятие смежных произведений. Оно основано на той же идее, которая используется при введении понятия соседства в параграфе 1.14. Два фундаментальных произведения Pi и Pj называются смежными, если они состоят из тех же самых переменных и различаются точно в одном литерале. Другими словами, имеется какая-то переменная, которая в одно из этих фундаментальных произведений входит без дополнения, а в другое с дополнением. В частности, объединение двух смежных фундаментальных произведений представляет собой произведение, в котором на один литерал меньше.

Любую формулу алгебры множеств можно, используя результаты параграфа 1.13, преобразовать к полной нормальной форме в виде объединения фундаментальных произведений. Поставим в соответствие такой формуле двудольный граф следующим образом. Вершины графа сопоставим фундаментальным произведениям, а две вершины соединены ребром, если соответствующие им фундаментальные произведения имеют различие точно в одном литерале (т. е. являются смежными).

Для единообразного изображения графов на диаграммах разобьем множество вершин на группы, которые разместим на диаграмме слева направо. В самую левую группу поместим вершину, которой соответствует фундаментальное произведение, не содержащее переменных с дополнениями. Далее поместим вершины, которым соответствуют фундаментальные произведения с одним дополнением, затем с двумя, с тремя и т. д. Последняя, правая, группа должна содержать вершину, соответствующую фундаментальному произведению, в котором все переменные имеют дополнения. Диаграмма может содержать не все группы, и каждая группа может содержать не все вершины, поскольку это определяется конкретным многочленом. Такое размещение вершин удобно еще и потому, что ребра в графе будут появляться только между вершинами, находящимися в соседних группах, поскольку только они могут быть смежными.

Пример 1.12. Построить граф для множества, задаваемого многочленом, представляющим собой полную нормальную форму объединения пересечений:

Е = (А ∩ В ∩ С) ∪ (А ∩ В ∩ СС) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ В ∩ СС) ∪ ∪ (АС ∩ ВС ∩ СС).

Многочлен содержит 5 фундаментальных произведений, поэтому в графе будет 5 вершин. Поскольку многочлен содержит n = 3 переменных, то при разбиении вершин возможны n + 1 = 4 группы. В левой группе будет вершина соответствующая фундаментальному произведению А ∩ В ∩ С. В следующей за ней группой с одним дополнением возможны три вершины, однако в данном многочлене имеется только одна такая вершина, соответствующая фундаментальному произведению А ∩ В ∩ СС. Фундаментальных произведений с двумя дополнениями в данном многочлене два: А ∩ ВС ∩ СС и АС ∩ В ∩ СС, поэтому группа состоит из двух вершин. Последняя правая группа состоит из одной вершины. Граф выглядит следующим образом (рис. 1.13):

Рис. 1.13

Пример 1.13. Для множества, задаваемого многочленом Е из предыдущего примера, найти полную нормальную форму пересечения объединений и построить для нее граф.

Чтобы найти для Е эквивалентную ему полную нормальную форму пересечения объединений, необходимо, как известно из параграфа 1.13, либо раскрыть скобки в выражении для Е, либо использовать диаграмму Венна. Любой из этих способов дает

Е = (A ∪ B ∪ CC) ∩ (A ∪ BC ∪ CC) ∩ (AC ∪ B ∪ CC).

Многочлен содержит три фундаментальных объединения, поэтому граф будет иметь три вершины. Группы, которая должна состоять из фундаментального объединения, не имеющего дополнений, здесь нет. Группа с одним дополнением имеет одно фундаментальное объединение A ∪ B ∪ CC, а группа с двумя дополнениями имеет два фундаментальных объединения: A ∪ BC ∪ CC и AC ∪ B ∪ CC, поэтому граф имеет вид (рис. 1.14):

Рис. 1.14

Следует заметить, что разбиение вершин на группы необязательно и граф можно изобразить и так (рис. 1.15):

Рис. 1.15

Однако построение графа при разбиении вершин на группы проще, особенно при большом количестве переменных в исходной формуле.