Tema Cálculo deductivo en lógica proposicional



Descargar 25,07 Kb.
Fecha de conversión20.03.2017
Tamaño25,07 Kb.

Tema 4. Cálculo deductivo en lógica proposicional

  • a) Deducción y reglas de inferencia
  • “Al igual que cualquier otro arte, la Ciencia de la Deducción
  • y el Análisis sólo puede dominarse a través del estudio
  • prolongado y paciente, y no es la vida tan larga como para
  • que ningún mortal alcance en ello el mayor grado posible
  • de perfección”
  • Sherlock Holmes
  • en Estudio en Escarlata (A. Conan Doyle)

Qué es una deducción: un juego de lógica

  • Se ha robado un importante botín. El criminal (o criminales) se dio a la fuga en un coche. Scotland Yard decide interrogar a tres sospechosos, Andy, Bill y Carl, y consigue determinar los hechos siguientes:
  • (i) En el robo no está implicada ninguna otra persona salvo A, B o C.
  • (ii) C nunca trabaja sin llevar a A (y es posible que otros) como cómplice.
  • (iii) B no sabe conducir.
      • ¿ES ANDY CULPABLE O INOCENTE?

Qué es una deducción: un juego de lógica

  • En juegos como éste se nos pide que deduzcamos la información que se pide a partir de la información dada.
  • En este caso la información que se pide es determinar si A es culpable.
  • Veamos un par de modos típicos de razonar para intentar resolver el juego:

Qué es una deducción: un juego de lógica

  • “Supongamos que A es inocente”
    • Dado que C nunca trabaja sin A, si A es inocente, C debe ser también inocente
    • Dado que el criminal huyó en coche y que B no sabe conducir, B no pudo cometer el robo solo: tuvo que ir con A o con C. Así que si A y C son inocentes, B también es inocente.
    • Así que si A es inocente, también lo son B y C. Pero sabemos que al menos uno es culpable
  • 5) Por tanto, no puede ser que A sea inocente

Qué es una deducción: un juego de lógica

  • 1’) Tenemos 3 posibilidades: A, B o C.
  • 2’) Si A lo hizo, A es culpable.
  • 3’) Si C lo hizo, lo hizo con A, así que A también sería culpable en este caso
  • 4’) Si B lo hizo, lo hizo con A o con C:
  • -si lo hizo con A, A es culpable
  • -si lo hizo con C, entonces (por 3’) también lo hizo con A, así que A es culpable
  • 5’) Por tanto, A es culpable en cualquier caso

Qué es una deducción

  • En una deducción progresamos a partir de la información conocida, hasta alcanzar cierta información desconocida que nos interesa obtener
  • La información conocida actúa como las premisas de un argumento, y la desconocida como la conclusión
  • Lo que caracteriza que una deducción esté bien hecha es que cada paso que demos sea seguro: cada nueva información debe seguirse de las anteriores

Qué es una deducción: Reglas

  • Es posible captar por medio de reglas los pasos más típicos que efectuamos cuando llevamos a cabo una deducción
  • Si una regla está bien elegida, nos conducirá desde cierto enunciado E a otro E’ que es consecuencia lógica de E
  • El proceso por el que pasamos de E a E’ es una inferencia lógica y la regla que da cuenta de dicho paso es una regla de inferencia

Qué es una deducción: Reglas

  • Hay reglas que intentan captar el “modo natural” de proceder cuando razonamos. Al sistema que se basa en tales reglas lo llamamos cálculo de deducción natural
  • La idea es recoger y sistematizar las reglas informales que aplicamos, v.g., en razonamientos como el del juego
  • Una vez formuladas de manera abstracta, podremos también aplicar las reglas a nuestras fórmulas de L0, de manera que podamos saber cómo obtener unas fórmulas a partir de otras

Reglas de inferencia primitivas

  • Vamos a ver un conjunto de reglas de inferencia básicas o primitivas para la deducción natural
  • Dado que tenemos 5 conectivas, vamos a definir dos reglas relacionadas con cada una de ellas, una de introducción de la conectiva, y otra para su eliminación
  • Las presentaremos primero de manera informal, para caracterizarlas después de modo más formal

Introducción del Conyuntor: IC

  • Premisas:
  • El asesino es zurdo
  • El asesino calza un 45
  • Conclusión:
  • 3. El asesino es zurdo Y calza un 45.

Introducción del Conyuntor: IC

  • ________
  •   
  • p
  • ¬(r  q)
  • ________
  • p  ¬(r  q)
  • q  p
  • ¬r  q
  • ________
  • (q  p)  (¬r  q)

Eliminación del Conyuntor: EC

  • Premisa:
  • El asesino es bizco y usa bombín
  • Conclusión:
  • o bien:
  • 2’. El asesino usa bombín

Eliminación del Conyuntor: EC

  •      
  • ________ ________
  •  
  • r  (p  ¬q) r  (p  ¬q)
  • ________ ________
  • r p  ¬q

Doble Negación: DN

  • Premisa:
  • No es el caso que el asesino no fume en pipa
  • Conclusión:
  • 2. El asesino fuma en pipa
  • Premisa:
  • El asesino tiene bigote
  • Conclusión:
  • 2. No es el caso que el asesino no tenga bigote

Doble Negación: DN

  • ¬¬  
  • _____ _____
  •  ¬¬ 
  • ¬¬ (r  q) r  q
  • _____ _____
  • r  q ¬¬ (r  q)
  • ¡CUIDADO!
  • ¬(¬r  q)
  • _____
  • r  q 

Introducción del Disyuntor: ID

  • Premisa:
  • El asesino mide 1,90m
  • Conclusión:
  • 2. El asesino mide 1,90m o veranea en Cancún
  • 2’. El asesino veranea en Cancún o mide 1,90m

Introducción del Disyuntor: ID

  • _____
  •   
  • p
  • _____
  • p  r
  • p  ¬q
  • _____
  • (r  t)  (p  ¬q)
  • _____
  •   

Eliminación del Disyuntor: ED (también Prueba por Casos o Dilema)

  • El asesino huyó en coche o en patinete
  • Si huyó en coche, se esconde en Cádiz
  • Si huyó en patinete, se esconde en Cádiz
  • Conclusión:
  • 4. El asesino se esconde en Cádiz

Eliminación del Disyuntor: ED

  •   
  •   
  •   
  • ______
  • r  ¬q
  • r  (s  t)
  • ¬q  (s  t)
  • ______
  • s  t
  • p  (r  q)
  • p  ¬q
  • (r  q)  ¬q
  • ______
  • ¬q

Eliminación del Condicional o Modus Ponens: MP

  • Premisas:
  • Si Gutiérrez es culpable, Fefa le encubre
  • Gutiérrez es culpable
  • Conclusión:
  • 3. Fefa encubre a Gutiérrez

Modus Ponens: MP

  •   
  • ______
  • (p  q)  ¬s
  • p  q
  • ______
  • ¬s
  • ¬(p  (¬r  q))  (s  ¬q)
  • ¬(p  (¬r  q))
  • ______
  • s  ¬q

Introducción del Bicondicional: IB

  • Premisas:
  • Si el asesino es calvo, entonces bebe vodka
  • Si el asesino bebe vodka, entonces es calvo
  • Conclusión:
  • 3. El asesino es calvo si, y sólo si, bebe vodka

Introducción del Bicondicional: IB

  •   
  •   
  • ______
  •   
  • r  ¬¬q
  • ¬¬q  r
  • ______
  • r  ¬¬q
  • (p  r)  ¬(q  p)
  • ¬(q  p)  (p  r)
  • ______
  • (p  r)  ¬(q  p)

Eliminación del Bicondicional: EB

  • Premisa:
  • Gutiérrez es culpable si, y sólo si, ama a Fefa
  • Conclusión:
  • 2. Si Gutiérrez es culpable, entonces ama a Fefa
  • o bien:
  • 2’. Si Gutiérrez ama a Fefa, entonces es culpable

Eliminación del Bicondicional: EB

  •      
  • ______ ______
  •      
  • (p  ¬p)  q
  • ______
  • (p  ¬p)  q
  • (p  ¬p)  q
  • ______
  • q  (p  ¬p)

