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

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

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

---

– список студентов, которые не имеют пропусков по математике и английскому языку, но имеют – по информатике, AС ∩ B ∩ CС = {8};

– список студентов, которые не имеют пропусков по математике, но имеют по информатике и английскому языку, AС ∩ B ∩ C = Ø;

– список студентов, которые имеют пропуски по математике, но не имеют по информатике и английскому языку, (A ∩ BС ∩ CС) = {1,6};

– список студентов, которые имеют пропуски по математике и английскому языку, но не имеют по информатике, A ∩ BС ∩ C = {2,7};

– список студентов, которые не имеют пропусков ни по математике, ни по информатике, но имеют по английскому языку, A ∩ B ∩ CС= {3};

– список студентов, которые имеют пропуски по всем трем предметам, A ∩ B ∩ C = {4, 5}.

Получив эти данные, деканат хотел бы составить списки тех студентов, которые:

1) имеют пропуски по математике, но не имеют по информатике;

2) имеют пропуски по математике и информатике;

3) имеют по крайней мере один пропуск по математике.

Для того чтобы ответить на вопрос первого пункта, т. е. найти множество тех студентов, которые имеют пропуски по математике, но не имеют по информатике, надо составить многочлен из тех фундаментальных произведений, которые включают в себя множество A ∩ BС.Таких фундаментальных произведений два. Их объединение и дает искомый многочлен (A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) = {1, 6} ∪ {2, 7} = {1, 2, 6, 7}. Это легко доказать, если выполнить упрощение данной формулы:

Аналогичное рассуждение можно применить и для второго пункта:

Для ответа на третий пункт, т. е. для определения множества А, надо составит многочлен из четырех фундаментальных произведений, содержащих множество А. Этот многочлен имеет вид

(A∩BС∩CС) ∪(A∩BС∩C)∪ (A∩B∩C) ∪(A∩B∩CC) = {1, 6}∪{2, 7}∪{3}∪{4, 5 } = {1, 2, 3, 4, 5, 6, 7}.

Многочлен можно упростить:

Решение задачи можно получить и при помощи диаграммы Венна, показанной на рис. 1.11.

Рис. 1.11

Поскольку мы имеем все 8 комбинаций из трех исходных множеств и их дополнений, т. е. имеем все 8 фундаментальных произведений для трех множеств, то к решению данной задачи можно подойти и иначе. Допустим, нам надо выполнить первый пункт задачи, т. е. найти множество тех студентов, которые имеют пропуски по математике, но не имеют их по информатике. Фактически нам надо найти пересечение двух множеств: множества А (имеющих пропуски по математике) и множества ВС (не имеющих пропусков по информатике), т. е. множество A ∩ BС. Для того чтобы найти элементы этого множества, нам нужно выразить множества A ∩ BС через фундаментальные произведения. Сделать это можно с помощью искусственного приема, который позволяет вводить в любое пересечение множеств те множества, которые в нем отсутствуют, приводя его тем самым к объединению фундаментальных произведений.

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

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

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

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