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

• Название: Дискретная математика. Краткий курс. Учебное пособие
• Автор: Александр Казанский
• Жанр: Математика

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

---

= (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

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