Lo que nunca me enseñaron: El álgebra de términos

Cuando me enseñaron la lógica de primer orden, empezaron con las definiciones de alfabeto, término, sustitución, igualdad, unificación, etc. Realmente antes habíamos visto los términos, las gramáticas, autómatas y demás, pero nunca desde el punto de vista algebraico.

En un caso era demasiado complejo y en otro demasiado general. Aquí explico lo que es el álgebra de términos de la manera más simple y sencilla posible. A partir de estas definiciones se pueden explorar otras estructuras y operaciones matemáticas con un buen fundamento.

El alfabeto

Supongamos que tenemos un alfabeto de símbolos (que llamaremos funtores) de forma que cada funtor tenga una aridad.

[$$ A=(F,a) $$]
[$$ a:F \rightarrow \mathbb{N} $$]

Este alfabeto no podrá ser vacío ni no numerable.

[$$ 0<\left| F \right| \le \aleph_0 $$]

Cuando la aridad de un funtor es cero, se denomina entonces constante.

Nota: Los símbolos de los paréntesis y las comas están reservados y no podrán formar parte de nuestro alfabeto. Estos símbolos son los que se usan para construir los términos.

Nota: Usaremos las letras del inicio del alfabeto para las constantes (a,b,c) y del medio para los funtores (f,g,h).

Los términos

Llamamos variables a otros símbolos tomados de un conjunto infinito y numerable.

[$$ \left| V \right| = \aleph_0 $$]

Nota: Usaremos las letras del final del alfabeto para las variables.

[$$ \left\{ x,y,z\right\} \subset V $$]

El conjunto de términos de primer orden se define como el menor conjunto[$$ T(A,V) $$]

tal que

[$$ V\subset T(A,V) $$]

y

[$$ M_1,...,M_n \in T(A,V), f\in F \Rightarrow f(M_1,...,M_n) \in T(A,V) $$]

Por ejemplo, si nuestro alfabeto fuera a,b,+ con a y b constantes y con + de aridad dos, algunos términos serían.

• a()
• b()
• +(a(),a())
• +(a(),b())
• +(x,b())
• x

En muchos casos se permite la licencia de omitir los paréntesis vacíos y usar otras notaciones como la infija o la circunfija. Los ejemplos de arriba serían entonces:

• a
• b
• a+a
• a+b
• x+b
• x

Términos con indefinido

Muchas veces es útil añadir un valor indefinido para denotar un error o algún valor excepcional. En estos casos se define

[$$ T^\Omega(A,V)=T(A,V)\cup \left\{ \Omega \right\} $$]

Obviamente, el valor indefinido no debe estar ni entre los funtores ni entre las variables.

[$$ \Omega \not \in F $$]
[$$ \Omega \not \in V $$]

Igualdad de términos

Dos términos son iguales si lo son símbolo a símbolo. Esta relación se puede definir recursivamente sobre la estructura de los términos:

[$$ x = x $$]
[$$ \frac{M_1=M'_1,...,M_n=M'_n}{f (M_1,...,M_n) = f (M'_1,...,M'_n)} $$]