Краткий курс лекций по Дискретной математике (стр. 12 )

В случае, когда утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта. Например, утверждение «Каждое чет­ное однозначное число является суммой двух простых чисел» легко проверить, рассмотрев равенства 2=1 + 1, 4 = 3+1, 6 = 5+1, 8 = 3 + 5.

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

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

Предположение, что Р (n) справедливо для всякого натурального n, если:

1) оно справедливо для n =1;

2) из справедливости утверждения для какого-либо произ­вольного натурального n = k следует его справедливость для n = k +1.

Действительно, из того, что утверждение верно при n= 1, вы­текает по второму условию его справедливость для n= 1 + 1 = 2, но тогда оно верно и для n = 2 + 1=3, n = 3+1= 4 и т. д. Ясно, что в конце концов мы дойдем до любого натурального числа n.

Сам метод математической индукции состоит в следующем:

Для доказательства справедливости P(n) для любого n (P(n) – есть одноместный предикат от n, значит, доказываем "nP(n) º 1)

1.  проверить истинность при n = 1, т. е. Р(1) = 1(истина);

2.  допускают, что Р(n) = 1 при n = k и

3.  проверяют истинность для n = k + 1.

Если P(k + 1) = 1, то "nP(n) º 1.

2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых

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

Пример 1. Пусть дана последовательность (n) натуральных чисел. Найдем формулу вычисления суммы первых n чисел:

S(n)=l+2 + 3 + ... + n.

Решение. Рассмотрим S(1), S(2), S(3), S(4). Мы имеем:

S(l)=l,

S(2)=1+2 = 3,

S(3)=1+2 + 3 = 6,

S(4)=1+2 + 3 + 4=10.

Заметив, что полученные числа можно записать в виде

естественно сделать предположение, что

(1)

Применим теперь метод математической индукции для доказа­тельства полученной формулы (1).

При n = 1: S(1) = 1×2/2=1.

Формула верна при n = 1. Предположим, что формула верна при n = k > 1:

Тогда

'Значит, из справедливости формулы для n = k вытекает ее справедливость для n = k + 1 По принципу математической индукции отсюда вытекает справедливость формулы (1) для всех натуральных значений n.

В некоторых случаях для доказательства тождества Р(n) = Q (n) можем сначала убедиться, что Р (1) = Q (1), и, предпола­гая справедливость равенства P(k)=Q(k), k>1, доказать тож­дество P(k + 1) = Q(k + 1). Тогда из истинности равенства P(k) = Q(k) будет следовать истинность равенства P(k + 1) = Q(k + 1)и по принципу математической индукции бу­дет следовать истинность тождества P(n)=Q(n) для всех n.

Пример 2. Рассмотрим последовательность (n2) квадратов натуральных чисел. Докажем справедливость формулы для вы­числения суммы первых n членов этой последовательности:

(2)

Обозначим l2 + 22 + 32 + ... + n2 = S (n) и

При n = 1: S(1) = 1, Т. е. S(1) = P(1).

Предполагаем теперь, что равенство верно для n = k, k > 1, т. е. S(k) = P(k).

Рассмотрим разности:

Итак, мы доказали, что S(1) = P(1) и S(k+l) - S (k) = = P (k+1) - P (k). Тогда по принципу математической индукции тождество (2) справедливо для всех n.

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

Пример 3. Пусть дана последовательность (n3) кубов нату­ральных чисел. Выведем формулу для вычисления суммы пер­вых n членов этой последовательности:

S(n)=l3 + 23 + 33 + … + n3.

Как и в примере 1, рассмотрим суммы S(1), S (2), S (3), S (4). Здесь мы имеем:

S(l)=l,

S(2)=l3 + 23 = 9,

S(3)=l3 + 23 + 33 = 36,

S (4)= 13 + 23 + 33 + 43= 100.

Поскольку мы предполагали, что S(k) = P(k), то отсюда сле­дует равенство S (k+ 1) = P (k + 1). Следовательно, по принципу математической индукции формула (3) справедлива для всех n.

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

Метод математической индукции успешно применяется и при доказательстве различных неравенств, при этом используются свойства неравенств. В качестве примера рассмотрим доказа­тельство неравенства, называемое неравенством Бернулли, которое имеет следующий вид:

(4)

при всех натуральных значениях n и для всех х> - 1.

При n = 1 это неравенство справедливо, так как 1 + х = 1 + x.

Предположим, что оно справедливо при n = k>1, т. е. спра­ведливо

Докажем, что оно верно и для n = k+1: умножим обе части равенства на 1 + х:

Учитывая, что kx2 ³ 0 и, следовательно, 1 + kx + x + kx2 ³ 1 + kx + x = 1+ x(k + 1). Тогда имеем:

(1 + x)k+1³ 1 + (k + 1)x.

Таким образом, мы показали, что неравенство (4) верно для n =1, и в предположении, что оно верно для n = k, доказали его справедливость для n = k+1 Значит, по принципу математиче­ской индукции неравенство Бернулли справедливо для всех на­туральных значений n.

Пример 4. Используя неравенство Бернулли доказать справедливость неравенства

При n = 1:

Пусть при n = k неравенство верно, т. е.

Докажем справедливость при n = k+1, т. е.

Левую часть представим в виде Используя неравенство Бернулли, имеем

Где

Но

Значит неравенство верно при любом n.

Пример 4. Доказать, что n3 – n делится на 3 при любом n.

При n = 1: 1 – 1 = 0 , 0 делится на 3.

Пусть при n = k : k3 – k делится на 3.

Докажем делимость при n = k + 1:

(k + 1)3 – (k + 1) = k3 + 3k2 + 3k + 1 – k – 1 = k3 + 3(k2 + k) – k = k3 – k + 3(k2 + k).

Т. к. k3 – k делится на 3 (по индуктивному предположению), 3(k2 + k) делится на 3, то и их сумма делится на 3.

Пример 5. Доказать, что сумма кубов трех последовательных натуральных чисел делится на 9.

Т. е. необходимо доказать, что n3 +(n + 1)3 + (n + 2)3 делится на 9.

При n = 1: 1+ 8 + 27 = 36 – делится на 9.

Пусть при n = k : k3 +(k + 1)3 + (k + 2)3 делится на 9.

Докажем, что делимость на 9 имеет место при n = k + 1:

(k+1)3+(k+2)3+(k+3)3 = (k+2)3 + k3 +3k2 +3k +1 +k3 + 9k2 +27k+27 = (k+2)2+k3+(k+1)3 +9(k2 +3k + 3), где

(k+2)2+k3+(k+1)3 делится на 9 по индуктивному предположению,

9(k2 +3k + 3) делится на 9.

Следовательно, их сумма делится на 9.

4. Обобщение метода математической индукции

Бывают случаи, когда утверждение, неверное для n =1, 2, ... , р - 1, справедливо для n = р. Если затем из предположения о его истинности для n = k>p можно доказать, что оно истинно и для n = k +1, то получаем, что данное выражение истинно для всех n ³ р.

Пример 6. Докажем, что выражение (кратно 19) для всех натуральных чисел n ³ 3.

Решение. При n = 3 получаем

73 + 82×3-3 = 343 + 512 = 855 = 45× 19

т. е. при n = 3 утверждение верно.

Предположим, что 7k +82k-3 кратно 19 при k >3, и докажем, что 7k+1 + 82(k+1)-3 кратно 19.

По предположению 7k +82k-3 = 19m, где mÎN, значит,

82k-3 = 19m – 7k.

Отсюда имеем:

7k+1 + 82(k+1)-3 = 7k+1 + 82k-3+2 = 7k+1 + 64×82k-3 = 7k+1 + 64(19m – 7k) = 7k(7 – 64) + 64× 19m = 64 × 19m – 57 × 7k = 19(64m - 3×7k),

т. е. выражение кратно 19.

Итак, мы доказали, что утверждение верно для n = 3, и из предположения, что оно верно для n = k>3, доказали его спра­ведливость для n = k + 1. Тогда на основании сказанного выше заключаем, что выражение для всех n ³ 3.

Пример 7. Доказать, что 2n ³ 5n – 3 при n ³ 5.

При n = 5: 25 = 32, 5×5 – 3 = 22 и 32 > 22.

Пусть неравенство верно при n = k, k > 5, т. е. 2k ³ 5k – 3.

Докажем справедливость неравенства при n = k +1, т. е. справедливость неравенства 2k+1 ³ 5(k+1) – 3 или 2k+1 ³ 5k +2.

Умножим обе части неравенства на 2: 2k+1 ³ 2(5k – 3).

Преобразуем правую часть неравенства: 2(5k – 3) = 10k – 6 = 5k + 2 + 5k – 8. Заметим, что 5k – 8 ³ 0 при k > 5, тогда 5k + 2 + 5k – 8 > 5k + 2 и, тогда 2k+1 ³ 5k +2.

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

1.  Сформулировать принцип метода математической индукции.

2.  Сформулировать обобщенный метод математической индукции.

3.  Вычислить сумму : 2+ 4+ 6+…+2n.

4.  Вычислить сумму : 1+3+5+…+(2n-1).

5.  Доказать справедливость равенства: 12+32+52+…+(2n-1)2 =

6.  Доказать справедливость неравенства: 2n

7.  Докажите, что истинно высказывание: при любых натуральных n.

8.  Доказать справедливость неравенства:

ЛЕКЦИЯ 15

ТЕМА: БИНАРНЫЕ ОТНОШЕНИЯ.

ПЛАН:

1.  Понятие отношения. Бинарное отношение

2.  Операции над бинарными отношениями

3.  Свойства бинарных отношений

4.  Специальные бинарные отношения

Главная

1.  Понятие отношения. Бинарное отношение.

Пусть заданы множества Х1, Х2,…,Хn и рассматривается некоторое подмножество их прямого произведения rÌ Х1Х2…Хn , т. е. множество упорядоченных наборов (а1, а2,…,аn), где а1ÎХ1 , а2ÎХ2,…,аnÎХn. Это множество называется n – местным отношением или n –арным предикатом, заданном на множестве Х1Х2…Хn .Если Х1= Х2=…=Хn=М, то rÌ Мn и называется n – местным отношением на множестве М.

Пример: на множестве R3 задан трехместный предикат или трехместное отношение P(x, y, z): «x2+y2+z2=25».

Говорят что а1, а2,…,аn находятся в отношении r, если (а1, а2,…,аn)Ì r.

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

Пусть даны непустые множества Х и У, и подмножество их прямого произведения rÌ ХУ. r называется бинарным отношением.

Т. е. r - множество упорядоченных пар (х, у). Говорят, что х и у находятся в отношении r, если (х, у) Ì r. Допускается запись: х r у, означающая, что (х, у) Ì r.

Элементы х и у называются координатами или компонентами отношения r.

Область определения бинарного отношения r называется множество Dr = {x| существует такое у, что х r у}.

Областью значений бинарного отношения r называется множество Rr = {y| существует такое х, что х r у}.

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

Рассмотрим некоторые примеры бинарных отношений.

1.  Отношения на множестве натуральных чисел N:

а) «х £ у», например, пары (7,7) и (6,8) принадлежат этому отношению, а пара (8,6) – не принадлежит. Область определения Dr =N, область значений Rr=N;

