21 Arbol estructural, recursion, induccion ‣ Parte V Sintaxis de la logica de predicados ‣ Lógica‣ Parte V Sintaxis de la logica de predicados ‣ Lógica

Observación.

Ejemplo.

Dibujar el arbol estructural de la formula:

\displaystyle\forall x(P(a,f(x))\wedge Q(f(a)))\rightarrow(p\vee P(g(b,y),a)% \leftrightarrow\exists y(Q(y)\wedge(g(a,a)=x)))

Ejemplo.

Recursion. Definir por recursion una fubcion que, dada una formula cualquiera de la logica de predicados, devuelva el numero de conectivas que aparecen en la formula.

	$\displaystyle f\colon\mathcal{{F}}_{1}$	$\displaystyle\longrightarrow\mathbb{N}\cup\{0\}$
	$\displaystyle\varphi$	$\displaystyle\longmapsto f(\varphi)=\text{ num conectivas }$

1.

Para formulas atomicas, $\displaystyle f(\top)=1$ , $\displaystyle f(\perp)=1$ . Si $\displaystyle p$ es un simbolo de proposicion atomica, $\displaystyle f(p)=0$ . $\displaystyle f(P(t_{1},\ldots,t_{n}))=0$ , $\displaystyle f(t_{1}=b_{1})=0$

Alternativamente si $\displaystyle\varphi$ es atomica,

$\displaystyle f(\varphi)=\begin{dcases}1\text{ si }\varphi=\top,\perp\\ 0\text{ en el resto de casos}\end{dcases}$
2.

Si $\displaystyle\varphi\in\mathcal{{F}}_{1}$ , entonces $\displaystyle f(\neg\varphi)=f(\varphi)+1$ .
3.

Si $\displaystyle\varphi,\psi\in\mathcal{{F}}_{1}\Rightarrow f((\varphi\circ\psi))% =f(\varphi)+f(\psi)+1$
4.

$\displaystyle f(\forall x\varphi)=f(\varphi)$
5.

$\displaystyle f(\exists x\varphi)=f(\varphi)$

Ejemplo.

Definir por recursion una funcion que, dada una formula cualquiera de la logica de predicados, devuelva el numero de simbolos no auxiliares que aparecen en esa formula.

	$\displaystyle f\colon\mathcal{{F}}_{1}$	$\displaystyle\longrightarrow\mathbb{N}$
	$\displaystyle\varphi$	$\displaystyle\longmapsto f(\varphi)=\text{num simbolos no aux }$

1.

Si $\displaystyle\varphi$ es atomica,

$\displaystyle f(\top)=1$

$\displaystyle f(\perp)=1$

$\displaystyle p$ simb de prop atomica $\displaystyle\Rightarrow f(p)=1$

Sea $\displaystyle P$ es un pred. de aridad $\displaystyle n$ con $\displaystyle t_{1},\ldots,t_{n}$ terminos.

Necesito una funcion nueva que cuente el numero de simbolos no auxiliares de un termino, que vamos a definir tambien por recursion.

	$\displaystyle g\colon\mathcal{{T}}$	$\displaystyle\longrightarrow\mathbb{N}$
	$\displaystyle t$	$\displaystyle\longmapsto g(t)=\text{ num simbolos no aux }$

a)

Si $\displaystyle t$ es termino atomico, $\displaystyle g(t)=1$ .
b)

Terminos compuestos:

Sea $\displaystyle h$ un simbolo de funcion de aridad $\displaystyle n$ y $\displaystyle t_{1},\ldots,t_{n}$ terminos: $\displaystyle g(h(t_{1},\ldots,t_{n}))=g(t_{1})+g(t_{2})+\cdots+g(t_{n})+1$

Luego $\displaystyle f(P(t_{1},t_{2},\ldots,t_{n}))=g(t_{1})+g(t_{2})+\cdots+g(t_{n})+1$

Si $\displaystyle t_{1},t_{2}$ son terminos, $\displaystyle f((t_{1}=t_{2}))=g(t_{1})+g(t_{2})+1$

2.

Sea $\displaystyle\varphi\in\mathcal{{F}}_{1}\Rightarrow f(\neg\varphi)=f(\varphi)+1$
3.

Sea $\displaystyle\varphi,\psi\in\mathcal{{F}}_{1}$ $\displaystyle\Rightarrow f((\varphi\circ\psi))=f(\varphi)+f(\psi)+1$
4.

Sea $\displaystyle\varphi\in\mathcal{{F}}_{1}$

$\displaystyle f(\forall x\varphi)=f(\varphi)+2$ $\displaystyle f(\exists x\varphi)=f(\varphi)+2$