Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Теория отображений и функций

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

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

Декартовым произведением двух множеств А и В является новое множество С, элементами которого являются все упорядоченные пары {а, Ь) такие, что первый элемент в паре принадлежит множеству А, второй элемент в паре принадлежит множеству В:

С = Ах В = {(a, b) / а е А, b е В}. (1.10)

Тогда мы говорим, что множество А отображается в множество В и элемент а отображается в элемент Ь. Обратите внимание, отображение не всегда взаимно однозначно!

Порядок в паре очень важен, в общем виде Ах В ф В х А. Декартово произведение не обладает свойством коммутативности.

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

Подмножество Fдекартова произведения ХхУназывается функцией, если для каждого элемента х е X найдется не более одного элемента у е Y (или существует единственный элементу, 3!у <е Y) такого, что (х, у) е F(x, у), т.е. выполняется свойство однозначности полученного результата.

Множество А1 называется областью определения функции F, т.е. dom/7, а множество Yназывается областью значений функции F.

Если элемент г ? dom/7, то говорят, что функция ^не определена на г. Таким образом, функции могут быть как полностью определенными на множестве X, так и частично определенными. Точно так же область значений функции может не совпадать с множеством Y, а быть его подмножеством.

Если область определения функции F из X в Y совпадает с X, то пишут F:X^> Y.

Например, тождественная функция U отображает множество X само в себя, причем U: X —» X для любого х е X. А функция-константа С, полностью определенная на X, переводит все элементы множества X в один-единственный элемент се Y ,С: X —» с.

В других разделах математики для функций обычно вместо записи (х, у) <е F используюту = F(x).

Функция называется F: X —> Yинъективной, или инъекцией (вложением), если она отображает разные элементы Xв разные элементы множества Y, т.е. для любого элемента х, принадлежащего X, и любого элемента z, принадлежащего X, неравных между собой, следует, что F(x) не равно F(z):

Ух е X и Mz 6 Х,х ф zF(x) ф F(z). (1.11)

Функция F:X^> Yназывается сюръективной, или сюръекцией (наложением), если множество ее значений есть все множество Y, т.е. для любого элемента у, принадлежащего множеству Л1, найдется элемент* из множества Л1 такой, что у = F(x):

Уу eY, EbceX—> у = F(x). (1.12)

Функция F: X —> Y называется биекцией или взаимно однозначным соответствием, если она одновременно является инъекцией и сюръекцией (вложением и наложением).

Любая функция F: X —> Yпредставляет собой подмножество декартова произведения множеств Хи Y. Поэтому мы можем построить подмножество обратного декартова произведения Y х X и определить обратную функцию F~]: F—> X.

Функция Fсостоит из пар вида (а, Ь), где b = F(a). Если функция обратима, то она состоит из пар (Ь, а), где а = /г_|(^)-3начит, обратимая функция должна удовлетворять условию: если F(a) = b, то F~) = а.

Теорема 1.3. Теорема о существовании обратной функции

Если F— биекция, то существует обратная функция F~l, для которой F~y) =х тогда и только тогда, когда F(x) =у.

Частным случаем функции является операция О. В этом случае область значения X и область определения ^совпадают, т.е. если задано множество М, то операция О есть подмножество декартова произведения М х М, причем для любого элемента х е М существует единственный у е М такой, что(х, у) е О(М):

О с М х М, х е М, 3!у е М, (*, у) е О(М). (1.13)

Теорема 1.4. Принцип Дирихле

Flyernь F: Л —» В — функция, отображающая конечное множество Л в конечное множество В. Тогда если Л > В, то по крайней мере одно значение F встретится более одного раза.

Если Л > кВ для некоего натурального к, то одно из значений функции F повторится по крайней мере k + 1 раз.

Задачи

Задача 1.26. Построить обратную функцию для Р:Х^> У, у = 4х + 5. Решение.

Выразим алгебраически х через у и получим обратную функцию

х = Р~у) =

I

(У ~ 5).

Задача 1.27. Построить на множестве М = {а, Ь, с, с1} операцию, сюръекцию, инъекцию и биекцию максимальной мощности.

Решение.

