Основные определения. Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения

Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения. Согласно терминологии работы [129], многосортная алгебра A = <(s^A)_s_Î_S, (f^A)_f_Î_F> состоит из семейства множеств-носителей s^A и семейства частичных функций f^A:

f^A : s₁^A ´ s₂^A´ ... ´ s_n-1^A® s_n^A, n³0,

Сигнатура S = (S, F) состоит из непустого множества S — символов для обозначения индексов множеств-носителей, называемых также сортами, и непустого множества F функциональных символов, каждому из которых приписана схема отображения

f : s₁ ´ s₂´ ... ´ s_n_-1® s_n, n³0,

означающая запись арности функции, сортность ее аргументов и результата.

Для сигнатуры S = (S,F) многосортная алгебра A = <(s^A)_s_Î_S, (f^A)_f_Î_F> называется S-алгеброй, если схемы отображений для всех fÎ F согласованы с соответствующими отображениями f^A.

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

- всякая переменная х Î X_s есть терм, причем тип(х) = s;

- всякий нульарный функциональный символ (константа) fÎ F со схемой отображения f: х ® s есть терм, причем mun(f) = s;

- если fÎ F имеет схему f : s₁ ´ ... ´ s_n_-1 ® s_n и t₁, t₂, …, t_n_-1 — термы, где mun(t₁) = s₁, ..., mun{t_n_-1} = s_n_-1, то f(t₁, t₂,... , t_n_-1) — терм, mun(f(t₁, t₂,..., t_n_-1)) = s_n.

Заметим, что везде в дальнейшем предикатные символы рассматриваются как функциональные со схемой отображения в специальный выделенный сорт BOOL^A= {0,1}.

В дальнейшем считаем заданными сигнатуруΣ = (S, F) и Σ –алгебруA=<(s^A)_s_Î_S, (f^A)_f_Î_F>.

Определение 1. Назовем фактом упорядоченный список вида (f^A,e₁,...,e_n),

где fÎ F, f : s₁ ´ s₂ ´ ... ´ s_n-1 ® s_n, e_i Î TR, mun(e_i) = s_i, i = 1...n.

В этих обозначениях ситуацией назовем конечную конъюнкцию фактов. В дальнейшем через D будем обозначать множество всевозможных ситуаций. Заметим, что понятие ситуации соответствует понятию текущего состояния базы данных или рабочей памяти.

Проиллюстрируем введенные понятия простым примером. Рассмотрим алгебраическую систему

A = < (R, BOОL^A), (+, -, *, ³) >,

где R — множество вещественных чисел, BOOL^A={0,1}; +, —, *, ³ — обычные операции и отношения над числами. Переменные будем обозначать буквами x, у, z. Тогда уравнение х+у =5 запишется в виде следующего факта: (+, x, y, 5), а система соотношений х+y=5,y³ 0, х £ 3 в виде ситуации:

d₀ = (+, 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= {t₁/v₁, t₂/v₂, ..., t_m/v_m},

где t_i — термы, v_i — переменные, mun(t_i) = mun(v_i), i = 1...т. Запись dq означает результат одновременной замены каждого вхождения переменной v_i, в d на соответствующий терм t_i.

Подстановку q = {x₁/y₁, x₂/y₂, ..., x_m/y_m}, где x_i, у_i, (i = 1...m) — переменные, назовем алфавитным вариантом. Для каждого алфавитного варианта определена обратная к нему подстановка q^-1 при условии, что между переменными определено взаимно - однозначное соответствие.

Определение 2. Две ситуации d и d' назовем эквивалентными (d º d'), если найдется алфавитный вариант q такой, что

d Ê d' q и d' Ê dq ^-1.

Пусть, например, задана подстановка q = {3/x, z/y}. Тогда ее применение к ситуации d₀, приведенной выше, дает

d₀ q = (+, 3, z, 5) Ù (³, z, 0,1) Ù (³, 3, 3, 1).

Очевидно, что относительно терминальных фактов, каким, например, является (³,3,3,1), в заданной алгебраической системе всегда можно говорить, истинны они или ложны. Все истинные терминальные факты опускаются при дальнейшем рассмотрении, так как они являются тавтологиями. Таким образом, ситуация d₀ q эквивалента ситуации

d₀ q = (+, 3, z, 5) Ù (³, z, 0,1).

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

<33 34 353637 38 39 >

Дата добавления: 2016-03-05; просмотров: 592;

Основные определения. Введем понятия из теории моделей в том объеме, в котором они пона­добятся для дальнейшего изложения

Основные определения. Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения