13 Equivalencia de formulas

Definición III.10.

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

  • ​

    φ⊧ψ\varphi\models\psi

  • ​

    ψ⊧φ\psi\models\varphi

Notacion: φ≡ψ\varphi\equiv\psi

Proposición III.2.

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

  • ​

    φ≡ψ\varphi\equiv\psi

  • ​

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

Demostración.

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

Proposición III.3.

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

Demostración.
  1. 1.
    ​

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

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

  2. 2.
    ​

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

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

  3. 3.
    ​

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

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

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

∎

Ejemplo III.9.

Asociatividad de conectivas binarias.

  • ​

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

    φ\varphi ψ\psi ω\omega (φ↔ψ)(\varphi\leftrightarrow\psi) (φ↔ψ)↔ω(\varphi\leftrightarrow\psi)\leftrightarrow\omega ψ↔ω\psi\leftrightarrow\omega φ↔(ψ↔ω)\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→pp\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=1u\begin{dcases}p=1\\ q=0\end{dcases}\Rightarrow p\rightarrow q=0,q\rightarrow p=1

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

Definición III.11 (Subformula).

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

Teorema III.1 (de sustitucion).

Sean

  • ​

    φ\varphi una formula

  • ​

    σ\sigma una subformula de φ\varphi

  • ​

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

  • ​

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

Entonces φ≡ψ\varphi\equiv\psi.

Demostración.

Obvio. ∎