Компьютерная алгебра

Эту статью следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.

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

Сигнатурой алгебры (то есть системой обозначений) называется тройка Ω = (S,F,σ), где S — множество сортов, F — множество функциональных символов, σтиповая функция, приписывающая каждому функциональному символу его тип — список сортов всех аргументов и результата соответствующей функции. Таким образом, для каждого fF определён его тип σ(f) = <s1,…,sn,sn+1>, где s1,…, sn — сорта аргументов, sn+1 — сорт результата функции f, n ≥ 0 — число аргументов функции, то есть её арность (говорят n-арная или n-местная функция). 0-арная функция называется константой.

Ω-алгеброй называется пара (A,I), где A — множество объектов алгебры, её носитель, а I — интерпретация сигнатуры Ω на A:

  • каждому сорту sS интерпретация приписывает его носитель — множество AsA объектов сорта s, при этом каждому объекту алгебры должен быть приписан некоторый сорт (может быть, не один);
  • каждому функциональному символу f типа <s1,…,sn,sn+1> интерпретация приписывает некоторую функцию fI : A1×…×An → An+1, где Ai — носитель сорта si. Функции могут быть частичными, то есть не всюду определёнными на A1×…×An. В этом случае алгебра называется частичной. Если же все функции тотальны (то есть, всюду определены на A1×…×An), алгебра называется тотальной.

На одном носителе A можно определить множество Ω-алгебр. Если определенная интерпретация подразумевается, то будем обозначать алгебру (A,Ω), а если подразумевается и сигнатура, то обозначаем её просто A.

Для определения понятия терм будем считать, что с каждым сортом s связано счётное множество символов Vsпеременных сорта s. Множество всех переменных обозначим V. Каждая переменная имеет только один сорт.

Ω-термом сорта s называется любая переменная или константа сорта s, а также любое конечное (то есть, состоящее из конечного числа символов) выражение вида f(t1,…,tn), где fF, σ(f) = < s1,…,sn,s> и ti — Ω-терм сорта si для каждого 1 ≤ i ≤ n.

Терм t, содержащий переменные x1,…,xk, будем обозначать t(x1,…,xk) или t(x). На каждой Ω-алгебре (A,I) такой терм определяет некоторую k-местную функцию. Пусть задана некоторая тотальная (то есть всюду определённая) функция γ: V → A такая, что γ(x)As, если xVs. Эта функция называется оценкой (или интерпретацией) переменных на A. Значение терма t на Ω-алгебре (A,I) при оценке γ обозначается tI[γ] или tI(a1,…,ak), если t = t(x1,…,xk) и γ(xi) = ai. Оно определяется следующим образом (индекс I будем опускать):

  • x[γ] = γ(x) для xV;
  • c[γ] = cI, если определена интерпретация константы c;
  • f(t1,…,tn)[γ] = fI (a1,…,an), если определены все значения ai = ti[γ];
  • в противном случае значение терма не определено.

В силу тотальности оценки значение любого Ω-терма на тотальной Ω-алгебре определено при любой оценке.

Ссылки


 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home