20 Alfabeto y reglas de formacion de formulas

Definición V.1 (Alfabeto de la logica de predicados).

$A\coloneqq\left\{p_{1},p_{2},p_{3},\ldots\right\}\cup\left\{\top,\perp,\neg,% \vee,\wedge,\rightarrow,\leftrightarrow,(,)\right\}\cup\left\{c_{1},c_{2},% \ldots\right\}\cup\left\{P_{1},P_{2},\ldots\right\}\cup\left\{x_{1},x_{2},% \ldots\right\}\cup\left\{=\right\}\cup\left\{,\right\}$ .

Nombre	Símbolo	Tipo	Aridad
Constante	$c_{i}$	Función	0
Función de aridad $n\geq 1$	$f_{i}$	Función	$n\geq 1$
Proposición atómica	$p_{i}$	Predicado	0
Predicado de aridad $n\geq 1$	$P_{i}$	Predicado	$n\geq 1$
Variable	$x_{i}$	Variable	-

Nombre	Símbolo	Tipo	Aridad
Verdadero	$\top$	Conectiva	0
Falso	$\perp$		0
Negación	$\neg$		1
Conjunción	$\wedge$		2
Disyunción	$\vee$
Implicación	$\rightarrow$
Doble implicación	$\leftrightarrow$
Igualdad	=	Igualdad	2
Para todo	$\forall$	Cuantificador	-
Existe	$\exists$	Cuantificador	-
Paréntesis izquierdo	(	Auxiliar	-
Paréntesis derecho	)
Coma	,

Vamos a definir de manera recursiva dos lenguajes sobre $A$ :

El conjunto $\mathcal{{T}}$ de los terminos de la logica de predicados (que representaran elementos del dominio).
El conjunto $\mathcal{{F}}_{1}$ de las formulas de la logica de predicados (que representaran enunciados).

Definición V.2 (Recursiva de termino).

1.
Terminos atomicos:
- Si $c$ es un simbolo constante $\Rightarrow c$ es un termino.
- Si $x$ es un simbolo de variable $\Rightarrow x$ es un termino.
2.

Si $f$ es un simbolo de funcion de aridad $n\geq 1$ y $t_{1},t_{2},\ldots,t_{n}$ son terminos entonces $f(t_{1},t_{2},\ldots,t_{n})$ es un termino.
3.

Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores no es un termino.

Definición V.3 (Recursiva de formula de la logica de primer orden).

1.
Formulas atomicas:
- Si $p$ es un simbolo de proposicion atomica $\Rightarrow p$ es una formula.
- $\top$ es una formula.
- $\perp$ es una formula.
- Si $P$ es un simbolo de predicado de aridad $n\geq 1$ y $t_{1},t_{2},\ldots,t_{n}$ son terminos, entonces $P(t_{1},t_{2},\ldots,t_{n}$ es una formula.
- Si $t_{1},t_{2}$ son terminos, entonces $(t_{1}=t_{2})$ es una formula.
2.

Si $\varphi$ es una formula $\Rightarrow\neg\varphi$ es una formula.
3.

Si $\varphi,\psi$ son formulas y $\circ\in\left\{\wedge,\vee,\rightarrow,\leftrightarrow\right\}$ entonces $(\varphi\circ\psi)$ es una formula.
4.
Si $x$ es un simbolo de variable y $\varphi$ es una formula, entonces:
- $\forall x\varphi$ es una formula.
- $\exists x\varphi$ es una formula.
5.

Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores no esu na formula.

Observación V.1.

Se aplican los mismos criterios para abreviar formulas mediante eliminacion de parentesis que vimos en logica proposicional.