Информатика. 10 класса. Босова Л.Л. Оглавление
§ 17. Некоторые сведения из теории множеств
17.1. Понятие множества
С понятием множества вы познакомились на уроках математики ещё в начальной школе, а затем работали с ним при изучении математики и информатики в основной школе.
Множество — это совокупность объектов произвольной природы, которая рассматривается как единое целое.
Примерами множеств могут служить: множество всех учеников вашего класса, множество всех жителей Санкт-Петербурга, множество всех натуральных чисел, множество всех решений некоторого уравнения и т. п.
Множества принято обозначать прописными буквами латинского алфавита (А, В, С, …). Объекты, входящие в состав множества, называются его элементами.
Множество можно задать следующими способами:
1) перечислением всех его элементов;
2) характеристическим свойством его элементов.
В первом случае внутри фигурных скобок перечисляются все объекты, составляющие множество. Каждый объект, входящий в множество, указывается в фигурных скобках лишь один раз.
Например, запись М = {1, 3, 5, 7, 9} означает, что множество М состоит из чисел 1, 3, 5, 7 и 9. Точно такой же смысл будет иметь запись М = {3, 1, 5, 9, 7}. Иначе говоря, порядок расположения элементов в фигурных скобках значения не имеет. Важно точно указать, какие именно объекты являются элементами множества.
Например:
• число 5 является элементом множества М: 5 ? М 1);
• число 4 не является элементом множества М: 4 ? М.
1) Символ ? называется знаком принадлежности.
Это же множество можно задать с помощью характеристического свойства образующих его элементов — такого свойства, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, который ему не принадлежит. В нашем примере можно говорить о множестве натуральных однозначных нечётных чисел.
В рассматриваемом множестве М содержится 5 элементов. Это обозначают так: |М| = 5. Можно составить множество, содержащее любое число элементов. Например, множество всех корней уравнения х2 — 4х — 5 = 0 конечно (два элемента), а множество всех точек прямой бесконечно. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом ?.
Первый способ задания множеств применим только для конечных множеств, да и то при условии, что число элементов множества невелико. Вторым способом можно задавать как конечные, так и бесконечные множества.
Из некоторых элементов множества М можно составить новое множество, например Р: Р = {1, 3, 5}.
Если каждый элемент множества Р принадлежит множеству М, то говорят, что Р есть подмножество М, и записывают: Р ? М.
Само множество М является своим подмножеством, т. к. каждый элемент М принадлежит множеству М. Пустое множество также является подмножеством М.
Работая с объектами какой-то определённой природы, всегда можно выделить «самое большое» или универсальное множество, содержащее все возможные подмножества. Пусть А — множество чётных чисел, В — множество натуральных чисел, С — множество чисел, кратных пяти.
Тогда самым большим множеством, содержащим в себе множества А, В и С, а также другие подобные множества, будет множество целых чисел. Универсальное множество будем обозначать буквой U.
Для наглядного изображения множеств используются круги Эйлера (рис. 4.1). Точки внутри круга считаются элементами множества.
Рис. 4.1. Графическое изображение множеств: 1) х ? М, 2) х ? М
17.2. Операции над множествами
Над множествами, как и над числами, производят некоторые операции.
Пересечением двух множеств X и Y называется множество их общих элементов.
Пересечение множеств обозначают с помощью знака ?: Х ? У. На рисунке 4.2 закрашено множество X ? Y.
Рис. 4.2. Графическое изображение множества X ? Y
Пусть множества X и Y состоят из букв:
X = {ш к, о, л, а};
У = {у, р, о, к}.
Эти множества имеют общие элементы: к, о.
X ? У = { к, о}.
Множества М и X не имеют общих элементов, их пересечение — пустое множество:
М ? Х = ?.
Пересечение множеств М и Р есть множество Р, а пересечение множеств М и М есть множество М:
М ? Р = Р;
М ? М = М.
Объединением двух множеств X и Y называется множество, состоящее из всех элементов этих множеств и не содержащее никаких других элементов.
Объединение множеств обозначают с помощью знака ?: X ? У.
На рисунке 4.3 закрашено множество X ? У.
Рис. 4.3. Графическое изображение множества X ? У
Для наших примеров:
Х ? У = {ш, к, о, л, а, у, р};
М ? X = {1, 3, 5, 7, 9, ш, к, о, л, а};
М ? Р = М; М ? М = М.
Подумайте, возможно ли равенство: А ? В = А ? В.
Пересечение и объединение выполняются для любой пары множеств. Третья операция — дополнение — имеет смысл не для всех множеств, а только тогда, когда второе множество является подмножеством первого.
Пусть множество Р является подмножеством множества М. Дополнением Р до М называется множество, состоящее из тех элементов М, которые не вошли в Р.
Дополнение Р до М обозначают
= {7, 9}.
Дополнение М до М есть пустое множество, дополнение пустого множества до М есть
Особый интерес представляет дополнение некоторого множества В до универсального множества U. Например, если В — это множество точек, принадлежащих некоторому отрезку, то его дополнением
до универсального множества U, которым в данном случае является множество всех точек числовой прямой, является множество точек, не принадлежащих данному отрезку.
В общем случае можем записать:
(рис. 4.4)
Рис. 4.4. Дополнение множества В до универсального множества
На рисунке 4.5 видно, что множество А ? В будет совпадать с универсальным, если А будет совпадать с множеством
или содержать его в качестве подмножества. В первом случае, т. е. при А =
мы имеем дело с минимальным множеством А, таким что A ? В = U.
Рис. 4.5. Выбор такого множества А, что А ? В = U
Каким должно быть множество А для того, чтобы множество
? В совпадало с универсальным множеством?
Для ответа на этот вопрос воспользуйтесь рисунком 4.6.
Рис. 4.6. Выбор такого множества А, что ? В = U
17.3. Мощность множества
Мощностью конечного множества называется число его элементов.
Мощность множества X обозначается |Х|.
В рассмотренных выше примерах |Х| = 5, |М| = 5.
Число элементов объединения двух непересекающихся множеств равно сумме чисел элементов этих множеств. Так, в объединении множеств М и X содержится 10 элементов: |М ? Х| = 10.
Если же множества пересекаются, то число элементов объединения находится сложнее. Так, X состоит из 5 элементов, множество Y — из 4, а их объединение — из 7. Сложение чисел 5 и 4 даёт нам число 9. Но в эту сумму дважды вошло число элементов пересечения. Чтобы получить правильный результат, надо к числу элементов X прибавить число элементов Y и из суммы вычесть число элементов пересечения. Полученная формула подходит для любых двух множеств: |Х ? Y| = |Х| + |Y| — |Х ? Y|. Это частный случай так называемого принципа включений-исключений.
Принципом включений-исключений называется формула, позволяющая вычислить мощность объединения (пересечения) множеств, если известны их мощности и мощности всех их пересечений (объединений).
Для случая объединения трёх множеств формула имеет вид:
Аналогичные формулы справедливы и для пересечения множеств:
Пример. В зимний оздоровительный лагерь отправляется 100 старшеклассников. Почти все они увлекаются сноубордом, коньками или лыжами. При этом многие из них занимаются не одним, а двумя и даже тремя видами спорта. Организаторы выяснили, что всего кататься на сноуборде умеют 30 ребят, на лыжах — 28, на коньках — 42. Всего умением кататься на лыжах и сноуборде из них могут похвастаться 8 ребят, на лыжах и коньках — 10, на сноуборде и коньках — 5, но только трое из них владеют всеми тремя видами спорта.
Сколько ребят не умеет кататься ни на сноуборде, ни на лыжах, ни на коньках?
Обозначим через S, L и К множества сноуборд истов, лыжников и любителей коньков соответственно. Тогда |S| = 30, |L| = 28 и |К| = 42. При этом |S ? L| = 8, |К ? L| = 10, |S ? К| = 5, |S ? L ? K| = 3.
Объединение множеств S, L и К — это множество ребят, увлекающихся хотя бы каким-то видом спорта.
По формуле включений-исключений находим:
|S ? L ? К| = 30 + 28 + 42 — 8 — 10 — 5 + 3 = 80.
Таким образом, из 100 старшеклассников 20 не умеют кататься ни на сноуборде, ни на лыжах, ни на коньках.
САМОЕ ГЛАВНОЕ
Множество — это совокупность объектов произвольной природы, которая рассматривается как единое целое.
Пересечением двух множеств X и Y называется множество их общих элементов.
Объединением двух множеств X и Y называется множество, состоящее из всех элементов этих множеств и не содержащее никаких других элементов.
Пусть множество Р является подмножеством множества М. Дополнением Р до М называется множество, состоящее из тех элементов М, которые не вошли в Р.
Мощностью конечного множества называется число его элементов.
Формула включений-исключений позволяет вычислить мощность объединения (пересечения) множеств, если известны их мощности и мощности всех их пересечений (объединений).
Вопросы и задания
3. Пусть А, В и С — некоторые множества, обозначенные кругами, U — универсальное множество.
§ 16. Кодирование звуковой информации
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И АЛГЕБРЫ ЛОГИКИ
§ 17. Некоторые сведения из теории множеств
§ 18. Алгебра логики