6 Definicion por recursion de funciones sobre formulas

Example 6.1.

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\text{fact}(1)\coloneqq 1

  2. 2.
    ​

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

Remark 6.2.

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

Example 6.3.

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 ff:

  1. 1.
    ​

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

  2. 2.
    ​

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

  3. 3.
    ​

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

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

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=11f(\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

Example 6.4.

Definir por recursion una funcion ff sobre el conjunto ℱ︀0\mathcal{{F}}_{0} que, dada una formula φ,\varphi, devuelva el numero total de apariciones de conectivas en φ\varphi.

Solucion:

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

Definimos ff:

  1. 1.
    ​

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

  2. 2.
    ​

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

  3. 3.
    ​

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

Example 6.5.

Definir por recursion una funcion ff sobre el conjunto ℱ︀0\mathcal{{F}}_{0} que, dada una formula φ,\varphi, devuelva el conjunto formado por todos los simbolos que aparecen en φ\varphi.

Solucion:

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

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}f(\top)=\left\{\top\right\},f(\perp)=\left\{\perp\right\},f(p)=\left\{p\right\}.

  2. 2.
    ​

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

  3. 3.
    ​

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

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