б) «иметь общий делитель, не равный единице». Пары (6,9), (4,2), (4,4) принадлежат этому отношению, а пары (7,9), (5,8) – не принадлежат. Область определения Dr =N, область значений Rr=N.

2. Отношение равенства на множестве действительных чисел R: «х = у». Этому отношению принадлежат все пары , в которых координаты равны, например, (9,9), (2,3; 2,3). Область определения Dr =R, область значений Rr=R.

3. Отношения на множестве точек декартовой плоскости:

а) «находится на одинаковом расстоянии от начала координат» - это множество всех пар (х, у), где хÎR и уÎR, таких, что х2 + у2 = r2, т. е. все точки окружности с центром в начале координат и радиусом r;

б) «быть симметричными относительно оси х» - этому отношению принадлежат пары точек (х, у) и (х,-у).

4. Отношения на множестве людей:

а) «жить в одном городе»;

б) «быть старше (моложе);

в) «быть сыном»;

г) «быть знакомыми».

2.  Операции над бинарными отношениями.

Для бинарных отношений определены теоретико – множественные операции объединения, пересечения и так далее.

Кроме этих операций над бинарными отношениями производят следующие оперции.

Обратное отношение. Для отношения r обратным является отношение r-1={(x, y)|(y, x)Îr}.

Для отношения х ³ у обратным является х £ у. Для отношения «быть делителем» обратное - «быть кратным».

Композицией отношений r1 и r2 называется отношение r2оr1 = {(x, z)| существует у такое, что (х, у) Îr1 и (у, z) Îr2 }.

Композицией двух отношений «Нина дочь Людмилы Ивановны» и «Людмила Ивановна мать Сергея» является отношение «Нина сестра Сергея».

Композицией двух отношений «прямая проходит через точку» и «точка принадлежит плоскости» является отношение «прямая пересекает плоскость».

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

1.  (r-1)-1=r. это свойство следует из определения обратного отношения;

2.  (r2оr1)-1 = r1-1оr2-1.

Для доказательства второго свойства, покажем, что множества в обеих частях равенства состоят из одних и тех элементов: (х, у)Î (r2оr1)-1«(у, х)Î r2оr1«$z (y, z)Îr1 и (z, x)Îr2«$z (y, z)Îr1-1 и (x, z) )Îr2-1«(x, y)Î r1-1оr2-1.

3. Свойства бинарных отношений.

Свойство рефлексивности и антирефлексивности.

Отношение r называется рефлексивным, если для любого хÎМ имеет место хrх.

Отношение r называется антирефлексивным, если ни для каких хÎМ не выполняется хrх.

