Álgebra y Matemática Discreta

Elena Giménez de Ory

Tema 1: Métodos de prueba

Índice

► Variables y cuantificadores

► Métodos de prueba

2
Variables y cuantificadores

Leer el Capítulo 1 del libro “Matemática Discreta y Aplicaciones”,

por Kenneth H. Rosen; J. M. Pérez

Proposición: Oración declarativa que es verdadera o falsa, pero no ambas

cosas a la vez

Ejercicio 1. Decidir si son proposiciones o no las siguientes oraciones.

1.Bruselas es la capital europea

2.Toronto es la capital de Canadá
3.¿Qué hora es?
4.Lee esto con atención
5.x + 1 = 2

3
Variables y cuantificadores

Si p y p son proposiciones, entonces las oraciones

“No se cumple p” (no p)

“p y q” (conjunción)

“p o q” (disyunción)

también son proposiciones

4
Variables y cuantificadores

5
Variables y cuantificadores

Si p y p son proposiciones, entonces

•El conectivo exclusivo de p y q es la proposición que solo es verdadera

cuando lo es exactamente una de las dos proposiciones

•La implicación (p implica q) es la proposición que es verdadera cuando p

es verdadera y q es falsa

6
Variables y cuantificadores

Si tenemos la proposición “p implica q”

La proposición recíproca es “q implica p”

La proposción contrarrecíproca es “no q implica no p”

Ejercicio: probar que la tabla de verdad de la implicación es igual a la de su

contrarrecíproco

Doble implicación

7
Variables y cuantificadores

Un predicado P(x) es una afirmación sobre una variable x

El predicado no es verdadero ni falso (es decir, no es una proposición). Para

saber si es verdadero o falso especificarse el valor a x

Ejemplo:

P(x): x < 3, P(x) predicado.

P(4) proposición verdadera, P(2) proposición falsa

8
Variables y cuantificadores

La cuantificación universal de P(x) es la proposición “P(x) es verdadera

para todos los valores x del dominio”

La cuantificación existencial de P(x) es la proposición “Existe un

elemento de x en el dominio tal que P(x) es verdadera”

9
Variables y cuantificadores

Una variable x está ligada cuando le asignamos un valor o usamos un

cuantificador sobre ella

Ejemplo 1:

“Algún estudiante de esta clase ha visitado México” puede formalizarse

como:

M(x): “x ha visitado México”. Si el dominio de x es la clase,

“Existe x tal que M(x)”

10
Variables y cuantificadores

Ejemplo 2:

Existe x tal que M(x, y)

(Para todo x, (P(x) y Q(x))) o (R(x))

Para todo x, (P(x) y Q(x))) o R(x)

11
Variables y cuantificadores

Cuantificación implícita en matemáticas

Ejemplos:

1. Todo número racional es también un número real

P(x): “x es racional”; Q(x): “x es real”

Para todo x, (P(x) implica Q(x))

2. 41 es la suma de dos cuadrados perfectos

Existe m y existe n tales que (41=m2+n2)

12
Métodos de prueba

En la proposición “p implica q”, p es la hipótesis o premisa y q la conclusión o

tesis

Existen distintas técnicas de demostración, veremos solo algunas de ellas

Demostración directa

13
Métodos de prueba

14
Métodos de prueba
Demostración indirecta

15
Métodos de prueba

• Todos estos son métodos deductivos (de lo general a lo particular)

• Métodos inductivos: de lo particular a lo general

• Ojo, la inducción, en general, no es un método válido de demostración

• La inducción matemática sí es una forma válida de hacer demostraciones

16
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 2: Inducción y recursión

Índice

► Inducción matemática

► Recursión

2
Inducción

Demostraciones sobre conjuntos inductivos

Ejemplo: 0, 1, 2, 3…

¿Cómo están construidos estos conjuntos?

3
Inducción
Demostración por inducción

1.Caso base: se demuestra que la proposición P(1) es verdadera

2.Se demuestra que si P(k) es verdadera, entonces P(k+1) también lo es

