1 Теория множества

1. Дискретная математика

Дискретный – это прерывистый, дробный,
состоящий из отдельных частей
(Толковый словарь русского языка под
редакцией Т. Ф. Ефремовой).

2.

Дискретная математика – направление в
математике, объединяющее отдельные её разделы,
ранее сформированные как самостоятельные
теории.
• Разделы дискретной математики:
• математическая логика;
• теория множеств;
• предикаты и кванторы;
• логические функции;
• теория алгоритмов;
• теория графов;
• комбинаторика и т.д.

3. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

4.

КАНТОР (Cantor) Георг
(1845—1918) немецкий математик, логик,
теолог, создатель теории
бесконечных множеств,
оказавшей определяющее
влияние на развитие
математических наук на
рубеже 19–20 вв.
Теория множеств появилась
на свет 7 декабря 1873 г.

5. Понятие множества

!
Множество
—
совокупность
объектов
произвольной природы, которая рассматривается
как единое целое.

6. Стандартные обозначения

Множества принято обозначать прописными буквами латинского
алфавита (A, B, C, …). Объекты, входящие в состав множества,
называются его элементами и обозначаются строчными
латинскими буквами (a,b,c,…).
Описание
Обозначение
x - элемент множества M
(x принадлежит множеству M)
x∈M
x не является элементом
множества М (x не принадлежит M)
x∉M
Например, если А – множество решений уравнения,
(x − 3)(x − 5)( x − 9) = 0, то 3 A, а 7 A.

7.

• Множество, не содержащее элементов,
называется пустым множеством и
обозначается .
Примеры:
• Множество сто этажных жилых домов
Нижнего Новгорода.
• Множество студентов, обучающихся в
РАНХиГС, возраст которых менее десяти лет .
• Множество действительных корней
2
x
квадратного уравнения + 3x + 10 = 0 - пустое
множество (дискриминант данного уравнения
меньше нуля D = 32 − 4 10 = −31 0) .

8. Виды множеств

Множество, содержащее
конечное число элементов,
называется конечным
множеством.
Если множество содержит
бесконечное число
элементов, то оно называется
бесконечным множеством.
Примеры:
множество дней в неделе,
месяцев в году
Примеры:
множество натуральных
чисел,
точек на прямой
Число элементов множества А называется мощностью
множества и обозначается А
Пример: 1) В={1,2,3}, | В |=3; 2) | Z |=∞ ; 3) | |=0.

9. Среди перечисленных ниже множеств укажите конечные и бесконечные множества:

а) множество чисел, кратных 11;
б) множество делителей числа 5;
в) множество океанов;
г) множество натуральных чисел;
д) множество рек Нижегородской области;
е) множество корней уравнения х - 3 = 10;
ж) множество решений неравенства х + 2 < 3.

10. Способы задания множества

1)
Перечисление
всех
элементов
множества, например, множество однозначных
неотрицательных чисел
X = 0,1,2,3,...9 .
Множества часто рассматриваются как
«неупорядоченные совокупности элементов»,
хотя иногда полезно подчеркнуть, что,
например
X = 0,1,2 = 2,1,0 = 2,0,1 .
10

11. Способы задания множества

2) Характеристическое свойство – это
свойство, которым обладают все элементы
данного множества. В этом случае пишут:
A = x p(x)
Читается «множество элементов х,
обладающих свойством р»
длинная вертикальная палка | или : выражает
словесный оборот «которые», «таких, что».

12. Примеры

1) Множество всех целых чисел, больших 10 но не
превосходящих 20.
• перечисление элементов A = 11,12,13,14,15,16,17,18,19, 20
• Характеристическое свойство A = x 10 x 20 .
2) Множество всех целых чисел, входящих в область
2
определения функции y = 16 − x .
• перечислением элементов A = − 4, − 3, − 2, − 1, 0,1, 2, 3, 4
• характеристического свойства A = x 16 − x 0 .
3) Если область D - круг с центром в точке (3;5) и
радиуса 4, то D =. (x; y ) R (x − 3) + ( y − 5) 16
2
2
2
2

13. Подмножество

Множество А называют подмножеством множества В
(обозначается А⊂ В ), если каждый элемент множества А
является также элементом множества В.
Само множество В
является своим
подмножеством:
В В
В
А
Пустое множество является
подмножеством В:
∅⊂В
А⊂ В

14.

