Отношения. Отображения. Соответствия

(лек. 2 час + прак. занят 2 час + лаб. 2 час. + самос. 2 час)

Одним из важных понятий теории множеств является понятие декартова (прямого) произведения множеств.

Декартовым (прямым) произведением M = M₁ M₂ …M_n множеств M_i (i = 1…n) называется множество, элементами которого являются кортежи длиной n такие, что каждая j-ая компонента есть элемент множества M_j.

Формально: M = {‹x₁, x₂,...x_n› x_j  M_j, j = 1,…,n}

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

Последовательность длины п, члены которой суть а₁, .... а_n, будем обозначать через {а₁, .... а_n}. Последовательность {а₁, а₂} длины два будем называть упорядоченной парой. Декартово (прямое) произведение множеств А и В определяется как множество всевозможных пар {а, b}, где , т.е.

AB {<a,b>|aA&bB}

Таким образом, декартовым произведением множеств М_a и М_ь, называется множество М вида .

Угловыми скобками < > обозначается последовательность, т. е. множество, в котором зафиксирован порядок элементов, т.е кортеж.

Кортежем длины n, составленным из элементов множеств X₁, X₂, …, X_n, называется конечная последовательность .

Если отношение устанавливается между двумя множествами, то Прямым (декартовым) произведением множеств А и В, обозначаемым АВ, называется множество упорядоченных пар, такое, что первая координата каждой пары — элемент А, а вторая координата — элемент В, т.е. АВ = {<a,b>| аА и bВ}.

В целях наглядного представления декартовых произведений удобно использовать язык геометрии. Для этого множества X, Y представляются осями координат. Элементы хX, уY — соответственно абсциссами и ординатами. Само произведение ХY — точками плоскости ХОY. В качестве примера на рис. 1 показано декартово произведение множеств Х = {1, 2, 3}, Y = {1, 2}.

рис. 4.1

Бинарное отношение RXY может отражать разный смысл.

Пример. Значениями множества Х можно закодировать названия книжных издательств, а элементами множества Y — всех фирм некоторого региона, которые занимаются продажей этих книг. Тогда отношению RXY можно придать смысл множества заключенных договоров между издательствами и торгующими фирмами. Пусть Х={1, 2, 3}, Y={1, 2} рассматриваются как три издательства и два магазина, продающие книги. Тогда отношение R = {<1,1>, <2,2>, <3,2>} означает, что издательство 1 заключило договор с магазином 1, издательство 2 — с магазином 2, издательство 3 — с этим же магазином 2.

Пример. Пусть А = {1,2}, В = {а,b,с}.

Тогда АВ = {<1,а>, <1,b>, <1,с>, <2,а>, <2,b>, <2,с>}. Декартово произведение АВ = {<а,1>, <b,2>, <с,1>, <а,2>, <b,2>, <с,2>}. Декартово произведение АА = {<1,1>, <1,2>, <2,1>, <2,2>} называется декартовым квадратом множества А.

Пример. Если множество А включает т различных элементов, а множество В — п элементов, то произведения множеств АВ и ВА имеет т п элементов. Пусть А = {1}, а В ={1,2,3}. Тогда АВ ={< 1, 1 >, <1,2>, <1, 3 >}. Если А = 0, а В = {1, 2, 3}. Тогда АВ=ВА=0.

Пример 2. Всё множество координат всех клеток шахматной доски можно записать декартовым произведением вида {a,b,c,d,e,f,g,h} {1,2,3,4,5,6,7,8} = {‹a,1›, ..., ‹a,b›, ‹b,1›, ..., ‹b,b›, ..., ‹h,8› }

Любое непустое подмножество R декартова произведения ХY множеств X, Y называется бинарным отношением между Х и Y. Записывается это так: RХY, или так: хRу, или так: <х,у>R. Слово «бинарный» происходит от английского binary, что в переводе означает «двойной». Любое непустое подмножество ХY является бинарным отношением на X. В частности, множество ХX называется универсальным отношением на X.

