Matemáticas Discretas – Demostración

Universidad Pedagógica y Tecnológica de Colombia

Angélica Liliana Sánchez
Taller – Demostraciones

Ejercicio de repasos:

1. ¿Qué es un sistema matemático?

Consiste en axiomas, definiciones y términos no definidos.
Un sistema matemático se puede interpretar como un sistema formal o un sistema
axiomático compuesto de símbolos que se unen entre sí formando cadenas que a su vez
pueden ser manipuladas según reglas para producir otras cadenas. De esta manera, el
sistema formal es capaz de representar cierto aspecto de la realidad.

La geometría euclidiana proporciona un ejemplo de un sistema matemático. Entre los

axiomas están los siguientes:
■Si se tienen dos puntos distintos, existe exactamente una línea que los contiene.
■Si se tienen una línea y un punto fuera de la línea, existe exactamente una línea paralela
a la línea que pasa por el punto.

2. ¿Qué es un axioma?
Se supone que los axiomas son verdaderos, Proposición o enunciado tan evidente que se
considera que no requiere demostración.

3. ¿Qué es una definición?

Las definiciones se usan para crear nuevos conceptos en términos de los existentes.

4. ¿Qué es un término no definido?

Algunos términos no están definidos de forma explícita por los axiomas.
Los términos punto y línea son términos no definidos que están implícitamente definidos
por los axiomas que describen sus propiedades.
Entre las definiciones se encuentran:
■Dos triángulos son congruentes si sus vértices se pueden aparear de manera que los
lados correspondientes y los ángulos correspondientes sean iguales.
■Dos ángulos son suplementarios si la suma de sus medidas es 180°.

5. ¿Qué es un teorema?
Un teorema es una proposición que se ha probado que es verdadera. Algunos tipos
especiales de teoremas reciben el nombre de lemas y corolarios.

6. ¿Qué es una demostración?

Un argumento que establece la verdad de un teorema se llama demostración o prueba. La
lógica es la herramienta para el análisis de las demostraciones. En esta sección se
Matemáticas Discretas – Demostración

describen algunos métodos generales de demostración y se usa la lógica para analizar

argumentos válidos e inválidos.

7. ¿Qué es un lema?
Un lema es un teorema que no suele ser muy interesante por sí mismo, pero que resulta
útil para probar otro teorema.
8. ¿Qué es una prueba directa?

Una prueba directa supone que p(x1, x2, . . . ,x n) es verdadera, y después, usando p(x1,
x2, . . . , x n) junto con otros axiomas, definiciones y teoremas derivados antes, demuestra
directamente que q(x1, x2, . . . , x n) es verdadera.

Todos “saben” qué es un entero par o impar, pero la siguiente definición hace estos
términos precisos y proporciona una manera formal de usar los términos “entero par” y
“entero impar” en las demostraciones.

Se dará una prueba directa de la siguiente afirmación. Para cualesquiera enteros my n, si

mes impar, y n es par, entonces m+n es impar.

9. ¿Cuál es la definición formal de “entero par”?

Un entero n es parsi existe un entero k tal que n=2k. Un entero n es impar si existe un
entero k tal que n=2k+1.
Ejemplo: El entero n=12 es par porque existe un entero k(a saber, k=6) tal que n=2k; es
decir, 12 =2 · 6.

10. ¿Cuál es la definición formal de “entero impar”?

El entero n=–21 es impar porque existe un entero k(a saber k=–11) tal que n=2k+1;
es decir, –21 =2 · –11 +1.

11. ¿Qué es una prueba por contradicción?

Una prueba por contradicción establece (1.5.1) suponiendo que la hipótesis pes cierta y
que la conclusión q es falsa y entonces, usando p y ¬q junto con otros axiomas,
definiciones y teoremas derivados antes, llega a una contradicción. Una contradicción es
una proposición de la forma r∧¬r (r puede ser cualquier proposición). Una prueba por
contradicción en ocasiones se llama prueba indirecta ya que para establecer (1.5.1)
usando la prueba por contradicción, se sigue una ruta indirecta: se deriva r∧¬r y después
se concluye que (1.5.1) es verdadera.

12. ¿Qué es una prueba indirecta?

La única diferencia entre las suposiciones en una prueba directa y una prueba por
contradicción es la conclusión negada. En una prueba directa no se supone la conclusión
negada, mientras que en una prueba por contradicción la conclusión negada es una
suposición.
Matemáticas Discretas – Demostración

La prueba por contradicción se justifica observando que las proposiciones

p→q y (p∧¬q) → ( r∧¬r)
Son equivalentes. La equivalencia es inmediata a partir de la tabla de verdad:

13. ¿Qué es una prueba por contrapositiva?

Use la prueba por contrapositiva para demostrar que para todo entero m, si m2 es impar,
entonces mes impar.

Demostración Primero, sea m un entero arbitrario. La contrapositiva de si m2 es impar,

entonces mes impar es si mes par, entonces m2 es no es impar o, de manera equivalente,
si mes par, entonces m2 es par.

Así, suponga que mes par. Entonces m=2kpara algún entero k. Ahora, m2=(2k)2=2 · (2k2).
Como m2 es de la forma 2 ×un entero (a saber 2k2), m2es par. La prueba queda completa.

14. ¿Qué es una demostración por casos?

