Семинар №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. Пусть А – множество корней уравнения х² − 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. Пусть при предварительном отборе претендентов на вакантную должность кадровую службу организации интересует следующие их характеристики:

А ₁ – пол; А ₁={женск., мужск.};

А ₂ – возраст (лет); А ₂= {18, 19, …, 35};

А ₃ – образование; А ₃= {среднее, незаконченное высшее, высшее};

А ₄ – общий страж работы (лет); А ₄= {0, 1, 2, …, 15, более 15};

А ₅ – стаж работы менеджером (лет); А ₅= {0, 1, 2, …, 10, более 10};

А ₆ – знание английского языка; А ₆= {не владеет, со словарем, свободно};

А ₇ – владение компьютером; А ₇= {компьютер, нет};

А ₈ – семейное положение; А ₈= {холост (не замужем), женат (замужем)}.

Опишите векторно двух претендентов:

а) Иванова 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. Преступники решили ограбить дом, в котором проживает семья из пяти человек: муж, жена, двое детей и мать жены. Сколько различных ситуаций (по количеству людей, находящихся в доме) их может ожидать?

Решение. 2⁵ = 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 = {х₁,x₂,х_з}, Y = {y₁,y₂,y_з}. Каждая дорога из А в С является парой (x_i,y_j), где x_i X, y_j 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}. Составить матрицы отношения , если:

R₁ – “быть делителем”;

R₂ – “иметь общий делитель, отличный от единицы”;

R₃ – “иметь один и тот же остаток от деления на 3”.

Решение.

1) R₁={(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 . Матрица отношения приведена на следующем рисунке

 

R₂={(a, b): a, b ; a и b имеют общий делитель, с≠1}.

Матрица отношения R₂ приведена ниже

R₃={(a, b): a, b ; a, b имеют один и тот же остаток от деления на 3 }. Матрица отношения R₃ приведена ниже

 

Задача 16. Англо-русский словарь устанавливает соответствие между множествами английских и русских слов. Каковы свойства этого соответствия?

Решение.

Данное соответствие не является:

• всюду определенным (всегда можно найти английское слово, не содержащееся в словаре);

• сюръективным (по отношению русских слов, имеющихся в словаре);

• функциональным (одному английскому слову ставится в соответствие, как правило, несколько русских);

• взаимно однозначным (в силу предыдущего).

 

Задача 17. Каковы свойства соответствия между множеством N натуральных чисел и множеством M _2n -степеней двойки:

G - {(n, 2^n-1): n N, 2^n-1 М_2n } N× М_2n?

Решение.

Соответствие G взаимно однозначно:

• всюду определено, так как пр₁ G = N;

• сюръективно. поскольку пр₂ G = М_2n;

• функционально, так как любому n N соответствует единственный образ 2^n-1 М_2n;

• характеризуется единственностью прообраза, ибо для любого 2^n-1 М_2n, существует единственное n N.

 

Задача 18. Таблица выигрышей лотереи устанавливает соответствие G между парами чисел из N×N = N ² (серия, номер выигравшего билета) и множеством выигрышей M, т.е. . Является ли заданное соответствие функцией, и если – да, то какой?

Решение.

Соответствие , задаваемое таблицей выигрышей, является функциональным, так как для каждой указанной пары из N ² - (серии, номера билета) определен конкретный (единственный) выигрыш из М. Таким образом, данное соответствие есть двухместная функция f: N×N→ М. Функция такого типа не всюду определена, значит не является отображением. Более того, как правило, число выигравших билетов (мощность области определения пр₁ f) больше перечня наименований выигрышей (мощности области значений пр₂ f). поэтому данная функция не обладает единственностью прообраза. В силу сказанного f не является взаимно однозначным соответствием.

Таким образом, таблица выигрышей лотереи определяет f: N×N→ М, которая не является отображением и тем более - взаимно однозначным соответствием.

 

Задача 19. Пусть М ₁, - множество сотрудников организации и R₁ - заданное на нем отношение "быть старше" (); М ₂ -конечное множество натуральных чисел (ограниченное, например, числом 100) и R ₂ - заданное на нем отношение "быть больше" (>). Гомоморфны (изоморфны) ли модели:

МО =(М ₁; ) и МО =(М ₂;>)?

Решение.

1. Определим отображение Г: М ₁→ М ₂, следующим образом: каждому сотруднику организации из М ₁, поставим в соответствие Г число из М₂, соответствующее его возрасту (в годах). Установленное таким образом отображение Г: М ₁→ М ₂, является гомоморфизмом моделей МО =(М ₁; ) и МО =(М ₂;>), так как очевидно выполняется условие (a R b влечет Г(а) R' Г(b) для любых а, b А). Действительно, если ‘Иванов ',37 лет, старше 'Петрова’, 26 лет, т.е.

‘Иванов' 'Петрова ' и Г(‘Иванов ') = 37,

Г('Петров’)= - 26, то и 37 > 26.

2. Однако установленное отображение Г: М ₁→ М ₂, не является изоморфизмом моделей МО =(М ₁; ) и МО =(М ₂;>), так как не является в общем случае взаимно однозначным (если в организации имеются сотрудники одною возраста, например ‘Петров' 26 лет и ‘ Сидоров ' 26 лет. В этом случае обратное соответствие Г^-1 не является отображением, поскольку не функционально (отсутствует единственность образа 26 на множество сотрудников организации).

Таким образом, заданные модели МО =(М ₁; ) и МО =(М ₂;>) гомоморфны, но не изоморфны.