Similar presentations:
Диаграммы Венна. Операции над множествами
1.
Конспект лекций по дисциплине «Дискретная математика»лектор – Гонтовая Наталия Викторовна
ГОУ ВПО ЛНР «Донбасский государственный технический университет»
2015-2016 учебный год
Тема 3:
Диаграммы Венна.
Операции над
множествами.
ДМ, лектор – Гонтовая Н.В.
2.
стр.2ПЛАН к теме 3:
1. Логические диаграммы. Диаграммы Венна
2. Операции над множествами. Свойства операций
3. Законы алгебры множеств
3.1 Законы де Моргана
3.2 Закон поглощения
3.3 Закон склеивания
4. Примеры решения задач по теме 3
5. Задания на самопроработку по теме 3
БЛОК 3.1
ДМ, лектор – Гонтовая Н.В.
3.
стр.31
Логические диаграммы (ЛД) – графический аппарат
теории множеств и математической логики.
Разновидностями логических диаграмм являются
диаграммы Эйлера, диаграммы Венна, диаграммы Вейча,
карты Карно и др.
Идея ЛД известна, начиная со средних веков.
Графические способы представления множеств
использовались в работах таких ученых как
Г.В. Лейбниц, Л. Эйлер, Э. Шрёдер, Ч.Л. Доджсон,
Дж. Вэнн и др.
ДМ, лектор – Гонтовая Н.В.
4.
стр.4Готфрид Вильгельм Лейбниц (1646-1716) – немецкий
математик-логик-физик-философ-языковед-юрист-дипломат
Леонард Эйлер (1707-1783) – математик-физик-механикастроном. Эйлер впервые подробно и обоснованно
изложил идею использования ЛД («круги Эйлера»)
«Л. Эйлер. Письма … к немецкой принцессе (1768 г.)»
Эрнст Шрёдер (1841-1902) – немецкий математик-логик
ДМ, лектор – Гонтовая Н.В.
5.
стр.5Чарлз Лютвидж Доджсон (1832-1898) – он же
Льюис Кэррол («Алиса в стране чудес») – английский
математик-логик-писатель, автор логических парадоксов.
Доджсон разработал удобную графическую технику решения
логических задач.
«Ч.Л.Доджсон. Символическая логика»
«Ч.Л.Доджсон. Логическая игра»
Доджсон сформулировал общие правила и алгоритмы для
получения правильного вывода из суждений, лишенных, на
первый взгляд, здравого смысла. Особого мастерства
достиг в составлении, анализе и решении таких логических
задач как «силлогизмы» и «сориты».
???
ДМ, лектор – Гонтовая Н.В.
6.
стр.6Джон Венн (1834 – 1923) – английский математик-логик
Диграммы Венна (разновидность логических диаграмм) –
способ схематического представления множеств и
операций над множествами.
Диаграммы Венна используются при решении любых
логических задач, в том числе для иллюстрации
логических высказываний в булевой алгебре, находят
применение в приложениях математической логики и
теории автоматов, в частности при решении задач,
связанных с использованием нейронных цепей.
Диаграммы Венна (ДВ) представляются в виде замкнутых
кривых (как правило, – кругов), ограничивающих области,
которым ставятся в соответствие те или иные множества.
ДМ, лектор – Гонтовая Н.В.
7.
стр.7На диаграммах Венна можно продемонстрировать
сходство, различия и взаимосвязи между понятиями,
категориями, группами и др. объектами, представленными
в виде множеств.
При этом сходство между отдельными множествами
(общие элементы множеств) представляется на ДВ
перекрывающимися частями кругов, а различия –
неперекрывающимся частями кругов.
Если множества не имеют общих элементов, то их
изображают на ДВ непересекающимися кругами.
На ДВ универсальное множество (…) изображают в виде
прямоугольника.
ДМ, лектор – Гонтовая Н.В.
8.
стр.8U - универсум
U
C
B
ДМ, лектор – Гонтовая Н.В.
9.
стр.91 2 3 4 5 6
ДМ, лектор – Гонтовая Н.В.
10.
см. Тема 2, п.9стр.10
ВИДЫ ПОДМНОЖЕСТВ
собственные
(или строгие)
несобственные
ДМ, лектор – Гонтовая Н.В.
11.
см. Тема 2, п.9стр.11
Множество В называют собственным подмножеством множества
при следующих условиях:
А
при этом множество А содержит хотя бы один элемент,
не принадлежащий подмножеству В.
Форма записи собственных подмножеств:
Говорят: «множество В строго включено в множество А»
Если множество В является собственным подмножеством множества А,
то мощность множества В меньше мощности множества А:
ДМ, лектор – Гонтовая Н.В.
12.
см. Тема 2, п.9стр.12
Подмножество В называют несобственным подмножеством
множества
А
при следующих условиях:
Форма записи несобственных подмножеств:
!!! Запись
более конкретна, чем
Записывая
, мы гарантируем, что
тогда как запись
.
,
не исключает случая
ДМ, лектор – Гонтовая Н.В.
13.
стр.13Примеры диаграмм Венна – см. рисунок 1, 2, 3.
!!! При всей своей наглядности, диаграммы Венна являются
всего лишь иллюстрацией (визуализацией) взаимного
соотношения множеств, но не могут использоваться в
качестве инструмента строгого формального
доказательства логических выводов.
ДМ, лектор – Гонтовая Н.В.
14.
стр.14не бывает
Рисунок 1 – «Памятка заказчику»
ДМ, лектор – Гонтовая Н.В.
15.
стр.15Рисунок 2 – Представления И. Канта о формах государства
ДМ, лектор – Гонтовая Н.В.
16.
стр.16Греческий
Латинский
Русский
Рисунок 3 – Что общего у русского, греческого и латинского
алфавитов (заглавные буквы)?
ДМ, лектор – Гонтовая Н.В.
17.
стр.17Греческий алфавит:
ДМ, лектор – Гонтовая Н.В.
18.
стр.18Инструменты рисования диаграмм Венна:
1
Создание диаграммы Венна с помощью
Gliffy
Gliffy – онлайн-программа для создания схем, графиков,
планов помещений, диаграмм (в том числе Venn diagrams,
BPMN, UML, UI Design, SWOT и др).
Запустить приложение можно без установки, просто зайти
на сайт
www.gliffy.com
Высокий уровень функционала при работе в Gliffy
достигается благодаря использованию Flash-технологии.
http://fevt.ru/load/gliffy_diagrams/104-1-0-839
ДМ, лектор – Гонтовая Н.В.
19.
стр.192
Создание диаграммы Венна с помощью приложения
Office (в виде графического элемента SmartArt
на основе макета диаграмм Венна)
https://support.office.com
ДМ, лектор – Гонтовая Н.В.
20.
стр.20ДМ, лектор – Гонтовая Н.В.
21.
2стр.21
Операции над множествами – это процедуры, с помощью
которых из заданных множеств можно сконструировать
новые множества (или другими словами – это способы
конструирования новых множеств на основе заданных
множеств).
ДМ, лектор – Гонтовая Н.В.
22.
стр.22В алгебре множеств используются пять стандартных операций:
№
1
Операция
Символ
обозначения
операции
объединение множеств
(или сумма множеств)
2
пересечение множеств (или произведение)
3
3
дополнение множества А
(или абсолютное дополнение множества А)
!!! данная операция определена только в том
случае, если задано некоторое универсальное
множество U
4
разность множеств
(или относительное дополнение множеств)
5
симметрическая разность
или
23.
Операциястр.23
1
Объединением (или суммой) множеств
А и В называется
х таких, что х принадлежит хотя бы
одному из 2-х множеств А или В :
множество элементов
В общем случае, объединением n множеств
называется множество , состоящее из элементов, входящих
хотя бы в одно из этих n множеств :
где
– обозначение логической операции «ИЛИ»
ДМ, лектор – Гонтовая Н.В.
24.
стр.24Пример 1:
Операция объединения множеств:
ДМ, лектор – Гонтовая Н.В.
25.
стр.25Пример 2:
Операция объединения множеств:
ДМ, лектор – Гонтовая Н.В.
26.
стр.26Свойства операции объединения множеств:
1) Объединение множеств коммутативно
(свойство коммутативности объединения множеств)
ДМ, лектор – Гонтовая Н.В.
27.
стр.272) Объединение множеств ассоциативно
(свойство ассоциативности объединения множеств)
а значит, при записи нескольких множеств,
соединённых знаком операции объединения,
скобки можно не использовать.
ДМ, лектор – Гонтовая Н.В.
28.
стр.283) Если
или
, то
ДМ, лектор – Гонтовая Н.В.
29.
стр.29Следствия из свойства 3 :
ДМ, лектор – Гонтовая Н.В.
30.
стр.304)* Дистрибутивность объединения множеств
относительно пересечения этих множеств
(или свойство дистрибутивности …)
Дистрибутивный (от лат.«distributivus» – распределительный)
!!! Благодаря свойству дистрибутивности можно раскрывать
скобки в сложных выражениях.
ДМ, лектор – Гонтовая Н.В.
31.
Операциястр.31
2
А и В
называется множество элементов х таких, что х принадлежит
и множеству А, и множеству В :
Пересечением (или произведением) множеств
Пересечением (или произведением)
n
множеств
называется множество
которого принадлежит каждому из этих
где
, каждый элемент
n множеств:
– обозначение логической операции «И»
ДМ, лектор – Гонтовая Н.В.
32.
стр.32Например:
Операция пересечения множеств:
ДМ, лектор – Гонтовая Н.В.
33.
стр.33Свойства операции пересечения множеств:
1) Пересечение множеств коммутативно
(свойство коммутативности пересечения множеств)
ДМ, лектор – Гонтовая Н.В.
34.
стр.342) Пересечение множеств ассоциативно
(свойство ассоциативности пересечения множеств)
а значит, при записи нескольких множеств,
соединённых знаком операции пересечения,
скобки можно не использовать.
ДМ, лектор – Гонтовая Н.В.
35.
стр.353) Если
или
, то
Все элементы множества А одновременно являются
элементами множества В
ДМ, лектор – Гонтовая Н.В.
36.
стр.36Следствия из свойства 3 :
ДМ, лектор – Гонтовая Н.В.
37.
стр.374)* Дистрибутивность пересечения относительно
объединения (или свойство дистрибутивности …)
!!! Не путать со свойством:
Дистрибутивность объединения относительно
пересечения
ДМ, лектор – Гонтовая Н.В.
38.
стр.385)* Дистрибутивность пересечения множеств
относительно симметрической разности
(или свойство дистрибутивности …)
Контроль:
Дистрибутивный (от лат.« … » – … )
!!! Благодаря свойству дистрибутивности можно … в сложных
выражениях.
ДМ, лектор – Гонтовая Н.В.
39.
стр.39!!! Приоритет выполнения операций:
если в выражении встречаются операции
и
то первой выполняется операция пересечения множеств
а затем – операция объединения множеств
.
,
Благодаря такому соглашению многие формулы
допускается записывать без скобок, и использовать их
только в тех случаях, когда порядок действий
необходимо изменить.
ДМ, лектор – Гонтовая Н.В.
40.
ОперацияЕсли
стр.40
3
U – универсальное множество, то дополнением множества
А называется
множество всех тех элементов, которые являются
элементами множества
U, но не входят в множество А :
Варианты обозначения операции «дополнение множеств»:
Например:
Пусть
U–
множество всех возможных десятичных цифр
Тогда если множество
то дополнением множества
А
является множество
ДМ, лектор – Гонтовая Н.В.
41.
стр.41U
ДМ, лектор – Гонтовая Н.В.
42.
стр.42Дополнение множества
А возможно не только до
универсального множества, но и до любого другого
множества
Q , при условии, что
где верхний индекс
при символе
(т.е.
)
означает, что операция дополнения осуществляется
до множества
Например, если
то
ДМ, лектор – Гонтовая Н.В.
43.
стр.43Свойства операции дополнения множеств:
1) Если
2) Если
3)
4)
5)
ДМ, лектор – Гонтовая Н.В.
44.
Операциястр.44
4
(или относительным дополнением множеств)
А и В называется называется множество
всех элементов х , принадлежащих множеству А, но
не входящих в множество В :
Разностью множеств
Аналогично определяется разность множеств
ВиА:
ДМ, лектор – Гонтовая Н.В.
45.
стр.45Например:
ДМ, лектор – Гонтовая Н.В.
46.
стр.46!!! Если
, то
!!!
То есть чтобы найти множество
, нужно
из множества А удалить все элементы,
принадлежащие множеству В.
В результате получится пустое множество.
ДМ, лектор – Гонтовая Н.В.
47.
стр.47!!!
Если
То есть при
, то
разность
с дополнением множества
совпадает
А до множества В.
ДМ, лектор – Гонтовая Н.В.
48.
стр.48!!! В тех случаях, когда разность множеств применяется к трём и
более множествам, необходимо использовать скобки, поскольку
то есть
разность множеств неассоциативна.
ДМ, лектор – Гонтовая Н.В.
49.
Операция5
стр.49
Симметрическая разность множеств А и В (иногда
называют «дизъюнктивная разность») – это множество вида:
ДМ, лектор – Гонтовая Н.В.
50.
стр.50Симметрическая разность может быть выражена через
разность множеств и операцию объединения множеств:
Например, если
то
ДМ, лектор – Гонтовая Н.В.
51.
стр.51Симметрическая разность может быть выражена через
операции дополнения, пересечения и объединения
множеств:
(1)
!!! В булевой алгебре операция
называется
«сложение по модулю 2» или «неравнозначность».
ДМ, лектор – Гонтовая Н.В.
52.
стр.52Свойства симметрической разности:
1) свойство коммутативности
2) свойство ассоциативности
3) свойство дистрибутивности пересечения множеств
относительно симметрической разности
ДМ, лектор – Гонтовая Н.В.
53.
стр.53Благодаря свойству дистрибутивности можно
раскрывать скобки в сложных выражениях.
Например:
ДМ, лектор – Гонтовая Н.В.
54.
стр.54!!! Операция симметрической разности множеств
не является дистрибутивной относительно
пересечения этих множеств.
(2)
Для доказательства утверждения (2) следует выразить
обе части неравенства (2) через операции
объединения, пересечения и дополнения,
и результаты преобразования множеств представить
в виде диаграмм Венна.
ДМ, лектор – Гонтовая Н.В.
55.
стр.55Преобразуем левую часть неравенства (2) в соответствии
с формулой (1):
ДМ, лектор – Гонтовая Н.В.
56.
стр.56Аналогично преобразуем правую часть неравенства (2):
ДМ, лектор – Гонтовая Н.В.
57.
стр.57Левая часть неравенства (2)
Правая часть неравенства (2)
На диаграммах Венна видно, что множества,
соответствующие левой и правой частям неравенства (2),
не совпадают, чтд.
ДМ, лектор – Гонтовая Н.В.
58.
стр.583
3.1 Законы де Моргана
Огастес (Августус) де Морган (1806 – 1871) – шотландский
математик-логик
Законы де Моргана устанавливают связь между операциями
объединения, пересечения и дополнения множеств.
ДМ, лектор – Гонтовая Н.В.
59.
стр.59Закон 1: Дополнение объединения множеств есть
пересечение дополнений этих множеств:
Закон 2: Дополнение пересечения множеств есть
объединение дополнений этих множеств:
Д/З: Найти иллюстрации законов де Моргана на
диаграммах Венна
ДМ, лектор – Гонтовая Н.В.
60.
стр.60Законы (правила) де Моргана применимы к произвольному
количеству множеств.
Например:
ДМ, лектор – Гонтовая Н.В.
61.
стр.613.2
Закон поглощения в двух формах:
дизъюнктивная форма закона поглощения:
конъюнктивная форма закона поглощения:
ДМ, лектор – Гонтовая Н.В.
62.
стр.623.3
Закон склеивания в двух формах:
дизъюнктивная форма закона склеивания:
конъюнктивная форма закона склеивания:
ДМ, лектор – Гонтовая Н.В.
63.
стр.63!!! Законы де Моргана, а также законы поглощения и
склеивания используют при упрощении аналитических
выражений, описывающих множества.
ДМ, лектор – Гонтовая Н.В.
64.
стр.644
Пример 1 (на упрощение с помощью з-на поглощения в ДФ):
Множество
Р представлено в виде выражения:
Пересечение
выражении два раза.
встречается в исходном
Введём обозначение
Тогда множество
Р принимает вид:
ДМ, лектор – Гонтовая Н.В.
65.
стр.65Согласно закону поглощения в ДФ имеем:
Следовательно,
Снова введём обозначение:
Тогда
Окончательный результат:
ДМ, лектор – Гонтовая Н.В.
66.
стр.66Пример 2 (на упрощение с помощью з-на поглощения в КФ):
Упростить выражение:
Введём обозначение:
Тогда множество S можно представить в виде:
Согласно з-ну поглощения в КФ получаем:
ДМ, лектор – Гонтовая Н.В.
67.
стр.67Пример 3 (на упрощение с помощью з-на склеивания):
ДМ, лектор – Гонтовая Н.В.