Premisas y supuestos

  • Las premisas corresponden a la información que nos viene dada de antemano (los datos del problema o las fórmulas iniciales)
  • A veces tenemos que introducir información hipotética para echar a andar un razonamiento: a esto que introducimos lo llamamos supuesto
  • Equivale a las ocasiones en que razonamos comenzando “Supongamos que...”
  • Hay 2 reglas de inferencia que se basan en el empleo de supuestos:

Reducción al Absurdo: RA

  • Supuesto:
  • (Supongamos que) el asesino no huyó a Cádiz
  •  ...bla bla bla... (cadena de inferencias válidas)
  •  Gutiérrez es dentista y no es dentista
  • Conclusión:
  • 1. El asesino huyó a Cádiz

Reducción al Absurdo: RA

  • En la RA comenzamos por introducir un supuesto, (que corresponde a la negación de aquello que intentamos concluir)
  • Para señalar que se trata de un supuesto y no de una premisa, usamos el símbolo  (abrir hipótesis)
  • A continuación seguimos la deducción aplicando las reglas de inferencia que sea conveniente
  • SI alcanzamos una contradicción, significa que nuestro supuesto inicial era erróneo. Al llegar a la contradicción, cerramos la cadena de inferencias con el símbolo  (cancelar hipótesis).
  • La conclusión será la negación del supuesto

Reducción al Absurdo: RA

  •  ...
  •   ¬ 
  • __________
  • ¬ 
  • demuéstrese p desde (¬p  q) y ¬q
  • 1. ¬p  q Premisa
  • 2. ¬q Premisa
  • 3. ¬p (hipótesis)
  •  4. ¬p  q EB 1
  •  5. q MP 3, 4
  • 6. q  ¬q IC 2, 5
  • 7. ¬¬p RA 3-6
  • 8. p DN 7

Introducción del Condicional: Icd (también Teorema de Deducción)

  • Supuesto:
  • (supongamos que) La víctima fue envenenada
  • ... bla bla bla ... (cadena de inferencias válidas)
  •  El asesino es la condesa Lecquia
  • Conclusión:
  • 1. Si la víctima fue envenenada, el asesino es la condesa Lecquia

Introducción del Condicional: Icd

  • Aquí también introducimos un supuesto. Seguimos con la deducción aplicando las reglas que sea conveniente y llegamos a determinado enunciado.
  • Nuestra conclusión NO ES ESTE ENUNCIADO.
  • La conclusión es un condicional, que tiene como antecedente el supuesto que hemos introducido y como consecuente el enunciado que hemos obtenido a partir de ese supuesto, aplicando reglas de inferencia

Introducción del Condicional: Icd

  • Demuéstrese (¬q  ¬r) desde ¬q  (p  ¬r)
  • 1. ¬q  (p  ¬r) Premisa
  • 2. ¬q (hipótesis)
  •  3. p  ¬r MP 1, 2
  •  4. ¬r EC 3
  • 5. ¬q  ¬r ICd 2-4
  •  ...
  • __________
  •   

Derivación y deducción

  • Normalmente nos interesa saber si una fórmula  se puede obtener desde otras 1 ... n En ese caso lo que tenemos que construir es una derivación desde 1 ... n hasta , de manera que en cada paso de la derivación apliquemos una regla de inferencia.
  • Si conseguimos obtener , diremos que hemos deducido  de 1 ... n

Procedimiento de deducción

  • Se determina cuáles son las premisas y se escribe cada premisa en una línea numerada, comenzando por el 1
  • Se determina cuál es la conclusión, y se deja aparte, marcada con el símbolo |–. Esto es lo queremos demostrar
  • Se aplican reglas de inferencia sobre las premisas y se van derivando nuevas líneas, que se van numerando
  • La deducción termina cuando llegamos a una línea, fuera de toda barra de hipótesis (de la RA o la ICd) que contiene lo que queremos demostrar

Ejemplo de deducción

  • q  r Pr
  • p  s Pr Colocamos las premisas numeradas
  • q  p Pr
  • 4. q hip
  • 5. r MP 1, 4 Junto a cada línea escribimos la regla
  • ... empleada y las líneas a las que se
  • ha aplicado: MP 1, 4 significa que se
  • aplicó Modus Ponens entre 1 y 4
  • Demostrar r  s desde {q  r, p  s, q  p}

