§ 2. Соответствия. Функции. Отображения

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

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

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

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

Соответствием между множествами X и Y называют тройку множеств

q = ( X,Y,Q ) , ,

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

Часто соответствием между множествами Х и Y называют только множество Q , которое является подмножеством декартового произведения , т.е.

Если ( х, у ) , то говорят, что элемент у соответствует элементу х. Геометрически это изображается стрелкой, направленной от х к у.

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

участвующие в сопоставлении.

Если , то соответствие называется всюду ( полностью ) определенным. В противном случае соответствие называется частично определенным.

Множество называется областью значений ( множеством прибытия ) соответствия. Она содержит элементы множества Y , участвующие в сопоставлении.

Если , то соответствие называется сюръективным.

Множество всех элементов , соответствующих элементу , называется образом элемента х в множестве Y при соответствии q (или Q ).

Множество всех элементов , которым соответствует элемент , называется прообразом элемента у в множестве Х при соответствии q ( или Q ).

Пример. Пусть даны два множества : Х = {1, 2, 3} и Y = {e, f, g }.

□ На рис. 1.3 показано соответствие между этими множествами.

Q = , которое является подмножеством прямого произведения

Область определения этого соответствия область значений .

Рис. 1.3

Элемент e – образ элементов 1,2 в множестве Y при соответствии Q;

элементы 1,2 – прообразы элемента e в множестве Х при соответствии Q. Так как не все элементы множества Х входят в область определения, то данное соответствие является частично определенным.

Пример всюду определенного соответствия показан на рис. 1.4

Рис. 1.4

Здесь все элементы множества Х участвуют в сопоставлении.

Пример сюръективного соответствия показан на рис. 1.5

Рис. 1.5

Здесь все элементы множества Y участвуют в сопоставлении. Этот рисунок описывает соответствие

Q = , . ■

Пример. Пусть Х = {1, 2}, Y = {3, 5}. Распределение элементов множества Х по элементам множества Y есть соответствие. Определить все возможные соответствия, их области определения и области значений.

□ Для нахождения соответствий необходимо определить декартово произведение заданных множеств:

Получили множество, состоящее из четырех двухэлементных кортежей. Одним из возможных соответствий может быть соответствие элемента 3 из множества Y элементу 1 из множества Х , т.е.

Тогда мы получим соответствие (тройку множеств)

Областью определения соответствия q₁ является , а

областью значений q₁ является

Как уже говорилось, в качестве соответствия можно взять не тройку множеств q , а множество Q , которое является подмножеством прямого произведения множеств X и Y. В этом случае запись будет короче. Выбирая , мы получим все возможные соответствия и их области определения и области значений :

Q₁₆ = {Ø} , Пр₁Q₁₆ = {Ø} , Пр₂Q₁₆ = {Ø} .

В тех случаях, когда Пр₁Q _I = X , соответствие определено всюду. Если Пр₂Q _I = Y , то соответствие является сюръективным. ■

Соответствие q (или Q) называется функциональным (однозначным ), если образом любого элемента из области определения соответствия является единственный элемент из области значений.

Соответствие q (или Q ) называется взаимно однозначным, если оно всюду определено, сюръективно, функционально, и, кроме того, прообразом любого элемента из области значений является единственный элемент из области определения соответствия.

На рисунках 1.3 и 1.4 показаны функциональные соответствия. При этом соответствие, изображенное на рис. 1.3, является частично определенным функциональным соответствием, а соответствие, показанное на рис. 1.4, является всюду определенным функциональным соответствием.

Соответствие, указанное на рис. 1.5 не является функциональным, т.к. элемент 3 из области определения соответствия имеет два образа f и g из области значений соответствия.

Пример взаимно однозначного соответствия показан на рис. 1.6

Рис. 1.6

Рассмотрим бесконечные множества.

Два множества М₁ и М₂ (и конечные тоже) называются равномощными ( |М₁| = |М₂| ), если между их элементами установлено взаимно однозначное соответствие.

Множество, равномощное N (N – множество натуральных чисел) называется счетным.

Другими словами, множество М является счетным, если все его элементы могут быть занумерованы в бесконечную последовательность а₁, а₂, …, а_п, … так , чтобы при этом каждый элемент получил только один номер п и каждое натуральное число п было бы номером лишь одного элемента множества М.

Отметим, что

1. любое бесконечное подмножество N счетно;

2. объединение конечного числа счетных множеств счетно;

3. объединение счетного множества конечных множеств также счетно.

Множество всех действительных чисел отрезка [0, 1] не является счетным. Действительно, нельзя пронумеровать все действительные числа, находящиеся в отрезке [0, 1], т.к. всегда между двумя числами этого отрезка (как бы близко друг к другу они не находились) найдется число, которое нужно пронумеровать.

Несчетное множество называют континуальным или континуумом. Его мощность несчетна. Иногда мощность несчетного множества называют континуумом.

Функцией f называется функциональное соответствие, т.е.

,

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

Это можно обозначить записью y = f(x). Элемент х – аргумент функции, у – значение функции.

Полностью определенная функция f называется отображением Х в Y и обозначается

В этом случае каждый элемент имеет только один образ y = f(x) из Y.

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

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

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

Так как отображение является функцией, то функцию можно записать в виде

Пример. Рассмотрим соответствие, изображенное на рис. 1.7

Рис. 1.7

□ Соответствие f является функциональным, т.е. функцией. Так как оно всюду определено, то f – отображение. Соответствие не является сюръективным (элемент d не имеет прообраза в множестве Х. Следовательно, соответствие f является отображением множества Х в множество Y , т.е. . ■

Пример. Рассмотрим соответствия :

□ Дадим характеристику свойств соответствий.

A – соответствие f всюду определено: ; не сюръективно,

так как , т.е. ; функционально, т.к.

образом любого элемента является единственный элемент ; является отображением множества R в множество R , т.к. оно всюду определено и функционально; отображение не является инъективным, т.к. существуют элементы , для которых f(x₁) = f(x₂) = у; отображение не является биективным, т.к. оно не является сюръективным и инъективным.

B – соответствие f всюду определено : ; сюръективно,

т.к. ; не функционально, поскольку существует ,

для которого f(x₁) = y₁, f(x₁) = y₂ , f(x₁) = y₃ ; отображением не является.

C – соответствие всюду определено: ; сюръективно:

; функционально: образом любого элемента из области

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

D – соответствие f является частично определенным, так как

; сюръективно, т.к. ; функционально,

т.к. образом любого элемента из является единственный

элемент из ; отображением не является потому, что соответствие не является всюду определенным. ■

Соответствие q ^{– 1} = ( Y,X,Q ^{– 1} ), Q ^{– 1} , называется обратным соответствием для соответствия

q = ( X,Y,Q ) , Q

Если соответствие , обратное к функции f , является функциональным, то оно называется функцией, обратной к f , и обозначается f ^{– 1} .

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

Пример. □ Различные виды кодирования (кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и т.д.) являются соответствиями между кодируемыми объектами и присваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно однозначного соответствия, кроме, возможно, одного – сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. Отсутствие сюръективности означает, что не каждый код имеет смысл. Например, кодирование телефонов шестизначными номерами не сюръективно, поскольку некоторые номера никаким телефонам не соответствуют. Для кодирующей функции, которая каждому объекту из своей области значений ставит в соответствие некоторый код, обратной будет декодирующая функция, которая каждому коду ставит в соответствие закодированный этим кодом объект. Если кодирующая функция не сюръективна, то декодирующая функция не всюду определена. ■

Пусть даны функции f : и g : Функция называется композицией функций f и g ( f ◦ g ), если имеет место равенство h(x) = g(f (x)), где

Композиция представляет собой последовательное применение функций f и g , при этом g применяется к результату функции f . Часто говорят, что функция h получена подстановкой функции f в g .

Пример. □ а) Рассмотрим множество {1,2,3} и два преобразования этого множества: и

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

следующую запись:

Композиция преобразований – есть новое преобразование:

б) Множество К= команд ЭВМ отображается в машинные коды, т.е. в натуральные числа. При помощи суперпозиции кодирующей функции и арифметических функций оказывается возможными арифметические действия над командами (которые сами по себе числами не являются!), т.е. функции , и т.д. ■

Пример. □

Рис. 1.8 Граф адресной дешифровки:

а – случай исправной схемы;

б – случай с неисправностью

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