Deduccion Natural
description
Transcript of Deduccion Natural
![Page 1: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/1.jpg)
Matemáticas Discretas
INFERENCIA ÓDEDUCCIÓN
![Page 2: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/2.jpg)
Inferencia
� Inferir conclusión a partir de premisasaplicando reglas de inferencia� Premisas: hipótesis, supuestos básicos� Conclusión: proposición a probar� Reglas de Inferencia: medio para
extraer conclusiones a partir de premisas
![Page 3: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/3.jpg)
Inferencia
� Prueba formal: aplicación de reglas de inferencia para derivar la conclusión
� Conclusión válida: conclusión a la quese llega aplicando reglas de inferencia
![Page 4: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/4.jpg)
� Mecanismos de inferencia o deducción� Tablas de verdad� Procedimiento de resolución� Reglas de inferencia....
Inferencia
![Page 5: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/5.jpg)
Deducción natural
� Reglas Básicas� Regla P: Una premisa se puede
introducir en cualquier paso de la deducción
� Regla T: Una fórmula S se puedeincorporar en la deducción, si S estátautológicamente implicada por una o más fórmulas anteriores en la deducción
![Page 6: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/6.jpg)
Deducción natural
� Reglas Básicas� Regla PCSi una fórmula s se pude deducir de otrafórmula r y un conjunto de premisas, entonces el enunciado (r → s) se puedededucir a partir del conjunto de premisasunicamente(p ∧ r ) → s ≡ p → (r → s)
![Page 7: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/7.jpg)
Reglas de Deducción natural
� Simplificación(p ∧ q) → p ( p ∧ q ╞ p)(p ∧ q) → q ( p ∧ q ╞ q)
� Adiciónp → p ∨ qq → p ∨ q
� Conjunción(p) ∧ (q) → (p ∧ q)
![Page 8: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/8.jpg)
Reglas de Deducción natural
� Modus Ponens(p ∧ (p → q)) → q
� Modus Tollens(¬q ∧ (p → q)) → ¬p
� Silogismo Hipotético[(p→q) ∧ (q →r)] → (p →r)
� Silogismo Disyuntivo[(p ∨ q) ∧ ¬p] → q
![Page 9: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/9.jpg)
Reglas de Deducción natural
� Resolución
[(p ∨ q) ∧ (¬p ∨ r )] → (q ∨ r)� Dilema
[(p ∨ q) ∧ (p → r) ∧ (q → r)] → r
![Page 10: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/10.jpg)
Argumentos válidos: Ejemplo
Si llueve mucho, el viaje será dificil. Si losestudiantes llegan a tiempo entonces el viaje no fué dificil. Los estudiantes llegaron a tiempo. Por tanto, no llovió mucho
p: llueve muchoq: el viaje es dificil
r: los estudiantes llegaron a tiempo
![Page 11: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/11.jpg)
Argumentos válidos: Ejemplodeducción natural
Premisas: p → q, r → ¬q, r
Conclusión: ¬pArgumento Razón1. p → q Regla P2. ¬q → ¬p contrareciproca de 13. r → ¬q Regla P4. r → ¬p Silogismo Hipotético (2,3)5. r Regla P6. ¬p Modus Ponens (4,5)
![Page 12: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/12.jpg)
Argumentos válidos: EjemploRefutación
Premisas: p → q, r → ¬q, r
Conclusión: ¬p1. p q2. r q3. r4. p5. q Resolvente(1,4)6. r Resolvente (2,5)7. □ Resolvente (3,6)
![Page 13: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/13.jpg)
Ejemplo
Si me mandas un e-mail entonces acabaré de escribir el programa. Si no me mandas un e-mail me iré a la camatemprano y si me voy a la cama temprano, me levantarédescansado. Por lo tanto, si no acabo de escribir el programa, me levantaré descansado.
p: me mandas un e-mailq: acabaré de escribir el programar: me iré a la cama tempranos: me levantaré descansado
![Page 14: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/14.jpg)
Ejemplo
1. p→ q
2. ¬p→ r3. r→ s
4. ¬q→ s
![Page 15: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/15.jpg)
Ejemplo: refutación por resolución
1. p q2. p r3. r s4. q5. s6. p Resol(1,4)7. r Resol(2,6)8. s Resol(3,7)9. □ Resol(5,8)
![Page 16: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/16.jpg)
Argumentos válidos: Ejemplo deducciónnatural
Premisas: p → q, ¬p → r, r → s
Conclusión: ¬q → sArgumento Razón1. p → q Hipótesis2. ¬q → ¬p contrareciproca de 13. ¬ p → r Hipótesis4. ¬q → r Silogismo Hipotético (2,3)5. r → s Hipótesis6. ¬q →s Silogismo Hipotético (4,5)
![Page 17: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/17.jpg)
Inferencia en LP: Algunas Reglas
� Particularización Universal
p(c) es verdadera, c es un elemento del dominiocuando la premisa ∀x p(x) es verdadera
∀x p(x)p(c)
![Page 18: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/18.jpg)
Inferencia en LP: Algunas Reglas
� Generalización Universal
Se afirma que ∀x p(x) es verdadera, dada la premisa que p(c) es verdadera para todoelemento c del dominio.
p(c), para un c arbitrario
∀x p(x)
![Page 19: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/19.jpg)
Inferencia en LP: Algunas Reglas
� Particularización Existencial
es posible afirmar que p(c) es verdadera, cuando ∃ x p(x) es verdadera
∃x p(x)p(c) para algún elemento c
![Page 20: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/20.jpg)
Inferencia en LP: Algunas Reglas
� Generalización Existencial
es posible concluir que ∃x p(x) es verdadera, cuando se conoce un elemento particular c conp(c) verdadera
p(c) para algun elemento c
∃x p(x)
![Page 21: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/21.jpg)
Ejemplo de razonamiento
Todos los hombres son mortales. Sócrates eshombre. Por lo tanto, Sócrates es mortal
mortal(x): x es mortal hombre(x): x es hombre
∀x (hombre(x)→mortal(x)) ∧∧∧∧ hombre(s) ╞ mortal(s)
![Page 22: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/22.jpg)
Ejemplo de razonamiento
∀x (hombre(x)→mortal(x)) ∧∧∧∧ hombre(s) ╞ mortal(s)Premisas: ∀x (hombre(x)→mortal(x)) , hombre(s) Conclusión: mortal(s)Argumento Razón1. ∀x (hombre(x)→mortal(x)) Hipótesis
2. hombre(s)→mortal(s)) Particularizac. Universal(1)
3. hombre(s) Hipótesis
4. mortal(s) Modus Ponens (2,3)
![Page 23: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/23.jpg)
Ejemplo
Un estudiante de esta clase sabe cómo escribirprogramas en JAVA. Todo el que sepa cómoescribir programas en JAVA puede conseguir un trabajo bien pagado. Por lo tanto, alguien en esta clase puede conseguir un trabajo bienpagado
![Page 24: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/24.jpg)
Simbolización
c(x): x está en clase, j(x): x sabe cómo escribirprogramas JAVA, t(x):x puede conseguir un buen trabajo.
Hipótesis
∃x(c(x) ∧∧∧∧ j(x))∀x (j(x)→ t(x))Conclusión
∃x(c(x) ∧∧∧∧ t(x))
![Page 25: Deduccion Natural](https://reader034.fdocumento.com/reader034/viewer/2022050723/55cf8f03550346703b980804/html5/thumbnails/25.jpg)
Prueba
1. ∃x(c(x) ∧∧∧∧ j(x)) Hipótesis2. c(a) ∧∧∧∧ j(a) Particularización existencial (1)3. c(a) Simplificacion (2)4. j(a) Simplificación (2)
5. ∀x (j(x)→ t(x)) Hipótesis6. j(a)→ t(a) Particularización Universal7. t(a) Modus Ponens (4,6)
8. c(a) ∧∧∧∧ t(a) Conjunción (3,7)9. ∃x(c(x) ∧∧∧∧ t(x)) Generalización Existencial