Рассмотрим числовые множества:
N
Z
I
Q
R
Множество
натуральных
чисел.
Множество
целых чисел.
Множество
иррациональ
ных чисел.
Множество
рациональных чисел.
Множество
действитель
ных чисел.
Примеры
элементов
множества:
Примеры
элементов
множества:
Примеры
элементов
множества:
Примеры
элементов
множества:
Примеры
элементов
множества:

15.

16. Задача.

Дано множество { -8,1; √2; 17/7}. Перечислите
все его подмножества, состоящие из двух чисел:
а)разного знака
б)положительных
в)рациональных
г)среди которых есть иррациональное число

17. Задача.

На числовой прямой изобразите
следующие промежутки:
А = (-√2; 1), В = [0; 1,9), С = [-1,5; 200/101].
Верно ли, что:
а)
б)
А В
с)
С А
В С
г)
А С

18.

Множество
всех
подмножеств
данного
множества M называется булеан (обозначается
В(М)).
Если множество состоит из n элементов, то число
n
2
его подмножеств равно .
Пример.
M = y, x, a , n = 3, B(M ) = 23 = 8,
B(M ) = , y
, x
, a
, y, x
, x, a
, y, a
, y, x, a .

19.

Универса́льное мно́жество (универсум) —
множество, содержащее все объекты и все
множества.
U
А

20.

Множества А и В называют равными
( A = B ), если каждый элемент множества А
является
одновременно
элементом
множества В и наоборот,
т.е. если A B и B A .
20

21.

«Парадокс брадобрея»
Одному солдату было приказано брить
тех и только тех солдат его взвода,
которые сами себя не бреют.
Неисполнение приказа в армии, как
известно, тягчайшее преступление.
Однако возник вопрос, брить ли этому
солдату самого себя. Если он побреется,
то его следует отнести к множеству
солдат, которые сами себя бреют, а таких
брить он не имеет права. Если же он себя
брить не будет, то попадёт во множество
солдат, которые сами себя не бреют, а
таких солдат согласно приказу он обязан
брить.

22. Основные операции над множествами Объединение множеств

Множество,
состоящее
из
элементов,
принадлежащих хотя бы одному из двух множеств
А или В называется объединением множеств А и В
и обозначается A B .
A∪∅=A
B
A
А∪В
Пример: А={1,2,6,7}, B={2,4,6,8}, тогда
А В ={1,2,4,6,7,8}
A подмножество множества
B:
A∪B=B
Идемпотентность
А∪А=А

23. Пересечение множеств

Множество, состоящее из элементов, принадлежащих
множеству А и множеству В одновременно называется
пересечением множеств А и В и обозначается А ∩ В.
А
В
А∩∅=∅
А∩В
А подмножество множества
В:
А∩В=А
Пример: А={1,2,6,7}, B={2,4,6,8}, тогда
А В ={2}
Идемпотентность
А ∩ А= А

24. Разность множеств

Множество,
состоящее
из
элементов,
принадлежащих
множеству
А,
но
не
принадлежащих множеству В называется разностью
множеств А и В и обозначается А\ В.
А
В
А\В
Пример:
А={1,2,6,7},B={2,4,6,8},
тогда
А\В={1,6,7},
В\А={4,6,8}

25.

Симметрической разностью множеств
Симметрической разностью множеств А и В
называется множество, состоящее из элементов
принадлежащих
множеству
А,
но
не
принадлежащих множеству В, а также из элементов,
принадлежащих множеству В но не принадлежащих
множеству А. Обозначается A B.
В
А
A B
A B = ( A \ B) (B \ A)
Пример: А={1,2,6,7}, B={2,4,6,8},
тогда
A B={1,4,7,8}

26.

Дополнение множества
Если A U , то дополнением множества А до
множества U называется множество элементов,
которые принадлежат множеству U, но не
принадлежат множеству А. Обозначается A.
U
А
A

27.

Пример 1. Найти если
A B.
A B, A B, A,\ B
A = a, b, c, f , h, k , m, n B = a, b, d , g, h, k , m
Пример 2.Найти X Y , X Y , X \ Y если
Х – множество решений уравнения
(5x2 + 9x − 2)(x 2 − 25) = 0 .
Y – множество всех простых чисел от 1 до 11.

28.

Для операций над множествами справедливы
следующие свойства:
1)Коммутативность объединения и пересечения
A B = B A
A B = B A
2)Ассоциативность объединения и пересечения
(A B) C = A (B C )
A (B C ) = ( A B ) C
3) Дистрибутивность пересечения относительно
объединения и объединения относительно
пересечения
A (B C ) = ( A B ) ( A C )
A (B C ) = ( A B ) ( A C )