Tema 1

Tema 1
Álgebra y Matemática discreta
Métodos de prueba
Índice
Esquema. . . . . . . . . . . . . . . . . . . . . . . 2
Ideas clave . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Introducción y objetivos . . . . . . . . . . . . . 3
1.2 Variables y cuantificadores . . . . . . . . . . . . 5
1.3 Tablas de verdad . . . . . . . . . . . . . . . . 11
1.4 Métodos de prueba . . . . . . . . . . . . . . . 13
1.5 Referencias bibliográficas . . . . . . . . . . . . . 20
1.6 Cuaderno de ejercicios . . . . . . . . . . . . . . 21
1.7 Soluciones cuaderno de ejercicios . . . . . . . . . 23
1.8 A fondo . . . . . . . . . . . . . . . . . . . . 23
1.9 Test . . . . . . . . . . . . . . . . . . . . . 24
Esquema

2
Tema 1. Esquema
Ideas clave
1.1 Introducción y objetivos
En el estudio de las matemáticas, existen dos temas fundamentales que se deben te-
ner presentes en todo momento. Estos son el saber cuando un argumento que se plan-
tea es correcto y en relación con este, conocer cuáles son los métodos o técnicas que
podemos usar para construir dichos argumentos matemáticos. Para ello, debemos co-
menzar con analizar la lógica de primer orden, también llamada lógica de predicados,
que es un sistema formal diseñado para estudiar la inferencia en los lenguajes de pri-
mer orden. Los lenguajes de primer orden son lenguajes formales con cuantificadores
que alcanzan sólo a variables individuales, y con predicados y conectores cuyos argu-
mentos son sólo constantes o variables de individuo. La lógica de primer orden tiene
el poder expresivo suficiente para definir a prácticamente todas las matemáticas.
Por tanto, en este primer tema abordaremos los elementos básicos relacionados con
la lógica de primer orden y los métodos de prueba, los cuales nos permiten expresar
en lenguaje matemático las afirmaciones con las que se construyen los teoremas. De
esta forma, encontraremos herramientas que nos permiten justificar razonamientos o
silogismos y hacer demostraciones de los distintos teoremas o proposiciones median-
te las reglas de inferencia.
Para ello, debemos enriquecer nuestra teoría con la introducción de predicados que
se puedan aplicar a individuos y colectivos de individuos y conectores que relacio-
nan dichos predicados. Con esta finalidad introducimos el cálculo de predicados y el
concepto de cuantificador. Seguidamente, mostramos distintos métodos (directos e
indirectos) para justificar la validez cierta afirmación matemática cuya formulación
contiene predicados. Por último, presentamos el método de inducción que trata de

3
Tema 1. Ideas clave
demostrar resultados donde los predicados hacen referencia al conjunto de los nú-
meros naturales.
Los métodos de demostración que se abordan en este tema, son importantes, por va-
rias razones, en primer lugar, por que nos sirven para demostrar teoremas matemáti-
cos, pero también, por que tienen gran aplicación en ciencias de la computación, para
la demostración de algoritmos, la verificación de la seguridad de un sistema operativo
o para comprobar que un determinado programa funciona de forma correcta.
Los objetivos que nos proponemos alcanzar en este tema son los siguientes:
I Conocer el contexto en el que se enmarcan los métodos de prueba, tanto desde el

punto de vista matemático como computacional.
I Conocer el modo de expresar los argumentos matemáticos, a través de los predi-

cados y los cuantificadores
I Utilizar adecuadamente predicados y cuantificadores para describir proposiciones

ciertas.
I Crear las tablas de la verdad.
I Demostrar proposiciones ciertas y sencillas utilizando las técnicas de prueba direc-

ta, contraposición, reducción al absurdo o inducción.
I Encontrar contraejemplos para proposiciones falsas.
I Comprender el razonamiento matemático de inducción y recursividad.
I Definir sucesiones y estructuras mediante recursión.
Para alcanzar estos objetivos, se propone la siguiente subdivisión del contenido de

este tema:
I Variables y cuantificadores.

4
Tema 1. Ideas clave
I Métodos de prueba.
• Métodos directos.
• Métodos indirectos.
I Inducción.
I Recursión.
1.2 Variables y cuantificadores
El desarrollo de la matemática a través de los siglos ha llevado siempre implícita la ne-

cesidad de argumentar de forma consistente las proposiciones que pueden llegar a ser
los teoremas en los que se apoya la teoría matemática. Así, es importante comenzar
este tema con algunas definiciones:
Definición 1: Predicado
Un predicado p(x) es una expresión lingüística que puede conectarse con una o
varias otras expresiones para formar una oración o proposición.
Definición 2: Proposición
Una proposición es una afirmación de la cual se puede decir sin ambigüedad (y

de forma excluyente) que es verdadera V o falsa F . Las proposiciones se suelen
representar mediante las letras minúsculas o mayúsculas p, q, r . . .
Para crear una proposición, debemos definir la variable el valor de x, para lo cual,
podemos asignar una valor a la variable o cuantificarla. Cuando la variable no tiene
restricciones se llama variable libre, mientras que si restringimos el valor de la variable
se llama variable cuantificada.