Пусть А и В два конечных множества. Напомним, что декартово произведение множеств А и В это множество АВ, состоящее из всех упорядоченных пар <а, b>, где а A, b B.

Бинарным отношением между элементами множеств А и В называется любое подмножество R. множества АВ,т.е. R АВ.

Под бинарным отношением (с левой областью А и правой областью В) подразумевается произвольное подмножество . Если А = В, то будем говорить о бинарном отношении на множестве А. Вместо часто пишут a R b.

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

Бинарное отношение R на множестве Х обладает следующими свойствами:

(а) рефлексивно, если хRх для каждого ,

Отношение R на множестве Х является рефлексивным, если оно выполняется между самим элементом, т.е. хRх. Пример, в отношениях «х имеет общий признак с у», «х похож на у» имеет место хRх, так как элемент х похож на самого себя.

- прямая x параллельна прямой y в плоскости z - хRх

- студент x ровесник студенту y – каждый студент сам себе ровесник хRх.

(а1) иррефлексивно, если хRх не имеет смысла

- отношение строго порядка x <x на множестве действительных чисел – оно всегда ложно.

(а2) антирефлексивно, если хRх для каждого ,

Отношение R на множестве Х является антирефлексивным, если хRх не выполняется ни для одного хX. Например, в отношениях «брат х старше брата у», «операция х выполняется раньше операции у», хRх не выполняется, так как брат х не может быть старше себя, а операция х начаться раньше самой себя.

(б) транзитивно, если произвольных ,

Отношение R на множестве Х является транзитивным, если для всех из соотношений хRу, уRz следует хRz. Например, в отношении «операция х предшествует операции y, а операция у предшествует операции z из хRу и уRz следует хRz.

- город x связан с городом y шоссейной дорогой – между городом y и z

- студент x ровесник студенту y

- треугольник x подобен треугольнику y

- действительное число x больше действительного числа y

(в) симметрично, если для произвольных ,

Отношение R на множестве Х является симметричным, если для всех х,уХ из хRу следует уRх. Например, в отношениях «х похож на у», «операция х несовместима с операцией у» имеет место как хRу, так и уRх. Действительно, если х похож на у, то у похож на х, если операция х несовместима с у, то операция у несовместима с х.

- прямая х перпендикулярна у (не рефлексивно).

- студент х приходится соседом у (не рефлексивно) .

(в1) антисимметрично, если для произвольных .

Отношение R на множестве Х является антисиммитричным, если соотношения хRу и уRх выполняются тогда и только тогда, когда х = у для всех . Например, в отношении «операция х является частью операции у» имеет место хRу и уRх только тогда, когда х = у.

- бинарное отношение включения множеств

(в2) асимметрично, если для произвольных .

Отношение R на множестве Х является асимметричным, если из двух соотношений хRу, уRх одно не выполнено для всех . Например, в отношениях «х подчиняется у», «операция х выполнена раньше операции у» имеет место хRу, но не выполняется уRх.

Помимо этих свойств на практике используются еще следующие:

- отношением эквивалентности,

- отношение толерантности

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

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

Отношение эквивалентности – это произвольное бинарное отношение R на множестве Х, обладающее свойствами:

- рефлексивности,

- транзитивности

- симметричности.

По смыслу отношение эквивалентности определяется как «элементы х и у одинаковы», «элементы х и у взаимозаменяемы».

В этом отношении каждый элемент эквивалентен самому себе (рефлексивность). Если элемент х эквивалентен элементу у, то и элемент у эквивалентен элементу х (симметричность). Если элемент х эквивалентен элементу у, а элемент у эквивалентен элементу z, то элемент х эквивалентен элементу z (транзитивность).

Лемма 1. Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности.

Доказательство. Пусть , положимaRb ↔ a и b лежат в одном классе разбиения. Покажем, что полученное бинарное отношение является отношением эквивалентности. Для этого необходимо доказать, что оно рефлексивно, симметрично и транзитивно. Действительно. Поскольку a лежит в некотором классе разбиения, то aRa, т.е. оно рефлексивно.

