8 Induccion para formulas

Definición 8.1.

Sea P\displaystyle P cierta propiedad que esta enunciada para formulas. Denotaremos como P⁢(φ)\displaystyle P(\varphi) el hecho de que la formula φ\displaystyle\varphi cumpel la propiedad P\displaystyle P.

Supongmaos que queremos demostrar que, para toda formula φ\displaystyle\varphi se tiene P⁢(φ)\displaystyle P(\varphi). Esto se puede hacer por induccion sobre el conjunto de todas las formulas mediante los siguientes pasos:

  1. 1.
    ​

    Caso base: demostrar que, para toda formula atomica φ\displaystyle\varphi, se tiene P⁢(φ)\displaystyle P(\varphi).

  2. 2.
    ​

    Para toda formula φ\displaystyle\varphi, suponiendo que es cierta la hipotesis de induccion P⁢(φ)\displaystyle P(\varphi) demostrar que se cumple P⁢(¬⁢φ)\displaystyle P(\neg\varphi).

  3. 3.
    ​

    Para todo par de formulas φ,ψ\displaystyle\varphi,\psi y toda conectiva binaria ∘\displaystyle\circ, suponiendo que es cierta la hipotesis de induccion: P⁢(φ)⁢ y ⁢P⁢(ψ)\displaystyle P(\varphi)\text{ y }P(\psi) demostar que se cumple P⁢((φ∘ψ))\displaystyle P((\varphi\circ\psi)).

Ejemplo.

Demostrar por induccion que toda formula tiene el mismo numero de parentesis izquierdos que de derechos.

P⁢(φ)=\displaystyle P(\varphi)= “φ\displaystyle\varphi tiene mismos parentesis izquierdos y derechos”.

  1. 1.
    ​

    Caso base: φ\displaystyle\varphi atomica. P⁢(φ)⁢?\displaystyle P(\varphi)?

    Si pongo una formula atomica tiene 0 parentesis en la izquierda y 0 en la derecha.

  2. 2.
    ​

    Negacion. H.I. P⁢(φ)\displaystyle P(\varphi), T.I. P⁢(¬⁢φ)=?\displaystyle P(\neg\varphi)=?. Num parentesis izq de ¬⁢φ\displaystyle\neg\varphi = num parent izq de φ\displaystyle\varphi = num parent dchos de φ\displaystyle\varphi = num parent dchos de ¬⁢φ\displaystyle\neg\varphi.

  3. 3.
    ​

    Conectiva binaria.

    H.I. P⁢(φ)\displaystyle P(\varphi), P⁢(ψ)\displaystyle P(\psi).

    T.I. P⁢((φ∘ψ))\displaystyle P((\varphi\circ\psi))?

    num parent izq de (φ∘ψ)\displaystyle(\varphi\circ\psi) = num parent izq de φ\displaystyle\varphi + num parent izq de ψ\displaystyle\psi + 1 = num parent dchos de φ\displaystyle\varphi + num parent dchos de ψ\displaystyle\psi + 1 = num parent dchos de (φ∘ψ)\displaystyle(\varphi\circ\psi).