Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
§12. Множества и логика.
Множества
Ключевые слова:
• множество • дополнение • пересечение • объединение • диаграмма Эйлера-Венна • поисковый запрос
Множество — некоторый набор элементов, каждый из которых отличается от остальных. Множество может состоять из конечного числа элементов (например, множество букв русского алфавита), бесконечного числа элементов (например, множество натуральных чисел) или вообще быть пустым (например, множество слонов, живущих на Северном полюсе). Пустое множество обозначается символом ?. Множества, с которыми работает компьютер, не могут быть бесконечными, потому что его память конечна.
Чтобы определить множество, мы можем перечислить все его элементы. Например, множество, состоящее из Васи, Пети и Коли, можно записать так: {Вася, Петя, Коля}.
Запишите в виде перечисления элементов:
а) множество натуральных чисел на отрезке [-5; 5];
б) множество чётных однозначных чисел;
в) множество целых чисел, делящихся на 4, на отрезке [0; 22];
г) множество простых чисел на отрезке [5; 20].
Можно задать множество иначе: определить условие {логическое выражение), которое должно быть истинным для всех элементов множества и ложным для всех элементов, не входящих во множество. Например, можно ввести множество драконов с пятью зелёными хвостами или множество чисел, делящихся на 11.
Запишите (словами или в символьном виде) условие, которое определяет множество:
а) {1, 3, 5, 7, 9};
б) {5, 6, 7};
в) {а, е, ё, и, о, у, ы, э, ю, я};
г) {17, 34, 51, 68, 85};
д) {00, 01, 10, 11};
е) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С};
ж) отрезок [0; 1].
Хотя множество — это математическое понятие, с множествами мы имеем дело каждый раз, когда обращаемся к поисковой системе в Интернете: ведь нас интересует множество страниц, на которых есть нужная нам информация. Задать такое множество перечислением элементов невозможно: во-первых, мы не знаем адресов этих страниц; во-вторых, их очень много. Поэтому для того, чтобы задать нужное нам множество, требуется написать поисковый запрос — логическое выражение, которое его определяет.
Диаграммы Эйлера-Венна
Множества удобно изображать графически, в виде диаграмм. Их называют диаграммами Эйлера—Венна в честь авторов этой идеи — математика Леонарда Эйлера и логика Джона Венна. На такой диаграмме каждому множеству соответствует какая-то область (круг, прямоугольник и др.) — рис. 2.34. Все элементы внутри этой области принадлежат множеству, все элементы вне области — не принадлежат.
Рис. 2.34
Вы уже знаете, что множество можно задать условием (логическим выражением), которое выполняется для всех элементов множества и не выполняется для всех элементов, не входящих в него. Дальше для сокращения записи мы будем вместо слов «множество, для которого выполняется условие А» писать просто «множество А». Тогда множество «НЕ А» на диаграмме — это все точки за границами круга (рис. 2.35).
Рис. 2.35
Такое множество называется дополнением множества А до универсального множества U, включающего все элементы некоторого класса. Например, если мы рассматриваем только целые числа и А — это множество чётных целых чисел, то А — множество нечётных целых чисел.
Можно считать, что дополнение А — это «разность» между универсальным множеством U и множеством А, т. е. все элементы из U, которые не входят в А.
Для каждого из следующих множеств выберите универсальное множество и запишите дополнение А:
а) А = {1, 3, 5, 7, 9};
б) А = {а, е, ё, и, о, у, ы, э, ю, я};
в) А = {17, 34, 51, 68, 85};
г) А = {00, 10};
д) А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С};
е) А = отрезок [0; 1].
На диаграмме можно изображать несколько множеств, каждому из них соответствует своя область (круг). Круги на диаграмме могут пересекаться. Элементы, расположенные в общей части кругов А и В, — это пересечение множеств А и В. Для этих элементов выполняется как условие А, так и условие В, т. е. выполняется условие А и В (А • В) — рис. 2.36.
Рис. 2.36
Если круги не пересекаются (множества не содержат общих элементов), их пересечение — это пустое множество ?.
Для пары множеств определите пересечение А • В:
а) А = {1, 3, 5, 7, 9}, В = {1, 5, 6, 9, 12};
б) А = {а, б, в, г, д, е, ё, ж}, В = {а, е, ё, и, о, у, ы, э, ю, я};
в) А = {17, 34, 51, 68, 85}, В = {17, 34, 51, 68, 85};
г) А = {00, 10}, В = {01, 11};
д) А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С}, В = {А, В, С, D, Е, F, G, Н};
е) А = [5; 15], В = [10; 20];
ж) А = [5; 15], В = [0; 20];
з) А = [5; 15], В = [10; 12];
и) А = [5; 15], В = [20; 30].
Элементы, входящие хотя бы в одно из множеств: в А или в В, образуют новое множество, которое называется объединением множеств А и В. Для всех элементов этого множества выполняется условие А или В (А + В) — рис. 2.37.
Рис. 2.37
Для пары множеств определите объединение А + В:
а) А = {1, 3, 5, 7, 9}, В = {1, 5, 6, 9, 12};
б) А = {а, б, в, г, д, е, ё, ж }, В = {а, е, ё, и, о, у, ы, э, ю, я};
в) А = {17, 34, 51, 68, 85}, В = {17, 34, 51, 68, 85};
г) А = {00, 10}, В = {01, 11};
д) А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С}, В = {А, В, С, D, Е, F, G, И};
е) А = [5; 15], В = [10; 20];
ж) А = [5; 15], В = [0; 20];
з) А = [5; 15], В = [10; 12];
и) А = [5; 15], В = [20; 30].
Подобные диаграммы можно нарисовать для любого логического выражения, ведь каждое из них определяет некоторое множество. Например, возьмём выражение А + В. Оно равно 0 только при А = 1 и В = 0, поэтому на диаграмме незакрашенной останется только область, которая входит в круг А и не входит в круг В (рис. 2.38).
Рис. 2.38
В тетради постройте диаграммы для логических выражений:
а) А + B;
б) А • B + А • В;
в) А • B + А • B.
Диаграмма для трёх переменных содержит три круга, каждый из которых (в общем случае) пересекается с двумя другими (рис. 2.39).
Рис. 2.39
Для удобства на рис. 2.39 области пронумерованы. Запишем, для примера, логическое выражение для области 3. Эта область находится внутри кругов А и B (следовательно, выражения А и B истинны), но вне круга С, поэтому выражение С ложно. Получается условие А и B и (не С), или, в других обозначениях, А • B • C.
Запишите в тетради логические выражения для остальных областей на рис. 2.39.
Для того чтобы найти выражение для объединения двух или нескольких областей, надо сложить (используя логическое сложение — операцию ИЛИ) выражения для всех составляющих. Например, выражение для объединения областей 3 и 4 на рис. 2.39 имеет вид:
3 + 4:А • В • C + А • В • C.
Вместе с тем точки в этих областях отличаются от других тем, что они входят в область Б и не входят в область С. Поэтому справедлива более простая формула:
3 + 4: B • C.
Это означает, что логические выражения в некоторых случаях можно упростить.
Количество элементов во множестве
Предположим, что множество А содержит 10 элементов, множество B — 15 элементов, а их пересечение (множество А • B) — два элемента. Как определить, сколько элементов содержится во множестве А + В?
Попробуем рассмотреть задачу в общем виде и вывести формулу для её решения. Обозначим через Nx число элементов в области X. Далее операцию И будет обозначать символом &, а операцию ИЛИ — символом | (именно эти символы используются в поисковых запросах в Интернете).
Построим диаграмму с двумя областями — А и В. Эти области могут быть разделены (рис. 2.40, а) или пересекаться (рис. 2.40, б).
Рис. 2.40
В первом случае (рис. 2.40, а), когда области не пересекаются, получаем очевидную формулу:
NA|B = NA + NB.
Во втором случае (рис. 2.40, б) в сумму NA + NB общие элементы (элементы множества NA&B) входят дважды. Поэтому, чтобы получить количество элементов в объединении множеств, нужно из этой суммы вычесть число общих элементов:
NA|В = NA + NB — NA&B. (*)
Эта формула, которую называют формулой включений и исключений, справедлива и для рис. 2.40, а, где NA&B = 0.
Используя формулу (*), постройте выражения для вычисления NA и NA&B
Рыбаки в посёлке ловят только лещей и судаков. 25 рыбаков ловят лещей, 12 рыбаков — судаков, причём 5 рыбаков ловят и лещей, и судаков. Сколько всего рыбаков в посёлке? Выполните формализацию задачи и решите её.
У дяди Вани живёт 30 животных: овцы и кролики. Все кролики белые, а у овец разный цвет шерсти. Известно, что у дяди Вани живёт 18 овец и 25 животных с белой шерстью. Сколько белых овец у дяди Вани? Выполните формализацию задачи и решите её.
В физико-математическом классе 27 учеников. Среди них нет таких, которые не программируют и не ходят в турпоходы. Известно, что 20 человек ходят в турпоходы, среди них 5 программистов. Сколько в классе программистов? Выполните формализацию задачи и решите её.
Сложные запросы в поисковых системах
Для решения задач, в которых используются множества, например множества страниц, полученных от поисковой системы в ответ на какой-то запрос, удобно применять диаграммы Эйлера-Венна.
Задача 1. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию И, а «|» — операцию ИЛИ):
собаки | кошки 770
кошки 550
собаки & кошки 100
Сколько страниц будет найдено по запросу собаки?
Введём два множества: А — множество страниц, где есть слово «собаки», В — множество страниц со словом «кошки». По формуле, которая получена в предыдущем пункте, получаем:
NA = NA|B — NB + NA&B = 770 — 550 + 100 = 320.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
незабудка 220
лилия & незабудка 100
лилия | незабудка 450
Сколько страниц найдёт этот сервер по запросу лилия?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
енот 200
кашалот 300
кашалот | енот 450
Сколько страниц найдет этот сервер по запросу
кашалот & енот?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
Италия 320
Франция 450
Франция & Италия 80
Сколько страниц найдёт этот сервер по запросу
Франция | Италия?
Рассмотрим теперь более сложную задачу с тремя областями.
Задача 2. Известно количество страниц, которые находит поисковый сервер по следующим запросам:
собаки & лемуры 320
кошки & лемуры 280
(кошки | собаки) & лемуры 430
Сколько страниц будет найдено по запросу
кошки & собаки & лемуры?
Заметим, что во всех запросах есть часть & лемуры. Это означает, что область поиска во всех случаях ограничена страницами, на которых встречается слово «лемуры».
Обозначим буквами С, К и Л области (группы страниц), содержащие ключевые слова «собаки», «кошки» и «лемуры» соответственно. Нас интересует только область, выделенная фоном на рис. 2.41, а.
Рис. 2.41
Эта область образована в результате пересечения двух областей (рис. 2.41, б):
А = собаки & лемуры
В = кошки & лемуры
Поэтому задачу можно свести к задаче с двумя областями.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
А 320
В 280
А | В 430
Сколько страниц будет выдано по запросу А & В?
Используя формулу включений и исключений, полученную в предыдущем пункте, находим:
NА&B = NА + NB — NA|B = 320 + 280 — 430 = 170.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
берёза & сирень 220
берёза & сирень & арбуз 30
сирень & (берёза | арбуз) 340
Сколько страниц найдёт этот сервер по запросу
арбуз & сирень?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
яхта & диван 270
диван & пирог 350
яхта & диван & пирог 80
Сколько страниц найдёт этот сервер по запросу
(пирог | яхта) & диван?
Задачу с тремя областями не всегда удаётся свести к более простой задаче с двумя областями. Серьёзным упрощением может стать то, что какие-то два множества не имеют общих элементов.
Если два множества не имеют общих элементов, что можно сказать об их изображении на диаграмме Эйлера-Венна?
Задача 3. Известно количество страниц, которые находит поисковый сервер по следующим запросам:
собаки 200
кошки 250
лемуры 450
кошки | собаки 450
кошки & лемуры 40
собаки & лемуры 50
Сколько страниц найдёт этот сервер по запросу
(кошки | собаки) & лемуры?
Здесь часть & лемуры встречается не во всех запросах, поэтому свести задачу к задаче с двумя областями не удаётся. Используя те же обозначения, что и в задаче 2, построим диаграмму с тремя переменными и выделим интересующую область, которая соответствует запросу (кошки I собаки) & лемуры.
На рисунке 2.42 эта область выделена фоном.
Рис. 2.42
В общем виде задача с тремя областями очень сложна. Попробуем найти какое-нибудь упрощающее условие. Например, выделим три условия:
собаки 200
кошки 250
кошки | собаки 450
Это означает, что область кошки | собаки равна сумме областей кошки и собаки, т. е. эти области не пересекаются! Таким образом, в нашем случае диаграмма выглядит так (рис. 2.43).
Рис. 2.43
Размеры областей 1 (собаки & лемуры) и 2 (кошки & лемуры) нам известны, они составляют соответственно 40 и 50 страниц, поэтому по запросу
(кошки | собаки) & лемуры
поисковый сервер найдёт 40 + 50 = 90 страниц.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
солнце 230
крабы 220
лето 100
крабы | солнце 450
крабы & лето 60
солнце & лето 20
Сколько страниц найдёт этот сервер по запросу
крабы | солнце | лето?
Выводы
• Множество — это набор неповторяющихся элементов.
• Множество может состоять из конечного числа элементов, бесконечного числа элементов или быть пустым. Множества, с которыми работает компьютер, не могут быть бесконечными, потому что его память конечна.
• Чтобы определить множество, можно перечислить все его элементы или задать условие, которое определяет элементы множества. Для всех элементов множества это условие должно быть истинным, для элементов, не входящих во множество, — ложным.
• Дополнение множества А до универсального множества U, включающего все элементы некоторого класса, — это все элементы из U, которые не входят в А.
• Пересечение двух множеств — это множество, составленное из элементов, входящих в оба исходных множества.
• Объединение двух множеств — это множество, составленное из элементов, которые входят хотя бы в одно из этих множеств.
• Для наглядного изображения множеств используют диаграммы Эйлера-Венна, на которых каждое множество обозначается кругом или другой фигурой.
• На диаграмме Эйлера-Венна дополнение множества А — это все точки за пределами области А; пересечение множеств А и В — это общая часть областей А и В, а объединение множеств А и В — это все точки, входящие в область А или в область В.
• Количество элементов в объединении двух множеств вычисляется по формуле включений и исключений:
NA|B = NA + NB — NA&B,
где NA и NB — число элементов соответственно в множествах А и В, a NA&B — число их общих элементов.
Нарисуйте в тетради интеллект-карту этого параграфа.
§12. Множества и логика.