6 Definicion por recursion de funciones sobre formulas

Ejemplo.

La funcion factorial

fact:ℕ\displaystyle\text{fact}\colon\mathbb{N} ⟶ℕ\displaystyle\longrightarrow\mathbb{N}
n\displaystyle n ⟼n!\displaystyle\longmapsto n!

se puede definir recursivamente mediante las siguientes dos reglas:

  1. 1.
    ​

    fact⁢(1)≔1\displaystyle\text{fact}(1)\coloneqq 1

  2. 2.
    ​

    ∀n≥2fact⁢(n)≔n⋅fact⁢(n−1)\displaystyle\forall n\geq 2\quad\text{fact}(n)\coloneqq n\cdot\text{fact}(n-1)

Observación.

Para definir una funcion sobre ℕ\displaystyle\mathbb{N} por recursion basta con definir f⁢(1)\displaystyle f(1) y, a partir de f⁢(n)\displaystyle f(n), calcular f⁢(n+1)\displaystyle f(n+1).

Ejemplo.

Vamos a definir por recursion una funcion que devuelva el numero de simbolos de una formula.

f:ℱ0\displaystyle f\colon\mathcal{{F}}_{0} ⟶ℕ\displaystyle\longrightarrow\mathbb{N}
formula ⟼numero\displaystyle\longmapsto\text{numero}

Definimos f\displaystyle f:

  1. 1.
    ​

    Si φ\displaystyle\varphi es una formula atomica, f⁢(φ)≔1\displaystyle f(\varphi)\coloneqq 1.

  2. 2.
    ​

    Si φ\displaystyle\varphi es una formula, f⁢(¬⁢φ)=1+f⁢(φ)\displaystyle f(\neg\varphi)=1+f(\varphi)

  3. 3.
    ​

    Si φ,ψ\displaystyle\varphi,\psi son formulas, f⁢(φ∧ψ)=3+f⁢(φ)+f⁢(ψ)\displaystyle f(\varphi\wedge\psi)=3+f(\varphi)+f(\psi), f⁢(φ∨ψ)=3+f⁢(φ)+f⁢(ψ)\displaystyle f(\varphi\vee\psi)=3+f(\varphi)+f(\psi)…

    f⁢(φ∘ψ)=f⁢(φ)+f⁢(ψ)+3\displaystyle f(\varphi\circ\psi)=f(\varphi)+f(\psi)+3 donde ∘∈{∧,∨,→,↔}\displaystyle\circ\in\{\wedge,\vee,\rightarrow,\leftrightarrow\}.

f(¬((¬p→q))∧r)=f((()¬p→q)∧r))+1=f((¬p→q))+f(r)+3+1=f(¬p)+f(q)+3+1+3+1=f(p)+1+1+3+1+3+1=1+1+1+3+1+3+1=11\displaystyle f(\neg((\neg p\rightarrow q))\wedge r)=f((()\neg p\rightarrow q)% \wedge r))+1=f((\neg p\rightarrow q))+f(r)+3+1=f(\neg p)+f(q)+3+1+3+1=f(p)+1+1% +3+1+3+1=1+1+1+3+1+3+1=11

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 apariciones de conectivas en φ\displaystyle\varphi.

Solucion:

f:ℱ0\displaystyle f\colon\mathcal{{F}}_{0} ⟶ℕ∪{0}\displaystyle\longrightarrow\mathbb{N}\cup\{0\}
formula ⟼num conectivas\displaystyle\longmapsto\text{num conectivas}

Definimos f\displaystyle f:

  1. 1.
    ​

    Si φ\displaystyle\varphi es una formula atomica, f⁢(φ)=0\displaystyle f(\varphi)=0. f⁢(⊤)=1\displaystyle f(\top)=1, f⁢(⟂)=1\displaystyle f(\perp)=1.

  2. 2.
    ​

    Si φ\displaystyle\varphi es una formula, f⁢(¬⁢φ)=1+f⁢(φ)\displaystyle f(\neg\varphi)=1+f(\varphi)

  3. 3.
    ​

    Si φ,ψ\displaystyle\varphi,\psi son formulas, f⁢(φ∘ψ)=1+f⁢(φ)+f⁢(ψ)\displaystyle f(\varphi\circ\psi)=1+f(\varphi)+f(\psi), siendo ∘∈{∧,∨,→,↔}\displaystyle\circ\in\{\wedge,\vee,\rightarrow,\leftrightarrow\}

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 conjunto formado por todos los simbolos que aparecen en φ\displaystyle\varphi.

Solucion:

A={p,q,⊤,⟂,∧,∨,→,↔,(,)}\displaystyle A=\{p,q,\top,\perp,\wedge,\vee,\rightarrow,\leftrightarrow,(,)\}

f:ℱ0\displaystyle f\colon\mathcal{{F}}_{0} ⟶𝒫⁢(A)\displaystyle\longrightarrow\mathcal{{P}}(A)
φ\displaystyle\varphi ⟼f⁢(φ)\displaystyle\longmapsto f(\varphi)
  1. 1.
    ​

    f⁢(⊤)={⊤},f⁢(⟂)={⟂},f⁢(p)={p}\displaystyle f(\top)=\{\top\},f(\perp)=\{\perp\},f(p)=\{p\}.

  2. 2.
    ​

    Dado φ∈ℱ0\displaystyle\varphi\in\mathcal{{F}}_{0}, f⁢(¬⁢φ)=f⁢(φ)∪{¬}\displaystyle f(\neg\varphi)=f(\varphi)\cup\{\neg\}

  3. 3.
    ​

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

    f((φ∘ψ))=f(φ)∪f(ψ)∪{(,),∘}\displaystyle f((\varphi\circ\psi))=f(\varphi)\cup f(\psi)\cup\{(,),\circ\}