Информатика и компьютерные науки (стр. 4 из 14)

Пример

(1) Вычислительная структура BOOL булевских значений Множество S типов вычислительной структуры BOOL задано так:

S = {Ьоо1}. Множество F символов функций структуры BOOL задано так:

F = {true, false, -, v, ^}. Множество носителей В1 сопоставлено типу Ьоо1, т. e. имеет место

boo|BOOL=B'= {L, О, ^}.

Символы из F обозначают следующие функции:

trueBOOL: ®. B',

faiseBOOL: ®B',

-bool : B' ® B' (бесскобочный префикс),

^ ВооL: B' х В' ® В' (инфикс),

v BOOL: B' х В' ® В' (инфикс).

Причем для a, b Î В имеет место

trueBOOL = L,

falseBOOL =o,

- bool b = not(b),

a vBOOL b = or(a, b),

а ^BOOL b = and(a, b).

Функции являются строгими и потому их значения для случая, когда один из аргументов есть ^, также установлены.

2.2.2. Сигнатуры

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

Определение (сигнатура). Сигнатура S- это пара (S, F) множеств S и F, причем

S обозначает множество типов, т. е. имен для носителей;

F обозначает множество символов (имен) функций;

для каждого символа функции f Î F пусть задана ее функциональное fct f Î S+.

В дальнейшем для улучшения читаемости при задании функциональности для f мы будем писать

fct f=(S1,..., Sn)Sn+l, .

чтобы выразить, что fА в вычислительной структуре А с соответствующей сигнатурой S используется для обозначения отображения

Пример (сигнатуры). Сигнатура вычислительной структуры BOOL булевских значении и натуральных чисел из вышеприведенного примера дает пример сигнатуры.

smat = (bool,),

fbool = {true, false, -i, v, ^},

fct true = bool,

fct false = bool,

fct ~ = (bool) bool (бесскобочный префикс),

fct v = (bool, bool) bool (инфикс),

fct ^ = (bool, bool) bool (инфикс),

Рис.2.3. Диаграмма сигнатуры

Сигнатуры допускают наглядное графическое представление в виде диаграммы сигнатуры. Такая диаграмма для каждого типа содержит узел и для каждого n-местного символа операции - ребро с n входными узлами и одним выходным узлом. Для вычислительной структуры bool мы получаем диаграмму сигнатуры, показанную на рис. 2.3.

Задания одной только сигнатуры, конечно, недостаточно для того, чтобы однозначно охарактеризовать вычислительную структуру. Имеется много различных вычислительных структур с одной и той же сигнатурой.

Вычислительные структуры указывают на структурные свойств информационных систем. В частности, имеет место:

({sА : s Î S}, S, T)

