Práctica 3: Consecuencia Lógica y Árboles (Lógica y Computabilidad)

Ejercicio 09

• Ej 9) o simil ej2 del parcial del 21/5/04

Sea Γ satisfacible, probar que $\{\alpha _{1},...,\alpha _{n}\}\models \gamma \Leftrightarrow \{(\alpha _{1}\land ...\land \alpha _{n})\}\models \gamma ,\forall \alpha _{i}\in \Gamma$.

Pruebo la ida: Como Γ es satisfacible, existe una valuación v tal que v(α) = 1 y v(γ) = 1 para todo α en Γ. Entonces v($\alpha _{1}\land ...\land \alpha _{n}$) = 1 y v(γ) = 1. Luego {($\alpha _{1}\land ...\land \alpha _{n}$), γ } es satisfacible por v. Por el teorema de la deducción vale $\{(\alpha _{1}\land ...\land \alpha _{n})\}\models \gamma$

Vuelta: Por el teorema de la deducción sabemos que $\{(\alpha _{1}\land ...\land \alpha _{n})\}\models \gamma \Leftrightarrow (\alpha _{1}\land ...\land \alpha _{n})\rightarrow \gamma$ es tautología. Esto es cierto si y sólo si $(\alpha _{1}\land ...\land \alpha _{n})$ es contradicción o γ es tautología.

• • Si $(\alpha _{1}\land ...\land \alpha _{n})$ es contradicción, absurdo! pues por hipótesis Γ es satisfacible y existe una valuación v tal que v(α) = 1 ∀ α ∈ Γ.
  • Si γ es tautología entonces $\emptyset \models$ γ. En particular $\{\alpha _{1},...,\alpha _{n}\}\models \gamma$.