Ejemplo: demostrar por inducción que la suma de los n primeros pares es n2

4
Inducción

5
Inducción

6
Inducción

Ejemplo: demostrar por inducción que n < 2n

7
Inducción

8
Inducción

Ejemplo: demostrar por inducción que n3 – n es divisible por 3

9
Inducción

10
Inducción

Ejemplo: demostrar por inducción que el cardinal de un conjunto

de n elementos es 2n

11
Inducción

12
Inducción

13
Recursión

14
Recursión
Funciones definidas por recursión:

Paso base: se especifica el valor de la función en cero

Paso recursivo: se proporciona una regla para obtener su valor en un

entero a partir de valores en enteros más pequeños

Ejemplo:

15
Recursión

Ejemplo:

16
Recursión

Ejemplos:

•Definir el factorial de un número de forma recursiva

•Definir an de forma recursiva

17
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 3: Conjuntos y funciones

Índice

► Conjuntos

► Funciones

2
Conjuntos

• Un conjunto es una colección desordenada de objetos

• Los objetos de un conjunto se llaman elementos o miembros del

conjunto. Se dice que un conjunto contiene a sus elementos

• En función de la naturaleza del conjunto se puede definir de una forma

u otra

3
Conjuntos

1. Enumeración (cuando el número de elementos es pequeño)

4
Conjuntos

2. Intervalo

Se puede definir un conjunto utilizando su continuidad (Ej: [0,1])

3. Elipsis

Se pueden definir solo unos elementos cuando el patrón es obvio (Ej:

[1, 2, 3, …, 100], [2, 4, 6, …, 20])

5
Conjuntos

6
Conjuntos

• Conjuntos muy importantes en matemáticas

7
Conjuntos

Notación:

Pertenencia

No pertenencia

Conjunto vacío

8
Conjuntos

El conjunto vacío es un subconjunto de S

S es un subconjunto de S

9
Conjuntos

Si un conjunto S tiene exactamente n elementos distintos, se dice que

S es finito y su cardinal es n.

Si un conjunto no es finito, entonces es infinito

Diagramas de Venn

Conjunto universal
Resto de conjuntos

Ejemplo: vocales

10
Conjuntos

Si S es un conjunto, partes de S (P(S)) es el conjunto de todos los

subconjuntos de S

Ejemplo:

Si un conjunto S tiene n elementos, P(S) tiene 2n elementos

11
Conjuntos

• Producto cartesiano

12
Conjuntos
Operaciones con conjuntos (álgebra de conjuntos)

13
Conjuntos

14
Conjuntos

15
Conjuntos

Representación en un ordenador

Conjunto ordenado (puede ser de manera arbitraria).

Representación de un subconjunto como cadena de bits donde 1 si el

elemento está 0 si no está

16
Funciones

17
Funciones

18
Funciones

19
Funciones

20
Funciones

21
Funciones

22
Funciones

Sean A y B dos conjuntos:

Si existe una función inyectiva definida desde A hasta B, entonces el

cardinal de A es menor o igual que el cardinal de B

Si existe una función sobreyectiva definida desde A hasta B, entonces

el cardinal de A es mayor o igual que el cardinal de B

23
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 4: Teoría de números y aritmética modular

Índice

► Divisibilidad y aritmética modular

► Números primos

► Máximo común divisor y mínimo común múltiplo

2
Divisibilidad y aritmética modular

3
Números primos

¿Cuántos números primos hay?

4
Números primos

5
Máximo común divisor y mínimo común múltiplo

6
Máximo común divisor y mínimo común múltiplo

7
Aplicaciones de la aritmética modular

8
Aplicaciones de la aritmética modular

9
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 5: Aplicaciones de la aritmética modular

Índice

► Congruencias lineales

► Teorema chino del resto

► Raíz primitiva

► Algoritmo de Diffie-Hellman

2
Congruencias lineales

Ejemplo: 2x≡3 (mod 7)

3
Congruencias lineales

Ejemplo: 2x≡3 (mod 7)

