Download NUEVO LogicTema4b

Tema 4. Cálculo deductivo en
lógica proposicional
b) Deducibilidad, teorema,
interdeducibilidad
Deducible
• Una fórmula  es deducible de una fórmula  si es
posible obtener  desde  aplicando una serie de
reglas de inferencia.
• Ejemplos:
q es deducible de (p  q) (Eliminación de conyuntor)
(r  s) es deducible de r (Introducción de disyuntor)
p no es deducible de (p  q)
r no es deducible de (q  r)
Deducible
• En general, una fórmula  es deducible de un
conjunto de fórmulas{1... n} si es posible obtener 
desde {1... n} aplicando una serie de reglas de
inferencia.
• Ejemplos:
q es deducible de {(p  q), p} (Modus ponens)
r es deducible de {(r  p), (q  ¬p) (Eliminación de
conyuntor, Eliminación de disyuntor por negación)
Teorema
• Las reglas de Reducción al Absurdo e Introducción del
Condicional permiten empezar una deducción sin utilizar
ninguna premisa.
• Si podemos cerrar la RA o la ICd con la que hemos comenzado,
la fórmula así obtenida será una que no requiere de premisa
alguna para su demostración.
• Ejemplo:
 1. p
 2. ¬q  p
 3. q  p
4. p  (q  p)
(hipótesis)
ID 1
DCD 2
ICd 1-3
Teorema
• Este tipo de fórmula demostrable sin premisas se llama
TEOREMA.
• Dado que un teorema es demostrable sin premisa alguna, eso
significa que un teorema es deducible desde cualquier otra
fórmula. El papel de esta fórmula es en realidad irrelevante:
1. r
premisa
 2. ¬(p  (q  p))
(hipótesis)
 3. p  ¬ (q  p)
NCC 1
Como se ve, la
 4. ¬(q  p)
EC 2
fórmula de la
 5. q  ¬p
NCC 3
premisa no desempeña
 6. p
EC 2
papel alguno.
 7. ¬p
EC 4
 8. p  ¬p
IC 5,6
9. ¬¬(p  (q  p))
RA 1-7
10. p  (q  p)
DN 8
Teorema
• Los teoremas no tienen por qué ser más difíciles de
demostrar que las derivaciones con premisas. La
dificultad depende de la complejidad de la fórmula a
obtener, no del hecho de que empleemos premisas o no.
• De hecho, demostrar un teorema plantea una restricción
en relación al modo de comenzar el ejercicio:
necesariamente debe empezar con la introducción de un
supuesto, bien con vistas a una Reducción o a una
Introducción de Condicional.
Teorema
•
Cualquier fórmula demostrable desde un teorema,
debe ser a su vez un teorema.
• Supongamos que  es un teorema y que  es
demostrable desde . Entonces existe la secuencia
siguiente de pasos:
1. Demostramos  sin premisas
2. Aplicamos reglas de inferencia
3. Obtenemos 
•
Como se ve,  ha sido obtenida sin utilizar tampoco
premisa alguna; por tanto,  es también un teorema
Interdeducibilidad
•
•
Si una fórmula  es deducible desde  y  a su vez es
deducible desde , decimos de ellas que son
INTERDEDUCIBLES.
Por ejemplo, ¬(p  (q  r)) y ¬((¬q ¬p)  r) lo son:
1. ¬(p  (q  r))
2. p  ¬(q  r)
3. p
4. ¬¬p
5. ¬(q  r)
6. ¬q  ¬r
7. ¬q  ¬¬p
8. ¬(¬q  ¬p)
9. ¬r
Pr
10. ¬(¬q  ¬p)  ¬r IC 8,9
NCC1 11. ¬((¬q  ¬p)  r) NDC 10
EC 2
DN 4
EC 2
NDC 5
IC 6, 4
NCC 7
EC 6
Interdeducibilidad
•
•
Si una fórmula  es deducible desde  y  a su vez es
deducible desde , decimos de ellas que son
INTERDEDUCIBLES.
Por ejemplo, ¬(p  (q  r)) y ¬((¬q ¬p)  r) lo son:
1. ¬((¬q ¬p)  r)
 2. p  (q  r)
 3. ¬(¬q ¬p)  ¬r
 4. ¬(¬q ¬p)
 5. ¬q  ¬¬p
 6. ¬q
 7. ¬r
8. ¬q  ¬r
9. ¬(q  r)
10. ¬p
11. ¬¬p
Pr
hip
NDC 1
EC 3
NCC 4
EC 5
EC 3
IC 6,7
NDC 8
EDN 2, 9
EC 5
 12. ¬p  ¬¬p IC 10,11
13. ¬(p  (q  r)) RA 2-12
Paralelismo sintáctico-semántico
•
Hay un paralelismo entre la tríada de propiedades
que acabamos de ver y las nociones semánticas
estudiadas el tema anterior:
SEMÁNTICO
SINTÁCTICO
Consecuencia lógica
Deducibilidad
Verdad lógica
Teorema
Equivalencia
Interdeducibilidad
Paralelismo sintáctico-semántico
•
En otras palabras, da la impresión de que:
a) Las consecuencias lógicas de  son deducibles desde
 y, a la inversa, lo que es deducible desde  es
consecuencia lógica de .
b) Toda verdad lógica constituye un teorema y, a la
inversa, todo teorema es una verdad lógica
c) Dos fórmulas  y  equivalentes son interdeducibles y,
a la inversa, dos fórmulas interdeducibles son
equivalentes
Paralelismo sintáctico-semántico
•
Esta impresión es correcta: (a), (b) y (c) se cumplen.
Pero decir que da la impresión no es suficiente:
demostrar que (a), (b) y (c) se cumplen es tarea de la
METALÓGICA.
•
Esta disciplina se encarga de investigar qué
propiedades tienen los sistemas lógicos.
•
En virtud de cumplir (a), por ejemplo, diremos que el
cálculo de la lógica proposicional es COMPLETO y
CORRECTO
•
No todo sistema lógico tiene estas propiedades.