Пусть K – некоторый класс разбиения и тогда ит.еaRb → bRa, Симметричность доказана.

Из aRb → bRc следует , СледовательноaRc, ч.т.д.

Лемма 2. Всякое отношение эквивалентности R, определенное на множестве А задает разбиение на классы.

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

Пример 1. Отношение эквивалентности на множестве чисел является отношение равенства (=). Любое число а из множества действительных чисел равно самому себе a=a (рефлексивность). Если а=b, то b=а (симметричность). Если а=b, а b=с, то а=с (транзитивность).

Пример 2. Отношения параллельности прямых в эвклидовой плоскости.

Пример 3. Отношения проживания в одном доме жителей города.

Отношение эквивалентности разбивает любое множество на непересекающиеся подмножества (классы эквивалентности). В примере 3 все жители города разбиваются на жителей, живущих в одних и тех же домах. В результате получим столько классов эквивалентности, сколько домов, в которых проживают люди. Таким образом, если М_i, — i-й класс iI, а М — множество жителей, то _iIM_i =M, M_iM_j= для всех i, j  I ,где I — множество классов.

Примеры на эквивалентность

1. R - отношение равенства (=).

Отношение равенства x = y является эквивалентностью на любом множестве A, так как оно

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

2. R - отношение подобия треугольников.

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

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

3. R - отношение равномощности.

На любом множестве B(U) отношение равномощности |A| = |B| является отношением эквивалентности. Для любых множеств A, B, C выполняются следующие свойства:

рефлексивно: (A ~ A поскольку id_A : A ↔ A),

симметрично: если A ~ B, то B ~ A (так как из f: A ↔ B следует f^-1: B ↔ A),

транзитивно: если A ~ B и B ~ C, то A ~ C (так как из f: A ↔ B, g: B ↔ C следует f◦g: A ↔ C).

4. R - отношение принадлежности.

Отношение принадлежности к одной студенческой группе на множестве студентов МГСУ является отношением эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

5. R - отношение вычисление одной и той же функции.

Пусть M – множество программ, вычисляющих одну и ту же функцию. Отношение E = {(x,y)| программы x и y вычисляют одну и ту же функцию} на множестве M является отношением эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

Отношение толерантности

Отношение R на множестве Х называется отношением толерантности, если оно

- рефлексивно

- симметрично.

Пример. Отношение «игрок х играет сам с собой в шахматы и с другом у» есть отношение толерантности, так как хRх, а хRу влечет уRх.

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

А) Нестрогий порядок

Отношение R на множестве Х называется отношением нестрого порядка, если оно

- рефлексивно,

- антисимметрично

- транзитивно.

Отношения ≤, ≥ на множестве чисел Х являются отношениями нестрогого порядка, так как любое число хХ равно самому себе (рефлексивность).

Для любой пары чисел х,уХ при а≤b не выполняется b≤a, а при а≥b не выполняется b≥a (антисимметричность).

Для любой тройки чисел х,у,zX, если а≤b и b≤с, то а≤с или, если а ≥b, b≥с, то а ≥с (транзитивность).

Б) Отношение частичной упорядоченности

Отношение частичной упорядоченности - это произвольное бинарное отношение, обладающее свойствами:

- рефлексивности,

- транзитивности

- антисимметричности.

Отношение частичной упорядоченности обычно обозначается через « ≤ », а пара <Х, ≤ > называется частично упорядоченным множеством. Будем применять также очевидные обозначения, такие как х ≥ у для у ≤ х, х <. у для и т. д.

Примером частично упорядоченного множества может служить множество целых чисел с отношением делимости, множество целых (или вещественных) чисел с обычным отношением меньше или равно « ≤ », а также множество Р(X) с отношением включения .

В) Отношение строго порядка

Отношение R на множестве Х называется отношением строго порядка, если оно

- антирефлексивно,

- антисимметрично

- транзитивно.

