Основные определения. Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения
Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения. Согласно терминологии работы [129], многосортная алгебра A = <(sA)sÎS, (fA)fÎF> состоит из семейства множеств-носителей sA и семейства частичных функций fA:
fA : s1A ´ s2A ´ ... ´ sn-1A® snA, n³0,
Сигнатура S = (S, F) состоит из непустого множества S — символов для обозначения индексов множеств-носителей, называемых также сортами, и непустого множества F функциональных символов, каждому из которых приписана схема отображения
f : s1 ´ s2 ´ ... ´ sn-1® sn, n³0,
означающая запись арности функции, сортность ее аргументов и результата.
Для сигнатуры S = (S,F) многосортная алгебра A = <(sA)sÎS, (fA)fÎF> называется S-алгеброй, если схемы отображений для всех fÎ F согласованы с соответствующими отображениями fA.
Пусть задана сигнатура S = (S,F). С каждым сортом s Î S свяжем счетное множество Xs переменных и определим множество термов TR и функцию тип : TR —> S следующим образом:
- всякая переменная х Î Xs есть терм, причем тип(х) = s;
- всякий нульарный функциональный символ (константа) fÎ F со схемой отображения f: х ® s есть терм, причем mun(f) = s;
- если fÎ F имеет схему f : s1 ´ ... ´ sn-1 ® sn и t1, t2, …, tn-1 — термы, где mun(t1) = s1, ..., mun{tn-1} = sn-1, то f(t1, t2,... , tn-1) — терм, mun(f(t1, t2,..., tn-1)) = sn.
Заметим, что везде в дальнейшем предикатные символы рассматриваются как функциональные со схемой отображения в специальный выделенный сорт BOOLA = {0,1}.
В дальнейшем считаем заданными сигнатуруΣ = (S, F) и Σ –алгебруA=<(sA)sÎS, (fA)fÎF>.
Определение 1. Назовем фактом упорядоченный список вида (fA,e1,...,en),
где fÎ F, f : s1 ´ s2 ´ ... ´ sn-1 ® sn, ei Î TR, mun(ei) = si, i = 1...n.
В этих обозначениях ситуацией назовем конечную конъюнкцию фактов. В дальнейшем через D будем обозначать множество всевозможных ситуаций. Заметим, что понятие ситуации соответствует понятию текущего состояния базы данных или рабочей памяти.
Проиллюстрируем введенные понятия простым примером. Рассмотрим алгебраическую систему
A = < (R, BOОLA), (+, -, *, ³) >,
где R — множество вещественных чисел, BOOLA={0,1}; +, —, *, ³ — обычные операции и отношения над числами. Переменные будем обозначать буквами x, у, z. Тогда уравнение х+у =5 запишется в виде следующего факта: (+, x, y, 5), а система соотношений х+y=5,y³ 0, х £ 3 в виде ситуации:
d0 = (+, x, y,5) Ù (³, у, 0,1) Ù (³, 3, x, 1)
Если все еi, (i = 1... n) в факте суть константы, то факт назовем терминальным. Поскольку среди фактов ситуации могут быть нетерминальные, то, в общем случае, ей соответствует неединственный набор множеств носителей алгебраической системы.
Для простоты изложения в дальнейшем ограничим термы в определении факта константами и переменными, что не нарушает общности изложения, поскольку термы с функциональными символами могут быть записаны в ситуации без них увеличением числа переменных. Например, отношение х+ у ³ 2 запишется в виде (+, х, у, z) Ù (³, z, 2,1).
Определенная таким образом ситуация представляет собой множество конъюнктивно-связанных фактов, и поэтому в дальнейшем будем обращаться с нею как с множеством, используя операции объединения È, пересечения Ç, разности \ и отношение включения Ê.
Обозначим через var{d) множество имен переменных, входящих в ситуацию d, а через T(d) = {mun(x)½x Î var(d)} — множество типов переменных, входящих в факты ситуации d.
Традиционным образом введем понятие подстановки
q= {t1/v1, t2/v2, ..., tm/vm},
где ti — термы, vi — переменные, mun(ti) = mun(vi), i = 1...т. Запись dq означает результат одновременной замены каждого вхождения переменной vi, в d на соответствующий терм ti.
Подстановку q = {x1/y1, x2/y2, ..., xm/ym}, где xi, уi, (i = 1...m) — переменные, назовем алфавитным вариантом. Для каждого алфавитного варианта определена обратная к нему подстановка q -1 при условии, что между переменными определено взаимно - однозначное соответствие.
Определение 2. Две ситуации d и d' назовем эквивалентными (d º d'), если найдется алфавитный вариант q такой, что
d Ê d' q и d' Ê dq -1.
Пусть, например, задана подстановка q = {3/x, z/y}. Тогда ее применение к ситуации d0, приведенной выше, дает
d0 q = (+, 3, z, 5) Ù (³, z, 0,1) Ù (³, 3, 3, 1).
Очевидно, что относительно терминальных фактов, каким, например, является (³,3,3,1), в заданной алгебраической системе всегда можно говорить, истинны они или ложны. Все истинные терминальные факты опускаются при дальнейшем рассмотрении, так как они являются тавтологиями. Таким образом, ситуация d0 q эквивалента ситуации
d0 q = (+, 3, z, 5) Ù (³, z, 0,1).
Если при подстановке появляется ложный терминальный факт, то считается, что подстановка неприменима к заданной ситуации.
Дата добавления: 2016-03-05; просмотров: 587;