Семинар №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}. Найти AB, АUВ, А\В, В\А.

Решение:

Корни уравнения составляют множество А={2,1} следовательно:

AB={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 на множество сотрудников организации).

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