Отношения <, > на множестве чисел Х являются отношениями строгого порядка, так как любое число хX не может быть меньше или больше самого себя (антирефлексивность).

Для любой пары чисел х, уX при х<у не может быть у<х, а при х>у не выполняется у>х (антисимметричность).

Для любой тройки чисел х,у,zX, если х<у, а у< z, то х< z, если х>у, а у> z, то х>z (транзитивность).

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

Если для каждой пары х, уX справедливо отношение строгого или нестрогого порядка, то множество <X, R> называется полностью упорядоченным. В противном случае множество <X, R> называется частично упорядоченным.

Строгий или нестрогий порядок, заданный на полностью упорядоченном множестве <X, R>, называется линейным порядком.

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

Пример 2. Множество букв русского или латинского алфавита линейно упорядочено отношением предшествования, или, что то же, отношением следования.

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

Тернарные отношения

Декартовым произведением XYZ трех множеств X,Y,Z называется множество всех упорядоченных троек <х,у,z>, составленных из элементов этих множеств так, что XYZ = {<х,у,z>| хХ, уY, zZ}. Любое непустое подмножество T декартова произведения XYZ множеств X, Y, Z называется тернарным отношением между X, Y и Z и записывается так: ТXYZ.

Пример. Трехместными отношениями ТXYZ могут быть такие: 1) из х видов сырья у предприятий выпускают z видов продукции; 2) х покупателей покупают отоварен по z ценам; 3) но х бомбардировщикам у ракетно-зенитных комплексов дали залп z ракетами.

n-арные отношения

По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение XYZ трех множеств X,Y,Z и вообще декартово произведение Х₁Х₂...Х_n п множеств Х₁,Х₂, ... ,Х_n.

Декартовым произведением Х₁Х₂...Х_n п множеств Х₁,Х₂, ... ,Х_n называется множество всех упорядоченных п-ок <х₁, х₂,..., x_n>, составленных из элементов этих множеств так, что Х₁Х₂...Х_n = {<х₁, х₂,..., x_n>|x₁X₁, x₂X₂, …, x_nX_n}. Любое непустое подмножество N декартова произведения Х₁Х₂...Х_n п множеств Х₁,Х₂, ... ,Х_n называется n-арным отношением между Х₁,Х₂, ... ,Х_n и записывается так: NХ₁Х₂...Х_n.

В том случае, если M₁ = M₂ =…= M_n, то пишут Mⁿ. Часто Mⁿ называют универсальным отношением. Точка на плоскости может рассматриваться как упорядоченная пара, а в пространстве - упорядоченная тройка. Координатное представление впервые ввел Рене Декарт (1596-1650), поэтому оно и называется «декартово произведение».

Декартовым произведением

множеств М₁, М₂, М₃, . . . , М_п называется множество

.

Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит изп элементов, причем первый элемент принадлежит множеству М₁, второй — множеству М₂,..., п-й элемент — множеству М_n.

Теорема. Для конечных множеств A и B, мощность декартова произведения равна произведению мощностей множеств декартового произведения, т.е. |AB| = |A| |B|

Доказательство. Первый компонент упорядоченной пары можно выбрать |A| способами, второй |B| способами. Всего упорядоченных пар <a_ib_j> будет |A| |B| ч.т.д.

Пример 1. Сколько вариантов окраски квадрантов круга возможно, если допускается пять цветов краски.

Решение:

Кортеж длины 4, каждая компонента которого есть цвет краски, есть элемент декартового произведения. Пусть цвета краски образуют множество M = {к,б,з,с,ф}. Тогда М⁴ = М  М  М  М и М⁴ = 5⁴ = 625.

Отображения

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

По количеству элементов, между которыми определены связи, отношения делятся на унарные (одноместные), бинарные (двухместные), тернарные (трехместные) и n-арные (n-местные). В унарном отношении участвует один элемент. Эти отношения называются свойствами и отождествляются с подмножеством элементов, которые этим свойством обладают. Так, например, в множестве всех положительных чисел отношение или свойство «быть четным» отождествляется с подмножеством чисел 2, 4, 6, ....

