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

Скачать книгу

и информатике;

      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

Скачать книгу