5
Tema 1. Ideas clave
Por ejemplo, en la oración «Marte es un planeta», la expresión «es un planeta» es un
predicado que se conecta con la expresión «Marte» (variable libre) para formar una
oración o proposición. De forma análoga, en la oración «Júpiter es más grande que
Marte», la expresión «es más grande que» es un predicado que se conecta con dos
expresiones, «Júpiter» (variable cuantificada) y «Marte» (variable libre), para formar
una proposición.
Definición 3: Cuantificador
Un cuantificador es una expresión que afirma que una condición se cumple para
un cierto número de individuos.
En la lógica clásica, los dos cuantificadores más estudiados son el cuantificador uni-
versal y el cuantificador existencial. El primero afirma que una condición se cumple
para todos los individuos de los que se está hablando. Se denota por el símbolo ∀,
usando la sintaxis ∀x p(x) y se lee “para todo valor de x, la propiedad p es cierta”; el
segundo que se cumple para al menos uno de los valores de la variable. Se denota con
el símbolo ∃, usando la sintaxis ∃x : p(x) y se lee “existe algún valor de x tal que p es
cierta”.
Por ejemplo, la expresión “para todo x (∀x)” es un cuantificador universal, que ante-
puesto a “x < 3”, produce: para todo x, x < 3, (∀x < 3). Esta es una expresión
con valor de verdad, en particular, una expresión falsa, pues existen muchos números
(muchos x) que son mayores que tres. Anteponiendo en cambio la expresión “para
al menos un x”, un cuantificador existencial, se obtiene: Para al menos un x, x < 3,
(∃x < 3). La cual resulta ser una expresión verdadera.
Se ha de tener en cuenta que es posible intercambiar los cuantificadores usando una

negación, así, podemos realizar las siguientes transformaciones:
¬(∀x, p(x)) ⇐⇒ ∃x, ¬p(x)
¬(∃x, p(x)) ⇐⇒ ∀x, ¬p(x)

6
Tema 1. Ideas clave
La primera se lee como “ no para todo x se cumple p(x)”, que es equivalente a decir
“ existe algún x para el que no se cunple p(x).” Por otra parte, la segunda se lee “ no
existe ningún x para el que se cumpla p(x)” que es equivalente a decir “ para todo x
no se cumple p(x)”
Las proposiciones se pueden combinar entre ellas, para crear nuevas que reflejen afir-
maciones mas complejas. La combinación entre ellas se realiza mediante los conecto-
res lógicos , los cuales tienen sus propios símbolos de representación. Los conectores
mas habituales son los siguientes:
I Negación “no” (¬)
La proposición (¬p), que se lee como “no p”, es cierta cuando la proposición p es
falsa. Des esta forma, cuando la proposición p es verdadera, lógicamente la pro-
posición ¬p será falsa. Por ejemplo, si la p es que “nieve no es blanca”, sabemos
que esta proposición es falsa, por tanto la proposición ¬p, (la nieve es blanca), será
cierta.
I Conjunción “y” (∧)
La proposición p ∧ q, que se lee “p y q”, será cierta cuando las dos proposiciones
que se relacionan, sean ciertas. Esto implica que basta que una de ellas es falsa, la
conjunción de ambas también será falsa. Así, la proposición p ∧ q donde p = La
nieve es blanca y q = París es la capital de Italia, es falsa, ya que la proposición “q”
lo es.
I Disyunción “o ” (∨)
La proposición p ∨ q, que se lee,“p o q”, es cierta siempre que al menos una de las
proposiciones p y q lo sea. Eso quiere decir que p∨q es cierta en tres casos: cuando
p es falsa y q es verdadera, cuando p es cierta y q es falsa y cuando p y q son ciertas.
En el Ejemplo 1, p ∨ q es la proposición «la nieve es blanca o la nieve es roja».
I Condicional “si . . .” entonces “. . .” (−→)
La proposición p −→ q (se lee si p entonces q) es falsa solo cuando p es cierta y q

es falsa. Debe entenderse el significado de este conector: lo que afirma es que si

7
Tema 1. Ideas clave
p es una proposición cierta, entonces q también lo es; sin embargo, no se afirma
nada acerca de la certeza de p y q. Por ejemplo, la proposición “si la nieve no es
blanca entonces 2+3=7” es cierta ya que las proposiciones “la nieve no es blanca”
y “2+3=7” son ambas falsas.
I Bicondicional “sí y solo sí” (←→)
La proposición p ←→ q (se lee p sí y solo si q) es cierta cuando las dos proposiciones

p y q son ciertas y también cuando ambas proposiciones son falsas. Por ejemplo “la
nieve es blanca sí y solo sí París es la capital de Francia”.
Los conectores se pueden utilizar para unir o relacionar las distintas proposiciones,
de tal forma que se pueden obtener, partiendo de proposiciones sencillas, otras mas
complejas.
Definición 4
Se denomina proposición atómica a aquellas que no incluyen conectores (son las

mas simples), mientras que se denominan proposiciones moleculares a aquellas
que están compuestas por dos o mas proposiciones atómicas unidas mediante
conectores.
Cuando una proposición molecular incluye varios átomos o diversos conectores

puede ser de utilidad utilizar el paréntesis para evitar ambigüedades:
«En este momento llueve y hace sol o está nevando»: p ∧ q ∨ r
No es clara salvo que utilicemos algún signo de puntuación, tal como se puede ver
a continuación:
«En este momento llueve, y hace sol o está nevando»: p ∧ (q ∨ r).
«En este momento llueve y hace sol, o está nevando»: (p ∧ q) ∨ r.

8
Tema 1. Ideas clave
Al igual que en las otras operaciones matemáticas, para reducir el número de parén-
tesis necesarios para representar las fórmulas proposicionales complejas se establece
una jerarquía de los conectores. Esta es, de mayor a menor tal como se indica:
←→, −→, ∧∨, ¬
El hecho de que la jerarquía de un conector sea más grande que la del otro quiere
decir que, en ausencia de paréntesis, el segundo se ejecuta antes que el primero. Por
ejemplo, en la expresión ¬p ←→ q la negación se debe aplicar únicamente a la pro-
posición p antes de aplicar el bicondicional, es decir, es equivalente a (¬p) ←→ q.
Cabe notar que los conectores de disyunción y conjunción tienen la misma jerarquía,
así que en ningún caso podemos escribir p ∧ q ∨ r porque no hay manera de saber si
esta expresión representa (p ∧ q) ∨ r o p ∧ (q ∨ r).
Ejemplo 1.
Estudiar la posibilidad de suprimir paréntesis en la proposición compuesta: «si
hoy llueve, entonces mañana no saldremos a pescar o cogeremos un resfriado».
Definiendo las proposiciones:
p: hoy llueve; q: mañana saldremos a pescar r: cogeremos un resfriado.
Podemos escribir la proposición como p −→ ((¬q)∨r). Pero como el condicional

tiene preferencia sobre la disyunción y esta sobre la negación, podemos suprimir
todos los paréntesis y escribir p −→ ¬q ∨ r).
Definición 5
Podemos distinguir distintos tipos de proposiciones, así, una proposición com-

puesta que siempre es cierta para cualquiera de los valores de sus proposiciones
atómicas recibe el nombre de tautología. La negación de una tautología, es decir,

9
Tema 1. Ideas clave
una proposición compuesta que siempre es falsa, recibe el nombre de contradic-
ción. Si unas veces es falsa y otras cierta, recibe el nombre de contingencia.
Además de los conectores lógicos que acabamos de ver, podemos encontrar con otro
tipo de relaciones entre las proposiciones y que serán de interés para construir los
razonamientos lógicos que permiten obtener las demostraciones de teoremas o pro-
posiciones complejas.
Se dice que dos proposiciones atómicas (o compuestas) cualesquiera p y q constituyen

una relación de implicación, cuya sintaxis es p ⇒ q (se lee p implica q) sí y solo si la
implicación p→q es una tautología.
Por último, se dice que dos proposiciones atómicas (o compuestas) cualesquiera p y

q son lógicamente equivalentes, denotado por p ⇐⇒ q, sí y solo si la bicondicional
p ↔ q es una tautología.

10
Tema 1. Ideas clave
1.3 Tablas de verdad
Para saber si una proposición compuesta es o no cierta se utilizan las tablas de verdad,
cuadros donde se muestran los valores de verdad de esta proposición en función de
los valores de verdad de las proposiciones que la componen.
Definición 6: Tabla de verdad
Una tabla de verdad es una matriz que contiene los valores de verdad de una
proposición en función de los valores de verdad de las proposiciones atómicas
que la componen.
A continuación, se muestran las tablas de verdad para los conectores analizados ante-
riormente:
Figura 1: Tablas de verdad. Fuente: Elaboración propia