В бинарных отношениях участвуют пары элементов множеств, так называемые упорядоченные пары <х₁,у₁>, <х₂,у₂>, х₁, х₂, … Х, у₁, у₂, … Y. Упорядоченность понимается как то, что в записи <х,у> на первом месте всегда стоит х X, а на втором у Y. Иными словами, х предшествует у.

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

Подмножество S декартового произведения называется n-арным соответствиeм элементов множеств M_i.

Формально S M.

Частные случаи.

1. Если n = 2, то говорят о бинарном соответствии S M₁ M₂.

2. Если говорят о подмножестве кортежей универсального отношения Mⁿ, то имеют в виду n-арное отношение r, т.е. R Mⁿ.

3. R M² называют бинарным отношением на множестве M.

4. Однозначное n-арное отношение есть n-местная функция.

Пример. Пусть M = {х₁,х₂,х₃} и R M².

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

{‹x₁,x₁›, ‹x₂,x₁›, ‹x₃,x₁› }

{‹x₁,x₂›, ‹x₂,x₄›, ‹x₃,x₃› }

Замечание. Поскольку S является подмножеством, то можно говорить о нечётких соответствиях, отношениях, функциях.

Функция

В основе всех разделов дискретной математики лежит понятие функции.

ПустьХ — некоторое множество на числовой оси. Говорят, что на этом множестве определена функция f, если каждому числу хХ поставлено в соответствие определенное число у=f(х). При этом множество Х называется областью определения (задания) функции f, а совокупность значений у=f(х) — множество Y — областью ее значений. Для наглядности функцию у=f(х) представляют ее графиком в координатных осях хОу.

На рис. 5, в качестве примера, изображена функция у=|х|. Область определения этой функции — интервал (-∞, ∞). Область значений — интервал (0, ∞).

Переменную х называют аргументом функции, а у — ее значением. Значок f интерпретируется, как правило, преобразования аргумента х в значение у, т.е. представляет собой способ реализации соответствия. Этот способ может быть задан аналитически (формулой), в виде таблицы, графика или специальной вычислительной процедурой. Важно только то, что для каждого значения хХ он должен давать одно и только одно значение у=f(х).

Функция многих переменных у=f(х₁, х₂, …, х_n) вводится аналогично. Пусть задано множество Х₁Х₂...Х_n. Тогда, если любому упорядоченному набору <х₁, х₂,..., x_n>Х₁Х₂...Х_n по определенному правилу f поставлено в соответствие число у=f(х₁, х₂, …, х_n), то говорят, что на множестве Х₁Х₂...Х_n определена функция многих переменных f(х₁, х₂, …, х_n).

Рассматривая вместо числовых множеств Х₁Х₂...Х_n множества любой природы, приходим к самому общему определению функции. Пусть М и N — два произвольных множества.

Если каждому элементу хМ по некоторому правилу поставлен в соответствие один и только один элемент уN, то на множестве М определена функция f, принимающая значения из множества N.

Вместо термина «функция» часто употребляют термин «отображение», понимая под ним отображение одного множества в другое. В данном случае имеем отображения одного множества М в множество N. Записывают это так: f:М→N.

Представление функции в терминах отношений

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

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

Множество М_x образует область определения функции F, множество М_у — область значений функции F. Часто вместо записи используют запись у = F(х); при этом элемент х называют аргументом или переменной, а у — значением функции F.

Пусть X, Y - некоторые множества. Говорят, что задана функция (отображения), действующая из множества X во множество Y, если задан закон или правило f, по которому каждому элементу x из множества X ставится в соответствие единственный элемент y из Y: y = f(x).

Пример. Пусть X = R (все вещественные числа) и Y = [-1; 1]. Рассмотрим функцию y = sin x. Каждому элементу из X поставлен в соответствие элемент из Y: пусть x = р/2, тогда y = sin р/2 = 1.

Множество Y называется множеством значений функции f. Элемент y = f(x) Y называют образом элемента x при отображении f. Элемент x - прообраз элемента y под действием отображения f. Множество X называется множеством прообразов отображения f.

