Sección 1.
Matemática Discreta- FIQ
2024
Finalmente me dije: jamás seré abogado si no entiendo lo que significa
demostrar. Dejé Springfield y regresé a casa de mi padre, donde permanecı́
hasta que pude demostrar cada Proposición de los seis libros de Euclı́des.
Entonces supe lo que significa demostrar, y volvı́ a mis estudios de leyes.
Abraham Lincoln.
Demostraciones en matemática.
Objetos con los que trabajamos en los sistemas matemáticos :
Axiomas, definiciones y términos no definidos.
Teoremas, lemas, resultados.
Demostraciones o pruebas: argumentos rigurosos que a partir de un
conjunto de hipótesis aplicando razonamientos válidos (lógica) que
permiten tener como consecuencia una tesis o conclusión.
Demostraciones en matemática.
Objetos con los que trabajamos en los sistemas matemáticos :
Axiomas, definiciones y términos no definidos.
Teoremas, lemas, resultados.
Demostraciones o pruebas: argumentos rigurosos que a partir de un
conjunto de hipótesis aplicando razonamientos válidos (lógica) que
permiten tener como consecuencia una tesis o conclusión.
Vamos a clasificar algunos tipos de demostraciones por su forma, utilizando
las ideas de lógica que hemos aprendido.
Geometrı́a Euclı́dea
La geometrı́a euclı́dea se desarrolla basándose en algunos axiomas o
postulados, como por ejemplo:
Si se tienen dos puntos distintos existe exactamente una lı́nea que los
contiene.
Las nociones de punto y lı́nea no se dan explı́citamente por una definición
sino que se comprenden a partir de los axiomas.
Geometrı́a Euclı́dea
La geometrı́a euclı́dea se desarrolla basándose en algunos axiomas o
postulados, como por ejemplo:
Si se tienen dos puntos distintos existe exactamente una lı́nea que los
contiene.
Las nociones de punto y lı́nea no se dan explı́citamente por una definición
sino que se comprenden a partir de los axiomas.
Como ejemplo, notemos que en esta geometrı́a plana el enunciado
Las rectas paralelas no se cruzan
resulta verdadero, mientras que es falso en otras geometrı́as. Por ejemplo en
la geometrı́a esférica (podemos pensar en la del planeta tierra) el enunciado
es falso porque las paralelas se cruzan en los polos.
Los números reales
Algunos axiomas o postulados y definiciones del sistema de números reales:
Axioma: Para todo par de números reales x, y se satisface que
x.y = y.x.
Definición: El valor absoluto de un número real x está definido como x
si x ≥ 0 y como −x si x < 0.
Teorema: Si x, y son números reales y x < y existe un real z tal que
x < z < y.
¿Cómo se prueba un teorema?
¿Cómo se prueba un teorema?
Si bien no hay recetas para probar un teorema, y la imaginación de un
matemático es la que se pone a prueba para llevar a cabo las demostraciones,
veremos la forma de algunos tipos de demostraciones. No todas!
Demostraciones:
Queremos probar un enunciado del tipo:
Si P entonces Q.
Por prueba directa: supongo P verdadera y demuestro Q.
Por contradicción: supongo P verdadera y ¬Q verdadera, y llego a una
contradicción.
Por contrarecı́proca: probamos (de manera directa) la proposición si
¬Q entonces ¬P, que es equivalente a la dada.
Otras: pruebas por casos, pruebas existenciales, etc.
Sea Z el conjunto de los números enteros. Recordemos que:
x ∈ Z se llama par si existe y ∈ Z que satisface que x = 2y.
x ∈ Z se llama impar si no es par. Si x no es par, es fácil ver que
x = 2k + 1 para algún entero k.
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Sea Z el conjunto de los números enteros. Recordemos que:
x ∈ Z se llama par si existe y ∈ Z que satisface que x = 2y.
x ∈ Z se llama impar si no es par. Si x no es par, es fácil ver que
x = 2k + 1 para algún entero k.
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Sean
P(x) : x es impar Q(x) = 2x no es múltiplo de 4.
Debemos probar
∀x si P(x) entonces Q(x),
donde el dominio de discurso es Z.
Prueba directa: Suponemos P(x) verdadera y probamos
Q(x).
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Supongamos x es impar (P(x) verdadera). Luego existe ∈ Z tal que
x = 2k + 1. Entonces
2x = 2(2k + 1) = 4k + 2.
Pero 2x 4k+2
4 = 4 =k+
1
2 no es entero. Lo que implica que 2x no es múltiplo
de 4 (Q(x) verdadera).
Prueba por contradicción : Suponemos P(x) verdadera y
¬Q(x) verdadera y llegamos a una contradicción.
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Supongamos x = 2k + 1 es impar (P(x) verdadera) y que ¬Q(x) es
verdadera, esto es, 2x = 4z para algún entero z. Luego
4z = 2x = 2(2k + 1) = 4k + 2
por lo que
4(z − k) = 2.
Prueba por contradicción : Suponemos P(x) verdadera y
¬Q(x) verdadera y llegamos a una contradicción.
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Supongamos x = 2k + 1 es impar (P(x) verdadera) y que ¬Q(x) es
verdadera, esto es, 2x = 4z para algún entero z. Luego
4z = 2x = 2(2k + 1) = 4k + 2
por lo que
4(z − k) = 2.
Pero como z − k es entero, esto implica que 2 es múltiplo de 4. Una
contradicción.
Prueba por contrarecı́proco: si ¬Q(x) entonces ¬P(x).
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Prueba por contrarecı́proco: si ¬Q(x) entonces ¬P(x).
Demostrar que si x un entero impar, entonces 2x no es múltiplo de 4.
Supongamos 2x = 4k (¬Q(x) verdadera). Dividiendo ambos miembros de la
ecuación por 2 tenemos que x = 2k es par (¬P(x) verdadera).
Otros tipos de pruebas.
Prueba de un enunciado del tipo P ↔ Q.
Prueba por casos.
Prueba de un enunciado del tipo ∃xP(x).
Argumentos
Vamos a llamar argumento en el lenguaje formal a una secuencia de
enunciados escrita
p1
p2
..
.
pn
∴q
Argumentos
Vamos a llamar argumento en el lenguaje formal a una secuencia de
enunciados escrita
p1
p2
..
.
pn
∴q
p1 , p2 , . . . , pn se llaman premisas del argumento.
q se llama conclusión.
El sı́mbolo ∴ se lee por lo tanto.
El argumento
p1
..
.
pn
∴q
se dice que es válido si cada vez que todas las premisas son verdaderas,
entonces la conclusión también lo es.
El argumento
p1
..
.
pn
∴q
se dice que es válido si cada vez que todas las premisas son verdaderas,
entonces la conclusión también lo es.
IMPORTANTE
Un argumento es válido por su forma, no por su contenido.
Ejemplo
Determine si el argumento
p
p→q
∴ q
es válido.
Ejemplo
Determine si el argumento
p
p→q
∴ q
es válido.
Para ver si es válido tenemos que ver si cada vez que la hipótesis son
verdaderas le conclusión es verdadera.
Ejemplo
Determine si el argumento
¬p
p→q
∴ q
es válido.
Reglas de inferencias
Modus Ponens
p
p→q
∴ q
Modus tollens
¬q
p→q
∴ ¬p
Reglas de inferencias
Intoducción de la disyunción
p
∴ p∨q
Eliminación de la conjunción
p∧q
∴p
Introducción de la conjunción
p
q
∴p∧q
Reglas de inferencias
Silogismo hipotético
p→q
q→r
∴p→r
Silogismo disyuntivo
¬p
p∨q
∴q
Reglas de inferencia para enunciados cuantificados.
Particularización universal
∀x P(x)
∴ P(d) si d ∈ D
Generalización universal
P(d) si d ∈ D
∴ ∀x P(x)
Particularización existencial
∃x P(x)
∴ P(d) para algún d ∈ D
Generalización existencial
P(d) para algún d ∈ D
∴ ∃x P(x)
Escriba el argumento en palabras y determine si es válido:
p : 4 megabytes es mejor que sin memoria.
q : Compraremos más memoria.
r : Compraremos una computadora nueva.
Argumento:
p → (r ∨ q)
r → ¬q
p→r
