Множества и отношения

Содержание

Слайд 2


Множества
Основные определения
Алгебра множеств
Представление множеств

Вопросы

Множества Основные определения Алгебра множеств Представление множеств Вопросы

Слайд 3

Множества. Основные определения
Множество - это совокупность определенных различимых объектов, для каждого

Множества. Основные определения Множество - это совокупность определенных различимых объектов, для каждого
из которых можно установить, принадлежит этот объект данному множеству или нет. Различимые объекты называются элементами множества.
Обозначения «наивной» теории множеств
а ∈ А - элемент а принадлежит множеству A
а ∉ A - элемент a не принадлежит A

Слайд 4

Множества. Основные определения

Способы задания множеств
прямым перечислением всех элементов A = {a,

Множества. Основные определения Способы задания множеств прямым перечислением всех элементов A =
b, c, … , z }
множество простых чисел, не превосходящих 10: { 2, 3, 5, 7} ;
множество всех месяцев года : { январь, февраль, … , декабрь };
множество всех натуральных чисел: ℕ = {1,2,3, …}.
характеристическим предикатом A = {a | P(a) }
множество целых степеней двойки: S2 = {s | s = 2k, k ∈ ℕ };
множество четных чисел: { x | x – четно, x ∈ℤ }.
порождающей процедурой A = {a | a:=f }
множество однозначных чисел: N1 = { n | for n:= 1 to 9 do write(n); };
множество чисел Фибоначчи: F = { fi | f1 = f2 = 1; fn+2 = fn + fn+1 , i ∈ℕ }.

Слайд 5

Множества. Основные определения
Универсальное множество или универсум есть множество U, состоящее из

Множества. Основные определения Универсальное множество или универсум есть множество U, состоящее из
элементов всех рассматриваемых множеств.
Пример: Пусть A = { 1, 3, 5 }, D = { 2, 3, 8 }, N = { 4 }.
Тогда U = { 1, 2, 3, 4, 5, 8 }.
Пустое множество – это множество без элементов.
∅ = { }
Семейство - множество, элементами которого являются множества.
Пример: Пусть A = { 1, 3, 5 }, D = { 2, 3, 8 }.
Тогда N = { A, D, 5 } = { { 1 ,3 ,5 }, { 2 ,3 ,8 }, 5 }.

Слайд 6

Множества. Основные определения

Мультимножество – совокупность элементов, в которые элементы входят по

Множества. Основные определения Мультимножество – совокупность элементов, в которые элементы входят по
нескольку раз.
расписание занятий – один и тот же предмет повторяется несколько раз;
штатное расписание – одна и та же должность повторяется несколько раз.
Обозначения:
X = 〈 a, … , a; b, … , b; … ; z, … , z 〉 = [an1, bn2, … , znk] – мультимножество
n1 n2 nk
A = {a, b, c, … , z} – носитель мультимножества
n1, n2 ,…, nk – показатели элементов мультимножества
Пример:
Пусть A = {a, b, c}. Тогда X = [a0,b3,c4] = 〈 b, b, b; c, c, c, c 〉

Слайд 7

Множества. Алгебра множеств

Сравнение множеств
Множество A является подмножеством множества B, если любой элемент

Множества. Алгебра множеств Сравнение множеств Множество A является подмножеством множества B, если
множества A принадлежит множеству B
A ⊂ B ⟺ ( x ∈ A ) ⇒ ( x ∈ B ).
Говорят: множество A содержится в множестве B
(множество B включает множество A).
Два множества равны, если они являются подмножествами друг друга
A = B ⟺ A ⊂ B и B ⊂ A
Свойства: 1. ∀A ( A ⊂ A );
2. ∀A, B (( A ⊂ B и B ⊂ A ) ⇒ ( A = B ));
3. ∀A, B, C (( A ⊂ B и B ⊂ С ) ⇒ ( A ⊂ С )).

Слайд 8

Множества. Алгебра множеств

Мощность множеств. Сравнение мощностей
Множество A называется собственным подмножеством множества B,

