Diferencia entre revisiones de «Práctica 5 (LyC Verano)»

De Cuba-Wiki
Línea 129: Línea 129:


==Ejercicio 09==
==Ejercicio 09==
===a)===
===b)===
===c)===
==Ejercicio 10==
==Ejercicio 10==
Como Γ1∪Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1∪Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ٨..٨ αn y β = β1 ٨..٨ βm. Es claro que β ε C(Γ1) y que β ε C(Γ2). Ademas, α ٨ β es una contradiccion. Pero α ٨ β ≡ ¬(¬α ٧ ¬β) ≡ ¬(α → ¬β), de lo cual podemos concluir que (α → ¬β) es una tautologia
Como Γ1∪Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1∪Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ٨..٨ αn y β = β1 ٨..٨ βm. Es claro que β ε C(Γ1) y que β ε C(Γ2). Ademas, α ٨ β es una contradiccion. Pero α ٨ β ≡ ¬(¬α ٧ ¬β) ≡ ¬(α → ¬β), de lo cual podemos concluir que (α → ¬β) es una tautologia

Revisión del 02:10 3 mar 2007

Ejercicio 01

Ejercicio 02

a)

  • 1.SP3: (¬φ → ¬φ) → [ (¬φ → φ) → φ ]
  • 2.VALE: (¬φ → ¬φ) (ya que p → p es tautologia)
  • 3.MP 1 y 2: (¬φ → φ) → φ

→ (¬φ → φ) → φ es tautologia

b)

  • 1.SP1: (ψ→θ)→( φ→(ψ→θ) )
  • 2.AXb: ψ→θ
  • 3.MP 1 y 2: φ→(ψ→θ)
  • 4.SP2: ( φ→(ψ→θ) ) → ( (φ→ψ)→(φ→θ) )
  • 5.MP 3 y 4: (φ→ψ)→(φ→θ)
  • 6.AXb: φ→ψ
  • 7.MP 5 y 6: φ→θ

→ {φ→ψ,ψ→θ} infiere φ→θ

c)

(Falta terminar)

  • 1.SP2: ( [¬φ → ¬ψ]→(φ[ψ → φ]) ) → ( ([¬φ → ¬ψ]φ)→([¬φ → ¬ψ][ψ → φ]) )
  • 2.SP1: φ→[ψ → φ]
  • 3.VALE: [¬φ → ¬ψ]→(φ→[ψ → φ]) = [¬φ → ¬ψ]→T = tautologia
  • 4.MP 1 y 3: ([¬φ → ¬ψ]→φ)→([¬φ → ¬ψ]→[ψ → φ])
  • 5.??

Ejercicio 03

Ejercicio 04

a)

b)

c)

d)

Ejercicio 05

a)

¬(¬(p1 ٧ p2) → ((p3 ٨ p1) ٧ (p2 → p3)))
  	  ¬(p1 ٧ p2)
      ¬((p3 ٨ p1) ٧ (p2 → p3))
	       ¬p1
	       ¬p2
             ¬(p3 ٨ p1)
             ¬(p2 → p3)
              ¬p3   ¬p1
               p2    p2
              ¬p3   ¬p3
               x      x

→ P es tautologia

b)

((p1 → p3) → ((p2 → p3) → ((p1 ٧ p2) → p3)))
      ¬(p1 → p3)     (p2 → p3) → ((p1 ٧ p2) → p3))
           p1                ¬(p2 → p3)    ¬((p1 ٧ p2) → p3)
         ¬p3                     p2               (p1 ٧ p2) 
                                  ¬p3                 ¬p3

¬P = (p1 ٨ ¬p3) ٧ (p2 ٨ ¬p3) ٧ ¬p3 = (p1 ٧ p2 ٧ T) ٨ ¬p3 = ¬p3. Es una contingencia

c)

¬((¬¬¬(p1 ٨ p2) ٧ p3) → p4)
   (¬¬¬(p1 ٨ p2) ٧ p3)
             ¬p4
¬¬¬(p1 ٨ p2)     p3
¬(p1 ٨ p2)
¬p1     ¬p2

¬P = ((¬p1 ٧ ¬p2) ٨ ¬p4) ٧ p3. Como cada variable aparece 1 vez, ¬P es contingencia

Ejercicio 06

a)

(((p0 ٨ ¬p0) ٨ p1) ٨ ¬(p1 ٨ (p1 → p0)))
              ((p0 ٨ ¬p0) ٨ p1)
             ¬(p1 ٨ (p1 → p0))
                  (p0 ٨ ¬p0)
                       p1
                ¬p1 
            p0     ¬(p1 → p0)
           ¬p0      p0
            x         ¬p0
                     p1
                  ¬p0
                    x

b)

((p1 ٨ (p1 → ¬p0)) ٨ ¬(p1 → p0))
        (p1 ٨ (p1 → ¬p0))
           ¬(p1 → p0)
                p1
          (p1 → ¬p0)
               p1     
             ¬p0
        ¬p1      ¬p0
         x

c)

(((p1 ٨ (p2 ٧ p0)) ٨ (p1 ٨ p0)) ٨ ¬((p1 ٨ p2) → p0))
         ((p1 ٨ (p2 ٧ p0)) ٨ (p1 ٨ p0))
              ¬((p1 ٨ p2) → p0)
               (p1 ٨ (p2 ٧ p0))
                  (p1 ٨ p0)
                  (p1 ٨ p2)
                     ¬p0
                       p1
                  (p2 ٧ p0)
                       p1
                       p0
                       p1
                       p2
                    p2  p0
                    x    x

Ejercicio 07

a)

b)

Ejercicio 08


a) F El unico arbol de la formula p1 es ella misma, que es un arbol abierto. Sin embargo, la formula no es una tautologia.
b) F El arbol (p1 ٨ ¬p1) para esa misma formula no es cerrado, pero la formula es una contradiccion. El asunto es que el arbol no esta completo.
c) V (Esta demostrada en algun lado, pero no me acuerdo donde)

Ejercicio 09

a)

b)

c)

Ejercicio 10

Como Γ1∪Γ2 es insatisfacible, por compacidad existe Γ0 Γ1∪Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ٨..٨ αn y β = β1 ٨..٨ βm. Es claro que β ε C(Γ1) y que β ε C(Γ2). Ademas, α ٨ β es una contradiccion. Pero α ٨ β ≡ ¬(¬α ٧ ¬β) ≡ ¬(α → ¬β), de lo cual podemos concluir que (α → ¬β) es una tautologia

Ejercicio 11


Sea Γ' Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {α} U Γ" (con α Γ"). Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a α. Construimos v' como sigue. En las variables de α, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad).


Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento αi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de αi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacias. v satisface a Γ.

Ejercicio 12

Ejercicio 13

Recordemos que {P} |= Q sii (P → Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α → β es tautologia o β → α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α → β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ .