13 Equivalencia de formulas

Definition 13.1.

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

  • •
    ​

    φ⊧ψ\varphi\models\psi

  • •
    ​

    ψ⊧φ\psi\models\varphi

Notacion: φ≡ψ\varphi\equiv\psi

Proposition 13.2.

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

  • •
    ​

    φ≡ψ\varphi\equiv\psi

  • •
    ​

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

Proof 13.3.

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

Proposition 13.4.

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

Proof 13.5.
  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.

Example 13.6.

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.

Definition 13.7 (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.

Theorem 13.8 (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.

Proof 13.9.

Obvio.