Глава II. ТЕОРИЯ МНОЖЕСТВ 1. Основные понятия теории множеств Множество – некоторая совокупность объектов, называемых элементами этого множества. Понятие множества является одним из исходных (аксиоматических) понятий математики, то есть не сводимое к другим понятиям, а значит и не имеющее определения. Однако, можно дать описание множества. Основатель теории множеств - Георг Кантор, немецкий математик,

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

1.1 Способы задания множеств Множества обозначают большими латинскими буквами: A, B, C,... Элементы множеств обозначают малыми латинскими буквами: a, b, c,... Если элемент a принадлежит множеству A, то пишут: a A Если элемент a не принадлежит множеству A, то пишут: a A

Способы задания множеств: 1. Множество А определяется перечислением всех своих элементов: V = {a, e, i, o, u, õ, ä, ö, ü} A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 2. Множество А определяется частичным перечислением своих элементов, которое выражает какую-то определенную закономерность: Z = {..., -2, -1, 0, 1, 2, 3...} – множество целых чисел N = {0, 1, 2, 3,...}- множество натуральных чисел Пример:

3. Множество А определяется как совокупность элементов из множества Т, которые обладают свойством : А = х Т (х), где запись (х) означает, что элемент х обладает свойством. B = {x N | x mod 2 = 0} – множество четных натуральных чисел C = {a N | a – простое число} – множество простых чисел D = {n N | n >1000 & n < 2000} – множество натуральных чисел больших 1000, но меньших 2000 Пример:

1.2 Операции над множествами (теоретико-множественные операции) Равенство множеств: Множества A и B равны, если они состоят из одних и тех же элементов: {1, 3, 5} = {5, 1, 3} Подмножество: Множество A является подмножеством множества B, A B, если каждый элемент множества A принадлежит в то же время и множеству B: A B x (x A x B ) А В диаграмма Эйлера - Венна

Свойства: 1. A (A A) 2.(A B)& (B A) A = B по определению равенства множеств: A = B ( x, x A x B & x, x В x А) Пустое множество является подмножеством любого множества: A ( A) Пустое множество: Множество, которое не содержит ни одного элемента называется пустым множеством и обозначается символом = { }. Свойство:

Универсальное множество I: V = {a, e, i, o, u, õ, ä, ö, ü} – множество гласных букв I = {множество всех букв} V Каждое множество A является подмножеством универсального множества: A ( A I ) Множество, которое содержит все возможные элементы, рассматриваемые в данном контексте. Пример: I

Дополнение множества: Элементы универсального множества I, не принадлежащие к множеству A, образуют дополнение множества A относительно универсального множества I, которое обозначают A I = {E,T,K,N,R,L,P} A = {L,P} A = {E,T,K,N,R} A A I A = {x I | x A} Пример: дни недели делятся на будничные и выходные дни

Объединение (сумма) множеств: A B = { x x A или x B } = A + B Пример: {1, 4, 7} {2, 4, 6, 7} = {1, 2, 4, 6, 7} Объединение множеств А и В состоит из элементов, принадлежащих хотя бы одному из множеств А или В: A B I

A B = { x x A и x B } = AB Пример: {1, 4, 7} {2, 4, 6, 7} = {4, 7} Пересечение (общая часть, умножение) множеств: Пересечение множеств А и В состоит из элементов, принадлежащих одновременно множеству А и множеству В: A B I A B

Непересекающиеся множества: Если A B =, то множества A и B непересекающиеся множества. {1, 4, 7} {2, 3, 6} = Пример:

A \ B = { x x A и x B } Пример: {1, 4, 7} \ {2, 4, 6, 7} = {1} Разность множеств: Разность множеств А и В состоит из элементов, принадлежащих множеству А и не принадлежащих множеству В: A B I

Симметрическая разность множеств: Симметрическая разность множеств A и B состоит из элементов принадлежащих множеству А или множеству В, но не принадлежащих множествам А и В одновременно: A B I A B = { x (x A) & (x B) (x A) & (x B) } Пример: {1, 4, 7} {2, 4, 6, 7} = {1, 2, 6}

Приоритет выполнения операций Сначала выполняются операции дополнения, затем пересечения, объединения, разности и симметрической разности которые имеют одинаковый приоритет. Последовательность выполнения операций может быть изменена скобками. Если в выражении есть знаки пересечения и объединения и нет скобок, то сначала выполняется операция пересечения, а потом – операция объединения (аналог сложению и умножению в арифметике).

