apuntes discreta 13 14 19

`
ESCUELA POLITECNICA
SUPERIOR
UNIVERSIDAD CARLOS III DE MADRID

Transparencias de Matem´
atica Discreta
Grado en Ingenier´ıa en Inform´atica
Doble Grado en Ingenier´ıa en Inform´atica y
Administraci´on de Empresas
Curso 2013–2014
Grupo de Modelizaci´on, Simulaci´on Num´erica y Matem´atica Industrial
Universidad Carlos III de Madrid
Avda. de la Universidad, 30
28911 Legan´es

v1.0: Septiembre2013

Matemática Discreta
Curso 2013–2014
Grado en Ingeniería en Informática
Doble Grado en Ingeniería en Informática y Administración de Empresas
Universidad Carlos III de Madrid

DM– p. 1/148

Relaciones entre temas

Combinatoria

Teoría de Grafos

Conjuntos

Relaciones

Inducción

DM– p. 2/148

Tema 1: Conjuntos y funciones
1. Teoría elemental de conjuntos:
• Definiciones y operaciones.
• Losnúmeros naturales.
2. Funciones:
• Definiciones y operaciones.
• Tipos de funciones.
• Cardinal de un conjunto.

3. Divisibilidad de enteros:
• Teorema de la divisibilidad.
• Máximo común divisor y mínimo común múltiplo.
• Números primos. Teorema fundamental de la aritmética.

DM– p. 3/148

Teoría de conjuntos elemental
Definición 1
Un conjunto A es una colección bien definida de objetos (denominadoselementos del
conjunto):

X = {x1 , x2 , x3 , . . .} .
Dado un conjunto X y un cierto objeto x una y sólo una de las siguientes afirmaciones debe ser
cierta:

• o bien x ∈ X , es decir el objeto x pertenece al conjunto X ,

• o bien no pertenece, x ∈
/ X.

Los conjuntos no poseen una ordenación privilegiada de sus elementos ni admiten
elementos múltiples.
Definición 2
El conjunto vacío ∅ es aquélque no tiene elementos: ∅

= { }.

Definición 3
El conjunto universal S es aquel que contiene todos los elementos de la clase que estemos
considerando.

DM– p. 4/148

¿Cómo definir un conjunto?
• Por extensión: en el caso de que sea posible enumerar todos los elementos de un
conjunto:
X = {1, 2, 3, 4, 5, 6} .

• Por comprensión: en el caso de que su definición se realice atendiendo a lapropiedad común que poseen todos los elementos del conjunto:
Y = {y : y es una provincia de Andalucía} .
• Notación “mixta”:

Z = {1, 2} ∪ {x : x ∈ [4, 5]} .

• Podemos definir un conjunto utilizando otro ya conocido a través de alguna regla
de formación:
C = {n3 : n ∈ N} = {m ∈ N : ∃k ∈ N tal que m = k 3 } .

DM– p. 5/148

Subconjuntos
Definición 4
A es un subconjunto de B (A

⊆ B ) si todo elemento de Aestá en B . Si existen elementos
de B que no están en A, entonces A es un subconjunto propio de B (A ⊂ B ).
• Todo conjunto A satisface A ⊆ A ⊆ S.

• El conjunto vacío ∅ satisface la propiedad ∅ ⊆ A para cualquier conjunto A.

Definición 5
El conjunto de las partes del conjunto
conjunto de todos los subconjuntos de A:

A (que se denota con el símbolo P(A)) es el

P(A) = {B : B ⊆ A} .

DM– p.6/148

Operaciones con conjuntos
Dados dos conjuntos A y B podemos definir las siguientes operaciones:
• Unión: A ∪ B = {x | (x ∈ B) ∨ (x ∈ A)}.

• Intersección: A ∩ B = {x | (x ∈ B) ∧ (x ∈ A)}.
• Conjunto complementario: A = {x | x ∈ A} y además satisface que (A) = A.

• Diferencia: A \ B = {x | (x ∈ A) ∧ (x ∈ B)}.

• Diferencia simétrica: A△B = {x | (x ∈ A ∪ B) ∧ (x ∈ A ∩ B)}.
Algunas propiedades:• Leyes distributivas
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
• Leyes de Morgan

• A ∪ B = A ∩ B.
• A ∩ B = A ∪ B.

• A△B = (A \ B) ∪ (B \ A).
DM– p. 7/148

Producto cartesiano
Definición 6
Dados dos conjuntos X e
de los pares ordenados:

Y , el producto cartesiano X × Y se define como el conjuntos

X × Y = {(x, y) : (x ∈ X) ∧ (y ∈ Y )} .
Observación: No es lo mismousar { } ó ( ). En concreto {1, 2} denota un conjunto y
por tanto {1, 2} = {2, 1}. Sin embargo (1, 2) es un par ordenado y por tanto
(1, 2) = (2, 1).
Definición 7
Dos conjuntos A y B son disjuntos si A ∩ B

= ∅.

DM– p. 8/148

Los números naturales
Definición 8
El conjunto de los números naturales N se define mediante las condiciones siguientes:
(1)

1 ∈ N.

(2) Si n ∈ N, entonces el número n +...