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

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

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

---

Шаг 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}. Отсюда, образовав из них пересечение, можно получить полную нормальную форму пересечения объединений