Пример. Для функции y = sin x: x = R - множество прообразов; Y:=[-1; 1] - множество значений функции; y = 1 - образ x = р/2 при данном отображении (y = sin р/2 = 1 ), x = р/2 - прообраз элемента y = 1 при данном отображении.

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

Пример 1.1. На рис. 1.2, а изображено подмножество декартова произведения множеств М_x = {х₁, х₂, х₃, х₄} и М_у = {у₁, у₁, у₃}, не являющееся функцией; на рис. 1.2, б,-являющееся полностью определенной функцией; на рис. 1.2,в — частично определенной функцией.

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

Если множество М_x в определении функции у = F(х) является декартовым произведением множеств М_x1, М_x2, . . . , М_xn, то получаем определение п-местной функции

у = F(х₁, х₂, . . . , х_n).

Две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции и область ее значений задается так же, как и для бинарных отношений. Если область определения д_f = Х и область значений с_f Y, то говорят, что функция f задана на множестве Х со значениями во множестве Y, при этом f отображает множество Х во множество Y. Это отображение обозначается как f: Х Y.

Если f — функция, то вместо пишут y = f(х) и говорят, что y — значение, соответствующее аргументу х, или у — образ элемента х при отображении f. При этом х называют прообразом элемента у.

Назовем f — n-местной функцией из Х в Y, если f: ХY. Тогда записываем y = f(х₁, … х_n) и говорим, что у — значение функции при значении аргументов х₁, … х_n.

Если функция (отображение) f сопоставляет каждому элементу элемент , то будем писать f: ХY (такая функция может трактоваться как отношение с тем свойством, что для каждого существует в R точно одна пара вида <х,y>, ; для наших же целей достаточно интуитивного понятия функции).

Отношение RХY, т.е. множество упорядоченных пар <х,у>, хX, уY называется функцией тогда и только тогда, когда первые элементы этих пар не повторяются.

Пример. Отношение не является функцией, так как оно представлено следующими парами: <1,2>, <1,3>, <2,3>, <2,4>, <3,3>, <3,4>, <4,2>, <4,3>. Примером функции на том же декартовом произведении является отношение <1,2>, <2,4>, <3,4>, <4,3>.

Требование неповторяемости первых элементов упорядоченных пар, представляющих отношение, гарантирует однозначность отображения, т.е. функцию f: ХY.

Функции, функционалы, операторы

В зависимости от того, какой характер имеют множества задания функций Х и множества ее значений Y, выделяют функции числовые (Х и Y — числовые множества), функционалы (множество Х — любой природы, а множество Y — числовое), операторы (множества X, Y — любой природы).

Пример. 1. Числовых функций являются все элементарные функции, например, у = х², у = logх, у = sinх и т.д., а также их суперпозиции.

2. Функционал. Пусть в некотором городе N между двумя пунктами А и В имеется множество дорог X, каждой из которой поставлено в соответствие время tТ передвижения по ней автомобиля. Тогда множество пар <х,t>, хX,tT — функционал от t, определенный на множестве X.

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

Инъекция, сюръекция, биекция

При использовании термина «отображение» различают отображение Х в Y и отображение Х на Y.

В том случае, когда Х отображается на некоторое собственное подмножество Y_сY, — это отображение Х в Y.

В противном случае, т.е. когда Y_с=Y, — это отображение Х на Y. Оно называется сюръекцией.

Если для любых двух различных х₁, и х₂ функции f(x₁) и f(x₂) также различны, такая функция f называется инъективной.

Функция называется биективной или взаимно однозначной, если она съюрсктивна и инъективна.

Пусть f: Х Y. Функция f называется инъективной, если для любых х₁, х₂, y, из у = f(x₁) и у = f(x₂) следует, что x₁ = x₂.

Функция f называется сюръективной, если для любого элементам существует элементтакой, чтоу = f(х).

Функция f называется биективной, если f одновременно сюръективна и инъективна.

Если существует биективная функция f: ХY, то говорят, что f осуществляет взаимно-однозначное соответствие между множествами Х и Y.

Суперпозиция бинарных отношений

Если f: ХY, а g: YZ, то функция F: XZ, определенная для каждого формулойF(х) = g(f(х)), называется композицией (суперпозицией) функции f и g, или сложной функцией.

Обратная функция

Для произвольных ,определим f(А) = {: существует такое , что у = f(х)} f ^-1(В) = {: }.

Если f(А) = Y, то будем говорить о функции из Х на Y. Функция f:Х→Y называется обратимой (взаимно однозначной), если для произвольных

а ≠ b → f(а) ≠ f(b).Пусть задана функция f: Х Y и с_f — множество ее значений. Совокупность всевозможных упорядоченных пар вида <y, f^-1(y)>, _f образует функцию, которая называется обратной функцией для функции f: и обозначается f^-1.

Обратная функция f^-1 ставит в соответствие каждому элементу _f его прообраз f^-1(y), т.е. некоторое множество элементов. Заметим, что для того, чтобы f^-1 являлась функцией, достаточно, чтобы функция f была инъективной.

Классификация отображений

Пусть X и Y - два частично упорядоченных множества.

Отображение ζ множеств X на Y есть изоморфизм (или изоморфное отображение), если оно взаимно однозначно и сохраняет порядок, то есть неравенства х ≤ у и ζ (х) ≤ ζ (у) равносильны.

Обратное отображение ζ ^-1 есть также изоморфизм.

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

Отображение ц называется изотопным, если неравенство х ≤ у влечет ζ (х) ≤ ζ (у). Изоморфное отображение всегда изотонно (но не наоборот!).

Взаимно однозначное отображение ω множества X на Y называется дуальным изоморфизмом, если равносильны неравенства х ≤ у и ζ (х) ≥ ζ (у). Если такое отображение существует, то говорят, что X и Y дуально изоморфны.

Операция

Частным случаем п-местной функции у = F(х₁, х₂, . . . , х_n) является п-местная операция. Под п-местной операцией O_n в множестве М понимается п-местная функция у = F(х₁, х₂, . . . , х_n), у которой области определения аргументов и область значений функции совпадают:М₁ = М₂ = ... = М_n = М_у. Таким образом, п-местная операция по п элементам множества М определяет (п + 1)-й элемент этого же множества.

Алгебраической n-арной (n-местной) операцией на множестве M называется n-местная функция у = f(x₁,x₂,...,x_n), у которой область определения аргументов x_i и область значений функции совпадают (n N).

Пояснение.

1. Тот факт, что алгебраическая операция является частным случаем бинарного однозначного соответствия, отражается в её формальной записи f: Mⁿ M., т.е.:

2. Поскольку алгебраическая операция по n элементам множества M определяет (n+1) элемент этого же множества M, то n-местную алгебраическую операцию можно рассматривать и как (n+1)-арное однозначное отношение на множестве M.

3. Если f: M M, то говорят об унарной (одноместной) алгебраической операции; если f: M² M, то имеют в виду бинарную (двухместную) алгебраическую операцию.

Частично упорядоченные множества

Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка с.

Частичным упорядочением (частичным порядком) в непустом множестве X называется всякое подмножество множества , удовлетворяющее следующим аксиомам:

I. При любом справедливо-рефлексивность отношений.

II. Если и, тоy = x - антисимметричность отношений.

III. Если и, то-транзитивность отношений.

Часто вместо записи пишут x ≤ y или y ≥ x . Иногда вместо знака ≤ могут применять и другие похожие символы например . Тогда аксиомы можно записать в виде:

I. при всех справедливо-рефлексивность отношений.

II. Если x ≤ y и y ≤ x, то y = x - антисимметричность отношений.

III. Если x ≤ y и y ≤ z, то x ≤ z - транзитивность отношений.

Эти соотношения называются неравенствами.