Примеры:

а) отношение «х£у» рефлескивно, т. к х£х;

б) отношение «ху» рефлексивно, т. к хх;

в) отношение «х<y»антирефлексивно, т. к. ни для каких х не верно x<x;

г) отношение «быть симметричным относительно оси» не является симметричным и антирефлексивным. Симметричны сами себе только точки, лежащие на оси симметрии. Таким образом не всякая точка симметрична сама себе. Значит отношение не является симметричным. Но в свою очередь отношение и не является антисимметричным, потому что существуют точки симметричные сами себе.

Свойство симметричности и антисимметричности.

Отношение r называется симметричным, если для всех (х, у)ÎМ2 из хrу следует уrх.

Отношение r называется антисимметричным, если из хrу и уrх следует, что х = у.

Примеры:

а) отношение «быть симметричным относительно оси» симметрично, т. к. если точка А симметрична точке В, то и точка В симметрична точке А;

б) отношение «х=у» симметрично, т. к. если х=у, то у=х;

в) отношение х£у антисимметрично, т. к. если х£у и у£х следует, что х=у;

г) отношение «ху» антисимметрично, т. к. если ху и ух, то х=у.

Свойство транзитивности.

Отношение r называется транзитивным, если для любых x, y, z из хrу и уrz следует хrz.

Примеры:

а) отношение равенства «х=у» транзитивно, действительно, если х=у и у=z, то х=z;

б) отношение «x<y» транзитивно, т. к. если x<y и y<z, то x<z;

в) отношение «быть сыном» не транзитивно, например, «Сергей сын Алексея Ивановича» и «Алексей Иванович сын Ивана Петровича» , то тогда «Сергей внук Ивана Петровича»;

г) отношение «быть перпендикуляром» на множестве прямых на плоскости не транзитивно, т. к. если прямая а перпендикулярна прямой b и прямая b перпендикулярна прямой с, то прямые а и с параллельны.

Свойство эквивалентности.

Отношение r называется отношением эквивалентности, если оно рефлексиво, симметрично и транзитивно.

Примеры:

а) Отношение «х=у»: х=х – рефлексивно; у=х – симметрично; если х=у и у=z, то х=z – транзитивно. Отношение эквивалентно.

б) Отношение «подобие на множестве треугольников»: DАВС@DАВС – рефлексивно; если DАВС@DА1В1С1 , то DА1В1С1@DАВС – симметрично; если DАВС@DА1В1С1 и DА1В1С1@DА2В2С2, то DАВС@D А2В2С2. Отношение эквивалентно.

в) Отношение «жить в одном городе на множестве людей»: Коля живет в Москве. Коля живет в Москве сам с собой – рефлексивно; если Коля живет в Москве с Сергеем, то и Сергей живет с Колей в Москве – симметрично; Коля живет в Москве с Сергеем и Сергей живет в Москве с Виктором, то Коля живет в Москве с Виктором. Отношение эквивалентно.

