Эскорт-услуги в Москве от Queens Palace


GOUSPO студенческий портал!

форум, учебники, лекции, и многое другое

Множества

Тема 2. Множества

План:

  1. Общие понятия теории множеств.
  2. Основные операции над множествами
  3. Кортежи
  4. Декартово произведение множеств
  5. Соответствия между множествами.
  6. Отображения
  7. Бинарные отношения
  8. Элементы комбинаторики
  9. Подстановки

Цель. Формирование базовых понятий, связанных с множествами. Обучение выполнению операций над множествами. Обучение умению строить бинарные соответствия, задавать отношения и отображения, устанавливая их свойства. Обучение решению практических задач, связанных с множествами и комбинаторикой.

Теоретические сведения

1. Общие понятия теории множеств.

Понятие Множество является одним из  основных понятий математики. Это понятие в явном виде не определяется, хотя на интуитивном уровне его можно описать, задать. Над множествами можно  выполнять многие операции, которые будут рассмотрены при изучении этой темы.

Под множеством можно понимать - неупорядоченную совокупность элементов, набор объектов.

Примерами множеств может служить:

  1. Множество людей.  Группа детей одного класса – элементами служат учащиеся именно данного класса. Множество берез в лесу

2.  Совокупность всех классов некоторой школы – элементами являются именно группы детей, образующих каждый их этих классов.

3.  Множество натуральных чисел  Натуральные числа – числа от 1 до бесконечности.

4.  Множество треугольников – любой треугольник является элементом этого класса.

5.  Знаки препинания, буквы алфавита, цифры для записи чисел

6.  D= {2, 4, 6, 8, 10, 12…} – множество четных чисел

7.  V= {3, 6, 9, 12…} – множество чисел кратных трем

8.  M={Иванов, Петров, Сидоров…} – множество спортсменов

9.  Множество делителей числа 24.

10.Множество письменных принадлежностей

Если множество задано, каждый элемент (объект) его уникален, т. е. отличим от других; причем для любого объекта существует возможность установить, принадлежит ли он множеству или нет.

Множества обозначаются заглавными буквами, как правило,  латинского алфавита. При этом элементы множества принято заключать в фигурные скобки.

Принадлежность  элемента а множеству А обозначается символом Î, например, а Î А (от греческой буквы e), не принадлежность символом Ï.

Например: Х={1,2,3,4,5,6}.

3ÎХ –  число 3 принадлежит множеству Х. 9ÏX  - число 9 не принадлежит множеству Х.

Совокупность {1,2,3,4,5,6} является множеством, последовательность (порядок) записи элементов не имеет значения, поэтому оно неотличимо от множества {1, 3, 5, 2, 4, 6}

Совокупность {1,2,3,1,3,3,5} множеством не является, здесь некоторые элементы записаны не единичным образом.

В множестве могут быть объединены объекты самой разной природы, в том числе и множества. Примерами  множеств могут быть множество студенты одной группы, множество команд языка программирования, множество групп студентов 2-го курса и т.д.

В последнем случае элементы сами являются множествами.

Число элементов множества А обозначается как |А| и называется мощностью или численность А (размером, нормой, длиной и др.) множества.

Множество, не содержащее элементов, обозначаемое символом Æ и называемое пустым множеством. Пустое множество может встретиться в реальных задачах. Так, например, может оказаться, что множество студентов группы, получивших две неудовлетворительные оценки, пусто. Это значит, что таковых студентов нет. Пустым множеством может оказать множество корней уравнения или решения неравенства. В программировании понятие пустого множества встречается очень часто.

Множество может быть представлено (задано) в виде:

~    Перечисления, например, А= {a, b, c, d, e, f};

~    Свойства, например,  В={bi ½bi студенты старше 25 лет};

~    Процедуры, например,  C={ci | ci =n2, n Î N}.

Здесь и далее при задании множества символ | вертикальная разделительная черта, используется вместо слов таких, что, всех и др.

Рассмотрим запись  M={x | P(x)}. Она означает, что множество M состоит их всех элементов x, обладающие свойством  P(x).

Например, M={x | 3x2 -2x =0}. Множеству M принадлежат корни уравнения 3x2 -2x =0. Это числа 0 и 1,5. M= {0; 1,5}

В дальнейшем при задании множества будут введенные иные символы и слова, например, такие символы как: символы:

&, Ç  для обозначения союза И

È  для обозначения союза ИЛИ

квантор общности, для обозначения слов: для всех, для каждого

$ квантор существования, для обозначения слов: существует,найдется ….

Свойство, с помощью которого задано множество, называется характеристическим свойством. Этим свойством должны обладать все элементы данного множества. А именно, все элементы заданного множества обладают характеристическим свойством и если некоторый из элементов не принадлежат этому множеству, то он не  обладают заданным свойством.

Это условие является и основой методов проверки равенства двух множеств. Необходимость в проверке равенства множеств может возникнуть тогда, когда множество описано   через различные свойства, и необходимо убедиться, что этим свойствам соответствует одно и тоже множество. В общем случае задача проверки равенства множеств является достаточно сложной задачей, требующей больших вычислительных затрат.

Для наглядности множества на плоскости  изображаются кругами или иными плоскими геометрическими фигурами, замкнутыми контрами, которые называются по фамилиям двух математиков, работавших в теории множеств,  кругами Эйлера – Венна

Элементы, принадлежащие множеству, изображаются точками внутри фигуры.

Множества:  А и В считаются равными, если они состоят из одних и тех же элементов. С помощью выше указанных символов Этот факт можно записать следующим образом:

Если (а ÎА $b ÎВ, а=b) Ç ( b ÎВ $aÎА, а=b).

Подмножеством некоторого множества называется любое множество, состоящее из элементов данного множества. Говорят, что подмножество является частью множества. На рисунке изображено  множество А, которое является подмножеством множества В. Данный факт принято обозначать символами: А Ì В.

Если множество X есть подмножество множества Y, то пишут XÌY. Знак Ì называется знаком включения. Не следует его путать со знаком Î принадлежности.

Если подмножество совпадает с самим данным множеством  или является пустым множеством, то оно называется несобственным подмножеством. Все остальные подмножества называются собственными подмножествами.

Число всех подмножеств множества,  содержащего n элементов, вычисляется по формуле k=2n.  Сюда входят все  собственные и несобственные подмножества. Множество всех подмножеств данного множества называется Булеаном

Множество В называется дополнением множества А если ни один элемент из В не принадлежит А. Дополнение обозначается как: В =`А;  В =A; иногда B= -A

Очевидно, что для любого подмножества, можно указать его дополнение до данного множества.

Рассмотрим множество двузначных чисел:

А={10;11;12;…98;99}

В={10;20;30;40;50;50:70;80;90} – двузначные числа, оканчивающиеся нулем, являются подмножеством множества двузначных чисел.

C- {11; 12…} двузначные числа, не оканчивающиеся нулем, которые и будут являться дополнением подмножества В до множества А

Если некоторое множество D дополняется до некоторого другого множества R, то такое множество R называется универсальным множеством.  Предполагается, что дополнение происходит до некоторого универсального множества, определяемого предметной областью задачи. Универсальное множество часто  обозначается символом U. Любое множество является подмножеством универсального множества. Например:

1. Для множества натуральных чисел универсальным множество можно считать множество действительных чисел.

2.  Для множества детей человеческого общества, универсальным множеством является множество всех людей.

3. Для множества студентов конкретных групп, универсальным множеством является множество студентов факультета.

Существует два особых подмножества. Одно  из них  совпадает с самим заданным множеством. Другое не содержит элементы или  пустое подмножество, которое  обозначается символом:  Æ. Последние два подмножества называются не собственными подмножествами. Остальные подмножества – называются собственными подмножествами.

Задание 1.

Что можно сказать о множествах:

Y={1;2;3;4;5;7;8;9}- множество однозначных чисел

Х={2;4;6;8} – множество четных однозначных чисел

Ответ:

  1. n(Y)=9, n(X)=4
  2. XÌY
  3. Z={1;3;5;7;9} – дополнение множества X до Y.
  4. Универсальным множеством для множества Y есть множество, например, двузначных чисел.

5.    и т.д.

Задание 2. Изобразите геометрически (кругами) множества

D= {10, 11, 12 …98, 99} – множество двузначных натуральных чисел,

F= {10, 20… 90} множество чисел, оканчивающихся нулем.

Решение. См. рисунок.

Очевидно, что все элементы множества  F – принадлежат множеству .D. В таких случаях говорят, что множество F – есть подмножество множества D

Подмножества могут содержать по одному, по два, по три  и более элементов.

Число возможных подмножеств, которое можно составить из данного множества, вычисляется по формуле:

k=2n, где n – число элементов в заданном множестве

Задание 3. Выписать все подмножества трехэлементного множества S={a,b,c}

Решение. a, b, c, ab, ac, bc, abc, Æ. Всего  k=23=8 подмножеств.

Задание 4. Запишите несколько подмножеств для множеств:

D= {10, 11, 12 …98, 99} – множество натуральных двузначных чисел,

F= {10, 20… 90} множество чисел, оканчивающихся нулем.

Установите число подмножеств каждого множества

Решение. Всего 90 двузначных чисел, значит k1=290 количество возможных подмножеств. Чисел, оканчивающихся нулем – 9 штук, значит k2=29=512 возможных подмножеств

Классификация множеств.

Основная  характеристика множества есть его количество  его элементов или  его  мощность..

Количество элементов в некотором множестве называется его численностью. Запись вида n(D)=12 обозначает, что число элементов в этом множестве D равно12.

Множества, имеющие одинаковую мощность, называются равномощными или эквивалентными множествами

Множества считаются равными, если они состоят из одних и тех же элементов.

Множество называется счетным, если оно равномощно множеству натуральных чисел.  В противном случае множество называется несчетным.

Множество, содержащее конечное число элементов, называется конечным множеством, а множество, содержащее бесконечное число элементов – бесконечным множеством.

Множества называется  конечным, если  элементы их можно пересчитать.

Множество называется бесконечным, если  число их элементов нельзя пересчитать или нельзя, по крайней мере, указать правило, которое позволяет теоретически установить число их элементов.

Проблема установления конечности или бесконечности множества, на первый взгляд кажется очевидной, но с точки теории множеств  очень сложная.

Рассмотрим несколько примеров.

  1. Число песчинок в стакане очень большое, но, тем не менее, их можно пересчитать, значит, их конечное число.
  2. Множество N натуральные числа бесконечно. В этом можно легко убедится, если понять, что к любому, пусть даже самому большому натуральному числу всегда можно прибавить,  по крайней мере, число 1.

Бесконечными являются и другие основные числовые множества:

Q -рациональные числа    Z целые числа R – действительные числа

Правомочен вопрос о сравнении числа элементов в этих множествах. А, именно, какое из основных числовых множеств более бесконечное, чем другие. Ответы на такие вопросы представляют чисто теоретический аспект и далеко выходят за рамки данного предмета разговора.

Задание 5. Выписать все подмножества трехэлементного множества S={a,b,c}

Решение. a, b, c, ab, ac, bc, abc, Æ. Всего  k=23=8 подмножеств.

Задание 6 Запишите несколько подмножеств для множеств:

D= {10, 11, 12 …98, 99} – множество натуральных двузначных чисел,

F= {10, 20… 90} множество чисел, оканчивающихся нулем.

Установите число подмножеств для каждого множества

Решение. Всего 90 двузначных чисел, значит k1=290 количество возможных подмножеств. Чисел, оканчивающихся нулем – 9 штук, значит k2=29=512 возможных подмножеств

2. Основные операции над множествами

На множестве множеств устанавливается несколько операций. Результатом выполнения той или иной операции над множествами является множество.

Одна операция  – дополнение, была рассмотрена выше. В связи с тем, что эта операция задана на одном множестве, она относится к так называемым, унарным операциям.

Определение бинарных операций

Рассмотрим операции, которые заданы для двух различных множеств. Множество таких операций относятся к бинарным операциям.

Пусть даны два множества А и В и множество С, которое  является результатом операций над ними (бинарная операция).

  1. Пересечение множеств состоит из элементов принадлежащих каждому из данных множеств. Обозначается:  А ÇВ = С. Эту операцию называют еще  умножением множеств.

M=A∩B – пересечение множеств. В пересечение входят только те элементы, которые принадлежат каждому из данных  множеств, а именно являются общими элементами  для всех заданных множеств

  1. Объединение множеств состоит из элементов, принадлежащих хотя бы одному из данных множеств.  Обозначается: А ÈВ=С. Эту операцию еще называют сложением множеств

K=AÈB – объединение множеств. В объединение входят элементы, которые принадлежат хотя бы  одному из данных  множеств

  1. Разность множеств состоит их элементов, принадлежащих первому (уменьшаемому) множеству A, но не принадлежащих второму  (вычитаемому) множеству B. Обозначается: A\B.   Эту операцию называют: А без В.

G=X \ Y – вычитание множеств. В разность входят элементы уменьшаемого, без элементов, входящих в вычитаемое множество.

  1. Симметрическая  разность состоит из элементов, не принадлежащих пересечению заданных множеств. Симметрическая  разность состоит из элементов, принадлежащих только одному из данных множеств: либо А, либо В. Обозначается  АDВ=С

В связи с тем, что результат любой операции является множеством той же предметной области, то такой результат  может участвовать в качестве аргумента в последующей операции. Это позволяет строить сложные формулы, описывающие множество через другие множества. Например, (АÇВ)È( АÇВÇС); (A\B) Ç(BÈD).

Две формулы F1 и  F2 называются эквивалентными (равносильными), если они описывают равные множества. Записывать это в виде равенства F1= F2.

Над множествами можно выполнять бинарные операции, такие как:

Свойства операций

  1. А Ç А=А;  А È А=А;  A Ì (AÇB)  Законы поглощения. Первые два равенства иногда называют  идемпотентность операции  пересечения (объединения).
  2. А Ç В = В ÇА;  А È В = В ÈА – Коммутативный (Переместительный) закон операции пересечения (объединения).
  3. А Ç(В ÇС) = (А ÇВ) ÇС;   А È(В ÈС) = (А ÈВ) ÈС  — Ассоциативный (Сочетательный) закон операции  пересечения (объединения).
  1. (В ÈС) Ç А = (А ÇВ) È(А ÇС  или     А Ç(В ÈС) = (А ÇВ) È(А ÇС)  Дистрибутивный (Распределительный) закон операции пересечения  по отношению к объединению
  2. (В ÇС) È А = (А ÈВ) Ç(А ÈС  или    А È (В ÇС) = (А ÈВ) Ç(А ÈС)  Дистрибутивный (Распределительный) закон операции  объединения по отношению к пересечению

6. Универсальное множество U  и пустое множество Æ дополняют друг друга: U=Æ, Æ=U.

7. Если A1 , A2 , A3 ,… An все n подмножеств множества А.

~    Объединение всех подмножеств дают само множество: A= A1 È A2 È A3 È… ÈAn

~    Справедливо равенство:

A\ (A1 Ç A2 Ç A3 Ç… ÇAn ) =(A\ A1) È(A\ A2) È(A\ A3) È… È (A\ An), котороеt записывается  кратко в виде:: , где i=1,2,3…n.

Дополнение обладает следующими  характерными свойствами

8. Для любого множества X Ì U (X)'=X, где U-универсальное множество.

9. Для любых множеств X ÌU и Y ÌU  выполняются равенства

(XÇY)=XÈY   и    XÈY)=XÇY

Эти равенства называются Равенства де Моргана, которые будут дополнительно рассорены в  разделе Математическая логика в связи с логической операцией отрицания.

10. Множество считается разбитым на классы подмножеств, если:

~    пересечение двух любых классов  пустое.

~    объединение всех классов дает само множество.

Операция разбиение множества на классы есть логическая операция. Как правило, разбиение множества на классы производится по одному или нескольким признакам (свойствам). Например: Множество людей можно разбить на классы по возрасту, годам рождения, полу, месту жительства. Множество чисел – на положительные. отрицательные и ноль. Множество геометрических фигур – на плоские и пространственные фигуры…

11. Особые случаи (свойства)

АÇU=А,          АÇÆ=Æ,                    AÈÆ=A,                    AÈU=U,
А ÇĀ=Æ,         A È Ā =U,                 A\A=Æ.

Упрощение выражений

Представленные в свойствах равенства используют для преобразования формул. Если в формуле заменить множество равным ему множеством, получится формула, равная исходной. Таким образом, можно в формулах удалять одинаковые члены, выносить за скобки или раскрывать скобки и т.п.

Для упрощения выражений могут быть оказать следующие утверждения

~      Если А ÈВ ÈС=Æ, то А= Æ, В= Æ, С= Æ.

~      Если А ÇВ=Æ, то  А Í~В или В Í~А.

~      Если F1=F2, то (F1Ç F2) È (F1Ç F2) =Æ.

~      Если уравнение записано в виде F1=F2 , где F2 не пустое множество, то это уравнение можно привести к виду, когда справа будет стоять пустое множество.

Задание 7. Упростить выражение: (А ÇВ ÇС) È(А ÇВ ÇС)

Решение: (А ÇВ ÇС) È(А ÇВ Ç~С) = (А ÇВ) Ç(C ÈC) =A ÇB

Задание 8. Установить зависимости между данными множествами, если (А Ç В) È (А ÇВ ÇС)=Æ

Решение. Если объединение двух множеств пустое, если оба это множества пустые, значит:

(А Ç В) =Æ   Откуда следует, что В  ÍА.

(А ÇВ ÇС)=Æ. Значит (А Ç С) Í В

3. Кортежи.

При записи (задании) множеств, часто интересуют не только элементы, из которых состоит множество, но и их последовательность появления (записи). В этом случае идет речь об упорядоченных множествах. Так при определении положения точки на плоскости или пространстве указывается упорядоченная пара  чисел на плоскости и упорядоченная тройка чисел в пространстве. Перестановка координат приводит к заданию других точек.

Кортеж – это упорядоченное множество элементов.

Длина  кортежа – есть количе6ство (число)  элементов в нем.

Картежи равны, если  на одинаковых местах  (номерах) у них находятся одинаковые элементы.

Элементы  кортежа  записываются в угловых или в круглых скобках.

D=á2;3;5;9ñ,  Y=(a;f;h;);    или  á2;3;5;9ñ,   (a;f;h;);

Соединение  кортежей есть кортеж, состоящий из элементов, записанных строго в той последовательности,  в которой объединяются  кортежи. Длина  такого кортежа равна сумме длин  соединяемых кортежей. Если число элементов кортежа можно предоставить в виде  суммы  n слагаемых, то такой кортеж можно разбить на  n  кортежей. Длина каждого из которых равна величине соответствующего слагаемого.

Примером кортежей может служить любой алфавит. Это алфавит любого разговорного языка. Множество цифр, используемых при записи чисел – так же алфавит и др.

Рассмотрим множество B={0;1} Множество кортежей длины m  состоящие из нулей и единиц обозначим Bm.. Тогда  n(Bm)=2m.Такие  кортежи называют упорядоченными наборами или векторами.

Если:

m=1, получим 2 кортежа (0) и (1)

m=2, получим 4 кортежа (00), (01), (10), (11)

m=3, получим 8 кортежей (000), (001), (010) …(111)

Они имеют широкое применение в дискретной математики и информатике.

При записи (кодировании) информации для ЭВМ используются , например  кортежи  длины 8 и 16, состоящие .из нулей и единиц

Кортежи длины 2  часто называют парами; длины 3 – тройками и т.д.

Элементы кортежей называются компонентами: первая компонента, вторая компонента  и т.д.

4. Декартово произведение множеств.

Декартовым произведением двух множеств называется множество пар элементов, у которых первая компонента принадлежит первому множеству, вторая – второму.

Для множеств: A=(1;2;3) и B=(n;m декартово произведение имеет вид

D=AxB={(1;n), (1;m), (2;n), (2;m), (3;n), (3;m)}

Число элементов декартового произведения, равно произведению мощностей  данных множеств. n(AxB)=n(A)·n(B)

Декартово произведение задается периселением элементов, таблицей, координатной плоскостью и иными, понятными  способами.

AxB n m
1 (1;n) (1;m)
2 (2;n) (2;m)
3 (3;n) (3;m)

Определение  декартового произведения двух множеств по  аналогии распространяется на любое число множеств, в том числе и на равные множества

Декартовым произведением n множеств называется множество кортежей длины n, у которых первая компонента принадлежит первому множеству, вторая – второму, …, компонента n принадлежит множеству n. Число элементов декартового  произведения n множеств равна произведению численностей всех множеств.

Если А12 =…=Аn =A, то Аn =A x A x A x … x A.

Для декартового  произведения не выполняются условия коммутативности и ассоциативности. Это легко усмотреть при рассмотрении нескольких частных примеров.

5.. Соответствия между множествами

Пусть даны два множества  A={a1; a2; a3;… an}  и B ={b1; b2; b3;… bm}. Декартово произведение  K= AxB их есть множество пар вида (ai;bj), где i=1,2,3,…n  и  j=1,2,3,…m. Выбирая из  него любое подмножество R, получаем  соответствие между некоторым подмножеством  X  множества A, состоящего из первых компонентов выбранных пар и некоторым подмножеством  Y множества B, состоящего из вторых компонентов выбранных пар. X – называется областью определения, а Y – множеством значения соответствия R. Причем, возможны случаи, когда X=A и Y=B одновременно или один из них.

Соответствием между двумя множествами является  любое подмножество декартового произведения этих множеств.

Соответствием между двумя множествами называется  правило, по которому каждому элементу множества X  выбирается (устанавливается, определяется) элемент из множества Y.

Если рассматривать все  пары декартового произведения, то пара (ai;bj) задает  соответствие между элементами множества A={a1; a2; a3;… an}  и множества B ={b1; b2; b3;… bm}. с соответствующими областями определения и значения.

Вторая компонента bj пары (ai;bj) называется образом элемента ai.

Первая компонента ai пары (ai;bj) называется прообразом элемента bj

Соответствие задается всеми способами, которыми задается декартово произведение двух множеств. Если соответствие задается  на координатной плоскости,  то область определения соответствия указывается на оси абсцисс, множество значений – оси ординат.

Если во всех парах, задающих соответствие R, компоненты поменять местами,  то получится соответствие R-1, обратное данному соответствию.

Примеры соответствий:

  1. График дежурства учащихся на неделю (месяц). Область определения список учащихся. Множество значений – день недели (месяца) дежурства..
  2. Таблица квадратов (кубов …) натуральных чисел. Область определения натуральные числа. Множество значений – их квадраты (кубы …)
  3. Формула y=x2 +3x-7  задает соответствие между множеством действительных чисел (ось CX) –  область определения и множеством действительных чисел, являющиеся значениями  этой формулы  (ось OY).
  4. Соответствие R задано кругами и стрелками.  A область определения, B множество значений. Число элементов в области определения в и множестве значений  могут быть различными., как в рассматриваемом примере.

6 . Отображения

Одним из важных понятий математики, есть понятие отображения, которое непосредственно связано с понятием соответствия, описывая его. Понятие отображения часто ассоциируется с понятием функции.

Для задания отображения f необходимо указать:

1. Область определения – множество, которое отображается. Область определения задается изначально. Обозначается  D(f). Элементы области определения называют аргументами.

2. Область значений – множество,  к которое или на которое  отображается заданная область. Область значений. Обозначается  E(f)

  1. Правило (закон, соответствие)  между D(f) и E(f).

Отображения можно записывать в т виде: f:A→B, , B=f(A), B=F(A), y=f(x)  и др.

В данном курсе будут рассматриваться  однозначные отображения, где каждому элементу из области определения (аргументу) поставлен в соответствие не более чем один элемент из области значений (один или ни одного).

При отображении, в том числе и однозначном отображении, количество образов равно или меньше числа прообразов. Это следует из того, что несколько элементов  из области определения могут отобразиться в один и тот же элемент множества значений.

Задание отображений.

Для  задания (записи) отображений используются следующие основные способы:

  1. Аналитический способ  – в виде формулы.
  2. Табличный способ. В первой строчке таблицы записываются элементы (числа) области определения, во второй – элементы множества значений.
  3. Графический способ – на координатной плоскости.
  4. С помощью графов -  двух кругов или иных геометрических фигур и стрелок.
  5. Словесный способ – в виде текста , описывающего закон соответствия.

Виды отображений.

Отображения делятся на два вида: отображения в и на.

Пусть задано отображение B=f (A)

1. Отображение в – инъекция Соответствие, при котором каждому элементу множества A соответствует единственный элемент множества B, а каждому элементу множества  B соответствует не более одного прообраза из A. При этом, мощность множества A меньше мощности множества B.

2. Отображение на – сюръекция. Соответствие, при котором каждому элементу множества A соответствует единственный элемент множества B, а каждому элементу множества  B соответствует хотя бы  один прообраз из A. При этом, мощность множества A больше или равна мощности множества B.

Особое место занимают взаимнооднозначные отображения (соответствия).

Взаимнооднозначное отображение (соответствие) – биекция. Соответствие, при котором каждому элементу множества A соответствует единственный элемент множества B и  каждому элементу множества  B соответствует один прообраз из множества A. При этом мощность множества A равна мощности множества B.

Множества будут равномощными (равносильными, эквивалентными), если между ними  можно установить (задать) взаимнооднозначное соответствие.

Для взаимнооднозначных отображений, обратное отображение также является взаимнооднозначным отображением.

Задание. Установить взаимнооднозначные соответствия между следующими равномощными множествами.

  1. Множества четных и натуральных чисел
  2. Множества натуральных  и рациональных чисел
  3. Множества точек расположенных на двух различных отрезках  (окружностях, квадратах).
  4. Равночисленные конечные множества.
  5. Множество точек на единичном отрезке координатной прямой и всей этой прямой.

Операция композиции отображений и ее свойства.

Пусть даны отображения вида: z=f(y), y=t(x). Последовательное выполнение таких отображений называется композицией (произведением, суперпозицией) отображений. Обозначается f и t или f ◦ t. Отображение часто называют функцией, при этом произведение функций называется сложной функцией или функцией от функции z=f(t(x)).

Обозначим через Q и W соответственно области определения и значения отображения для функции  z=f(y). Через S и  L соответственно области определения и значения отображения для функции  y=t(x). В композиции двух функций участвуют  4 множества. Не обязательно множество значений функции z=f(t(x)).должно совпадать с множеством L, скорее всего ее множество значений будет являться подмножеством множества L, а именно  L1 =t (W∩S), L1ÌL

Для наглядности изобразим этот факт  в виде схемы:

z=f(y)                Q                     W

y=t(x)                                  S                                L

z=f(t(x)).            Q                     S1 =W∩S                    L1 =t (W∩S)

Полученные факты хорошо  проверяются и иллюстрируются  на числовых функциях.

Сложная функция

Сложная функции есть композиция двух и более функций. Композиция функций не обладает переместительным свойством, но обладает сочетательным законно: f◦(t◦w))=(f◦t)◦w. При этом надо внимательно следить за областями определения и значений каждой из этих функций.

Композицию функций нельзя считать как произведение чисел или многочленов.

При построении композиций, функции могут совпадать, тогда имеет место натуральная степень композиции. z=f◦f◦f…◦f.

Задание 10. Даны функции::  z=Sin y ,  y=t2 ,  t= lln x. Составить сложные функции.

Возможные варианты решений:

z=Sin (t2);  y=(lln x)2;   z=Sin (lln x)2); z= Sin(Sin(Sin x))

Задание 11. Даны два множества  А и В., причем  n(A)=3, n)B)=8. Сколькими способами можно отобразить множество А в множество В?  Решить задачу в общем виде. Ответ. Каждый из трех элементов множества А, может отобразиться в каждый из 8 элементов множества В.Причем они могут отображаться не обязательно в разные элементы. 83=512

7. Бинарные отношения.

Отношением называется соответствие (отображение), заданное  на  равных множествах. В ряде случаем удобно говорить об одном и том же множестве..

В данном случае имеется в виду, что отношения устанавливают связь между двумя элементами множества, поэтому их называют бинарными отношениями. Иных отношений  в данном курсе математике рассматриваться не будет.

Примеры отношений

1. На множестве людей задано отношение R=Человек s знаком с человеком d . Здесь можно задать отношения Быть выше по росту, Иметь один цвет глаз и др.

2. На множестве натуральных чисел задано отношение Число m больше числа n

3. На множестве треугольников задано отношение Треугольник r и треугольник l имеют равные углы (стороны)

Отношением, заданным на некотором множестве, могут обладать не все элементы этого множества, что легко проверяется  на приведенных примерах отношений.

Задание отношений.

Отношения задаются всеми способами, которые присущи соответствиям и отношения. Это графически, таблицей, перечислением пар, занятых в данном отношении и др.

Для каждого отношения можно задать обратное отношение.

Пусть на множестве А={2,3,4,6,8} задано отношение R=Число x делитель числа y.

1.  Запишем  отношение в виде пар  (xRy): (2;2), (2;4), (2;6), (2;8),(3;3),…

2.  Зададим отношение в виде графа . Стрелки показывают пары, между которыми задано отношение.. Петли около элементов, показывают, что элем находится в заданном отношении сам с собой. В данном случае, каждое число есть делитель себя.

Свойства отношений.

  1. 1. Рефлективность. Для любых элементов справедливо аRa. Быть равным
  2. Антирефлективность.. Не выполняется  первое свойство, а именно, для любых элементов не справедливо   аRa. Быть больше
  3. Симметричность. Для любых элементов а ≠b, если  справедливо  аRb, то справедливо bRa для (выполняются одновременно). Параллельность прямых на плоскости.  Быть равным. Замечание: хотя бы для одной пары выполняется аRb и bRa.
  4. Антисимметричность. Для любых элементов а ≠b,, если  справедливо аRb, то  ложно bRa (не выполняются одновременно). Быть не больше. Быть делителем. Замечание: хотя бы для одной пары выполняется аRb,
  5. Асимметричность .Ни для одной пары не выполняется одновременно аRb и bRa. Число х больше числа b.
  6. Транзитивность. Для любых элементов, если aRb,  bRc? то aRc. Быть больше, Параллельность прямых. Замечание: могут участвовать равные элементы.
  7. Антитранзитивность. Отношение не обладает свойством транзитивности. Перпендикулярность прямых, Быть знакомым  .
  8. Связность. Для  любых  x  и  y   имеет место xRy  или yRx  Быть выше по росту среди людей, Замечание: все элементы заняты в отношении.

Виды отношений.

1. Отношение эквивалентности отношение, для которого выполняются одновременно  свойства: рефлективности, симметричности, транзитивности. Быть равным, Быть подобным

Отношение эквивалентности, заданное на некотором не пустом множестве, разбивает его на не пересекающие классы.. Отношение Иметь один возраст разбивать множество  людей (деревьев, животных и др.) на непересекающиеся классы

Эквивалентность часто обозначают символом Ω. – Заглавная буква омега.    Например,  А Ω В.

2. Отношение толерантности отношение, для которого выполняются одновременно  свойства: рефлективности и симметричности.  Транзитивность при этом не выполняется. Быть другом,  Параллельность

Толерантность является более слабой мерой сходства., но, тем не менее, может выявлять схожие и  отличительные  стороны элементов множества.

Свойства эквивалентности и толерантности  позволяют вести речь о схожести, рассматриваемых множеств или отдельных объектов. Например, по скольким совпадающим признакам можно судит о совпадении (равенстве) множеств или объектов.

3. Отношение порядка отношение, для которого выполняются одновременно  свойства: антисимметричности и  транзитивности

Выполнения и не выполнения остальных свойств позволяет указать  различные виды отношения порядка. Это, например,  строгий, нестрогий, линейный, частичный порядок и др..

Множество считается упорядоченным, если на нем установлено отношение порядка. В обыденной жизни, понятие порядок считается интуитивно понятным и трактуется как некоторая последовательность объектов, определенная система. Например: порядок на  столе, в классе, на производстве и др.

В любом случае  в упорядоченном множестве можно усмотреть последующий и предыдущий элемент (элементы), усмотреть некоторую подчиненность и соподчиненность, наличие начальника, заместителя  и других сотрудников

Предшествование иногда  обозначается  символом:

8. Элементы комбинаторики.

Комбинаторикой называется раздел математики, изучающий вопрос о том, сколько комбинаций определенного типа можно составить из элементов данного множества (группы) элементов (объектов)

Пусть дано множество, содержащее n элементов.

Размещением из n элементов по m называется комбинация (подмножество), содержащая   n элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования. Под размещение можно понимать любое упорядоченное множество, состоящее из n элементов, взятых из данного множества.

Anm =n(n-1)(n-2) …(n-m+1)

Перестановкой из n элементов называется любая комбинация из n элементов, отличающаяся от других только порядком следования. Под перестановкой можно понимать любое упорядоченное множество, составленное из n  элементов данного множества.

Р= n(n-1)(n-2) …3·2·1

Произведение n последовательных натуральных чисел называется факториалом и обозначается Р!, S!

Сочетанием из n элементов данного множества по m элементов, называется любая комбинация, состоящая из n элементов, взятых из данного множества, которые отличаются, по крайней мере, одним элементом. Под сочетанием можно понимать любое подмножество, содержащее n элементов, взятых из данного множества, состоящего из m элементов.

При вычислении сочетаний легко усмотреть свойства, которое упрощает вычисления:

Сnm =Cnn-m ,     С11 =1,            Сn n=1,            Cn1=n,             Сn0 =1

9. Подстановки.

Подстановкой, заданной на множестве En={1,2,3,…n} называется взаимнооднозначное отображение (соответствие, отношение) установленное на этом множестве.

Пусть дано взаимнооднозначное отображение σ(x) на множестве En={1,2,3,…n} при котором каждому элементу множества Еn (прообразу, аргументу) по правилу σ(x) поставлен в соответствие единственный элемент этого же множества Еn (образ), то Еn→Еn (отображение множества на себя) есть подстановка. Число n – есть степень подстановки

Множество En={1,2,3,…n} часто вызывают отрезком натуральных чисел. Индекс буква Е показывает число элементов множества.

Пример подстановки, заданной на множестве E5={1,2,3,4,5}, степени n=5.

σ=Первая строчка – аргументы, вторая – образы подстановки.

Если все аргументы подстановки записаны в порядке возрастания, то такая подстановка называется канонической подстановкой.

Любая подстановка путем упорядочивания  по аргументу пар аргумент – образ переводится в каноническую подстановку. Виду этого подстановку рекомендуется задавать в каноническом виде, если это не оговорено дополнительно или для решения некоторой задачи не требуется иная подстановка.

Множество подстановок, заданных на En={1,2,3,…n}, обозначается  Sn .Численность которого есть число перестановок, заданных на этом  множестве. Итак,  n(Sn)=n!

Подстановка называется тождественной, если элементы обоих ее строк записаны в порядке возрастания

σ=каноническая подстановка, e =- тождественная подстановка Произведение подстановок находится путем последовательного выполнения заданных подстановок.

, т.к. 2→4 в первой подстановке, 4→2 – во второй подстановке, поэтому 2→2. Аналогично 3→3→1, 1→1→4, 4→2→3.

Свойства умножения подстановок.

1. Перемножаются подстановки только одинаковой степени

2. Переместительный закон умножения подстановок не выполним, но сочетательный закон умножения подстановок выполним

3. σ ◦ e= σ, e тождественная подстановка

4. Любая подстановка имеет единственную обратную подстановку.

5. σn= σ ◦ σ ◦ σ ◦ … σ   умножение последовательно выполняется n раз

6.  σn ◦ σm = σn+m,  σ0= σ ◦ σ -1= e

Следствия:

1. n )m= σn + m

2. Любую подстановку, путем возведения в степень можно привести к тождественной подстановке. Если σk=e, то k – называется порядком подстановки.

Транспозиция - переставление двух любых  элементов второй (нижней) строки

Инверсия переставление (рокировка) двух соседних элементов второй (нижней) строки.

Инверсия – частный случай транспозиция

Выполнение достаточного числа инверсий подряд приводит каноническую подстановку к единичной, причем если таковых инверсий четное число, то подстановка вызывается четной в противном случае – нечетной подстановкой

Пусть r – число инверсий, приводящих подстановку к единичной подстановке и  (-1)r=1, то подстановка четная подстановка или со знаком + (реже говорят положительная), (-1)r=-1, то подстановка нечетная подстановка или со знаком – (реже говорят отрицательная)

Каждая выполненная инверсия  меняет четность этой подстановки.

Четное число транспозиций не меняет  знак подстановки, нечетное число транспозиций  меняет  знак подстановки

Число четных и нечетных подстановок одинаковое и равно n!/2.

Теория подстановок тесно связано с математической дисциплиной – теория групп, изучение которой в данном курсе математики не предусмотрено.

Практические задания

[1, 61-68с]

1. № 1-5, 1-14, 1-18, 1-24, 1-26, 1-28(б,г,е), 1-29(2,4,6), 1-30(2,4,6)

Контрольные вопросы

  1. Способы задания множеств.
  2. Классификация множеств.
  3. Виды операций над множествами
  4. Свойства операция над множествами.
  5. Определение кортежа.
  6. Примеры декартовых произведений.
  7. Сравните понятие:  соответствие,  отношение, отображение, функция.
  8. Порядок и его виды.
  9. Комбинаторные задачи.
  10. Действия над подстановками.

Требования к знаниям, умениям, навыкам

Требования к знаниям умениям и навыкам.   Студенты должны  иметь представление об основных понятиях теории множеств. Знать способы задания множеств. Уметь производить бинарные операции над множествами, устанавливать соответствия между множествами. Понимать свойства отношений, заданных на множестве. Уметь применять комбинаторные формулы а процессе решения комбинаторных задач.