La prueba por casos se emplea cuando la hipótesis original se divide de manera natural en
varios casos. Por ejemplo, la hipótesis “x es un número real” se puede dividir en casos: a) x
es un número real no negativo y b) x es un número real negativo. Suponga que la tarea es
probar p→q y que p es equivalente a p
1∨p 2∨. . . ∨p n(p1, . . . , p n son los casos). En lugar de probar (p1 ∨p2 ∨ . . . ∨ p n) →q,
(1.5.2)se prueba(p1→q) ∧(p2→q) ∧ . . . ∧(p n→q). (1.5.3)
Como se verá, la prueba por casos se justifica porque las dos afirmaciones son
equivalentes.
Primero suponga que alguna pies verdadera. En especial, se supone que p j es cierta.
Matemáticas Discretas – Demostración

Entonces p1 ∨p2 ∨. . . ∨ p n es verdadera. Si q es verdadera, entonces (1.5.2) es verdadera.

Ahora, pi →q es verdadera para toda i; de manera que (1.5.3) también es verdadera. Si q
es falsa, entonces (1.5.2) es falsa. Como p j →q es falsa, (1.5.3) también es falsa.

15. ¿Qué es una prueba de existencia?

Las técnicas de demostración presentadas hasta ahora se aplican a afirmaciones

cuantificadores universales. En la sección 1.3 se muestra que para probar ∃xP(x)
simplemente se necesita encontrar un elemento x del dominio de discurso que haga P(x)
verdadera. Tal prueba se llama prueba existencial.

Sea n a y b números reales con a<b. Pruebe que existe un número real x que satisface a
<x<b.

Demostración Es suficiente encontrar un número real x que satisfaga a<x<b. El número

real a la mitad entre ay b, sin duda satisface a<x<b.

Demuestre que existe un número primo p tal que 2p – 1 es compuesto (es decir, no es
primo).

Demostración Por prueba y error, se encuentra que 2p– 1 es primo para p=2, 3, 5, 7 pero
no para p=11, ya que 2 11– 1 =2048 – 1 =2047 =23 · 89.

16. ¿Qué es el razonamiento deductivo?

Este proceso de obtener conclusiones de una secuencia de proposiciones se llama
razonamiento deductivo. Las proposiciones que se dan, como (1.5.4), se llaman hipótesis o
premisas, y la proposición que se deriva de la hipótesis, como (1.5.5), se llama conclusión.
Un argumento (deductivo) consiste en hipótesis junto con una conclusión. Muchas
demostraciones en matemáticas y ciencias de la computación son argumentos deductivos.
Cualquier argumento tiene la forma
Si p1y p2 y... y p n, entonces q. (1.5.6)
Se dice que el argumento (1.5.6) es válido si la conclusión se obtiene de la hipótesis; es
decir, si p1 y p2 y... y p n son verdaderas, entonces q también debe ser verdadera. Este
análisis motiva la siguiente definición.

17. ¿Qué es una hipótesis en un argumento?

Un argumento (deductivo)consiste en hipótesis junto con una conclusión. Muchas
demostraciones en matemáticas y ciencias de la computación son argumentos deductivos.
Cualquier argumento tiene la forma
Matemáticas Discretas – Demostración

Si p1 y p2 y ... y p n, entonces q. (1.5.6)

Se dice que el argumento (1.5.6) es válido si la conclusión se obtiene de la hipótesis; es
decir, si p1 y p2 y ... y p n son verdaderas, entonces q también debe ser verdadera. Este
análisis motiva la siguiente definición.
Un argumento es una secuencia de proposiciones escritas

18. ¿Qué es una premisa en un argumento?

Las premisas, se dice que el argumento es deductivamente válido

Son los enunciados, que relacionados entre sí, permiten justificar o apoyar con conclusión
(la tesis o la creencia). En muchas ocasiones, las premisas son introducidas por palabras
como dado que, teniendo en cuenta que, se determina que…entre otras.

19. ¿Qué es una conclusión en un argumento?

La conclusión de deriva de las premisas y viene siendo la tesis o la creencia (Las premisas
apoyan la conclusión) las conclusiones, en muchas ocasiones

20. ¿Qué es un argumento válido?

En un argumento válido, a veces se dice que la conclusión se deriva de la hipótesis.
Observe que no se está afirmando que la conclusión es cierta; sólo se dice que si se
garantiza la hipótesis, también se debe garantizar la conclusión. Un argumento es válido
por su forma no por su contenido.
Determine si el argumento es válido.
[Primera solución] Se construye una tabla de verdad para todas las proposiciones
implicadas:

Se observa que cuando las hipótesis p→q y p son verdaderas, la conclusión q también es
verdadera; por lo tanto, el argumento es válido.
[Segunda solución] Es posible evitar escribir la tabla de verdad con una verificación directa
de que cuando las hipótesis son verdaderas, la conclusión también lo es.
Suponga que p→q y p son verdaderas. Entonces q debe ser verdadera, pues de otra
manera p→q sería falsa. Por lo tanto, el argumento es válido.
Matemáticas Discretas – Demostración

Represente el argumento
Si 2 =3, entonces yo me comí mi sombrero.
Me comí mi sombrero.
________________________________
∴2 =3
Simbólicamente y determine si el argumento es válido.
Si se hace
p: 2 =3, q: Me comí mi sombrero, el argumento se escribe como

21. Qué es un argumento inválido?

Los descartamos pues no garantizan la verdad de la conclusión, ni siquiera cuando las

premisas sabemos que son verdaderas. La validez es independiente de la verdad de sus
premisas. Sólo queda garantizada la verdad de la conclusión, haciendo una inferencia
válida a partir de premisas verdaderas.
Si el argumento es válido, entonces siempre que p→q y q sean ciertas ambas, p también
debe ser cierta. Suponga que p→q y q son verdaderas. Esto es posible si p es falsa y
Q es verdadera. En este caso, pn o es verdadera; así, el argumento es inválido.