Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
5.doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
195 Кб
Скачать
☆

5.3.3. Отношения и функции.

Любое множество 2-списокв или пар называется отношением. Отношения будут особенно полезны при обсуждении значения программ.

Слово «отношение» может означать правило сравнения, «эквивалентность» или «является подмножеством» и т.д. Формально отношения, которые являются множествами 2-списков, могут описать эти неформальные правила точно, путем включения точно тех пар, чьи элементы состоят в нужной связи друг с другом. Например, отношение между символами и 1-строками содержащими эти символы задается следующим отношением:

C = {<x, x>: x - символ} = {<a, †a†>, <b, †b†>, …}

Поскольку отношение это множество, пустое отношение также возможно. Например, соответствие между четными натуральными числами и их нечетными квадратами – таких не существует. Более того, операции над множествами применимы к отношениям. Если s и r отношения, то существуют

s  r, s – r, s  r

поскольку это множества упорядоченных пар элементов.

Частный случай отношения – функция, отношение со специальным свойством, отличающееся тем, что каждый первый элемент находится в паре с уникальным вторым элементом. Отношение r является функцией, если и только если для любого

<x, y>  r и <x, z>  r, то y = z.

В таком случае каждый первый элемент может служить именем для второго в контексте отношения. Например, описанное выше отношение C между символами и 1-строками является функцией.

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

Если f,g –функции, то f  g, f – g тоже функции, но f  g, может быть а может и не быть функцией. Например, определим отношение голова

H = {< Θ y, y>: y - строка} = {<a, †a†>, <a, †aa†>, …}

И возьмем отношение C, описанное выше. Тогда из факта, что C  H:

C  H = C

является функцией,

H - С = {< Θ y, y>: y – строка как минимум из 2 символов}

является отношением, но не функцией,

C – H = {}

является пустой функцией, и

C  H = H

является отношением.

Множество первых элементов пар отношения или функции называется областью определения (domain), а множество вторых элементов пар называется областью значений (range). Для элементов отношения , скажем <x, y>  r, x называется аргументом r, а у называется значением r.

Когда <x, y>  r и и y является единственным значением для x, value-нотация:

y=r(x)

читается, как «y является значением r для аргумента x» или, более кратко, «y является значением r для x» (функциональная форма записи).

Зададим произвольное отношение r и аргумент x, тогда существуют три варианта их соответствия:

  1. x  domain(r), в таком случае r не определено на x

  2. x  domain(r), и существуют различные y, z, такие что <x, y>  r и <x, z>  r. В этом случае r неоднозначно определено на x

  3. x  domain(r), и существует уникальная пара <x, y>  r. В этом случае r однозначно определено на x и y=r(x).

Таким образом, функция – это отношение, которое однозначно определено для всех элементов его области определения.

Выделяют три специальные функции:

Пустая функция {}, не имеет аргументов и значений, то есть

domain({}) = {}, range({}) = {}

Функция эквивалентности (identity function), функция I такая,

что если x  domain(r), тогда I(x) = x.

Постоянная функция, область значений которой задается 1-множеством, то есть всем аргументам соответствует одно и то же значение.

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

r = {<†ball†, †bat†>, <†ball†, †game†>, <†game†, †ball†>}

является отношением, поскольку все его элементы - 2-списки

domain(r) = {†ball†, †game†}

range (r) = {†ball†, †game†, †bat†}

Однако, r не является функцией, потому что два разных значения встречаются в паре с одним аргументом †ball†.

Пример отношения, определенного с помощью правила:

s = {<x, y>: слово x непосредственно предшествует слову y

в строке †this is a relation that is not a function†}

Это отношение также может быть задано перечислением:

s = {<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>, <†relation†, †that†>,

<†that†, †is†>, <†is†, †not†>, <†not†, †a†>, <†a†, †function†>}

Следующее правило определяет функцию:

f = {<x, y>: первый экземпляр слова непосредственно предшествующий слову y

в строке †this is a relation that is also a function†}

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

f = {<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>,

<†relation†, †that†>, <†that†, †is†>, <†also†, †a†>}

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]