г) Отношение «параллельность прямых на плоскости». Проверьте самостоятельно.

д) Отношение «перпендикулярность прямых на плоскости». Никакая прямая не перпендикулярна сама себе, значит, отношение антирефлексивно, следовательно, не является эквивалентным.

4. Специальные бинарные отношения.

В математике важную роль играют два вида специальных бинарных отношений: отношение эквивалентности и отношение порядка.

4.1. Отношение эквивалентности.

Пусть на некотором множестве Х задано отношение эквивалентности r. Выберем элемент х1ÎХ и образуем класс (подмножество) Х1, состоящий из х1 и всех элементов уÎХ, для которых хrу. Затем выберем из Х элемент х2ÏХ1 и составим класс Х2 из элемента х2 и всех элементов из Х\Х1 находящихся в отношении r с х2 и т. д.

Получим систему классов Х1, Х2,…,Хn такую, что любой элемент из множества Х входит в какой –либо из классов этой системы. Эти классы называются классами эквивалентности.

Определение: Классом эквивалентности, образованным (порожденным)элементом х, называется подмножество множества Х, состоящее из элемента х и всех элементов уÎХ, для которых хrу.

Обозначение класса эквивалентности, порожденного элементом х:

[x]={y|yÎX и хrу}.

Примеры:

а) Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого хÎZ[x]={x}, т. е. каждый класс состоит из одного элемента - числа х.

б) Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы.

Введем понятие разбиения множества Х.

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

Примеры:

а) Х={1,2,3,4,5}, тогда его разбиение множество {{1,2}, {3,5}, {4}}.

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

Система классов эквивалентности обладает следующими свойствами:

1.  Система образует разбиение множества Х.

2.  Любые два элемента из одного класса эквивалентны.

3.  Любые два элемента из разных классов не эквивалентны.

Докажем первое свойство: пусть Х1 и Х2 пересекаются, тогда существует элемент у такой, что х1rу (х1ÎХ1) и уrх2 (х2ÎХ2), следовательно х1rх2, что противоречит условию построения Х2.

Доказательства 2-го и 3-го свойств аналогичны.

Приведем формулировки теорем о классах эквивалентности.

Теорема1. Пусть r - отношение эквивалентности на множестве Х. Тогда:

1.  если хÎХ, то хÎ[x];

2.  если {x, y}ÌX и хrу, то [x]=[y], т. е. класс эквивалентности порождается любым своим элементом.

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

Теорема 2. Любое разбиение множества Х определяет на этом множестве Х отношение эквивалентности r: хrу тогда и только тогда, когда х и у принадлежат одному подмножеству разбиения.

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

Теорема 3. Любое отношение эквивалентности определяет разбиение множества Х на классы эквивалентности относительно этого отношения.

4.2. Отношение порядка.

Рассмотрим еще один тип специальных бинарных отношений.

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

Отношение частичного порядка обозначается символом

Пример:

а) отношение на множестве действительных чисел «х£у»- рефлексивно, антисимметрично и транзитивно, значит, является отношением частичного порядка.

б) отношение «АÍВ» - отношение частичного порядка.

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

Пример:

а) Отношение на множестве действительных чисел «x<y» - антирефлексивно, не симметрично, транзитивно, значит, является отношением строгого порядка на множестве действительных чисел.

б) Схема организации подчинения в учреждениях – отношение строгого порядка (проверьте самостоятельно).

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

Примеры:

а) Отношение «х£у» - отношение линейного порядка, т. к. любые два действительных числа сравнимы.

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

Множество Х с заданным на нем отношением частичного или линейного порядка называется частично или линейно упорядоченным.

Любое частично упорядоченное множество можно представить в виде схемы. Для введения правила построения схемы введем некоторые понятия.

Пусть Х непустое конечное множество. На этом множестве задано отношение частичного порядка . х у, если ху и х¹ у.

Говорят: у покрывает х, если ху и не существует такого элемента u, что хuу.

Пример: отношение на множестве целых чисел : , т. е. 2 покрывает 1, т. к. 1<2 и не существует целого числа х такого, что 1<x<2.

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

Такие схемы называются диаграммами Хассе.

Примеры:

