Post on 11-Mar-2020
Proceso de admisión 2019 – Curso de matemáticasLógica computacional
Dr. Eduardo A. RODRÍGUEZ TELLO
CINVESTAV-Tamaulipas
20 de mayo de 2019
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 1 / 80
1 Teoría de inferencia y demostración en lógica proposicional
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 2 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 3 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostración
Inferencia y deducción son procesos muy importantes en la lógicaproposicional
Deducción. Inicia con un conjunto de fórmulas lógicas(proposiciones simbolizadas) que se denominan premisas y sebusca entonces usar reglas de inferencia para que estas premisasnos conduzcan a otras fórmulas denominadas conclusiones
La idea principal de la inferencia lógica es que de premisasverdaderas se obtienen sólo conclusiones que son verdaderas
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 4 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus ponendo ponens
La regla de inferencia llamada modus ponendo ponens (en latín: el modo que, alafirmar, afirma) permite demostrar Q A partir de P → Q y P
Ejemplo:
Premisa 1: Si él está en partido de fútbol, entonces él está en elestadioPremisa 2: Él está en el partido de fútbolConclusión: Él está en el estadio
Sea
P = “Él está en el partido de fútbol”Q = “Él está en el estadio”
Entonces
Premisa 1: P → Q (antecedente P , consecuente Q)Premisa 2: PConclusión: Q
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 5 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus ponendo ponens
Otros ejemplos:
a. R → SR
∴ S
b. PP → ¬Q
∴ ¬Q
c. P ∧Q → RP ∧Q
∴ R
Observe que en el ejemplo b. la condicional (P → ¬Q) está como segundapremisa y P es el antecedente
Cuando el modus ponendo ponens (o cualquier otra regla de inferencia) seaplica el orden de las premisas es indiferente
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 6 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónDemostraciones
Cuando se emplea una regla de inferencia para pasar de unconjunto de proposiciones a otra proposición (conclusión) sedemuestra que la última proposición es consecuencia lógica delas otras
También puede expresarse como que se ha derivado laconclusión de las premisas, o que la conclusión se infiere de (esimplicada por) las premisas
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 7 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónDemostraciones
Un ejemplo de demostración:
R → S P(1)R P(2)S PP(3)
Cada línea de la demostración está numerada
Las premisas están identificadas con P
La línea (3) se deduce a partir de ellas usando el modus ponendo ponens,indicado con PP
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 8 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónDemostraciones de dos pasos
Algunas veces no es posible ir directamente de las premisas a laconclusión en un solo paso
Cada vez que se deduce una proposición por medio de una regla,esta proposición puede utilizarse junto con las premisas paradeducir otra proposición
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 9 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónDemostraciones de dos pasos
Ejemplo de demostración de dos pasos:
Se requiere probar la proposición C, para ello se requieren dos pasos, cada unousando el modus ponendo ponens
Estos dos pasos son las líneas (4) y (5) de la siguiente demostración
A → B P(1)B → C P(2)A P(3)B PP 1, 3(4)C PP 2, 4(5)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 10 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónDemostraciones de dos pasos
Un ejemplo más de demostración de dos pasos:
Se requiere probar la proposición R
S → ¬T P(1)S P(2)
¬T → R P(3)¬T PP 1, 2(4)R PP 3, 4(5)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 11 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónRegla de la doble negación
Es una regla simple que permite pasar de una premisa única a laconclusión
Por ejemplo:No ocurre que Ana no es una estudiante
¿Qué conclusión podemos sacar de esta premisa?Ana es una estudiante
Esta regla también actúa e sentido contrario Por ejemplo, de laproposición:
Juan toma taxi para ir a la escuela
Se puede concluir la negación de su negación:No ocurre que Juan no toma taxi para ir a la escuela
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 12 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónRegla de la doble negación
La regla de la doble negación (abreviada DN) tiene dos formassimbólicas:
P∴ ¬¬P
¬¬P∴ P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 13 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónRegla de la doble negación
Ejemplo 1:
R P(1)¬¬R DN 1(2)
Ejemplo 2:
¬¬(P ∧Q) P(1)P ∧Q DN 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 14 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo tollens
La regla de inferencia llamada modus tollendo tollens (en latín: elmodo que, al negar, niega) permite pasar de dos premisas (a) unaproposición condicional, y (b) una proposición que niega elconsecuente, a una conclusión que niega el antecedente
Se abrevia TT y simbólicamente se representa así:
P → Q¬Q
∴ ¬P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 15 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo tollens
Ejemplo:
Premisa 1: Si tiene luz propia, entonces el astro es una estrellaPremisa 2: El astro no es una estrellaConclusión: Por lo tanto no tiene luz propia
Sea
P = “Tiene luz propia”Q = “El astro es una estrella”
Entonces
Premisa 1: P → QPremisa 2: ¬QConclusión: ¬P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 16 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo tollens
Ejemplo 1:
Q ∧R → S P(1)¬S P(2)
¬(Q ∧R) TT 1, 2(3)
Ejemplo 2:
P → ¬Q P(1)¬¬Q P(2)¬P TT 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 17 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo tollens
Veamos un ejemplo donde se empleen las tres reglas vistas hastaahora. Se quiere demostrar ¬¬R:
P → Q P(1)¬Q P(2)¬P → R P(3)¬P TT 1, 2(4)R PP 3, 4(5)
¬¬R DN 5(6)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 18 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo tollens
Otro ejemplo adicional. Se quiere demostrar A:
¬A → ¬B P(1)B P(2)
¬¬B DN 2(3)¬¬A TT 1, 3(4)
A DN 4(5)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 19 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
Se tienen dos proposiciones como premisas:Jorge es adultoMaría es adolescente
Si ambas son verdaderas, entonces se podrían juntar en unaproposición molecular con el operador de enlace y (∧)
Esto daría lugar a la proposición verdadera siguiente:Jorge es adulto y María es adolescente
Si ambas premisas son ciertas, la conclusión será cierta
La regla que permite hacer esto se denomina regla de adjunción(abreviada A)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 20 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
La regla de adjunción simbólicamente se representa así:
PQ
∴ P ∧Q o también Q ∧ P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 21 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
Ejemplo 1:
Q ∧ S P(1)¬T P(2)¬T ∧ (Q ∧ S) A 1, 2(3)
Ejemplo 2:
A ∨B P(1)B ∨ C P(2)
(A ∨B) ∧ (B ∨ C) A 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 22 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
La regla de simplificación (abreviada S) permite pasar de unaconjunción a cada una de las dos proposiciones que están unidascon el operador de enlace y (∧)
Suponga que se tiene la premisa:El cumpleaños de María es el viernes y el mío es el sábado
De esta premisa se pueden deducir dos proposiciones(conclusiones):
El cumpleaños de María es el viernesEl mío es el sábado
Si la premisa es cierta, ambas conclusiones también lo serán
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 23 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
La regla de simplificación simbólicamente se representa así:
P ∧Q∴ P o también Q
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 24 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
Ejemplo 1:
(P ∨Q) ∧R P(1)R S 1(2)
Ejemplo 2:
Q ∧ S P(1)Q S 1(2)
Ejemplo 3:
(P ∨Q) ∧R P(1)P ∨Q S 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 25 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónAdjunción y simplificación
Ejemplo 4:
(P ∧Q) ∧R P(1)(P ∧Q) S 1(2)
Ejemplo 5:
T ∧ ¬V P(1)¬V S 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 26 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo ponens
La regla de inferencia llamada modus tollendo ponens (en latín: elmodo que, al negar, afirma) establece que negando un miembrode una disyunción se afirma el otro miembro
Se abrevia TP y simbólicamente se representa así:
P ∨Q¬P
∴ Q
P ∨Q¬Q
∴ P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 27 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo ponens
Ejemplo:
Premisa 1: Esta sustancia contiene hidrógeno o contiene oxígenoPremisa 2: Esta sustancia no contiene hidrógenoConclusión: Esta sustancia contiene oxígeno
Sea
P = “Esta sustancia contiene hidrógeno”Q = “Esta sustancia contiene oxígeno”
Entonces
P ∨Q P(1)¬P P(2)Q TP 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 28 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo ponens
Ejemplo 1:
(P ∧Q) ∨ S P(1)¬S P(2)P ∧Q TP 1, 2(3)
Ejemplo 2:
¬S ∨ T P(1)¬T P(2)¬S TP 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 29 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración
Reglas básicas de inferencia y demostraciónModus tollendo ponens
Ejemplo 3:
¬P ∨ ¬Q P(1)¬¬P P(2)¬Q TP 1, 2(3)
Ejemplo 4:
(P ∧Q) ∨ (R ∧ S) P(1)¬(P ∧Q) P(2)
R ∧ S TP 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 30 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 31 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
Deducción proposicional
Hasta ahora hemos aprendido a efectuar deducciones simples
Consideremos ahora algunas un poco más avanzadas
Si la ballena es un mamífero entonces toma oxígeno del aire. Sitoma oxígeno del aire, entonces no necesita branquias. Laballena es un mamífero y vive en el océano. Por lo tanto, nonecesita branquias.
El primer paso es simbolizar el razonamiento anterior
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 32 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
Deducción proposicional
Sea
W = “La ballena es un mamífero”
O = “Toma oxígeno del aire”
G = “Necesita branquias”
H = “Habita en el océano”
Entonces las premisas y la conclusión quedan de la siguiente forma:
Premisa 1: W → O
Premisa 2: O → ¬G
Premisa 3: W ∧H
Conclusión: ¬G
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 33 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
Deducción proposicional
La deducción proposicional se puede escribir así:
W → O P(1)O → ¬G P(2)W ∧H P(3)W S 3(4)O PP 1, 4(5)
¬G PP 2, 5(6)
Así puesto que ¬G representa la proposición “No necesita branquias” se ha
demostrado que la conclusión del razonamiento es válida. Esto es un ejemplo dededucción formal.
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 34 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
Deducción proposicional
Veamos otro ejemplo más
Si la enmienda no fue aprobada entonces la Constitución quedacomo estaba. Si la Constitución queda como estaba entonces nopodemos añadir nuevos miembros al comité. O podemos añadirnuevos miembros al comité o el informe se retrasará un mes. Peroel informe no se retrasará un mes. Por lo tanto la enmienda fueaprobada.
Simbolicemos este razonamiento
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 35 / 80
Teoría de inferencia y demostración en lógica proposicional Deducción proposicional
Deducción proposicionalSea
A = “La enmienda fue aprobada”
C = “La Constitución queda como estaba”
M = “Podemos añadir nuevos miembros al comité”
R = “El informe se retrasará un mes”
Entonces la deducción proposicional se puede escribir así:
¬A → C P(1)
C → ¬M P(2)
M ∨R P(3)
¬R P(4)
M TP 3, 4(5)
¬C TT 2, 5(6)
A TT 1, 6(7)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 36 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 37 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionales
Hasta ahora hemos visto sólo algunas reglas básicas deinferencia
Esto limita un poco las deducir que podemos realizar
Por esta razón a continuación estudiaremos reglas de inferenciaadicionales
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 38 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de la adición
La ley de la adición (abreviada LA) expresa el hecho que si setiene una proposición cierta, entonces la disyunción de esaproposición y otra cualquiera será también cierta
Dado P , entonces la proposición P ∨Q es consecuencia
Ejemplo: suponga que la siguiente premisa es ciertaEste libro es azul
Entonces se sabe que la proposición siguiente ha de ser tambiéncierta
Este libro es azul o es nuevo
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 39 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de la adición
Ejemplo 1:
Q P(1)Q ∨ ¬R LA 1(2)
Ejemplo 2:
¬R P(1)S ∨ ¬R LA 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 40 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de la adición
Ejemplo 3:
T ∧ S P(1)(T ∧ S) ∨R LA 1(2)
Ejemplo 4:
T ∨R P(1)(P ∧ S) ∨ (T ∨R) LA 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 41 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo hipotético
La ley del silogismo hipotético es una forma de argumento válidoque consiste en un silogismo con una sentencia condicional parauna o ambas de sus premisas
Se abrevia HS y se representa simbólicamente así:
P → QQ → R
∴ P → R
Recordemos: un silogismo es un tipo de argumento lógico que aplica razonamiento deductivo para llegar a una conclusión
basado en dos o más proposiciones que asume son verdaderas
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 42 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo hipotético
Ejemplo: de las premisasPremisa 1: Si hace calor, entonces José va nadarPremisa 2: Si José va a nadar, entonces arregla la casa despuésde comer
Se puede obtener la conclusión: Si hace calor, entonces arregla la casadespués de comer
Para simbolizar el razonamiento, seaD = “Hace calor”S = “José va a nadar”H = “Arregla la casa después de comer”
Entonces
D → S P(1)
S → H P(2)
D → H HS 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 43 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo hipotético
Ejemplo 1:
¬P → ¬Q P(1)¬Q → ¬R P(2)¬P → ¬R HS 1, 2(3)
Ejemplo 2:
¬P → ¬Q ∨R P(1)¬Q ∨R → ¬T P(2)
¬P → ¬T HS 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 44 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo hipotético
Ejemplo 3:
S → T P(1)T → R ∨Q P(2)S → R ∨Q HS 1, 2(3)
Ejemplo 4:
(P → Q) → R P(1)R → (Q ∧ T ) P(2)
(P → Q) → (Q ∧ T ) HS 1, 2(3)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 45 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo disyuntivo
La ley del silogismo disyuntivo empieza con una disyunción y doscondicionales que tienen como antecedente a cada una de laspremisas de la disyunción. La conclusión es otra disyunción delos consecuentes de las condicionales.
Se abrevia DS y se representa simbólicamente así:
P ∨QP → RQ → S
∴ R ∨ S o también S ∨R
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 46 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo disyuntivo
Ejemplo: de las premisas
Premisa 1: Llueve o el campo está secoPremisa 2: Si llueve, entonces jugaremos adentroPremisa 3: Si el campo está seco, entonces jugaremos baloncesto
Se puede obtener la conclusión: jugaremos adentro o jugaremos al baloncesto
Para simbolizar el razonamiento, sea
R = “Llueve”
D = “El campo está seco”
P = “Jugaremos adentro”
B = “Jugaremos al baloncesto”
Entonces
R ∨D P(1)
R → P P(2)
D → B P(3)
P ∨B DS 1, 2, 3(4)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 47 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo disyuntivo
Ejemplo 1:
¬P ∨Q P(1)¬P → ¬R P(2)Q → S P(3)
¬R ∨ S DS 1, 2, 3(4)
Ejemplo 2:
P ∨Q P(1)P → ¬R P(2)Q → ¬S P(3)
¬S ∨ ¬R DS 1, 2, 3(4)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 48 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey del silogismo disyuntivo
Ejemplo 3:
¬P ∨ ¬Q P(1)¬P → R P(2)¬Q → S P(3)R ∨ S DS 1, 2, 3(4)
Ejemplo 4:
P ∨ ¬Q P(1)P → ¬R P(2)
¬Q → S P(3)¬R ∨ S DS 1, 2, 3(4)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 49 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de simplificación disyuntiva
La ley de simplificación disyuntiva (abreviada DP) se representasimbólicamente así:
P ∨ P∴ P
Ejemplo de la proposición:“El equipo de los Pumas ganará o el equipo de los Pumas ganará”
Se puede concluir que “El equipo de los Pumas ganará”
Simbólicamente:
P ∨ P P(1)P DP 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 50 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de simplificación disyuntiva
Ejemplo 1:
¬Q ∨ ¬Q P(1)¬Q DP 1(2)
Ejemplo 2:
(P ∧Q) ∨ (P ∧Q) P(1)P ∧Q DP 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 51 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes conmutativas
Las leyes conmutativas (abreviadas CL) se aplican a conjuncionesy disyunciones. Expresan que el orden de las proposicionesatómicas no afectan el significado de la proposición molecular
Representadas en forma simbólica:
P ∧Q∴ Q ∧ P
P ∨Q∴ Q ∨ P
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 52 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes conmutativas
El razonamiento siguiente es un ejemplo del uso de las leyes conmutativas en laconjunción:
Galileo murió en 1642 y Newton nació en 1642Por lo tanto, Newton nació en 1642 y Galileo murió en 1642
Sea:
G = “Galileo murió en 1642”N = “Newton nació en 1642”
El razonamiento es:
G ∧N P(1)
N ∧G CL 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 53 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes conmutativas
El razonamiento siguiente es un ejemplo del uso de las leyes conmutativas en laconjunción:
x es mayor que cinco o x es igual a cincoPor lo tanto, x es igual a cinco o x es mayor que cinco
Sea:
M = “x es mayor que cinco”I = “x es igual a cinco”
El razonamiento es:
M ∨ I P(1)
I ∨M CL 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 54 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes conmutativas
Ejemplo 1:
P ∧ ¬Q P(1)¬Q ∧ P CL 1(2)
Ejemplo 2:
¬P ∨ ¬Q P(1)¬Q ∨ ¬P CL 1(2)
Ejemplo 3:
¬P ∧Q P(1)Q ∧ ¬P CL 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 55 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes de De Morgan
Las leyes de De Morgan (abreviadas DL) son un par de reglas deinferencia que permiten la expresión de conjunciones ydisyunciones puramente en términos una de otra vía la negación
Representadas en forma simbólica:
¬(P ∨Q)∴ ¬P ∧ ¬Q
¬(P ∧Q)∴ ¬P ∨ ¬Q
Se resumen en tres pasos:Cambiar ∧ por ∨ o ∨ por ∧Negar cada miembro de la conjunción o disyunciónNegar la fórmula completa
Augustus De Morgan (1806-1871) matemático y lógico británico
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 56 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes de De Morgan
Ejemplo 1:
¬(P ∧ ¬Q) P(1)¬P ∨ ¬¬Q DL 1(2)
Ejemplo 2:
¬(¬P ∧ ¬Q) P(1)¬¬P ∨ ¬¬Q DL 1(2)
Ejemplo 3:
¬¬P ∨ ¬Q P(1)¬(¬P ∧Q) DL 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 57 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLeyes de De Morgan
Ejemplo 4:
¬(P ∨ ¬Q) P(1)¬P ∧ ¬¬Q DL 1(2)
Ejemplo 5:
¬¬P ∧ ¬Q P(1)¬(¬P ∨Q) DL 1(2)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 58 / 80
Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales
Reglas de inferencia adicionalesLey de las proposiciones bicondicionales
La ley de las proposiciones bicondicionales (abreviadas LB)permite deducir de una bicondicional dos proposicionescondicionales
Representadas en forma simbólica:
P ↔ Q∴ P → Q
P ↔ Q∴ Q → P
P ↔ Q∴ (P → Q) ∧ (Q → P )
P → QQ → P
∴ P ↔ Q
Se adoptará la convención de que la bicondicional tieneprecedencia que cada uno de los otros términos de enlace
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 59 / 80
Teoría de inferencia y demostración en lógica proposicional Árboles de verdad
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 60 / 80
Teoría de inferencia y demostración en lógica proposicional Árboles de verdad
Árboles de verdad
Independientemente de la longitud de una proposición molecular,es posible encontrar sus valores de verdad si se conocen losvalores de verdad de sus partes
Una forma de analizar el valor de verdad de una proposiciónmolecular es estableciendo un árbol de verdad (también llamadosdiagramas de certeza)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 61 / 80
Teoría de inferencia y demostración en lógica proposicional Árboles de verdad
Árboles de verdad
Veamos un ejemplo con la proposición (P ∨Q) ∧R donde P esuna proposición cierta, Q es falsa y R es una proposición cierta
(P ∨Q) ∧R
T F T
T
T
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 62 / 80
Teoría de inferencia y demostración en lógica proposicional Árboles de verdad
Árboles de verdad
Consideremos ahora otro ejemplo con la proposición(P ∧Q → P ) ∧ (R ∨ S) donde P es cierta, Q es cierta, R es falsay S es falsa
(P ∧Q → P ) ∧ (R ∨ S)
T T T
T
T
F F
F
F
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 63 / 80
Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 64 / 80
Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas
Conclusiones no válidas
Hasta ahora en todo los ejemplos que hemos realizado se pedíadeducir a partir de premisas dadas una conclusión que eraefectivamente válida
En lógica a veces se requiere también probar que una conclusiónno es consecuencia lógica de las premisas dadas
O que un razonamiento particular es no válido
Una conclusión es una consecuencia lógica de las premisas cuando toda interpretación que hace verdaderas a las premisastambién hace verdadera a la conclusión
Un razonamiento es válido sólo si la conclusión es una consecuencia lógica de las premisas
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 65 / 80
Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas
Conclusiones no válidas
Veamos a través de un ejemplo un método para probar que unrazonamiento particular es no válido
Suponga el siguiente razonamiento:Si usted es un habitante de Cd. Victoria, entonces usted es unhabitante de MéxicoUsted es un habitante de MéxicoPor lo tanto, usted es un habitante de Cd. Victoria
Sea:V = “Usted es un habitante de Cd. Victoria”M = “Usted es un habitante de México”
Simbolizando:
V → MM
∴ V
La forma del razonamiento nos permite deduciruna conclusión falsa de premisas verdaderas (Vfalsa, M verdadera)
Se demuestra entonces que el razonamientoes no válido
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 66 / 80
Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas
Conclusiones no válidas
El método (denominado de asignación de certeza) para demostrarque una inferencia es no válida se puede resumir en dos pasos:
1 Simbolizar las premisas y conclusiones2 Encontrar una asignación de valores de verdad para las
proposiciones atómicas tales que todas las premisas sean ciertas yla conclusión sea falsa
V → M
F T T
T
Premisas
M
Conclusion
F
V
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 67 / 80
Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas
Conclusiones no válidas
Un ejemplo un poco más largo
P ∧Q → (P → R) ∨ S
T T
T
Premisas
P ∧ ¬RConclusion
¬P ∨ ¬QT T
F F
F
T F
F
T
T
T
T FF
T
T
El razonamiento es no válido por que la conclusión no es unaconsecuencia lógica de las premisas
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 68 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración condicional
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 69 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración condicional
Demostración condicional
Una demostración condicional (abreviada CP) permite usar partede la conclusión como una premisa que se puede usar paraprobar el resto de la conclusión
Para demostrar la validez de un argumento cuya conclusión tienela forma X → y (i.e., cualquier declaración condicional) se puedenseguir los siguientes pasos:
1 Separe el antecedente X de la condicional2 Agregue ese antecedente X a la lista de premisas (como una
premisa supuesta AP)3 Se prueba el consecuente y como si fuera la conclusión
Veamos un ejemplo a continuación
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 70 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración condicional
Demostración condicional
Dadas las premisas P → Q, R → ¬Q; deseamos probar la conclusión R → ¬P
P → Q P(1)
R → ¬Q P(2)
R AP(3)
¬Q PP 2, 3(4)
¬P TT 1, 4(5)
R → ¬P CP 3, 5(6)
En (3) se introduce el antecedente de la condicional (se recorre a la derecha -no es premisa original)
En (5) se deduce el consecuente de la condicional
La línea (6) se recorre a la izquierda por que es conclusión de las premisasoriginales
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 71 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración condicional
Demostración condicional
Ejemplo 2. Dadas las premisas A → (B → C), ¬D ∨A, B; deseamos probar laconclusión D → C
A → (B → C) P(1)
¬D ∨A P(2)
B P(3)
D AP(4)
A TP 2, 4(5)
B → C PP 1, 5(6)
C PP 3, 6(7)
D → C CP 4, 7(8)
La parte de la demostración que se ha corrido a la derecha se denominademostración subordinada
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 72 / 80
Teoría de inferencia y demostración en lógica proposicional Consistencia
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 73 / 80
Teoría de inferencia y demostración en lógica proposicional Consistencia
Consistencia
Como hemos visto ya, una contradicción (representada ⊥) es unaproposición que siempre es falsa, independientemente de losvalores de verdad de sus constantes
Un ejemplo de contradicción es la proposición P ∧ ¬P
Cada dos o más proposiciones que lógicamente no pueden serciertas a la vez se dice que son inconsistentes
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 74 / 80
Teoría de inferencia y demostración en lógica proposicional Consistencia
Consistencia
En ocasiones no se requiere deducir una conclusión particular,sino deducir si un conjunto de proposiciones es consistente oinconsistente
Para demostrar que un conjunto de premisas son inconsistentesse deduce una contradicción (i.e., las premisas no pueden sertodas ciertas a la vez)
Veamos un ejemplo
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 75 / 80
Teoría de inferencia y demostración en lógica proposicional Consistencia
Consistencia
Dadas las premisas D → J , D, ¬J ; deseamos probar que soninconsistentes
D → J P(1)D P(2)¬J P(3)J PP 1, 2(4)J ∧ ¬J A 3, 4(5)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 76 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración indirecta
1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 77 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración indirecta
Demostración indirecta
Una demostración indirecta1 (abreviada RAA) permite demostrarla negación del antecedente de una condicional cuando se sabeque el consecuente es falso (i.e., es una contradicción)
Representados en forma simbólica:P → (Q ∧ ¬Q)
∴ ¬P
1También puede denominarse demostración por contradicción o demostración por reducción al absurdo.
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 78 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración indirecta
Demostración indirecta
Para ello se seguen los siguientes pasos:1 Introducir la negación de la conclusión deseada como una nueva
premisa2 Con la premisa nueva y las premisas dadas se deduce una
contradicción3 Se establece la conclusión deseada como una inferencia lógica
deducida de las premisas originales
Veamos un ejemplo a continuación
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 79 / 80
Teoría de inferencia y demostración en lógica proposicional Demostración indirecta
Demostración indirecta
Dadas las premisas (1)-(3), se desea llegar a la conclusión ¬D
D → W P(1)
A ∨ ¬W P(2)
¬(D ∧A) P(3)
D P(4)
W PP 1, 4(5)
A TP 2, 5(6)
¬D ∨ ¬A DL 3(7)
¬A TP 4, 7(8)
A ∧ ¬A A 6, 8(9)
¬D RAA 4, 9(10)
Introducir la negación de la conclusión deseada como una nueva premisa, línea (4)
Con la premisa nueva y las premisas dadas se deduce una contradicción, líneas (5) a (9)
Se establece la conclusión deseada como una inferencia lógica deducida de las premisas originales, línea (10)
Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 80 / 80