LÓGICA Y MATEMÁTICAS DISCRETAS
PERIODO 2023 - 1
Modulo 2: Inducción Matemática y Recursividad.
Encuentros 12
3 de marzo de 2023
TÉCNICAS DE DEMOSTRACIÓN.
OBSERVACIÓN
Cunado las pruebas por inspección no funcionan surge la pregunta
¿Cómo se puede demostrar que 𝑃 ⟹ 𝑄 es cierto?
Un enfoque puede ser el que llamaremos una prueba directa.
TÉCNICAS DE DEMOSTRACIÓN.
PRUEBA DIRECTA:
Una prueba o demostración directa consiste en suponer que la hipótesis 𝑃 es cierta y
deducir la conclusión 𝑄. Una prueba formal requeriría una secuencia de pasos y
argumentos que lleven de 𝑃 a 𝑄.
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO:
Demuestre que:
“El producto de dos números pares, siempre es par”
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO:
Dé una demostración directa (informal) del teorema
”Todo numero entero divisible por 6 también es divisible por 3".
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO:
Dé una demostración directa (informal) del teorema
"Si un número entero es divisible por 6, entonces el doble de ese número entero es
divisible por 4".
TÉCNICAS DE DEMOSTRACIÓN.
PRUEBAS POR CONTRAPOSICIÓN
Si se ha intentado hacer un demostración directa del enunciado 𝑃 ⟹ 𝑄 y no se ha
conseguido ningún resultado y aun así se piensa que el enunciado es verdadero,
entonces puede intentarse probando
¬𝑄 ⟹ ¬𝑃
Lo cual es completamente valido por la reglas de inferencia en las que se tiene que
¬𝑄 ⟹ ¬𝑃 ⟹ 𝑃 ⟹ 𝑄
A esta técnica se le conoce como pruebas por contraposición.
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO:
Demuestre que para todo 𝑛 ∈ 𝑍, si 𝑛! es impar entonces 𝑛 también es impar.
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO:
Demostrar que si n + 1 contraseñas separadas se emiten a n estudiantes, entonces
algún estudiante obtiene 2 o más contraseñas.
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO
Demuestra que el producto xy es impar si y sólo si x e y son enteros impares.
TÉCNICAS DE DEMOSTRACIÓN.
PRUEBAS POR CONTRADICCÓN:
Usando lógica proposicional podeos probar que
𝑃 ∧ ¬𝑄 ⟹ 0 ⟹ (𝑃 ⟹ 𝑄)
TÉCNICAS DE DEMOSTRACIÓN.
PRUEBAS POR CONTRADICCÓN:
Esto permite el hecho de ante la imposibilidad de probar de forma directa 𝑃 ⟹ 𝑄
y mas aun la imposibilidad de probar ¬𝑄 ⟹ ¬𝑃 “Contraposición”, se puede
intentar probar que
𝑃 ∧ ¬𝑄 ⟹ 0
A lo cual llamaremos una prueba por contradicción, lo cual es una técnica
completamente validad a la luz de la lógica formal.
TÉCNICAS DE DEMOSTRACIÓN.
EJEMPLO
Demuestre que si se cumple 𝑥 + 𝑥 = 𝑥 entonces 𝑥 = 0
TÉCNICAS DE DEMOSTRACIÓN.
EN RESUMEN
TÉCNICA Enfoque para probar 𝑷 ⟹ 𝑸 Observación.
Prueba por inspección Demostrar 𝑃 ⟹ 𝑄 para Usar solo para probar
todos los casos posibles. cuando se tiene un numero
finito de casos
Prueba directa Suponer 𝑃 y deducir 𝑄 Enfoque estándar, suele ser
lo que hay que probar.
Prueba por contraposición. Suponer ¬𝑄 y deducir ¬𝑃 Utilícelo si ¬𝑄 como hipótesis
paree dar mas argumentos
que la propia 𝑃
Prueba por contradicción. Suponer 𝑃 ∧ ¬𝑄 y deducir Se suele usar cuando 𝑄 dice
una contradicción. que algo no es cierto.