а) Пусть А={1,2,3}. Рассмотрим отношение быть подмножеством r= {Æ, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Диаграмма имеет вид:

б) На множестве Х={1,2,3,4,5,6,7,8} рассмотрим отношение «х£у». Его диаграмма имеет вид.

 

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

в) Дано множество А = {1,2,3,5,6,10,30}. Отношение «быть делителем». У покрывает х, если у делится на х. Диаграмма имеет вид:

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

1.  Сформулировать определение бинарного отношения.

2.  Описать операции, выполняемые с бинарными отношениями.

3.  На множестве прямых на плоскости рассмотрим отношения: а) параллельность прямых,

б) перпендикулярность прямых. Определить будут ли эти отношения отношениями эквивалентности.

4.  Дано множество: люди, живущие в одной стране. Задать какое либо отношение эквивалентности и разбить данное множество на классы эквивалентности.

5.  К какому типу отношения порядка относятся следующие отношения: схема организации подчинения в учреждениях.

ЛЕКЦИЯ 16

ТЕМА: СООТВЕТСТВИЯ И ОТОБРАЖЕНИЯ

ПЛАН:

Соответствие Функция Отображение n –местная функция Обратная функция Свойства отображений

Главная

Соответствие

1.1. Основные понятия

Определение: Соответствием называется какое – либо правило, с помощью которого элементу а из множества А ставится в соответствие элемент b из множества В.

Таким образом, соответствие есть множество G пар (a; b) , где и .

Множество значений а называется областью определения, а множество значений b называется областью значений соответствия G.

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

Если область определения строгое подмножество множества А, то соответствие называется частично определенным.

Примеры:

а). Соответствие х ≤ у, где . Область определения данного соответствия , значит, соответствие всюду определенное.

б). Соответствие , где . Область определения данного соответствия х≥3, значит, соответствие частично определенное.

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

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

Множество всех , которым соответствуют b, называются прообразами b в А при данном соответствии.

Для соответствия между множеством учеников класса и множеством кружков образами являются кружки, а прообразами – ученики.

Виды соответствий

Если образом элемента а из области определения является единственный элемент b из области значений, то такое соответствие называется функциональным.

Примеры:

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

б). , область определения и область значений – действительные числа, удовлетворяющие данному равенству. Но для всех х ≠ 0 из области определения соответствуют по два образа. Значит, это соответствие не является функциональным.

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

Примеры:

а). у = кх + b , где область определения и область значений – действительные числа, взаимнооднозначное соответствие, т. к. каждому х соответствует единственный у и наоборот.

б). у = х2 , где область определения – действительные числа, а область значений - неотрицательные числа. Не является взаимнооднозначным соответствием, т. к. любому положительному образу соответствует по два прообраза.

Заметим, что взаимнооднозначное соответствие является в свою очередь функциональным.

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

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

б). - круг, на границе которого отмечены точки А, В, С. Область определения – числовой отрезок [2; 4], область значений - числовой отрезок [1; 3].

Дуга окружности АВС – является функциональным соответствием между [2; 4] и [1; 3]- каждому прообразу х соответствует единственный образ у.

Дуга окружности ВС – это взаимнооднозначное соответствие, т. к. каждому прообразу х соответствует единственный образ у и наоборот.

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

в). Позиция фигуры на шахматной доске - это взаимнооднозначное соответствие, т. к. каждому прообразу – шахматной фигуре соответствует единственная клетка – образ и наоборот.

Функция

Функцией называется функциональное соответствие между множествами А и В, и обозначается f, или f: A → В, или f(a) = b. Причем, а называется аргументом функции, а b – значением функции.

Определение функции можно сформулировать, используя понятие бинарного отношения:

Бинарное отношение f называется функцией, если из и следует, что y = z.

1. 4. Отображение

Всюду определенная функция f(a) = b называется отображением А в В.

Следовательно, область определения такой функции D(f) = A, а область значений E(f) B.

Если область значений E(f) = B, то такое отображение называют отображением А на В.

Если f(a) состоит из единственного элемента, то функция называется постоянной или константой.

Отображение А→ А (А на А) называется преобразованием множества А.

Примеры:

а). f(x) = 2x, где , есть отображение N в N, т. к. область значений E(f) не все натуральные числа, т. е. .