Семинар №1. Теория множеств
Цель семинара:
Закрепить теоретический материал, изученный в теории множеств, а именно множества, отношения, соответствия и функции.
План занятия:
На данный семинар отводится 3 часа. В нем рассматриваются такие темы как множества и операции над ними, отношения и соответствиям и функции. Решаются задачи по данным тематикам с подробным описанием.
Задача1. Представить перечислением элементов булеан В(Е), образованный от универсума Е, равного: а) {а, b}; б) {b, c, d}; в) {1, 2}; г) {2, 3, 4}.
Решение:
а) {0, {a}, {b}, {a, b}};
б) {0, {b}, {c}, {d}, {b, c}, {b, d}, {c, d}, {b, c, d}};
в) {0, {1}, {2}, {1,2}};
г) {0, {2}, {3}, {4}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}}.
Задача 2. Пусть А – множество корней уравнения х2 − 3х + 2 = 0 , а В = {0;2}. Найти A∩B, АUВ, А\В, В\А.
Решение:
Корни уравнения составляют множество А={2,1} следовательно:
A∩B={2}, АUВ={0,1,2}, А\В={1}, В\А={0}.
Пример 3.Пусть универсальное множество E – множество всех сотрудников некоторой фирмы; A – множество всех сотрудников данной организации старше 35 лет; B – множество всех сотрудников, имеющих стаж работы более 10 лет; C – множество менеджеров фирмы. Каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:
а) ;
б) B C;
в) A ( B );
г) B \ C;
д) C \ B.
Решение:
а) - множество сотрудников организации, стаж работы которых не превышает 10 лет.
б) - множество менеджеров фирмы не старше 35 лет, имеющих стаж работы более 10 лет.
в) - множество всех сотрудников фирмы старше 35 лет, а также сотрудников, не являющихся менеджерами, стаж работы которых более 10 лет.
г) В\С - множество сотрудников организации со стажем работы более 10 лет, не работающих менеджерами.
д) С\В – множество менеджеров со стажем работы не более 10 лет.
Задача 4.Изобразить диаграмму Венна, задающую множества А, В и С (А∩В∩С≠0) и обозначить на ней штриховкой множество:
а)
Решение:
Задача 5.Известно, что из 100 студентов увлекаются:
а) спортом – 19; музыкой – 21; живописью – 23; спортом и музыкой – 7; музыкой и живописью – 9; спортом и живописью – 8; спортом, музыкой и живописью – 3;
б) спортом – 25; музыкой – 38; живописью – 12; спортом и музыкой – 15; музыкой и живописью – 3;
в) спортом – 23; музыкой – 26; живописью – 31; спортом и музыкой – 10; музыкой и живописью – 13; спортом и живописью– 12; спортом, музыкой и живописью – 4;
г) спортом – 17; музыкой – 25; живописью – 32; спортом и живописью – 2; музыкой и живописью – 5.
Изобразить соответствующую диаграмму Эйлера и определить, сколько студентов:
а) ничем не увлекаются;
б) увлекаются только музыкой;
в) увлекаются только спортом;
Решение:
Задача 6.Представить перечислением элементов декартово произведение А×В, если:
а) A = {1, 2}, B = {a, b};
б) A = {a, b, c}, B = {0, 1};
в) A = {b, c}, B = {2, 3};
г) A = {3, 4}, B = {b, c, e}.
Решение:
а) {(1, a), (1, b), (2, a), (2, b)};
б){(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)};
в){(b, 2), (b, 3), (c, 2), (c,3)};
г){(3, b), (3, c), (3, e), (4, b), (4, c), (4, e)}.
Задача 7.Пусть при предварительном отборе претендентов на вакантную должность кадровую службу организации интересует следующие их характеристики:
А1 – пол; А1={женск., мужск.};
А2 – возраст (лет); А2= {18, 19, …, 35};
А3 – образование; А3= {среднее, незаконченное высшее, высшее};
А4 – общий страж работы (лет); А4= {0, 1, 2, …, 15, более 15};
А5 – стаж работы менеджером (лет); А5= {0, 1, 2, …, 10, более 10};
А6 – знание английского языка; А6= {не владеет, со словарем, свободно};
А7 – владение компьютером; А7= {компьютер, нет};
А8 – семейное положение; А8= {холост (не замужем), женат (замужем)}.
Опишите векторно двух претендентов:
а) Иванова 23 лет, окончившего МИФИ, владевшего английским со словарем, однако не имеющего стажа работы по специальности менеджера, неженатого;
б) Петрова 27 лет, окончившего Международный университет 3 года назад и проработавшего далее менеджером в коммерческой фирме, свободно владевшего двумя иностранными языками, в том числе, английским, женатого.
Определите проекции полученных векторов на оси с номерами: 2, 5, 6, 7.
Решение:
При указанной последовательности характеристик векторные описания претендентов:
а = (мужск., 23, высшее, 5, 0, со стажем, компьютер, неженат),
б = (мужск., 27, высшее, 7, 3, свободно, компьютер, женат).
Проекции полученных векторов на сои (характеристики) с номерами 2, 5, 6, 7:
пр2,5,6,7а = (23, 0, со словарем, компьютер),
пр2,5,6,7б = (27, 3, свободно, компьютер).
Задача 8.Пусть X – конечное множество, a – элемент множества X. Каких подмножеств множества X больше, содержащих элемент a или не содержащих элемент a.
Решение.Каждый раз, когда мы указываем подмножество A множества X, содержащее элемент a, то мы указываем и подмножество X \ A множества X, не содержащее элемент a, и наоборот. Если мы указываем подмножество множества X, не содержащее элемент a, то мы указываем и подмножество множества X, содержащее элемент a. Поэтому подмножеств множества X, содержащих элемент a столько же, сколько и подмножеств множества X, не содержащих элемент a.
Ответ. Поровну.
Проверим ответ данной задачи на следующем примере.
Задача 9.Преступники решили ограбить дом, в котором проживает семья из пяти человек: муж, жена, двое детей и мать жены. Сколько различных ситуаций (по количеству людей, находящихся в доме) их может ожидать?
Решение.25 = 32 ситуации.
Задача 10.Из 220 школьников 163 умеют играть в хоккей, 175 – в футбол, 24 не умеют играть в эти игры. Сколько школьников одновременно умеет играть в хоккей и футбол?
Решение.Введем обозначения: Ш – множество всех школьников, m(Ш) = 220, Ф – множество школьников, умеющих играть в футбол, m(Ф) = 175, Х – множество школьников, умеющих играть в хоккей, m(Х) = 163, Ф Х – множество школьников, умеющих играть и в футбол, и в хоккей, Ф U Х – множество школьников, умеющих играть хотя бы в одну из игр – или в футбол, или в хоккей. По условию 24 школьника не умеют играть в эти игры, следовательно:
m(Ф U Х) = m(Ш) – 24=196.
Окончательно: m(Ф U Х) = m(Ф) + m(Х) – m(Ф Х), откуда
m(Ф Х) = m(Ф) + m(Х) – m(Ф U Х) = 175 + 163 – 196 = 142.
Ответ.142 школьника играют и в футбол, и в хоккей.
Задача 11.В студенческой группе 25 человек. Во время летних каникул 9 из них выезжали в турпоездки за границу, 12 – путешествовали по России, 15 – отдыхали в Сочи, 6 – путешествовали за границей и по России, 7 – были и за границей и в Сочи, 8 – и путешествовали по России и были в Сочи и 3 – участвовали во всех трех поездках. Сколько студентов никуда не выезжало?
Решение.Пусть:
Г – множество студентов, выезжавших за границу;
Р – множество студентов, путешествовавших по России;
С – множество студентов, отдыхавших в Сочи.
Тогда множество студентов, выезжавших хотя бы куда-то из города есть ГUРUС. Так как 9 + 12 + 15 = 36 > 25, то множества Г, Р, С пересекаются (это видно и непосредственно из условия задачи, так как некоторые студенты были в различных поездках) и
Тогда: m(Г U Р U С) = 9 + 12 + 15 – 6 – 7 – 8 + 3 = 39 – 21 = 18, а из города никуда не выезжало 25 –18 = 7 студентов.
Ответ.Никуда не выезжало 7 студентов.
Задача 12.В студенческой группе 25 человек. 14 студентов изучают английский язык, остальные 16 студентов изучают немецкий язык. Сколько студентов изучают два языка: английский и немецкий?
Решение.Обозначим через X множество студентов, изучающих английский язык, через Y - множество студентов, изучающих немецкий. Тогда |Х| = 14, |Y| = 16, |Х Y| = 25. Следовательно, 25 = 14+16 - |Х∩Y| и количество студентов, изучающих два языка равно |Х∩Y| = 5.
Задача 13.Из города А в город В ведет 3 дороги, из города В в город С - 4 дороги. Сколько различных дорог ведет из города А в город С ?
Решение.
Обозначим через X множество дорог из А в В, Y - множество дорог из В в С. Тогда X = {х1,x2,хз} , Y = {y1,y2,yз}. Каждая дорога из А в С является парой (xi,yj), где xi X, yj Y. Таким образом множество всех дорог из А в С является декартовым произведением X ×Y. Следовательно, |Х × Y| = |Х| ∙ |Y| = 12.
Задача 14.Пусть М={1, 2, 3, 4, 5, 6}. Задать в явном виде (списком) и матрицей отношение , если R означает – “быть строго меньше”.
Решение.
Отношение R как множество содержит все пары элементов а, b из М такие, что а < b:
R={(a, b): (a, b) а < b }.
Тогда R={(1,2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)}.
Матрица отношения приведена на следующем рисунке
Задача 15.Пусть М={1, 2, 3, 4, 5, 6}. Составить матрицы отношения , если:
R1 – “быть делителем”;
R2 – “иметь общий делитель, отличный от единицы”;
R3 – “иметь один и тот же остаток от деления на 3”.
Решение.
1) R1={(a, b):a,b M; a - делитель b} и выполняется для пар {(1, 1), (1, 2), (1, 3), (1,4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6)}. Эти пары (a, b) определяют наличие единиц в матрице отношения на пересечении строки элемента a и столбца элемента b; a, b . Матрица отношения приведена на следующем рисунке
R2={(a, b): a, b ; a и b имеют общий делитель, с≠1}.
Матрица отношения R2 приведена ниже
R3={(a, b): a, b ; a, b имеют один и тот же остаток от деления на 3 }. Матрица отношения R3 приведена ниже
Задача 16. Англо-русский словарь устанавливает соответствие между множествами английских и русских слов. Каковы свойства этого соответствия?
Решение.
Данное соответствие не является:
• всюду определенным (всегда можно найти английское слово, не содержащееся в словаре);
• сюръективным (по отношению русских слов, имеющихся в словаре);
• функциональным (одному английскому слову ставится в соответствие, как правило, несколько русских);
• взаимно однозначным (в силу предыдущего).
Задача 17. Каковы свойства соответствия между множеством N натуральных чисел и множеством M2n -степеней двойки:
G - {(n, 2n-1): n N, 2n-1 М2n} N× М2n?
Решение.
Соответствие G взаимно однозначно:
• всюду определено, так как пр1 G = N ;
• сюръективно. поскольку пр2 G = М2n;
• функционально, так как любому n N соответствует единственный образ 2n-1 М2n;
• характеризуется единственностью прообраза, ибо для любого 2n-1 М2n, существует единственное n N.
Задача 18. Таблица выигрышей лотереи устанавливает соответствие G между парами чисел из N×N = N2 (серия, номер выигравшего билета) и множеством выигрышей M, т.е. . Является ли заданное соответствие функцией, и если – да, то какой?
Решение.
Соответствие , задаваемое таблицей выигрышей, является функциональным, так как для каждой указанной пары из N2- (серии, номера билета) определен конкретный (единственный) выигрыш из М. Таким образом, данное соответствие есть двухместная функция f: N×N→ М. Функция такого типа не всюду определена, значит не является отображением. Более того, как правило, число выигравших билетов (мощность области определения пр1 f) больше перечня наименований выигрышей (мощности области значений пр2f). поэтому данная функция не обладает единственностью прообраза. В силу сказанного f не является взаимно однозначным соответствием.
Таким образом, таблица выигрышей лотереи определяет f: N×N→ М, которая не является отображением и тем более - взаимно однозначным соответствием.
Задача 19.Пусть М1, - множество сотрудников организации и R1 - заданное на нем отношение "быть старше" ( );М2 -конечное множество натуральных чисел (ограниченное, например, числом 100) и R2 - заданное на нем отношение "быть больше" (>). Гомоморфны (изоморфны) ли модели:
МО =(М1; ) и МО =(М2;>)?
Решение.
1. Определим отображение Г:М1→ М2, следующим образом: каждому сотруднику организации из М1, поставим в соответствие Г число из М2, соответствующее его возрасту (в годах). Установленное таким образом отображение Г:М1→ М2, является гомоморфизмом моделей МО =(М1; ) и МО =(М2;>), так как очевидно выполняется условие (a R b влечет Г(а) R' Г(b) для любых а, b А). Действительно, если ‘Иванов ',37 лет, старше 'Петрова’, 26 лет, т.е.
‘Иванов' 'Петрова' и Г( ‘Иванов') = 37,
Г( 'Петров’ )=- 26, то и 37 > 26.
2. Однако установленное отображение Г:М1→ М2, не является изоморфизмом моделей МО =(М1; ) и МО =(М2;>), так как не является в общем случае взаимно однозначным (если в организации имеются сотрудники одною возраста, например ‘Петров' 26 лет и ‘Сидоров' 26 лет. В этом случае обратное соответствие Г-1 не является отображением, поскольку не функционально (отсутствует единственность образа 26 на множество сотрудников организации).
Таким образом, заданные модели МО =(М1; ) и МО =(М2;>) гомоморфны, но не изоморфны.