Композиция отношений и функций.
Частное значение заголовка программы - преобразование внешнего списка строк в строковое представление значения INPUT в таблице выполнения; частное значение точки –преобразование строкового представления OUTPUT в таблице выполнения во внешний список строк. Оставшаяся часть программы между заголовком и финальной точкой последовательно преобразует начальное состояние выполнения в финальное. Таким образом, функция, соответствующая частному значению заголовка программы, предоставляет входные данные для основной части программы, а основная часть программы предоставляет входные данные для функции, соответствующей частному значению финальной точки.
Результат последовательного выполнения функций, выполняющихся одна после другой, где выходные данные предыдущей функции используются как входные данные для следующей, называется композицией.
Композицией отношений r и s, обозначаемая как r ◦ s, является новое отношение всех возможных пар <x, z>, таких, что для некоторого промежуточного значения у, <x, y> Î r и <y, z> Î s. Записанное в set-нотации данное определение будет выглядеть как:
r ◦ s = {<x, z>, :для некоторого у, <x, y> Î r, <y, z> Î s}
Новое понятие, «некоторое y», может быть определено через известные нам понятие области определения отношения. Рассмотрим отношение между парами и промежуточными значениями.
t = {<<x, z>, y>: <x, y> Î r, <y, z> Î s }
Аргумент <x, z> находится в паре с y в t, только тогда когда промежуточное значение y существует, таким образом, значением r ◦ s будут все возможные аргументы t.
r ◦ s = domain(t)
Программное исчисление формализует интуитивно определяемые значения в таблице выполнения, но существует глубокое различие между box-функциями программного исчисления и таблицами выполнения. Box-функция определяет значение программы во всей его полноте, тогда как таблица выполнения описывает только один элемент значения программы, соответствующий заданным входным данным.
Информация в таблице выполнения получается вычислением box-функции к определенному значению аргумента. Начиная с этого аргумента, значение программы значение программы производит набор промежуточных значений в таблице выполнения.
Таким образом, таблица выполнения является представлением композиции частных значений, но вычисленных для одного аргумента.
Композиция box-функций является также функцией (а не просто значением), и может быть использована для вычисления функции значения больших частей программы, тогда как значение, которое предоставляется таблицей выполнения, не может быть использовано в таких вычислениях.
Определение композиции использует понятие промежуточного значения, которое может быть опущено для функций. Если r однозначно определено на x, определение может быть переписано с использованием функциональной формы записи (value-нотации):
r ◦ s = {<x, z>, :для некоторого у, y=r(x), <y, z> Î s}
если дополнительно s однозначно определено на y
r ◦ s = {<x, z>, :для некоторого у, y=r(x), z=s(y)}
Производя замену для y
r ◦ s = {<x, s(r(x))>: r однозначно определено на x. s однозначно определено на r(x) }
в этой форме промежуточное значение, y, не встречается. Когда r и s однозначно определены, композиция также будет однозначно определена на x.
Поскольку все функции определены однозначно, композиция двух функций также является функцией.
Value-нотация предоставляет способ найти значение композиции двух функций. Для вычисления (f ◦ g)(x) сначала находим y=f(x), затем g(y)
Например, функция, заданная композицией
PROGRAM Any (INPUT, OUTPUT) ◦ .
Может быть прямо вычислена для списка строк L. Сначала найдем
y = PROGRAM Any (INPUT, OUTPUT) (L)
и затем .(y)
Таким образом, PROGRAM Any (INPUT, OUTPUT) ◦ .(L)= .(y),
где y = PROGRAM Any (INPUT, OUTPUT) (L)
Результат ,eltn:
y= {INPUT ·<††, u, R>, OUTPUT ·<††, ††, W>},
.(y)= <††>
вне зависимости от строки u, полученной из списка L. Значение строки прошлого в OUTPUT пусто, и этого достаточно для вычисления результата композиции, который оказался постоянной функцией для любого входного списка строк L.
Композиция является ассоциативной, т.е. для любых отношений r, s, t
(r ◦ s) ◦ t = r ◦ (s ◦ t)
потому что
(r ◦ s) ◦ t = {<x,u>: для некоторого z, <x, z> Î (r ◦ s), <x, u> Î t}
= {<x, u>: для некоторого z, некоторого y <x, y> Î r, <y, z> Î s, <z, u> Î t }
= {<x, u>: некоторого y <x, y> Î r, <y, u> Î (s◦ t}
= r◦ (s ◦ t)
Композиция более чем двух отношений не нуждается в скобках, порядок вычисления может быть любым и может определяться удобством вычисления.
Композиция не является коммутативной. Однако, функция эквивалентности (identity function I) и пустая функция коммутативны с любым отношением, т.н. для любого отношения s:
если domain(s) Í domain(I), тогда s ◦ I = I ◦ s = s
s ◦ {} = {} ◦ s = s
Функции и отношения, применение которых в отношении отменяет друг друга называются инверсными, т.е. r является инверсным отношением для s если и только если,
r ◦ s = I
где I – функция эквивалентности для domain(r)
Транспозицией функции или отношения r, обозначаемой rT является отношение, где поменяли местами элементы всех пар в r, т.е:
rT= {<x, y>: <y, x> Î r}
Транспонирование может быть инверсным, и именно в таком качестве оно будет использоваться в программном исчислении. Полезна следующая проверка:
Если транспозицией отношения r является функция, тогда такая транспозиция является прямой инверсией для r.
Чтобы проиллюстрировать это, предположим, что транспозицией r является функция, тогда, по определению композиции,
r ◦ rT = {<x, z>: для некоторого y, <x, y> Î r, <y, z> Î rT}
= {<x, z>: для некоторого y, <y, x> Î rT, <y, z> Î rT}
Поскольку rT – функция, любые два значения, находящиеся в паре с одним аргументом, идентичны, как x и z для y в примере выше. Тогда
r ◦ rT = {<x, x>: для некоторого y, <x, y> Î r, <y, x> Î rT}
= {<x, x>: для некоторого y, <x, y> Î r }
= I, функция эквивалентности над domain(r)
Поэтому rT является прямой инверсией для r.
Дата добавления: 2016-12-08; просмотров: 923;