Определение выражение теории множеств определяется следующим образом: 1.Все множества A, B,... - выражения теории множеств; 2.Пустое множество и универсальное множество I - выражения (константы) теории множеств; 3.Если A – выражение теории множеств, то A – тоже выражение теории множеств; 4.Если A и B - выражения теории множеств, то A B, A B, A \ B, A B – тоже выражения теории множеств. При помощи теоретико-множественных операций из множеств образуют выражения. 1.3 Выражение теории множеств

Свойства теоретико-множественных операций 2. Коммутативность: a) A B = B b) A B = B 3. Асоциативность: a) A ( B C ) = ( A B ) C b) A ( B C ) = ( A B ) C 4. Дистрибутивность: a) A ( B C ) = ( A B ) ( A C ) b) A ( B C ) = ( A B ) ( A C ) 5. Идемпотентность: a) A A = A b) A A = A 1.

6. Действия с константами: 7. Законы де Моргана: 8. Преобразование разности: A \ B = A B 9. Преобразования симметрической разности: a) A B = (A \ B) (B \ A) b) A B = (A B) \ (A B) 10. Законы склеивания: a) (A B) (A B) = A b) (A B) (A B) = A 11. Законы поглощения: a) A (A B) = A b) A (A B) = A d) A I = I e) A A = I f) A A = a) A = b) A = A c) A I = A

1.4 Нормальные формы Кантора (НФК) Нормальной формой Кантора (НФК) выражения теории множеств называют выражение, которое представляет собой пересечение объединений или объединение пересечений. Пересечение объединений в теории множеств аналогично КНФ в мат. логике. ( A B ) ( A C ) Дополнение в нормальной форме может быть применено только к отдельным множествам, не к их объединению или пересечению. Объединие пересечений в теории множеств аналогично ДНФ в мат. логике.

Совершенной нормальной формой Кантора (СНФК) выражения теории множеств называют такое пересечение объединений или объединение пересечений, где в каждом пересечении/объединении присутствует каждое множество выражения и точно один раз.

Задача 1. Доказать равенство выражений теории множеств: А) B) C) D)

Задача 2. Найти СНФК: А) B) C) D)

Задача 3. Найти МНФК: A) H(A,B,C)=(0,2,3,4,6) B) H(A,B,C,D)=(0,1,4,5,8,9,14) C) H(A,B,C,D)=(1,3,4,5,7,8,9,11,12,15)

A B C = A + B + C - A B - A C - B C + + A B C 1.5. Мощность множеств. Формулы Грассмана Мощностью конечного множества A называют количество (число) элементов этого множества и обозначают A. Формулы Грассмана позволяют найти мощность объединения множеств: A B = A + B - A B

Задача 4. Множество A состоит из натуральных чисел от 1 до Сколько элементов множества A не делится ни на 3, ни на 5. В группе 25 студентов. Для допуска к экзамену необходимо получить зачет по двум контрольным работам. По первой контрольной работе зачет получили 20 студентов, по второй 21. Сколько студентов (минимум и максимум) будет допущено к сдаче экзамена. Задача 5. Задача 6. Каждый студент физико-математического факультета интересуется физикой или математикой. Сколько студентов интересуется и физикой, и математикой, если математикой интересуется 84%, а физикой 64% студентов.

По результатам опроса 100 студентов 28 из них интересуется искусством, 30 музыкой, 42 спортом. 10 студентов интересуются и искусством, и спортом. 5 студентов интересуются и искусством, и музыкой. 8 студентов интересуются и спортом, и музыкой. 3 студента интересуется и искусством, и музыкой, и спортом. Сколько студентов интересуются только спортом? Только музыкой? Ничем из перечисленного? Задача 7.

1. A B C 2. A B C 3. A B C 4. A B C 5. A B C 6. A B C 7. A B C 8. A B C 8 возможных областей представимых диаграммой Венна для трёх множеств

1.6. Прямое произведение множеств Прямое произведение множеств А и В состоит из упорядоченных пар элементов этих множеств А x B = { (a, b) | (a A) & (b B) } Свойства: 1.A x B B x A 2.| A x B | = | A | x | B | Пример: A = { a,b,c } B = {1,2} A x B = { (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }

Множество всех подмножеств множества A называется булеаном A или степенью множества A, и обозначается Р(А) или 2 A. A x B x C x D x … x Y = {(a, b, c, d, …, y) | a A, b B,..., y Y} Прямое произведение нескольких множеств: A x А x ……. x А = А k – Декартова степень множества А k раз R x R = R 2 – ху-плоскость R x R x R = R 3 – xyz-пространство Пример: