Лекции и задания по дискретной математике

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНА МЕТАЛУРГІЙНА АКАДЕМІЯ УКРАЇНИ





Г.Г. ШВАЧИЧ, М.С. САЗОНОВА, Г.М. Бартенєв







ДИСКРЕТНА МАТЕМАТИКА

РОЗДІЛ 1. ТЕОРІЯ МНОЖИН. АЛГЕБРА МНОЖИН














Дніпропетровськ НМетАУ 2015
УДК 543. 211/.205+543.4
Швачич Г.Г., Сазонова М.С., Бартенєв Г.М. Дискретна математика. Розділ 1. Теорія множин. Алгебра множин: навчальний посібник (російською мовою).
· Дніпропетровськ: НМетАУ, 2015.  – 70 с.

Навчальний посібник містить доступно викладений теоретичний матеріал і рекомендації до виконання практичних робіт з дисципліни “Дискретна математика”(Розділ 1: теорія множин. Алгебра множин).
Наведено приклади розв’язування типових задач і варіанти завдань для індивідуального виконання.
Призначений для студентів напряму [ Cкачайте файл, чтобы посмотреть ссылку ]– комп’ютерні науки.
Іл. 45. Табл. 2. Бібліогр.: 9 найм.

Друкується за авторською редакцією.

Відповідальний за випуск Швачич Г.Г., зав. каф. ПМ та ОТ, д. т. н., проф.

Рецензенти:
Коряшкіна Л.С., завідувач кафедри обчислювальної математики та
математичної кібернетики Дніпропетровського національного 
університету імені Олеся Гончара,
к.ф.-м.н., доц.

Лебідь О.Ю., доцент кафедри вищої математики та інформатики Академії митної служби України, к.ф.-м.н., доц.

© Національна металургійна академія України, 2015
© Швачич Г.Г., Сазонова М.С.,
Бартенєв Г.М., 2015
Содержание

13 TOC \o "1-3" \h \z \u 1413 LINK \l "_Toc420342410" 141. МНОЖЕСТВА 13 PAGEREF _Toc420342410 \h 1441515
13 LINK \l "_Toc420342411" 141.1. МНОЖЕСТВО И ЕГО ЭЛЕМЕНТЫ 13 PAGEREF _Toc420342411 \h 1441515
13 LINK \l "_Toc420342412" 141.2. СПОСОБЫ ЗАДАНИЯ МНОЖЕСТВ 13 PAGEREF _Toc420342412 \h 1451515
13 LINK \l "_Toc420342413" 141.3. ПУСТОЕ МНОЖЕСТВО 13 PAGEREF _Toc420342413 \h 14131515
13 LINK \l "_Toc420342414" 141.4. ПАРАДОКС РАССЕЛА 13 PAGEREF _Toc420342414 \h 14131515
13 LINK \l "_Toc420342415" 141.5. ПОДМНОЖЕСТВА И ИХ СВОЙСТВА 13 PAGEREF _Toc420342415 \h 14131515
13 LINK \l "_Toc420342416" 142. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 13 PAGEREF _Toc420342416 \h 14181515
13 LINK \l "_Toc420342417" 143. ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ МНОЖЕСТВ 13 PAGEREF _Toc420342417 \h 14251515
13 LINK \l "_Toc420342418" 143.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна 13 PAGEREF _Toc420342418 \h 14271515
13 LINK \l "_Toc420342419" 144. БУЛЕВЫ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 13 PAGEREF _Toc420342419 \h 14341515
13 LINK \l "_Toc420342420" 144.1. МОЩНОСТЬ КОНЕЧНОГО МНОЖЕСТВА 13 PAGEREF _Toc420342420 \h 14341515
13 LINK \l "_Toc420342421" 144.2. БУЛЕАН МНОЖЕСТВА. РАЗБИЕНИЕ МНОЖЕСТВА 13 PAGEREF _Toc420342421 \h 14391515
13 LINK \l "_Toc420342422" 144.3. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. ПОНЯТИЕ УПОРЯДОЧЕННОГО МНОЖЕСТВА 13 PAGEREF _Toc420342422 \h 14401515
13 LINK \l "_Toc420342423" 144.4. СООТВЕТСТВИЯ МЕЖДУ МНОЖЕСТВАМИ. ОБРАЗ И ПРОООБРАЗ. БИНАРНЫЕ СООТВЕТСТВИЯ 13 PAGEREF _Toc420342423 \h 14441515
13 LINK \l "_Toc420342424" 144.5. СПОСОБЫ ЗАДАНИЯ БИНАРНЫХ СООТВЕТСТВИЙ 13 PAGEREF _Toc420342424 \h 14471515
13 LINK \l "_Toc420342425" 144.6. ТИПЫ (СВОЙСТВА) БИНАРНЫХ СООТВЕТСТВИЙ 13 PAGEREF _Toc420342425 \h 14501515
13 LINK \l "_Toc420342426" 144.7. ОБРАТНОЕ СООТВЕТСТВИЕ 13 PAGEREF _Toc420342426 \h 14541515
13 LINK \l "_Toc420342427" 144.8. ФУНКЦИЯ 13 PAGEREF _Toc420342427 \h 14551515
13 LINK \l "_Toc420342428" 144.9. ОТНОШЕНИЕ НА МНОЖЕСТВЕ 13 PAGEREF _Toc420342428 \h 14601515
13 LINK \l "_Toc420342429" 144.10. ОСНОВНЫЕ ТИПЫ (СВОЙСТВА) БИНАРНЫХ ОТНОШЕНИЙ 13 PAGEREF _Toc420342429 \h 14621515
13 LINK \l "_Toc420342430" 144.11. ОСНОВНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙ 13 PAGEREF _Toc420342430 \h 14661515
13 LINK \l "_Toc420342431" 14ЛИТЕРАТУРА 13 PAGEREF _Toc420342431 \h 14701515
15
1. МНОЖЕСТВА
1.1. МНОЖЕСТВО И ЕГО ЭЛЕМЕНТЫ
Понятие множества обычно принимается за одно из исходных ([ Cкачайте файл, чтобы посмотреть ссылку ]) понятий, то есть несводимое к другим понятиям, а значит, и не имеющее определения (так же, как, например, нельзя определить, что такое точка или прямая).
Теорию множеств создал Георг Кантор. В частности, определил множество как «единое имя для совокупности всех объектов, обладающих данным свойством». Эти объекты он назвал [ Cкачайте файл, чтобы посмотреть ссылку ]. Т.е. элемент множества – это объект, принадлежащий данному множеству.
Бертран Рассел (также основоположник теории множеств) дал такое определение множества: «Множество есть любое собрание определённых и различимых между собою объектов нашей интуиции или интеллекта, мыслимое как единое целое».
Под множеством понимается класс, совокупность, собрание различных между собой абстрактных объектов (элементов), безразлично какой природы. Каждый составляющий его элемент рассматривается лишь с точки зрения некоторых признаков. Эти объекты считаются неразличимыми. Им приписываются одни и те же признаки, отличие их друг от друга определяется не по свойствам и отношениям, а по их именам.
Множества обозначаются большими латинскими буквами (например, А, В, Х, Y и т.д.), а элементы этих множеств – малыми буквами (например, a, b, x, y).
Если множество содержит конечное число элементов, его называют конечным, если в нём бесконечно много элементов – бесконечным.
Множества могут состоять из объектов самой различной природы. Этим объясняется чрезвычайная широта теории множеств и её применимость в самых различных областях – математике, механике, физике, химии, биологии, лингвистике и т.д.
Знаком ( обозначается отношение принадлежности некоторого элемента тому или иному множеству. Например, выражение 13 EMBED Equation.DSMT4 1415означает, что элемент а принадлежит множеству А. Если же а не является элементом множества А, то это записывается 13 EMBED Equation.DSMT4 1415.

Если два множества А и В состоят из одних и тех же элементов, то они считаются равными. Если А и В равны, то пишем А=В, в противном случае 13 EMBED Equation.DSMT4 1415. Например, возьмём множество {1,3,5}, состоящее из трёх положительных нечётных чисел. Поскольку {1,3,5} и{1,5,3} состоят из одних и тех же элементов, они являются равными множествами, т.е. {1,3,5}={1,5,3}. По этой же причине {1,3,5}={1,3,3,5,5,5}.
Элементы какого либо множества сами могут быть множествами. Например, {{1,2},{3,4},{5,6}} – множество из трёх элементов {1,2},{3,4},{5,6}.
Множества {{1,2},{2,3}} и {1,2,3} не равны, т.к. элементами первого являются {1,2} и {2,3}, а элементами второго 1,2 и 3.
Множества {{1,2}} и {1,2} также не равны, т.к. поскольку первое множество состоит из одного и только одного элемента {1,2} (одноэлементное множество), а второе имеет два элемента 1 и 2. Потому, в общем виде, следует различать объект и множество, единственным элементом которого является этот объект.
Задача 1.1. Среди следующих множеств указать равные:
А = {3, 5, x, y}; B = {3, 2, 5, x, y}; C = {y, y, 5, 3, x, x}; D = {3, 4, 5, x, y}.
Решение. A = C, поскольку качественно оба множества состоят из элементов 3, 5, x и y. Количество элементов множества А равно 4. Множество В, на первый взгляд, содержит больше элементов. Однако среди них есть повторяющиеся: 2 раза х и столько же у. Для множества же неважно, сколько раз повторяется один и тот же элемент, важно лишь, чтобы элементы отличались друг от друга. Что же касается множеств B и D, то они не равны, так как содержат разные элементы.

1.2. СПОСОБЫ ЗАДАНИЯ МНОЖЕСТВ
Множество считают заданным (известным), если имеется способ, позволяющий для любого объекта решить, принадлежит ли он этому множеству или нет, т.е. определить истинно или ложно выражение 13 EMBED Equation.DSMT4 1415. Существует несколько способов задания множеств. Множество может быть задано:
перечислением (полным списком) своих элементов. Если хотим сказать, что данное множество М состоит из элементов 13 EMBED Equation.DSMT4 1415, то записываем: 13 EMBED Equation.DSMT4 1415 . Данный способ применим лишь к конечным множествам, да и то не ко всем. Например, хотя множество птиц конечно, вряд ли его можно задать списком. Тем более, список невозможен в случае бесконечномерного множества. Тогда применимы другие способы;
характеристическим свойством (предикатом), которым должны обладать все его элементы и не должен обладать ни один объект, не являющийся его элементом. Причём необходимо формулировать описание характеристических свойств элементов множества достаточно корректно, для того, чтобы множество было определено вполне однозначно.
Множество M объектов, обладающих свойством 13 EMBED Equation.DSMT4 1415, Г. Кантор обозначил 13 EMBED Equation.DSMT4 1415 «множество всех x, обладающих свойством 13 EMBED Equation.DSMT4 1415», где 13 EMBED Equation.DSMT4 1415 - характеристическое свойство(предикат) множества М;
порождающей процедурой f, то есть указать правило, по которому формируются элементы данного множества: 13 EMBED Equation.DSMT4 1415;
Замечание. Многие числовые множества могут быть заданы всеми тремя указанными способами (например, множество чётных однозначных чисел).
геометрическим способом – с помощью графиков или диаграмм. Этот способ применим как к конечным, так и бесконечным множествам;
Пример 1.1. Некоторые примеры множеств, заданных различными способами.
а) M1={1;2;3;4};
б) M2={x|13 EMBED Equation.DSMT4 1415, -4в) M3={x|x=2n+1, 13 EMBED Equation.DSMT4 1415};
г) M4= {(x,y)(x(R, y(R ; 13 EMBED Equation.DSMT4 1415 ( 4};
Задача 1.2. Выяснить, каким способом заданы следующие множества и перечислить все элементы этих множеств:
{ x( x есть делитель числа 100};
{ x( x есть простой делитель числа 100};
{ x( x есть простой множитель числа 100};
{ x( x (N; 13 EMBED Equation.DSMT4 1415– 1 = 0 и 13 EMBED Equation.DSMT4 1415 – 4 = 0};
{ x( x есть буква слова «академия»};
{ x( x (N; 213 EMBED Equation.DSMT4 1415= 1};
{ x( x (N; 13 EMBED Equation.DSMT4 1415}.

Решение.
Данное множество состоит из всех делителей числа 100, то есть в него включаются лишь те числа, которые делят число 100 нацело. Очевидно, что налицо задание множества с помощью характеристического предиката «быть делителем числа 100». Перечислим все эти числа: 2, 4, 5, 10, 20, 25, 50. Добавив сюда число 1 и самое 100, получим искомое множество. Обозначим его А. Тогда А = {1, 2, 4, 5, 10, 20, 25, 50, 100}.
Множество задано с помощью характеристического предиката «быть простым делителем числа 100». Среди делителей предыдущей задачи отберём лишь простые числа, которыми будут 2 и 5. Все же остальные делители являются составными. Число 1, как известно из курса школьной арифметики, не относится ни к простым, ни к составным числам. Обозначив это множество В, получим: В = {2, 5}.
Множество задано с помощью характеристического предиката «быть простым множителем числа 100». Разложим 100 на простые множители. Получим следующее тождество: 100 = 2(2(2(5. Эти числа и будут элементами искомого множества, которое обозначим С = {2, 2, 5, 5}. Ответ можно было бы оставить в таком виде, однако в теории множеств количество одинаковых элементов, как правило, игнорируется. Поэтому будет корректнее ответ представить в виде: С = {2, 5}.
Данное множество можно считать заданным с помощью порождающей процедуры, которой является процедура решения квадратных уравнений и отбора корней по признаку принадлежности их к множеству натуральных чисел. Однако, справедливости ради, следует отметить, что часто при определении способа задания множества бывает достаточно трудно утверждать, что множество задано этим и только этим способом. В данном примере вполне можно утверждать, что способ задания множества – с помощью характеристического предиката «отбор корней уравнения по признаку принадлежности к множеству N». Решаем оба уравнения: 13 EMBED Equation.DSMT4 1415, его корни +1 и -1; 13 EMBED Equation.DSMT4 1415, его корни +2 и -2. Поскольку числа -1 и -2 не являются натуральными, искомое множество, которое мы обозначим D, будет таким: D = {1, 2}.
Способ задания – с помощью характеристического предиката. Обозначим множество Е. Получим: Е = {а, к, д, е, м, и, я}, где буква «а» упомянута лишь один раз.
Способ задания данного множества аналогичен примеру 4). Решим данное показательно-логарифмическое уравнение 213 EMBED Equation.DSMT4 1415 = 1. ОДЗ данного уравнения – все х(0. 13 EMBED Equation.DSMT4 1415 = 1, откуда 13 EMBED Equation.DSMT4 1415 = 0, корни х равны 13 EMBED Equation.DSMT4 1415 2. Натуральным числом является 2. Значит, наше множество, которое обозначим через F, будет состоять только из одного элемента: F = {2}.
Способ задания данного множества аналогичен примеру 4). Решаем данное иррациональное неравенство 13 EMBED Equation.DSMT4 1415. ОДЗ – все х ( 1. Обе части возведём в квадрат: х – 1 ( 4, откуда х ( 5. Это не противоречит ОДЗ, поэтому область решения данного неравенства х ( 5. Другими словами, х ( [5; (]. Очевидно, что натуральных чисел на данном интервале будет бесчисленное множество. Поэтому данное множество G будет бесконечным: G = {5, 6, 7, n,}.
Задача 1.3. Записать множества с помощью свойства P(х):
{2, 3, 11};
{1, 3, 9, 27, 81, 243};
{s, t, u, d, e, n, t}.
Решение.
подобрать характеристический предикат можно, например, так. Перемножим все числа. Получим: 2(3(11 = 66. Тогда
А = {a(a – простой делитель числа 66};
все представленные числа являются степенями числа 3 (30=1, 31=3, 32=9 и т.д.). Поэтому множество В можно задать с помощью свойства: В = {b(b – степень числа 3 с показателем от 0 до 5};
C = {c(c – буква слова «student»}.
Задача 1.4. Изобразить следующие множества графически:
А = {(x,y)(x(R, y(R ; 13 EMBED Equation.DSMT4 1415 ( 4};
B = {(x,y)(x(R, y(R ; x + y (0, x + y – 2 ( 0};
C = {(x,y)(x(R, y(R ; (x ( ( 1 и (y + 2( ( 4};
D = {(x,y)(x(R, y(R и 13 EMBED Equation.DSMT4 1415};
E = {(x,y)(x(R, y(R и y ( (sin x(};
F = {(x,y)(x(R, y(R и 13 EMBED Equation.DSMT4 1415}.
Решение. Все заданные множества состоят из пар действительных чисел, которые удовлетворяют некоторым условиям. Изображая точки, соответствующие данным парам в декартовой системе координат на плоскости, получим некоторые области, которые и будут геометрическим (графическим) изображением исследуемого множества.
Построим границу множества А. Для этого от неравенства перейдём к равенству: 13 EMBED Equation.DSMT4 1415 = 4. Из курса аналитической геометрии известно, что это уравнение есть уравнение окружности с центром в начале координат и радиусом 2. Она и будет являться границей множества. Далее следует выяснить, какую часть плоскости нам следует выбрать: ту, что лежит внутри окружности либо ту, что лежит извне. Для этого зададимся координатами какой-либо точки, которая явно находится в выбранной области. Например, точка начала координат О(0;0). Подставим значения х = 0 и у = 0 в неравенство 13 EMBED Equation.DSMT4 1415 ( 4. Получим: 13 EMBED Equation.DSMT4 1415 ( 4, то есть в точке О (0;0) данное неравенство справедливо. Следовательно, нам нужно выбрать часть плоскости внутри окружности. Если взять координаты других точек внутри окружности и подставить их в неравенство, результат будет таким же. Напротив, для точек извне неравенство будет ложным. Например, точка Q(10;10): 13 EMBED Equation.DSMT4 1415 = 200, а это никак не меньше 4! Подытоживая всё сказанное, можем утверждать, что множество А – это круг радиуса 2 с центром в начале координат.
13 SHAPE \* MERGEFORMAT 1415
Для построения границ множества В рассмотрим равенства: x + y =0, x + y – 2 = 0. Первая прямая (её уравнение можно записать как у = ( х ) есть биссектриса 2-го и 4-го координатных углов. Она разделяет координатную плоскость на две части: ту, которая лежит выше (или правее) прямой и ту, которая ниже (или левее) прямой. Чтобы выбрать нужную часть, возьмем пробную точку с координатами, например, Q(10;10) и подставим её координаты в неравенство x + y ( 0. Получим: 10 +10 ( 0 то есть неравенство справедливо для части плоскости выше (правее) прямой x + y =0. Вторая прямая (её уравнение x + y – 2 = 0 может быть записано в отрезках на осях 13 EMBED Equation.DSMT4 1415) отсекает на обеих осях отрезки длиной по 2 единицы и проходит параллельно первой прямой через 2-й, 1-й и 3-й квадранты. Она также разделяет координатную плоскость на две части: одна выше (правее) и вторая ниже (левее). Для выбора нужной нам части можно использовать, например, точку О(0;0). Подставляем х = 0 и у = 0 в неравенство x + y – 2 ( 0. Получим: 0 + 0 – 2 ( 0 справедливо. Следовательно выбираем ту часть плоскости по отношению ко второй прямой, где лежит точка О(0;0). В итоге получаем область, координаты точек которой удовлетворяют обоим неравенствам (например, это точки (1;1), (0;1), (1;0); (2;-1) и т.д.). Это полоса, лежащая между двумя параллельными прямыми, включая и точки, принадлежащие второй прямой (поскольку неравенство нестрогое). Данная область и определяет искомое множество В.
Неравенство (x ( ( 1 эквивалентно двум: (1 ( х ( 1. Казалось бы, что это множество точек отрезка [-1; 1]. Если бы мы рассматривали множество из одного элемента, это было бы так. Однако наше множество С состоит из пар действительных чисел (х; у). Поэтому геометрически неравенство (1 ( х ( 1 представляет собой множество точек, лежащих внутри вертикальной полосы между прямыми х = 1 и х = (1. Неравенство (y + 2( ( 4 также эквивалентно двум: (4 ( y + 2 ( 4. Перенося 2 влево и вправо, получаем: (6 ( y ( 2. Геометрически это будет множество точек, лежащих внутри горизонтальной полосы между прямыми y = (6 и y = 2. Итак, мы получили две пересекающиеся полосы. Какую же часть необходимо выбрать для искомого множества С? В условии задачи оба неравенства соединены союзом «и». А это значит, что необходимо выбрать те точки из обеих полос, координаты которых одновременно удовлетворяют обоим неравенствам. В результате получаем прямоугольник. Это и есть наше множество С.
13 SHAPE \* MERGEFORMAT 1415
Рассмотрим неравенство 13 EMBED Equation.DSMT4 1415. Чтобы оно стало «узнаваемым», возведём в квадрат левую и правую его части. Это можно сделать потому, что справа - неотрицательная величина арифметического корня. Слева величина у также неотрицательна, ибо в противном случае неравенство теряло бы всякий смысл. После возведения во вторую степень обеих частей и некоторого преобразования получаем: 13 EMBED Equation.DSMT4 1415 Это неравенство описывает часть координатной плоскости, лежащей вне эллипса 13 EMBED Equation.DSMT4 1415 Однако исходное неравенство имеет вид 13 EMBED Equation.DSMT4 1415, причём, как было сказано, величина у неотрицательна. Значит, описываемая область будет включать лишь верхнюю часть координатной плоскости, лежащей вне эллипса. Рассмотрим последнее неравенство х ( 0, которое описывает правую часть координатной плоскости. Сопоставляя все выкладки, получим множество точек, расположенных в первом квадранте вне эллипса. Это и будет искомое множество D.
Построим график функции у = sin x, а затем ту его часть, которая находится ниже оси абсцисс, зеркально отразим на верхнюю полуплоскость. Получим график у = |sin x|. Неравенство же y ( (sin x( определит искомое множество Е, точки которого будут находиться между осью абсцисс и дугами отраженной вверх синусоиды.
В отличие от предыдущих задач, здесь имеем равенство x2 = y2 , которое, как известно, определяет некоторую линию. Для «узнавания» данной линии сделаем ряд тождественных преобразований: 13 EMBED Equation.DSMT4 1415= 0, (х – у) (х + у) = 0. Далее приходим к совокупности х – у = 0 и х + у = 0. Получаем пару пересекающихся прямых - биссектрис 1
· 3-го и 2 – 4-го квадрантов. Множество F и представляет собой точки этих прямых.
13 SHAPE \* MERGEFORMAT 1415
Задачи для самостоятельного решения.
1. Перечислить все элементы следующих множеств:
{ x( x есть делитель чисел 6 и 8}; (ответ: 2);
{ x( x(N; x3 ( 5x2 + 4 = 0}; (ответ: 1);
{ x ( x(R; x + 1/x ( 2; x ( 0}; (ответ: х((0, ());
{ x ( x – буква слова «университет»};
{ x ( x(Z; sin x < 0; cos x > 0}; (ответ: -1).
2. Изобразить следующие множества графически:
{ (x, y)( y ( 2x2 };
{ (x, y)( y ( |x| + 1};
{ (x, y)( x2 + y2 – 25 > 0}.
Два первые способа задания множества предполагают, что мы имеем возможность отождествлять и различать объекты. Но такая возможность существует не всегда, в этом случае мы сталкиваемся с различного рода осложнениями. Так, может быть, что два различных характеристических свойства задают одно и то же множество, т.е. каждый элемент, обладающий одним свойством, обладает и другим, и наоборот. Например, в арифметике свойство «целое число делится на 2» задаёт то же множество, что и свойство «последняя цифра делится на 2». Во многих случаях речь идёт о совпадении двух множеств (например, множества равносторонних треугольников с множеством равноугольных треугольников). Кроме того, при задании множеств характеристическими свойствами (предикатами) трудности возникают из-за недостаточной чёткости, неоднозначности формулировки. Разграничение объектов на принадлежащие и не принадлежащие данному множеству затрудняется наличием большого числа промежуточных форм.
Особо выделяется универсальное (или фундаментальное) множество, т.е. такое множество, которое состоит из всех элементов исследуемой предметной области (обозначается буквой U и читается «универсум», а в геометрической интерпретации изображается множеством точек внутри некоторого прямоугольника).
Отметим, что «универсальное множество» понятие относительное: оно выбирается для какого-нибудь определенного раздела науки и при том часто даже явно не определяется, а просто подразумевается.
Так, например, в элементарной планиметрии в качестве универсального множества принято рассматривать множество всех точек плоскости.
В элементарной арифметике универсальным множеством считается множество Z всех целых рациональных чисел и т. д.
1.3. ПУСТОЕ МНОЖЕСТВО
Пустое множество – множество, которое не содержит ни одного элемента (обозначается символом 13 EMBED Equation.DSMT4 1415). Пустое множество можно определить любым противоречивым свойством, например 13 EMBED Equation.DSMT4 1415= {х | x13 EMBED Equation.DSMT4 1415 х}, в области множеств оно играет как бы роль нуля. Многие математические (и не только математические) проблемы можно сформулировать как задачи о пустоте некоторых множеств.
1.4. ПАРАДОКС РАССЕЛА
Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: Y={X | X 13 EMBED Equation.DSMT4 1415X}. Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если Y 13 EMBED Equation.DSMT4 1415 Y, то Y 13 EMBED Equation.DSMT4 1415Y. С другой стороны, если Y 13 EMBED Equation.DSMT4 1415Y, то Y 13 EMBED Equation.DSMT4 1415 Y. Получается неустранимое логическое противоречие, известное как парадокс Рассела. Это противоречие можно разрешить различными способами, в целом сводящимися к тому, что Y не является множеством.

1.5. ПОДМНОЖЕСТВА И ИХ СВОЙСТВА
Подмножество – это любая часть основного множества U. При этом элементы его подмножества A обладают некоторым дополнительным свойством Pа(х). Этот факт можно записать так: А = { x(x(U и Pа(х)} («А – это по определению множество всех тех и только тех х, которые принадлежат U и обладают свойством Pа»). Если, например, U – множество людей, а Pа – быть учащимся высшего учебного заведения, то А – множество студентов.
Если свойство, задающее некоторое подмножество, противоречит свойству, по которому задаётся само основное множество, то данное подмножество будет пустым (, то есть не содержащим ни единого элемента.
Полная и пустая части всякого множества образуют его несобственные подмножества. Все остальные подмножества данного множества являются собственными.
Отношение между множеством M и любым его подмножеством A называется включением и обозначается символом [ Cкачайте файл, чтобы посмотреть картинку ]: A[ Cкачайте файл, чтобы посмотреть картинку ]M.
Отметим следующие свойства подмножеств, прямо вытекающих из определения.
а) Отношение включения любого собственного подмножества A (т.е. отличного от M) в множество M, называется собственным и обозначается [ Cкачайте файл, чтобы посмотреть картинку ]: A[ Cкачайте файл, чтобы посмотреть картинку ]M.
Выражение А ( M (читается «А включено в M») означает, что множество А есть подмножеством множества M. При этом все элементы, принадлежащие А, будут также принадлежать и M. Однако в множестве M могут найтись элементы, не принадлежащие А. В этом случае множество А – собственное подмножество множества M, а M, в свою очередь, называется надмножеством. Можно также рассматривать и выражение M ( А, которое читается «M включает в себя А».
Равными считаются множества A и B, состоящие качественно из одних и тех же элементов. Факт равенства множеств записывается так: А = B, неравенства А ( B.
Выражение А ( M обозначает включение в широком смысле, то есть А есть подмножеством M. При этом не исключено, что А = M. Можно также рассматривать и выражение M ( А.
Два множества А и В равны тогда и только тогда, когда А ( В, а В ( А.
Принято считать, что пустое множество [ Cкачайте файл, чтобы посмотреть картинку ] является подмножеством любого множества M (пустой его частью).
Каждое непустое множество М является подмножеством самого себя: М[ Cкачайте файл, чтобы посмотреть картинку ]М (Если свойства, которыми заданы некоторое множество и его подмножество, совпадают (одни и те же), то эти множества будут равны. Поэтому и считается, что множество является частью самого себя).
б) Отношение включения транзитивно, т. е. из A[ Cкачайте файл, чтобы посмотреть картинку ]B и B[ Cкачайте файл, чтобы посмотреть картинку ]C следует, что A[ Cкачайте файл, чтобы посмотреть картинку ]C. Транзитивно также отношение собственного включения, т. е. из A13 EMBED Equation.DSMT4 1415B и B13 EMBED Equation.DSMT4 1415C следует, что A13 EMBED Equation.DSMT4 1415C.
в) Очень важно не смешивать отношения принадлежности [ Cкачайте файл, чтобы посмотреть картинку ] (элемента) и включения [ Cкачайте файл, чтобы посмотреть картинку ] (подмножества): если подмножество {а}[ Cкачайте файл, чтобы посмотреть картинку ]М, то элемент а[ Cкачайте файл, чтобы посмотреть картинку ]М, и наоборот; но из {a}[ Cкачайте файл, чтобы посмотреть картинку ]М не следует {а}[ Cкачайте файл, чтобы посмотреть картинку ]М (т.е. из того, что подмножество {a} включено в М, не следует, что элементом множества М будет множество {a}). Так, например, если М = {1, 2, {3, 4}}, то это означает, что 1[ Cкачайте файл, чтобы посмотреть картинку ]М и 2[ Cкачайте файл, чтобы посмотреть картинку ]М, {3, 4}[ Cкачайте файл, чтобы посмотреть картинку ]M; но из {1, 2}[ Cкачайте файл, чтобы посмотреть картинку ]M не следует, что элементом множества М будет множество {1,2}.
Отметим, что для рассмотренного множества M правильны следующие утверждения включения:
[ Cкачайте файл, чтобы посмотреть картинку ][ Cкачайте файл, чтобы посмотреть картинку ]М, {1}[ Cкачайте файл, чтобы посмотреть картинку ]М, {2}[ Cкачайте файл, чтобы посмотреть картинку ]М, {{3, 4}}[ Cкачайте файл, чтобы посмотреть картинку ]М, {1, 2}[ Cкачайте файл, чтобы посмотреть картинку ]М, {1, {3, 4}}[ Cкачайте файл, чтобы посмотреть картинку ]М,{ 2, {3, 4}}[ Cкачайте файл, чтобы посмотреть картинку ]М, {1, 2, {3, 4}}[ Cкачайте файл, чтобы посмотреть картинку ]М.
Другой пример. Пустое множество [ Cкачайте файл, чтобы посмотреть картинку ]не имеет элементов х[ Cкачайте файл, чтобы посмотреть картинку ][ Cкачайте файл, чтобы посмотреть картинку ]для любого объекта х. Между тем [ Cкачайте файл, чтобы посмотреть картинку ]содержит одно подмножество, а именно само себя.
г) Если известно число элементов данного множества, то общее число подмножеств будет 13 EMBED Equation.DSMT4 1415, где n – число элементов. Из пустого подмножества можно образовать только одно подмножество – само пустое множество (при n=0, 13 EMBED Equation.DSMT4 1415)
Задача 1.5. Дано универсальное множество U = {1,2,3,20} – натуральные числа от 1 до 20. Найти следующие подмножества:
множество простых чисел;
множество делителей числа 20;
множество чисел, делящихся на 6;
множество квадратов чисел;
множество разностей предыдущего и последующего элементов универсума.
Решение.
множество простых чисел: А = {2, 3, 5, 7, 11, 13, 17, 19}. Очевидно, что А ( U;
множество делителей числа 20: В = {1, 2, 4, 5, 10, 20}. Здесь также В ( U;
множество чисел, делящихся на 6: С = {6, 12, 18}, C ( U;
множество квадратов чисел: D = {1, 4, 9, 16}. По условию задачи D ( U, и мы должны рассмотреть лишь множество тех квадратов чисел, которые не выйдут за пределы универсума;
множество Е = {x1- x2; x2- x3; x19- x20}. Совершенно очевидно, что полученное множество не есть подмножеством данного универсума. Иными словами, предикат, по которому оно формируется, противоречит предикату универсума. Таким образом Е ( V, хотя по условию Е ( V. Значит Е = (.

Задача 1.6. Среди следующих множеств указать равные: А = {3, 5, x, y}; B = {3, 2, 5, x, y}; C = {y, y, 5, 3, x, x}; D = {3, 4, 5, x, y}.
Решение. A = C, поскольку качественно оба множества состоят из элементов 3, 5, x и y. Количество элементов множества А равно 4. Множество В, на первый взгляд, содержит больше элементов. Однако среди них есть повторяющиеся: 2 раза х и столько же у. Для множества же неважно, сколько раз повторяется один и тот же элемент, важно лишь, чтобы элементы отличались друг от друга. Что же касается множеств B и D, то они не равны, так как содержат разные элементы. Можно лишь утверждать, что А ( В, А ( D, C ( B и C ( D.
Задача 1.7. Будут ли равны между собой множества А и В и, если нет, то почему?
A = {1, (2, 5), 6} , B = {1, 2, 5, 6};
A = {1, {2, 5}, 6} , B = {1, {5, 2}, 6};
A = {1, {2, 7}, 6} , B = {1, (2, 7), 6};
A = (, B = {(};
A = {0}, B = {(}.
Решение.
A ( B. Разберём, почему. Множество В состоит из элементов 1, 2, 5 и 6. В отличие от А, элементами которого являются 1, 6 и упорядоченная пара чисел (2, 5). Элементы обоих множеств качественно различны. Поэтому эти множества и не равны.
А = В. Элементами множества А являются числа 1 и 6, а также подмножество {2, 5}. Множество В также состоит из элементов 1 и 6, а также подмножества {5, 2}. Очевидно, что подмножества {2, 5} и {5, 2} равны. Следовательно множества А и В состоят из одних и тех же элементов. Значит, они равны.
A ( B. Оба множества имеют одинаковые элементы 1 и 6. Однако элементом А является подмножество {2, 7}, а элементом В есть упорядоченная пара чисел (2, 7). Понятно, что это качественно различные элементы. Следовательно, множества не равны.
A ( B. Множество А – это пустое множество, не содержащее ни одного элемента. В состав же множества В входит один элемент, которым является пустое множество.
A ( B. Множество А имеет один элемент – это число 0. Множество В также состоит из одного элемента, которым является множество, в данном случае пустое. Это качественно разные элементы.
Задачи для самостоятельного решения.
1. Записать следующие утверждения, используя символы теории множеств:
множество S есть подмножество Т;
х принадлежит множеству Р;
множество Y не является подмножеством множества Х;
z не принадлежит множеству Z.
2. Заданы четыре множества: А = {1, 3, 5, 7}; B = {3, 5}; C = {2}; D = {5, 7, 9}. Какие из следующих утверждений являются истинными, а какие ложными?
В ( А (ответ: верно);
( ( D (ответ: неверно, хотя пустое множество и включено в D, но не в качестве его элемента, а в качестве подмножества);
С ( В (ответ: неверно);
В ( D (ответ: неверно);
В ( А (ответ: неверно, хотя В и включено в А, но как подмножество, а не как элемент);
С ( В (ответ: верно).

2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Рассмотрим некоторое универсальное множество U и его подмножества А, В, С и т.д. Для наглядности будем изображать множества геометрически с помощью диаграмм Эйлера-Венна. При этом универсальное множество принято обозначать прямоугольником, а его подмножества – произвольными геометрическими фигурами (чаще всего кругами) (см. рис. 2.1).




На рисунке 2.1 изображено множество А ( U , А = {x( x ( A и x ( U}.
На множестве всех возможных подмножеств универсума (включая пустое множество ( и само универсальное множество U) определим следующие пять операций: дополнение, объединение, пересечение, разность и симметрическую разность.
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
1. Дополнением множества А (обозначается A, читается «не-А») называется множество, состоящее из всех тех и только тех элементов х из U таких, которые не принадлежат множеству А, т.е. :

· = {x( x ( V и х ( А}.
На рисунке 2.2 серым цветом изображено множество
· – дополнение множества А.
Операция дополнения обладает свойствами:
1) 13 EMBED Equation.DSMT4 1415– инволюция;
2) 13 EMBED Equation.DSMT4 1415(.
3)(Ш = U.
Видно, что любой элемент универсального множества принадлежит либо А, либо
·, но не может принадлежать обоим.
2. Объединением множеств А и В (обозначается А ( В, читается «объединение А с В», можно читать «А или В») называется множество, состоящее из всех тех и только тех элементов х, которые принадлежат хотя бы одному из множеств А или В, т.е.
А ( В = {x( x( A или x( B}.
Замечание. Союз “или” з определению десь употреблён в смысле “и/или”.
Например:
{1,2,3} ({1,3,4}={1,2,3,4}.
На рисунке 2.3 серым цветом изображено множество А ( В.
Операция объединения множеств обладает свойствами:
А ( А = А – идемпотичность;
А ( (В ( С) = (А ( В) ( С – ассоциативность;
А ( В = В ( А – коммутативность;
А ( ( = А, А ( U = U;
А (
· = U.
3. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству А, так и множеству В.
А ( В = {x( x ( A и х ( В}
На рисунке 2.4 серым цветом изображено пересечение множеств А и В.
Операция пересечения обладает свойствами:
А ( А = А идемпотичность;
А (
· = (;
А ( ( В ( С) = (А ( В) ( С – ассоциативность;
А ( В = В ( А – коммутативность;
А ( ( = (; А ( U = А.
4. Разностью множества А и множества В называется множество, состоящее из тех и только тех элементов множества А, которые не принадлежат множеству В.
A \ B = {x| x (A и x ( B}
Разность множеств А и В, исходя из данного определения, можно также задать как А ( 13 EMBED Equation.DSMT4 1415.
На рисунке 2.5 серым цветом изображена разность множества А и В.
5. Симметрической разностью множества А и множества В называется множество, состоящее из тех и только тех элементов, принадлежащих множеству А или множеству В, исключая элементы, принадлежащие обоим множествам одновременно.
A ( B = {x| x ( A и x ( B или x ( A и x ( B}
На рисунке 2.6 серым цветом изображена симметрическая разность множеств.
Данная операция обладает следующими свойствами:
А ( В = В ( А - коммутативность;
(А ( В) ( С = А ((В ( С) – ассоциативность;
А ( ( = ( ( А – существование нейтрального элемента;
А ( (В ( С) = (А ( В) ( (А ( С) – дистрибутивность относительно пересечения.
Симметрическая разность с помощью определенных ранее операций может быть представлена в виде: A(B=(А\В)((В\А) или A(B=(А(В)\(А( В).
Следует также отметить, что иногда эту операцию называют дизъюнктивной суммой и обозначают знаком ( или (.
Замечание 2.1. Над множествами, полученными в результате указанных пяти операций, можно в свою очередь производить те же самые операции. Так, например, можно образовывать дополнения пересечения 13 EMBED Equation.DSMT4 1415, объединения 13 EMBED Equation.DSMT4 1415 или разности 13 EMBED Equation.DSMT4 1415; можно образовывать пересечение объединений (А(В) ( (С( D) или объединение пересечений (А(В) ( (С( D) и т.д.
Замечание 2.2. Для указания порядка операций применяются скобки. Отношение между скобками, знаками ( и ( такое же, как между скобками, знаками * и + в алгебре. Дополнение берётся от всего выражения, над которым стоит черта.
Замечание 2.3. Нужно помнить, что все указанные операции можно производить только над множествами, принадлежащими одному и тому же универсальному множеству.
Задача 2.1. Заданы множества: U = {2; 3; 4; 8; 9; 10; 11}; A = {2; 3; 4}; B = {3; 4; 8; 9} и С = {2; 10; 11}. Найти следующие множества:
А ( В; А ( В ( С;

·; 13 EMBED Equation.DSMT4 1415
А ( В; В (
·;
А \ В; В \ А; А \ С \ В;
А ( В; А ( С; (А ( В) ( С.
Решение.
По определению объединение А ( В будет состоять из всех элементов обоих множеств, то есть А ( В ={2; 3; 4; 8; 9}. Как мы помним, кратность элементов не учитывается. Аналогично для нахождения А ( В ( С к элементам множества А ( В присоединим элементы множества С. Получим: А ( В ( С = {2; 3; 4; 8; 9; 10; 11}. Очевидно, что А ( В ( С = U.
Для нахождения дополнения множества А (множества
·) выберем те элементы, которые принадлежат универсуму и не принадлежат А. Таковыми будут элементы 8, 9, 10 и 11. То есть
· = {8; 9; 10; 11}. Аналогично найдем 13 EMBED Equation.DSMT4 1415= {2; 10; 11}; 13 EMBED Equation.DSMT4 1415= {3; 4; 8; 9}.
Пересечение множеств – это множество, состоящее из их общих элементов. Для множеств А и В таковыми будут только два элемента – 3 и 4. Следовательно, можем записать: А ( В = {3; 4}. Аналогично найдём В (
· = {3; 4; 8; 9} ( {8; 9; 10; 11} = {8; 9}.
Для нахождения разности А \ В отберём только те элементы, которые принадлежат исключительно множеству А и не принадлежат В. Таковым будет только один элемент – 2. Значит, А \ В = {2}. Аналогично найдём В \ А = {8; 9}. A \ C \ B = (A \ C) \ В = {3; 4} \ {3; 4; 8; 9} = (.
Для нахождения симметрической разности А ( В сначала объединим эти множества, а затем из полученного множества удалим общие элементы двух множеств. Таких элементов будет два: 3 и 4. Следовательно, А ( В = {2; 8; 9}. Аналогично, А ( С = {3; 4; 10; 11}.
(А ( В) ( С = {2; 8; 9} ( {2; 10; 11} = {8; 9; 10; 11}.
Задача 2.2. Заданы множества: U = {a; b; c; d; e; f; k, m, n}; P = {a; b; c, d}; Q = {b; c; e; f; k} и R = {k; m; n}. Выполнить следующие действия:
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
Решение.
Сначала выполним действие в скобках и найдём объединение множеств P c Q: P ( Q = {a, b, c, d, e, f, k}. Далее найдём дополнение множества R: 13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f}. Объединяем оба полученных множества: 13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f, k}. И, наконец, находим дополнение к последнему множеству. Окончательно 13 EMBED Equation.DSMT4 1415 = {m, n}.
Сначала находим разность P \ R = {a; b; c, d}. Очевидно, что P \ R = P. Далее найдём разность этого множества с Q: P \ R \ Q = P \ Q = {a, d}. Дополнение к этому множеству 13 EMBED Equation.DSMT4 1415={b, c, e, f, k, m, n}. Находим теперь пересечение этого множества с R. Окончательно: 13 EMBED Equation.DSMT4 1415 = {k, m, n}.
Находим дополнения 13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f}, 13 EMBED Equation.DSMT4 1415= {a, d, m, n}. Их симметрическая разность 13 EMBED Equation.DSMT4 1415 = {b, c, e, f, m, n}. Дополнение Р: 13 EMBED Equation.DSMT4 1415 = {e, f, k, m, n}. Теперь можем найти симметрическую разность 13 EMBED Equation.DSMT4 1415 = {e, f}. Окончательно получаем: 13 EMBED Equation.DSMT4 1415 = {b, c, m, n}.
Найдём P(Q={b,c}. Дополнение к нему 13 EMBED Equation.DSMT4 1415 = {a, d, f, k, m, n}. Пересечение Q(R={k}. Его дополнение 13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f, m, n}. Разность между найденными дополнениями 13 EMBED Equation.DSMT4 1415={k}. Дополнение этого множества было найдено на предыдущем шаге. Поэтому
13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f, m, n}.
Очевидно, что пересечение U с R будет не что иное, как R, то есть 13 EMBED Equation.DSMT4 1415. Отсюда получаем, что 13 EMBED Equation.DSMT4 1415 = {a, b, c, d, e, f}. Далее найдём 13 EMBED Equation.DSMT4 1415 = {e, f, k, m, n} и симметрическую разность 13 EMBED Equation.DSMT4 1415 = {b, c, m, n}. Окончательно получаем: 13 EMBED Equation.DSMT4 1415 = {b, c}.
Задача 2.3. Для двух произвольных множеств А и В построить диаграммы и найти следующие множества:
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415
Решение.
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
Задача 2.4. Даны три произвольные множества А, В и С. Построить диаграммы и описать следующие восемь множеств, на которые разделится универсальное множество.
13 SHAPE \* MERGEFORMAT 1415
Решение
область 1 – это пересечение трёх множеств А, В и С. Значит, эта область может быть описана выражением А ( В ( С;
область 2 получится, если из пересечения А с В убрать элементы множества С, то есть 13 EMBED Equation.DSMT4 1415;
область 3 аналогична области 2:
13 EMBED Equation.DSMT4 1415;
область 4: 13 EMBED Equation.DSMT4 1415;
область 5 проще всего получить пересечением множества А с множествами 13 EMBED Equation.DSMT4 1415, то есть 13 EMBED Equation.DSMT4 1415;
область 6: 13 EMBED Equation.DSMT4 1415;
область 7: 13 EMBED Equation.DSMT4 1415;
область 8 – это дополнение к объединению трёх множеств: 13 EMBED Equation.DSMT4 1415.
Задача 2.5. Для трёх произвольных множеств А, В и С построить диаграммы и найти следующие множества:
(A\B)(C;
A\(B(C);
13 EMBED Equation.DSMT4 1415.
Решение.
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
Задачи для самостоятельного решения.
1. Записать универсальное множество и выполнить над множествами А = {о, т, с, ф, х}, В = { т, с, у, х}, C = {x, y}, D = {о, к, е, ф} следующие операции:
(A(B)\(C(D);
(A\B)\(C\D);
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415.
2. Построить диаграммы для трёх произвольных множеств А, В, С:
(A(B)((A(C);
(A(B)((A(B);
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415.

3. ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ МНОЖЕСТВ
Рассмотренные операции над множествами подчинены некоторым законам, которые напоминают известные элементарные законы алгебры чисел. Этим определяется название алгебра множеств, которую часто называют булевой алгеброй множеств, что связано с именем английского математика Джона Буля, который положил в основу своих логических исследований идею аналогии между алгеброй и логикой.
Для произвольных множеств А, В, и С справедливы следующие тождества (табл. 3.1):

Таблица 3.1
1. Закон тождества
13 EMBED Equation.DSMT4 1415

2. Коммутативность объединения
[ Cкачайте файл, чтобы посмотреть картинку ]
2’. Коммутативность пересечения
[ Cкачайте файл, чтобы посмотреть картинку ]

3. Ассоциативность объединения
[ Cкачайте файл, чтобы посмотреть картинку ]
3’. Ассоциативность пересечения
[ Cкачайте файл, чтобы посмотреть картинку ]

4. Дистрибутивность объединения относительно пересечения
[ Cкачайте файл, чтобы посмотреть картинку ]
4’. Дистрибутивность пересечения относительно объединения
[ Cкачайте файл, чтобы посмотреть картинку ]

5. Законы действия с пустым 13 EMBED Equation.DSMT4 1415 и универсальным U множествами
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ](закон исключённого третьего)
[ Cкачайте файл, чтобы посмотреть картинку ]
5’. Законы действия с пустым 13 EMBED Equation.DSMT4 1415 и универсальным U множествами
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ] (закон противоречия)
[ Cкачайте файл, чтобы посмотреть картинку ]

6. Закон идемпотентности объединения
[ Cкачайте файл, чтобы посмотреть картинку ]
6’. Закон идемпотентности пересечения
 [ Cкачайте файл, чтобы посмотреть картинку ]

7. Закон де Моргана
[ Cкачайте файл, чтобы посмотреть картинку ]
7’. Закон де  Моргана
[ Cкачайте файл, чтобы посмотреть картинку ]

8. Закон элиминации (поглощения)
[ Cкачайте файл, чтобы посмотреть картинку ]
8’. Закон элиминации (поглощения)
[ Cкачайте файл, чтобы посмотреть картинку ]

9. Закон склеивания
[ Cкачайте файл, чтобы посмотреть картинку ]
9’. Закон склеивания
[ Cкачайте файл, чтобы посмотреть картинку ]

10. Закон Порецкого
[ Cкачайте файл, чтобы посмотреть картинку ]
10’. Закон Порецкого
[ Cкачайте файл, чтобы посмотреть картинку ]

11. Закон инволюции (двойного дополнения)
[ Cкачайте файл, чтобы посмотреть картинку ]


Законы алгебры множеств по отношению к операциям пересечения (() и объединения (() подчинены принципу двойственности: если в каком-либо законе все знаки пересечения заменить знаками объединения, а все знаки объединения – знаками пересечения, знак универсума (U) заменить знаком пустого множества (Ш), а знак пустого – знаком универсума, то получим снова верное тождество. Например (в силу этого принципа), из [ Cкачайте файл, чтобы посмотреть картинку ] следует [ Cкачайте файл, чтобы посмотреть картинку ] и т. п.

3.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна
 Все законы алгебры множеств можно наглядно представить и доказать, используя диаграммы Эйлера-Венна. Для этого необходимо:
Начертить соответствующую диаграмму и заштриховать все множества, стоящие в левой части равенства.
Начертить другую диаграмму и сделать то же для правой части равенства.
Данное тождество истинно тогда и только тогда, когда на обеих диаграммах заштрихована одна и та же область.
Замечание 3.1. Два пересекающихся круга делят всё универсальное множество на четыре области (см. рис.3.1)

А ( В;
А ( 13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415 ( В;
13 EMBED Equation.DSMT4 1415 ( 13 EMBED Equation.DSMT4 1415.

Рис.3.1

Замечание 3.2. Три пересекающихся круга делят всё универсальное множество на восемь областей (см. рис.3.2):



А ( В ( С;
А ( В ( 13 EMBED Equation.DSMT4 1415;
А ( 13 EMBED Equation.DSMT4 1415 ( С;
А ( 13 EMBED Equation.DSMT4 1415 ( 13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415 ( В ( С;
13 EMBED Equation.DSMT4 1415 ( В ( 13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415 ( 13 EMBED Equation.DSMT4 1415 ( С;
13 EMBED Equation.DSMT4 1415 ( 13 EMBED Equation.DSMT4 1415 ( 13 EMBED Equation.DSMT4 1415.
Замечание 3.2. При записи условий различных примеров часто используются обозначения:
( - из следует;
( - тогда и только тогда, когда .
Задача 3.1. Упростить выражения алгебры множеств:
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415.
Решение.
13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415
Задача 3.2. Доказать тождества:
(А(В)\В = А\В;
А((В(С) = А\(А\В)((А\С).
Решение.
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415

Задача 3.3. Доказать следующие соотношения двумя способами: с помощью диаграмм и с помощью определения равенства множеств.
13 EMBED Equation.DSMT4 1415
A((B(C) = (A(B)((A(C);
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
Решение.
13 EMBED Equation.DSMT4 1415
1. Доказательство с помощью диаграммы:
13 SHAPE \* MERGEFORMAT 1415
2. Доказательство с помощью определения равенства множеств.
По определению, множества Х и Y равны, если одновременно выполнены соотношения: X(Y и Y(X.
Сначала покажем, что 13 EMBED Equation.DSMT4 1415. Пусть х – произвольный элемент множества 13 EMBED Equation.DSMT4 1415, то есть х(13 EMBED Equation.DSMT4 1415. Это означает, что х(U и х(13 EMBED Equation.DSMT4 1415. Отсюда вытекает, что х(А или х(В. Если х(А, то тогда х(
·, а значит, 13 EMBED Equation.DSMT4 1415. Если же х(В, то 13 EMBED Equation.DSMT4 1415, а значит, 13 EMBED Equation.DSMT4 1415. Таким образом, всякий элемент множества .13 EMBED Equation.DSMT4 1415. есть также элементом множества 13 EMBED Equation.DSMT4 1415 То есть 13 EMBED Equation.DSMT4 1415
Теперь докажем обратное, то есть, что 13 EMBED Equation.DSMT4 1415. Пусть 13 EMBED Equation.DSMT4 1415. Если х(
·, то х(U и х(А, а значит, х(А(В. Отсюда следует, что 13 EMBED Equation.DSMT4 1415. Если же 13 EMBED Equation.DSMT4 1415, то х(U и х(В. Значит, х(А(В, то есть 13 EMBED Equation.DSMT4 1415. Отсюда следует, что всякий элемент множества 13 EMBED Equation.DSMT4 1415 является также элементом множества 13 EMBED Equation.DSMT4 1415, то есть 13 EMBED Equation.DSMT4 1415.
Значит, 13 EMBED Equation.DSMT4 1415, что и требовалось доказать.
A((B(C) = (A(B)((A(C);
1. Доказательство с помощью диаграммы:
13 SHAPE \* MERGEFORMAT 1415
2. Доказательство с помощью определения равенства множеств.
Пусть х(А((В(С). Тогда х(А и х(В(С. Если х(В, то х(А(В, что не противоречит сказанному, а значит, х((А(В)((А(С). Если же х(С, то х(А(С. Следовательно, х((A(B)((A(C). Итак, доказано, что A((B(C) ( (A(B)((A(C.
Пусть теперь х( (A(B)((A(C). Если х(А(В, то х(А и х(В. Отсюда следует, что х(А и х(В(С, то есть х(А((В(С). Если же х(А(С, то х(А и х(С. Отсюда вытекает, что х(А и х(В(С, то есть х(А((В(С). Таким образом, (A(B)((A(C)( A((B(C). Следовательно, A((B(C) = (A(B)((A(C). Что и требовалось доказать.
13 EMBED Equation.DSMT4 1415 Пересечение множеств А и В есть подмножеством множества С тогда и только тогда, когда множество А является подмножеством объединения множеств не-В и С.
13 SHAPE \* MERGEFORMAT 1415
При доказательстве достаточности мы получили, что А(В=(. Очевидно, что ((С, поэтому соотношение доказано. При доказательстве был рассмотрен самый общий случай. Однако здесь возможны ещё некоторые варианты при построении диаграмм. Например, случай равенства А(В=С либо 13 EMBED Equation.DSMT4 1415, случай пустых множества и так далее. Очевидно, что все возможные варианты учесть бывает затруднительно. Поэтому считается, что доказательство соотношений с помощью диаграмм не всегда является корректным.
2. Доказательство с помощью определения равенства множеств.
Необходимость. Пусть А(В(С и элемент х(А. Покажем, что в этом случае элемент множества А будет являться также и элементом множества 13 EMBED Equation.DSMT4 1415.
Рассмотрим два случая: х(В или 13 EMBED Equation.DSMT4 1415.
Если х(В, то х(А(В(С, то есть х(С, и, как следствие этого, 13 EMBED Equation.DSMT4 1415.
Если же 13 EMBED Equation.DSMT4 1415, то и 13 EMBED Equation.DSMT4 1415. Необходимость доказана.
Пусть теперь 13 EMBED Equation.DSMT4 1415 и х(А(В. Покажем, что элемент х также будет элементом множества С.
Если х(А(В, тогда х(А и х(В. Поскольку 13 EMBED Equation.DSMT4 1415, значит х(С. Достаточность доказана.
13 EMBED Equation.DSMT4 1415 Если множество А является подмножеством множества В, то тогда множество 13 EMBED Equation.DSMT4 1415будет подмножеством множества
·.
1. Доказательство с помощью диаграммы:
13 SHAPE \* MERGEFORMAT 1415
2. Доказательство с помощью определения равенства множеств.
Пусть А(В. Рассмотрим элемент х(В (или 13 EMBED Equation.DSMT4 1415). Аналогично: х(А (или х(
·). То есть всякий элемент множества 13 EMBED Equation.DSMT4 1415 есть также элементом множества
·. А это может быть в случае, если 13 EMBED Equation.DSMT4 1415. Что и требовалось доказать.

Задача 3.4. Выразить символически указанные области и упростить полученные выражения.
13 SHAPE \* MERGEFORMAT 1415
Решение.
Искомая область состоит из двух изолированных частей. Условно назовём их верхней и нижней. Множество, которое они изображают, можно описать так:
М = {x(x(A и х(В и х(С или х(С и х(А и х(В}.
Из определения операций над множествами получим:
М = ((А(В)\С)((С\А\В).
Запишем это выражение с помощью основных операций – дополнения, объединения и пересечения:
13 EMBED Equation.DSMT4 1415.
Упростить это выражения нельзя, поскольку имеем по одному вхождению каждого символа. Это и есть простейший вид данной формулы.
Данную область можно рассматривать как объединение множеств А\В\С и А(В(С. По определению M = {x( x(A и x(В и х(С или х(А и х(В и х(С}. Упростим:
13 EMBED Equation.DSMT4 1415
Задачи для самостоятельного решения.
1. Упростить:
13 EMBED Equation.DSMT4 1415
(А(В)((А(В); (ответ А(В);
13 EMBED Equation.DSMT4 1415(ответ V).
2. Доказать с помощью диаграмм, законов алгебры множеств и определения равенства множеств:
(А(В)\В = А\В;
А((В(С) = А\(А\В)((А\С);
А(В = А(В ( А=В;
А\В = ( ( А(В = А.
3. Выяснить, существует ли множество Х, удовлетворяющее при любом А равенству:
А(Х = А; (ответ ();
А(Х = А; (ответ U).

4. БУЛЕВЫ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
4.1. МОЩНОСТЬ КОНЕЧНОГО МНОЖЕСТВА
Пусть задано некоторое множество А. Количество элементов данного множества называется его мощностью и обозначается символом (А(.
Очевидно, что пустое множество имеет мощность, равную нулю, то есть (((= 0.
Как могут меняться мощности множеств при операциях, производимых над ними? Точного ответа на этот вопрос нет, так как всё будет зависеть от взаимного расположения множеств.
Рассмотрим три возможных случая расположения двух непустых множеств А и В.
13 SHAPE \* MERGEFORMAT 1415
Рассмотрим множество, равное объединению А ( В. Какова же будет его мощность в каждом из возможных трёх случаях.
Случай 1. Множества не пересекаются, то есть (А(В(= 0. Тогда (А(В(( (А( + (В(. Иными словами, мощность объединения (суммы) множеств не превышает суммы их мощностей.
Случай 2. Множества пересекаются. Тогда (А(В(= (А( + (В(( (А(В(, то есть мощность объединения двух пересекающихся множеств равна сумме их мощностей без мощности их общей части (их пересечения).
Эта формула носит название формулы включений и исключений. С её помощью можно вычислить мощность любого множества.
Случай 3. Множество В включено в множество А, то есть имеет место включение В ( А. Очевидно, что здесь (А(В( = (А(, то есть мощность объединения подмножества и множества будет равно мощности самого множества. В случае, если А ( В, то (А(В( = (В(.
Обобщая эти три случая, получаем для объединения: (А(В( ((А( + (В.(
Рассмотрим множество, равное пересечению А ( В. Какова же будет его мощность в каждом из возможных трёх случаях.
Случай 1. (А(В( = ((( = 0.
Случай 2. (А(В( = (А(В(( (А(( (В(.
Случай 3. (А(В( = (В(.
Обобщая эти три случая, получаем для пересечения: 0 ( (А(В( ( (В(.
Рассмотрим множество, равное дополнению множества А. Поскольку
· = V\А , то (
·( = (V( ( (А(.
Рассмотрим множество, равное разности А \ В.
Случай 1. Здесь А\В = А, тогда и (А\В( = (А(.
Случай 2. (А\В( = ((((( ( (((.
Случай 3. (А\В( = ((( ( (В(.
Рассмотрим множество, равное симметрической разности А ( В.
Случай 1. Здесь А(В = А((, тогда и (А(В( = (А(((= |A| + |B|.
Случай 2. (А(В( = (А\(( + (В\(( = ((((+ ((( (2(((((=
= 2((((( ( (((( + ((().
Случай 3. Здесь А(В = А\В, поэтому ((А(В( = ((( ( (В(.

Задача 4.1.1. А = {1, 2, 3, 4, 5}; B = {4, 5, 6, 7}. Найти мощности указанных множеств.
Решение.
((((((5, ((( = 4, ((( = {4, 5}, ((((( = 2, тогда
(((((= (А( + (В(( (А(В| = 5 + 4 – 2 = 7.
A\B = {1, 2, 3}, |A\B| = |A| ( |A(B| = 5 – 2 = 3. B\A = {6, 7},
|B\A| = |B| ( |A(B| = 4 – 2 = 2.
A(B = {1, 2, 3, 6, 7}, |A(B| = (А\В( ( (В\А( = 3 + 2 = 5.

Задача 4.1.2. В одном канадском городе жители говорят на английском и французском языках. На английском говорят 90% жителей, на французском  80%. Сколько процентов жителей города говорят на обоих языках и на одном языке?
Решение. Пусть множество А – множество говорящих по-английски, В – говорящих по-французски. Тогда А\В – это множество жителей, которые говорят только по-английски, В\А – по-французски, а А(В – на обоих языках. А(В – это множество всех жителей города.
Из условия задачи получаем:
((( = 90, (В( = 80, (А(В(= 100.
Так как ((((( = (А( + (В( ( (((((. Отсюда ((((( = (А( + (В(( (((((, и ((((( = 90 + 80 ( 100 = 70. На обоих языках говорят 70% жителей.
13 SHAPE \* MERGEFORMAT 1415
На одном английском говорят ((\В(= (((( (((((= 90 ( 70 = 20 процентов, только на французском ((\А(= (((( ((((( = 80 ( 70 = 10 процентов жителей.

Задача 4.1.3. В отряде из сорока ребят 30 умеют плавать, 27 умеют играть в шахматы и только пятеро не умеют ни того, ни другого. Сколько ребят умеют плавать и играть в шахматы?
Решение. Пусть А – множество умеющих плавать, В – множество играющих в шахматы. Универсальное множество V – это весь отряд. Те же, кто не умеет ни того, ни другого – это множество, равное дополнению к А(В или V\( А(В). Имеем: (А(=30, (В(=27, (V(=40, (V\(A(B(=5.
13 SHAPE \* MERGEFORMAT 1415
(
·(= (V(-(A(=40-30=10 – это те, кто не плавает (играет в шахматы или ничего не умеет); 13 EMBED Equation.DSMT4 1415– это те, кто не играет в шахматы (плавает или ничего не умеет). Те, кто только играет в шахматы – множество В\А мощностью 10-5=5, множество А\В – это умеющие плавать. Их количество равно 13-5=8.Так как (V\(A(B(=(V(-(A(B(=5, отсюда (A(B(=(V(-5=40-5=35. По формуле включений и исключений (А(В(= (А( + (В(( (А(В( получим, что 35=5+8((А(В(, откуда (А(В(=22.
Задача 4.1.4. Из 100 деталей на первом станке обработано 42 штуки, на втором – 30, на третьем – 28 шт. При этом на первом и втором станках обработано всего 5 деталей, на первом и третьем – 10, на втором и третьем – 8. На всех трёх станках обработано 3 детали.
Сколько деталей обработано на первом станке и сколько деталей не обработано ни на одном станке?
Решение. Пусть А – множество деталей, обработанных на 1-м станке; В – на 2-м; С – на 3-м. Универсум V – множество всех деталей в задаче. Очевидно, что |V| = 100, |A| = 42, |B| = 30, |C| = 28.
13 SHAPE \* MERGEFORMAT 1415
Метка 1 соответствует множеству А(В(С – это детали, обработанные хотя бы на одном станке (либо на одном, либо на двух, либо на трёх). Мощность его (А(В(С( = 3.
Метки 1 и 2– детали, обработанные на 1 и 2-м станках. Это множество А(В. Его мощность по условию (А(В(= 5.
Метки 1 и 3 – детали, обработанные на 2-м и 3-м станках, множество А(С, (А(С(= 10, а метки 1 и 4 – на 2-м и 3-м станках, множество В(С, (В(С(= 8.
Метка 2 соответствует множеству деталей, которые обработаны только на 1-м и 2-м станках. Это множество (А(В)\С, мощность которого находим так: (А(В(((А(В(С(= 5-3=2.
Метка 3 – детали, обработанные на 1-м и 3-м станках. Это множество (А(С)\В, мощность которого равна (А(С(( (А(В(С (= 10-3=7.
Метка 4 - множество деталей, обработанных на 2-м 3-м станках. Это множество (В(С)\А. Его мощность (В(С(( (А(В(С(= 8-3=5.
Детали, которые обрабатывались только на одном первом станке  множество с меткой 5, равное разности множества А и множеств с метками 1, 2 и 3. Мощность этого множества (метка 5) равна (А((( (м.1(+(м.2(+(м.3() = 42((3+2+7) = 30.
Множество с меткой 6 – детали, обработанные только на втором станке. Его мощность равна (В((( (м.1(+(м.2(+(м.4() = 30((3+2+5) = 20.
Множество с меткой 7 – детали, обработанные только на третьем станке. Его мощность равна (С((( (м.1(+(м.3(+(м.4() = 28((3+7+5) = 13.
А(В(С – множество всех обработанных деталей. Его мощность можно найти как сумму мощностей всех семи множеств: (А(В(С( = 3+2+7+5++30+20+13 = 80.
13 EMBED Equation.DSMT4 1415 – множество всех необработанных деталей. Его мощность вычислим так:
13 EMBED Equation.DSMT4 1415.
Итак, на 1-м станке обработано 30 деталей, вообще не обрабатывалось 20 деталей.
Задачи для самостоятельного решения.
1. В классе 40 учеников. 30 из них могут плавать, 27 – играть в шахматы, а пятеро не умеют ни того, ни другого. Сколько учеников могут плавать и играть в шахматы? (ответ:22).
2. На протяжении недели в кинотеатре демонстрировались фильмы А, В и С. Из 40 учеников каждый посмотрел либо все три фильма, либо только один из трёх. Фильм А посмотрели 13 человек, фильм В – 16, фильм С – 19. Сколько учеников посмотрели все три фильма? (ответ: 3).

4.2. БУЛЕАН МНОЖЕСТВА. РАЗБИЕНИЕ МНОЖЕСТВА
Пусть задано непустое множество X. Множество всех подмножеств этого основного множества, включая его само и пустое множество, называется булеаном данного множества и обозначается Р(X) или 2х. Если X содержит n элементов, то булеан содержит 2п элементов, которыми есть подмножества множества А, собственные и несобственные.
Говорят, что элементы Х1, Х2,Хп булеана 2х образуют разбиение множества X, если
13 EMBED Equation.DSMT4 1415(4.2.1)
В этом случае множества Х1, Х2,Хп называются блоками разбиения множества X.
Правило суммы (лежащее в основе многих комбинаторных вычислений и оценок). Пусть X – конечное множество, 13 EMBED Equation.DSMT4 141513 EMBED Equation.DSMT4 1415, (X(- его мощность (число его элементов). Тогда имеет место условие:
(X(( (Х1( +(Х2(++(Хп(, (4.2.2)
причём равенство достигается, когда Х1, Х2,Хп образуют разбиение множества X, т.е. удовлетворяют (4.2.1).

Задача 4.2.1. Найти булеаны множеств А={1, 2}; B={a, b, c}; C={1, 2, 3, 4}.
Решение. Р(А) = {{1}, {2}, {1, 2}, {(}};
P(B) = {{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {(}};
P(С) = {{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}, {(}}.

Задача 4.2.2. Найти разбиение множеств А={1, 2}; B={a, b, c}; C={1, 2, 3, 4}.
Решение.
Множество А: Х1 = {1}, X2 = {2}; A = X1(X2. Это единственный способ разбиения множества А.
Множество В: первый способ: Х1 = {a}, X2 = {b}; X3 = {c};
второй способ: Х1 = {a, b}, X2 = {c};
третий способ: Х1 = {a}, X2 = {b, c}.
Множество С: первый способ: Х1 = {1}, X2 = {2}; X3 = {3}; Х4 = {4};
второй способ: Х1 = {1}, X2 = {2, 3}; X3 = {4};
третий способ: Х1 = {1, 2}, X2 = {2}; X3 = {3, 4};
четвёртый способ: Х1 = {1, 2}, X2 = {3, 4};
пятый способ: Х1 = {1, 2, 3}, X2 = {4}; и т.д.

Задачи для самостоятельного решения.
1. Найти булеаны следующих множества: А ={1}, B ={3, 5}, C ={7, 8, 10}, D ={m, n, p, q}. Найти разбиение множеств A, B, C, D.

4.3. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. ПОНЯТИЕ УПОРЯДОЧЕННОГО МНОЖЕСТВА
Пусть X и Y – некоторые непустые множества, где x(X, y(Y. Рассмотрим двухэлементное множество, состоящее из пар x и y. Пара (или двойка) {x, y} называется неупорядоченной. Здесь порядок записи элементов не важен, поэтому {x, y} = {y, x}. Пара (x, y) называется упорядоченной. Здесь порядок записи существенен, поэтому (x, y) ( (y, x).
Множество, для которого имеет значение порядок записи его элементов, называется упорядоченным. В противном случае – неупорядоченным.
Декартовым (или прямым) произведением множеств X и Y называется множество всех упорядоченных пар, где первый элемент принадлежит множеству X, а второй – Y.
X(Y = {(x, y) (x(X, y(Y}
Аналогично определяется декартово произведение любого конечного числа n множеств:
X1 (X2 (( Xn = {(x1, x2, , xn) ( x1(X1, x2(X2,, xn(Xn}
Упорядоченные элементы этого произведения (x1, x2, , xn) называются векторами, последовательностями, кортежами или просто «энками».
Если декартово произведение выполняется на одном и том же множестве, то его называют декартовой степенью этого множества.
X1 (X2 ( (Xn = Xп
Правило произведения (лежащее в основе многих комбинаторных вычислений и оценок). Для конечных множеств Х1, Х2,Хп :
| X1 (X2 ( (Xn | = | X1| ( | X2| ( (| Xn|
Декартово произведение обладает следующими свойствами:
некоммутативность: А(В ( В(А, если А ( В;
неассоциативность: (А(В)(С ( А((В(С);
дистрибутивность относительно операций :
(А(В)(С = (А(С)((В(С),
(А(В)(С = (А(С)((В(С),
(А \ В)(С = (А(С) \ (В(С),
(А(В)(С = (А(С)((В(С),
(А( В)(С = (А(С) ((В(С).
Для случая двух множеств декартово произведение можно иллюстрировать с помощью диаграммы Венна. Пусть А = {a1, a2,, an};
B = {b1, b2,, bm}.








Рассмотрим прямое произведение множества R действительных чисел самое на себя. Множество R(R или R2 состоит из всех упорядоченных пар вещественных чисел (х, у). Их можно трактовать как координаты точек плоскости XOY, то есть декартовой плоскости. Часто в дискретной математике множество вещественных чисел обозначают D (вместо R). Смысл этого обозначения станет понятным из дальнейшего изложения.

Задача 4.3.1. Найти декартово произведение А(В и В(А на множествах А={1, 2} и B={a, b, c}.
Решение.
А(В = {1, 2}( {a, b, c} = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)};
B(A = {a, b, c} ( {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

Задача 4.3.2. Найти декартовы степени А2, А3, В2, А={1, 2} и B={a, b, c}.
Решение.
А2 = А(А = {1, 2}({1, 2} = {(1,1), (1,2), (2,1), (2,2)};
A3 = A(A(A = A2 (A = {1, 2}({1, 2}({1, 2} = {(1,1), (1,2), (2,1), (2,2)}({1, 2}= = {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)};
B2 = B(B = {a, b, c}({a, b, c} =
= {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)}.

Задача 4.3.3. Найти геометрическую интерпретацию множеств:
[1, 4] ( [2,3];
[1, 2]2;
[1, 2]3.
Решение.
Пусть А ={x(1( x (4}, B = {у(2( у (3}. Отложим на оси ОХ множество А, а множество В – на оси OY. Совершенно ясно, что множества А и В содержат бесконечное множество элементов. Их произведение А(В={(x,y)(x(A, y(B} есть множество точек прямоугольника с вершинами в точках (1,2), (1,3), (4,2) и (4,3).
13 SHAPE \* MERGEFORMAT 1415
Множество [1,2]2 = [1,2] ( [1,2] – это множество точек квадрата с вершинами в точках (1,1), (1,2), (2,1), (2,2).
Множество [1, 2]3 – это множество точек куба с вершинами в точках (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2).

Задача 4.3.4. Проверить справедливость равенства
С((В\А)=(С(В)((С((А(В))
для множеств А={a, d}, B={b, d}, C={c} .
Решение. Найдём множество в левой части равенства:
В\А = {b, d}\{a, d} = {b}; C((B\A) = {c}({b} = {(c, b)};
Аналогично находим множество в правой части равенства:
С(В = {c}({b, d} = {(c, b), (c, d)}; A(B = {a, d} ( {b, d} = {d};
C((A(B ) = {c}({d} = {(c, d)}; (С(В)((С((А(В)) =
= {(c, b), (c, d)}( {(c, d)} = {(c, b)};
В левой и правой части равенства имеем одно и то же множество. Следовательно, для данных множеств равенство справедливо.

Задача 4.3.5. Доказать, что (А(В)(С = (А(С)((В(С).
Решение. Воспользуемся определением равенства множеств. Ясно, что мы имеем дело с множествами, состоящими из упорядоченных пар. Пусть элемент (х, у)((А(В)(С, откуда имеем, что х((А(В), у(С. Значит х(А или х(В, а тогда (х, у)(А(С или (х, у)(В(С. Мы показали, что всякий элемент, принадлежащий множеству слева, принадлежит также и множеству справа, то есть (А(В)(С ((А(С)((В(С).
Пусть теперь (х, у) ( (А(С)((В(С). Отсюда вытекает, что (х, у)((А(С) или что (х, у)((В(С). В первом случае х(А, у(С, во втором – х(В, у(С. Следовательно, х(А(В, а (х, у)((А(В)(С. Итак, (А(С)((В(С) ((А(В)(С. Что и доказывает наше равенство.

Задачи для самостоятельного решения.
1. Найти декартово произведение А(В и В(А на множествах
А={2, 4} и B={3, 5, 7};
A={k, m} и B={m, n, l}.
2. Найти декартовы степени А2, А3, если А={a, b, c}.
3. Проверить справедливость равенства С((A(B)=(С(A)((С((B\A)) для множеств А={1, 2}, B={2, 3}, C={1, 3} .
4. Доказать, что
если В(А и С(А, то (В(С)((А(А); b) A((B(C) = (A(B)((A(C).

4.4. СООТВЕТСТВИЯ МЕЖДУ МНОЖЕСТВАМИ. ОБРАЗ И ПРОООБРАЗ. БИНАРНЫЕ СООТВЕТСТВИЯ
Рассмотрим два непустых множества А и В. Элементы этих множеств могут каким-либо образом сопоставляться друг другу, образуя пары (а, b). Если задан способ такого сопоставления, то говорят, что между множествами установлено соответствие. При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множеств А и В.
Соответствием между множествами А и В называется любое подмножество G ( А(В – декартово произведения этих множеств.
Множество А иногда называют областью отправления соответствия G, а множество В – областью прибытия.
График этого соответствия – множество упорядоченных пар (а, b) соответствия G.
Обозначается соответствие так:
G: A(B или G ( А(В = {(a, b)(a(A, b(B, (a, b)(G}.

Первой проекцией или областью определения соответствия G называется множество всех первых компонентов пар (а, b)(G. Обозначается
пр1 G или Dom(G) = {a (a(A, (а, b)(G}.

Второй проекцией или областью значений соответствия G называется множество всех вторых компонентов пар (а, b)(G. Обозначается
пр2 G или Im(G) = {b(b(B, (а, b)(G}.
Каждый элемент b(B, соответствующий элементу a(A, называется образом этого элемента a . Множество всех образов элемента a(A будем обозначать
·(a, G) = {b(b(B, (а, b)(G}.
Каждый элемент a(A, соответствующий элементу b(B, называется прообразом элемента b. Множество всех прообразов элемента b(B будем обозначать
·
·1(b, G) = {a(a(A, (а, b)(G}.
Очевидно, что множество всех образов всех элементов a(A есть ни что иное, как множество значений соответствия G (его вторая проекция), а множество всех прообразов всех элементов b(B ( множество определения соответствия G (его первая проекция).
Пусть Х(А, а Y(B. Образом множества Х при данном соответствии G называется такое множество
Г(X,G) = {b (b=
·(x,G), x ( X, b ( B}.
Прообразом множества Y называется множество Г
·1(Y,G) = {x (x ( A, y ( Y, (x, y) ( G}.
Рассмотренное выше соответствие относится к двум множествам и поэтому носит название бинарного соответствия. Однако этот понятие распространяется на любое конечное число множеств. Рассмотрим, например, декартово произведение n непустых множеств: А1 (А2 ((Ап. Рассмотрим какое-либо подмножество G этого произведения, то есть отберём элементы произведения, удовлетворяющие некоторому условию
G ( А1 (А2 ((Ап =
= {(a1, a2, an) ( a1(A1, a2(A2,, an(An, (a1, a2, an)(G}.
Это подмножество называют п-местным соответствием на множестве А1 (А2 ((Ап. Подобные многоместные соответствия используются в теории баз данных. Предметом же нашего рассмотрения будут бинарные соответствия.
Задача 4.4.1. Рассмотрим экзаменационную ведомость студенческой группы и установим соответствия между студентами и полученными ими оценками.
Табл.4.1
Ф.И.О.
студента
Математика
Физика
История
Физкультура

Борисенко А.В.
5
4
не явился
2

Волошин В.П.
2
не доп.
3
5

Марабу Б.
3
не явился
3
5

Яковенко К.Д.
4
4
4
4

Решение. Обозначим множество студентов через А = {Б, В, М, Я}, множество оценок через B = {2, 3, 4, 5}. Тогда соответствие G ( A(B = {(Б,5), (Б,4), (Б,2), (В,2), (В,3), (В,5), (М,3), (М,5), (Я,4), (Я,5)}. Некоторые упорядоченные пары встречаются несколько раз, но мы их записываем только один раз.
Первая проекция (или область определения) соответствия:
пр1G = Dom(G) = {Б,В,М,Я}, вторая проекция (область значений):
пр2 = Im(G) = {2,3,4,5}.
Образ Б:
·(Б,G) = {2,4,5}; образ В:
·(B,G) = {2,3,5};
образ M:
·(M,G) = {3,5}; образ Я:
·(Я,G) = {4}.
Прообраз 2:
·
·1(2,G) = {Б,В}; прообраз 3:
·
·1(3,G) = {В,М}; прообраз 4:
·
·1(4,G) = {Б,Я}; прообраз 5:
·
·1(5,G) = {Б,В,М}.
Задача 4.4.2. Дано соответствие G = {(a,2), (b,1), (b,5), (d,4)} для множеств А= {a, b, c, d} и B = {1, 2, 3, 4, 5}. Найти образ множества X = {a, b} и прообраз множества Y = {3, 4}.
Решение. Найдём образы элементов множества Х:
·(а,G)=2;
·(b,G)={1,5}. Объединяя эти элементы в одно множество, получим образ множества Х: Г(Х,G) = {1,2,5}.
Найдём прообразы элементов множества Y:
·
·1(3,G) = (;
·
·1(4,G) = d . Поэтому прообразом множества Y будет множество, состоящее из одного элемента: Г
·1(Y,G) = {d}. Пустое множество ( является частью любого множества, поэтому записи {(, d} и { d } выражают одну и ту же мысль.
Задача 4.4.3. Найти образ отрезка [1, 10] при соответствии y = lg x.
Решение. Функция y = lg x является непрерывной и монотонной на множестве (0,
·) – множество А, область её изменения (-
·,
·) – множество В. G = {(x, y)| x(A, y(B, y = lg x}. Значению х=1 соответствует у = lg1 = 0, значению х=10 соответствует у = lg10 = 1. Следовательно, образом отрезка [1, 10] будет отрезок [0, 1].

Задачи для самостоятельного решения.
1. Дано соответствие G = {(a,4), (b,3), (b,2), (с,3), (d,4)} для множеств А= {a, b, c, d} и B = {1, 2, 3, 4}. Найти образы и прообразы элементов множеств А и В, а также и прообраз множеств X = {b, d} и Y = {2, 4}.
2. Найти прообраз отрезка [-1, 1] при соответствии y = sin x. (ответ – вся числовая ось).

4.5. СПОСОБЫ ЗАДАНИЯ БИНАРНЫХ СООТВЕТСТВИЙ
Соответствие может быть задано перечислением всех упорядоченных пар, находящихся в соответствии G и соответствующих множеств (см. предыдущий пункт). Очевидно, что такой способ задания приемлем только для относительно небольших по мощности множеств.
Матричный способ. Соответствие G задаётся прямоугольной (квадратной) матрицей С = [ ( ij ], где
13 EMBED Equation.DSMT4 1415.
Табличный способ. Для задания этим способом соответствия G проводят вертикали, каждой присваивают значение элемента первого множества А, затем горизонтали, которые получают имена элементов второго множества В. Затем жирными точками обозначают пересечение этих прямых, удовлетворяющих соответствию G. Иногда такая таблица называется графиком соответствия.
Графический способ. Элементы обоих множеств изображаются точками, кружочками или другими геометрическими фигурами. Стрелками же соединяются те элементы множеств, которые принадлежат данному соответствию. Стрелки направлены из области отправления (множество А) к области прибытия (множество В). Такой способ иногда называют стрелочным представлением соответствия.
С помощью сечений. Пусть (a,b) ( G. Тогда сечением множества G по элементу а (или левым сечением) называется множество, равное множеству образов этого элемента
·(a,G) = {b(b(B, (а, b)(G}. Сечением G по элементу b (или правым сечением) называется множество, равное множеству прообразов этого элемента
·
·1(b, G) = {a(a(A, (а, b)(G}. Если под каждым элементом множества А записать соответствующее сечение, то получим новый способ задания соответствия G – с помощью сечений. Множество сечений соответствия G называется фактор-множеством по данному соответствия и обозначается F/G.

Задача 4.5.1. Задать бинарное соответствие на множествах всеми возможными способами.
А = {июнь, май, февраль, август, октябрь, январь, апрель, декабрь}; B = {зима, весна, лето, осень}; G = {(a, b) (a(A, b(B; a ( месяц времени года b}.
Решение. Для удобства элементы множества А обозначим числами: A = {6, 5, 2, 8, 10, 1, 4, 12}, a элементы множества В буквами: B = {z, w, l, o}. Это позволит нам в дальнейшем отвлечься от конкретного смысла элементов множеств и получить соответствие в формализованном виде.
Задание перечислением: G = {(6,l), (5,w), (2,z), (8,l), (10,o), (1,z), (4,w), (12,z)}. Это позволит нам в дальнейшем отвлечься от конкретного смысла элементов множеств и получить соответствие в формализованном виде.
Задание матричным способом:
13 EMBED Equation.DSMT4 1415
Соответствие G состоит из восьми упорядоченных пар. Поэтому матрица С имеет 8 единиц, соответствующих этим парам. Остальные элементы матрицы нули, поскольку соответствующих пар в G нет.
Задание табличным способом:
13 SHAPE \* MERGEFORMAT 1415
Полученная таблица напоминает привычный график, например, функции y = f(x), построение которого изучалось в курсе высшей математики. Здесь на оси абсцисс откладываются элементы первого множества (первая проекция соответствия), а на оси ординат – второго множества (вторая проекция).
Задание графическим способом.
13 SHAPE \* MERGEFORMAT 1415
Задание с помощью сечений. Сечения лучше всего определять по графику соответствия. Запишем матрицу, где первая строка– это элементы множества А, а вторая строка - соответствующие сечения по каждому элементу множества А:
13 EMBED Equation.DSMT4 1415
Фактор-множество по соответствию G записано во второй строке: F/G = {{z},{w},{l},{o}}.

Задача 4.5.2. Бинарное соответствие на множествах А = {a, b, c}; B = {1,2,3,4,5,6,7} задано перечислением: G = {(a,2), (b,3), (a,4), (a,6), (b,6)}. Рассмотреть иные способы задания этого соответствия.

Задание матричным способом:
13 EMBED Equation.DSMT4 1415


13 EMBED Equation.DSMT4 1415Задание табличным способом: Задание графическим способом:
13 SHAPE \* MERGEFORMAT 1415
Задание с помощью сечений. 13 EMBED Equation.DSMT4 1415.
Фактор-множество F/G = {{2,4,6},{3,6},{(}}.

Задачи для самостоятельного решения.
1. Задать бинарное соответствие на множествах всеми возможными способами. А = {Т.Шевченко, А.Пушкин, Л.Украинка, Л.Толстой, У.Шекспир};
B = {«Анна Каренина», «Евгений Онегин», «Му-Му», «Сон», «Война и мир», «Гайдамаки», «Руслан и Людмила», «Заповіт», «Лісова пісня», «Каштанка»}.
G = {(a, b)( a(A, b(B, a
· автор b}.
2. На множествах A = {0,1,2,3,4} и B = {5,6,7,8,9} заданы соответствия:
G1 = {(1,5), (1,6), (2,6), (3,9), (4,9)};
G2 = {(0,6), (1,6), (2,7), (3,7), )4,9)};
G3 = {(0,6), (1,7), (2,5), (3,9), (4,8)}.
Задать соответствия всеми возможными способами.

4.6. ТИПЫ (СВОЙСТВА) БИНАРНЫХ СООТВЕТСТВИЙ
Пусть задано некоторое соответствие G ( А(В = {(a, b)(a(A, b(B, (a, b)(G}.
Соответствие называется всюду определённым (или полностью определённым), если его область определения совпадает со всем множеством А: Dom(G) = А. Иными словами каждый элемент множества А участвует в парах (а,b)(G, и при этом для каждого а(А найдётся хотя бы один образ из множества В. Сечение по всякому элементу а(А не будет пустым.
В противном случае соответствие называют частично определённым (или просто частичным).
Соответствие G называется сюръективным, если его множество значений совпадает со всем множеством B : Im(G) = B. Иными словами, каждый элемент b(B участвует в парах (а,b)(G, как минимум, один раз. То есть для каждого элемента b(B найдется хотя бы один прообраз из множества А. Говорят, что при сюръективном соответствии покрывается всё множество В.
13 SHAPE \* MERGEFORMAT 1415
Соответствие G называется функциональным (или однозначным), если каждому элементу множества А соответствует не более одного элемента из множества В. Пары (a, b) такого соответствия не содержат одинаковых первых координат и различных вторых. Каждый элемент а(А имеет не более одного образа b(B.
Среди функциональных также различают полностью определённые и частично определенные соответствия, равно как и сюръективные и не сюръективные.






Функциональное соответствие Не функциональное соответствие
Соответствие G называется инъективным, если любой элемент b(В имеет не более одного прообраза. Пары такого соответствия (a, b) не содержат одинаковых вторых и разных первых координат. При этом каждый элемент а(А имеет не более одного образа.
13 SHAPE \* MERGEFORMAT 1415
Соответствие G называется биективным (или взаимно однозначным), если оно всюду определено, сюръективно, функционально и инъективно. В этом случае каждому элементу а(А ставится в соответствие один и только один элемент b(В. В парах (a, b) нет двух одинаковых первых элементов, вторых также.
13 SHAPE \* MERGEFORMAT 1415
Соответствие G называется отображением множества А в множество В (или просто А в В), если оно является всюду определенным и функциональным.
Соответствие G называется отображением множества А на множество В (или просто А на В), если оно является всюду определенным, функциональным и сюръективным.
13 SHAPE \* MERGEFORMAT 1415
Задача 4.6.1. На множествах А = {a,b,c,d,e} и В = {1,2,3} задано соответствие G={(a,2), (b,3), (c,1), (d,2), (e,1)}. К какому из основных типов (всюду определённое, сюръективное, функциональное, инъективное) оно относится. Для удобства представить G графически (стрелочное изображение).
Решение.
Соответствие является всюду определённым, так как пр1G = A.
Соответствие является сюръективным, поскольку пр2G = В.
Соответствие является функциональным, поскольку первые координаты пар не повторяются.
Соответствие является не инъективным, так как элементы 1(В и 2(В имеют больше одного прообраза.
Данное соответствие есть отображение А в В.
13 SHAPE \* MERGEFORMAT 1415
Задача 4.6.2. На множествах А = {a,b,c,d} и В = {1,2,3,4} задано соответствие G={(a,1), (b,2), (b,3), (d,4)}. К какому из основных типов (всюду определённое, сюръективное, функциональное, инъективное) оно относится. Для удобства представить G графически (стрелочное изображение).
Решение.
Соответствие является частично определённым, так как пр1G
· A (элемент с(А не встречается ни в одной паре).
Соответствие является сюръективным, поскольку пр2G = В.
Соответствие не является функциональным, поскольку первые координаты пар повторяются (координата b).
Соответствие является инъективным, так как элементы из множества В имеют ровно по одному прообразу.
Данное соответствие не есть отображение, так как не является всюду определённым и функциональным.
Задача 4.6.3. Пусть A = R – множество действительных чисел, множество B = R+ - неотрицательных действительных чисел, G ={( x, y )(x(R, y(R+, y = x2 }. Найти тип этого соответствия.
Решение.
Из свойств функции y = x2 вытекает, что рассматриваемое соответствие:
Всюду определено, так как для каждого x(R найдется образ – значение y = x2 ( 0.
Сюръективно, ибо для каждого y (0 найдется прообраз – значение 13 EMBED Equation.DSMT4 1415.
Функционально, потому, что для каждого x(R найдется только один образ – значение y = x2 ( 0.
Не инъективно, так как для всякого y(R+, y > 0 во множестве R существуют два прообраза – значения x1 = y , x2 =
·y .
Не взаимно однозначно, поскольку не является инъективным.

4.7. ОБРАТНОЕ СООТВЕТСТВИЕ
Пусть задано некоторое соответствие G ( А(В = {(a, b)(a(A, b(B, (a, b)(G}. Обратным по отношению к данному называется соответствие G
·1 ( В(А = {(b, a)(a(A, b(B, (a, b)(G}. Переход от G к G
·1 осуществляется перестановкой первой и второй координат графика соответствия. В этом случае образ соответствия G становится прообразом для G
·1 , а прообраз для G – образом для G
·1.
Графически обратное соответствие получается из прямого изменением направления стрелок.
Функциональное соответствие называется обратимым, если и обратное ему соответствие также будет являться функциональным. Обращение функционального соответствия возможно тогда и только тогда, когда оно является биективным.
Задача 4.7.1. А = {a, b, c, d}; B = {1, 2, 3, 4, 5}; G = {(a,2), (b,1), (b,5), (d,3)}. Определить тип прямого и обратного соответствий.
Решение. Обратное G
·1={(2,a), (1,b), (5,b), (3,d)}.
Прямое соответствие G является частично определённым, не сюръективным, не функциональным (элемент b имеет два образа) и инъективным.
Обратное G
·1 также есть частично определённым и не сюръективным, но является функциональным, но не инъективным (элемент b имеет два прообраза).
Задача 4.7.2. А = {a, b, c,}; B = {1, 2, 3}; G = {(a,1), (с,3), (b,2)}. Определить тип прямого и обратного соответствий.
Решение. G
·1 = {(1,a), (3,с), (2,b) }. Прямое и обратное соответствия являются биективными.
Задачи для самостоятельного решения.
1. Найти типы прямого и обратного соответствий:
G = {1,a), (1,b), (2,a)}; A = {1, 2}, B = {a, b};
G = {1,4), (2,3), (3,2), (4,1)}; A = B = {1, 2, 3, 4};
G = {( a1,b1), (a2,b2), (a3,b2)}; A = {a1, a2, a3}, B = {b1, b2 ,b3}.

4.8. ФУНКЦИЯ
Функции – это частный случай бинарных соответствий, на которые наложены дополнительные ограничения. Это понятие является основополагающим в математике.
Под функцией из множества Х в(на) множество Y мы понимаем всюду определённое бинарное соответствие, при котором каждый элемент множества Х связан с единственным элементом множества Y. Другими словами, для каждого х(Х существует ровно одна пара из соответствия вида (х, у). Графически (в стрелочном представлении) из каждого кружочка, представляющего элемент х, выходит ровно одна стрелка.
Для обозначения функции применяется такая символика: если f ( X(Y, то f : X(Y. При этом важно подчеркнуть, что функция f переводит элементы из Х в элементы из Y. Множество Х принято называть областью определения, а Y – областью значения функции.
13 SHAPE \* MERGEFORMAT 1415
Множеством значений функции называется подмножество в Y, состоящее из образов всех элементов х(Х. Оно обозначается символом f (Х).
Поскольку для каждого х(Х существует единственным образом определённый y(Y, такой, что (х, у) (f, мы будем писать у = f(x) и говорить, что функция f отображает множество Х в множество Y, а f(x) будем называть образом х при отображении f или значением функции, соответствующей аргументу х.
Если множества Х и Y бесконечны, мы не можем нарисовать стрелочное представление этого соответствия. В этом случае необходимо обратиться к традиционному математическому представлению такой функции, а именно, к её графику.
Рассмотрим важнейшие свойства функции. Функция называется инъективной или инъекцией, если из равенства f(х1) = f(х2) следует, что х1 = х2 для всех х1, х2 ( Х. Логически это эквивалентно тому, что из неравенства х1
· х2 вытекает неравенство f(х1)
· f(х2). То есть у инъективной функции нет повторяющихся значений.
Функция называется сюръективной или сюръекцией, или функцией «на», если множество её значений совпадает с областью значений. Это означает, что для каждого у*(Y найдётся такой х*(Х, что у* = f(х*). Таким образом, каждый элемент области значений будет являться образом какого-то элемента из области определения f.
Функция называется биективной или биекцией, если она инъективна и сюръективна одновременно.
Поскольку любая функция – это бинарное соответствие f : X(Y, поэтому всегда можно построить обратное соответствие. Если при этом мы снова получим функцию, то исходную функцию будем называть обратимой. Обратную функцию будем обозначать: f
·1 :Y(X.
Функция f состоит из пар вида (х, у), где у = f(x). Обратная функция f
·1 будет состоять из пар (у, х), где х = f
·1 (у). Иными словами, обратная функция «переворачивает» действие исходной.
Функция обратима тогда и только тогда, когда она биективна.

Задача 4.8.1. Какие из следующих соответствий есть функции, а какие нет и почему?
A = {a, b, c}, B = {1, 2, 3}.
G1 = {a,1), (b,1), (c,2)};
G2 = {(a,1), (b,2), (b,3), (c,2)};
G3 = {(a,1), (c,2)}.
Решение. G1 – это функция; G2 – не функция, так как элементу b соответствуют два различных элемента из Y – 2 и 3; G3 – не функция, потому что соответствие не является полностью определённым.
13 SHAPE \* MERGEFORMAT 1415
Задача 4.8.2.
Определить, какие из изображенных функций инъективны, сюръективны или биективны.

Рис.4.18

Решение.
Данная функция не инъективна, поскольку значение 1(Y соответствует а и b(X. Функция не является сюръекцией, потому что в элемент 2(Y ничего не переходит;
данная функция инъективна, так не имеет повторяющихся значений. Она также и сюръективна, поскольку множество её значений совпадает с областью значений. В этом случае имеем биективную функцию;
значение 1 функция принимает как на а, так и на b. Значит, она не инъекция. Однако она сюръективна, поскольку в множество её значений входят все элементы области значений;
функция инъективна, но не сюръективна.
Задача 4.8.3. Показать, что функция k : R(R, заданная формулой k(x) = 4x + 3 является биекций.
Решение. В этой задаче множества Х и Y равны множеству действительных чисел R. Предположим, что существуют значения х = а1 и х = а2 такие, что k(a1) = k(a2), то есть
4а1 + 3 = 4а2 + 3.
Из этого равенства вытекает, что 4а1 = 4а2 , откуда следует, что а1 = а2. То есть разным значениям аргумента х соответствуют разные значения функции k(x). Значит, данная функция инъективна.
Покажем, что функция сюръективна. Для этого нужно доказать, что область значений функции совпадает с её множеством значений. Пусть у = b(Y. Найдётся ли такое значение х = а(Х, что k(a) = b? Имеем: 4а1 + 3 = b. Откуда 13 EMBED Equation.DSMT4 1415. Очевидно, что это значение принадлежит множеству Х. Итак, данная функция сюръективна.
Поскольку k(x) = 4x + 3 является одновременно и сюръективной, и инъективной, то она биективна.
Задача 4.8.4. Найти функцию, обратную к заданной формулой
k(x) = 4x + 3.
Решение. Поскольку в предыдущей задаче доказана биективность данной функции, следовательно она является обратимой. То есть если у = k(x), следовательно, существует функция х = k
·1 (у). Из равенства у = 4x + 3 выразим 13 EMBED Equation.DSMT4 1415. Это и есть k
·1 (у). Однако по традиции в математике аргумент обозначается символом х, функция у. Перейдя к таким обозначениям, получим обратную функция в виде: 13 EMBED Equation.DSMT4 1415.
График прямой и обратной функций симметричны относительно биссектрисы 1 и 3-го координатных углов (прямая у = х).

13 SHAPE \* MERGEFORMAT 1415
Рис.4.19
Задачи для самостоятельного решения.
1. Х = {0, 2, 4, 6}, Y = {1, 3, 5, 7}. Какие из следующих соответствий между множествами Х и Y являются функциями, определёнными на Х со значениями в Y? Какие из найденных функций инъективны, сюръективны?
{(6, 3), (2, 2), (0, 3), (4, 5)};
{(2, 3), (4, 7), (0, 1), (6, 5)};
{(2, 4), (4, 5), (6, 3)};
{(6, 1), (0, 3), (4, 1), (0, 7), (2, 5)}.
2. Области определения и значений следующих функций совпадают с множеством целых чисел Z. Какие из них инъективны, сюръективны или биективны?
f(n) = 2n + 1;
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
3. Изобразить графики функций. Найти их множество значений. Какие из них инъективны, сюръективны или биективны. Найти обратную функцию (если возможно).
f : Z ( Z, f(x) = x2 + 1;
f : N ( N, f(x) = 2x ;
f : R ( R, f(x) = 5x - 1;
f : R ( R, 13 EMBED Equation.DSMT4 1415
f : R ( R, f(x) = 2x - |x|.
4. Функция f : Х ( Y задана формулой f(x) = 1 + 2/х , где Х – множество вещественных чисел, отличных от 0, а Y – множество вещественных чисел без 1. Показать, что эта функция биективна и найти её обратную к ней функцию. Сделать чертёж.
4.9. ОТНОШЕНИЕ НА МНОЖЕСТВЕ
Пусть задано некоторое непустое множество А и R – некоторое подмножество декартова квадрата множества А: R ( A ( A.
Отношением R на множестве А называют подмножество множества А(А (или А2). Таким образом отношение есть частный случай соответствия, где область прибытия совпадает с областью отправления. Так же, как и соответствие, отношение – это упорядоченные пары, где оба элемента принадлежат одному и тому же множеству.
R ( A ( A = {(a, b) | a(A, b(A, (a, b)(R}.
Тот факт, что (a, b)(R можно записать так: a R b. Читается: «а находится в отношении R к b» или «между а и b имеет место отношение R». В противном случае записывают: (a, b)(R или a(R b.
Примером отношений на множестве чисел являются следующие: «=», «(», «(», «>» и т.д. На множестве сотрудников какой-либо фирмы  отношение «быть начальником» или «быть подчинённым», на множестве родственников – «быть предком», «быть братом», «быть отцом» и т.д.
Рассмотренные отношения носят название бинарных (двухместных) однородных отношений и являются важнейшими в математике. Наряду с ними рассматривают также п-местные или п-арные отношения:
R ( A ( A (( A = An = {(a1, a2,an) | a1, a2,an ( A}.
Поскольку отношение есть частный случай соответствия, для их задания могут быть использованы все ранее описанные способы.
Очевидно, что задавая отношение матричным способом, мы получим квадратную матрицу.
При геометрическом (графическом) изображении отношения мы получим схему, включающую:
вершины, обозначаемые точками или кружочками, которые соответствуют элементам множества,
и дуги (линии), соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу a к вершине, соответствующей элементу b , если a R b.
Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.
Задача 4.9.1.Отношение R «быть делителем на множестве M = {1, 2, 3, 4 }» может быть задано матрицей:
13 EMBED Equation.DSMT4 1415;
перечислением: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4)};
геометрически (графически):

13 SHAPE \* MERGEFORMAT 1415
Задачи для самостоятельного решения.
1. Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям на множестве А = {1, 2, 3, 4, 5, 6, 7}:
R1 = {(x, y)| x, y(A; x + y = 9};
R2 = {(x, y)| x, y(A; x < y}.
2. Отношение R на множестве X = {a, b, c, d} задано матрицей
13 EMBED Equation.DSMT4 1415,
у которой порядок строк и столбцов соответствует порядку выписанных элементов. Перечислить упорядоченные пары, принадлежащие данному отношению. Изобразить отношение с помощью графа.
3. Отношение на множестве А = {1, 2, 3, 4} представлено графом. Необходимо:
перечислить упорядоченные пары, принадлежащие R;
выписать соответствующую матрицу;
определить это отношение с помощью предикатов.
(ответ: a-b=1).

4.10. ОСНОВНЫЕ ТИПЫ (СВОЙСТВА) БИНАРНЫХ ОТНОШЕНИЙ
Пусть задано бинарное отношение R на множестве А2 : R ( A ( A = {(a, b) | a(A, b(A, (a, b)(R}
Бинарное отношение R на множестве А называется рефлексивным, если для любого a(А выполняется aRa , то есть (а, а)(R. Главная диагональ матрицы рефлексивного отношения состоит из единиц. Граф рефлексивного отношения обязательно имеет петли у каждой вершины.
Примеры рефлексивных отношений: (, =, ( на множестве действительных чисел, «не быть начальником» на множестве сотрудников.
Бинарное отношение R на множестве А называется антирефлексивным (иррефлексивным), если для любого a(А не выполняется отношение aRa, то есть (а, а)(R. Главная диагональ матрицы иррефлексивного отношения состоит из нулей. Граф иррефлексивного отношения не имеет петель.
Примеры антирефлексивных отношений: <, > на множестве действительных чисел, перпендикулярность прямых на множестве прямых.
Бинарное отношение R на множестве A называется симметричным, если для любых a, b(А из aRb следует bRa, то есть если (a, b)(R, то и (b, a)(R. Матрица симметричного отношения симметрична относительно своей главной диагонали (
·ij =
·ji). Граф симметричного отношения не является ориентированным (рёбра изображаются без стрелок). Каждая пара вершин здесь соединена неориентированным ребром.
Примеры симметричных отношений: ( на множестве действительных чисел, «быть родственником» на множестве людей.
Бинарное отношение R на множестве A называется:
антисимметричным, если для любых a, b(А из aRb и bRa следует, что a=b. То есть, если (a, b)(R и (b, a)(R, то отсюда вытекает, что a=b. Матрица антисимметричного отношения вдоль главной диагонали имеет все единицы и не имеет ни одной пары единиц, расположенных на симметричных местах по отношению к главной диагонали. Иными словами, все
·ii=1, и если
·ij=1, то обязательно
·ji=0. Граф антисимметричного отношения имеет петли у каждой вершины, а вершины соединяются только одной направленной дугой.
Примеры антисимметричных отношений: , (, ( на множестве действительных чисел; (, ( на множествах;
асимметричным, если для любых a, b(А из aRb следует невыполнение bRa, то есть если (a, b)(R, то (b, a)(R. Матрица асимметричного отношения вдоль главной диагонали имеет нули (
·ij=0) все и ни одной симметричной пары единиц (если
·ij=1, то обязательно
·ji=0). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.
Примеры асимметричных отношений: <, > на множестве действительных чисел, «быть отцом» на множестве людей.
Бинарное отношение R на множестве A называется транзитивным, если для любых a, b, с(А из aRb и bRa следует, что и aRс. То есть если (a, b)(R и (b, с)(R вытекает, что (а, с)(R. Матрица транзитивного отношения характеризуется тем, что если
·ij=1 и
·jm=1, то обязательно
·im=1. Граф транзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно есть дуги из первой в третью вершину.
Примеры транзитивных отношений: <, (, =, >, ( на множестве действительных чисел; «быть начальником» на множестве сотрудников.
Бинарное отношение R на множестве A называется антитранзитивным, если для любых a, b, с(А из aRb и bRa следует, что не выполняется aRс. То есть если (a, b)(R и (b, с)(R вытекает, что (а, с)(R. Матрица антитранзитивного отношения характеризуется тем, что если
·ij=1 и
·jm=1, то обязательно
·im=0. Граф антитранзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно нет дуги из первой в третью вершину.
Примеры антитранзитивных отношений: «несовпадение чётности» на множестве целых чисел; «быть непосредственным начальником» на множестве сотрудников.
Если отношение не обладает некоторым свойством, то, добавив недостающие пары, можно получить новое отношение с данным свойством. Множество таких недостающих пар называют замыканием отношения по данному свойству. Обозначают его как R*. Так можно получить рефлексивное, симметричное и транзитивное замыкание.
Задача 4.10.1. На множестве А = {1, 2, 3, 4} задано отношение R={(a,b)| a,b(A, a+b(чётное число}. Определить тип данного отношения.
Решение. Матрица данного отношения:
13 EMBED Equation.DSMT4 1415. Очевидно, что отношение является рефлексивным, так как вдоль главной диагонали расположены единицы. Оно симметрично:
·13 =
·31,
·24 =
·42. Транзитивно: (1,3)(R, (3,1)(R и (1,1)(R; (2,4)(R, (4,2)(R и (2,2)(R и т.д.
Задача 4.10.2. Какими свойствами на множестве А = {a, b, c, d} обладает бинарное отношение R = {(a,b), (b,d), (a,d), (b,a), (b,c)}?
Решение. Построим матрицу данного отношения и его граф:
13 SHAPE \* MERGEFORMAT 1415
Отношение иррефлексивно, так как все
·ii = 0. Оно не симметрично, так как
·23=1, а
·32=0, однако
·12=
·21=1. Отношение не транзитивно, поскольку
·12=1,
·23=1 и
·13=0;
·12=1,
·21=1 и
·11=0; но при этом
·12=1,
·24=1 и
·14=1.
Задача 4.10.3. На множестве А = {1,2,3,4,5} задано отношение R = {(1,2), (2,3), (2,4), (4,5)}. Определить тип отношения и найти следующие замыкания для R:
рефлексивное;
симметричное;
транзитивное.
Решение. Отношение иррефлексивно, поскольку нет ни одного элемента вида (а,а). Асимметрично, так как не содержит пар вида (a,b) и (b,a) и все диагональные элементы равны 0. Антитранзитивно, поскольку (1,2)(R, (2,3)(R, но (1,3)(R. Аналогично (2,4)(R, (4,5)(R, а (2,5)(R и т.д.
рефлексивное замыкание данного отношения R*={(1,1), (2,2), (3,3), (4,4), (5,5)};
симметричное замыкание: R*={(2,1), (3,2), (4,2), (5,4)};
транзитивное замыкание: R*={(1,3), (1,4), (2,5)}. Рассмотрим граф исходного отношения и полученного транзитивного.
13 SHAPE \* MERGEFORMAT 1415
Задачи для самостоятельного решения.
1. Задано отношение R = {(1,1), (1,2), (1,3), (3,1), (2,3)}. Определить его тип и найти замыкания по рефлексивности, симметричности и транзитивности.
2. Отношение на множестве слов русского языка определено следующим образом: аRb тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.
3. Указать примеры бинарных отношений на множестве А = {1, 2) и В = {1, 2, 3}, которые были бы:
не рефлексивное, не симметричное, не транзитивное;
рефлексивное, не симметричное, не транзитивное;
симметричное, но не рефлексивное и не транзитивное;
транзитивное, но не рефлексивное и не симметричное;
рефлексивное, симметричное, но не транзитивное;
рефлексивное, транзитивное, но не симметричное;
не рефлексивное, симметричное, транзитивное;
рефлексивное, симметричное, транзитивное.
4.11. ОСНОВНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙ
Отношение эквивалентности. Бинарное отношение R на множестве А, которое является рефлексивным, симметричным и транзитивным, называется отношением эквивалентности.
Важное значение этого отношения состоит в том, что оно даёт признак разбиения множества А на непересекающиеся подмножества, которые называются классами эквивалентности. Класс эквивалентности – это множество вторых координат пар (а, b)(R, у которых первая координата одна и та же. Обозначается: К(а) = {b | b(A, (а, b)(R}. Для каждого элемента а(A можно определить его класс эквивалентности. Множество всех классов эквивалентности называется фактор-множеством по данному отношению R. Обозначается F/R. Мощность фактор-множества называется индексом разбиения исходного множества А.
Граф отношения эквивалентности представляет собой объединение (сумму) полных подграфов, каждый из которых соответствует классу эквивалентности.
Отношение порядка.
Бинарное отношение R на множестве А называется отношением строгого порядка, если оно иррефлексивно, асимметрично и транзитивно.
Бинарное отношение R на множестве А называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.
Множество, на котором можно определить отношение порядка, называется упорядоченным этим отношением.
Если для произвольных элементов а и b такого множества имеет место соотношение aRb либо bRa, то такое множество называется линейно (полностью) упорядоченным.
Если же для произвольных элементов а и b такого множества соотношение aRb либо bRa определено не для всех, а лишь для некоторых элементов а и b, то такое множество называется частично упорядоченным.
Для линейно упорядоченного множества любые два его элемента а и b называются сравнимыми.
Для частично упорядоченного множества некоторые элементы сравнимы, а некоторые не сравнимы.
Элемент р(А называется наименьшим элементом множества А, если для всех а(А имеет место соотношение: pRa. Обозначается так: p = min A.
Элемент q(А называется наибольшим элементом множества А, если для всех а(А имеет место соотношение: aRq. Обозначается так: q = max A.
Задача 4.11.1. Показать, что отношение R = {(a,a), (a,b), (b,a), (b,b), (c,c), (d,d), (d,e), (e,d), (e,e)} а множестве A = {a, b, c, d, e} является отношением эквивалентности. Найти фактор-множество по данному отношению и индекс разбиения данного множества.
Решение. Очевидно, что отношение R рефлексивно, так есть все пары вида (а, а). Оно симметрично, поскольку содержит пары (a,b) и (b,a), (d,e) и (e,d). Транзитивно: (a,b), (b,a) и (a,a); (d,e), (e,d) и (d,d). Следовательно, отношение R – отношение эквивалентности.
13 SHAPE \* MERGEFORMAT 1415
Классы эквивалентности: К(а) ={a, b}; K(b) ={a, b}; K(c) = {c}; K(d) ={d, e}; K(e) = {d, e}.
Фактор-множество по отношению R: F/R = { {a, b}; {c}; {d, e}}.
Индекс разбиения данного множества А: | F/R | = 3.
Задача 4.11.2.
Является ли множество А линейно упорядоченным отношением R?
А = {Петров (рост 180 см); Сидоров (рост 175 см); Данилов (рост 174 см); Орлов (рост 171 см); Васильев (рост 176 см)}; R = «а выше b».
Решение. Построим матрицу и граф данного отношения.
13 SHAPE \* MERGEFORMAT 1415
Данное отношение является иррефлексивным, асимметричным и транзитивным. Следовательно, R - это отношение строгого порядка. Множество А является линейно упорядоченным, поскольку для любых двух его элементов выполняется соотношение: либо а выше b, либо а не выше b (то есть либо a R b , либо a(R b). Поэтому любые два элемента множества А будут сравнимы. Найдём минимальный и максимальный элементы множества А. Так для элемента П(А выполняется соотношение ПRa для всех а(А (то есть Петров выше Сидорова, выше Данилова и т.д.). По определению элемент П – наименьший на множестве А: П = min A. Для элемента О(А выполняется соотношение аRO для всех а(А (то есть Петров выше Орлова, Сидоров выше Орлова, Данилов выше Орлова и т.д.). По определению элемент О – наибольший на множестве А: О = max A.
Задача 4.11.3. Для данного отношения R ={(1,2), (2,3), (3,4), (5,5)} на множестве А = {1, 2, 3, 4, 5} проделать следующее:
изобразить графически;
достроить до отношения порядка (строгого или нестрогого);
упорядочить частично и линейно;
найти наибольший и наименьший элементы и указать пары несравнимых элементов.

Решение.
13 SHAPE \* MERGEFORMAT 1415
Достроить до отношения строгого порядка нельзя, поскольку имеется элемент (5,5). Поэтому можем лишь добавить пары (1,1), (2,2) и (3,3) и тем самым сделаем отношение рефлексивным. С учётом добавленных пар отношение становится антисимметричным. Найдём транзитивное замыкание данного отношения. Для пар (1,2) и (2,3) добавим (1,3); для (2,3) и (3,4) – (2,4); для вновь добавленной (1,3) и данной (3,4) – (1,4). Элемент (5,5) транзитивности не нарушает. Получаем новое отношение R1 нестрого порядка:
R1 = {(1,2), (2,3), (3,4), (5,5), (1,1), (2,2), (3,3), (1,3), (2,4), (1,4)}.
Полученное отношение является частично упорядоченным, поскольку элемент 5 не может быть сравним с остальными. То есть, например, если для элементов 1 и 2 выполняется 1R2, то для 1 и 5 не выполняется ни 1R5, ни 5R1.
Минимальный элемент множества А – это 1, поскольку он входит во все пары: (1,2), (1,3), (1,4). Максимальный – элемент 4: (1,4), (2,4), (3,4). Однако, минимальным также будет и элемент 5, поскольку имеем пару (5,5). По этой же причине элемент 5 есть и максимальным. Несравнимыми будут элементы 1 и 5, 2 и 5, 3 и 5, 4 и 5, потому что они не входят ни в одну пару отношения. Следовательно, наше новое отношение R1 является частично упорядоченным.
Задачи для самостоятельного решения.
1. Для данного отношения R на множестве А = {1, 2, 3, 4, 5} проделать следующее:
изобразить R графом;
достроить R до отношения эквивалентности, указать фактор-множество и индекс разбиения;
достроить до отношения порядка и частично упорядочить, указать максимальный и минимальный элементы, а также пары несравнимых элементов;
достроить до отношения строгого порядка и линейно упорядочить, указать наибольший и наименьший элементы множества.
R = {(1,2), (2,3), (4,5), (5,3)};
R = {(1,2), (1,3), (3,2), (4,5)};
R = {(1,2), (2,3), (1,4), (3,5)}.

ЛИТЕРАТУРА
Галушкина Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. М.: Айрис-пресс, 2007. 176 с. (Высшее образование).
Капитонова Ю. В. Лекции по дискретной математике. БХВ-Петербург, 2004. 614 с.
Ерусалимский Я. М. Д Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 2000. 280 с.
Судоплатов С. В. Элементы дискретной математики / С. В. Судоплатов, Е. В. Овчинникова. - М.-Новосибирск: ИНФРД-М НГТУ, 2002. 280 с.
Нефёдов В.Н. Курс дискретной математики / В. Н. Нефёдов, В. А. Осипова - М. : Изд-во МАИ, 1992. 264 с.
Кузнецов О.П. Дискретная математика для инженеров. 6-е узд.,стер. СПб: издательство «Лань», 2009. 400 с.
Романовский И. В. Дискретный анализ. 4-е изд., испр. и доп. СПб.: Невский Диалект, БХВ-Петербург, 2008. 336 с.
Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука; Физматлит, 2000. 544 с.
Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. - СПб.: БХВ-Петербург, 2005. 416 с.
Навчальне видання




Швачич Геннадій Григорович
Сазонова Марина Сергіївна
Бартенєв Георгій Михайлович


«ДИСКРеТНА МАТЕМАТИКА»
Розділ 1. Теорія множин. Алгебра множин

Навчальний посібник



Тем план 2015, поз. .




Підписано до друку ______2015. Формат 60х84 1/16. Папір друк. Друк плоский. Облік.-вид. арк. . Умов. друк. арк. . Тираж 100 пр. Замовлення № ____


Національна металургійна академія України
49600, Дніпропетровськ-5, пр. Гагаріна, 4
______________________________________
Редакційно-видавничий відділ НМетАУ








13PAGE \* MERGEFORMAT14315

13PAGE 15


13PAGE 147115



х

у

А

х

у

2

В

2

Рис. 1.1

Рис. 1.2


1

-1

-6

x

y

2


Рис. 1.3


-3

2

Рис. 1.4
d

3

у

х

F

E

х

1

Рис. 1.5


-(

-2(

2(

(

у

Рис. 1.6


Рис. 2.3. А ( В

Рис. 2.2
·

Рис. 2.1. А ( U

В

А

U

U

А

U

A

В

В


В

Рис. 2.6. А ( В

Рис. 2.5. А \ В

Рис. 2.4. А ( B

А

U

U

А

U

A

А

В

V

A

B

V

A

B

V

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415V

A

B


· \ B

13 EMBED Equation.3 1415

V

A

B

V

A

B

13 EMBED Equation.3 1415

V

A

B

13 EMBED Equation.3 1415

1)

2)

V

3)

A

B

13 EMBED Equation.3 1415

V

A

B

13 EMBED Equation.3 1415

V

A

B

13 EMBED Equation.3 1415

С

В

А

8

4

3

2

1

6

7

V

5

1)

A

B

C

V

A

B

C

V

А

В

С

V

A\B

C

(A\B)(C

2)

C

B

A

C

A\(B(C)

B

C

B(C

A

U

Случай 3

A

U

C

B

A

R

U

Q

P

U

R

Q

P

U

R

Q

P

3)

U

R

Q

P

P(Q

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

Случай 2

Cлучай 1

V

B

A

V

B

A

V

В

А

А\В -

В\А -

А(В -

Рис. 4.3

U

A

B

A(B

U

A

B

13 EMBED Equation.3 1415

U


A

B


·

U

A

B

13 EMBED Equation.3 1415

B

A

U

13 EMBED Equation.3 1415

- Левая часть равенства

- Правая часть
равенства

U

A

B

C

U

A

B

C

U

A

B

C

A

B(C

A((B(C)

- Левая часть
равенства

U

A

B

C

U

A

B

C

(A(B)((A(C)

C

B

A

U

A(B

A(C

- Правая
часть
равенства

V

A

B

C

V

A

B

C

A(B ( C

13 EMBED Equation.3 1415

Необходимость:
если A(B ( C,
то 13 EMBED Equation.3 1415


V

A

B

C

V

A

B

C

13 EMBED Equation.3 1415

A(B=(

Достаточность:
если 13 EMBED Equation.3 1415,
то A(B(C

V

A

B

A(B

13 EMBED Equation.3 1415

V

A

B

V

A

B

C

a)

V

A

B

C

б)

5

6

7

V

1

2


3

4

A

B

C

a1
a2
.
.
an

A

b1 b2 b3 bm

B

(a1, b1) (a1, b2) (a1, b3) (a1, bm)



(a2, b1) (a2, b2) (a2, b3) (a2, bm)

(an, b1) (an, b2) (an, b3) (an, bm)







A(B

х

у

1 2 3 4
А

3


B 2


1

А ( В

С

D

х

у

А

В

V

30

27

5

40


·

13 EMBED Equation.3 1415

10

8

В

А

1

2

4

5

6

8

10

12

z

w

l

o

1

2

4

5

6

8

10

12

z

w

l

o

А

В

B

A

5

6

7

1

2

3


4

c

b

a

B

7

6

5

4

3

2

1

A

c

b

а


·

·

·

·

·

·

(
(
(
(
(
(
(


А

В

Dom(G)

Im(G)


·

·

·

·

(
(
(
(
(
(

Не инъективное
соответствие

Im(G)


А=Dom(G)


В


Частично определённое
соответствие

Всюду определённое
соответствие



·

·

·

·

·

·

(

(

(

(

(

В= Im(G)



·

·

·

·

A

Dom(G)
om(G)

Сюръективное
соответствие


·


·


·

Отображение
А в В


·


·


·


(

(

(

Не биективное
соответствие


(

(

(

(

(

(

Инъективное
соответствие

(

(

(

(





·

·

·

·

(

(

(


·

·

·

·

(

(

(

(


·

·

·

·

Биективное
соответствие

(

(

(


·


·


·


·

·

·

·

(

(

(

Отображение
А на В


А

В

А

В

a
·
b
·
c
·
d
·
e
·

( 1

( 2

( 3

A

B

a
·

b
·

c
·

d
·


( 1

( 2

( 3

( 4



А

В

Задача 1

Задача 2







Рис. 4.16


множество
значений

область
значений

область
определения

Диаграмма Эйлера-Венна функции f(x)

a
·
b
·
c
·

X

(1
(2
(3

Y

(1
(2
(3

X

a
·
b
·
c
·

Y

Y

Y

(1
(2
(3

X

a
·
b
·
c
·

Y

a)

б)

в)


A

2

B

1
3

4









U

х

у

у=4х+3

у=(х-3)/4

f(X)

Y

X

1 (

( 2

3 (

( 4

1 2


5 3

4

1 2


5 3

4

13 EMBED Equation.3 1415

a ( ( d




b ( ( c


a b c d e

{a,b} {a,b} {c} {d,e} {d,e}

c

e

d


b

a


c

b



d

a



e

П



В

С


Д

О

13 EMBED Equation.3 1415

1




5

2




3

4 (

1



5

2



3

4 (

R

R1

Рис. 2.7

Рис. 2.8

Рис. 2.9

Рис. 2.10

Рис. 2.11

Рис. 2.12

Рис. 2.13

Рис. 3.3

Рис. 3.4

Рис. 3.5

Рис. 3.6

Рис. 3.7

Рис. 4.1

Рис. 4.2

Рис. 4.4

Рис. 4.5

Рис. 4.6

Рис. 4.8

Рис. 4.7

Рис. 4.9

Рис. 4.10

Рис. 4.11

Рис. 4.12

Рис. 4.13

Рис. 4.14

Рис. 4.15


f

Рис. 4.17

Рис. 4.20

Рис. 4.21

Рис. 4.22

Рис. 4.23

Рис. 4.24

Рис. 4.25











Рис.3.2








 BDFJLNPVXZ\^`bdfhj
·
·
·
·
·
·
·
·
·
·
·
·CRoot EntryEquation NativeEquation NativeEquation NativeEquation Native,Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeBEquation Native

Приложенные файлы

  • doc 244450
    Размер файла: 2 MB Загрузок: 0

Добавить комментарий