Операция означает, что множество X совпадает с множеством У, для получения максимальной мощности они же равны множеству М. При задании операции необходимо обеспечить свойство однозначности результата, например Р{ = {(а, Ь), (Ь, Ь), (с, с1), (с!, с/)}.

При построение инъекции необходимо учитывать, что различным х соответствуют различающиеся у, например У2 = {(а, Ь), (Ь, с), (с, с1), (с1, а)}. Для построения сюръекции нужно использовать все элементы множества У, Р3 = {{а, а), (Ь, с1), (с, с), (с1, Ь)}. Обе эти функции являются как сюръекциями, так и инъекциями, следовательно, они — биекции. Мощность во всех случаях равна четырем.

Сами решения могут быть и другие, но максимальная мощность вычисляется однозначно.

Задача 1.28. В учебной группе 15 студентов. Показать, что по крайней мере у двоих день рождения в одном и том же месяце.

Решение.

Положим, что множество Л — множество студентов, а множество В — множество 12 месяцев. Рассмотрим функцию Р: Л —» В, которая каждому студенту сопоставляет месяц рождения. Так как А > В, то согласно принципу Дирихле функция должна иметь повторяющиеся значения, т.е. найдутся два человека, родившиеся в одном и том же месяце.

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

Решение.

Положим, х — один из шести людей, множество А — множество оставшихся пяти человек в группе и множество В = {0, 1}.

Определим функцию /т Д —> В следующим образом:

/ ч ГО, если а не знаком с х,

F(а) = <.

[1, если а знаком с х.

Поскольку 5 = А > 2В, то найдется три человека, которые либо знакомы с х, либо все трое его не знают.

Задача 1.30. Дано множество натуральных чисел. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве.

Задача 1.31. Дано множество четных натуральных чисел. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве.

Задача 1.32. На множестве натуральных чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = аь
  • б) а ОЬ = а + Ь
  • в) а Ob-а- Ъ
  • г) а ОЬ = а ? Ь.

Задача 1.33. На множестве натуральных чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = а / Ь;
  • б) а ОЬ = а2 + Ь2
  • в) a Ob = NOD(a, b);
  • г) а Ob-а1- Ь2
  • д) а ОЬ = -2(а2 + 2Ь).

Задача 1.34. На множестве рациональных чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = аь
  • б) а ОЬ = а + Ь
  • в) а ОЬ = а - Ь;
  • г) а ОЬ = а ? Ь.

Задача 1.35. На множестве рациональных чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = а / Ь
  • б) а ОЬ = а2 + Ь2
  • в) a Ob = NOD(a, Ь)
  • г) aOb- MOD(a, Ь)
  • д) а ОЬ = -2(о2 + 2Ь).

Задача 1.36. На множестве целых чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = а / Ь;
  • б) а ОЬ = а2 + Ь2
  • в) а ОЬ = N00(0, Ь)
  • г) а ОЬ-а1- Ь2
  • д) а ОЬ = -2(а2 + 2Ь).

Задача 1.37. На множестве действительных чисел задана операция О. Какой может быть эта операция?

  • а) аОЬ- аь;
  • б) а ОЬ = а + Ь
  • в) а ОЬ = а - Ь;
  • г) аОЬ-а-Ь.

Задача 1.38. На множестве действительных чисел задана операция О. Какой может быть эта операция?

  • а) а ОЬ = а / Ь
  • б) а ОЬ = а2 + Ь2
  • в) аОЬ- ИОО(а, Ь)
  • г) аОЬ - МОО(а, Ь)
  • д) а ОЬ = -2(о2 + 2Ь).
  • 1.4. Бинарные отношения и их свойства

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

Бинарным отношением Т(М) на множестве М называется подмножество М2 = М х М, Т(М) с А/2. Формальная запись бинарного отношения выглядит как

Т(М) = {(х,у)/(х,у) еГсМх М). (1.14)

Понятие «бинарное отношение» является более общим понятием, чем функция. Каждая функция представляет собой бинарное отношение, но не каждое бинарное отношение есть функция.

Мы уже сталкивались с понятием отношения при рассмотрении с (включение) и = (равенство) между множествами. Также неоднократно вами использовались отношения =, Ф, <, >, <, >, заданные на множестве чисел — как натуральных, так и целых, рациональных, вещественных и т.д.

Общепринятые бинарные отношения, заданные на множестве М:

• обратное отношение

R~' = {(х, у) / (у, х) е R}- (1.15)