11
Tema 1. Ideas clave
Tal como se ha comentado, las tablas de verdad permiten analizar las proposiciones,
atómicas o moleculares, así, podemos decir que p ∨ ¬q es una tautología, mientras
que p ∧ ¬q es una contradicción, como se puede ver en la siguiente tabla de la verdad:
p ¬p p ∨ ¬p p ∧ ¬p
F V V F
V F V F
Y para terminar esta sección, analizamos el siguiente ejemplo:
Ejemplo 2.
Probar la equivalencia lógica de las siguientes proposiciones
(p ∨ q)y(q ∧ p)
Para ello, debemos construir la tabla de la verdad para cada una de las proposi-
ciones, como se muestra a continuación:
p q p∨p p∧p
F F F F
F V V V
V F V V
F V V V
Dado que las dos últimas columnas contienen los mismos resultados, la relación
(p ∨ q)↔(q ∧ q) es una tautología.

12
Tema 1. Ideas clave
1.4 Métodos de prueba
A continuación, vamos a introducir los métodos de prueba que permiten demostrar

que un teorema es verdadero mediante una secuencia de sentencias que constituyen
un argumento al que llamamos demostración. Un teorema es una sentencia que se
puede demostrar que es verdadera y para ello, se siguen una serie de métodos que
permiten obtener sentencias nuevas en base a las anteriores, es decir, los métodos de
prueba utilizan predicados y conectores para construir nuevos predicados o proposi-
ciones, que de forma lógica concluyen la veracidad de la sentencia o teorema que se
quiere demostrar.
Para ello se utilizan las reglas de inferencia, que enlazan cada uno de los pasos que for-
man la demostración. Así, las reglas de inferencia, constituyen cada uno de los pasos
lógicos que nos llevan de p a q para demostrar una sentencia condicional (p −→ q). A
la primera parte de la sentencia condicional se la llama premisa, antecedente o hipó-
tesis y a la segunda, conclusión, consecuencia o tesis.
Son muchas las reglas de inferencia que podemos manejar, de las cuales son especial-
mente importantes el Modus ponens y Modus tollens, cuya sintaxis es la siguiente:
Modus ponens:
p
p→q
∵q
Que se lee: “si p implica q y p es cierto, entonces q es cierto”.
Modus tollens:
¬q
p→q
∵ ¬p
Que se lee: “si q es falso y p implica q, entonces p es falso”.

13
Tema 1. Ideas clave
Figura 2: Reglas de inferencia. Fuente: Elaboración propia
La siguiente tabla muestra algunas de ellas. Todas pueden demostrarse fácilmente uti-
lizando tablas de verdad.
Los métodos de prueba que se utilizan para la demostración de teoremas o sentencias

son muchos y dependiendo de la sentencia que se desee demostrar, será mas conve-
niente la utilización de uno u otro. Los mas importantes que se verán en este tema y
en el tema siguiente son el Método de prueba directo, el Método de prueba indirecto
y los Métodos de inducción.
Dada una sentencia condicional (p→q) la diferencia fundamental entre los métodos
directos e indirectos, radica en que si aplicamos un método directo, lo que hacemos
es estudiar la premisa p para sacar conclusiones sobre la q. En cambio, si el método es
indirecto, se estudia q para sacar conclusiones sobre p→q
Demostraciones directas: Una implicación condicional (Ej.- p→q), se puede demostrar

de forma directa, analizando p. Si esta es verdadera, entonces q también es verdadera.
y por tanto, nunca ocurrirá que q sea falsa. Para realizar este tipo de demostraciones,
suponiendo que p es verdadera, se buscan reglas de inferencia y teoremas que ya han

14
Tema 1. Ideas clave
sido demostrados para demostrar que q debe ser también verdadera.
Ejemplo 3.
Definición: Un número entero n es par, si existe un entero k tal que n = 2k y es

impar si existe un entero k tal que n = 2k + 1.
Dada la definición de número par y número impar, demostrar de forma directa

que « Si n es un entero impar, entonces n2 es un número entero impar».
Solución: Suponemos cierta la hipótesis de que la implicación es verdadera, es

decir, que n es un número impar. Entonces , n = 2k + 1, siendo k un número
entero. Calculamos por tanto n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1.
Como se puede ver, el resultado es el doble del entero mas una unidad, por tanto
es también un número impar.
Si tenemos en cuenta que la implicación p→q es equivalente a su contrarecíproca, es

decir ¬q→¬p, podemos realizar el análisis de veracidad de la sentencia estudiando la
veracidad de la contrarecíproca. Este argumento es el que se conoce como demostra-
ción indirecta. Veamos un ejemplo:
Ejemplo 4.
Demostrar que hay infinitos números primos (resultado de Euclides).
Solución: Supongamos que los números primos no son infinitos. Entonces, serían
finitos:
2, 3, 5, 7, ...P

15
Tema 1. Ideas clave
Siendo P el mayor de todos los números primos.
Consideramos ahora el número H = (2·3·5·7·...·P ) + 1
H no es primo, pues es mayor que P. Entonces H debe tener algún divisor primo.
Pero si dividimos H por cualquiera de los números primos, obtendremos resto 1,
por la forma en que se ha definido H.
De esta forma hemos llegado a una contradicción. Luego la afirmación inicial es

cierta.
En este ejemplo se han combinado dos métodos de prueba, la demostración indirecta,

ya que para demostrar el teorema, lo que hemos hecho es rechazar su contrario y
posteriormente, para refutar este, hemos llegado a una contradicción, utilizando así
el método de demostración por reducción al absurdo.
Este vídeo explica 2 métodos de demostración matemática, uno es la demostración di-

recta y otro es una demostración indirecta llamada demostración por contraposición,
y pone varios ejemplos.
� Accede al vídeo: Demostración directa y Demostración indirecta por contraposi-

ción
Finalmente, cabe destacar que los métodos vistos hasta ahora, son métodos de razo-
namiento deductivo porque van desde proposiciones generales a conclusiones parti-
culares. Por contraposición, el razonamiento inductivo construye proposiciones gene-
rales a partir de observaciones particulares. El método de demostración por inducción
que se abordará en el siguiente tema.

16
Tema 1. Ideas clave
Estrategias de demostración
Una vez se han definido los métodos mas utilizados para realizar demostraciones, cabe
la pregunta ¿cúal es el método mas apropiado utilizar para demostrar un teorema?. La
respuesta no siempre es única y en ocasiones dependerá de la experiencia o intuición
o la dificulta de la demostración que se pretende obtener. En cambio, si podemos dar
unas pautas o pistas que ayuden en el proceso. En primer lugar, debemos evaluar la
eficacia de una demostración directa. Debemos desarrollar las definiciones que vie-
nen dadas en la hipótesis inicial y luego comenzar a razonar con ellas, teniendo en
cuenta también los axiomas o teoremas que puedan ser necesarios. En caso de no
encontrar ningún argumento que nos lleva a alguna conclusión, debemos intentar el
mismo procedimiento mediante la demostración indirecta, asumiendo que la conclu-
sión de la implicación que buscamos demostrar es falsa. En cualquier caso, tal como
se comentó, el llegar a obtener una demostración, en ciertas ocasiones puede resultar
complicado y requiere de cierta habilidad en el manejo de teoremas, axiomas y uso
de conectores. Tres importantes estrategias de demostración son las siguientes:
I Razonamiento hacia delante y hacia atrás. Esta es una de las estrategias mas co-
mún para demostrar razonamientos relativamente sencillos. En este caso, la idea
es comenzar con la hipótesis e ir elaborando una secuencia de pasos que lleven a
la conclusión. Si queremos realizar un razonamiento indirecto, se puede comenzar
por la conclusión y mediante una secuencia lógica de pasos, llegar a la negación de
la hipótesis. Es lo que se conoce como razonamiento hacia delante. Desgraciada-
mente, en muchas ocasiones, la conclusión puede encontrarse lejos de la hipótesis,
por lo que resultará complicado llegar a ella por este camino. En esa situación, pue-
de ser interesante utilizar el razonamiento hacia atrás, que consiste en demostrar
la sentencia q con la propiedad p −→ q.
Ejemplo 5.
Demuestra el teorema de Pitágoras.

17
Tema 1. Ideas clave
Solución: dado un triángulo rectángulo con catetos que miden a y b, e hipote-
nusa que mide h, construimos la siguiente figura geométrica:
El cuadrado interior tiene lado h, mientras que el cuadrado mayor tiene lado
a + b. La suma del área del cuadrado interior más cuatro veces el área de los
triángulos equivale al área del cuadrado grande. Es decir, se cumple la siguiente
igualdad:
ab
h2 + 4 = (a + b)2 −→ h2 + 2ab = a2 + 2ab + b2 −→ h2 = a2 + b2
2
Quedando así demostrado de forma directa el teorema de Pitágoras
I Demostración por casos. Esta estrategia consiste en demostrar la proposición para

cada uno de los casos. Se utiliza cuando no se encuentra de forma evidente la ma-
nera de comenzar la demostración, pero si que se encuentra en cada caso cierta
información que permite dar pasos hacia la demostración de la proposición. Por
ejemplo para hacer demostraciones sobre números, se puede comenzar estudian-
do la proposición para los números pares o los impares... de tal manera que po-
damos encontrar ciertas conclusiones que ayuden a finalizar la demostración. Un
error común en este procedimiento, es no considerar todos los casos.
I Adaptación de demostraciones conocidas. Una buena forma de encontrar demos-

traciones, es partir de otras conocidas. En muchas ocasiones, una demostración
conocida se puede adaptar para crear una nueva demostración. El simple entendi-
miento de una demostración, puede dar pistas o estrategias que se pueden aplicar
en la demostración de otros teoremas. Por ello es importante detenerse en com-
prender los pasos lógicos de aquellas demostraciones que se conocen.

18
Tema 1. Ideas clave
Errores en demostración
Conviene terminar este tema comentando que en ocasiones se puede llegar a con-
clusiones o demostraciones erróneas debido a fallos en la construcción de la propia
demostración. Uno de los fallos mas comunes es el de cometer fallos en la aritméti-
ca y álgebra básica, que suelen darse cuando se realizan demostraciones de fórmulas
especialmente complejas. Por ello es importante revisar cuidadosamente los pasos
realizados. Cada paso en la demostración debe ser correcto y la conclusión se debe
obtener de los pasos que se han seguido de forma lógica. Vamos a ilustrar con el fa-
mosos ejemplo de la supuesta demostración de que 1 = 2:
Ejemplo 6.
«Demostración»: Consideramos los siguientes pasos:
Paso Razonamiento
(1) a = b Dato
(2) a2 = ab Multiplicando ambos lados de (1) por a
(3) a2 − b2 = ab − b2 Restando b2 a ambos lados de (2)
(4) (a − b)(a + b) = b(a − b) Factorizando ambos lados de (3)
(5) a + b = b Dividiendo por (a − b) ambos lados de (4)
(6) 2b = b Reemplazando a por b en (5), por que a = b, y simplificando
(7) 2 = 1 Dividiendo ambos lados de (6) por b
Solución: Todos los pasos son correctos salvo el paso (5), ya que se ha dividido
en ambos lados de la ecuación por (a − b), pero esto no se puede hacer ya que
(a − b), de acuerdo con (1), es igual a cero.

19
Tema 1. Ideas clave
1.5 Referencias bibliográficas
Rosen, K. H., & Morales, J. M. P. (2004). Matemática discreta y sus aplicaciones.
Koshy, T. (2004). Discrete mathematics with applications. Elsevier.
Grimaldi, R. P. (2006). Discrete and Combinatorial Mathematics, 5/e. Pearson Educa-

tion India.

20
Tema 1. Ideas clave
1.6 Cuaderno de ejercicios
Ejercicio 1. Busca las leyes de Morgan que relacionan la conjunción «y» la disyun-
ción «o» y la negación.
Solución:
¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B
¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B
En palabras: la negación de «A y B» es «no A, o no B». La negación de «A o B» es

«no A y no B».
Ejercicio 2. Demuestra que es cierta la siguiente afirmación de números enteros
∀x, ∃y, x + y = 0
Ejercicio 3. El predicado p(x) es cierto si y solo si x es un número primo. Demues-

tra que la siguiente afirmación de números naturales es falsa:
∀n, p(n) −→ p(2n − 1)
Un contraejemplo es n = 11 ya que la hipótesis es cierta, es un número natural y

es primo (11 es primo), pero hemos visto que p(2n −1) es falso (2047 no es primo),
luego p(n) −→ (2n −1) es falso y la afirmación del enunciado también.
Ejercicio 4. Indicar si las siguientes fórmulas proposicionales son tautologías, con-

tingencias o contradicciones.
I ¬p ∧ ¬q

21
Tema 1. Ideas clave
I ¬(p −→ q) ∧ (q −→ p)
I ((p −→ q) −→ q) −→ (p ∨ q)
Ejercicio 5. Demuestra que hay infinitos números primos.

22
Tema 1. Ideas clave
1.7 Soluciones cuaderno de ejercicios
Solución 1.
¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B
¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B
En palabras: la negación de «A y B» es «no A, o no B». La negación de «A o B» es

«no A y no B».
Solución 2. Nos piden ver que para cualquier número entero , existe un núme-
ro entero y que, al sumarlos, el resultado es 0. Para demostrarlo, consideramos
un cualquiera (como tenemos que demostrarlo para cualquier valor, lo dejamos
como variable), ahora hay que encontrar un y correspondiente que cumpla la
condición. Viendo la ecuación, se propone el siguiente: y = −x (como y es un nú-
mero entero puede tomar valores negativos). y comprobamos que efectivamente
x + y = x + (−x) = 0, por lo que la proposición es cierta.
Solución 3. En palabras, nos piden ver que no es cierto que 2 elevado a un número
primo menos 1 siempre es un número primo. Tenemos que ver que una expre-
sión que empieza por un cuantificador universal es falsa. Para ello es suficiente
encontrar un caso en que falla: un contraejemplo. La condición p(n) −→ p(2−1)
siempre es cierta cuando n no es primo. Tenemos que buscar un contraejemplo
entre los números primos. Probaré primos hasta encontrar un contraejemplo:
I n = 2 : 22 −1 = 3.
I n = 3 : 23 −1 = 7.
I n = 5 : 25 −1 = 31.
I n = 7 : 27 −1 = 127.
I n = 11 : 21 1−1 = 2047 = 23×89.

