Lógica Matemática: Proposicional e Primer Orden

Vista previa del material en texto

Lógica Matemática
M.C. Mireya Tovar Vidal
Contenido
 Proposicional
 Definición 
 Sintaxis
 Proposición
 Conectivos lógicos
 Semántica
 Primer orden
 cuantificadores
Finalidad de la unidad
 Traducir enunciados sencillos a expresiones 
lógicas. 
 Construir tablas de verdad de proposiones 
compuestas
 Averiguar si dos proposiciones son 
lógicamente equivalentes.
 Verificar si un razonamiento es correcto.
Definición
 Lógica
 Es la disciplina que trata de los métodos de razonamiento.
 Proporciona reglas y técnicas para determinar si es o no 
válido un argumento dado.
 Razonamiento lógico
 Matemáticas: demostrar teoremas
 Ciencias de la computación: verificar si son o no correctos los 
programas y demostrar teoremas
 Ciencias físicas y naturales: sacar conclusiones de 
experimentos
 Ciencias sociales: para resolver una multitud de problemas.
Lógica
 Ciencia formal y rama de la Filosofía que estudia los principios de la 
demostración e inferencia válida.
 La inferencia es la forma en la que obtenemos conclusiones de un 
planteamiento dado. 
 Un argumento, por ejemplo es una inferencia, donde las premisas 
son los datos o expresiones conocidas y de ellas se desprende una 
conclusión. 
 La palabra deriva del griego antiguo λόγος (logos), "palabra, 
pensamiento, idea, argumento, razón o principio".
 Lenguaje
 Sintaxis
 Alfabeto
 Formulas bien formadas
 Semántica
 Tablas de verdad
Sintaxis
 Proposiciones
 Una proposición o enunciado es una oración que 
declara que algo es verdadero o falso pero no 
ambas cosas.
 Ejemplos:
 La tierra es redonda 
 2+3 = 5
 ¿Habla inglés?
 3-x=5
 Tome dos aspirinas
 El sol saldrá mañana
Si
Si
No, es una pregunta
No, porque depende del valor de x
No, es una orden 
Si
Ejercicio
 Son proposiciones las siguientes sentencias:
1. ¿A donde estas?
2. Y te acabas la sopa!
3. Esta oración es falsa
4. Victoria es alta.
5. El helado es delicioso.
6. X > 5.
No son Proposiciones!!!
 La primera sentencia es una pregunta. 
 La segunda es una orden. 
 La tercera hay que analizarla a profundidad, es una sentencia que hace 
referencia a si misma.
 Dificultad para determinar su valor de verdad (paradoja) 
 Si asumimos que es verdadera y la sentencia dice que es falsa se 
contradice.
 Si asumimos que es falsa y la sentencia dice que es falsa entonces
la sentencia es verdadera.
 La cuarta se refiere a una persona y que es alta pero no define la altura
específica. 
 La quinta es una opinión. 
 La sexta es un predicado (sentencia que contiene una o más variables que
no se le puede asignar un valor de verdad hasta que se les asigne valores
a sus variables).
Sintaxis
 Alfabeto
 Variables
 p, q, r, …
 p: El sol esta brillando hoy
 q: Hace frío 
 Conectivos
 Proposiciones compuestas
 Son la combinación de conectivos y proposiciones
 Una fórmula sintácticamente correcta se define de acuerdo a las siguientes 
