Download Lógica de proposiciones - Tecnológico de Monterrey, Campus

Resolución, la regla de inferencia
y el cálculo
Raúl Monroy
Campus Estado de México—Raúl Monroy
Resolución: la regla de
inferencia
• Sistema de inferencia con “sólo” una regla:
P,Q Q,R
P Q
Q R
P  R
P,R
• Modus Ponens y Modus Tollens son casos especiales de
resolución

– Cuidado: nunca resolver sobre proposiciones distintas
simultáneamente
• Una deducción por resolución de P, dado , es una
secuencia de cláusulas i) rematada con P y ii) donde cada
miembro está en  o es resultado de aplicar resolución a 2
cláusulas que aparecen antes en la secuencia
Campus Estado de México—Raúl Monroy
Resolución: el método
• Idea básica: Si, dado un conjunto de
premisas, , se desea mostrar la
proposición, P, entonces añade a  la
negación de P y busca una refutación; i.e.,
muestra que {¬P} es inconsistente
• Restricción: Aplica sólo a términos de
primer orden en forma clausular
Campus Estado de México—Raúl Monroy
Forma normal clausular (CF)
• Un conjunto de fórmulas se encuentra en
forma clausular sii cada fórmula es una
cláusula
• Una cláusula es una disyunción de literales
• Una literal es una constante objeto o la
negación de una constante objeto
– N.B. use un procedimiento de normalización
Campus Estado de México—Raúl Monroy
Forma normal conjuntiva
(CNF)
• Lema: El procedimiento de forma normal
conjuntiva, aplicado a una fórmula, termina
produciendo otra, equivalente, en forma normal
conjuntiva
Campus Estado de México—Raúl Monroy
Forma clausular
• Romper la conjunción de cláusulas en cláusulas
independientes:
• Lema : El proceso forma clausular, aplicado a una
fórmula en forma normal conjuntiva, termina
produciendo otra en forma clausular
Campus Estado de México—Raúl Monroy
Propiedades del método de
resolución
• Proposición 1: El método de resolución es
correcto
• Si existe una deducción resolución de P a
partir de , entonces  |= P
– Demostración: por inducción en la longitud de
la deducción resolución
Campus Estado de México—Raúl Monroy
• Lema: Si la cláusula C = C1\{L}C2\{L}
que resulta de una aplicación de la regla de
resolución es falsa bajo una evaluación E,
entonces la conjunción de las hipótesis de la
regla, C1C2, es falsa bajo E.
• Corolario: si podemos derivar  usando
resolución, entonces las premisas implican
lógicamente  y por lo tanto no pueden
satisfacerse.
Campus Estado de México—Raúl Monroy
• Proposición 2: El método de resolución es
completo
• Teorema: Si  no puede satisfacerse, hay
una deducción por resolución de {} (= )
Campus Estado de México—Raúl Monroy
• Demostración de Proposición 2
• El caso en que  está en  es simple; el otro caso se deriva
del siguiente
• Proposición: Si  no puede satisfacerse, y tiene k literales
en exceso, entonces hay una deducción por resolución de
{} (= )
• exceso(C) =
– 0
si |C| < 1
– |C| - 1
si |C| > 1
• exceso =  exceso(Ci)
Campus Estado de México—Raúl Monroy
• Base: k = 0, simple, no hay cláusulas nounitarias
• Inductivo: k > 0, la hipótesis se cumple
para cualquier ’, que no puede
satisfacerse, con menos de k literales
exceso, demuestre el resultado para  con k
literales exceso (NB no olvide que  no
puede satisfacerse)
Campus Estado de México—Raúl Monroy
Lógica de proposiciones:
Semántica
• Semántica: La semántica de una lógica es
una definición de la veracidad de las
oraciones en un lenguaje de la lógica en
términos de una interpretación
Campus Estado de México—Raúl Monroy
Interpretación
• Una interpretación, I, para un lenguaje, L, es
una definición de cada uno de los símbolos no
lógicos de L en términos de algún dominio,
v.gr.:
S={b,p,q}; D={⊺, };
I(b)= , I(p)= , I(q)= ⊺
Campus Estado de México—Raúl Monroy
Modelo y consecuencia
lógica
• Una interpretación, I, para un lenguaje, L,
satisface o es modelo de una oración, P, si P es
verdadera en I. En símbolos,
• Sean P y  una oración y un conjunto de
oraciones, P es una consecuencia lógica de sii
cada interpretación que es modelo de todas las
oraciones en  también es un modelo de P. En
símbolos,
Campus Estado de México—Raúl Monroy
Semántica de la lógica de
proposiciones
• La semántica de la lógica proposicional es
una definición de la veracidad de una oración
con respecto a una interpretación:
• I(P) = ⊺ sii I(P) = 
• I(P1  P2) = ⊺ sii I(P1) = ⊺ y I(P2) = ⊺
• I(P1  P2) = ⊺ sii I(P1) = ⊺ o I(P2) = ⊺
• I(P1  P2) = ⊺ sii I(P1) =  o I(P2) = ⊺
• I(P1  P2) = ⊺ sii I(P1) es equivalente a I(P2)
Campus Estado de México—Raúl Monroy
• P es universalmente válida, o
tautológica, si es verdadera en
cualquier interpretación:
• Si por el contrario P es falsa en toda
interpretación, decimos que es una
contradiccion
Campus Estado de México—Raúl Monroy
Teoría
• Una teoría es un conjunto de oraciones el cual está
cerrado bajo consecuencia lógica.
• Una teoría, , es completa sii, para cada oración,
P, P o bien P es miembro de 
• Una teoría, , es inconsistente sii, para alguna
oración P,
–
–
y
Campus Estado de México—Raúl Monroy
Enfoque sintáctico versus
enfoque semántico
• Satisfacción e inferencia están relacionadas
por dos propiedades:
– Corrección:
– Calidad de cobertura:
• Corrección y calidad de cobertura no son
conceptos cuyo sentido es absoluto en
Lógica
Campus Estado de México—Raúl Monroy
Conclusiones
• Algunos cálculos son menos estructurados
que otros
• Cálculos estructurados permiten la
construcción de procedimientos de
demostración, algunos de los cuales a su
vez permiten construir un procedimiento de
decisión
• Lógica de proposiciones es soluble
Campus Estado de México—Raúl Monroy