23
Tema 1. Ideas clave
Un contraejemplo es n = 11 ya que la hipótesis es cierta, es un número natural y
es primo (11 es primo), pero hemos visto que p(2n −1) es falso (2047 no es primo),
luego p(n) −→ (2n −1) es falso y la afirmación del enunciado también.
Solución 4. Realizando las tablas de verdad, se concluye que son contingencia,

contradicción y tautología, respectivamente.
Solución 5. Supongamos que es falso, es decir, solo hay una cantidad finita de nú-
meros primos. Construimos un nuevo número, al que llamaré «q», multiplicando
todos los primos y sumando 1. q no es divisible por ningún número primo «p», ya
que está formado por la suma de un múltiplo de p más 1, que no es divisible por p.
En consecuencia, q es un número primo. Por como lo hemos construido, q es ma-
yor a cualquier número primo. Por consiguiente, es un nuevo número primo. Esto
entra en contradicción con la suposición que habíamos empezado diciendo que
hay un número finito de números primos. Por reducción al absurdo, concluimos
que hay una cantidad infinita de números primos.

24
Tema 1. Ideas clave
1.8 A fondo

25
Tema 1. Ideas clave
A fondo
Método de demostración
El capítulo de Miguel de Guzmán describe y ejercita las técnicas de demostración directa
e indirecta.
Accede al artículo desde el aula virtual o a través de la siguiente dirección web:
http://www.mat.ucm.es/cosasmdg/cdsmdg/05edumat/remediosfracasouniv/laborator
io99/segunda%20parte/cap2dem.doc
La demostración por reducción al absurdo

Este vídeo de Fernando Lazo explica cómo se hace una demostración por reducción
al absurdo.
Accede al vídeo desde el aula virtual o a través de la siguiente dirección web:
https://www.youtube.com/watch?v=kJ4we8gDMkI
Discrete Mathematics Using a Computer

Este libro presenta los principales temas de la matemática discreta con un fuerte
énfasis en las aplicaciones a la informática. Se utilizan programas informáticos para
aplicar e ilustrar las ideas matemáticas, ayudando al lector a obtener un
entendimiento concreto de las matemáticas abstractas. Los programas también son
útiles para los cálculos prácticos y pueden servir como una base para los paquetes
de software más grandes.
Diseñado para el primer y segundo año de los estudiantes de pregrado, el libro

también es ideal para autoestudio. No se requieren conocimientos previos de
programación funcional, el libro y la documentación en línea ofrecen todo lo
necesario.
Podrás encontrar información sobre el libro en su página oficial:
http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/

26
Tema 1. Ideas clave
1.9 Test

