Recordemos que cada uno de los tipos de estructuras consideradas en el Capítulo Estructuras y su Lenguaje Elemental tiene su tipo asociado. Es decir: \[\begin{aligned} \text{Tipo de los posets} & =(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\\ \text{Tipo de los ret. ternas} & =(\emptyset,\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\\ \text{Tipo de los ret. acotados} & =(\{0,1\},\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\\ \text{Tipo de los ret. comp.} & =(\{0,1\},\{\mathsf{s},\mathsf{i},c\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2),(c,1)\})\\ \text{Tipo de los ret. cuaternas} & =(\emptyset,\{\mathsf{s},\mathsf{i}\},\{\leq\},\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2)\})\\ \text{Tipo de las median algebras} & =(\emptyset,\{M\},\emptyset,\{(M,3)\})\\ \text{Tipo de los grafos} & =(\emptyset,\emptyset,\{r\},\{(r,2)\})\\ \text{Tipo de los grafos bicoloreados} & =(\emptyset,\emptyset,\{r,R\},\{(r,2),(R,1)\}) \end{aligned}\] Nótese que en cada uno de los casos anteriores los símbolos de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\) son los que se usan (junto con los símbolos lógicos, las variables y los nombres de elementos fijos) para formar sus correspondientes términos y fórmulas elementales. Es decir, lo particular de los términos y las fórmulas elementales de cada tipo de estructura estaba dado por los correspondientes símbolos de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\). Esto nos permite generalizar nuestros conceptos intuitivos de término elemental y fórmula elemental, para el caso de cualquier tipo \(\tau\) de estructuras. Aunque debe quedar claro que como en los casos ya vistos estos conceptos serán definidos en forma intuitiva y no se dará una definición matemática precisa de los mismos.
Dado un tipo \(\tau=(\mathcal{C},\mathcal{F},\mathcal{R},a)\) los términos elementales de tipo \(\tau\) se definen con las siguientes clausulas:
adhocprefix(1)adhocsufix Cada palabra de \(\mathcal{C}\) es un término elemental de tipo \(\tau\)
adhocprefix(2)adhocsufix Las variables \(x,y,z,w,...\) son términos elementales de tipo \(\tau\)
adhocprefix(3)adhocsufix Los nombres de elementos fijos \(a,b,c,d,...\) son términos elementales de tipo \(\tau\)
adhocprefix(4)adhocsufix Si \(f\in\mathcal{F}_{n}\), con \(n\geq1\) y \(t_{1},...,t_{n}\) son términos elementales de tipo \(\tau\), entonces la palabra \(f(t_{1},...,t_{n})\) es un término elemental de tipo \(\tau\)
adhocprefix(5)adhocsufix Una palabra es un término elemental de tipo \(\tau\) si y solo si se puede construir usando las clausulas anteriores
Es muy importante entender que un término elemental de tipo \(\tau\) como objeto matemático es una palabra. Nótese que arriba \(f(t_{1},...,t_{n})\) denota el resultado de concatenar las \(n+(n-1)+3\) siguientes palabras \[f\;\;\;(\;\;\;t_{1}\;\;\;,\;\;\;t_{2}\;\;\;,\;\;\;...\;\;\;,\;\;\;t_{n}\;\;\;)\] es decir que \(f(t_{1},...,t_{n})\) es una palabra de longitud \(\left|f\right|+\left|t_{1}\right|+...+\left|t_{n}\right|+(n-1)+2\) (note que \(n-1\) cuenta la cantidad de comas). También debería quedar claro que el concepto de término elemental de tipo \(\tau\) no es un concepto definido en forma matemática precisa.
Veamos algunos ejemplos:
adhocprefix(E1)adhocsufix Si \(\tau\) es el tipo \[(\{\mathrm{un},0\},\{\mathrm{MAS},\mathrm{P},+\},\{\mathrm{Verde}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(+,2),(\mathrm{Verde},1)\})\] entonces las siguientes palabras son términos elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(\mathrm{MAS}(a,b,\mathrm{un},z)\)
adhocprefix-adhocsufix \(\mathrm{P}(\mathrm{P}(z))\)
adhocprefix-adhocsufix \(+(+(0,x),\mathrm{P}(z))\)
adhocprefix-adhocsufix \(\mathrm{MAS}(\mathrm{P}(0),+(0,b),\mathrm{un},\mathrm{MAS}(x,x,x,x))\)
adhocprefix-adhocsufix \(\mathrm{un}\)
adhocprefix-adhocsufix \(0\)
adhocprefix-adhocsufix \(x\)
adhocprefix-adhocsufix \(a\)
Por supuesto las aridades de los nombres de \(\mathcal{F}\) son importantes y deben ser respetadas. Por ejemplo \[\mathrm{P}(x,y)\ \ \ \ \ \ \mathrm{MAS}(a,b)\ \ \ \ \ \ +(x,y,z)\] no son términos elementales de tipo \(\tau\).
adhocprefix(E2)adhocsufix Si \(\tau\) es el tipo de los reticulados complementados \[(\{0,1\},\{\mathsf{s},\mathsf{i},c\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2),(c,1)\})\] entonces las siguientes palabras son términos elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(\mathsf{s}(x,y)\)
adhocprefix-adhocsufix \(\mathsf{s}(\mathsf{i}(x,0),z)\)
adhocprefix-adhocsufix \(c(\mathsf{s}(\mathsf{i}(x,0),c(z)))\)
adhocprefix-adhocsufix \(c(\mathsf{s}(\mathsf{i}(0,0),0))\)
adhocprefix-adhocsufix \(a\)
adhocprefix-adhocsufix \(x\)
adhocprefix-adhocsufix \(0\)
Nótese que no coinciden con los términos elementales de reticulados complementados definidos en el Capítulo Estructuras y su Lenguaje Elemental ya que aquí usamos un formato mas general y usamos \(\mathsf{s}(x,y)\) en lugar de \((x\ \mathsf{s}\ y)\), etc. Obviamente esto no cambia mucho las cosas y es hecho a los fines de homogeneizar la escritura y no hacer un uso distinto para los nombres de función de aridad 2.
adhocprefix(E3)adhocsufix Si \(\tau\) es tal que \(\mathcal{F}=\emptyset\) entonces los términos elementales de tipo \(\tau\) son las variables, los nombres de elementos fijos y los elementos de \(\mathcal{C}\)
adhocprefix(E4)adhocsufix Si \(\tau\) es el tipo \[(\{1,\mathrm{er}\},\{+,\mathsf{s}\},\emptyset,\{(+,5),(\mathsf{s},3)\})\] entonces las siguientes palabras son términos elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(\mathsf{s}(x,z,1)\)
adhocprefix-adhocsufix \(+(1,1,1,1,1)\)
adhocprefix-adhocsufix \(\mathsf{s}(+(\mathrm{er},\mathrm{er},z,a,a),\mathrm{er},\mathsf{s}(x,x,x))\)
adhocprefix(E5)adhocsufix Tal como lo aclaramos anteriormente la definición de tipo es muy libre en lo que respecta a que palabras componen los conjuntos \(\mathcal{C}\), \(\mathcal{F}\) y \(\mathcal{R}\), es decir salvo por ciertas restricciones leves, ellas pueden ser cualquier palabra aunque a veces resulte chocante la elección de las mismas debido al uso y costumbre de los matemáticos. Por ejemplo si tomamos \(\tau=(\{\leq\},\{1\},\emptyset,\{(1,3)\})\), obtenemos un tipo en el cual \(\leq\) es un nombre de constante y el numeral \(1\) es un nombre de función \(3\)-aria (lo cual nos dice que en una estructura de tipo \(\tau\) el símbolo \(\leq\) deberá interpretarse como un elemento del universo y el símbolo \(1\) deberá interpretarse como una operación \(3\)-aria). Algunos términos elementales de este tipo \(\tau\) son:
adhocprefix-adhocsufix \(1(z,z,z)\)
adhocprefix-adhocsufix \(1(x,a,1(\mathrm{\leq},\mathrm{\leq},\mathrm{\leq}))\)
adhocprefix-adhocsufix \(x\)
adhocprefix-adhocsufix \(\mathrm{\leq}\)
Un término elemental de tipo \(\tau\) será llamado puro cuando en el no ocurran nombres de elementos fijos.
Usando el concepto de término elemental de tipo \(\tau\) podemos definir las fórmulas elementales de tipo \(\tau\) con las siguientes clausulas:
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de tipo \(\tau\), entonces la palabra \((t=s)\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(2)adhocsufix Si \(r\in\mathcal{R}_{n}\), con \(n\geq1\) y \(t_{1},...,t_{n}\) son términos elementales de tipo \(\tau\), entonces la palabra \(r(t_{1},...,t_{n})\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de tipo \(\tau\), entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de tipo \(\tau\), entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de tipo \(\tau\), entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de tipo \(\tau\), entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de tipo \(\tau\), entonces la palabra \(\lnot\varphi\) es una fórmula elemental de tipo \(\tau\)
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de tipo \(\tau\), entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de tipo \(\tau\)
adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de tipo \(\tau\), entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de tipo \(\tau\)
adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de tipo \(\tau\) si y solo si se puede construir usando las clausulas anteriores.
Es muy importante entender que una fórmula elemental de tipo \(\tau\) como objeto matemático es una palabra. Debería quedar claro que arriba \(r(t_{1},...,t_{n})\) denota el resultado de concatenar las \(n+(n-1)+3\) siguientes palabras \[r\;\;\;(\;\;\;t_{1}\;\;\;,\;\;\;t_{2}\;\;\;,\;\;\;...\;\;\;,\;\;\;t_{n}\;\;\;)\] es decir que \(r(t_{1},...,t_{n})\) es una palabra de longitud \(\left|r\right|+\left|t_{1}\right|+...+\left|t_{n}\right|+(n-1)+2\) (notar que \(n-1\) cuenta la cantidad de comas). También debería quedar claro que el concepto de fórmula elemental de tipo \(\tau\) no es un concepto definido en forma matemática precisa.
Veamos algunos ejemplos
adhocprefix(E1)adhocsufix Sea \(\tau\) el tipo \[(\{\mathrm{un},0\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her},\mathrm{Verde}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3),(\mathrm{Verde},1)\})\] Entonces las siguientes palabras son fórmulas elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(\mathrm{Her}(x,y,z)\)
adhocprefix-adhocsufix \(\mathrm{Verde}(x)\)
adhocprefix-adhocsufix \(\mathrm{Verde}(\mathrm{MAS}(a,b,\mathrm{un},z))\)
adhocprefix-adhocsufix \(\mathrm{Her}(0,\mathrm{MAS}(a,b,\mathrm{un},z),\mathrm{P}(\mathrm{P}(z))))\)
adhocprefix-adhocsufix \((\mathrm{un}=\mathrm{P}(z))\)
adhocprefix-adhocsufix \((a=a)\)
adhocprefix-adhocsufix \((\mathrm{Verde}(\mathrm{MAS}(a,b,\mathrm{un},z))\wedge(\mathrm{un}=\mathrm{P}(0)))\)
adhocprefix-adhocsufix \((\mathrm{MAS}(a,b,\mathrm{un},z)=b)\)
adhocprefix-adhocsufix \((\mathrm{MAS}(a,b,\mathrm{un},\mathrm{P}(z))=\mathrm{P}(\mathrm{P}(\mathrm{P}(z))))\)
adhocprefix-adhocsufix \(\exists z(\mathrm{MAS}(a,b,\mathrm{un},z)=b)\)
adhocprefix-adhocsufix \(\forall x\forall y\mathrm{Her}(0,y,\mathrm{P}(\mathrm{P}(x)))\)
adhocprefix-adhocsufix \(\forall y\ ((\mathrm{P}(\mathrm{P}(z))=x)\rightarrow\exists z\ (\mathrm{Verde}(z)\wedge\mathrm{Her}(x,y,z)))\)
Por supuesto las aridades de los nombres de \(\mathcal{F}\cup\mathcal{R}\) son importantes y deben ser respetadas. Por ejemplo \[(\mathrm{P}(x,y)=x)\ \ \ \ \ \ \mathrm{Her}(x,y)\ \ \ \ \ \ \ \ \mathrm{Verde}(x,y)\] no son fórmulas elementales de tipo \(\tau\).
adhocprefix(E2)adhocsufix Si \(\tau\) es el tipo \[(\{0,1\},\{\mathsf{s},\bigtriangleup\},\{\leq,r\},\{(\mathsf{s},2),(\bigtriangleup,5),(\leq,2),(r,2)\})\] entonces las siguientes palabras son fórmulas elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(r(x,z)\)
adhocprefix-adhocsufix \(\mathrm{\leq}(x,y)\)
adhocprefix-adhocsufix \(\mathrm{\leq}(\bigtriangleup(x,y,z,0,0),\mathsf{s}(x,x))\)
adhocprefix-adhocsufix \((\mathsf{s}(a,b)=\bigtriangleup(x,y,z,0,0))\)
adhocprefix-adhocsufix \((\bigtriangleup(x,y,z,0,0)=\bigtriangleup(1,1,0,x,z))\)
adhocprefix-adhocsufix \((\mathsf{s}(\bigtriangleup(x,y,z,0,0),z)=1)\)
adhocprefix-adhocsufix \(\lnot r(x,\mathsf{s}(a,\mathsf{s}(a,b)))\)
adhocprefix-adhocsufix \(\lnot\forall y(\mathsf{s}(x,y)=x)\)
adhocprefix-adhocsufix \(\exists z\forall x\ (r(x,\mathsf{s}(z,z)\wedge\lnot\mathrm{\leq}(x,z))\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z\;((r(x,y)\wedge r(y,z))\rightarrow r(x,z))\)
Nótese que hay algunas pequeñas diferencias con las fórmulas elementales de las estructuras clásicas definidas en el Capítulo Estructuras y su Lenguaje Elemental ya que aquí respondemos a un formato mas general. Por ejemplo hemos escrito \(\mathrm{\leq}(x,y)\) en lugar de \(x\leq y\) y \(\mathsf{s}(x,y)\) en lugar de \((x\ \mathsf{s}\ y)\). Esto es a los fines de homogeneizar la escritura y no hacer un uso distinto para los nombres de función y de relación de aridad 2.
Por supuesto las aridades de los nombres de \(\mathcal{F}\cup\mathcal{R}\) son importantes y deben ser respetadas. Por ejemplo \[(+(x,y,z)=x)\ \ \ \ \ \ r(x,y,z)\ \ \ \ \ \ \ \ \mathrm{\leq}(x,y,z)\] no son fórmulas elementales de tipo \(\tau\).
adhocprefix(E3)adhocsufix Si \(\tau\) es el tipo \[(\{\mathrm{er}\},\{+\},\{\leq\},\{(+,4),(\leq,5)\})\] entonces las siguientes palabras son fórmulas elementales de tipo \(\tau\):
adhocprefix-adhocsufix \(\mathrm{\leq}(x,y,\mathrm{er},\mathrm{er},\mathrm{er})\)
adhocprefix-adhocsufix \(\mathrm{\leq}(+(x,y,z,\mathrm{er}),+(x,x,\mathrm{er},x),a,b,z)\)
adhocprefix-adhocsufix \(\exists z(+(x,z,x,+(x,x,x,x))=z)\)
adhocprefix(E4)adhocsufix Si \(\tau\) es el tipo \[(\{\mathrm{er}\},\{\leq\},\{+\},\{(\leq,3),(+,2)\})\] entonces las siguientes palabras son fórmulas elementales de tipo \(\tau\):
adhocprefix-adhocsufix \((\mathrm{\leq}(x,y,\mathrm{er})=x)\)
adhocprefix-adhocsufix \(+(z,\mathrm{er})\)
adhocprefix-adhocsufix \(\exists z\lnot\mathrm{+}(z,\mathrm{er})\)
(aquí hay que tener en cuenta que \(\leq\) es un nombre de función de aridad 3 y que \(+\) es un nombre de relación de aridad 2, lo cual es inusual pero perfectamente posible en nuestra muy general definición de tipo)
adhocprefix(E5)adhocsufix Si \(\tau\) es el tipo \[(\{\leq\},\{+\},\emptyset,\{(+,3)\})\] entonces las siguientes palabras son fórmulas elementales de tipo \(\tau\):
adhocprefix-adhocsufix \((\mathrm{\leq}=x)\)
adhocprefix-adhocsufix \((+(z,\leq,a)=\mathrm{\leq})\)
adhocprefix-adhocsufix \((+(+(z,\leq,\leq),x,a)=b)\)
(aquí hay que tener en cuenta que \(\leq\) es un nombre de constante, lo cual es inusual pero perfectamente posible)
Una fórmula elemental de tipo \(\tau\) será llamada pura cuando en ella no ocurran nombres de elementos fijos. Nótese que en particular los términos elementales de tipo \(\tau\) que ocurran en una fórmula elemental pura de tipo \(\tau\) serán también puros.
Estos conceptos se definen para una fórmula elemental \(\varphi\) de un tipo \(\tau\) cualquiera, de la misma manera que lo hicimos en la Sección de Reticulados Cuaterna para las fórmulas elementales de reticulados cuaterna. Dejamos al lector que los repace. Recordemos que una variable libre de una fórmula elemental era una que al menos una vez ocurría libremente (aunque también pudiera ocurrir acotadamente en dicha fórmula elemental). Cuando una fórmula elemental de tipo \(\tau\) no tenga variables libres, diremos que es una sentencia elemental de tipo \(\tau\). O sea que una sentencia elemental pura de tipo \(\tau\) será una sentencia elemental de tipo \(\tau\) la cual sea pura.