reglas.
 Las proposiciones p, q, r, s, .... son fórmulas correctamente formadas.
 Si A y B son fórmulas correctas, también son fórmulas correctas:
 ~A, ~B
 (A B)
 (A v B)
 (A B)
 (A B)
 Sólo son fórmulas correctas las que cumplen las condiciones anteriores.
)(),(,,(~),
Cómo formalizar el lenguaje natural 
I. Identificar los enunciados simples
II. Asignar a cada enunciado simple una 
constante proposicional
III. Identificar los conectivos lógicos: negación, 
disyunción, condicional, etc.
IV. Reconstruir los enunciados complejos a 
partir de los simples y los conectivos lógicos
Formalización de proposiciones 
compuestas
 Negación: ~p.
 No p.
 Es falso que p.
 No es cierto que p.
 Conjunción: p ^ q.
 p y q.
 p pero q.
 p no obstante q
 p sin embargo q
 p a pesar de q
 p, q
 p, pero q
 p, aunque q
 Aunque p, q
 Mientras p, q
 A pesar de que p, q
 Disyunción: p v q.
 p o q ó ambos.
 p ó q.
 Al menos p ó q.
 Como mínimo p ó q
 p a menos que q
 Condicional: Causa – Efecto. 
p q.
 Si p entonces q.
 Si p, q
 p sólo si q
 q si p
 q necesario para p
 p suficiente para q.
 No p a menos que q.
 p implica q
 q se sigue de p
 q siempre que p
 Cuando p, entonces q
 q con tal que p
 Bicondicional o equivalencia:
p q.
 p suficiente y necesario para q
 p si y sólo si q.
 Una condición suficiente y necesaria para p es 
q
 p es equivalente a q
Ejemplos
 Negación
 p: Hay vida en la luna 
 ¬p: No hay vida en la luna
 p: Los elefantes temen a los ratones
 ¬p Los elefantes no temen a los ratones
 Conjunción
 p: Aquiles corre velozmente.
 q: La tortuga corre velozmente.
 p ¬ q: Aquiles corre velozmente, pero la tortuga 
no.
 Disyunción
 Sea 
p: "El mayordomo cometió el crimen", 
q: "El pintor cometió el crimen" 
r: "La sirvienta cometió el crimen"
 p v q: "O el mayordomo o el pintor cometieron el 
crimen"
 (pvq) ¬r: "O el mayordomo o el pintor cometieron 
el crimen, pero no la sirvienta".
 Condicional o implicación
 Si los burros vuelan, entonces las tortugas saben 
álgebra
 p: los burros vuelan
 q: las tortugas saben álgebra 
 p q 
 Bicondicional
 La Tierra es cúbica si y sólo si el Sol es un 
planeta“
 p: "La Tierra es cúbica": F
 q: "El Sol es un planeta": F
Ejemplo:
 Programa:
i:=1
j:=1
while (i < 2 and j<5) or i+j = 5 do
begin
i:=i+2
j:=j+1
end
 p: i < 2 q: j<5 r: i+j = 5
 (p q) v r
Semántica
 Tablas de verdad
A ~A
V F
F V
A B A ^ B
V V V
V F F
F V F
F F F
A B A v B
V V V
V F V
F V V
F F F
A B A B
V V V
V F F
F V V
F F V
A B A B
V V V
V F F
F V F
F F V
Tablas de verdad en proposiciones 
compuestas
 Una tabla de verdad es un algoritmo o procedimiento que a
través de la aplicación mecánica de un conjunto finito de reglas,
permite definir la validez o invalidez de las inferencias.
 Consiste en aplicar valores de verdad en cada expresión
atómica que conforma la proposición compuesta; de esta forma,
cualquier renglón de la tabla para una fórmula dada p se le
denomina interpretación de p.
Jerarquía de Conectivos Lógicos
Menor Prioridad
…
Negación
Conjunción
Disyunción
Condicional
Equivalencia
Mayor Prioridad
Algoritmo para construir una tabla de 
verdad
1. Generar una tabla donde las columnas correspondan a cada 
proposición simple, además de cada una de las proposiciones 
compuestas considerando las prioridades.
2. El número de filas es el resultado de aplicar la formula 2n, donde 
n es el número de proposiciones simples.
3. Asignar valor de verdad a cada una de las columnas restantes 
de acuerdo al operador indicado.
4. La última columna, correspondiente a la fórmula original, es la 
que indica los valores de verdad posibles de la fórmula para 
cada caso. 
Ejemplo
p q p q (p q) p q ( p q) (p q) ( p q)
V V V F F F F V
V F F V F V V V
F V F V V F V V
F F F V V V V V
Definiciones
 Tautología
 La proposición compuesta P es una tautología si P es verdadera 
para todos los valores de verdad que se asignen a las 
proposiciones p1,…, pn que forman a P.
 Contradicción
 La proposición compuesta P es una contradicción si P es falsa 
para todos los valores de verdad que se asignen a las 
proposiciones p1,…, pn que forman a P.
 Incongruencia
 Una proposición incongruente (llamada también contingente) es 
una proposición compuesta que es verdadera en algunos casos 
y falsa en otros. Su valor de verdad depende no de la forma 
lógica sino del valor de verdad de sus proposiciones simples.
Ejemplo de Tautología
 Si Isis y Osiris no son felices, entonces o Isis no es feliz o
Osiris no es feliz.
 p= Isis es feliz
 q= Osiris es feliz
(p q) ( p q)
p q p q (p q) p q ( p q) (p q) ( p q)
V V V F F F F V
V F F V F V V V
F V F V V F V V
F F F V V V V V
 Demuestre que son tautologías:
 (p q) v [(¬p)v(¬q)]
 [(¬p) q] v [p (¬q)] 
Ejemplo de Contradicción
 Osiris ama a Isis y Set ama a Isis, Osiris noama a
Isis
 p= Osiris ama a Isis
 q= Set ama a Isis
p q p q p (p q) p 
V V V F F
V F F F F
F V F V F
F F F V F
(p q) p 
 Demuestre que son contradicciones:
 [(¬p) q] [p (¬q)]
 [(¬p) p]
 [(¬p) q] [p (¬q)]
Definición
 La proposición compuesta P implica 
lógicamente la proposición compuesta Q.
P => Q
p1, p2, p3, … pn => q1, q2, … qm
 Esto se cumple cuando
p1, p2, p3, … pn → q1, q2, … qm es una tautología
 Ejemplo:
 ~(p v q) => ~ p
 ~(p v q) es T, p v q es F, p es F, q es F. Luego ~p es T
 Definición
 Las proposiciones compuestas P y Q son 
lógicamente equivalentes 
P ≡ Q
p1, p2, p3, …, pn ↔ q1, q2, …, qm
 Esto se cumple cuando
p1, p2, p3, …, pn ↔ q1, q2, …, qm es una tautología
 Leyes de De Morgan
 ¬(p q) ≡ ¬p v ¬q
 ¬(p v q) ≡ ¬p ¬q
Tautologías
0.- p q p v q Ley de la implicación 
Tautologías
Reglas de Inferencia
 Los argumentos basados en tautologías representan 
métodos de razonamiento universalmente correctos. 
 Su validez depende solamente de la forma de las 
proposiciones que intervienen y no de los valores de 
verdad de las variables que contienen.
 A esos argumentos se les llama reglas de inferencia. 
 Las reglas de inferencia permiten relacionar dos o 
más tautologías o hipótesis en una demostración.
Reglas de inferencia
 MP Modus ponens
A → B 
A 
- - - - -
B 
 MT Modus tollens
A → B 
¬B 
- - - - -
¬A 
 SD Silogismo Disyuntivo 
A ∨ B 
¬A 
- - - - -
B 
• SH Silogismo hipotético
A → B
B → C
- - - - -
A → C
• LS Ley de simplificación
A ∧ B
- - - - -
A
• LA Ley de adición
A
- - - - -
A ∨ B
• CONTRAPOSITIVA
A → B
- - - - -
¬B → ¬A
Ejemplo de inferencia
Juan invierte en el mercado de valores.
Si Juan invierte en el mercado de valores entonces se
hace rico.
_________________________________
Juan es rico
Sea:
p: Juan invierte en el mercado de valores.
q: Juan es rico
[p (p q) q
Primera Solución
 Tablas de verdad
p q p q p (p q) [p (p q)] q
v v v v v
v f f f v
f v v f v
f f v f v
Segunda solución
 Mediante reducciones con tautologías.
[p (p q) q
p (p q q
p ( p q q
p ( p q q
( p p) ( p q q
T ( p q q
( p q q
( p) ( q q)
( p) T
T
Ejercicio
1. Deduce la conclusión (primero formalizar)
 Sí es un perro entonces es carnívoro.
 Es un perro.
2. Deduce la conclusión (primero formalizar)
 Una de dos: pera o manzana.
 No quiero la pera.
3. Para el primer inciso demuestra con tabla de
verdad y con reducción de expresiones (vía
tautologías que es válido)
Razonamientos y demostraciones
 Sistema axiomático, formado:
 Axiomas: se suponen ciertos.
 Definiciones: se usan para crear nuevos conceptos en términos 
de otros ya existentes.
 Términos no definidos: pero si lo están implícitamente por los 
axiomas.
 Ejemplo:
 Sistema axiomático: Geometría euclidiana
 Axiomas:
 Dados dos puntos distintos, existe una recta única que los contiene.
 Términos no definidos:
 Punto, recta, pero están implícitamente definidos por los axiomas 
que describen sus propiedades.
 Definiciones:
 Dos ángulos son suplementarios si la suma de sus medidas es 180º.
 Teoremas
 Es un resultado que se puede deducir de los axiomas, de las 
definiciones y de los teoremas establecidos previamente.
 Demostración
 El razonamiento que establece la veracidad de un teorema.
 Lema
 Es un teorema que no tiene especial interés en sí mismo pero 
que es útil para probar otro teorema.
 Si los lados de un triángulo son iguales, entonces los ángulos 
opuestos a ellos también son iguales.
 Corolario
 Es un teorema que se deduce inmediatamente de un teorema.
 Si un triángulo es equilátero, entonces tiene sus ángulos iguales.
Demostración directa
 Los teoremas son de la forma:
Si p, entonces q (1)
 Una demostración directa supone que p es verdadera y 
después, usando tanto p como axiomas, definiciones y teoremas 
establecidos con anterioridad, prueba directamente que q es 
verdadera.
 Ejemplo:
Si d = min {d1, d2} y x<d, entonces x < d1 y x < d2. 
Dem: De la definición de mín, se deduce que d ≤ d1 y d ≤ d2 . Como 
x < d y d ≤ d1, se puede deducir que x < d1. Ya que x < d y d ≤ d2 , 
puede deducirse que x < d2 . Por lo tanto, x < d1 y x < d2
Demostración por contradicción o 
indirecta
 Se establece mediante la demostración de la proposición 
lógicamente equivalente
(p ~q) → (r ~r) (2)
 Cuya conclusión es una contradicción. Se prueba (2) y se 
concluye que (1) es verdadera.
 Ejemplo:
 Si x + y ≥ 2, entonces x ≥ 1 o bien y ≥ 1.
Dem: Considere la hipótesis verdadera y la conclusión falsa. 
Entonces, x<1 y y<1. Sumando estas dos desigualdades 
obtenemos:
x + y < 1 + 1 = 2
Con esto llegamos a la contradicción p ~p, en donde 
p: x + y ≥ 2. Por lo tanto, se concluye que la proposición es 
verdadera.
Razonamientos
 Definición
 Un razonamiento es una sucesión de proposiciones escritas de 
la siguiente manera:
p1
p2
.
.
.
_pn_
q
 El razonamiento es válido si
p1 p2 … pn => q 
 se cumple; en caso contrario, no es válido (se dice que es una 
falacia).
 El razonamiento tiene validez cuando
p1 p2 … pn → q es una tautología
Reglas de inferencia
 Modus Ponens (MP)
A B
A 
B
 Regla de Prueba por Casos
A C
B C 
A v B 
C
 Contrapositiva
A B
~B ~A
 Simplificación
A B A B
A B
 Amplificación disyuntiva
A
A v B
 Modus Tollens
A B
~B
~ A
 Regla de la conjunción
A 
B
A B
 Regla del silogismo disyuntivo
A v B
~ A
B
 Regla del dilema constructivo
A B
C D
A v C
B v D
Reglas de inferencia
 Introducción al antecedente (IA)
A 
B A
 Regla del silogismo (Sil)
A B
B C
A C
 Mutación (Mut)
A (B C)
B (A C)
 Importación (Imp)
A (B C)
A B C
 Exportación (Exp)
A B C
A (B C)
 Conmutativa (Conm)
A B B A
B A A B
 Asociativa (As)
A (B C)
(A B) C)
 Distributiva (Distr)
A (B v C) (A B) v (A C)
(A B) v (A C) A (B v C)
 Idempotencia (Idem)
A A A
A A A
 Absorción (Absr)
A (A v B) A
A A (A v B)
 Conmutativa (Conm)
A v B B v A
B v A A v B
 Asociativa (As)
A v (B v C)
(A v B) v C)
Reglas de inferencia
 Distributiva (Distr)
A v (B C) (A v B) (A v C)
(A v B) (A v C) A v (B C)
 Idempotencia (Idem)
A v A A
A A v A
 Absorción (Absr)
A v (A B) A
A A v (A B)
 Doble negación (DN)
A ~ ~ A 
~ ~ A A
 Definición de implicación (DI1)
A B A v B
~ A v B ~ A B
 Definición de implicación (DI2)
A B A B
~(A ~B) ~ (A ~ B)
 Ley de De Morgan (DM1)
~(A v B) ~ A ~ B
~A ~B ~ (A v B)
 Ley de De Morgan (DM2)
~(A B) ~ A v ~ B
~A v ~B ~ (A B)
z:=4;
for i:=1 to 10 do
begin
x:=z-i;
y:=z+3*i;
if ((x>0) and (y>0)) then
writeln(‘The value of the sum x+y is’, x+y)
end
Ejemplo
.
.
.
if x>0 then
if y>0 then
…
Exportación (Exp)
A B C
es lógicamente equivalente a 
A (B C)
p q r
p q r
p q r
p q r
p q r
p q r
( )
( )
( )
( )
( )
( )
Ejemplo
 Comprobar si es correcta la deducción:
p q, ~(q v r) ~ p
Solución:
1. p q Premisa
2. ~(q v r) Premisa
3. ~q ~ r DM a 2
4. ~q Simpl. a 3
5. ~q ~p CP a 1
6. ~p MP 4,5
Ejercicio
 Comprobar si es correcta la deducción:
p q, ~(q v r) ~ p
Ejercicio
p q
q r s
r t u
p t
u
( )
( )
p, t
q
r, s
t u
u
Ejemplo
Demostrar que el siguiente argumento es válido
 Si la banda no pudiera tocar rock o las bebidas no llegasen a tiempo, entonces 
la fiesta de Año Nuevo tendría que cancelarse y Alicia se enojaría. Si la fiesta 
se cancelaran, habría que devolver el dinero. No se devolvió el dinero. Por lo 
tanto la banda pudo tocar rock.
 Forma simbólica:
 p: la banda pudo tocar rock q: las bebidas se entregaron a tiempo
 r: la fiesta de año nuevo se canceló s: Alicia estaba enojada
 t: Hubo que devolver el dinero
1. r → t Premisa
2. ~t Premisa
3. ~r ModusTollens de 1, 2
4. ~r v ~s Amplificación disyuntiva a 3
5. ~(r s) De Morgan a 4
6. (~p v ~q) → (r s) Premisa
7. ~(~p v ~q) Modus tollens 6,5
8. p q De Morgan y doble negación a 7
9. p simplificación a 8
(~p v ~q) → (r s)
r → t
~t
p
Ejercicio
p r
p q
q s
r s
r p
r q
r s
 Regla por casos
 Ejemplo:
Ejercicio
Demostrar que el siguiente argumento es válido
 Si voy a mi primera clase mañana tendré que madrugar y si voy al 
baile esta noche me acostaré tarde.
 Si me acuesto tarde y madrugo tendré que vivir con sólo cinco 
horas de sueño.
 No puedo vivir con sólo cinco horas de sueño.
Por lo tanto:
 O no voy a mi primera clase mañana o no voy al baile esta noche.
Solución
Demostrar que el siguiente argumento es válido
 Si voy a mi primera clase mañana tendré que madrugar y si voy al 
baile esta noche me acostaré tarde.
 Si me acuesto tarde y madrugo tendré que vivir con sólo cinco 
horas de sueño.
 No puedo vivir con sólo cinco horas de sueño.
Por lo tanto:
 O no voy a mi primera clase mañana o no voy al baile esta noche.
p
q
r s (p →q) (r → s)
(s q) → t
t
~ t
~p v ~r
Solución
Premisa
Premisa
Premisa
CP 2
MP 3,4
De Morgan 5
Casos 6
Simpl 1.
MT 7,8
Ad 9
Casos 6
Simpl 1
MT 11, 12
Ad 13
Prueba por casos 6,7, 11
1. (p →q) (r → s)
2. q s → t
3. ~t
4. ~t → ~(q s)
5. ~(q s)
6. ~q v ~s
7. ~q
8. p →q
9. ~p
10. ~p v ~r
11. ~ s
12. r → s
13. ~ r
14. ~p v ~r
15. ~p v ~r
(p →q) (r → s)
(s q) → t
~ t
~p v ~r
 Supuestos
, A B
A B
 Ejemplo:
A (B C) A ^ B C
1. A (B C) Premisa
2. A ^ B Supuesto
3. A Simplificación 2
4. B C MP 3,1
5. B Simplificación 2
6. C MP 5,4
7. A ^ B C Cancelación del supuesto 2,6
p
p
p
q r
n
1
2

p
p
p
q
r
n
1
2

Ejercicio
u r
r s p t
q u s
t
q p
( ) ( )
( )
u r
r s p t
q u s
t
q
p
( ) ( )
( )
u, s
p t
p
u s
r
Ejercicios
 Comprobar si es correcta la deducción:
p (q r), r s t, (s t) w p (q w)
 Comprobar si es correcta la deducción:
p (r q), ~ s v p, r s q,
Bibliografía
 Grimaldi Ralph P. Matemáticas Discreta y 
Combinatoria. Una introducción con 
aplicaciones. Addison Wesley Longman. 
3ª.edición.
 Johnsonbaugh Richard. Matemáticas 
Discretas. Iberoamericano.
 Kolman Estructuras de matemáticas 
discretas para la computación. Prentice Hall.
 http://www.isftic.mepsyd.es/w3/eos/Materiale
sEducativos/mem2003/logica/