Подпоследовательность.

s b t – s явл. подпоследовательностью t.

"t "s $ u, v Î A* [ t = u . s . v => s b t ]

14. Соответствия: определения, свойства соответствий. Понятия функции и отображения.

A, B – некоторые произвольные множества

G A × B – соответствие из A в B

Область определения соответствия: Dom G A

Область значений соответствия: Im G B

im_G a = { b: b Î B & (a, b) Î G } – образ элемента a в В при соответствии G

coim_G b = { a: a Î A & (a, b) Î G } – прообраз элемента b в А при соответствии G

Соответствие G A × B называется взаимнооднозначным, если выполняются условия полноты и единственности.

1. Условия полноты:

1) Dom G = A. Тогда соответствие полностью (всюду) определено.

2) Im G = B. Тогда соответствие сюръективное.

2. Условия единственности:

1) a Î A [ |im_G a| = 1 ]. Тогда соответствие – функциональное (образом любого элемента является единственный элемент)

2) b Î B [ |coim_G b| = 1 ]

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

Каждому элементу а из своей области определения функция ставит в соответствие единственный элемент b из области значений. Это записывается всем известной формулой f(a) = b.

Отображением называется всюду определенное функциональное соответствие.

G: A → B – отображение.

//R A × A – бинарное отношение

//G A × A × ... × A – многоместное отношение

15. Отношения: основные определения, способы задания. Отношения тождества, универсальное и обратное отношение.

Подмножество называется -местным отношением на множестве . Говорят, что находится в отношении , если . Одноместное отношение – это просто подмножество . Такие отношения называют признаками: обладает признаком , если и .

Свойства одноместных отношений — это свойства подмножеств М; поэтому для случая n=1 термин «отношение» употребляется редко.

Наиболее часто встречающимися и хорошо изученными являются двухместные, или бинарные, отношения. Если a, b находятся в отношении R, это часто записывается как aRb.

Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на множестве — это квадратная матрица С порядка т, в которой элемент , стоящий на пересечении i-й строки и j-го столбца, определяется следующим образом:

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

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

Отношение называется обратнымк отношению R (обозначение ), если тогда и только тогда, когда . Из определения непосредственно следует, что .

По Красюку: