13 Equivalencia de formulas

Definición 13.1.

Sean φ\displaystyle\varphi y ψ\displaystyle\psi dos formulas. Decimos que son equivalentes si se cumple simultaneamente:

  •  
    ​

    φ⊧ψ\displaystyle\varphi\models\psi

  •  
    ​

    ψ⊧φ\displaystyle\psi\models\varphi

Notacion: φ≡ψ\displaystyle\varphi\equiv\psi

Proposición 13.1.

Sean φ\displaystyle\varphi y ψ\displaystyle\psi dos formulas. Las siguientes dos afirmaciones son equivalentes.

  •  
    ​

    φ≡ψ\displaystyle\varphi\equiv\psi

  •  
    ​

    φ↔ψ\displaystyle\varphi\leftrightarrow\psi es una tautologia

Demostración.

Ambas afirmaciones son equivalentes a que todo modelo de φ\displaystyle\varphi tambien lo es de ψ\displaystyle\psi y viceversa. ∎

Proposición 13.2.

La relacion ≡\displaystyle\equiv de equivalencia de formulas es una relacion de equivalencia en ℱ0\displaystyle\mathcal{{F}}_{0}.

Demostración.
  1. 1.
    ​

    Reflexiva: ∀φ\displaystyle\forall\varphi, φ=φ⁢?\displaystyle\varphi=\varphi?

    Si φ\displaystyle\varphi tiene los mismos modelos y los mismos contraejemplos que φ\displaystyle\varphi.

  2. 2.
    ​

    ∀φ,ψ\displaystyle\forall\varphi,\psi Si φ≡ψ⇒ψ≡φ⁢?\displaystyle\varphi\equiv\psi\Rightarrow\psi\equiv\varphi?.

    Si φ\displaystyle\varphi y ψ\displaystyle\psi tienen los mismos modelos y contraejemplos ⇒ψ\displaystyle\Rightarrow\psi y φ\displaystyle\varphi tienen los mismos modelos y contraejemplos.

  3. 3.
    ​

    ∀φ,ψ,α\displaystyle\forall\varphi,\psi,\alpha

    φ≡ψψ≡α}⁢⇒?⁢φ≡α\displaystyle\begin{rcases}\varphi\equiv\psi\\ \psi\equiv\alpha\end{rcases}\overset{?}{\Rightarrow}\varphi\equiv\alpha

    Si φ,ψ\displaystyle\varphi,\psi tienen los mismos modelos y contraejemplos y φ,α\displaystyle\varphi,\alpha tienen los mismos modelos y contraejemplos, entonces φ\displaystyle\varphi y α\displaystyle\alpha tienen los mismos modelos y contraejemplos.

∎

Ejemplo.

Asociatividad de conectivas binarias.

  •  
    ​

    (φ↔ψ)↔ω≡φ↔(ψ↔ω)\displaystyle(\varphi\leftrightarrow\psi)\leftrightarrow\omega\equiv\varphi% \leftrightarrow(\psi\leftrightarrow\omega)

    φ\displaystyle\varphi ψ\displaystyle\psi ω\displaystyle\omega (φ↔ψ)\displaystyle(\varphi\leftrightarrow\psi) (φ↔ψ)↔ω\displaystyle(\varphi\leftrightarrow\psi)\leftrightarrow\omega ψ↔ω\displaystyle\psi\leftrightarrow\omega φ↔(ψ↔ω)\displaystyle\varphi\leftrightarrow(\psi\leftrightarrow\omega)
    0 0 0 1 0 1 0
    0 0 1 1 1 0 1
    0 1 0 0 1 0 1
    0 1 1 0 0 1 0
    1 0 0 0 1 1 1
    1 0 1 0 0 0 0
    1 1 0 1 0 0 0
    1 1 1 1 1 1 1

Obs: la implicacion no es conmutativa ni asociativa en general.

Contraejemplos: p→q⁢⇒⁢q→p\displaystyle p\rightarrow q\cancel{\Rightarrow}q\rightarrow p.

Para justificarlo encuentro una valoracion que haga una verdadera y otra falsa.

u⁢{p=1q=0⇒p→q=0,q→p=1\displaystyle u\begin{dcases}p=1\\ q=0\end{dcases}\Rightarrow p\rightarrow q=0,q\rightarrow p=1

p→(q→r)⁢≡⁢(p→q)→r\displaystyle p\rightarrow(q\rightarrow r)\cancel{\equiv}(p\rightarrow q)\rightarrow r con la valoracion u:p=1,q=1,r=0\displaystyle u:p=1,q=1,r=0.

Definición 13.2 (Subformula).

Sea φ\displaystyle\varphi una formula. Decimos que σ\displaystyle\sigma es subformula de φ\displaystyle\varphi si σ\displaystyle\sigma es una cadena de simbolos consecutivos que aparecen dentro de la formula φ\displaystyle\varphi y que es, a su vez, una formula.

Teorema 13.1 (de sustitucion).

Sean

  •  
    ​

    φ\displaystyle\varphi una formula

  •  
    ​

    σ\displaystyle\sigma una subformula de φ\displaystyle\varphi

  •  
    ​

    ρ\displaystyle\rho una formula tal que φ≡ρ\displaystyle\varphi\equiv\rho

  •  
    ​

    ψ\displaystyle\psi el resultado de sustituir en φ\displaystyle\varphi la subformula σ\displaystyle\sigma por ρ\displaystyle\rho

Entonces φ≡ψ\displaystyle\varphi\equiv\psi.

Demostración.

Obvio. ∎