Термин алгебра - Term algebra
В универсальной алгебре и математической логике , термин алгебра является свободно порожденной алгебраической структурой над данной подписью . Так , например, в подписи , состоящей из одной двоичной операции , термин алгебра над множеством X переменных в точности свободной магма , порожденная X . Другие синонимы этого понятия включают абсолютно свободную алгебру и анархическую алгебру .
С точки зрения теории категорий термин алгебра является исходным объектом для категории всех X- порожденных алгебр одной и той же сигнатуры , и этот объект, уникальный с точностью до изоморфизма , называется исходной алгеброй ; он порождает посредством гомоморфной проекции все алгебры в категории.
Сходное понятие - это понятие вселенной Herbrand в логике , обычно используемое под этим именем в логическом программировании , которое (абсолютно свободно) определяется, начиная с набора констант и функциональных символов в наборе предложений . То есть вселенная Хербранда состоит из всех основных терминов : терминов, в которых нет переменных.
Атомная формула или атом обычно определяются как предикат , применяемого к кортежу терминов; атом в основном тогда предикат , в котором появляются только измельченные условия. База Herbrand - это набор всех основных атомов, которые могут быть образованы из предикатных символов в исходном наборе предложений и терминов в его вселенной Herbrand. Эти две концепции названы в честь Жака Эрбрана .
Срочные алгебры также играют определенную роль в семантике из типов абстрактных данных , где абстрактное объявление типа данных обеспечивает подпись мульти-отсортировано алгебраической структуру и термин алгебра представляет собой модель бетоны абстрактной декларации.
Разрешимость
Терминовые алгебры можно показать разрешимыми с помощью исключения кванторов . Сложность проблемы решения НЕЛЕМЕНТАРНАЯ .
База Herbrand
Подпись σ языка является тройка < О , Р , Р > , состоящее из алфавита констант O , функциональных символов F , и предикаты P . Эрбран база подписи σ состоит из всех атомов Основание сг : из всех формул вида R ( т 1 , ..., т п ), где т 1 , ..., т п являются терминами , не содержащие переменные (т.е. элементы Вселенная Эрбранда), а R - n- мерный символ отношения ( то есть предикат ). В случае логики с равенством он также содержит все уравнения вида t 1 = t 2 , где t 1 и t 2 не содержат переменных.
Смотрите также
- Программирование набора ответов
- Клон (алгебра)
- Область дискурса / Вселенная (математика)
- Теорема Рабина о дереве (монадическая теория бесконечного полного двоичного дерева разрешима)
- Начальная алгебра
- Абстрактный тип данных
Рекомендации
дальнейшее чтение
- Джоэл Берман (2005). «Строение свободных алгебр» . В структурной теории автоматов, полугрупп и универсальной алгебры . Springer . С. 47-76. Руководство по ремонту 2210125 .