Термин алгебра - Term algebra

В универсальная алгебра и математическая логика, а алгебра терминов свободно генерируемый алгебраическая структура над данным подпись.[1][2] Например, в подпись состоящий из одного бинарная операция, термин алгебра над множеством Икс переменных - это в точности свободная магма создано Икс. Другие синонимы этого понятия включают: абсолютно свободная алгебра и анархическая алгебра.[3]

Из теория категорий В перспективе термин "алгебра" - это исходный объект для категория всех алгебр одной сигнатуры, и этот объект, уникальный до изоморфизм, называется начальная алгебра; он генерируется гомоморфный проекция всех алгебр в категории.[4][5]

Аналогичное понятие имеет Вселенная Herbrand в логика, обычно используется под этим именем в логическое программирование,[6] который (абсолютно свободно) определяется, начиная с набора констант и функциональных символов в наборе статьи. То есть вселенная Herbrand состоит из всего основные условия: термины, в которых нет переменных.

An атомная формула или же атом обычно определяется как предикат применяется к набору терминов; а основной атом тогда является предикатом, в котором появляются только основные термины. В База Herbrand - это набор всех основных атомов, которые могут быть образованы из предикатных символов в исходном наборе предложений и терминов в его вселенной Herbrand.[7][8] Эти две концепции названы в честь Жак Эрбранд.

Терминные алгебры также играют роль в семантика из абстрактные типы данных, где объявление абстрактного типа данных обеспечивает подпись многосортной алгебраической структуры, а термин алгебра является конкретной моделью абстрактного объявления.

Разрешимость

Термин алгебры можно показать разрешимыми, используя исключение квантора. Сложность решения проблемы заключается в НЕЭЛЕМЕНТАРНЫЙ.[9]

База Herbrand

Основные статьи: Интерпретация Herbrand и Структура Herbrand

В подпись σ языка - тройка <О, F, п> состоящий из алфавита констант О, функциональные символы F, а предикаты п. В База Herbrand[10] сигнатуры σ состоит из всех основных атомов σ: всех формул вида р(т1, …, тп), куда т1, …, тп - термины, не содержащие переменных (т. е. элементы вселенной Эрбранда) и р является псимвол -арное отношение (т.е. предикат ). В случае логики с равенством он также содержит все уравнения вида т1 = т2, куда т1 и т2 не содержат переменных.

Смотрите также

Рекомендации

  1. ^ Вилифрид Ходжес (1997). Более короткая модельная теория. Издательство Кембриджского университета. стр.14. ISBN  0-521-58713-1.
  2. ^ Франц Баадер; Тобиас Нипков (1998). Перезапись терминов и все такое. Издательство Кембриджского университета. п. 49. ISBN  0-521-77920-0.
  3. ^ Клаус Денеке; Шелли Л. Висмат (2009). Универсальная алгебра и коалгебра. Всемирный научный. С. 21–23. ISBN  978-981-283-745-5.
  4. ^ T.H. Це (2010). Унифицирующая платформа для структурного анализа и моделей проектирования: подход, использующий исходную семантику алгебры и теорию категорий. Издательство Кембриджского университета. С. 46–47. Дои:10.1017 / CBO9780511569890. ISBN  978-0-511-56989-0.
  5. ^ Жан-Ив Безио (1999). «Математическая структура логического синтаксиса». В Вальтере Александра Карниелли, Итала М. Л. Д'Оттавиано (ред.). Достижения современной логики и информатики: материалы одиннадцатой бразильской конференции по математической логике, 6-10 мая 1996 г., Сальвадор, Баия, Бразилия. Американское математическое общество. п. 9. ISBN  978-0-8218-1364-5. Получено 18 апреля 2011.
  6. ^ Дирк ван Дален (2004). Логика и структура. Springer. п. 108. ISBN  978-3-540-20879-2.
  7. ^ М. Бен-Ари (2001). Математическая логика для компьютерных наук. Springer. С. 148–150. ISBN  978-1-85233-319-5.
  8. ^ Новорожденная Монро (2001). Автоматизированное доказательство теорем: теория и практика. Springer. п. 43. ISBN  978-0-387-95075-4.
  9. ^ Жанна Ферранте; Чарльз В. Ракофф (1979). Вычислительная сложность логических теорий. Springer.
  10. ^ Рохелио Давила. Обзор программирования набора ответов.

дальнейшее чтение

внешняя ссылка