4
Teorema chino del resto

5
Teorema chino del resto
• Ejemplo:

x≡2 (mod 3). Por tanto, a1=2

x≡3 (mod 5). Por tanto, a2=3
x≡2 (mod 7). Por tanto, a3=2

m=3*5*7=105
M1=m/3=35; 35≡2 (mod 3). Por tanto, d1=2
M2=m/5=21; 21≡1 (mod 5). Por tanto, d2=1
M3=m/7=15; 15≡1 (mod 7). Por tanto, d3=1

x = a1*M1*d1 + a2*M2*d2 + a3*M3*d3 (mod m)

x = 2*35*2 + 3*21*1 + 2*15*1 = 233 = 23 (mod 105)

6
Pequeño teorema de Fermat

7
Raíz primitiva

Ejemplos:

3 (mod 7) es una raíz primitiva

3 (mod 11) no es una raíz primitiva

8
Raíz primitiva

9
Raíz primitiva

Historia de la criptografía:

-Cifrado César

-Cifrado por sustitución

-Código enigma

-Sistemas centrados en la clave

-Sistemas simétricos

-Sistemas asimétricos

10
Algoritmo de Diffie-Hellman

11
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 6: Matrices
Índice

► Concepto de matriz

► Operaciones fundamentales con matrices

► La matriz identidad y la potencia de una matriz

► Matriz inversa, traspuesta y determinantes

► Matrices booleanas

2
Concepto de matriz

Ejemplo:

Aplicaciones:

•Algoritmo de búsqueda de Google

•Imágenes tipo raster
•Pantalla de un ordenador

3
Concepto de matriz

4
Operaciones con matrices

Suma:

Ejemplo:

5
Operaciones con matrices

Producto:

6
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 7: Relaciones
Índice

► Relaciones binarias

► Propiedad reflexiva

► Propiedades simétrica y antisimétrica

► Propiedad transitiva

► Relación de equivalencia

2
Relaciones binarias

Ejemplos:

i)Alumno-asignatura

ii)Equivalencia

iii)Países-capitales

3
Relaciones binarias

4
Relaciones binarias

Ejemplo 5

5
Relaciones binarias

Ejemplo 7

6
Propiedad reflexiva

¿Qué relaciones del ejemplo 5 son reflexivas?

¿Qué relaciones del ejemplo 7 son reflexivas?

7
Propiedad simétrica y antisimétrica

¿Qué relaciones del ejemplo 5 son simétricas y antisimétricas?

¿Qué relaciones del ejemplo 7 son simétricas y antisimétricas?

8
Propiedad transitiva

¿Qué relaciones del ejemplo 5 son transitivas?

¿Qué relaciones del ejemplo 7 son transitivas?

9
Relación de equivalencia

Una relación R es de equivalencia si cumple:

i)Propiedad reflexiva

ii)Propiedad simétrica

iii)Propiedad transitiva

10
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 7: Relaciones
Índice

► Sistemas de ecuaciones

► Eliminación gaussiana ingenua

► Eliminación gaussiana con pivotaje parcial escalado

2
Sistemas de ecuaciones

3
Sistemas de ecuaciones

4
Sistemas de ecuaciones

5
Eliminación gaussiana ingenua

6
Eliminación gaussiana ingenua

7
Eliminación gaussiana ingenua

8
Eliminación gaussiana ingenua

9
Eliminación gaussiana por pivotaje parcial
escalado

10
Eliminación gaussiana por pivotaje parcial
escalado

11
Eliminación gaussiana por pivotaje parcial
escalado

12
Eliminación gaussiana por pivotaje parcial
escalado

13
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 9: Programación lineal

Índice

► Introducción a la programación lineal

► Forma estándar

► Forma distensionada

► Dualidad

2
Introducción a la programación lineal

3
Introducción a la programación lineal

4
Introducción a la programación lineal

En resumen, ¿cuáles son las características de un problema de

programación lineal?

5
Introducción a la programación lineal

6
Forma estándar

