Свободно сгенерированная алгебраическая структура по заданной сигнатуре.
В универсальной алгебре и математической логике термальная алгебра представляет собой свободно порождаемую алгебраическую структуру по заданной сигнатуре . [1] [2] Например, в сигнатуре , состоящей из одной бинарной операции , термин алгебра над набором X переменных представляет собой в точности свободную магму , порожденную X. Другие синонимы этого понятия включают абсолютно свободную алгебру и анархическую алгебру . [3]
С точки зрения теории категорий , терминальная алгебра является исходным объектом для категории всех X -порожденных алгебр одной и той же сигнатуры , и этот объект, уникальный с точностью до изоморфизма , называется исходной алгеброй ; он порождает гомоморфным проектированием все алгебры в категории. [4] [5]
Аналогичным понятием является универсум Эрбрана в логике , обычно используемый под этим названием в логическом программировании [6] , который (абсолютно свободно) определяется, начиная с набора констант и функциональных символов в наборе предложений . То есть вселенная Эрбрана состоит из всех основных терминов : терминов, в которых нет переменных.
Атомная формула или атом обычно определяется как предикат , применяемый к кортежу терминов; тогда основной атом является предикатом, в котором появляются только основные термины. База Эрбрана — это набор всех основных атомов, которые могут быть образованы из символов-предикатов в исходном наборе предложений и терминов во вселенной Эрбрана. [7] [8] Эти две концепции названы в честь Жака Эрбрана .
Алгебры терминов также играют роль в семантике абстрактных типов данных , где объявление абстрактного типа данных обеспечивает подпись многосортной алгебраической структуры, а термин алгебра является конкретной моделью абстрактного объявления.
Универсальная алгебра
Тип — это набор функциональных символов, каждый из которых имеет связанную с ним арность ( т. е. количество входов). Для любого неотрицательного целого числа обозначим функциональные символы в арности . Константа — это функциональный символ арности 0.![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _ {n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Пусть — тип, и пусть — непустой набор символов, представляющий переменные символы. (Для простоты предположим, что и не пересекаются.) Тогда набор термов типа over — это набор всех правильно сформированных строк , которые можно построить с использованием переменных символов, а также констант и операций . Формально это наименьшее множество такое, что:![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
— каждый переменный символ from является термом в , как и каждый постоянный символ из .![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _{0}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для всех и для всех функциональных символов и термов у нас есть строка — заданные термы , применение к ним -арного функционального символа снова представляет собой терм.
![{\displaystyle n\geq 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f\in \tau _ {n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle t_ {1},..., t_ {n} \ in T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(t_{1},...,t_{n})\in T(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle t_{1},...,t_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Короче говоря, термин «алгебра типа over» — это алгебра типа , которая отображает каждое выражение в его строковое представление. Формально определяется следующим образом: [9]![{\displaystyle {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Домен . _
![{\displaystyle {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для каждой нулевой функции в определена как строка .
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _{0}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f^{{\mathcal {T}}(X)}()}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для всех и для каждой n -арной функции и элементов в области определения определяется строка .
![{\displaystyle n\geq 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle t_{1},...,t_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(t_{1},...,t_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Алгебра терминов называется абсолютно свободной , потому что для любой алгебры типа и для любой функции она расширяется до единственного гомоморфизма , который просто присваивает каждому терму соответствующее значение . Формально для каждого :![{\displaystyle {\mathcal {A}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g:X\to {\mathcal {A}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle г}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g^{\ast }: {\mathcal {T}}(X)\to {\mathcal {A}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle т\in {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g^{\ast }(t)\in {\mathcal {A}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle т\in {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если , то .
![{\displaystyle т\в X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle g ^ {\ ast } (t) = g (t)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если , то .
![{\displaystyle t=f\in \tau _{0}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g^{\ast }(t)=f^{\mathcal {A}}()}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если где и , то .
![{\displaystyle t=f(t_{1},...,t_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f\in \tau _ {n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n\geq 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n })))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Пример
В качестве примера тип, основанный на целочисленной арифметике, может быть определен как , , и для каждого .![{\displaystyle \tau _{0}=\{0,1\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _{1}=\{\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _{2}=\{+,*\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \tau _{i}=\{\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle я>2}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Самая известная алгебра типа имеет натуральные числа в качестве своей области и интерпретирует , , , и обычным способом; мы называем это .![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle +}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle *}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {A}}_{nat}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Для примера набора переменных мы собираемся исследовать терминальную алгебру типа над .![{\displaystyle X=\{x,y\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Сначала рассматривается множество термов типа over . Мы используем красный цвет для обозначения его членов, которые в противном случае может быть трудно распознать из-за их необычной синтаксической формы. У нас есть, например ![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
, поскольку является переменным символом;![{\displaystyle x\in X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
, поскольку является постоянным символом; следовательно![{\displaystyle 1\in \tau _{0}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
, поскольку – 2-арный функциональный символ; следовательно, в свою очередь,![{\displaystyle +}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
поскольку является 2-арным функциональным символом.![{\displaystyle *}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
В более общем смысле каждая строка соответствует математическому выражению , построенному из допустимых символов и записанному в польской префиксной записи ; например, термин соответствует выражению в обычной инфиксной записи . Во избежание двусмысленности в польских обозначениях скобки не нужны; например, инфиксное выражение соответствует термину .![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}*+x1x}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x+1)*x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle х+(1*x)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}+x*1x}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Чтобы привести несколько контрпримеров, мы имеем, например,
, поскольку не является ни допустимым переменным символом, ни допустимым постоянным символом;![{\displaystyle z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
, по той же причине,
, поскольку является 2-арным функциональным символом, но используется здесь только с одним аргументом (а именно ).![{\displaystyle +}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}1}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Теперь, когда набор термов установлен, мы рассмотрим алгебру термов типа над . Эта алгебра использует в качестве своей области определения сложение и умножение. Функция сложения принимает два термина и возвращает термин ; аналогично функция умножения отображает данные термины и в термин . Например, оценивает термин . Неформально, операции и являются «лентяями», поскольку они просто записывают, какие вычисления следует выполнить, а не выполняют их.![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {T}}(X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \тау }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle +^{{\mathcal {T}}(X)}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle q}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}+}pq}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle *^{{\mathcal {T}}(X)}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle q}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}*}pq}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle *^{{\mathcal {T}}(X)}({\color {red}+x1}, {\color {red}x})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\color {красный}*+x1x}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle +^{{\mathcal {T}}(X)}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle *^{{\mathcal {T}}(X)}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
В качестве примера однозначной расширяемости гомоморфизма рассмотрим определяемый и . Неформально, определяет присвоение значений переменным символам, и как только это будет сделано, каждый термин из может быть оценен уникальным способом в . Например, ![{\displaystyle g:X\to {\mathcal {A}}_{nat}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g(x)=7}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g(y)=3}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle г}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle T (X)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {A}}_{nat}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{ *}({\color {red}1})&{\text{ поскольку }}g^{*}{\text{ является гомоморфизмом }}\\=&g({\color {red}x})+g ^{*}({\color {red}1})&{\text{, так как }}g^{*}{\text{ совпадает на }}X{\text{ с }}g\\=&7+g ^{*}({\color {red}1})&{\text{ по определению }}g\\=&7+1&{\text{, поскольку }}g^{*}{\text{ является гомоморфизмом }}\\=&8&{\text{ в соответствии с известными арифметическими правилами из }}{\mathcal {A}}_{nat}\\\end{array}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Аналогичным образом получают .![{\displaystyle g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
База Эрбрана
Сигнатура σ языка — это тройка < O , F , P > , состоящая из алфавита констант O , функциональных символов F и предикатов P. База Эрбрана [10] сигнатуры σ состоит из всех основных атомов σ : всех формул вида R ( t 1 , ..., t n ), где t 1 , ..., t n — члены, содержащие нет переменных (т.е. элементов вселенной Эрбрана), а R является n -арным символом отношения ( т.е. предикатом ). В случае логики с равенством она также содержит все уравнения вида t 1 = t 2 , где t 1 и t 2 не содержат переменных.
Разрешимость
Алгебры термов можно показать разрешимыми с помощью исключения кванторов . Сложность проблемы решения НЕЭЛЕМЕНТАРНА, поскольку бинарные конструкторы являются инъективными и, следовательно, образуют пары. [11]
Смотрите также
Рекомендации
- ^ Уилфрид Ходжес (1997). Теория более коротких моделей . Издательство Кембриджского университета . стр. 14. ISBN 0-521-58713-1.
- ^ Франц Баадер ; Тобиас Нипков (1998). Переписывание терминов и все такое. Издательство Кембриджского университета . п. 49. ИСБН 0-521-77920-0.
- ^ Клаус Денеке; Шелли Л. Висмат (2009). Универсальная алгебра и коалгебра. Всемирная научная . стр. 21–23. ISBN 978-981-283-745-5.
- ^ ТД Це (2010). Унифицированная структура для моделей структурного анализа и проектирования: подход, использующий исходную семантику алгебры и теорию категорий . Издательство Кембриджского университета . стр. 46–47. дои : 10.1017/CBO9780511569890. ISBN 978-0-511-56989-0.
- ^ Жан-Ив Безио (1999). «Математическая структура логического синтаксиса». В Карниелли, Вальтер Александр; Д'Оттавиано, Итала М.Л. (ред.). Достижения в современной логике и информатике: материалы одиннадцатой бразильской конференции по математической логике, 6–10 мая 1996 г., Сальвадор, Баия, Бразилия . Американское математическое общество . п. 9. ISBN 978-0-8218-1364-5. Проверено 18 апреля 2011 г.
- ^ Дирк ван Дален (2004). Логика и структура. Спрингер . п. 108. ИСБН 978-3-540-20879-2.
- ^ М. Бен-Ари (2001). Математическая логика для информатики. Спрингер . стр. 148–150. ISBN 978-1-85233-319-5.
- ^ Монро Ньюборн (2001). Автоматизированное доказательство теорем: теория и практика. Спрингер . п. 43. ИСБН 978-0-387-95075-4.
- ^ Стэнли Беррис; HP Санкаппанавар (1981). Курс универсальной алгебры. Спрингер. стр. 68–69, 71. ISBN. 978-1-4613-8132-7.
{{cite book}}
: CS1 maint: multiple names: authors list (link) - ^ Рохелио Давила. Обзор программирования набора ответов.
- ^ Жанна Ферранте; Чарльз В. Ракофф (1979). Вычислительная сложность логических теорий . Спрингер , глава 8, теорема 1.2.
дальнейшее чтение
- Джоэл Берман (2005). «Строение свободных алгебр». В структурной теории автоматов, полугрупп и универсальной алгебры . Спрингер . стр. 47–76. МР 2210125.
Внешние ссылки