Término de álgebra

En álgebra universal y lógica matemática , un término álgebra es una estructura algebraica generada libremente sobre una firma determinada . ^[1]^[2] Por ejemplo, en una firma consiste en una sola operación binaria , el álgebra plazo sobre un conjunto X de variables es exactamente el magma libre generado por X . Otros sinónimos de la noción incluyen álgebra absolutamente libre y álgebra anárquica . ^[3]

Desde la perspectiva de la teoría de categorías , un término álgebra es el objeto inicial para la categoría de todas las álgebras generadas por X de la misma firma , y este objeto, único hasta el isomorfismo , se denomina álgebra inicial ; genera por proyección homomórfica todas las álgebras de la categoría. ^[4]^[5]

Una noción similar es la de un universo Herbrand en lógica , usualmente usado con este nombre en programación lógica , ^[6] que se define (absolutamente libremente) a partir del conjunto de constantes y símbolos de función en un conjunto de cláusulas . Es decir, el universo de Herbrand consta de todos los términos básicos : términos que no tienen variables.

Una fórmula atómica o átomo se define comúnmente como un predicado aplicado a una tupla de términos; un átomo fundamental es entonces un predicado en el que sólo aparecen términos fundamentales. La base de Herbrand es el conjunto de todos los átomos de tierra que se pueden formar a partir de símbolos predicados en el conjunto original de cláusulas y términos en su universo Herbrand. ^[7]^[8] Estos dos conceptos llevan el nombre de Jacques Herbrand .

Las álgebras de términos también juegan un papel en la semántica de los tipos de datos abstractos , donde una declaración de tipo de datos abstractos proporciona la firma de una estructura algebraica de múltiples ordenamientos y el término álgebra es un modelo concreto de la declaración abstracta.

Decidibilidad

Este artículo puede resultar confuso o poco claro para los lectores . Por favor ayude a aclarar el artículo . Puede haber una discusión sobre esto en la página de discusión . ( Octubre de 2018 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Las álgebras de términos pueden mostrarse decidibles mediante la eliminación de cuantificadores . La complejidad del problema de decisión es NO ELEMENTAL . ^[9]

Base de Herbrand

La firma σ de una lengua es un triple < O , F , P > que consiste en el alfabeto de las constantes de O , símbolos de la función F , y los predicados P . La base Herbrand ^[10] de una firma σ consiste en todos los átomos de tierra de σ : de todas las fórmulas de la forma R ( t ₁ ,…, t _n ), donde t ₁ ,…, t _n son términos que no contienen variables (es decir elementos del universo Herbrand) y R es un nsímbolo de relación -arial ( es decir, predicado ) En el caso de la lógica con igualdad, también contiene todas las ecuaciones de la forma t ₁ = t ₂ , donde t ₁ y t ₂ no contienen variables.

Ver también

Programación de conjuntos de respuestas
Clon (álgebra)
Dominio del discurso / Universo (matemáticas)
Teorema del árbol de Rabin (la teoría monádica del árbol binario completo infinito es decidible)
Álgebra inicial
Tipo de datos abstracto

Referencias

^ Wilfrid Hodges (1997). Una teoría del modelo más corta . Prensa de la Universidad de Cambridge . págs. 14 . ISBN 0-521-58713-1.
^ Franz Baader ; Tobias Nipkow (1998). Reescritura de términos y todo eso . Prensa de la Universidad de Cambridge . pag. 49. ISBN 0-521-77920-0.
^ Klaus Denecke; Shelly L. Wismath (2009). Álgebra universal y Coalgebra . World Scientific . págs. 21-23. ISBN 978-981-283-745-5.
^ TH Tse (2010). Un marco unificador para el análisis estructurado y los modelos de diseño: un enfoque que utiliza la semántica del álgebra inicial y la teoría de categorías . Prensa de la Universidad de Cambridge . págs. 46–47. doi : 10.1017 / CBO9780511569890 . ISBN 978-0-511-56989-0.
^ Jean-Yves Béziau (1999). "La estructura matemática de la sintaxis lógica" . En Carnielli, Walter Alexandre; D'Ottaviano, Itala ML (eds.). Avances en Lógica Contemporánea y Ciencias de la Computación: Actas del XI Congreso Brasileño de Lógica Matemática, 6 al 10 de mayo de 1996, Salvador, Bahía, Brasil . Sociedad Matemática Estadounidense . pag. 9. ISBN 978-0-8218-1364-5. Consultado el 18 de abril de 2011 .
^ Dirk van Dalen (2004). Lógica y Estructura . Springer . pag. 108. ISBN 978-3-540-20879-2.
^ M. Ben-Ari (2001). Lógica matemática para la informática . Springer . págs. 148–150. ISBN 978-1-85233-319-5.
^ Recién nacido de Monroe (2001). Demostración automatizada de teoremas: teoría y práctica . Springer . pag. 43. ISBN 978-0-387-95075-4.
^ Jeanne Ferrante; Charles W. Rackoff (1979). La complejidad computacional de las teorías lógicas . Springer .
^ Rogelio Davila. Descripción general de la programación del conjunto de respuestas .

Otras lecturas

Joel Berman (2005). "La estructura de las álgebras libres" . En Teoría Estructural de Autómatas, Semigrupos y Álgebra Universal . Springer . págs. 47-76. Señor 2210125 .

enlaces externos

Weisstein, Eric W. "Herbrand Universe" . MathWorld .

[1] Wilfrid Hodges (1997). Una teoría del modelo más corta . Prensa de la Universidad de Cambridge . págs. 14 . ISBN 0-521-58713-1.

[2] Franz Baader ; Tobias Nipkow (1998). Reescritura de términos y todo eso . Prensa de la Universidad de Cambridge . pag. 49. ISBN 0-521-77920-0.

[DeneckeWismath2009-3] Klaus Denecke; Shelly L. Wismath (2009). Álgebra universal y Coalgebra . World Scientific . págs. 21-23. ISBN 978-981-283-745-5.

[Tse2010-4] TH Tse (2010). Un marco unificador para el análisis estructurado y los modelos de diseño: un enfoque que utiliza la semántica del álgebra inicial y la teoría de categorías . Prensa de la Universidad de Cambridge . págs. 46–47. doi : 10.1017 / CBO9780511569890 . ISBN 978-0-511-56989-0.

[CarnielliD'Ottaviano1999-5] Jean-Yves Béziau (1999). "La estructura matemática de la sintaxis lógica" . En Carnielli, Walter Alexandre; D'Ottaviano, Itala ML (eds.). Avances en Lógica Contemporánea y Ciencias de la Computación: Actas del XI Congreso Brasileño de Lógica Matemática, 6 al 10 de mayo de 1996, Salvador, Bahía, Brasil . Sociedad Matemática Estadounidense . pag. 9. ISBN 978-0-8218-1364-5. Consultado el 18 de abril de 2011 .

[Dalen2004-6] Dirk van Dalen (2004). Lógica y Estructura . Springer . pag. 108. ISBN 978-3-540-20879-2.

[Ben-Ari2001-7] M. Ben-Ari (2001). Lógica matemática para la informática . Springer . págs. 148–150. ISBN 978-1-85233-319-5.

[Newborn2001-8] Recién nacido de Monroe (2001). Demostración automatizada de teoremas: teoría y práctica . Springer . pag. 43. ISBN 978-0-387-95075-4.

[9] Jeanne Ferrante; Charles W. Rackoff (1979). La complejidad computacional de las teorías lógicas . Springer .

[10] Rogelio Davila. Descripción general de la programación del conjunto de respuestas .

[1]