- •Часть II. Программное исчисление.
- •Программы как математические объекты
- •5. Семантика cf pascal.
- •Глава 5 знакомит нас с концепцией значения программ. Для точного описания этой идеи используются такие математические структуры как строки, списки, множества, отношения и функции.
- •5.1. Строки символов.
- •5.1.1. Конкатенация строк.
- •5.1.2. Подстроки.
- •5.1.3. Композиция строк.
- •5.1.3. Декомпозиция строк.
- •5.2. Списковые структуры.
- •5.2.1. Списковые операции.
- •5.2.2. Описание файлов с помощью списков.
- •5.3. Множества
- •5.3.1. Правила описания множеств.
- •5.3.2. Операции над множествами.
- •5.3.3. Отношения и функции.
- •5.4. Значение программ.
- •5.4.2. Прямое определение значения программы.
- •5.5. Заключение
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, тогда существуют три варианта их соответствия:
x domain(r), в таком случае r не определено на x
x domain(r), и существуют различные y, z, такие что <x, y> r и <x, z> r. В этом случае r неоднозначно определено на x
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†>}