• дополнительное отношение

R = {(х, у) / (х, у) г R); (1.16)

• тождественное отношение

и = {(х,х) / х Е М}; (1.17)

• универсальное отношение

I = {(х, у) / X Е М, у Е М}. (1-18)

Способы представления бинарных отношений: перечисление, графическое представление, матричное представление.

Бинарные отношения R можно задать в виде перечисления, как любое множество пар. При графическом представлении каждый элемент л: и у множества М представляется вершиной, а пара (х, у) представляется дугой из х в у. Матричным способом бинарные отношения задаются с помощью матрицы смежности. Такой способ наиболее удобен при решении задач с помощью компьютера. Матрица смежности S представляет собой квадратную матрицу тх т, где т — мощность множества М, и каждый ее элемент S(x, у) равен единице, если пара (х, у) принадлежит Т(М), и равен нулю в противном случае.

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

Бинарное отношение Т(М) называется рефлексивным тогда и только тогда, когда для каждого элемента х е М пара (х, х) принадлежит этому бинарному отношению Т(М), т.е. Vx е М,3(х, х) <е Т(М).

Классическим определением этого свойства является следующее утверждение: из того, что элемент х принадлежит множеству М, следует, что пара (х, х) принадлежит бинарному отношению Т(М), заданному на этом множестве, т.е. Vx е М -» (х, х) е Т(М).

Прямо противоположное свойство бинарных отношений называется иррефлексивностью. Бинарное отношение Т(М) называется иррефлексивным тогда и только тогда, когда для каждого элемента х из множества М пара (х, х) не принадлежит этому бинарному отношению, т.е. Vx е М —> (х, х) g Т(М).

Если бинарное отношение Т(М) не обладает ни свойством рефлексивности, ни свойством иррефлексивности, то оно является нерефлексивным.

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

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

Бинарное отношение Т(М) называется симметричным тогда и только тогда, когда для каждой пары различных элементов (х, у), принадлежащей бинарному отношению Т(М), обратная пара (у, х) также принадлежит этому бинарному отношению, т.е. /(х, у) є Т(М), 3(у, х) є Т(М). Свойство симметричности мы определяем только для множеств, содержащих хотя бы два различных элемента, и непустых бинарных отношений.

Классическим определением свойства симметричности является следующее утверждение: из того, что пара (х, у) принадлежит Т(М), следует, что обратная пара (у, х) также принадлежит Т(М), т.е. /(х, у) є Т(М) —> (у, х) є Т(М). В этом случае еслих = у, то свойство симметричности плавно переходит в рефлексивность.

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

Классическим определением антисимметричности можно считать следующее [2]. Из того, что в антисимметричном бинарном отношении Т(М) для любой пары (х, у) обратная пара (у, х) также принадлежит ДМ), следует, чтох = у, т.е. ((х, у) є Т(М), (у, х) є Т(М)) —> х = у.

Если бинарное отношение ДМ) не обладает ни свойством симметричности, ни свойством антисимметричности, то оно является несимметричным.

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

Свойство транзитивности определяется на трех различных элементах х, у и ? множества М. Бинарное отношение ДМ) называется транзитивным тогда и только тогда, когда для каждых двух пар различных элементов (х, .у) и (у, I), принадлежащих бинарному отношению Т(М), пара (х, также принадлежит этому бинарному отношению, т.е. /(х, у) е Т(М), /(у, I) е Т(М),3(х, I) е Т(М). Таким образом, между элементами х г существует транзитивное замыкание («транзит»), которое «спрямляет» путь длины два (х, у) и (у, ^).

Классическое определение свойства транзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) также принадлежит этому бинарному отношению, т.е. ((х, у) е Т(М), (у, I) е Т(М)) -э (х, I) е Т(М).

Бинарное отношение Т(М) называется интранзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у, ?), принадлежащих бинарному отношению Т(М), пара (х, $ не принадлежит этому бинарному отношению, т.е. /(х, у) е Т(М), /(у, I) е Т(М), (х, I) ? Т(М). Таким образом, в интранзитивном бинарном отношении ни один имеющийся путь длины два не обладает транзитивным замыканием!

Классическое определение свойства интранзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) не принадлежит этому бинарному отношению, т.е. ((х, у) е Т(М), (у, I) е Т(М)) -э (х, I) ? Т(М).

