04.04.2020г. гр.874 Основные понятия дискретной математики
материал

Тема: Основные понятия дискретной математики. Операции над множествами.

Лекционный         материал.

1.1 Понятие множества и подмножества

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

Множество – совокупность объектов, различаемых нашей интуицией.

Объекты, составляющие множество называются элементами этого множества.

Множества обозначаются большими латинскими буквами, а элементы – маленькими латинскими буквами.

Если элемент а принадлежит множеству А, то будем использовать запись , в противном случае используется запись .

Множество, содержащее конечное число элементов называется конечным. Если множество не содержит ни одного элемента, оно называется пустым. Если множество содержит все элементы, присутствующие в задаче, то оно называется универсальным и обозначается Е.

Множество можно задать различными способами. Самые распространенные это: перечисление элементов: ; указание свойств элементов: , (после двоеточия указаны свойства х).

Множество А называется подмножеством множества В только тогда, когда любой элемент множества А принадлежит множеству В. записывается это так:  если .

 - знак нестрогого включения (говорят В содержит или покрывает А).

 - знак строгого включения.

 - не включение.

Очевидно: если  и , то эти множества состоят из одних и тех же элементов и А=В.

1.2 Графическая интерпретация множеств и операций над ними

Для графической интерпретации множеств используют диаграммы Венна, которые имеют следующий вид:

Над множествами выполняются три двуместные операции:

• Пересечение;
• Объединение;
• Разность множеств.

Пересечением множеств А и В (мультипликативная операция) называется новое множество С , которое включает в себя элементы принадлежащие и множеству А и множеству В.

АВ

Пример: 

Объединением множеств А и В (аддитивная операция) называется новое множество С, состоящее из элементов множества А и из элементов множества В.

АUВ

Пример: 

Разностью множеств А и В называется новое множество С, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

А\ В из А вычесть В

Пример: 

.

Кроме рассмотренных двухместных операций существует одна одноместная операция – дополнение. Дополнением множества М является множество  (не М) = .

Порядок выполнения операций: сначала выполняется одноместная операция дополнения, затем операция пересечения, затем операция объединения и операция разности. Для изменения этого порядка в выражении используют скобки.

1.3 Свойства операций

1. Ассоциативность;
2. Коммутативность;
3. Дистрибутивность.

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел - ассоциативные операции, что и позволяет не ставить скобки (пример: a+b+c; abc) пример неассоциативной операции: возведение в степень (ab)c здесь скобки необходимы.

Операция называется коммутативной. Сложение и умножение являются коммутативными (от перемены мест слагаемых сумма не меняется). Вычисление и деление – некоммутативные, некоммутативной так же является операция умножения матриц.

1.4 Тождества и их доказательство

При выполнении операций над множествами часто приходиться доказывать равенства, т. е. тождества. (В частности, условия приведенные выше являются тождествами, которые необходимо доказать).

Доказать, что M=N, где M и N – выражения с множествами.

Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».

1. Сначала предположим, что некий элемент х принадлежит левой части равенства:  эта запись звучит следующим образом:

«если , то ».

2. На втором этапе предполагается, что элемент х принадлежит правой части равенства: .

1.5 Отношения на множествах

Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение– это просто подмножество. Мы остановимся на бинарных отношениях.

1. упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.
2. Две пары (x, y) и (x1, y1) считаются равными тогда и только тогда x1 = х, y1 = y.
3. Прямым произведением x y называется совокупность пар (x,y)таких, что .

Можно привести следующие примеры бинарных отношений:

• Отношение «иметь общий делитель отличный от 1» выполняется для пар (6,9); (4,2); (2,4); (4,4), но не выполняется для пар (7,9); (4,7).
• Отношение «быть делителем», т. е. x делит y выполняется для пар (2,4); (4,4), но не выполняется для пар (4,2); (7,9).
• Отношение выполняется для пар (7,9); (7,7), но не выполняется для пары (9,7).

1.6 Свойства отношений

1. Рефлексивность;
2. Симметричность;
3. Транзитивность.

Отношение обозначается R и записывается так: xRy (x и y находятся в отношении R).

Отношение R называется рефлективным, если для любого имеет место aRa. Главная диагональ его матрицы содержит только единицы.

Отношение R называется антирефлективным, если для любого не выполняется aRa. Главная диагональ его матрицы содержит только нули. Отношения = - рефлективные, а отношение < - антирефлективное.

Отношение R называется симметричным, если для пары (а,в)из aRb следует bRa, иначе говоря для любой пары отношение выполняется либо в обе стороны, либо не выполняется вообще. Матрица данного отношения симметрична относительно главной диагонали.

Отношение R называется транзитивным, если для любых a,b,c из aRb и bRс следует aRс отношения = - транзитивны, отношение «пересекаться» – нетранзитивно. (Пример:  пересекается с  пересекается с , однако  и  не пересекаются).

Задание №2

Установите какими свойствами обладает каждое из отношений, заданных на R следующими высказывательными формами:

1. x+y=2;

Решение:

в данном случае заданы отношения + и .

Подставим в выражение x+y=2 конкретные значения: 1+1=2, последовательно проверим каждое свойство:

Рефлективность: aRа = а+а = 1+1 – условие выполняется , следовательно данное отношение рефлективно.

Симметричность: из aRb следует bRa = из а+b следует b+а = из 1+1 следует 1+1 – условие выполняется, следовательно данное отношение симметрично.

Транзитивность: из aRb и bRс следует aRс данное условие мы проверит не можем, т. к. оно применимо только для трех или более элементов.

Выполнить задачи самостоятельно:

Задача №1

В олимпиаде по математике для абитуриентов приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии – 18 человек, по тригонометрии – 18 человек.

По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека.

1. Сколько учащихся решили все задачи?
2. Сколько учащихся решили только две задачи?
3. Сколько учащихся решили только одну задачу?

Задача № 2

Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов.

Сколько студентов успешно решили только одну контрольную работу?

Задача № 3

В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом – 15 учеников, метро и троллейбусом – 13 учеников, троллейбусом и автобусом – 9 учеников.

Сколько учеников пользуются только одним видом транспорта?

Требования к отчетности:

1. Изучаем лекционный материал с задачами и оформляем его в рабочую тетрадь;
2. Выполнить 3 задачи самостоятельно в рабочей тетради;
3. Присылаем фотоотчет на почту: vismyt89@mail.ru или в ВКонтакте.

*Для дополнительной информации, можно пройти по ссылке: https://siblec.ru/informatika-i-vychislitelnaya-tekhnika/diskretnaya-matematika