7
Forma estándar

8
Forma estándar

9
Forma estándar

10
Forma estándar

11
Forma estándar

12
Forma estándar

13
Forma distensionada

14
Forma distensionada

15
Forma distensionada

Ejemplo:

16
Dualidad

17
Dualidad

18
Dualidad

19
Dualidad

20
¿Qué tengo que saber?

• Qué es un problema de programación lineal y cómo son todos sus

elementos

• Reconocer y caracterizar la región factible

• Las formas estándar y distensionada

• Qué es el problema dual y cómo se construye

21
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 10: Algoritmo del Simplex

Índice

► Introducción

► Método + ejemplo

► Ejemplo

2
Introducción

• Los problemas de programación lineal admiten solución

• Calcular las regiones factibles y evaluar la función objetivo en ellos puede

ser muy costoso

• El algoritmo del simplex ofrece una solución computacionalmente más

eficiente al problema de programación lineal

• Se puede utilizar para cualquier tipo de problema (máximizar o minimizar)

y con cualquier tipo de restricciones

• En esta clase vamos a ver el caso en que busquemos un máximo y las

restricciones sean de la forma mayor o igual que

3
Método + ejemplo

4
Método + ejemplo

5
Método + ejemplo

Ejemplo:

6
Método + ejemplo

7
Método + ejemplo

8
Método + ejemplo

9
Método + ejemplo

Primera solución:

10
Método + ejemplo

11
Método + ejemplo

12
Método + ejemplo

13
Método + ejemplo

14
Método + ejemplo

15
Método + ejemplo

Hacemos combinaciones lineales entre filas para que en la columna

del pivote el resto de los elementos sea cero

16
Método + ejemplo

17
Método + ejemplo

18
Método + ejemplo

19
Método + ejemplo

20
Método + ejemplo

21
Método + ejemplo

22
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 11: Grafos

Índice

► Tipos y terminología

► Grafos bipartitos

► Isomorfismo

► Conectividad

2
Isomorfismo

Queremos saber si dos grafos son equivalentes o no (isomorfismo)

Representación computacional de los grafos

3
Isomorfismo

4
Isomorfismo

5
Isomorfismo

6
Isomorfismo

7
Isomorfismo

8
Isomorfismo

9
Isomorfismo

10
Isomorfismo

Fuente: https://www.emaze.com/

11
Isomorfismo

12
Isomorfismo

Fuente: http://ars-uns.blogspot.com/

13
Isomorfismo

14
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 11: Grafos

Índice

► Tipos y terminología

► Grafos bipartitos

► Isomorfismo

► Conectividad

2
Tipos y terminología

3
Tipos y terminología

4
Tipos y terminología

5
Tipos y terminología

6
Tipos y terminología

7
Tipos y terminología

8
Tipos y terminología

9
Tipos y terminología

10
Tipos y terminología

Fuente: https://elisa.dyndns-web.com/

11
Tipos y terminología

12
Tipos y terminología

¿Son bipartitos?

13
Tipos y terminología

14
Tipos y terminología

Fuente: https://www.geeksforgeeks.org/

15
Tipos y terminología

Fuente: https://math.stackexchange.com/

16
Tipos y terminología

Fuente: http://mathworld.wolfram.com/

17
Tipos y terminología

Fuente: https://www.geeksforgeeks.org/

18
Tipos y terminología

19
Álgebra y Matemática Discreta
Elena Giménez de Ory

Tema 12: Árboles

Índice

► Tipos y terminología

► Propiedades

► Recorrido

2
Tipos y terminología

3
Tipos y terminología

4
Tipos y terminología

5
Tipos y terminología

6
Tipos y terminología

7
Tipos y terminología

8
Aplicaciones

9
Aplicaciones

10
Aplicaciones

11
Recorrido

12
Recorrido

Fuente: https://www.oscarblancarteblog.com/

13
Recorrido

Fuente: https://www.oscarblancarteblog.com/

14
Recorrido

Fuente: https://www.oscarblancarteblog.com/

15