Если бинарное отношение Т(М) не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным.

Задачи

Задача 1.39. На множестве М = {а, Ь, с, ^/, е} задано бинарное отношение Т(М) = {(а, а), (а, Ь), (Ь, с), (с, с!), (с], (1), (с/, е)}. Построить отношение, обратное к Г, дополнительное к Г, тождественное бинарное отношение и и универсальное бинарное отношение I.

Решение.

Для решения этих задач нам нужны только определения.

По определению на множестве М- {а, Ь, с, (1, е} обратное к Т(М) бинарное отношение должно содержать все обратные пары тождественного бинарного отношения Т~х = {(а, Ь), (Ь, а), (с, Ь), (с1, с), (с1, <1),

, с!)}.

По определению на множестве М= {а, Ь, с, ^/, е} дополнительное к Т(М) бинарное отношение должно содержать все пары из декартова произведения Л/2, которые не принадлежат Т(М), т.е. {{а, с), (а, сі),, е), (Ь, я), (Ь, Ь), (Ь, сі), (Ь, е), (с, а), (с, Ь), (с, с), (с, е), (с/, я), (сі, Ь), (сі, с), (с, я), (е, А), (е, с), (е, сГ), (е, е)}.

По определению на множестве Л/ = {я, Ь, с, сі, е} тождественное бинарное отношение и = {(я, я), (Ь, 6), (с, с), (сі, ^/), (е, е)}.

