Дискретная математика. Краткий курс. Учебное пособие - Александр Казанский

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

1.16. Минимизация формул алгебры множеств на графе

Задание множества многочленом, представляющим собой объединение фундаментальных произведений (или этот многочлен образован каким-либо другим способом), может привести к достаточно сложному выражению. Часто на практике для определения его элементов необходимо иметь более простое выражение для задания того же самого множества. Кроме метода определения минимальных форм, рассмотренного в параграфе 1.14, известны методы минимизации, использующие матрицы, а также метод, основанный на картах Карно (Karnaugh maps). Однако наиболее простым и эффективным является метод, использующий неориентированные двудольные графы.

Декартовым произведением графовG1 × G2 называется граф, множество вершин которого состоит из всех упорядоченных пар (u, v) декартова произведения множеств U × V (где U – вершины из графа G1, а V — вершины из графа G2). Две вершины произведения соединены ребром тогда и только тогда, когда либо первые вершины пары совпадают, а вторые смежны в исходном графе, либо вторые вершины совпадают, а первые смежны в исходном графе.

Граф, называемый n-мерным кубом Qn, определяется рекурсивно:

Q1 = K2 (полный граф с двумя вершинами, или ребро),

Qn = K2 × Qn-1.

Каждый n-куб имеет 2n вершин и n × 2n ребер.

Найдем граф Q2, представляющий собой декартово произведение К2 × К2.

Образуем все пары декартова произведения U×V:

(u1v1) (u1v2) (u2v1) (u2v2).

Пары (u1v1) и (u1v2) образуют ребро, поскольку первая вершина каждой пары одна и та же u1, а вторые вершины v1 и v2 смежны. Пары (u1v1) и (u2v2) не образуют ребра, потому что нет совпадения вершин ни для первой, ни для второй пары. Граф Q2 показан на рис. 1.16.

Рис. 1.16

Кубы Q3 и Q4 показаны на рис. 1.17.

Рис. 1.17

Связь между фундаментальными произведениями и вершинами графа – это фактически связь между областями на диаграмме Венна. Если связать таким образом все области диаграммы Венна при двух переменных, то образуется граф, изоморфный графу Q2, при трех – графу Q3, при n – Qn. Граф Q3 для диаграммы Венна при трех переменных показан на рис. 1.18.

Рис. 1.18

Теорема 1.5

Каждое покрытие вершин графа, соответствующего формуле для n переменных, наименьшим числом кубов Qp, наибольшей размерности p (p = 0, 1, 2, …, n – 1), определяет все эквивалентные ей минимальные формулы.

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

Чтобы найти импликант для куба Qp, надо рассмотреть фундаментальные произведения для всех 2р вершин этого куба, выбрать из них те литералы, которые не изменяются ни на одной из вершин этого куба, и составить из них пересечение (без повторений).

Куб Q0 – это одна вершина, и поэтому импликант для него соответствует фундаментальному произведению.

Куб размерности 1 – это ребро, и его импликант имеет на один литерал меньше, чем фундаментальное произведение вершины, например если куб задается фундаментальными произведениями AС ∩ BС ∩ C и AС ∩ B ∩ C, то здесь не изменяются литералы AС и С. Поэтому импликант состоит из их пересечения АС ∩ С.

Куб размерности 2 состоит из четырех вершин, и если размерность задачи больше 2, то импликант имеет на две переменные меньше, чем фундаментальное произведение вершины. Например, если куб задается фундаментальными произведениями

A ∩ B ∩ C, A ∩ B ∩ CС, A ∩ BС ∩ C, A ∩ BС ∩ CС, то здесь только литерал А не изменяется во всех четырех фундаментальных произведениях, поэтому А и будет импликантом для этого куба.

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

Пример 1.13. Найти минимальную форму для следующей формулы:

Е = (B ∩ C) ∪ (AС ∩ B ∩ C) ∪ (AС ∩ B) ∪ (AС ∩ CС).

Определим все фундаментальные произведения для формулы Е и получим

Е = (А ∩ B ∩ C) ∪ (AС ∩ B ∩ C) ∪ (AС ∩ B ∩ CС) ∪ (AС ∩ BС ∩ CС).

Разобьем вершины на четыре группы и получим следующий граф (рис. 1.19):

Рис. 1.19

Для минимального покрытия вершин этого графа необходимо два куба размерности 2 (два ребра) – рис. 1.20):

Рис. 1.20

Это покрытие дает минимальную форму для исходной формулы

Е = (B ∩ C) ∪ (АС ∩ CС).

Использование графов позволяет понять многие методы, используемые при определении минимальных форм. Например, упрощение, используемое в правиле соседства:

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

Построим граф для этой формулы. Для этого найдем полную нормальную форму объединения пересечений:

Е = (А ∩ B ∩ C) ∪ (A ∩ B ∩ СС) ∪ (Ac ∩ BС ∩ C) ∪ (Аc ∩ B ∩ C).

Разбив вершины на две группы, получим граф (рис. 1.21):

Рис. 1.21

Этот граф состоит из трех кубов размерности 2 (три ребра), однако наименьшее число кубов, которыми можно покрыть все его вершины, только два (все четыре вершины закрываются двумя ребрами А ∩ В и АС ∩ С). Поэтому вместо трех импликантов, имеющихся в представлении данного множества, оно имеет эквивалентное задание двумя импликантами, что и доказывает минимальное покрытие на рис. 1.21.

Пример 1.14. Найти минимальную форму для следующей формулы

Е = (A ∩ B ∩ CС) ∪ (A ∩ B ∩ C) ∪ (ВС ∩ C) ∪ (AС ∩ B ∩ C).

Определим все пять фундаментальных произведений для формулы Е и получим

Е = (А ∩ B ∩ C) ∪ (A ∩ B ∩ CС) ∪ (A ∩ BС ∩ C) ∪ (AС ∩ BС ∩ C) ∪ ∪ (AС ∩ B ∩ C).

Разобьем вершины на четыре группы, построим граф и найдем два его минимальных покрытия (рис. 1.22 и 1.23), т. е. имеются две эквивалентные минимальные формы.

Рис. 1.22

Рис. 1.23

Е1 = А ∩ B ∪ А ∩ С ∪ AС ∩ B;

Е2 = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B и при этом

А ∩ B ∪ А ∩ С ∪ AС ∩ B = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B.

1.17. Решенные задачи

Множества и подмножества

1.1. Определить, какие из следующих множеств правильно определены:

А = {1, 2, 3, 4 },

B = { a, d, c, d, f },

C = {x: x ∈ N и

=2},

D = { A, B, C },

Все множества определены правильно.

Множество А состоит из чисел. Строго говоря, числа – выдуманные объекты, их не существует. Они придуманы для того, чтобы записывать результаты счета. Поэтому более точно следовало бы говорить о множестве символов чисел, или множестве их имен. Однако очень часто, когда необходимо представить множество каких-то объектов, обычно представляют их имена.