Множества. Алгебра множеств Мощность множеств. Сравнение мощностей Множество A называется собственным подмножеством
если A ⊂ B и A ≠ B .
Равномощными называются множества, между элементами которых можно установить взаимно-однозначное соответствие, т.е. |A| = |B| ⟺ A ~ B.
Пример: Пусть ℕ - множество натуральных чисел,
N2 - множество четных натуральных чисел. Очевидно, N2 ⊂ ℕ и N2 ≠ ℕ .
ℕ: 1 2 3 … n …
⇒ ℕ ~ N2 или |ℕ | = | N2 |.
N2 : 2 4 6 … 2n …
Свойства: 1. ∀A (|A| = |A| );
2. ∀A, B (|A| = |B| ⇒ |B| = |A| );
3. ∀A, B, C ((|A| = |B| и |B| = |C|) ⇒ (|A| = |C|)).

Слайд 9

Множества. Алгебра множеств

Мощность множеств. Сравнение мощностей
Конечным называется такое множество A, у которого

Множества. Алгебра множеств Мощность множеств. Сравнение мощностей Конечным называется такое множество A,
не существует равномощного собственного подмножества, т.е.
∀B (( B ⊂ A и |B| = |A|) ⇒ ( B = A ))
Обозначение: |A| < ∞
Бесконечным называется такое множество, которое равномощно некоторому своему собственному подмножеству, т.е.
∃B ( B ⊂ A и |B| = |A| и B ≠ A )
Обозначение: |A| = ∞

Слайд 10

Множества. Алгебра множеств

