7 Arbol estructural de una formula

Ejemplo.

Vamos a construir (antes de definirlo) el arbol estructural de la formula (abreviada):

¬(p↔¬q∨⊤)→q∧¬r→¬(p∨⟂∨r)\displaystyle\neg(p\leftrightarrow\neg q\vee\top)\rightarrow q\wedge\neg r% \rightarrow\neg(p\vee\!\perp\!\vee r)
Definición 7.1 (Grafos, muy informal).

Un grafo no dirigido es un conjunto de puntos (vertices) unidos por segmentos (aristas).

El grado de un vertice es el numero de aristas que inciden en ese vertice.

Un camino entre dos vertices es una sucesion de aristas que conectan esos dos vertices. La longitud del camino es el numero de aristas que lo componen.

Definición 7.2 (Arboles, muy informal).

Un arbol es un tipo especial de grafo que cumple dos condiciones:

  •  
    ​

    Es conexo: entre dos vertices siempre hay algun camino.

  •  
    ​

    No tiene ciclos: no hay caminos que empiecen y acaben en el mismo vertice (sin repetir arista).

Un arbol con raiz es un arbol con vertice marcado (llamado raiz).

Las hojas de un arbol son los vertices “terminales”, es decir, los vertices de grado 1 (a excepcion de la raiz).

La profundidad de un arbol es la longitud del camino mas largo que va desde la raiz hasta una hoja.

Definición 7.3.

La construccion del arbol estructural de una formula se puede definir mediante el siguiente procedimiento recursivo:

  1. 1.
    ​

    Si φ\displaystyle\varphi es una formula atomica, su arbol es un unico vertice etiquetado con φ\displaystyle\varphi. Este vertice es raiz y no hoja. Por definicion, tiene profundidad 0.

  2. 2.
    ​

    Dada una formula cualquiera φ\displaystyle\varphi, el arbol de ¬⁢φ\displaystyle\neg\varphi consiste en un vertice raiz etiquetado con ¬\displaystyle\neg del que sale una arista (hacia abajo). En el otro extremo se “pega” el arbol de φ\displaystyle\varphi.

  3. 3.
    ​

    Dadas dos formulas cualesquiera φ,ψ\displaystyle\varphi,\psi y una conectiva binaria ∘\displaystyle\circ, el arbol de (φ∘ψ)\displaystyle(\varphi\circ\psi) consiste en un vertice raiz etiquetado con ∘\displaystyle\circ del que salen dos aristas (hacia abajo, una hacia la izquierda y otra hacia la derecha). En el extremo de la arista izquierda se “pega” el arbol de φ\displaystyle\varphi y en el extremo de la arista derecha se “pega” el arbol de ψ\displaystyle\psi.

Ejemplo.

Definir por recursion una funcion f\displaystyle f sobre el conjunto ℱ0\displaystyle\mathcal{{F}}_{0} que, dada una formula φ,\displaystyle\varphi, devuelva el numero total de vertices del arbol estructural de φ\displaystyle\varphi.

f:ℱ0\displaystyle f\colon\mathcal{{F}}_{0} ⟶ℕ\displaystyle\longrightarrow\mathbb{N}
φ\displaystyle\varphi ⟼f⁢(φ)= num vertices\displaystyle\longmapsto f(\varphi)=\text{ num vertices}
  1. 1.
    ​

    Si φ\displaystyle\varphi es formula atomica, f⁢(φ)=1\displaystyle f(\varphi)=1.

  2. 2.
    ​

    Dada φ∈ℱ0\displaystyle\varphi\in\mathcal{{F}}_{0}.

    f⁢(¬⁢φ)=f⁢(φ)+1\displaystyle f(\neg\varphi)=f(\varphi)+1

  3. 3.
    ​

    φ,ψ∈ℱ0\displaystyle\varphi,\psi\in\mathcal{{F}}_{0}, ∘∈{∨,∧,→,↔}\displaystyle\circ\in\{\vee,\wedge,\rightarrow,\leftrightarrow\}.

    f⁢(φ∘ψ)=f⁢(φ)+f⁢(ψ)+1\displaystyle f(\varphi\circ\psi)=f(\varphi)+f(\psi)+1

Observacion: coincide con el numero de simbolos no auxiliares de la formula (porque cada vertice tiene un simbolo que no es un parentesis).