Частично упорядоченное множество – это некоторое множество X вместе с заданным на нем частичным порядком P, то есть пара (X, P).

Минимизации представления множества

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

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

Пусть в пространстве 1 = {М₁, М₂, М₃} задано множество вида

М(М₁, М₂, М₃) = неМ₁неМ₂неМ₃неМ₁неМ₂М₃неМ₁М₂неМ₃ М₁неМ₂неМ₃М₁М₂неМ₃М₁М₂М₃ сложность которого равна 18.

На основании законов идемпотентности, коммутативности и ассоциативности объединения получаем

М(М₁, М₂, М₃) = (неМ₁неМ₂неМ₃неМ₁неМ₂М₃) (неМ₁неМ₂неМ₃М₁неМ₂неМ₃) (неМ₁неМ₂неМ₃М₁неМ₂неМ₃) (М₁неМ₂неМ₃М₁М₂неМ₃) (М₁неМ₂неМ₃М₁М₂М₃)

Используя законы коммутативности пересечения и склеивания, имеем

.

Сложность представления уменьшилась до 10.

Согласно законам коммутативности объединения _и пересечения и закону склеивания получаем Сложность представления уменьшилась до 7.

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

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

Рассмотрим алгебру и определим множества, которые могут быть порождены (образованы) из произвольных подмножествМ₁, М₂,...,М_n, называемых порождающими или образующими пространства 1 с помощью операций .

Множество

i = 1,2, …n,

М, * = < , I = 1, 2,...,п,

в дальнейшем будем называть первичным термом.

Множество вида

_I = 0,1 назовем конституентой.

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

. ,.

Лемма 1.1. Пересечение двух различных конституент пусто.

Действительно, если конституенты иразличны, топо крайней мере для одногоk, k  n. Но тогда , следовательно. .

Лемма 1.2. Объединение всех конституент равно 1.

Представим 1 в виде

и, раскрыв скобки, в правой части равенства получим объединение всех конституент.

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

1. Что такое: декартово произведение множеств; декартова степень некоторого множества А; бинарное отношение, заданное на множестве А?

2. Что такое унарное отношение, приведите примеры.

3. Что такое бинарное отношение, приведите примеры.

4. Назовите основные свойства бинарных отношений.

5. Какое отношение называется рефлексивным, симметричным, антисимметричным, транзитивным?

6. Какое отношение называется отношением эквивалентности?

7. Дайте определение отображения множества А во множество В. Поясните термин «мощность множества».

8. Что такое сюръекция, инъекция, биекция?

9. Дайте определение функции.

10. Чему в математике служат отношения?

11. Как классифицируются отношения в зависимости от числа связей между элементами множества?

12. Дайте определение бинарного отношения.

13. Что представляет собой декартово произведение множеств?

14. Выпишите декартовы произведения множеств А = {а, b}, В = {1, 3}; декартового квадрата А = {1, а}.

15. Сколько элементов включает декартовый квадрат множества A = {1, 2,...,i, ...,n}?

16. Дайте определение бинарного, тернарного и n-арного отношения в терминах множеств.

17. Что понимают под рефлексивными и антирефлексивными отношениями?

18. Как характеризуются симметричные, асимметричные

и антисимметричные отношения?

19. Дайте определение транзитивного отношения.

20. Дайте определение отношения эквивалентности и приведите примеры.

21. Какое отношение называется отношением нестрогого порядка? Является ли отношение ≤ на множестве А = {1, 2, 3} отношением нестрогого порядка?

22. Какое отношение называется отношением строгого порядка?

23. Какое множество называется упорядоченным, полностью упорядоченным?

24. Что такое линейный порядок?

25. Дайте определение функции.

26. Является ли отношение R = {<1,а>, <1,b>, <2,а>}, определенное на декартовом произведении множеств А = {1,2}, B = {а, b}, функцией?

27. Является ли функция f(х) = х² инъективной?

28. Что представляет собой функционал?

Лекция № 5

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

А. Пойа Математика и правдоподобные рассуждения. М.: Наука, 1975 с.