Операции над множествами
Объединение A ∪ B = { x | x

Множества. Алгебра множеств Операции над множествами Объединение A ∪ B = {
∈ A или x ∈ B }
Пересечение A ∩ B = { x | x ∈ A и x ∈ B }
Разность A \ B = { x | x ∈ A и x ∉ B }
Симметрическая разность
A ∆ B = (A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A)
Дополнение A = { x | x ∉ A } = U \ A, где U – универсум.

Слайд 11

Множества. Алгебра множеств

Объединение
A ∪ B = { x | x ∈ A

Множества. Алгебра множеств Объединение A ∪ B = { x | x
или x ∈ B }
Свойства
Идемпотентность А ∪ А = A
Коммутативность А ∪ В = В ∪ А
Ассоциативность А ∪ (В ∪ С) = (А ∪ В) ∪ С = А ∪ В ∪ С
свойство нуля А ∪ ∅ = А
свойство единицы А ∪ U = U

Слайд 12

Множества. Алгебра множеств

Пересечение
A ∩ B = { x | x ∈

Множества. Алгебра множеств Пересечение A ∩ B = { x | x
A и x ∈ B}
Свойства
идемпотентность А ∩ А = A
коммутативность А ∩ В = В ∩ А
ассоциативность А ∩ (В ∩ С) = (А ∩ В) ∩ С = А ∩ В ∩ С
свойство нуля А ∩ ∅ = ∅
свойство единицы А ∩ U = А

Слайд 13

Множества. Алгебра множеств

Разность
B \ A = { x | x ∈ B

Множества. Алгебра множеств Разность B \ A = { x | x
и x ∉ A}
Свойства
свойства нуля А \ ∅ = А ∅ \ А = ∅
свойства единицы А \ U = ∅ U \ А = A

Слайд 14

Множества. Алгебра множеств

Симметрическая разность
A ∆ B = (A ∪ B) \ (A

Множества. Алгебра множеств Симметрическая разность A ∆ B = (A ∪ B)
∩ B) = (A \ B) ∪ (B \ A)
Свойства
коммутативность А ∆ В = В ∆ А
Ассоциативность А ∆ (В ∆ С) = (А ∆ В) ∆ С = А ∆ В ∆ С
свойство нуля А ∆ ∅ = А
свойство единицы А ∆ U = А

Слайд 15

Множества. Алгебра множеств

Разбиения. Покрытия
Семейство множеств F = { Fi } называется покрытием

Множества. Алгебра множеств Разбиения. Покрытия Семейство множеств F = { Fi }
множества B, если для любого элемента множества B найдется подмножество Fi, которому он принадлежит, т.е.
∀ x ∈ B ( ∃Fi ( x ∈ Fi ))
Покрытие называется разбиением множества B, если :
1. ∀i ( Fi ⊂ B )
2. ∀ i,j  ( i ≠ j ⇒ Fi ∩ Fj = ∅ ) , т.е. никакие два подмножества покрытия не пересекаются
Пример: Пусть A = {1, 2, 3 }. Тогда 
{{1, 2}, {2, 3}, {3, 1}} – покрытие множества A, но не разбиение;
{{1}, {2}, {3}} – разбиение множества A;
{{∅}, {1}, {3}} - не является ни покрытием, ни разбиением.

Слайд 16

Множества. Алгебра множеств

Булеан
Булеаном множества А называется множество всех подмножеств множества А и

Множества. Алгебра множеств Булеан Булеаном множества А называется множество всех подмножеств множества
обозначается как 2A или P(А).
Обозначение: 2A = P(A) = { B | B ⊂ A }
Теорема: Если множество A - конечно, то |2A| = 2|A|.
Пример:
Если A = { 1, 2, 3 }, то
2A = { ∅, {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3}, {1, 2, 3} }.
Если A = ∅, то
|2A| = 2|A| = 21 = 2, т.е. 2A = {∅, {∅}}.

Слайд 17

Множества. Алгебра множеств
Алгебра множеств – множество всех подмножеств множества U с операциями

Множества. Алгебра множеств Алгебра множеств – множество всех подмножеств множества U с
пересечения, объединения, разности и дополнения.
Обозначение: 2U =
U – носитель алгебры
{ ∩, ∪, \, ¬ } – сигнатура алгебры

Слайд 18

Множества. Алгебра множеств

Законы алгебры множеств
Дистрибутивный A ∩ (B ∪ C) = (A ∩

Множества. Алгебра множеств Законы алгебры множеств Дистрибутивный A ∩ (B ∪ C)
B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Закон поглощения (A ∩ B) ∪ A = A
(A ∪ B) ∩ A = A
Законы де Моргана (A ∪ B) = A ∩ B
(A ∩ B) = A ∪ B
Выражение для разности A \ B = A ∩ B
Закон двойного отрицания A = A

Слайд 19

Массив
Связанный список
Двоичный вектор

Представление множеств

Массив Связанный список Двоичный вектор Представление множеств

Слайд 20

Массив – простейшее представление конечного множества,
Плюсы:
прямой доступ к любому элементу (li =

Массив – простейшее представление конечного множества, Плюсы: прямой доступ к любому элементу
l1 + (i - 1)d)
Минусы:
количество элементов ограничено размером массива;
время поиска элемента определяется размером массива;
для хранения массива необходимо выделять память;
более сложная реализация операций над множествами (изменение/удаление элемента влечет перемещение многих элементов).

Представление множеств

Слайд 21

Характеристический вектор – разновидность последовательного распределения
Длина вектора – мощность универсума |U|
Пример: U =

Характеристический вектор – разновидность последовательного распределения Длина вектора – мощность универсума |U|
{1, 2, 3, 4, 5, 6 , 7, 8, 10}
P = {2, 3, 5, 7} – множество простых чисел
vp = (0 1 1 0 1 0 1 0 0) – вектор множества P
Плюсы:
легко изменять список (место каждого элемента известно)
Минусы:
ограниченность количества элементов множества;
необходимость упорядочивания элементов множества;
неэкономичность в случае «редкого» распределения.

Представление множеств

Слайд 22

Список – более гибкое представление конечного множества,
Плюсы:
легко изменять список – работа с

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

Представление множеств

Слайд 23

Словари (справочники)
Хэш – таблицы (системы представителей)
Очереди с приоритетами (задачи планирования)
Базы данных (знаний)

Применение

Словари (справочники) Хэш – таблицы (системы представителей) Очереди с приоритетами (задачи планирования)
множеств
Имя файла: Множества-и-отношения.pptx
Количество просмотров: 44
Количество скачиваний: 0