27
Tema 1. Ideas clave
Test
1. ¿ Decir que ∀𝑥, ¬𝑝(𝑥) es equivalente a decir:
A. ¬(∀𝑥, ¬𝑝(𝑥))
B. ¬(∀𝑥, 𝑝(𝑥)
C. ¬(∃𝑥, 𝑝(𝑥)
D. ∃𝑥, 𝑝(𝑥)
2. ¿Cuál es la negación de la proposición ∀𝜖,∃ 𝛿,∀ x,p(x,𝜖,𝛿)?:

A. ∃𝜖, ∀ 𝛿, ∃ x, p(x,𝜖,𝛿 ).
B. ∃𝜖,∀ 𝛿,∃ x,¬ p(x,𝜖,𝛿).
C. ∀𝜖, ∃ 𝛿, ∀ x, ¬p(x,𝜖,𝛿 ).
D. Ninguna de las anteriores.
3. ¿Qué podemos deducir del número x x a partir de la afirmación

∃y, ∃z, y ∈ Z∧z∈Z∧z≠0∧x=y/z
A. x es un número natural.
B. x es un número entero.
C. x es un numero racional.
D. x es par.
4. Cuando comparamos una proposición con un predicado encontramos que:

A. Ambos representan verdades matemáticas sobre una variable.
B. Ambos representan hechos desconocidos respecto a una variable
C. La proposición es una afirmación sobre una variable.
D. El predicado puede ser cierto o no.

28
Tema 1. Ideas clave
5. Cuál de estas afirmaciones es falsa:
A. El modus ponens se aplica en la prueba directa.
B. El modus tollens se aplica en la prueba por inducción.
C. El modus tollens se aplica en la prueba por reducción al absurdo.
D. El modus tollens se aplica en la prueba por contraposición.
6. El teorema de Pitágoras que demuestra que no hay ningún número racional x que
cumpla que x2=2 se demostró por:
A. Prueba directa.
B. Contradicción.
C. Contraposición.
D. Inducción.
7. La prueba por contraposición:

A. Es una forma de prueba indirecta.
B. Se opone a la reducción al absurdo.
C. La reducción al absurdo es una forma de contraposición.
D. Es una forma de prueba por inducción.
8. Qué podemos decir de la deducción «siempre que llueve, el autobús llega tarde.
Como hoy el autobús ha llego tarde, esto quiere decir que llueve»?
A. Ha usado modus ponens.
B. Ha usado modus tollens.
C. No está lloviendo.
D. La deducción es errónea.
9. Cuál de las siguientes expresiones es una proposición?

A. «El Quijote»
B. ∀ 𝑥
C. «Sueño despierto».
D. «Sin x »

29
Tema 1. Ideas clave
10. Cuál de estas afirmaciones es cierta
A. La prueba indirecta es la forma de prueba por contradicción.

B. La prueba indirecta es la forma de prueba por contraposición.
C. La prueba por contraposición es una forma de prueba directa.
D. La prueba por contraposición y por contradicción son formas de prueba
indirecta.

30
Tema 1. Ideas clave

Tema 1 - Métodos de Prueba

Cargado por

Copyright:

Formatos disponibles

Tema 1 - Métodos de Prueba

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tema 1 - Métodos de Prueba

Cargado por

Copyright:

Formatos disponibles

Álgebra y Matemática discreta

1.1 Introducción y objetivos . . . . . . . . . . . . . 3

1.2 Variables y cuantificadores . . . . . . . . . . . . 5

1.3 Tablas de verdad . . . . . . . . . . . . . . . . 11

1.4 Métodos de prueba . . . . . . . . . . . . . . . 13

1.5 Referencias bibliográficas . . . . . . . . . . . . . 20

1.6 Cuaderno de ejercicios . . . . . . . . . . . . . . 21

1.7 Soluciones cuaderno de ejercicios . . . . . . . . . 23

Álgebra y Matemática discreta

1.1 Introducción y objetivos

Álgebra y Matemática discreta

I Conocer el contexto en el que se enmarcan los métodos de prueba, tanto desde el

I Conocer el modo de expresar los argumentos matemáticos, a través de los predi-

I Utilizar adecuadamente predicados y cuantificadores para describir proposiciones

I Crear las tablas de la verdad.

I Demostrar proposiciones ciertas y sencillas utilizando las técnicas de prueba direc-

I Encontrar contraejemplos para proposiciones falsas.

I Comprender el razonamiento matemático de inducción y recursividad.

I Definir sucesiones y estructuras mediante recursión.

Para alcanzar estos objetivos, se propone la siguiente subdivisión del contenido de

Álgebra y Matemática discreta

1.2 Variables y cuantificadores

El desarrollo de la matemática a través de los siglos ha llevado siempre implícita la ne-

Una proposición es una afirmación de la cual se puede decir sin ambigüedad (y

Álgebra y Matemática discreta

Se ha de tener en cuenta que es posible intercambiar los cuantificadores usando una

¬(∀x, p(x)) ⇐⇒ ∃x, ¬p(x)

¬(∃x, p(x)) ⇐⇒ ∀x, ¬p(x)

Álgebra y Matemática discreta

I Negación “no” (¬)

I Conjunción “y” (∧)

I Condicional “si . . .” entonces “. . .” (−→)

La proposición p −→ q (se lee si p entonces q) es falsa solo cuando p es cierta y q

Álgebra y Matemática discreta

I Bicondicional “sí y solo sí” (←→)

La proposición p ←→ q (se lee p sí y solo si q) es cierta cuando las dos proposiciones

Se denomina proposición atómica a aquellas que no incluyen conectores (son las

Cuando una proposición molecular incluye varios átomos o diversos conectores

«En este momento llueve y hace sol o está nevando»: p ∧ q ∨ r

«En este momento llueve, y hace sol o está nevando»: p ∧ (q ∨ r).

«En este momento llueve y hace sol, o está nevando»: (p ∧ q) ∨ r.

Álgebra y Matemática discreta

←→, −→, ∧∨, ¬

p: hoy llueve; q: mañana saldremos a pescar r: cogeremos un resfriado.

Podemos escribir la proposición como p −→ ((¬q)∨r). Pero como el condicional

Podemos distinguir distintos tipos de proposiciones, así, una proposición com-

Álgebra y Matemática discreta

Se dice que dos proposiciones atómicas (o compuestas) cualesquiera p y q constituyen

Por último, se dice que dos proposiciones atómicas (o compuestas) cualesquiera p y

Álgebra y Matemática discreta

Definición 6: Tabla de verdad

Figura 1: Tablas de verdad. Fuente: Elaboración propia

Álgebra y Matemática discreta

Y para terminar esta sección, analizamos el siguiente ejemplo:

Álgebra y Matemática discreta

A continuación, vamos a introducir los métodos de prueba que permiten demostrar

Que se lee: “si q es falso y p implica q, entonces p es falso”.

Álgebra y Matemática discreta