l´ogica y programaci´on - universidad de sevilla · 2012-02-10 · procedimiento para demostrar...
TRANSCRIPT
Logica y Programacion
Calculo de Secuentes
Antonia M. Chavez, Agustın Riscos, Carmen Graciani
Dpto. Ciencias de la Computacion e Inteligencia ArtificialUniversidad de Sevilla
Definiciones
• Objetivo: Resolver problemas de satisfacibilidad para LogicaProposicional
• Descomposicion de objetivo incial en subobjetivos mas simples
• Definicion: Un secuente es un par formado por dos conjuntosde formulas:
F1, . . . ,Fn ⊢ G1, . . . ,Gm
• {F1, . . . ,Fn} se denomina antecedente del secuente
• {G1, . . . ,Gn} se denomina consecuente del secuente
Definiciones
• Objetivo: Resolver problemas de satisfacibilidad para LogicaProposicional
• Descomposicion de objetivo incial en subobjetivos mas simples
• Definicion: Un secuente es un par formado por dos conjuntosde formulas:
F1, . . . ,Fn ⊢ G1, . . . ,Gm
• Idea: Si todas las formulas del antecedente son ciertas,entonces alguna del consecuente lo es tambien
• Equivale a:
F1 ∧ F2 ∧ · · · ∧ Fn → G1 ∨ G2 ∨ · · · ∨ Gm
Reglas de calculo
• Objetivo: Establecer que secuentes (subobjetivos) tienen queser ciertos para que un determinado secuente (objetivo)tambien lo sea
• Representacion de reglas:
Subobjetivos
Objetivo
Reglas de calculo
• Definicion: Un axioma es un secuente en el que aparece unamisma formula en el antecedente y en el consecuente
• Regla del Axioma:
Γ1,F ,Γ2 ⊢ ∆1,F ,∆2
Ax
donde Γ1,Γ2,∆1 y ∆2 son secuencias finitas de formulas
• La Regla del axioma se lee: Cualquier secuente en el que unamisma formula F aparezca tanto en el antecedente como en elconsecuente es cierto y no genera ningun subobjetivo
Reglas de calculo
• El resto de las reglas del calculo de secuentes indican comodescomponer una formula del secuente objetivo (parte inferiorde la regla) obteniendo un conjunto de secuentes subobjetivos(parte superior de la regla).
• Las reglas se clasifican segun el tipo de formula en cuestion ysi esta se encuentra en el antecedente o en el consecuente delobjetivo.
Reglas de la negacion
Γ1,Γ2 ⊢ F ,∆
Γ1,¬F ,Γ2 ⊢ ∆¬I
F ,Γ ⊢ ∆1,∆2
Γ ⊢ ∆1,¬F ,∆2
¬D
donde Γ,Γ1,Γ2,∆,∆1 y ∆2 son secuencias finitas de formulas
Reglas de la disyuncion
Γ1,F ,Γ2 ⊢ ∆ Γ1,G ,Γ2 ⊢ ∆
Γ1,F ∨ G ,Γ2 ⊢ ∆∨ I
Γ ⊢ ∆1,F ,G ,∆2
Γ ⊢ ∆1,F ∨ G ,∆2
∨ D
donde Γ,Γ1,Γ2,∆,∆1 y ∆2 son secuencias finitas de formulas
Reglas de la conjuncion
Γ1,F ,G ,Γ2 ⊢ ∆
Γ1,F ∧ G ,Γ2 ⊢ ∆∧ I
Γ ⊢ ∆1,F ,∆2 Γ ⊢ ∆1,G ,∆2
Γ ⊢ ∆1,F ∧ G ,∆2
∧ D
donde Γ,Γ1,Γ2,∆,∆1 y ∆2 son secuencias finitas de formulas
Reglas de la implicacion
Γ1,G ,Γ2 ⊢ ∆ Γ1,Γ2 ⊢ F ,∆
Γ1,F → G ,Γ2 ⊢ ∆→ I
F ,Γ ⊢ ∆1,G ,∆2
Γ ⊢ ∆1,F → G ,∆2
→ D
donde Γ,Γ1,Γ2,∆,∆1 y ∆2 son secuencias finitas de formulas
Reglas de la equivalencia
Γ1,F → G ,G → F ,Γ2 ⊢ ∆
Γ1,F ↔ G ,Γ2 ⊢ ∆↔ I
Γ ⊢ ∆1,F → G ,∆2 Γ ⊢ ∆1,G → F ,∆2
Γ ⊢ ∆1,F ↔ G ,∆2
↔ D
donde Γ,Γ1,Γ2,∆,∆1 y ∆2 son secuencias finitas de formulas
Procedimiento
Para demostrar la validez de una formula F mediante el calculo desecuentes:
• Considerar F como secuente objetivo inicial
• Se van aplicando las reglas dando lugar a nuevos subobjetivos
• El proceso se repite hasta que todos los subobjetivos han sidoeliminados mediante la Regla del Axioma. En ese caso, laformula F es valida.
• Si se alcanza un subobjetivo al que no puede aplicarseninguna regla, entonces F no es valida
Ejemplo I
Demostrar la validez de la formula F ≡ p → (q ∨ p) mediante elcalculo de secuentes:
• Considerar F como secuente objetivo inicial
Ejemplo I
Demostrar la validez de la formula F ≡ p → (q ∨ p) mediante elcalculo de secuentes:
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D a p: p ⊢ q ∨ p
⊢ p → (q ∨ p)→ D
Ejemplo I
Demostrar la validez de la formula F ≡ p → (q ∨ p) mediante elcalculo de secuentes:
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D a p: p ⊢ q ∨ p
⊢ p → (q ∨ p)→ D
• Aplicamos la regla ∨D al con-secuente del subobjetivo q ∨ p:
p ⊢ q, p
p ⊢ q ∨ p∨ D
Ejemplo I
Demostrar la validez de la formula F ≡ p → (q ∨ p) mediante elcalculo de secuentes:
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D a p: p ⊢ q ∨ p
⊢ p → (q ∨ p)→ D
• Aplicamos la regla ∨D al con-secuente del subobjetivo q ∨ p:
p ⊢ q, p
p ⊢ q ∨ p∨ D
• Aplicamos la regla del Axioma:p ⊢ q, p
Ax
Ejemplo I
Demostrar la validez de la formula F ≡ p → (q ∨ p) mediante elcalculo de secuentes:
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D a p: p ⊢ q ∨ p
⊢ p → (q ∨ p)→ D
• Aplicamos la regla ∨D al con-secuente del subobjetivo q ∨ p:
p ⊢ q, p
p ⊢ q ∨ p∨ D
• Aplicamos la regla del Axioma:p ⊢ q, p
Ax
• No quedan objetivos pendientes, por tanto F es valida
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D p ∧ (p → q) ⊢ q
⊢ (p ∧ (p → q)) → q→ D
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D p ∧ (p → q) ⊢ q
⊢ (p ∧ (p → q)) → q→ D
• Aplicamos la regla ∧I p, p → q ⊢ q
p ∧ (p → q) ⊢ q∧I
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D p ∧ (p → q) ⊢ q
⊢ (p ∧ (p → q)) → q→ D
• Aplicamos la regla ∧I p, p → q ⊢ q
p ∧ (p → q) ⊢ q∧I
• Aplicamos la regla → I p ⊢ p, q p, q ⊢ q
p, p → q ⊢ q→ I
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D p ∧ (p → q) ⊢ q
⊢ (p ∧ (p → q)) → q→ D
• Aplicamos la regla ∧I p, p → q ⊢ q
p ∧ (p → q) ⊢ q∧I
• Aplicamos la regla → I p ⊢ p, q p, q ⊢ q
p, p → q ⊢ q→ I
• Aplicamos la regla del ax-ioma a los dos subobjetivos: p ⊢ p, q
Axp, q ⊢ q
Ax
Ejemplo II
Demostrar la validez de la formula F ≡ (p ∧ (p → q)) → q
• Considerar F como secuente objetivo inicial
• Aplicamos la regla → D p ∧ (p → q) ⊢ q
⊢ (p ∧ (p → q)) → q→ D
• Aplicamos la regla ∧I p, p → q ⊢ q
p ∧ (p → q) ⊢ q∧I
• Aplicamos la regla → I p ⊢ p, q p, q ⊢ q
p, p → q ⊢ q→ I
• Aplicamos la regla del ax-ioma a los dos subobjetivos: p ⊢ p, q
Axp, q ⊢ q
Ax
• No quedan objetivos pendientes: la formula es valida