21 Arbol estructural, recursion, induccion

Dibujar el arbol estructural de la formula:

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.

1. 1.
   ​

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

   Alternativamente si $\varphi$ es atomica,

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

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

3. 3.
   ​

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

4. 4.
   ​

   $f(\forall x\varphi)=f(\varphi)$

5. 5.
   ​

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

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.

1. 1.
   ​

   Si $\varphi$ es atomica,

   $f(\top)=1$

   $f(\perp)=1$

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

   Sea $P$ es un pred. de aridad $n$ con $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 }$

   1. (a)
      ​

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

   2. (b)
      ​

      Terminos compuestos:

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

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

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

2. 2.
   ​

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

3. 3.
   ​

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

4. 4.
   ​

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

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