Ejemplo de deducción

  • q  r Pr
  • p  s Pr
  • q  p Pr
  • 4. q hip
  • 5. r MP 1, 4
  • 6. r  s ID 5
  • 7. q  (r  s) ICd 4-6
  • ...
  • Demostrar r  s desde {q  r, p  s, q  p}
  • Aunque en la línea 6 ya aparece lo
  • que queremos demostrar, está dentro
  • de una barra abierta por una hipótesis,
  • así que no nos sirve como conclusión.
  • Pero podemos cerrar la barra con la
  • regla de Introducción del Condicional.

Ejemplo de deducción

  • q  r Pr
  • p  s Pr
  • q  p Pr
  • 4. q hip
  • 5. r MP 1, 4
  • 6. r  s ID 5
  • 7. q  (r  s) ICd 4-6
  • 8. p hip
  • 9. s MP 2, 8
  • 10. r  s ID 9
  • 11. p  (r  s) ICd 8-10
  • 12. r  s ED 3, 7, 11
  • Demostrar r  s desde {q  r, p  s, q  p}
  • Podemos introducir todas las hipótesis
  • que necesitemos, pero la deducción no
  • termina hasta obtener lo deseado
  • fuera de las barras de hipótesis.
  • Las fórmulas obtenidas en las líneas 7
  • y 11 están fuera de dichas barras, así que
  • podemos combinarlas sin problemas con
  • la premisa conveniente, en este caso la
  • línea 3.
  • Concluimos la deducción aplicando la
  • Eliminación de la Disyunción en esas
  • tres líneas.

Regla auxiliar: Repetición

  • Podemos repetir cualquier línea ya obtenida, siempre y cuando no la saquemos ilegalmente fuera de unas barras (pero siempre podemos meterla dentro):
  • |– p  q
  • 1. (p  p)  q Pr
  • 2. p hip
  • 3. p Rep 2
  •  4. p  p IC 2, 3
  •  5. q MP 1, 4
  • 6. p  q ICd 2-5
  • |– p  q
  • 1. p hip
  • 2. p  q ID 1
  • 3. p  q Rep 2 ?? 

Reglas derivadas

  • Las reglas de inferencia primitivas son suficientes para hacer todas las derivaciones que queremos
  • Pero a veces nos encontramos con secuencias de pasos que se repiten muy a menudo y que podemos abreviar en forma de regla
  • Estas reglas están derivadas de las primitivas, en el sentido de que lo que ellas hacen podría hacerse igualmente sólo con reglas primitivas, aunque de manera más larga.
  • Al igual que ocurre respecto al número de conectivas, se trata de encontrar un equilibrio en una cantidad de reglas que sea manejable pero suficiente para nuestros fines

Reglas de simetría

  • Disyuntor: SD Conyuntor: SC Bicondicional:SB
  •         
  • _____ ______ ______
  •         
  • Se explican por sí solas y su demostración desde las reglas primitivas es muy sencilla

Modus Tollens: MT

  •    Si el crimen fue en la sala, fue con el puñal
  • ¬  El crimen no fue con el puñal
  • ______
  • ¬ El crimen no fue en la sala
  • Es la recíproca del Ponens
  • y se demuestra fácilmente
  • con la ayuda de éste y la
  • Reducción al Absurdo:
  • p  q Pr
  • ¬q Pr
  • 3. p hip.
  • 4. q MP 1, 3
  • 5. q  ¬q IC 2, 4
  • 6. ¬p RA 3-5

Eliminación del Disyuntor por Negación: EDN (tb Silogismo Disyuntivo o Tollendo Ponens)

  •    El asesino es Rómulo o Remo
  • ¬ El asesino no es Rómulo
  • ______
  •  El asesino es Remo
  • Su demostración es interesante para ver las virtudes de la contradicción, así como Reducciones al Absurdo “anidadas”:

Eliminación del Disyuntor por Negación: EDN

  • 1. p  q Pr
  • 2. ¬p Pr
  • 3. p hip
  • 4. p  ¬p IC 2, 3
  •  5. ¬q hip
  •   6. p  ¬p Rep 4
  •  7. ¬¬q RA 5-6
  •  8. q DN 7
  • 9. p  q ICd 3-8
  • 10. q hip
  • 11. q Rep 10
  • 12. q  q ICd 10-11
  • 13. q ED 1, 9, 12
  • Queremos demostrar q desde (p  q)
  • y ¬p.
  • Al hacerlo, podemos ver en práctica
  • el principio que dice que de una
  • contradicción se sigue cualquier cosa
  • (pasos 5-7). En este caso lo hemos
  • explotado para nuestros fines, pero
  • siempre siguiendo escrupulosamente
  • las reglas de inferencia.
  • Nótese que en 7 podemos obtener la
  • negación de cualquier fórmula  cuya
  • negación pongamos en 5. Pero fuera de
  • las barras (en 9) sólo obtendríamos
  • p  

Leyes de De Morgan

  • Las equivalencias entre conyuntor, disyuntor y condicional pueden explotarse para obtener reglas de inferencia basadas en ellas.
  • Estas equivalencias se conocen como leyes de De Morgan:
  •     ¬(¬  ¬)  ¬(  ¬)
  •     ¬(¬  ¬)  ¬  
  •    ¬(  ¬)  ¬  
  • Al demostrar las reglas, iremos empleando las primitivas y las derivadas ya demostradas

Negación del Disyuntor al Conyuntor: NDC

  • ¬(  )
  • __________
  • ¬  ¬
  • ¬  ¬
  • __________
  • ¬(  )
  • 1. ¬(p  q) Pr
  • 2. p hip
  • 3. p  q ID 2
  • 4. (p  q)  ¬(p  q) IC 1, 3
  • 5. ¬p RA 2-4
  • 6. q hip
  • 7. p  q ID 6
  • 8. (p  q)  ¬(p  q) IC 1, 7
  • 9. ¬q RA 6-8
  • 10. ¬p  ¬q IC 5, 9

Negación del Disyuntor al Conyuntor: NDC

  • ¬(  )
  • __________
  • ¬  ¬
  • ¬  ¬
  • __________
  • ¬(  )
  • 1. ¬p  ¬q Pr
  • 2. p  q hip
  • 3. ¬p EC 1
  • 4. q EDN 2, 3
  • 5. ¬q EC 1
  • 6. q  ¬q IC 4, 5
  • 10. ¬(p  q) RA 2-6

Definición del Condicional por el Disyuntor: DCD

  •   
  • __________
  • ¬  
  • ¬  
  • __________
  •   
  • 1. p  q Pr
  • 2. ¬ (¬p  q) hip
  • 3. ¬¬p  ¬q NDC 2
  • 4. ¬¬p EC 3
  • 5. p DN 4
  • 6. q MP 1, 5
  • 7. ¬q EC 3
  • 8. q  ¬q IC 6, 7
  • 9. ¬p  q RA 2-8

Definición del Condicional por el Disyuntor: DCD

  •   
  • __________
  • ¬  
  • ¬  
  • __________
  •   
  • 1. ¬p  q Pr
  • 2. p hip
  • 3. ¬¬p DN 2
  •  4. q EDN 1, 3
  • 5. p  q ICd 2-4

Negación del Conyuntor al Disyuntor: NCD

  • ¬(  )
  • __________
  • ¬  ¬
  • ¬  ¬
  • __________
  • ¬(  )
  • 1. ¬(p  q) Pr
  • 2. ¬ (¬p  ¬q) hip
  • 3. ¬¬p  ¬¬q NDC 2
  • 4. ¬¬p EC 3
  • 5. ¬¬q EC 3
  • 6. p DN 4
  • 7. q DN 5
  • 8. p  q IC 6,7
  • 9. (p  q)  ¬(p  q) IC 1, 8
  • 10. ¬p  ¬q RA 2-6

Negación del Conyuntor al Disyuntor: NCD

  • ¬(  )
  • __________
  • ¬  ¬
  • ¬  ¬
  • __________
  • ¬(  )
  • Queda como ejercicio la demostración en la dirección opuesta

Negación del Condicional al Conyuntor: NCC

  • ¬(  )
  • __________
  •   ¬
  •   ¬
  • __________
  • ¬(  )
  • Quedan como ejercicio las dos demostraciones


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal