Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Разрешимость [ править ]

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

База Herbrand [ править ]

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

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

См. Также [ править ]

  • Программирование набора ответов
  • Клон (алгебра)
  • Область дискурса / Вселенная (математика)
  • Теорема Рабина о дереве (монадическая теория бесконечного полного двоичного дерева разрешима)
  • Начальная алгебра
  • Абстрактный тип данных

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

  • Джоэл Берман (2005). «Строение свободных алгебр» . В структурной теории автоматов, полугрупп и универсальной алгебры . Springer . С. 47-76. Руководство по ремонту 2210125 .

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Вселенная Хербранда» . MathWorld .