Лексикографический порядок

Лексикографический порядоклежит в основе упорядочения слов в различных словарях. Рассмотрим непустое множество символов Х={x,y,…}, называемое алфавитом. Словами будем называть конечные наборы написанных друг за другом элементов Х. Элемент x_i слова x₁,x₂,…,x_n назовём его i-ой координатой, а число n - его длиной.

Определение. Пусть W(X) – множество слов алфавита Х, пусть ≤ - отношение порядка на множестве Х, т.е. (Х,≤) – упорядоченное множество.

Отношение лексикографического порядка(обозначается или L) на W(X) задаётся по правилу: x_1,х_2,…,x_m L y₁,y₂,…,y_n, если выполнено одно из условий: а) x₁< y₁; б) x_i=y_i i:1≤i≤m, m<n; в) x_i=y_i i:1≤i≤k, x_k+1< y_k+1.

Функциональные отношения (функции)

Определение. Бинарное отношение f А×В называется функциональным или функцией из множества А в множество В, если:

а) (x,y₁) f, (x,y₂) f → y₁=y₂ или x A ! y B, (x,y) f;

б) D_f=A, E_f B, где D_f - область определения функции, E_f - область значений.

В этом случае функцию иногда называют тотальной или всюду

определённой; если D_f A, то f называют частичной функцией или частично определённой. В математике, как правило, рассматривают тотальные функции и называют их просто функциями.

Пример1.2.15 – , - функция, т.к. ,

; – не функция, т.к. содержит пары и с одинаковыми первыми и разными вторыми элементами; отношение - функция, т.к. из того, что следует ; – не функция, т.к. содержит пары с одинаковыми первыми и разными вторыми элементами, например, , ;

- частичная функция, т.к. , .

Если задана функция f = {(x,y)|x A, y B}, то x- аргумент, y- значение функции. Различные обозначения функции: y=f(x), f: A→B, f: x→ y; A ^f B,

x ^f у. Говорят также, что f ставит в соответствие элементу х элемент у.

Пусть f = {(x,y)| x A, y B} – функция. Она называется:

а) инъективной (инъекцией, разнозначной), если (x₁,y) f и (x₂,y) f → x₁=x₂ (или x₁≠x₂ → f(x₁) ≠ f(x₂)), при этом - частичная функция;

б) сюръективной (сюръекцией, отображением А на В),

если y B x A, что (x;y) f, т.е. E_f = B;

в) биективной (биекцией, взаимно-однозначным соответствием), если является и инъективной и сюръективной (для тотальной функции). Обозначается А В.

Заметим, что если функция частичная, то, в случае её инъективности и сюръективности, она не всегда биективна, например, ( ) - частичная функция, т.к. , . Она инъективна, т.к. для любых из области определения выполняется ; она сюръективна, т.к. _, но биекции нет, т.к. существуют (например, ), которым не соответствует ни один .

Если биекция f: А А, то она называется подстановкой множества А. Простейший пример подстановки есть тождественное отношение I.

Пример 1.2.16 - Рассмотрим три функции : .

1) - инъективна, т.к. для любых выполняется ; но не сюръективна, т.к. (см. рисунок 1.2.7);

2) - сюръективна, т.к. , но не инъективна, поскольку существуют , но (см. рисунок 1.2.8);

3) - биективна, каждому соответствует один и, наоборот, (график – прямая линия).

Рисунок 1.2.7 Рисунок 1.2.8

Заметим, что свойства этих, а также других функций проще всего определять по их графикам.

Пример 1.2.17 - Рассмотрим функции : , графики которых изображены на рисунке 1.2.9:

Рисунок 1.2.9

По графикам можно установить, что а) - сюръекция (не инъекция);

б) - инъекция (не сюръекция); в) - биекция; г) - не инъективная и не сюръективная функция.

Дата добавления: 2014-12-27