По определению на множестве М = {я, 6, с, сі, е} универсальное бинарное отношение содержит все пары из декартова произведения Л/2, т.е. / = {(я, я), (я, Ь), (я, с), (я, с/), (я, с), (А, я), (А, А), (А, с), (Ь, (I), (А, с), (с, я), (с, Л), (с, с), (с, АО, (с, с), (а?, я), (с/, А), (с/, с), (с/, аО, (

Задача 1.40. На множестве М натуральных чисел от 1 до 5 построить бинарное отношение Я = {(я, Ь) / тос1(я, Ь) = 0}, где тосі — остаток от деления я на Ь.

Решение.

В соответствии с заданием на множестве натуральных чисел М строим такие пары (я, Ь), где я делится на Ь без остатка, т.е. шос1(я, Ь) = 0. Получаем /? = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3,1), (4,1), (5,1), (4, 2)}.

Задача 1.41. Построить графическое и матричное представление для Т(М) = {(я, я), (я, Ь), (Ь, с), (с, аО, (сі, сі), (сі, є)).

Решение.

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

а

ь

с

(1

е

а

і

1

0

0

0

ь

0

0

1

0

0

С

0

0

0

1

0

сі

0

0

0

1

1

е

0

0

0

0

0

Графическое (а) и матричное (б) представление множества

Рис. 1.3. Графическое (а) и матричное (б) представление множества

Задача 1.42. На множестве М- {я, Ь, с, (1, е) заданы бинарные отношения ТХ(М) = {(я, я), (я, Ь), (Ь, Ь), (Ь, с), (с, с), (с, сГ), (с1, сГ), (с1, е), (е, е)} и Т2(М) = {(я, Ь), (Ь, с), (с, с1), (с1, с), (с!, е)). Определить, какое из них является рефлексивным.

Решение.

Бинарное отношение ТХ(М) = {(я, я), (я, Ь), (Ь, Ь), (Ь, с), (с, с), (с, с1), (с1, сГ), (с1, е), (е, е)) является рефлексивным, так как для каждого элемента множества М содержит все пары (я, я), (Ь, Ь), (с, с), (с/, ?/), (е, е). Бинарное отношение Т2(М) = {(я, Ь), (Ь, с), (с, сГ), (^/, с), (?/, е)} является иррефлексивным, так как не содержит ни одной пары вида (х, х).

Задача 1.43. На множестве М= {я, Ь, с, (1, е} заданы бинарные отношения Ту = {(я, я), (я, Ь), (Ь, я), (с, с1), (с/, с), (е, с), (с, е)}, Т2 = {(я, я), (а, Ь), (с, с1), (е, с), (с, Ь), , е)} и Т3 = {(я, я), (я, Ь), , я), (с, с/), (е, с), (с, я)}. Определить, являются ли они симметричными.

Решение.

Бинарное отношение Ту = {(а, а), (а, Ь), (Ь, я), (с, йО, (б/, с), (е, с), (с, е)} является симметричным, Т2 = {{а, а), (я, Ь), (с, с1), (е, с), (с, 6), (Ь, е)} является антисимметричным, Т3 = {(я, я), (я, /?), (Ь, я), (с, йО, (с, с), (с, я)} — несимметричным. Обратите внимание: петля (я, я) никак не влияет на симметричность и антисимметричность.

Задача 1.44. На множестве М = {я, Ь, с, с1, с} заданы бинарные отношения Ту = {(я, я), (я, Ь), (я, с), (6, с), (с, с), (с, с)}, Т2 = {(я, я), (я, Ь), (6, с), (с, 0, (6, *0} и Т’з = {(я, я), (я, 6), (6, с), (^/, с), (я, с), (с, сТ)}. Определить, какие из них транзитивны.

Решение.

Бинарное отношение Ту = {(я, я), (я, Ь), (я, с), (6, с), (с, с), (с, с)} является транзитивным, Т2 = {(я, я), (я, 6), (6, с), (с, б/), (6, с)} является интранзитивным, Т3 = {(я, я), (я, 6), (6, с), (с1, с), (я, с), (с, с/)} — нетранзитивным.

Задача 1.45. На множестве Му = {я, Ь, с, ^/, с} построить бинарное отношение /? с заданными свойствами: нерефлексивности, антисимметричности и нетранзитивности.

Решение.

Правильных решений этой задачи целое множество! Построим одно из них. В нашем бинарном отношении на некоторых вершинах, но не на всех, должны быть петли; не должно быть ни одной обратной дуги; должны быть хотя бы два пути длины 2, из них хотя бы один не иметь транзитивного замыкания. Таким образом, получаем Я = {(я, я), (Ь, Ь), (я, Ь), (Ь, с), (с, с1), (с1, е), (я, с), (с, е)}.

Задача 1.46. Определить свойства бинарного отношения Т, заданного на множестве М2 = {я, Ь, с, ?/, е}, представленного ранее на рис. 1.3.

Решение.

В данном бинарном отношении на двух вершинах есть петли, на трех петель нет, следовательно, бинарное отношение нерефлексивно. Нет ни одной обратной дуги, следовательно, бинарное отношение антисимметрично. Бинарное отношение обладает несколькими путями длины два, но ни один из них не обладает транзитивным замыканием — Т интранзитивно.

Задача 1.47. На множестве натуральных чисел задано отношение тождества. Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

Задача 1.48. На множестве натуральных чисел задано универсальное отношение. Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

Задача 1.49. На множестве целых чисел задано тождество. Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

Задача 1.50. На множестве М = {а, b, с, d, е} задано бинарное отношение Т(М) = {(а, а), (а, b), (b, b), (b, с), (с, с), (с, d), (d, е)}. Построить бинарное отношение, обратное к данному.

Задача 1.51. На множестве М = {a, b, с, d, е} задано бинарное отношение Т(М) = {(a, a), (a, b), (b, b), (b, с), (с, с), (с, d), (d, е), (е, а)}. Построить бинарное отношение, дополнительное к данному.

Задача 1.52. Построить бинарное отношение R(M) и определить его свойства. А/ ={1,2, ..., 8}, R = {(a, b) / res(Z>, а) = 0}, где функция res — остаток от деления.

Задача 1.53. Построить бинарное отношение R и определить его свойства. М— {1,2,..., 8}, R = {(a, b) / res(b, а) = 1}, где функция res — остаток от деления.

Задача 1.54. Построить бинарное отношение R(M) и определить его свойства. М={ 1, 2,..., 8}, R = {(a, b) / res(a+ 1,6) = 0}, где функция res — остаток от деления.

Задача 1.55. Определить свойства бинарного отношения Т, заданного на множестве М2 - {a, b, с, d, e,f} (рис. 1.4).

Задача 1.56. Определить свойства бинарного отношения Г, заданного на множестве М2 = {а, Ь, с, ?/, с,/} (рис. 1.5).

Задача 1.57. Определить свойства бинарного отношения Г, заданного на множестве М2 = {я, Ь, с, ?/, с,/} (рис. 1.6).

 
<<   СОДЕРЖАНИЕ   >>