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

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

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

---

Найти данное выражение можно также и при помощи диаграммы Венна. Поскольку в исходное множество {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 ∩ С) ∪ (В ∩ С).