1.2. Соответствия, отображения и функции

Если по какому-то правилу для элементов множества A ставят в соответствие один или несколько элементов множества B, то формируют упорядоченные пары или кортежи (x, y), множество которых называют соответствием или отображением.

Соответствия или отображения, как и множества, могут быть четкими и нечеткими. Так каждому символу клавиатуры компъютера соответствует определенная кодовая комбинация, но фоторобот недостаточно четко соответствует какому-то лицу.

1.2.1. Четкие отображения и функции

Если некоторым элементам множества А соответствуют некоторые элементы множества В, то множество упорядоченных пар формирует подмножество прямого произведения множеств А и В,

т. е. {(x, y)| xA и yB}(АВ). Множество A называют областью отправления, а множество B - областью прибытия.

На рис. 1.1 показаны области отправления A={a, b, c, d, e, f} и прибытия – B={1, 2, 3, 4, 5, 6}.

Проекция на первую компоненту пары {₁(x, y)} формирует область определения A⁰={a, b, c, d, f} A, а на вторую {₂(x, y)} - область значений B⁰={1, 2, 4, 5, 6} B. Элемент y_jB⁰ есть образ элемента х_iA⁰, а элемент х_iA⁰ - прообраз элемента y_jB⁰.

Если хотя бы для одного элемента х_iA⁰ существует несколько образов, то {(x, y)|xA,yB} (AB) называют соответствием.

Например, на рис. 1.1. представлено соответствие, т. к. есть

(c, 1), (c, 6), (d, 4), (d, 5).

Соответствие - это, как правило, двуязычные словари, когда словам одного языка (множество А), как правило, соответствуют несколько слов другого языка (множество В). Например, capacity – способность, мощность, емкость, array – массив, таблица, расположение, scanner - лексический анализатор, устройство для ввода изображений и т. д.

Если для каждого элемента х_iA⁰ существует единственный образ, то такое множество упорядоченных пар называют отображением.

Например, в компьютере каждая буква, цифра или символ отображаются в уникальную 8-битовую кодовую комбинацию: “F”:=01000110,.. “s”:=01110011,.. ”Ф”:=11000100,.. “я”:=11001111,.. “5”:=00110101,.. “+”:=00101011,.. “”:=00100110,.. “{“:=01111011 и т.д.

Единственное отображение принято обозначать t=(x, y), а их множество h={(x, y)|xA, yB}(AB).

Если область определения задана на нескольких множествах Хi, то каждое отображение есть кортеж t=(x1, x2,..,xn, y), а их множество

h={(x₁, x₂, ..,x_n, y)| x_iX_i, yY}((X₁X₂..X_n)Y).

В этом случае y_jY⁰ является образом для (x_1i, x_2i,..,x_ni)(X₁X₂..X_n), а (x_1i, x_2i,..,x_ni)(X₁X₂..X_n) - прообразом для y_jY⁰.

Если X₁=X₂=..=X_n=X, то h={(x₁, x₂,..,x_n, y)| x_iX, yY}(XⁿY).

Отображение удобно представлять в операторной форме:

h: XⁿY,

где h -оператор отображения.

Отображение логически совпадает с понятием функция

f=(x, y) или f=(x₁, x₂,..,x_n, y). В этом случае элементы х и (x₁, x₂,..,x_n) называют аргументами, а y –значением функции y=f(x) или y=f(x₁, x₂,..,x_n).

Например, f₊=(x₁, x₂, y) есть y=x₁+x₂ или f_sg=(x, y) есть y=sg(x).

Множество, связывающее значения аргументов и значения функции, называют графиком функции.

Мощность отображения не больше мощности прямого произведения, т.е.

|h||X₁|_*|X₂|_*.._*|X_n|_*|Y|.

Каждому отображению h может быть найдено обратное отображение: h^-1: YXⁿ или h^-1={(y, x₁, x₂,..x_n)| x_iX, yY}(YXⁿ).

Обратное отображение удобно применять при формировании таблиц реляционных баз данных (см. табл.1.3), когда в “шапке” указывают для каждого столбца имя соответствующей атрибута - I_y, I_x1, I_x2,..I_xn, а в “теле” записывают их значения.

таблица 1.3
h^-1	Iy	Ix1	Ix2	...	Ixn
	y1	x11	x12	...	x1n
	y2	x21	x22	...	x2n
	...	...		...	...
	ym	xm1	xm2	...	xmn

В таблице 1.4 дан фрагмент “Журнала заказов..”. В первом столбце приведен уникальный код заказа (Iy), а в остальных указаны атрибуты клиента.

таблица 1.4.

Код	Клиент	Дата	Город	Индекс
10326	Bolido Comidas preparadas	10-ноя	Мадрид	28023
10837	Berglunds snabbkop	16-фев	Лулео	S-958 22
10853	Blauer Delikatessen	27-фев	Мангейм	68306
10876	Antonio Moreno Taqueria	28-фев	Мехико	05023
11011	Alfreds Futterkiste	09-май	Берлин	12209
...	...	...	...	...

Функция, принимающая значение на двухэлементном множестве {“истина”, “ложь”} или {1, 0}, называется предикатом. В тексте ее обозначают Р(х) или Р(x₁, x₂,..,x_n).

Например, если на множестве целых чисел задать предикаты: Р₁(х):-”x - простое число”, Р₂(x_i, x_j):- ”x_i и x_j имеют общий делитель”, Р₃(f₊(x_i, x_j), x_k):- ”x_k ,больше суммы x_i и х_j”, то для x₁=3, х₂=4 и х₃=8 имеем Р₁(3)=“истина”, Р₁(4)=“ложь”, Р₁(8)=“ложь”, Р₂(3, 4)=“ложь”, Р₂(3, 8)=“ложь”, Р₂(4, 8)=“истина”, Р₃(f₊(3, 4), 8)=“истина”;

Значения предикатов удобно описывать двухмерными таблицами, каждая клетка которых содержит “1”, если выполняется логическое условие, и “0” в противном случае. Например, для Р₂(x_i, x_j) см. таблицу 1.5.

таблица 1.5.
Р2(xi, xj)	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	1	0	1	0	1	0	1	0	1
3	1	0	1	0	0	1	0	0	1	0
4	1	1	0	1	0	1	0	1	0	1
5	1	0	0	0	1	0	0	0	0	1
6	1	1	1	1	0	1	0	1	1	1
7	1	0	0	0	0	0	1	0	0	0
8	1	1	0	1	0	1	0	1	0	1
9	1	0	1	0	0	1	0	0	1	0
10	1	1	0	1	1	1	0	1	0	1

Если даны два отображения h₁ и h₂, то в результате присоединения справа к каждому кортежу первого отображения каждого кортежа второго отображения формируются кортежи нового отображения h, как результат прямого произведения h₁ и h₂, т. е.

h=(h¹h²)={(y¹;x₁¹;x₂¹;...x_n¹;y²;x₁²;x₂²;...x_n²)|y(Y¹Y²), x_i¹X¹; x_i²X²}.

Операторная запись прямого произведения имеет вид:

h:=product(h¹, h²)

Число строк формируемого отображения равно произведению числа кортежей первого и второго отображений, а его ранг равен сумме рангов первого и второго отображений.