образует снова информационную систему с Т: S ® {sА : s Î S, причем T[s] = sА

Также ({fА: f Î F}, F, I) с I: F® {fА: f Î F}, причем I[f] = fА являет информационной системой.

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

2.2.3. Основные термы

При заданной сигнатуре существует множество основных термов, которые могут быть образованы с помощью символов функций сигнатуры. Пусть S = (S, F) есть сигнатура. Множество основных термов типа s с s Î S определяется следующим образом:

(i) каждый нульместиый символ функции f Î F с fct f = s образует основной терм типа s;

(ii) каждая последовательность символов f(t1, ..., tn) с f Î F и fct f= (S1, ..., Sn) s есть основной терм типа s, если для всех i, 1 <= i <= n, ti есть основной терм типа si.

Множество всех основных термов сигнатуры S обозначим через WS, a множество основных термов типа s - через WSs. Если не существует нульместных символов функций, то множество WS пусто.

Если имеется вычислительная структура А с сигнатурой S, то основные термы в А допускают интерпретацию. Переход от основного терма (представления) типа s к соответствующему элементу а из множества А называют интерпретацией t в А. Интерпретация IA поэтому означает отображение

IA: WS ® {а Î sA; s Î S}.

Для каждого основного терма t запись IA[t] обозначает интерпретацию I в А. Пишут также tA вместо IA[t]. Интерпретация получается заменой в основном терме символов функций на соответствующие функции:

IA[f(t1,...,tn)]=fA (IA[t1] ,.., IA[tn]).

В классической математике часто заданная интерпретация опускается и вместо tA просто записывается t; разницей между основным термом и его интерпретацией там сознательно пренебрегают.

Для каждой вычислительной структуры А сигнатуры S основные термы типа s Î S могут использоваться как представления элементов из множества sA, которые связаны с типом s в А. Если для каждого элемента а (<>^) носителей из А имеется представление терма, т. е. для каждого s и каждого а Î sA (<>^) существует основной терм типа s с tA = а, то А называется термопроизводимой, это равносильно требованию, что в соответствующей информационной системе отображение интерпретаций является сюръективным.

Интерпретация ("значение") основного терма допускает соответственно вычисление терма. Один из простых способов организации такого вычисления представляют собой схемы.

2.2.4. Вычисления основных термов: схемы

Основные термы имеют характерную внутреннюю структуру. Основной терм образуется из символов функций и последовательности (иногда пустой) основных термов ("подтермов"), являющихся термами-аргументами.

Схема (или формуляр) для основного терма - это графическое представление вычислений при интерпретации этого терма; схема состоит из прямоугольников, в которые заносится интерпретация основных термов, и из подсхем для вычислений подтермов. Вычисление интерпретации основного терма допускает удобное его проведение по схеме. Поскольку интерпретация основного терма производится через значения интерпретаций его подтермов, эта интерпретация подтермов упорядочивается с помощью схемы, структура которой аналогична структуре самого основного терма.

Примеры (схемы).

(1) Основному терму ((1 + 2) * 3) - 4 с интерпретацией в N соответствует схема, показанная на рис. 2.4.

Рис. 2.4. Вычислительная схема

(2) Основному тepмy (true ^ false) v (false v ((~false ^ true)) с интерпретацией в BOOL соответствует схема, приведенная на рис. 2.5.

true

false

false

false

true

Рис. 2.5. Вычислительная схема

Как уже говорилось, основные термы могут очень легко применяться для представления элементов из множества носителей вычислительной структуры. Чтобы можно было определить отображение между этими элементами, используют термы со свободными идентификаторами.

2.2,5. Термы с (свободными) идентификаторами

Идентификатор ("обозначатель", "переменная", "неизвестное") - это держатель места ("имя") для терма (или элемента), который (позднее) может быть подставлен на это место. Идентификаторы могут пониматься как имена термов или элементов, которые будут конкретизированы только позднее.

Пусть S = (S, F) - сигнатура, и Х = {Xs: s Î S} - семейство множеств идентификаторов. Пусть множества Xs идентификаторов попарно не пересекаются и отличны от символов функций в F. WS(X) обозначает алгебру термов, распространенную на X, т. е. WSI с SI = (S, F u {х Î Xs: s Î S}) и fct x = s для х Î Хs, где Xs обозначает множество идентификаторов (держателей мест, обозначений) типа s.

Примеры (термы с идентификаторами).

Уравнения с "неизвестными" в математике - это уравнения между термами с идентификаторами, например ax2 + bx + с = 0.

(2) Часто термы снабжаются свободными идентификаторами, чтобы определять функции. Функция f может быть определена через:

f: N ® N с f(x) = 2х+ 1

Термы со свободными идентификаторами называются также полиномами. Вместо идентификаторов в термы могут подставляться другие термы. Соответствующее отображение называется подстановкой в термы с (свободными) идентификаторами.

Пусть t - терм с идентификаторами, х - идентификатор типа s и г -терм типа s; через t [г/х] обозначается терм, который получается, когда идентификатор х заменяется на г. Этот процесс называется подстановкой.

Подстановки описываются формально, аналогично построению термов, с помощью следующих уравнении:

x [t/x] = t,

у [t/x] = у, если х и у - различные идентификаторы,

f(tl,...,tn)[t/x]=f(t1[t/x],...,tn[t/x]), где f Î F с fct f= (S1, .... Sn) Sn+1 и термы ti имеют типы si;.

Через t [t1|/X], ..., tn/Xn] обозначается терм, который возникает из терма t при одновременной подстановке ti вместо (попарно различных) идентификаторов Xi.

Пусть t - терм с (свободными) идентификаторами. Терм г назовем экземпляром t, если г получается из t путем замены (подстановки) в нем определенных (свободных) идентификаторов.

2.2.6. Интерпретация термов с (свободными) идентификаторами

Пусть А - вычислительная структура с сигнатурой S = (S, F), а Х - семейство множеств идентификаторов. Отображение

b: {х Î Xs: s Î S} ® {а Î sA : s Î S},

которое каждому идентификатору х в X типа s ставит в соответствие элемент а Î sA структуры данных sA типа s, называется конкретизацией Х (в А).

Для каждой конкретизации b определяется интерпретация IAb терма t со свободными идентификаторами из Х с помощью следующих равенств:

IAb[x]=b(x), IAb [f(t1,…,tn)]=fA(IAb [t1],…, IAb [tn]),

лтя n = 0 получается IAb [f] = fA .

2.2.7. Термы с (свободными) идентификаторами как схемы

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

Пример (из геометрии). Площадь S кольца s с внутренним радиусом г и внешним радиусом R получается по формуле

S = p(R2 - r').

Терму в правой части формулы соответствует схема, приведенная на рис. 2.7.