UNIVERSIDAD CENTROCIDENTAL ’LISANDRO ALVARADO’

DECANATO DE CIENCIAS Y TECNOLOGÍA

DEPARTAMENTO DE MATEMÁTICAS

INTRODUCCIÓN A LAS ESTRUCTURAS DISCRETAS

Por: Ronald Gutiérrez

Barquisimeto 2009
Índice general

0.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2. Orientaciones Generales para los Usuarios . . . . . . . . . . . 4
0.2.1. Para los Alumnos . . . . . . . . . . . . . . . . . . . . . 4
0.2.2. Para los Docentes (Sugerencias para la Evaluación de
los Aprendizajes) . . . . . . . . . . . . . . . . . . . . . 5
0.3. Objetivos de Aprendizajes . . . . . . . . . . . . . . . . . . . . 6
0.3.1. Generales . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.3.2. Especı́ficos . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.4. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 8
0.4.1. Básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.4.2. Complementarias . . . . . . . . . . . . . . . . . . . . . 9

1. CÁLCULO PROPOSICIONAL 10
1.1. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Operaciones Veritativas . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Formas Proposicionales . . . . . . . . . . . . . . . . . . . . . . 18
1.4. Tautologı́as, Implicaciones y Equivalencias . . . . . . . . . . . 21
1.5. Circuitos Lógicos . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6. Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.7. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 30
1.8. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 32
1.9. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 36

2. CONJUNTOS 37
2.1. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2. Operaciones con Conjuntos . . . . . . . . . . . . . . . . . . . . 41
2.3. Producto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . 49
2.4. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 53

2
 2.6. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 56

3. RELACIONES 58
3.1. Relaciones Binarias . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2. Relaciones en un Conjunto . . . . . . . . . . . . . . . . . . . . 65
3.3. Relaciones de Equivalencia y de Orden . . . . . . . . . . . . . 68
3.4. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 73
3.6. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 76

4. FUNCIONES 78
4.1. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 88
4.4. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 91

5. ÁLGEBRAS DE BOOLE 92
5.1. Álgebras de Boole . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2. Polinomios Booleanos y Circuitos Lógicos . . . . . . . . . . . . 96
5.3. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 102
5.4. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 103
5.5. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 104

6. GRAFOS 105
6.1. Grafos no Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2. Dı́grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3. Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . 117
6.4. Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . 119
6.5. Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . 125

3
0.1. Introducción
La presente unidad curricular Estructuras Discretas está concebida para
la carrera de Análisis de Sistemas para introducir al estudiante del primer
semestre en el conocimiento y dominio de la lógica básica, lo que le per-
mitirá desarrollar distintos lenguajes de programación, en virtud de que un
programa representa una serie de secuencias lógicas.

Con este programa se propone el desarrollo del análisis, sı́ntesis y pen-

samiento abstracto que le permitan al estudiante manejar el más óptimo niv-
el en la comprensión de problemas complejos para darle solución, ası́ como
pretende estudiar las proposiciones, conjuntos, relaciones, funciones, álge-
bras booleanas y grafos y dı́grafos. La adquisición y apropiación de estos
conocimientos se inserta en las metas del diseño curricular de la carrera de
Análisis de Sistema de la UCLA, puesto que proporcionará al estudiante la
capacidad de resolver problemas de la lógica matemática, lo que favorece el
desarrollo integral del perfil profesional de un analista de sistemas.

0.2. Orientaciones Generales para los Usuar-

ios
0.2.1. Para los Alumnos
Esta monografı́a fue elaborada pensando en los estudiantes de Estruc-
turas Discretas (M1) del programa de Análisis De Sistemas del decanato de
Ciencias y Tecnologı́a de la UCLA, y su contenido está presentado acorde
con los objetivos (generales y especı́ficos) del programa de dicha asignatura.
Pero aún ası́ puede ser un buen texto de consulta para los estudiantes de
las diversas carreras del decanato, y entre los estudiante que más se podrı́an
beneficiar estarı́an los del programa de Ingenierı́a En Informática (por el
parecido del contenido del programa de la asignatura en ambas carreras).

Cada capı́tulo es presentado de forma sencilla, en la mayorı́a de los casos

tras cada definición y teorema presentamos diversos ejemplos que muestran
distintas situaciones que se pueden presentar. Cada capı́tulo trae consigo
además de su respectivo contenido, una sección de ejercicios prácticos resuel-
tos, ejercicios propuestos y recomendaciones bibliográficas del contenido del

4
capı́tulo.

Para un éxito durante el curso el estudiante debe tener un dominio general

de temas relacionados con la matemática básica como lo son: propiedades y
operaciones elementales de los números reales, valor absoluto, factorización,
racionalización. Una ayuda para estos temas de matemática básica la encon-
trarás en el texto Matemáticas Pre-Universitarias por Mireya Braca-
montes, Jurancy Ereú y Miguel Vivas.
En otro orden de ideas te mencionamos que debes tener presente que
cada tema y capı́tulo estará muy relacionado en general con el anterior o
anteriores, por lo tanto debe cumplir con los objetivos especı́ficos de cada
capı́tulo para un buen desempeño en los siguientes (capı́tulos).
Por último no intentes resolver ejercicios sin antes tener un buen dominio
teórico, este es un error muy común, y en matemática la forma de resolver
los problemas puede variar mucho entre ejercicios, por ello un buen dominio
teórico es la clave para atacar los problemas. Tambien recuerda que lo im-
portante NO es que resuelvas todos los ejercicios, sino que APRENDAS a
resolver cualquier problema.
Si tienes presente estas sugerencias de seguro no sólo aprovecharás al
máximo este curso sino que tus posibilidades de éxitos crecerán.

0.2.2. Para los Docentes (Sugerencias para la Evalu-

ación de los Aprendizajes)
En los diversos ejemplos presentados, se dan las explicaciones básicas que
se esperan del estudiante durante las evaluaciones, en ocasiones se pide al
estudiante completar algunas de estas.

Por otro lado como se mencionó, al final de cada capı́tulo existen sec-
ciones de ejercicios resueltos y propuestos; los ejercicios resueltos siguen el
modelo de los ejemplos que siguen a las definiciones y/o teoremas, y en los
ejercicios propuestos el estudiante y profesor encontrará ejercicios acordes a
los objetivos (generales y especı́ficos) a evaluar.

A continuación se presenta el plan de evaluación sugerido para el curso.

5
 Evaluación Tema Ponderación Parcial
Prueba escrita individual 1 30 puntos I
Prueba escrita individual 2 20 puntos II
Prueba escrita individual 3 15 puntos II
Trabajo grupal (máx. 3 estudiantes) 6 5 puntos III
Prueba escrita individual 4, 6 30 puntos III

0.3. Objetivos de Aprendizajes

0.3.1. Generales
1. Reconocer e identificar algunas Estructuras Discretas, sus propiedades
y aplicación en la resolución de problemas.

2. Explicar los conceptos básicos de proposiciones, conjuntos, relaciones,

funciones, grafos, Álgebra de Boole, cálculo mediante la utilización de
diversos lenguajes.

3. Reconocer el carácter instrumental, formativo y lógico de la Matemática.

4. Desarrollar en los alumnos el pensamiento reflexivo, la capacidad la

abstracción y la relación entre las estructuras discretas y los problemas
de vida diaria.

5. Eliminar las ambigüedades y dificultades del lenguaje ordinario cuando

se analiza el rigor matemático de una demostración.

0.3.2. Especı́ficos
A continuación se describen los objetivos especificos que se esperan que
alcance el estudiante en cada capı́tulo:
Capı́tulo 1:

1. Identificar las diferencias entre una proposición y una oración.

2. Definir e identificar las operaciones lógicas.

3. Distinguir las tablas que definen los operadores lógicos.

4. Traducir proposiciones del lenguaje simbólico al español.

6
 5. Verificar Tautologı́as, Contradicciones y Contigencias.

Capı́tulo 2:

1. Identificar las diferencias entre elementos y conjunto.

2. Definir e identificar conjunto por extensión y por comprensión.

3. Diferenciar las relaciones de pertenencia, igualdad e inclusión.

4. Definir las operaciones entre conjuntos.

5. Definir el producto cartesiano de dos conjuntos.

6. Definir el conjunto potencia.

Capı́tulo 3:

1. Definir e identificar relaciones binarias entre conjuntos.

2. Determinar la inversa de una relación.

3. Representar gráficamente relaciones binarias.

4. Representar mediante matrices las relaciones binarias.

5. Definir Dominio y Rango.

6. Identificar Dominio y Rango de una relación.

7. Definir e identificar relaciones reflexivas, simétricas, transitivas en un

conjunto.

8. Identificar relaciones de Equivalencia y de Orden en un Conjunto.

Capı́tulo 4:

1. Definir función.

2. Establecer la diferencia entre función y relación.

3. Determinar dominio y rango de una función.

4. Distinguir funciones inyectiva, sobreyectiva y biyectiva.

7
 5. Definir la inversa de una función.

Capı́tulo 5:

1. Identificar un Álgebra de Boole.

2. Enunciar algunas propiedades de un Álgebra de Boole.

3. Identificar funciones Booleanas y criterios Lógicos.

Capı́tulo 6:

1. Definir Grafos.

2. Determinar la relación existente entre grafos y las relaciones binarias.

3. Diferenciar grados simples y elementales.

4. Determinar si un grafo es conexo o disconexo.

5. Identificar grafos digiridos.

6. Definir subgrafos.

7. Identificar árboles.

8. Establecer la relación entre grafos y árboles.

0.4. Referencias Bibliográficas

0.4.1. Básicas
1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Ramos, Dennis. Estructuras Discretas.

3. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

8
0.4.2. Complementarias
1. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta
edición, 1997.

2. Sáenz, Jorge; y otros. Fundamentos de la Matemática. Hipotenusa. Se-

gunda edición, Barquisimeto, 2001.

9
Capı́tulo 1

CÁLCULO PROPOSICIONAL

En este capı́tulo estudiaremos las proposiciones, los diferentes elementos

que intervienen ella (conectivos, cuantificadores) y los efectos de estos en
las proposiciones. Uno de los temas principales que abordaremos será el de
formas proposicionales.

1.1. Proposiciones
Definición 1.1.1 Una proposición es un juicio declarativo del que tiene
sentido decir que es verdadero o falso pero no ambas simultáneamente.

Ejemplo 1.1.1 Consideremos las siguientes expresiones:

1. Barquisimeto es la capital del estado Lara.

2. 3 − 2 = 4

3. ¿ Hay clase hoy?

4. ¡ Vete !

5. Todos los números son positivos.

6. Esta proposición es falsa.

7. 4 · 8 = 32

10
Son proposiciones 1,2,5 y 7 (verdadera, falsa, falsa, verdadera respectiva-
mente). 3 y 4 no son siquiera juicios declarativos. 6 es un juicio declarativo
pero es contradictorio.

Definición 1.1.2 Si p es una proposición verdadera decimos que su valor

lógico, denotado por V L(p), es uno (V L(p) = 1), si p es falsa entonces
diremos que su valor lógico es cero (V L(p) = 0).

Ejemplo 1.1.2 La expresión:

’EL trillonesimo dı́gito de la expresión decimal de es 5’

es una proposición. Aunque cuando no se sepa de antemano si es verdad o

no, es claro que solo es una de ella.

Aunque sea muy dificil o casi imposible saber si un juicio declarativo es o no

verdad, para que sea proposición lo importante es que se tenga la certeza de
que será sólo una de ellas.
Otra proposición de este tipo es:

’en Marte existen piedras de 2.42 kilogramos de peso’

Prestemos atención ahora a las expresiones:

a) x + 1 > 0.

b) Para todo número real x se cumple que x + 1 > 0.

La primera expresión NO es proposición, pero la segunda SÍ lo es (falsa).

Esto se debe a que en la primera no hay especificación sobre x, depende de
que número real x se coloque para conocer si la expresión es verdadera o falsa
(por ejemplo 2 + 1 > 0 es verdadero, −4 + 1 > 0 es falso).
En cambio en la segunda, la expresión para todo número real x, es la
que hace que tenga sentido decir que el juicio declarativo sea falso debido a
que existen nuḿeros para los cuales es verdad que el más uno es mayor que
cero(2 por ejemplo), pero para otros no es ası́ (por ejemplo -4).

Definición 1.1.3 Una función proposicional (o proposición abierta)

(A, P (x)), consta de un conjunto A y un juicio declarativo P (x) tal que:

1. Tiene variable (a saber x).

11
 2. No es proposición.

3. Se convierte en proposición cuando la variable es reemplazada por un

elemento del conjunto A.

Al conjunto de todos los elementos de A que hacen verdadera P (x) se le llama

dominio de verdad de la función proposicional.
Es costumbre decir la función proposicional P (x) en lugar de la función
proposicional (A, P (x)).

Ejemplo 1.1.3 Sea (A, P (x)) la función proposicional donde:

A = {−2, 0, 4, 5, 7}, P (x) : x + 3 < 4

El dominio de verdad de P (x) viene dado por {−2, 0} ya que:

1. P (−2) : −2 + 3 < 4 (verdadero).

2. P (0) : 0 + 3 < 4 (verdadero).

3. P (4) : 4 + 3 < 4 (falso).

4. P (5) : 5 + 3 < 4 (falso).

5. P (7) : 7 + 3 < 4 (falso).

Una función proposicional puede tener varias variables, si por ejemplo tiene
dos variables digamos: x, y entonces deben existir dos conjuntos, uno donde
varia x y otro donde varia y. Por ejemplo:

(A, B, Q(x, y)) donde A = {1, 2, 3}, B = {0, 1} y

Q(x, y) : x + y < 2

Ası́ Q(1, 0) : 1 + 0 < 3 (verdadero) y Q(2, 1) : 2 + 1 < 3 (falso)

El dominio de verdad se escribe entre llaves, pero se escriben entre parénte-

sis los elementos, ası́ el dominio de verdad de la función anterior viene dado
por:
{(1, 0), (1, 1), (2, 0)}

12
Siempre conservando el orden, es decir los elementos de A en primer lugar
y en segundo lugar los de B, esto es importante pues cambiar el orden nos
puede producir errores, veamos un ejemplo.
Sea (A, B, P (x, y)) con A = {0, 1, 2, 3}, B = {1, 2, 4, 5, 6}, P (x, y) : x − y > 0

Notemos que P (2, 1) : 2 − 1 = 1 es verdadero, pero P (1, 2) : 1 − 2 = −1 es

falso. Por lo tanto es importante tener cuidado con el orden. Más aún P (2, 4)
es falso pero P (4, 2) no tiene sentido ya que 4 no está en A. Le pedimos al
lector que encuentre el dominio de verdad de (A, B, P (x, y)).

Se pueden tener funciones proposicionales de cualquier número finito de

variables y el dominio de verdad se escribe siguiendo el esquema descrito para
dos variables.

1.2. Operaciones Veritativas

Consideremos las siguientes proposiciones:

2 no es número par.

2 es número par y es primo.

2 es número par o es primo.

o 2 es número par o es primo.

Si dos es número par, entonces 2 es primo.

2 es número par si y sólo si es primo.

A los términos no, y, o, o...o, si...entonces, ...si y sólo si..., se les llama conec-
tivos lógicos elementales.
Por otro lado, diremos que una proposición es simple si no posee conec-
tivos lógicos. Por ejemplo:
p: 2 es número par.
q: 2 es número primo.
Una proposición compuesta es una proposición que posee conectivos
lógicos; como por ejemplo las seis proposiciones iniciales.

13
Definición 1.2.1 Una operación veritativa es una operación con proposi-
ciones tal que el valor lógico de la proposición resultante depende de los val-
ores lógicos de las proposiciones componentes.
Definición 1.2.2 Sea p una proposición. La negación de p es la proposi-
ción denotada por ∼ p que se lee: ’no p’, ’no es cierto que p’, ’es falso que
p’ y cuyo valor lógico viene dado por la siguiente tabla de verdad:
p ∼p
1 0
0 1
La proposición ’ 2 no es número par’ es falsa, porque la proposición ’2 es
número par’ es verdadera.
Definición 1.2.3 Sean p y q dos proposiciones. La conjunción de p y q
es la proposición denotada por p ∧ q que se lee: ’ p y q’, y cuyo valor lógico
viene dado por la siguiente tabla de verdad:
p q p∧q
1 1 1
1 0 0
0 1 0
0 0 0
El valor lógico de la proposición ’2 es número par y es primo’ es 1 ya que las
proposiciones ’2 es número par’ y ’2 es número primo ’ son verdaderas.
Definición 1.2.4 Sean p y q dos proposiciones. La disyunción de p y q es
la proposición denotada por p ∨ q que se lee: ’ p o q’, y cuyo valor lógico viene
dado por la siguiente tabla de verdad:
p q p∨q
1 1 1
1 0 1
0 1 1
0 0 0
El valor lógico de la proposición ’2 es número par o es primo’ es 1, ya que
la proposición ’2 es número par’ es verdadera.
’2 es número primo ’ tambien es verdadera pero es suficiente que sólo una
de las proposiciones involucradas sea verdadera para que lo sea la disyunción.

14
Definición 1.2.5 Sean p y q dos proposiciones. La disyunción exclusiva
de p y q es la proposición denotada por p Y q que se lee: ’ o p o q’, y cuyo
valor lógico viene dado por la siguiente tabla de verdad:
p q pYq
1 1 0
1 0 1
0 1 1
0 0 0
El valor lógico de la proposición ’o 2 es número par o es primo’ es 0, ya que
las proposiciones ’2 es número par’ y ’2 es número primo ’ son verdaderas.
Definición 1.2.6 Sean p y q dos proposiciones. El condicional con an-
tecedente p y consecuente q es la proposición denotada por p → q que se
lee:
1. Si p, entonces q.
2. q es condición necesaria para p.
3. Una condición necesaria para p es q.
4. p es condición suficiente para q.
5. Una condición suficiente para q es p.
6. q si p.
7. p sólo si q.
8. p solamente si q.
y cuyo valor lógico viene dado por la siguiente tabla de verdad:
p q p→q
1 1 1
1 0 0
0 1 1
0 0 1
El valor lógico de la proposición ’ si 2 es número par entonces es primo’ es
1 ya que las proposiciones ’2 es número par’ y ’2 es número primo ’ son
verdaderas.

15
Al condicional p → q (el cual llamaremos directo) se le asocian los siguientes
condicionales:

1. Recı́proco: q → p

2. Contrario: (∼ p) → (∼ q)

3. Contrarrecı́proco: (∼ q) → (∼ p)

Ejemplo 1.2.1 Consideremos la proposición: ’ si 2 es número par entonces

2 es número primo’
Sean:
p : 2 es número par.
q : 2 es número primo.
Entonces:

1. El recı́proco de la proposición p → q viene dado por q → p:’si 2 es

número primo, entonces 2 es número par’.

2. El contrario de la proposición p → q viene dado por ∼ p →∼ q:’si 2 es

no es número par, entonces 2 no es número primo’.

3. El contrarecı́proco de la proposición p → q viene dado por ∼ q →∼ p:’si

2 no es número primo, entonces 2 no es número par’.

Definición 1.2.7 Sean p y q dos proposiciones. El bicondicional de p y

q es la proposición denotada por p ↔ q que se lee: ’ p si y sólo si q’, ’p es
condición necesaria y suficiente para q’ y cuyo valor lógico viene dado por la
siguiente tabla de verdad:
p q p↔q
1 1 1
1 0 0
0 1 0
0 0 1
El valor lógico de la proposición ’2 es número par si y sólo si es primo’ es
1, ya que las proposiciones ’2 es número par’ y ’2 es número primo ’ son
verdaderas.

16
Debemos tener mucho cuidado al pasar una proposición del lenguaje simbóli-
co al lenguaje cotidiano (viceversa), pues una coma puede ser suficiente para
darle un significado distinto a una proposición, veamos un ejemplo.
Consideremos las proposiciones p, q, r dadas por:

p: Juan tiene hambre.

q: Juan está enfermo.

r: Juan llora mucho.

Consideremos las proposiciones:

(p ∨ q) ∧ r

p ∨ (q ∧ r)
Se puede caer el error de escribir ambas expresiones como:

Juan tiene hambre o está enfermo y llora mucho.

Lo cual no puede ser ya que las proposiciones son distintas, ası́ que ’NO
DEBERÍAN’ escribirse iguales, pero efectivamente no se escriben iguales.
Veamos como se escriben en lenguaje cotidiano respectivamente:
Juan tiene hambre o está enfermo, y llora mucho.
Juan tiene hambre, o está enfermo y llora mucho.
Veamos un problema que puede surgir en el caso del condicional Sean p,q,r
como antes y consideremos las proposiciones:

(p → q) ∧ r

p → (q ∧ r)
Se puede cometer el error acá nuevamente de escribir las proposiciones como:

Si Juan tiene hambre entonces está enfermo y llora mucho.

Se escriben repectivamente como:

Si Juan tiene hambre entonces está enfermo, y llora mucho.
Si Juan tiene hambre, entonces está enfermo y llora mucho.

17
1.3. Formas Proposicionales
Definición 1.3.1 A las expresiones que se obtienen a partir de las variables
proposicionales, mediante aplicaciones de conectivos lógicos se llaman for-
mas proposicionales.
Ejemplo 1.3.1 Son formas proposicionales:
1. (p ∨ q) → r
2. (∼ p) ∧ t
3. (p ↔ q) Y (q →∼ r)
No son formas proposicionales:
1. (p, q) → r
2. p →↔ r
3. ∼ pq
Observación 1.3.1 1. Las variables proposicionales son formas proposi-
cionales (llamadas formas proposicionales atómicas).
2. Si P Y Q son formas proposicionales, entonces también lo son:
a) ∼P
b) P ∨Q
c) P ∧Q
d) P YQ
e) P →Q
f) P ↔Q
Para comodidad en la escritura, se adoptarán las siguientes convenciones, que
nos permitirán eliminar algunos signos de agrupación en una forma proposi-
cional sin que esta pierda su sentido original. Para esto se asignan a las
conectivas los siguientes rangos:
Conectiva Rango
↔ 4
→ 3
∨, ∧, Y 2
∼ 1

18
Definición 1.3.2 El rango de una forma proposicional atómica lo
definimos como 0; el rango de una forma proposicional no atómica
será igual al rango de su conectiva principal.

Ejemplo 1.3.2 Los rangos de las formas proposicionales:

1. (p ∨ q) → r

2. (∼ p) ∧ t

3. (p ↔ q) Y (q →∼ r)

4. p

son respectivamente 3, 2, 2, 0.

Observación 1.3.2 1. Se escribirá de ahora en adelante ∼∼ P en lugar

de ∼ (∼ P ).

2. Sean P y Q dos formas proposicionales, y sea α un conectivo lógico dis-

tinto a la negación. Entonces la forma proposicional (P )αQ (P (αQ)),
se puede escribir como P αQ si el rango de α es mayor que el rango de
P (Q).

Ejemplo 1.3.3 Las formas proposicionales:

1. (p ∨ q) → r

2. (∼ p) ∧ t

3. (p ∧ q) → (q →∼ r)

4. ∼ (∼ (p ↔ q))

se pueden escribir respectivamente como:

1. p ∨ q → r

2. ∼ p ∧ t

3. p ∧ q → (q →∼ r)

4. ∼∼ (p ↔ q)

19
El valor lógico de una forma proposicional dependerá de los valores lógicos
de sus variables proposicionales, para el cálculo (ordenado) de este valor
utilizaremos las tablas de verdad.
Existen dos métodos para construir tablas de verdad:

1. Método acumulativo: Dada una forma proposicional, se asigna una

columna para cada variable proposicional y una columna para cada
operación, conservando el orden en que se llevaron a cabo tales opera-
ciones.

Ejemplo 1.3.4 La tabla de verdad (por el método acumulativo) de

p ∨ q →∼ q viene dada por:

p q ∼q p∨q p ∨ q →∼ q
1 1 0 1 0
1 0 1 1 1
0 1 0 1 0
0 0 1 0 1

2. Método abreviado: Se escribe la forma proposicional y se le asignan

los valores lógicos a las variables proposicionales o a las negaciones de
éstas. Luego se asignan los valores a las conectivas según el orden en
que éstas se usaron para construir la forma proposicional.

Ejemplo 1.3.5 La tabla de verdad (por el método abreviado) de

p ∨ q →∼ q viene dada por:

p ∨ q → ∼q
1 1 1 0 0
1 1 0 1 1
0 1 1 0 0
0 0 0 1 1

Usualmente se trabaja por el método abreviado pues es más corto y sencillo.

En la construcciones de tablas de verdad se suelen seguir los siguientes
ordenes en los valores de las variables proposicionales para una, dos, tres

20
variables respectivamente:
p q r
1 1 1
p q 1 1 0
p 1 1 1 0 1
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0
0 0 1
0 0 0

1.4. Tautologı́as, Implicaciones y Equivalen-

cias
Definición 1.4.1 Una forma proposicional es:
1. Una tautologı́a si es verdadera para cualquier valor lógico que se le
asignen a sus variables proposicionales.

2. Una contradicción si es falsa para cualquier valor lógico que se le

asignen a sus variables proposicionales.

Ejemplo 1.4.1 La forma proposicional p ∨ q ↔ q ∨ p es una tautologı́a ya

que
p ∨ q ↔ q ∨ p
1 1 1 1 1 1 1
1 1 0 1 0 1 1
0 1 1 1 1 1 0
0 0 0 1 0 0 0

Ejemplo 1.4.2 La forma proposicional p∧ ∼ p es una contradicción ya que

p ∧ ∼p
1 0 0
0 0 1

Observación 1.4.1 1. Existen formas proposicionales que no son tau-

tologı́as y que no son contradicciones, por ejemplo la forma proposi-
cional del ejemplo 1.3.5.

21
 2. La negación de una tautologı́a es una contradicción, y la negación de
una contradicción es una tautologı́a.
Definición 1.4.2 Sean P y Q dos formas proposicionales.
1. Diremos que P implica lógicamente (implica a) a Q, denotado por
P ⇒ Q, si la forma proposicional P → Q es una tautologı́a. En otras
palabras P implica lógicamente a Q si cada asignación de valores que
hacen verdadera P , también hacen verdadera Q.
2. Diremos que P lógicamente equivalente (equivalente a) a Q, deno-
tado por P ⇔ Q o P ≡ Q, si la forma proposicional P ↔ Q es una
tautologı́a. En otras palabras P equivalente a Q si y sólo si tienen los
mismos valores lógicos.
Ejemplo 1.4.3 p ∧ q ⇒ p ya que
p ∧ q → q
1 1 1 1 1
1 0 0 1 0
0 0 1 1 1
0 0 0 1 0
Ejemplo 1.4.4 p ∨ q ⇔ q ∨ p ya que
p ∨ q ↔ q ∨ p
1 1 1 1 1 1 1
1 1 0 1 0 1 1
0 1 1 1 1 1 0
0 0 0 1 0 0 0
Observación 1.4.2 1. Para toda forma proposicional P se cumple que
P ≡ P (reflexividad).
2. Si P ≡ Q, entonces Q ≡ P (simetrı́a).
3. Si P ≡ Q y Q ≡ R, entonces P ≡ R (transitividad).
Debido a la segunda propiedad podemos decir que P y Q son equivalentes, en
lugar de decir que P es equivalente Q o que Q es equivalente a P .
A continuación veremos una lista de unas equivalencias lógicas fundamen-
tales, a las que llamaremos leyes del álgebra de proposiciones.

22
 LEYES DEL ÁLGEBRA DE PROPOSICIONES
Leyes Idempotentes
p∨p≡p p∧p≡p
Leyes Conmutativas
p∨q ≡q∨p p∧q ≡q∧p
Leyes Asociativas
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Leyes Distributivas
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Leyes de Identidad
p∨V ≡V p∨F ≡p
p∧F ≡F p∧V ≡p
Leyes de Complementación
p∧ ∼ p ≡ F p∨ ∼ p ≡ V
∼ (∼ p) ≡ p ∼ F ≡ V, ∼ V ≡ F
Leyes de De Morgan
∼ (p ∨ q) ≡∼ p∧ ∼ q ∼ (p ∧ q) ≡∼ p∨ ∼ q
Leyes de Absorción
p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p

OTRAS EQUIVALENCIAS NOTABLES

p → q ≡∼ p ∨ q Ley del condicional
p ↔ q ≡ (p → q) ∧ (q → p) Ley del bicondicional
p Y q ≡ (p∧ ∼ q) ∨ (q∧ ∼ p) Ley de la disyunción exclusiva
p → q ≡∼ q →∼ p Ley del contrarrecı́proco
p ∧ q ≡∼ (∼ p∨ ∼ q)
[(p ∨ q) → r] ≡ (p → r) ∧ (q → r) Ley de demostración por casos
(p → q) ≡ (p∧ ∼ q → F ) Ley de reducción al absurdo

La prueba de cada una de ellas se realiza verificando que al intercambiar

≡ por el bicondicional se obtiene una tautologı́a. Por ejemplo p ∨ q ≡ q ∨ p
ya que
p ∨ q ↔ q ∨ p
1 1 1 1 1 1 1
1 1 0 1 0 1 1
0 1 1 1 1 1 0
0 0 0 1 0 0 0

23
 Existe otra forma de demostrar equivalencias utilizando las propiedades
de las tablas antes dadas, la idea es llegar de una forma proposicional a
otra mediante equivalencias ya probadas, tal tipo de demostración se llama
prueba deductiva. Veamos un ejemplo.

Ejemplo 1.4.5 Probar deductivamente que (p → q ∨ r) ⇔ (∼ r → (p → q)).

Demostración:

(p → q ∨ r) ≡ (∼ p) ∨ (q ∨ r) (leycond.)
≡ (∼ p) ∨ (r ∨ q) (conmut.)
≡ (∼ p ∨ r) ∨ q (asoc.)
≡ (r∨ ∼ p) ∨ q (conmut.)
≡ r ∨ (∼ p ∨ q) (asoc.)
≡ ∼∼ r ∨ (p → q) ([Link], ycondicional.)
≡ ∼ r → (p → q) (leycond.)

1.5. Circuitos Lógicos

El interruptor (switch) de un circuito electrico asume los estados de
conducción (excluyentes) de abierto o cerrado. Esta cerrado si deja pasar la
corriente, y está abierto si no permite el paso de la misma.

24
Asociaremos un interruptor cerrado, con una proposición verdadera y en este
caso diremos que el valor de conducción del interruptor es 1 , por otro lado
asociaremos uno abierto con una proposición falsa y diremos que el valor
de conducción es 0 en tal caso. Los interruptores se dibujarán como sigue,
representados con letras minúsculas como en el caso de las proposiciones.

La conjunción de proposiciones corresponde, en la teorı́a de los circuitos, a

la llamada conexión en serie, esto es, la proposición p ∧ q esta relacionada
al circuito lógico:

25
La disyunción de proposiciones corresponde, en la teorı́a de los circuitos, a la
llamada conexión en paralelo, esto es, la proposición p ∨ q está relacionada
al circuito lógico:

Ejemplo 1.5.1 Los circuitos lógicos que corresponden a las expresiones

1. p∧ ∼ q

2. p ∨ (∼ r ∧ q)

vienen dados respectivamente por:

26
Ejemplo 1.5.2 La forma proposicional que corresponde al circuito

viene dada por: [(p∧ ∼ q)∨ ∼ p] ∨ (p ∧ q)

El circuito lógico dado por la forma proposicional

(p ∨ q) ∧ (∼ p ∧ q) ∧ (∼ p∧ ∼ q)

viene dado por:

Simplifiquemos la forma proposicional (dejamos al lector la justificación de

los pasos).

(p ∨ q) ∧ (∼ p ∨ q) ∧ (∼ p∨ ∼ q) = [(p ∨ q) ∧ (∼ p ∨ q)] ∧ (∼ p∨ ∼ q)
= [(p∧ ∼ p) ∨ q] ∧ (∼ p∨ ∼ q)
= [F ∨ q] ∧ (∼ p∨ ∼ q)
= q ∧ (∼ q∨ ∼ p)
= (q∧ ∼ q) ∨ (q∧ ∼ p)
= F ∨ (∼ q∧ ∼ p)
= ∼ q∧ ∼ p

El circuito correspondiente a la última expresión es:

27
este circuito es ’equivalente’ al inicial.

1.6. Cuantificadores
Sea (A, P (x)) un función proposicional. Para cada elemento a del con-
junto A obtenemos una proposición P (a), la cual o es verdadera o es falsa.
¿ Cuántos elementos de A, hacen P (x) verdadera? todos, algunos, uno sólo,
ninguno; todos estos términos se llaman cuantificadores, estudiaremos los
tres primeros (el cuarto se obtiene del primero).
1. El cuantificador para todos se llama cuantificador universal, y se
lo denota por ∀.

Ejemplo 1.6.1 Consideremos la proposición ’todos los números reales

son naturales’. Para escribir en lenguaje simbólico, debemos identificar
el conjunto A y P (x).
A viene dado por el conjunto de todos los números reales, R.
P (x) : x es número natural.
En lenguaje simbólico la proposición se escribe como:
(∀x ∈ R)(P (x))

Cuando el conjunto A está sobreentendido se puede escribir

(∀x)(P (x))
en lugar de
(∀x ∈ A)(P (x))
Una proposición del tipo (∀x ∈ A)(P (x)) (llamada proposición uni-
versal) es verdadera si y sólo si P (a) es verdadera para todo a elemento
de A.
Ası́ que la proposición del ejemplo anterior es falsa porque existen
números reales que no son naturales.

28
2. El cuantificador algunos o existe al menos uno se llama cuantifi-
cador existencial, y se lo denota por ∃.

Ejemplo 1.6.2 Consideremos la proposición ’existen números enteros

que son pares’. Para escribir en lenguaje simbólico, debemos identificar
el conjunto A y P (x).
A viene dado por el conjunto de todos los números enteros, Z.
P (x) : x es número par.
En lenguaje simbólico la proposición se escribe como
(∃x ∈ Z)(P (x))

Cuando el conjunto A está sobreentendido se puede escribir

(∃x)(P (x))
en lugar de
(∃x ∈ A)(P (x))
Una proposición del tipo (∃x ∈ A)(P (x)) (llamada proposición ex-
istencial) es verdadera si y sólo si P (a) es verdadera para algún a
elemento de A.
Por la tanto la proposición del ejemplo anterior es verdadera porque
existen números enteros que son pares.
3. El cuantificador existe un único o existe al sólo uno se llama cuan-
tificador existencial de unicidad, y se lo denota por ∃!.

Ejemplo 1.6.3 Consideremos la proposición ’existe sólo un número

racional menor que 0’. Para escribir en lenguaje simbólico, debemos
identificar el conjunto A y P (x).
A viene dado por el conjunto de todos los números racionales, Q.
P (x) : x < 0
En lenguaje simbólico la proposición se escribe como
(∃!x ∈ Q)(P (x))
Otra manera de escribirla serı́a
(∃!x ∈ Q)(x < 0)

29
 Cuando el conjunto A está sobreentendido se puede escribir

(∃!x)(P (x))

en lugar de
(∃!x ∈ A)(P (x))

Una proposición del tipo (∃!x ∈ A)(P (x)) es verdadera si y sólo si P (a)
es verdadera para sólo un valor a de A.
Por la tanto la proposición del ejemplo anterior es falsa porque existen
más de un número racional que es menor que 0.

4. ¿ Como escribir una proposición con el cuantificador ningún ?.Veamos

un ejemplo.
Escribamos en lenguaje simbólico la proposición:

’ningún número real elevado al cuadrado es menor que 0’

A=R
P (x) : x2 < 0
En lenguaje simbólico la proposición se escribe como

(∀x ∈ R)(∼ P (x))

o como
(∀x ∈ R)(x2 ≥ 0)

Como ∼ P (x) siempre es verdadera (un número al elevarlo al cuadrado

no es negativo), entonces la proposición es verdadera.

1.7. Ejercicios Resueltos

1. Simbolizar la proposición:
Si el examen comenzó a las 8 A.M. y Lucy llegó a tiempo, entonces Pe-
tra no llegó 15 minutos más temprano que Lucy o Petra no presentó el
examen.

30
Solución: Encontremos en primer lugar las proposiciones atómicas de
la proposición. Estas son:

p : El examen comenzó a las 8 A.M.

q : Lucy llegó a tiempo.
r : Petra llegó 15 minutos más temprano que Lucy.
s : Petra presentó el examen.

Entonces la proposición anterior se puede simbolizar como

(p ∧ q) → (∼ r∨ ∼ s)

Por otro lado, si se conoce que esta proposición es falsa, responda las
siguientes preguntas:

a) ¿ Llego Lucy llegó a tiempo ?

b) ¿ A que hora llegó Petra ?
c) ¿ Presentó Petra el examen.

Para responder estas preguntas debemos encontrar los valores lógicos

de las proposiciones atómicas de la proposición.

Nos dicen que la proposición es falsa; ahora la conectiva principal de la

proposición es un condicional, un condicional es falso si el antecedente
es verdadero y el consecuente es verdadero, razonando de esta manera
obtendremos las respuestas, esto se escribe como sigue:

(p ∧ q) → (∼ r∨ ∼ s)
1| {z 1} 0| {z 0}
1| {z 0}
0
Como vemos V L(p) = V L(q) = V L(r) = V L(s) = 1, entonces Petra
presentó el examen, Lucy llegó a tiempo, y como el examen comenzo a
la 8 y Petra llegó 15 minutos antes que Lucy quien llegó a tiempo (es
decir a las 8), entonces Petra llegó a las 7:45 A.M., en conclusión:

31
 a) Lucy llegó a tiempo.
b) Petra llegó a las 7:45 A.M.
c) Petra presentó el examen.

2. Probar mediante tabla de verdad que

(p → q ∨ r) ⇔ (∼ r → (p → q))

Demostración:

p → q ∨ r ↔ (∼ r → (p → q))
1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 0 0
1 0 0 0 0 1 1 0 1 0 0
0 1 1 1 1 1 0 1 0 1 1
0 1 1 1 0 1 1 1 0 1 1
0 1 0 1 1 1 0 1 0 1 0
0 1 0 0 0 1 1 1 0 1 0

1.8. Ejercicios Propuestos

1. Hallar el dominio de verdad de las funciones proposicionales dadas por:
3x − 1
a) (A, P (x)) donde A = {0, 1, 3, 4} y P (x) : < 4.
2

−3x
b) (A, P (x)) donde A = {−4, −2, 0, 1} y P (x) : + 1 < 5.
2

c) (A, P (x)) donde A = {−3, −2, 0, 2} y P (x) : 2x2 − x < 3.

d ) (A, P (x)) donde A = {−4, −2, 0, 2} y P (x) : −2x2 + x < 3.

e) (A, P (x)) donde A = {2, 3, −5, 0} y P (x) = x2 + 1 es par.

f ) (A, P (x)) donde A = {−2, 3, 5, 0, 1} y P (x) = x2 − 1 es impar.

32
 g) (A, P (x)) donde A = {2, 3, −5, 0, 7, 9, −1} y P (x) = x − 1 es par
o x es primo.

2. Encuentra el dominio de verdad de la función proposicional dada por

(A, B, C, P (x, y, z)), donde A = {0, 1, 3}, B = {−2, −1}, C = {1, 2}, y

P (x, y, z) : x − y + z > 2

3. Escriba una proposición compuesta en lenguaje común y en lenguaje

simbólico, cuya conectiva principal sea un condicional. Luego escriba
su recı́proco, contrario y contrarrecı́proco en ambos lenguajes.

4. Escriba una misma proposición compuesta cuya conectiva principal sea

un condicional en lenguaje común de tres formas distintas.

5. Dada la proposición:
O no veo televisón y hago gimnasia o si hago gimnasia, entonces no
hago dieta ni veo televisión.

Si la proposición es falsa y sı́ se hizo dieta, determinar:

a) ¿ Se hizo gimnasia?
b) ¿ Se vio televisión?

6. Dada la proposición:
Si la función de las 9:30 pm. en el cine empezó a la hora exacta y Pedro
llegó a tiempo, entonces Marı́a no llegó 30 minutos más temprano que
Pedro o no asistió a esta función.
Conociendo que esta proposición es falsa, responda las siguientes pre-
guntas:

a) ¿ Llegó a tiempo Pedro?

b) ¿ Asistió Marı́a a la función?

7. Halle la tabla de verdad de las formas proposicionales dadas por:

a) (p → q) ∧ (r → q) ↔ (p ∨ r → q)
b) (p ∨ q) → r ≡ (p → r) ∧ (q → r)

33
 c) (p → q)∧ ∼ q →∼ p
d ) (p Y q) ↔ (∼ r → p ∧ q)
e) ∼ (p ∨ s) ∧ (∼ q → r)

8. Elimine tantos signos de agrupación como sea posible sin que se altere
el sentido original de las siguientes expresiones:

a) (∼ p) ∧ (∼ (∼ (q → p)))
b) [p → (q ∧ r)] → [p ∨ (∼ (∼ q))]
c) (p ∨ (∼ q)) ↔ (r ∧ s)

9. Dada la expresión:
∼p→q∧r∨m↔t
Utilizar los signos de agrupación necesarios para que la expresión sea:

a) Conjunción de un condicional con un bicondicional.

b) Disyunción de un condicional con un bicondicional.
c) Disyunción de una conjunción con un bicondicional.
d ) Negación de un condicional con consecuente una disyunción.

10. Pruebe deductivamente que:

a) (p ∨ q)∧ ∼ q =⇒ p
b) (p → q)∧ ∼ q ⇒ ∼ p
c) (p → q) ∨ (p → r) ≡ (p → q ∨ r)
d ) (p ∨ q) → r ≡ (p → r) ∧ (q → r)
e) (p ↔ q) ≡ (p ∧ q) ∨ (∼ p∧ ∼ q)
f ) (p ↔ q) ≡∼ (p Y q)
g) (p∨ ∼ q) → (∼ r → p) ≡ (∼ p → q) ∨ (∼ r → q)
h) (∼ r ∧ q) →∼ (q → p) ≡ (p ∧ q) → r

11. Para cada una de las siguientes formas proposicionales:

a) (∼ p ∧ q) ∨ [q ∧ (p ∧ r)]
b) (∼ p∨ ∼ q) ∧ (∼ p∨ ∼ q) ∧ (p ∨ q)

34
 c) [(p ∧ r) ∨ (q∧ ∼ r) ∨ (∼ r ∧ p) ∨ (q ∧ r)] ∧ p
d ) [p ∧ ((q∧ ∼ p) ∨ (r ∧ p))] ∨ [∼ p ∧ ((p ∧ q) ∨ (q ∧ r))]
e) [(p ∧ r) ∨ (∼ q ∨ r) ∨ (p∧ ∼ r)] ∧ [(∼ r ∧ p) ∨ (∼ r∨ ∼ q) ∨ (r ∧ q)]
1) Dibuje su circuito asociado.
2) Simplifique tal circuito.
3) Dibuje el circuito equivalente encontrado.

12. Escriba en lenguaje simbólico las proposiciones:

a) Ningún hombre es inteligente.

b) Algunos hombres no son inteligentes.
c) Algunos estudiantes son puntuales y trabajadores.
d ) Algunos números reales no son racionales.

13. Dadas las formas proposicionales:

p(x) : x es un número par.

q(x) : x es un número entero.

Escriba en lenguaje común la proposición:

(∀x ∈ R)(p(x) → q(x))

14. Dadas las formas proposicionales:

p(x) : x es un número par.

q(x) : x es positivo.

Escriba en lenguaje común las proposiciones:

(∃x ∈ R)(∼ q(x) ∧ p(x))

(∃x ∈ R)(∼ p(x) ∧ q(x))

15. Dadas las formas proposicionales:

35
 p(x) : x es un número par.

q(x) : x es negativo.

r(x) : x es entero.

Escriba en lenguaje común

(∃x ∈ R)(q(x) ∧ p(x) → r(x))

1.9. Referencias Bibliográficas

1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

3. Ramos, Dennis. Estructuras Discretas.

4. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

5. Sáenz, Jorge; y otros. Fundamentos de la Matemática. Hipotenusa. Se-

gunda edición, Barquisimeto, 2001.

36
Capı́tulo 2

CONJUNTOS

En este capı́tulo veremos una introducción a la teorı́a de conjuntos, comen-

zaremos con las definiciones básicas (conjuntos, igualdad de conjuntos, sub-
conjuntos), luego definiremos distintas operaciones que se pueden realizar
con los conjuntos.

2.1. Conjuntos
La teorı́a de conjuntos se construye a partir de tres términos básicos que
son: Conjunto, elemento y pertenencia. El término de conjunto tendrá el
significado que se le da en el lenguaje usual, esto es una colección de objetos,
a estos objetos los llamaremos elementos del conjunto. Por otro lado si A
es un conjunto y x es un elemento de A, diremos que x pertenece a A, y
este lo denotaremos por x ∈ A. Si x no pertenece a A se denotará x ∈ / A.
Es costumbre escribir los conjuntos en letras mayúsculas, mientras que
los elementos de los conjuntos se escriben es minúscula.
Llamaremos conjunto vacı́o a un conjunto que carece de elementos. Se
puede probar que sólo existe un conjunto vacı́o, por lo tanto se suele decir el
conjunto vacı́o, el cual se denota como ∅.
Se llama conjunto referencial o conjunto universal, usualmente de-
notado por U , al conjunto formado por todos los elementos en discusión. Tal
conjunto no es único, depende del contexto en que se trabaja.

Observación 2.1.1 En la teorı́a de conjuntos no se puede hablar del con-

junto que contiene a todos los conjuntos, pues nos conduce a contradicciones.

37
Existen dos maneras de determinar (escribir) un conjunto:
1. Por extensión: se enumeran, entre llaves, sin importar el orden los
elementos del conjunto. Por ejemplo:
a) {1, 2, 3, 4, 5}
b) {a, e, i, o, u}
c) {a, 1, −2, 5, 3, 7, e}
2. Por comprensión: se expresa el conjunto como el dominio de verdad
de una función proposicional.
Si (U, P (x)) es una función proposicional, entonces
A = {x ∈ U/P (x)}
es el conjunto formado por todos los elementos de U que hacen ver-
dadero P (x) (en pocas palabras A es el dominio de verdad de (U, P (x))).
Ası́ por ejemplo:
a) {1, 2, 3, 4, 5} = {x ∈ N/1 ≤ x ≤ 5}.
b) {a, e, i, o, u} = {x ∈ U/x es vocal }, donde U es el conjunto de
todas las letras del abecedario.
c) ∅ = {x ∈ R ∈ /x2 + 1 = 0}.
Un conjunto infinito puede escribirse por extensión, al escribir unos pocos
elementos y luego cuando sea clara la secuencia de los elementos se escriben
puntos suspensivos (dependiendo del conjunto, se escriben puntos suspensivos
al comienzo y/o al final). Veamos unos ejemplos.
1. El conjunto de los números impares positivos {1, 3, 5, 7, 9, ...}.
2. El conjunto de los números impares {..., −3, −1, 3, 5, 7, ...}.
3. Los números enteros negativos {..., −5, −4, −3, −2, −1}.
Definición 2.1.1 Dos conjuntos A y B son iguales, denotado por A = B,
si se cumple que todo elemento de A es elemento de B y viceversa
A = B ⇔ (∀x)(x ∈ A ⇔ x ∈ B)
Si A y B no son iguales decimos que son distintos, lo cual denotaremos
como A 6= B.

38
Ejemplo 2.1.1 Los conjuntos A = {1, 2, 3, 4}, B = {2, 3, 1, 2, 4} son iguales.

Ejemplo 2.1.2 Los conjuntos A = {1, 2, 3, 4} y C = {2, 3, 4} son distintos.

Observación 2.1.2 La igualdad de conjuntos satisface las siguientes propiedades:

1. Para todo conjunto A se cumple que A = A (reflexividad).

2. Si A = B, entonces B = A (simetrı́a).

3. Si A = B y B = C, entonces A = C (transitividad).

Definición 2.1.2 Sean A y B dos conjuntos. Diremos que:

1. A es subconjunto de B ( A está incluido en B), denotado por A ⊂ B,

si se cumple que todo elemento de A es elemento de B.

A ⊂ B ⇔ (∀x)(x ∈ A ⇒ x ∈ B)

Si A no es subconjunto de B, escribiremos A * B.

2. A es subconjunto propio de B (A está incluido propiamente en B),

denotado por A B, si A ⊂ B y A 6= B.

Ejemplo 2.1.3 Si A = {1, 2, 3, 4} y B = {2, 3, 1, 2, 4}, entonces A ⊂ B y

B ⊂ A.

39
Ejemplo 2.1.4 Si A = {1, 2, 3, 4} y C = {2, 3, 4}, entonces C ⊂ A, pero
A * C (1 ∈
/ C), es decir, C A.

Ejemplo 2.1.5 Si A = {x ∈ R/x − 1 < 0} y B = {x ∈ R/ | x + 2 |< 3},

entonces B ⊂ A.

Demostremos esto.

x∈B ⇔ | x + 2 |< 3
⇔ −3 < x + 2 < 3
⇔ −3 − 2 < x + 2 − 2 < 3 − 2
⇔ −5 < x < 1
⇒ x<1
⇔ x−1<0
⇔ x∈A

Ası́ tenemos que B ⊂ A.

Observación 2.1.3 La inclusión de conjuntos satisface las siguientes propiedades:

1. Para todo conjunto A se cumple que ∅ ⊂ A ⊂ U .

2. Para todo conjunto A se cumple que A ⊂ A (reflexividad).

3. Si A ⊂ B y B ⊂ A, entonces A = B (antisimetrı́a).

4. Si A ⊂ B y B ⊂ C, entonces A ⊂ C (transitividad).

La parte dos se puede generalizar como sigue:

Teorema 2.1.1
A=B ⇔A⊂B∧B ⊂A

Esto último nos puede ayudar a la hora de determinar si dos conjuntos son
iguales o no.

40
Definición 2.1.3 El conjunto potencia (o conjunto de partes de A),
denotado por P(A), es el conjunto formado por todos los subconjuntos de A,
es decir,
P(A) = {X ⊂ U/X ⊂ A}

Por la observación anterior, se concluye que para todo conjunto A, se cumple

que: ∅, A ∈ P(A).

Ejemplo 2.1.6 1. P(∅) = {∅}.

2. Si A tiene un elemento, entonces P(A) = {∅, A}.

3. Si A = {1, 2}, entonces P(A) = {∅, {1}, {2}, A}.

4. Si A = {{1}, a, ∅}, entonces

P(A) = {∅, {{1}}, {a}, {∅}, {{1}, a}, {{1}, ∅, {a, ∅}, A}

Observación 2.1.4 1. Si A de n elementos, entonces P(A) tiene 2n ele-

mentos (al número de elementos de un X conjunto se le llama cardinal
y se escribe como ](X)).

2. A ⊂ B ⇔ P(A) ⊂ P(B).

2.2. Operaciones con Conjuntos

Definición 2.2.1 Dados dos conjuntos A y B, se llama unión de A y B,
denotado por A ∪ B, al conjunto formado por los elementos que pertenecen
a A o a B.
A ∪ B = {x ∈ U/x ∈ A ∨ x ∈ B}

41
Ejemplo 2.2.1 Si A = {1, 2, 3, 4, 5} y B = {−1, 0, 1, a, b, 2, 7}, entonces

A ∪ B = {−1, 0, 1, 2, 3, 4, 5, 7, a, b}

Teorema 2.2.1 Para todo conjunto A y B se cumple que A ⊂ A ∪ B y que

B ⊂ A ∪ B.

Demostración:

Demostraremos que A ⊂ A ∪ B y dejaremos la prueba de que B ⊂ A ∪ B

como ejercicio.

x∈A ⇒ x∈A∨x∈B (adición)

⇔ x∈A∪B (def. unión)

Por definición tenemos que A ⊂ A ∪ B.

Definición 2.2.2 Dados dos conjuntos A y B, se llama intersección de

A y B, denotado por A ∩ B, al conjunto formado por los elementos que
pertenecen a A y a B.

A ∩ B = {x ∈ U/x ∈ A ∧ x ∈ B}

42
Ejemplo 2.2.2 Si A = {1, 2, 3, 4, 5}, B = {−1, 0, 1, a, b, 2, 7} C = {−1, 0},
entonces A ∩ B = {1, 2}, A ∩ C = ∅, B ∩ C = {−1, 0}.

Definición 2.2.3 Dos conjuntos son disjuntos si su intersección es vacı́a.

Por ejemplo los conjuntos A y C del ejemplo anterior son disjuntos.

Teorema 2.2.2 Para todo conjunto A y B se cumple que A ∩ B ⊂ A y que

A ∩ B ⊂ B.

Demostración:

Demostraremos que A ∩ B ⊂ A y dejaremos la prueba de que A ∩ B ⊂ B

como ejercicio

x∈A∩B ⇔ x∈A∧x∈B (def. intersección)

⇒ x∈A (simplificación)

Por definición tenemos que A ∩ B ⊂ A.

Teorema 2.2.3 A ⊂ B ⇔ A ∩ B = A

Dejamos esta demostración como el problema resuelto 2.

43
Definición 2.2.4 Dados un conjunto A, se llama complemento de A, de-
notado por {A, al conjunto formado por los elementos del conjunto referencial
U que no pertenecen a A.
{A = {x ∈ U/x ∈
/ A}

Ejemplo 2.2.3 Si U = {1, 2, 3, 4, 5, 6, 7, 8, 9} y A = {1, 3, 4, 7}, entonces

{A = {2, 5, 6, 8, 9}
Definición 2.2.5 Dados dos conjuntos A y B, se llama diferencia de A y
B, denotado por A−B, al conjunto formado por los elementos que pertenecen
a A y que no pertenecen a B.
A − B = {x ∈ U/x ∈ A ∧ x ∈
/ B}

44
Ejemplo 2.2.4 Si A = {1, 2, 3, 4, 5}, B = {−1, 0, 1, a, b, 2, 7}, entonces

A − B = {3, 4, 5}

B − A = {−1, 0, a, b, 7}
Note que A − B 6= B − A.

Observación 2.2.1
{A = U − A
A − B = A ∩ {B

Definición 2.2.6 Dados dos conjuntos A y B, se llama diferencia simétri-

ca de A y B, denotado por A4B, al conjunto formado por los elementos que
pertenecen o a A o que pertenecen a B.

A4B = {x ∈ U/x ∈ A Y x ∈ B}

Ejemplo 2.2.5 Si A = {1, 2, 3, 4, 5}, B = {−1, 0, 1, a, b, 2, 7}, entonces

A4B = {3, 4, 5, −1, 0, a, b, 7}

Teorema 2.2.4
A4B = (A − B) ∪ (B − A)
A4B = (A ∪ B) − (A ∩ B)

45
Demostración:

Demostraremos la primera igualdad, dejaremos la prueba de la segunda

al lector.

x ∈ A4B ⇔ x∈AYx∈B (def. difer. simétrica)

⇔ (x ∈ A ∧ x ∈
/ B) ∨ (x ∈ B ∧ x ∈
/ A) (ley. disy. exclusiva)
⇔ x ∈ (A − B) ∨ x ∈ (B − A) (def. diferencia)
⇔ x ∈ (A − B) ∪ (B − A) (def. unión)

46
 LEYES DEL ÁLGEBRA DE CONJUNTOS

Leyes Idempotentes
A∪A=A A∩A=A
Leyes Conmutativas
A∪B =B∪A A∩B =B∩A
Leyes Asociativas
(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Leyes Distributivas
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Leyes de Identidad
A∪U =U AT∪∅=A
A∩∅=∅ A U =A
Leyes de Complementación
A ∩ {A = ∅ A ∪ {A = U
{({A) = A {∅ = U, {U = ∅
Leyes de De Morgan
{(A ∪ B) = {A ∩ {B {(A ∩ B) = {A ∪ {B
Leyes de Absorción
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

Demostraremos dos propiedades, el resto queda como ejercicio para el

lector.

Probemos que (A ∪ B) ∪ C = A ∪ (B ∪ C)

x ∈ (A ∪ B) ∪ C ⇔ x ∈ (A ∪ B) ∨ x ∈ C (def. unión)
⇔ (x ∈ A ∨ x ∈ B) ∨ x ∈ C (def. unión)
⇔ x ∈ A ∨ (x ∈ B ∨ x ∈ C) (asociativa)
⇔ x ∈ A ∨ x ∈ (B ∪ C) (def. unión)
⇔ x ∈ A ∪ (B ∪ C) (def. unión)

∴ (A ∪ B) ∪ C = A ∪ (B ∪ C)

47
Probemos ahora que {(A ∩ B) = {A ∪ {B
x ∈ {(A ∩ B) ⇔ x∈/ (A ∩ B) (def. complemento)
⇔ ∼ (x ∈ (A ∩ B)) (negación)
⇔ ∼ (x ∈ A ∧ x ∈ B) (def. intersección)
⇔ ∼ (x ∈ A)∨ ∼ (x ∈ B) (De Morgan)
⇔ x∈/ A∨x∈ /B (negación)
⇔ x ∈ {A ∨ x ∈ {B (def. complemento)
⇔ x ∈ ({A ∩ {B) (def. intersección)

∴ {(A ∩ B) = {A ∪ {B


Probemos que A ∪ (B − C) = (A ∪ B) − (C − A)

(A ∪ B) − (C − A) = (A ∪ B) ∩ {(C ∩ {A) (X − Y = X ∩ {Y )
= (A ∪ B) ∩ ({C ∪ {({A)) (De Morgan)
= (A ∪ B) ∩ ({C ∪ A) (complementación)
= (A ∪ B) ∩ (A ∪ {C) (conmutativa)
= A ∪ (B ∩ {C) (distributiva)
= A ∪ (B − C) (X − Y = X ∩ {Y )


Ejemplo 2.2.6 Sean U = {1, 2, 3, 4, ..., 10}, A = {1, 2, 3, 4, 8}, B = {2, 4, 6, 8},
C = {1, 2, 5, 7, 9}. Encuentre:
(A ∩ B) − (C ∪ {A)
Solución:
A ∩ B = {2, 4, 8}
{A = {5, 6, 7, 9}
C ∪ {A = {1, 2, 5, 6, 7, 9}
(A ∩ B) − (C ∪ {A) = {4, 8}

48
Definición 2.2.7 Sea X un conjunto no vacı́o. Una partición del conjunto
X es una familia de subconjuntos no vacı́os de X, disjuntos dos a dos y cuya
unión es X.

Ejemplo 2.2.7 Sea X = {1, 2, 3, 5, a}. Una partición de X serı́a por ejemplo

{{1, 3}, {2, a, 5}}

Otra partición de X serı́a

{{1}, {2, 3}, {5, a}}

Los siguientes conjuntos no son particiones de X.

1. {{1, 2, 3}, ∅, {5, a}}

2. {{1, 2, 3}, {3, a}, {5}}

3. {{1, 3}, {5, 2}}

El primero no lo es porque uno de los conjuntos es vacı́o, el segundo no lo es

porque dos de sus conjuntos no son disjuntos, y el tercero no lo es porque la
unión de los conjuntos no es todo X.

2.3. Producto Cartesiano

Definición 2.3.1 Un par ordenado (a, b), es un conjunto de dos elementos
en el que el orden de los elementos es tomado en cuenta (a es el primer
elemento y b es el segundo elemento del par ordenado respectivamente).

Observación 2.3.1

(a, b) = (c, d) ⇔ a = c ∧ b = d

Definición 2.3.2 Dados dos conjuntos A y B, se llama producto carte-

siano de A y B, denotado por AxB, al conjunto:

AxB = {(x, y) ∈ U/x ∈ A ∧ y ∈ B}

Ejemplo 2.3.1 Si A = {1, 2, 3} y B = {1, 3, a, 4}. Entonces,

49
 1. AxB = {(1, 1), (1, 3), (1, a), (1, 4), (2, 1), (2, 3), (2, a), (2, 4), (3, 4), (3, 3), (3, a), (3, 4)}.

2. BxA = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 2), (3, 3), (a, 1), (a, 2), (a, 3), (4, 1), (4, 2), (4, 3)}.

3. AxA = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}.

Note que AxB 6= BxA.

Para obtener una representación gráfica del conjunto XxY , donde X, Y
son subconjuntos de R o conjuntos finitos, se dibuja un plano tomando como
abscisas los elementos del conjunto X y como ordenadas el conjunto Y . En
el plano obtenido se marcan los pares ordenados que conforma el conjunto
XxY .
Por ejemplo el punto (a, 1) de BxA ( ejemplo anterior) lo podemos rep-
resentar como sigue:

Teorema 2.3.1 Sean A, B, C conjuntos. Entonces se cumple que:

1. Ax(B ∪ C) = (AxB) ∪ (AxC)

2. Ax(B ∩ C) = (AxB) ∩ (AxC)

3. Ax(B − C) = (AxB) − (AxC)

50
2.4. Ejercicios Resueltos
1. Sean A = {x ∈ R/ | x+2 |< 3}, B = {x ∈ R/−5 < x < 1}. Demuestre
que A = B
Demostración:

x∈A ⇔ | x + 2 |< 3
⇔ −3 < x + 2 < 3
⇔ −3 − 2 < x + 2 − 2 < 3 − 2
⇔ −5 < x < 1
⇔ x∈B

Entonces B = C.

2. Si U = {0, 1, 2, 3, 4, ..., 10}, A = {x ∈ U/ x es par}

B = {x ∈ U/ x divide a 4} y C = {x ∈ U/x > 7}. Encuentre:

1) A, B, C, BxC
T S
2) B A − {(C A)

Solución:
1. A = {0, 2, 4, 6, 8, 10}, B = {1, 2, 4}, C = {8, 9, 10}
BxCS= {(1, 8), (2, 8), (4, 8), (1, 9), (2, 9), (4, 9), (1, 10), (2, 10), (4, 10)}
2. C A = {0, 2, 4, 6, 8, 9, 10}, luego
S
{(C A) = {1, 3,T5, 7}
por otro lado, B A = {2, 4}, entonces

T S
B A − {(C A) = {2, 4}

3. Demuestre que A ⊂ B ⇔ A ∩ B = A
Demostración: Para realizar esta demostración debemos tener pre-
sente que
p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p)
Entonces dividiremos la prueba en dos, primero se demostrará que
A ⊂ B ⇒ A ∩ B = A y luego que A ∩ B = A ⇒ A ⊂ B.
(⇒)

51
 Hipótesis: A ⊂ B.
Tesis: A ∩ B = A (lo que se debe probar).
Por el teorema anterior se tiene que A∩B ⊂ A, ası́ que sólo falta probar
que A ⊂ A ∩ B (bajo nuestra hipótesis).
x∈A ⇔ x∈A∧x∈A (idempotencia)
⇒ x∈A∧x∈B (hipótesis)
⇔ x∈A∩B (def. intersección)

Tenemos ası́ que A ⊂ A ∩ B y como A ∩ B ⊂ A, del teorema 2.1.1

tenemos que A ∩ B = A.
(⇐)
Hipótesis: A ∩ B = A.
Tesis: A ⊂ B.

x∈A ⇒ x∈A∩B (hipótesis)

⇔ x∈A∧x∈B (def. intersección)
⇔ x∈B (simplificación)

Tenemos ası́ que A ⊂ B.


S
4. Demuestre que A4B ⊂ {A {B.
Demostración:

x ∈ A4B ⇔ x∈AYx∈B Def. Dif. Simétrica

⇔ (x ∈ A ∧ x ∈
/ B) ∨ (x ∈ B ∧ x ∈/ A) Ley Dis. Exclusiva
⇒ (x ∈
/ B) ∨ (x ∈
/ A) Ley Simplificación
⇔ (x ∈
/ A) ∨ (x ∈
/ B) Ley Conmutativa
⇔ (x ∈ {A) ∨ (x ∈ {B) Def. Complemento
[
⇔ x{A {B Def. Unión
S
∴ A4B ⊂ {A {B

52
 
T S T S T S
5. Demuestre que (A B) ({A B) (A {B) = A B.
Demostración: Dejamos como ejercicio al lector el justificar los pasos.
\ [ \ [ \ [ \ [ \
(A B) ({A B) (A {B) = [(A {A) B)] (A {B)
\ [ \
= (U B) (A {B)
[ \
= B (A {B)
[ \ [
= (B A) (B {B)
[ \
= (B A) U
[
= (B A)
[
= (A B)

2.5. Ejercicios Propuestos

1. Escriba por compresión los siguientes conjuntos:
2 2 2 2 2
a) { , , , , ..., }
3 4 5 6 50
1 3 5 7 49
b) { , , , , ..., }
2 4 6 8 50
1 3 5 7 49
c) { , , , , ..., }
2 2 2 2 2
d) {1, 4, 7, 10, 13, ...}

e) {0, 4, 8, 12, 16, ...}

f ) {..., −8, −3, 2, 7, 12, ...}

g) {1, 4, 9, 16, 25, ..., 144}

53
2. Escribe por extención los siguientes conjuntos:

a) {x ∈ Z/x = 2n + 3, n ∈ Z}
b) {x ∈ Z/1 < x < 10}
−4
c) {x ∈ Q/x = , n ∈ {1, 2, 3, 4, 5, 6, 7}}
n+5
d) {x ∈ Z/x = 4n, n ∈ Z}
e) {x ∈ Z/ − 5 ≤ x ≤ 3}

2n + 1
f ) {x ∈ Q/x = , n ∈ {0, 1, 2, 3, 4, ..., 50}}
2n + 3

g) {x ∈ N/x = n2 + 1, n ∈ {0, 1, 2, 3, 4, ..., 10}}

3. Encuentre P(A) si:

a) A = {∅, 1, {a}}
b) A = {∅, 1, a}
c) A = {∅, −1, {3}}
d) A = {1, −1, {3}, a}
e) A = {1, {1}, {{1}}}

4. Si U = {1, 2, 3, 4, ..., 9}, A = {x ∈ U/ x es par}

B = {x ∈ U/ x es mayor que 4} y C = {x ∈ U/ x divide a 9}.
Encuentre:

1) A, B, C
T S
2) B A − {(C A)
3) B 4 (A − C)
4) AxB, AxC

5. Si U = {1, 2, 3, 4, ..., 9}, A = {x ∈ U/ x es impar }

B = {x ∈ U/ x es menor que 5} y C = {x ∈ U/ x divide a 9}.
Encuentre:

1) A, B, C
T S
2) B A − {(C B)

54
 3) B 4 (A − C)
4) AxB, CxB, BxB

6. Si U = {1, 2, 3, 4, ..., 9}, A = {x ∈ U/ x es impar }

B = {x ∈ U/ x es menor que 7} y C = {x ∈ U/ x divide a 8}.
Encuentre:

1) A, B, C
T S
2) B A − {(C B)
3) B 4 (A − C)
4) Ax(A ∪ B), Ax(B − C)

7. Si U = {1, 2, 3, 4, ..., 9}, A = {x ∈ U/ x es primo }

B = {x ∈ U/ x es par } y C = {x ∈ U/ x divide a 8}. Encuentre:

1) A, B, C
T S
2) B A − {(C B)
3) A 4 (B − C)
4) AxB, CxB

8. Demuestre que:
S
a) (A − B) − C = A − (B C)
S T
b) A − (B − C) = (A − B) (A C)
S S
c) (A B) − C = (A − C) (B − C)
d ) A4B = {A4{B
S S T
e) A B = (A4B) (A B)
f ) (A − B) − C ⊂ A − (B − C)
g) A ∪ (B − C) = (A ∪ B) − (C − A)
h) (A ∩ B) − C = (A − C) ∩ (B − C)
S
i ) A4B ⊂ A B

9. Si A = {x ∈ R/4x + 5 > 13} y B = {x ∈ R/x > 2}, demuestre que

A = B.

55
 10. Si A = {x ∈ R/x = 2n + 2, n ∈ Z} y B = {x ∈ R/x es par }
demuestre que A = B.
2x
11. Si A = {x ∈ R/ − 1 < 3} y B = {x ∈ R/x < 10}, demuestre que
5
A = B.
2x
12. Si A = {x ∈ R/ − 1 < 1} y B = {x ∈ R/x < 7}, demuestre que
5
A ⊂ B.

13. Encuentre tres particiones distintas del conjunto dado por:

A = {1, −2, 3, −4, b, 6, 7, ∅, 9, a}

14. Encuentre los números reales x, y tales que los puntos A y B sean
iguales si:

a) A = (x, y) y B = (4, y + 3)
b) A = (x, y + 4) y B = (2 − x, 3y − 4)
c) A = (x, y 2 ) y B = (x + 2, 2y + 1)
2x y
d) A = ( , 3y) y B = (x + 1, − 1)
3 3
15. Dibuje los siguientes conjuntos:

a) [1, 4]x[−1, 5]
b) [−2, 7)x(5, 7]
c) (0, 2)x[−3, 4]
d) [−3, 1)x(−5, 2)

2.6. Referencias Bibliográficas

1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

56
3. Ramos, Dennis. Estructuras Discretas.

4. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

5. Sáenz, Jorge; y otros. Fundamentos de la matemática. Hipotenusa. Se-

gunda edición, Barquisimeto, 2001.

57
Capı́tulo 3

RELACIONES

Comenzaremos con la definición formal de relación, ası́ como los concep-

tos de dominio, rango y relación inversa, pasaremos luego al estudio de las
relaciones compuestas y las relaciones en un conjunto.

3.1. Relaciones Binarias

Definición 3.1.1 Sean X, Y conjuntos. Una relación de X en Y es un
subconjunto R del producto cartesiano XxY . Al conjunto X en este caso se
le llama conjunto de partida de R y al conjunto Y se le llama conjunto
de llegada de la relación R.

Ejemplo 3.1.1 Si X = {1, 2, 3} y Y = {1, 3, a, 4}. Entonces:

XxY = {(1, 1), (1, 3), (1, a), (1, 4), (2, 1), (2, 3), (2, a), (2, 4), (3, 4), (3, 3), (3, a), (3, 4)}

Por lo tanto

1. ∅

2. XxY

3. R = {(1, 1), (1, 4), (2, 1)}

4. S = {(1, 1), (1, 3), (2, a), (3, 4)}

son relaciones de X en Y .

58
Notemos por otro lado que:

Y xX = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 2), (3, 3), (a, 1), (a, 2), (a, 3), (4, 1), (4, 2), (4, 3)}

ası́ que {(1, 1), (a, 1), (4, 1)} (por ejemplo) es una relación de Y en X, pero
no una relación de X en Y (casualmente {(1, 1), (1, 3)} es relación de Y en
X y de X en Y ).
Observación 3.1.1 Sea R una relación de X en Y :
1. Si X = Y , en lugar de decir que R es una relación de X en X, diremos
que R es una relación en X.

2. Si (x, y) ∈ R, escribiremos a menudo xRy, que se lee ’x está relaciona-

do con y, mediante la relación R’.

Definición 3.1.2 Sea R una relación de X en Y . Definimos como:

1. El dominio de R, denotado por dom(R), al conjunto dado por:

dom(R) = {x ∈ X/xRy, para algún y ∈ Y }

2. El rango de R, denotado por rang(R), al conjunto dado por:

rang(R) = {y ∈ Y /xRy, para algún x ∈ X}

En otras palabras el dominio (rango) de una relación R, esta formado

por todos aquellos puntos del conjunto de partida (llegada) que aparecen
en la primera (segunda) componente de los elementos de la relación R.

3. La relación inversa de R, denotado por R−1 , a la relación de Y en

X dada por:
R−1 = {(y, x) ∈ Y xX/xRy}

Ejemplo 3.1.2 Consideremos las relaciones R = {(1, 1), (1, 4), (2, 1)} y
S = {(1, 1), (1, 3), (2, a), (3, 4)} del ejemplo anterior. Entonces:
1. dom(R) = {1, 2}, dom(S) = {1, 2, 3}

2. rang(R) = {1, 4}, rang(S) = {1, 3, a, 4}

3. R−1 = {(1, 1), (4, 1), (1, 2)}, S −1 = {(1, 1), (3, 1), (a, 2), (4, 3)}

59
Teorema 3.1.1 Sea R una relación de X en Y . Entonces:
1. dom(R) = rang(R−1 )

2. dom(R−1 ) = rang(R)

3. (R−1 )−1 = R

Demostración:

Demostraremos la parte 1 del teorema y dejaremos el resto como ejercicio

al lector.

Sea R una relación de X en Y .

x ∈ dom(R) ⇔ ∃y ∈ Y, (x, y) ∈ R (def. dominio)

⇔ ∃y ∈ Y, (y, x) ∈ R−1 (def. inversa)
⇔ x ∈ rang(R−1 ) (def. rango)

REPRESENTACIONES GRÁFICAS DE LAS RELACIONES

Veremos tres formas de representar gráficamente una relación.

1. REPRESENTACIÓN CARTESIANA

Para obtener una representación cartesiana de una relación se dibuja

un plano tomando como abscisas los elementos del conjunto de parti-
da y como ordenadas el conjunto de llegada. En el plano obtenido se
marcan los pares ordenados que conforma la relación.
Generalmente este tipo de representación es muy útil cuando los con-
junto de partida y llegada son subconjuntos de R.

Ejemplo 3.1.3 Si X = {1, 2, 3}, Y = {−1, 0, a, b}, y R es la relación

de X en Y dada por:

R = {(1, −1), (1, a), (3, 0), (3, a)}

Entonces la representación cartesiana de R viene dada por:

60
2. REPRESENTACIÓN MATRICIAL

La representación matricial se usa cuando los conjuntos de partida y de

llegada son finitos y con pocos elementos. Se asigna a cada elemento del
conjunto de partida una fila y a cada elemento del conjunto de llegada
una columna. Si (x, y) está en la relación R, en la intersección de la fila
que corresponda a x con la columna que corresponda a y, escribiremos
1; en caso contrario escribiremos 0. A la matriz resultante se le llama
matriz de la relación R, denotada por MR .

Ejemplo 3.1.4 Si X = {1, 2, 3}, Y = {−1, 0, a, b}, y R es una relación

de X en Y dada por:

R = {(1, −1), (1, a), (3, 0), (3, b), (3, a)}

Entonces MR viene dada por:

 
1 0 1 0
MR =  0 0 0 0 
0 1 1 1

3. REPRESENTACIÓN SAGITAL

61
La representación sagital se usa cuando los conjuntos de partidas y
de llegada son finitos y con pocos elementos. Se obtiene representando
mediante los llamados diagramas de Venn el conjunto de partida y
el conjunto de llegada. Si (x, y) está en la relación R, se une x con y
mediante una flecha, esta flecha parte de x y términa en y.

Ejemplo 3.1.5 Si R = {(1, −1), (1, a), (3, 0), (3, b), (3, a)} es la relación
del ejemplo anterior (entonces R−1 = {(−1, 1), (a, 1), (0, 3), (b, 3), (a, 3)}),
la representación de sagital de R y R−1 vienen dadas respectivamente
por:

62
 Si el conjunto de partida es igual al conjunto de llegada, se usa un
sólo diagrama de Venn, y las flechas se representan en el interior del
diagrama.

Ejemplo 3.1.6 Si X = {1, a, 2}, R = {(1, 1), (a, 1), (2, 2), (1, 2)} es
una relación en X. La representación sagital de R viene dada por:

Definición 3.1.3 Sea R una relación de X en Y y sea S una relación de Y

en Z. Se llama composición de R con S a la relación de X en Z, denotada
por S ◦ R, dada por:
S ◦ R = {(x, z) ∈ XxZ/∃y ∈ Y, xRy ∧ ySz}

63
Es decir,
x(S ◦ R)z ⇔ ∃y ∈ Y, xRy ∧ ySz

Ejemplo 3.1.7 Sean X = {1, 2, 3}, Y = {1, 2, 4, 5}, Z = {3, 5, 7, 8}. Con-
sideremos las relaciones R y S de X en Y y de Y en Z respectivamente,
definidas como:
R = {(1, 1), (2, 4), (3, 5), (1, 2)}, S = {(1, 3), (2, 3), (5, 8)}
Entonces la relación S ◦ R viene dada por:
S ◦ R = {(1, 3), (3, 8)}
Teorema 3.1.2 Si R es una relación de X en Y y S es una relación de Y
en Z, entonces:
(S ◦ R)−1 = R−1 ◦ S −1
Ejemplo 3.1.8 Consideremos X, Y, Z, R, S como en el ejemplo anterior, en-
tonces
(S ◦ R)−1 = {(3, 1), (8, 3)}
Por otro lado S −1 = {(3, 1), (3, 2), (8, 5)} y R−1 = {(1, 1), (4, 2), (5, 3), (2, 1)},
ası́ que
R−1 ◦ S −1 = {(3, 1), (8, 3)}

64
3.2. Relaciones en un Conjunto
Recordemos que si R es una relación de X en Y , donde X = Y , entonces
se suele decir que R es una relación en X.
Definición 3.2.1 Sea R una relación en un conjunto X. Diremos que:
1. R es reflexiva si y sólo si para todo x en X, se cumple que xRx.

2. R es simétrica si y sólo si se cumple que xRy ⇒ yRx.

3. R es antisimétrica si y sólo xRy ∧ yRx ⇒ x = y.

4. R es transitiva si y sólo xRy ∧ yRx ⇒ xRz.

Ejemplo 3.2.1 Sea X un conjunto no vacı́o. Definimos la relación diag-

onal de X o la relación identidad de X, denotada por IX , a la relación
dada por:
IX = {(x, x)/x ∈ X}
Es decir, xIX y ⇔ x = y

Ası́ por ejemplo si X = {1, 2, 3}, entonces

IX = {(1, 1), (2, 2), (3, 3)}

Si X = {1, 3, −5, a}, entonces

IX = {(1, 1), (3, 3), (−5, −5), (a, a)}

Se puede ver que para todo conjunto X la relación IX es una relación reflex-
iva, simétrica, antisimétrica y transitiva.

Ejemplo 3.2.2 Sea U un conjunto referencial. Sea R la relación de inclusión

en P(U ), esto es
ARB ⇔ A ⊂ B
De la teorı́a de conjuntos concluimos que esta relación es reflexiva, anti-
simétrica y transitiva (solamente es simétrica si U es vacı́o).

Observación 3.2.1 Si una relación está representada en forma sagital, con-

cluimos que es:

65
 1. Reflexiva si y sólo si cada vértice tiene un lazo.

2. Simétrica si y sólo si cada flecha que une dos vértices distintos existe
otra de sentido contrario.

3. Antisimétrica si y sólo si para cada par de vértices distintos donde

hay flecha de ida no hay otra entre ellos de vuelta.

4. Transitiva si y sólo si para cada par de flechas consecutivas existe

una tercera flecha que une el vértice inicial de la primera flecha con el
vértice final de la segunda flecha.

Ejemplo 3.2.3 Consideremos las siguientes relaciones:

66
 1. R1 no es reflexiva ya que no hay un lazo en a, no es simétrica porque
no hay flecha de vuelta de 1 hasta a (tampoco desde 2 hasta 1). Es
antisimétrica. No es transitiva pues hay una fleha de a hasta 1, y de 1
hasta 2, pero no hay una de a hasta 2.
2. R2 es reflexiva, no es simétrica porque no hay flecha de vuelta de 2
hasta 1. No es antisimétrica porque hay una flehas de ida y vuelta de
a hasta 1. Es transitiva.
3. R3 es reflexiva. Es también simétrica, antisimétrica y transitiva (se
puede notar que no hay conflicto con las definiciones).

A continuación veremos un teorema que nos ayudará a la hora de determinar

si una relación (en un conjunto) es reflexiva, simétrica, antisimétrica y/o
transitiva. Demostraremos la parte 2 del teorema y dejaremos el resto como
ejercicio para el lector.
Teorema 3.2.1 Sea R una relación en X. Entonces:
1. R es reflexiva si y sólo si IX ⊂ R.
2. R es simétrica si y sólo si R = R−1 .
3. R es antisimétrica si y sólo si R ∩ R−1 ⊂ IX .
4. R es transitiva si y sólo si R ◦ R−1 ⊂ R.
Demostración:

Sea R una relación en X.

(⇒)
Supongamos que R es simétrica.

(x, y) ∈ R ⇒ (y, x) ∈ R (R es simétrica)

⇒ (x, y) ∈ R−1 (def. relación inversa)

∴ R ⊂ R−1 (∗)
Por otro lado,

(x, y) ∈ R−1 ⇒ (y, x) ∈ R (def. relación inversa)

⇒ (x, y) ∈ R (R es simétrica)

67
∴ R−1 ⊂ R (∗∗)
De (∗) y (∗∗) concluimos que R = R−1
(⇐)
Supongamos que R = R−1 .

(x, y) ∈ R ⇒ (x, y) ∈ R−1 (por hipótesis R = R−1 )

⇒ (y, x) ∈ R (def. relación inversa)

∴ R es simétrica.


Ejemplo 3.2.4 Sean X = {1, 2, 3, 4} y R la relación en X dada por:

R = {(1, 1), (1, 3), (1, 4), (2, 2), (4, 2), (4, 4), (3, 3), (3, 4), (2, 3)}

1. IX = {(1, 1), (2, 2), (3, 3), (4, 4)}, como IX ⊂ R, entonces R es reflexiva.

2. R−1 = {(1, 1), (3, 1), (4, 1), (2, 2), (2, 4), (4, 4), (3, 3), (4, 3), (3, 2)}, como
R 6= R−1 , entonces R no es simétrica.

3. R ∩ R−1 = {(1, 1), (2, 2), (3, 3), (4, 4)} ⊂ IX , ası́ que la relación es anti-
simétrica.

4. R ◦ R−1 = {(1, 1), (1, 3), (1, 2), (1, 4), (2, 2), (2, 4), (4, 2), (4, 4), (4, 1),
(4, 3), (3, 1), (3, 3), (3, 2), (3, 4), (2, 1), (2, 3)}
como R◦R−1 no es subconjunto de R, concluimos que R no es transitiva.

3.3. Relaciones de Equivalencia y de Orden

Definición 3.3.1 Sea R una relación en un conjunto X. Diremos que:
1. R es una relación de equivalencia si es reflexiva, simétrica y transi-
tiva, en tal caso es costumbre denotar la relación por el simbolo ∼
En este caso si a ∼ b (aRb), se dice que a es equivalente a b.

2. R es una relación de orden si es reflexiva, antisimétrica y transitiva,

en tal caso es costumbre denotar la relación por el simbolo ≺
En este caso si a ≺ b (aRb), se dice que a es anterior a b o que b es
posterior a a.

68
Ejemplo 3.3.1 1. La relación IX es una relación de equivalencia y es
una relación de orden.

2. La relación de inclusión es una relación de orden (sólo es de equiva-

lencia si U es vacı́o).

3. La relación del ejemplo 3.2.4 no es de equivalencia ni de orden.

Definición 3.3.2 Sea X un conjunto y ∼ una relación de equivalencia en

X. Si x ∈ X, llamaremos clase de equivalencia de x, denotado por [x], al
subconjunto de X formado por todos los elementos de X que son equivalentes
ax
[x] = {y ∈ X/x ∼ y}

Teorema 3.3.1 Si ∼ es una relación de equivalencia en X, entonces

a ∼ b ⇔ [a] = [b]

Definición 3.3.3 Sea ∼ una relación de equivalencia en un conjunto X. Se

X
llama conjunto cociente de X por ∼ al conjunto denotado por dado
∼
por:
X
= {[x]/x ∈ X}
∼
Observación 3.3.1 1. El conjunto cociente de un conjunto X por una
relación de equivalencia es una partición de X.

2. Toda partición de un conjunto X, determina sobre este conjunto una

relación de equivalencia cuyo conjunto cociente es precisamente, la par-
tición dada.

Definición 3.3.4 Un conjunto ordenado es un par (X, ≺), donde X es

un conjunto y ≺ es una relación de orden en X. En tal caso se dice que X
está ordenado por ≺.

Definición 3.3.5 Sea (X, ≺) un conjunto ordenado. Dos elementos x, y de

X se dice que son comparables si se cumple que

x≺y∨y ≺x

en caso contrario se dice que son incomparables.

69
Ejemplo 3.3.2 Sea U = {1, 2}. Entonces P(U ) = {∅, U, {1}, {2}}. Si con-
sideramos la relación inclución en P(U ) (que es una relación de orden en
P(U )), tendremos que
{1} ⊂ U , ası́ que {1} ≺ U , por lo tanto {1} y U son comparables.

Por otro lado, {1} no es subconjunto de {2}, ni {2} es subconjunto de

{1}, por lo tanto {1} y {2} son incomparables.

Definición 3.3.6 Una relación de orden total (o de orden lineal) en un

conjunto X es una relación de orden ≺ en X tal que todo par de elementos
de X son comparables. Es decir

(∀x ∈ X)(∀y ∈ Y )(x ≺ y ∨ y ≺ x)

Una relación de orden que no es de orden total se dice que es de orden

parcial.

Definición 3.3.7 Si ≺ es un orden total en X, entonces se dice que (X, ≺)

es un conjunto totalmente ordenado. Si ≺ es un orden parcial en X,
entonces se dice que (X, ≺) es un conjunto parcialmente ordenado.

Ejemplo 3.3.3 La relación menor o igual, ≤, en R, es una relación de orden

total.

3.4. Ejercicios Resueltos

1. Sea R la relación en Z dada por:

xRy ⇔| x |=| y |

Investigue si R es reflexiva, simétrica, antisimétrica o transitiva.

Solución: Sea x ∈ Z
| x |=| x |⇒ xRx
Por lo tanto R es reflexiva.

70
 Supongamos que xRy
xRy ⇒ | x |=| y |
⇒ | y |=| x |
⇒ yRx

Por lo tanto R es simétrica.

R no es antisimétrica, ya que 1R(−1) y (−1)R1 pero claramente 1 6=

−1.

Por último veamos si R es transitiva. Sean xRy y yRz

xRy ∧ yRz ⇒ | x |=| y | ∧ | y |=| z |
⇒ | x |=| z |
⇒ xRz

Ası́ que R es transitiva.

2. La relación del ejemplo anterior es reflexiva, simétrica y transitiva por
lo tanto es una relación de equivalencia. Encontremos entonces el con-
junto cociente de Z por R.

[0] = {x ∈ Z/xR0}
= {x ∈ Z/ | x |=| 0 |}
= {x ∈ Z/ | x |= 0}
= {x ∈ Z/x = 0}
= {0}
Sea a ∈ Z − 0
[a] = {x ∈ Z/xRa}
= {x ∈ Z/ | x |=| a |}
= {x ∈ Z/x = a, x = −a}
= {a, −a}

71
 Notemos que [a] = [−a].
Z
= {[0], [1], [2], [3], [4], ...}
R
3. Si X = {0, 1, 2}, Y = {0, 4, 5}, Z = {0, 6, 7} y R, S son relaciones de
X en Y y de Y en Z respectivamente, dadas por:
xRy ⇔ x + y es par ySz ⇔ z − y < 1
Encuentre:

a) R, S, R−1 , S −1 .
b) El dominio y rango de cada una de las relaciones de la parte anterior.
c) La representación matricial de R, S, R−1 , S −1 .
d) S ◦ R, (S ◦ R)−1 , R−1 ◦ S −1 .

Solución:

a) Sustituyendo los valores de x, y, z encontramos que

R = {(0, 0), (0, 4), (1, 5), (2, 0), (2, 4)} y S = {(0, 0), (4, 0), (5, 0)}
Por lo tanto
R−1 = {(0, 0), (4, 0), (5, 1), (0, 2), (4, 2)} y S −1 = {(0, 0), (0, 4), (0, 5)}
b) dom(R) = rang(R−1 ) = {0, 1, 2}, rang(R) = dom(R−1 ) = {0, 4, 5}
dom(S) = rang(S −1 ) = {0, 4, 5}, rang(S) = dom(S −1 ) = {0}
     
1 1 0 1 0 1 1 0 0
c) MR =  0 0 1 , MR−1 =  1 0 1 , MS =  1 0 0 ,
1 1 0
  0 1 0 1 0 0
1 1 1
MS =
−1  0 0 0 
0 0 0
d) S◦R = {(0, 0), (1, 0), (2, 0)}, entonces (S◦R)−1 = {(0, 0), (0, 1), (0, 2)}
Recordemos por teorema que (S ◦ R)−1 = R−1 ◦ S −1 , ası́ que

R−1 ◦ S −1 = {(0, 0), (0, 1), (0, 2)}

4. Sean R y S relaciones en un conjunto X. Pruebe que si R y S son

transitivas, entonces R ∩ S es transitiva.

72
 Demostración: Supongamos que x(R ∩ S)y y que y(R ∩ S)z (dejamos
la justificación de los pasos como ejercicio al lector)

x(R ∩ S)y ∧ y(R ∩ S)z ⇒ (x, y) ∈ R ∩ S ∧ (y, z) ∈ R ∩ S

⇒ (x, y) ∈ R ∧ (x, y) ∈ S ∧ (y, z) ∈ R ∧ (y, z) ∈ S
⇒ xRy ∧ xSy ∧ yRz ∧ ySz
⇒ (xRy ∧ yRz) ∧ (xSy ∧ ySz)
⇒ xRz ∧ xSz
⇒ (x, z) ∈ R ∧ (x, z) ∈ S
⇒ (x, z) ∈ R ∩ S
⇒ x(R ∩ S)z

3.5. Ejercicios Propuestos

1. Si X = {0, −1, 3}, Y = {0, 4, 5, 7, 9}, Z = {0, −6, 7, 1} y R, S son
relaciones de X en Y y de Y en Z respectivamente, dadas por:

xRy ⇔ x2 + y es par ySz ⇔ y − z < 2

Encuentre:
a) R, S, R−1 , S −1 .
b) El dominio y rango de cada una de las relaciones de la parte anterior.
c) La representación matricial y sagital de R, S, R−1 , S −1 .
d) S ◦ R, (S ◦ R)−1 , R−1 ◦ S −1 .

2. Si X = {0, 1, 2, 3, 4}, Y = {0, 4, 5, 7, 8}, Z = {0, 6, 7, 8, −9} y R, S son

relaciones de X en Y y de Y en Z respectivamente, dadas por:

x
xRy ⇔ + y es par ySz ⇔ 2z + y < 7
2

Encuentre:

73
 a) R, S, R−1 , S −1 .
b) El dominio y rango de cada una de las relaciones de la parte anterior.
c) La representación matricial y sagital de R, S, R−1 , S −1 .
d) S ◦ R, (S ◦ R)−1 , R−1 ◦ S −1 .

3. Si X = {0, −1, 2, 3}, Y = {0, 4, 7}, Z = {0, −2, 7, 8} y R, S son rela-

ciones de X en Y y de Y en Z respectivamente, dadas por:

y
xRy ⇔ x − es impar ySz ⇔ 3y − z < 7
2

Encuentre:

a) R, S, R−1 , S −1 .
b) El dominio y rango de cada una de las relaciones de la parte anterior.
c) La representación matricial y sagital de R, S, R−1 , S −1 .
d) S ◦ R, (S ◦ R)−1 , R−1 ◦ S −1 .

4. Si R y S son relaciones de X en Y, probar que:

S S
a) dom(R S) = dom(R) dom(S)
S S
b) rang(R S) = rang(R) rang(S)
T T
c) dom(R S) ⊂ dom(R) dom(S)
d ) (R ∪ S)−1 = R−1 ∪ S −1
e) (R ∩ S)−1 = R−1 ∩ S −1
f ) (R − S)−1 = R−1 − S −1

5. Para cada una de las siguientes relaciones en Z. Cuáles son reflexivas,

simétricas, antisimétricas y/o transitivas:

a) xR1 y ⇔ x + y < 3
b) xR2 y ⇔ y = 0
c) xR3 y ⇔ x + y = 3
d ) xR4 y ⇔ x < y

74
 e) xR5 y ⇔ x2 = y
f ) xR6 y ⇔ x − y es par
g) xR7 y ⇔ 2x = y

6. Dibuje una relación en el conjunto X = {a, b, c} tal que:

a) Sea reflexiva, simétrica y que no sea transitiva.

b) No sea reflexiva, que sea antisimétrica, que no sea simétrica y que
sea transitiva.
c) Sea reflexiva, transitiva, que no sea antisimétrica y no sea simétri-
ca.

7. Si X = {0, −1, 2, 3, 4} y R es la relación en X dada por:

R = {(0, 0), (−1, 2), (4, 4), (−1, −1), (2, −1), (3, 2), (2, 3), (2, 2)}

Determine si R es reflexiva, simétrica, antisimétrica o transitiva.

8. Si X = {0, −1, 2, 3, 4} y R es la relación en X dada por:

R = {(0, 0), (−1, 2), (4, 4), (−1, −1), (3, 3), (3, −1), (−1, 3), (2, −1), (3, 2), (2, 3), (2, 2)}

Determine si R es reflexiva, simétrica, antisimétrica o transitiva.

9. Si X = {0, −1, 2, −3, a} y R es la relación en X dada por:

R = {(0, 0), (−1, 2), (a, a), (−1, −1), (a, −1), (2, −3), (a, 2), (−3, −3)}

Determine si R es reflexiva, simétrica, antisimétrica o transitiva.

10. Probar que la relación en R2 dada por:

(a, b) ∼ (c, d) ⇔ b − a = d − c

es una relacion de equivalencia.

11. Probar que la relación en R dada por:

a ∼ b ⇔ (a − b) ∈ Z

es una relacion de equivalencia.

75
 12. Si X = {0, 1, 2, 3, 4, 5, 6}. Probar que la relación en X dada por:

a ∼ b ⇔ 7 divide a (a2 − b2 )

es una relacion de equivalencia y encuentre el conjunto cociente de X

por ∼.

13. Demuestre que la relación R = {(1, 1), (1, 2), (2, 1), (3, 3), (3, a), (2, 2),
(a, a), (a, 3), (−7, −7), (4, 4), (−7, 3), (−7, a), (a, −7), (3, −7), (7, 7)}
es una relación de equivalencia en X = {a, −7, 1, 2, 3, 4, 7}, y encuentre
el conjunto cociente de X por R.

14. Probar que la relación en R2 dada por:

(a, b) ∼ (c, d) ⇔ a + b = c + d

es una relación de equivalencia.

15. En X = {2, 3, 5, 8, 10, 12, 15, 16, 20} la relación:

n ≺ m ⇔ n divide a m

es una relación de orden. Encuentre X y dibuje el respectivo diagrama

de Hasse.

16. En X = {1, 2, 3, 7, 8, 9, 12, 14, 16, 42} la relación:

n ≺ m ⇔ n divide a m

es una relación de orden. Encuentre X y dibuje el respectivo diagrama

de Hasse.

3.6. Referencias Bibliográficas

1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

76
3. Ramos, Dennis. Estructuras Discretas.

4. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

5. Sáenz, Jorge; y otros. Fundamentos de la matemática. Hipotenusa. Se-

gunda edición, Barquisimeto, 2001.

77
Capı́tulo 4

FUNCIONES

Como ya se ha mencionado el concepto de función es uno de los conceptos

más importantes en la matemática, en este capı́tulo veremos la definición for-
mal de función como una relación que satisface ciertas condiciones, veremos
las definiciones de función: inyectiva, sobreyectiva y biyectiva (invertible).

4.1. Funciones
Definición 4.1.1 Sean X, Y conjuntos. Una función de X en Y es una
trı́ada (f, X, Y ), donde f es una relación de X en Y que satisface las sigu-
ientes condiciones:

1. dom(f ) = X

2. xf y ∧ xf z ⇒ y = z
f
En tal caso se acostumbra escribir f : X → Y o X Y en lugar de
→
(f, X, Y ).

Si xf y se suele escribir y = f (x), en este caso se dice que y es la imagen

de x mediante f y que x es preimagen de y.

78
La primera condición nos dice que cada elemento de X tiene una imagen en
una función. La segunda condición nos dice que la imagen de un elemento en
una función es única. f y g no son funciones, f viola la segunda condición, g
viola la primera.

79
Observación 4.1.1 En el conjunto de llegada de una función pueden existir
elementos que no tengan preimagen. Además pueden existir elementos con
más de una imagen. Por ejemplo f dada a continuación es función.

Ejemplo 4.1.1 Sean X = {1, 2, 3, 4, 5} y Y = {1, a, −1, 0}. Las siguientes

relaciones de X en Y son funciones.
1. R = {(1, 1), (2, a), (3, a), (4, 1), (5, 1)}
2. S = {(1, 1), (2, 1), (3, 1), (4, a), (5, −1)}
Esta claro que dom(R) = dom(S) = X. Por otro lado
rang(R) = {1, a}, rang(S) = {1, a, −1}

80
Las siguientes relaciones de X en Y no son funciones.
1. {(1, 1), (2, 1), (1, a), (3, a), (4, −1), (5, −1)}
2. {(1, −1), (2, 0), (4, 0), (5, 1)}
La primera no es función porque 1 tiene dos imagenes. La segunda no lo es
porque su dominio no es todo X.
Teorema 4.1.1 Sean f : X → Y , g : X → Y dos funciones. Entonces:
f = g ⇔ f (x) = g(x), ∀x ∈ X
Ejemplo 4.1.2 Sea X un conjunto arbitrario.
Entonces IX : X → X dada por f (x) = x para todo x en X, es una función,
llamada función identidad , cuyo rango niene dado por: rang(IX ) = X
(esta es la misma relación identidad del capitulo anterior).
Ejemplo 4.1.3 Sean X, Y conjuntos cualesquiera y sea c ∈ Y un elemento
fijo. Entonces, f : X → Y dada por f (x) = c, para todo x en X es una
función , llamada función constante. En este caso rang(f ) = {c}.
Ejemplo 4.1.4 Sea X un conjunto y sea A subconjunto de X. Se llama
función inclusión de A en X a la función, denotada por iA , dada por:
iA : A → X; iA (x) = x, ∀x ∈ A
En este caso rang(iA ) = A.
Ejemplo 4.1.5 Sean X, Y, Z conjuntos. Una función f : XxY → Z es lla-
mada función de dos variables.

Por ejemplo, f : RxR → R, dada por:

f (x, y) = x + 2y es una función de dos variables.

f (1, 1) 1+2·1=3
=
f (2, 0) 2+2·0=2
=
f (1, 3) 1+2·3=7
=
f (3, 1) 3+2·1=5
=
2 1 2 5
f (2/3, 1/2) = +2 = +1=
3 2 3 3
81
Para evaluar una función en un punto (de dos coordenadas es este caso),
debemos recordar que el dominio de f esta formado por conjuntos ordenados,
ası́ que no es necesariamente igual f (1, 3) a f (3, 1).

Ejemplo 4.1.6 Sea X un conjunto y sea A subconjunto de X. Se llama

función caracteristica de A, denotada por 1A , a la función 1A A → R,
dada por: 
1, x∈A
1A (x) =
0, si x ∈
/A
Si A = X, rang(1A ) = {1}. Si A 6= X, entonces rang(1A ) = {0, 1}.

Definición 4.1.2 Una función cuyo conjunto de llegada es R se llama fun-

ción real, por otro lado si tanto el dominio como el conjunto de llegada de
una función es R,a la función se le llama función real de variable real.

Definición 4.1.3 Sea f : X → Y una función y sea A subconjunto de X.

Se llama restricción de f al conjunto A a la función denotada por f /A,
dada por:
f /A : A → Y ; (f /A)(x) = f (x), ∀x ∈ A
Por otro lado si f : X → Y es una función y X es subconjunto de Z y
además g : Z → Y es una función tal que f = g/X, diremos entonces que g
es una extensión de f .

Ejemplo 4.1.7 Sea f : R − {0} → R, la función definida por

1
f (x) =
x
Las funciones g : (0, +∞) → R y h : (−∞, 0) → R dadas respectivamente
por:
1 1
g(x) = y h(x) = son restricciones de f (por otro lado podemos decir
x x
que f es una extensión de g ó de h). Ahora una extensión de f puede ser
i : R → R dada por: ( 1
, x 6= 0
i(x) = x
0, x=0

82
Definición 4.1.4 Sea f : X → Y una función. Diremos que f es inyectiva
si se cumple que:
f (x) = f (y) ⇒ x = y
o de manera equivalente, que:

x 6= y ⇒ f (x) 6= f (y)

Es decir una función es inyectiva si cada elemento de Y tiene a lo más (puede

no tener) sólo una preimagen.

Ejemplo 4.1.8 Sean X = {1, 2, 3, 4} y Y = {1, a, −1, 4}. Consideremos las

siguientes funciones X en Y .

1. R = {(1, 1), (2, a), (3, 4), (4, −1)}

2. S = {(1, 1), (2, 1), (3, 1), (4, a)}

La primera función es inyectiva, pero la segunda no (1 tiene tres preima-

genes).

Ejemplo 4.1.9 Sea g : R → R la función dada por:

g(x) = x2

Esta función no es inyectiva. Porque f (2) = f (−2) = 4, es decir 4 tiene dos

preimagenes.
Pero notemos que h : [0, +∞) → R dada por:

h(x) = x2

si es inyectiva, ya que:

h(x) = h(y) ⇒ x2 = y 2
√ p
⇒ x2 = y 2
⇒ | x |=| y |
⇒ x=y (x, y ≥ 0)

83
Definición 4.1.5 Sea f : X → Y una función. Diremos que f es sobreyec-
tiva si
(∀y ∈ Y )(∃x ∈ X)(f (x) = y)
Esto es equivalente a decir que rang(f ) = Y , es decir que todo elemento de
Y tiene preimagen.

Ejemplo 4.1.10 Sean X = {1, 2, 3, 4} y Y = {1, a, −1, 4}. Consideremos

las siguientes funciones X en Y .
1. R = {(1, 1), (2, a), (3, 4), (4, −1)}
2. S = {(1, 1), (2, 1), (3, 1), (4, a)}
La primera función es sobreyectiva, pero la segunda no (-1 y 4 no tienen
preimagenes).

Ejemplo 4.1.11 Sea g : R → R la función dada por:

g(x) = x2

Esta función no es sobreyectiva. Porque −1 no tiene preimagen ( no existe

número real x tal que x2 = −1).
Pero notemos que i : R → [0, +∞) dada por:

g(x) = x2

si es sobreyectiva.

g(x) = y ⇒ x2 = y
√ √
⇒ x2 = y (y ≥ 0)
√
⇒ | x |= y
√ √
⇒ x= y∨x=− y

√
Si x = y
√
g(x) = g( y)
√ 2
= y
= y

84
Definición 4.1.6 Una función es biyectiva si es inyectiva y sobreyectiva.

Por ejemplo la función R antes estudiada es biyectiva. Por otro lado las
funciones S, h, i anteriores no son biyectivas. Aunque h es inyectiva no es
sobreyectiva. i es sobreyectiva pero no es inyectiva. Ahora j : [0, +∞) →
[0, +∞) dada por:
j(x) = x2
si es biyectiva (dejamos la justificación de esto al lector).

Definición 4.1.7 Una función f : X → Y es invertible si su relación

inversa es una función. En tal caso diremos que f −1 es la inversa de f .

Teorema 4.1.2 Si f : X → Y es invertible. Entonces:

y = f (x) ⇔ x = f −1 (y)

Ejemplo 4.1.12 Sean X = {1, 2, 3, 4} y Y = {1, a, −1, 4}. Consideremos

las funciones de X en Y , R y S definidas anteriormente.

1. R = {(1, 1), (2, a), (3, 4), (4, −1)}

2. S = {(1, 1), (2, 1), (3, 1), (4, a)}

1. R−1 = {(1, 1), (a, 2), (4, 3), (−1, 4)}

2. S −1 = {(1, 1), (1, 2), (1, 3), (a, 4)}

R−1 es función, en cambio S −1 no lo es porque su dominio no es todo Y ,

además el 1 tiene tres imagenes.

Teorema 4.1.3 Una función f : X → Y es invertible si y sólo si es biyec-

tiva.

Ejemplo 4.1.13 La función j antes estudiada es invertible, para encontrar

la inversa en estos casos, se ve el despeje de la x cuando se verifica que la
función es sobreyectiva (el cual en estos casos es único) y de allı́ se obtiene
la inversa. Se puede probar que la inversa de i (dejamos los detalles como
ejercicio), viene dada como:
√
i−1 : [0, +∞) → [0, +∞), i−1 (x) = x

85
Las funciones g, h, i no son invertibles.
Teorema 4.1.4 Si f : X → Y , g : Y → Z son funciones, entonces la
relación compuesta g ◦ f : X → Z es también función. En este caso

(g ◦ f )(x) = g(f (x))

Ejemplo 4.1.14 Sean f, g, h : R → R (funciones) dadas respectivamente

por:
1
f (x) = 2x, g(x) = 2
x +1
Encontremos f ◦ f , g ◦ f .

(f ◦ f )(x) = f (f (x))
= f (2x)
= 2(2x)
= 4x

(g ◦ f )(x) = g(f (x))

= g(2x)
1
=
(2x)2 + 1
1
= 2
4x + 1
Teorema 4.1.5 Sea f : X → Y una función. Entonces,
f es invertible si y sólo si existe g : Y → X tal que f ◦ g = IY y g ◦ f = IX
En este caso g = f −1 .

4.2. Ejercicios Resueltos

1. Sea f : R → R la función dada por:

f (x) = −2x + 3

Demuestre que esta función es inyectiva.

86
 Demostración:
f (x) = f (y) ⇒ −2x + 3 = −2y + 3
⇒ −2x = −2y
⇒ x=y

2. Sea f : R → R la función dada por:

f (x) = −2x + 3
Demuestre que esta función es sobreyectiva.

Demostración:

Sea y ∈ Y . Debemos encontrar x ∈ X tal que f (x) = y. Para buscar

tal x se suele despejar x es la ecuación f (x) = y.
y = f (x) ⇒ y = −2x + 3
⇒ y − 3 = −2x
y−3
⇒ =x
−2
Comprobemos que este x funciona (se pueden encontrar varios x en
este paso, pero sólo es suficiente con encontrar uno).
y−3
f (x) = f ( )
−2
y−3
= −2( )+3
−2
= (y − 3) + 3
= y

3. La función f anterior es invertible, al demostrar que f era sobreyectiva

encontramos:
y−3
x=
−2
−1
Ası́ que f : R → R viene dada por:
x−3
f −1 (x) =
−2

87
 4. Sean f, g, h : R → R (funciones) dadas respectivamente por:
1
f (x) = 2x, g(x) = −x + 1, h(x) =
x2 +1
Encuentre h ◦ g ◦ f

(h ◦ g ◦ f )(x) = h((g ◦ f )(x))

= h(g(f (x)))
= h(g(2x))
= h(−2x + 1)
1
=
(−2x + 1)2 + 1
1
= 2
4x − 4x + 1 + 1
1
= 2
4x − 4x + 2

4.3. Ejercicios Propuestos

1. ¿ Cuáles de las siguientes relaciones de X = {1, 2, 3, 4} en Y = {2, b, −3, 5}
son funciones ?

a) R = {(1, 2), (1, b), (2, −3), (3, −3), (4, b)}
b) S = {(1, 2), (2, 2), (3, 2), (4, 2)}
c) T = {(1, 2), (3, 2), (4, 5)}
d ) U = {(3, 2), (4, b), (2, −3), (1, b)}

2. Para cada una de las siguientes funciones, diga cuáles son inyectivas,
sobreyectivas, biyectivas. Para aquellas que sean invertibles diga cuál
es su inversa.

a) f1 : R → R, dada por f1 (x) = −3x + 5.

4x − 7
b) f2 : R → R, dada por f2 (x) = .
2
c) f3 : R − {0} → R, dada por f3 (x) = 1/x.

88
 −6
d ) f4 : R − {1} → R − {0}, dada por f4 (x) = .
x−1
√
e) f5 : [0, +∞) → [0, +∞), f5 (x) = x + 1.

3. Sean f : X → Y, g : Y → Z funciones. Probar que:

a) Si f y g son inyectivas, entonces g ◦ f es inyectiva.

b) Si f y g son sobreyectivas, entonces g ◦ f es sobreyectiva.
c) Si f y g son invertibles, entonces g ◦ f es invertible.
d ) Si g ◦ f es inyectiva, entonces f es inyectiva.
e) Si g ◦ f es sobreyectiva, entonces g es sobreyectiva.

4. Sean f, g : R → R, h : [−3, +∞) → R, i : R − {0} dadas por:

√ 1
f (x) = 2x + 4, g(x) = x2 − 2, h(x) = x + 3, i(x) = + 2
x

Encuentre:
−1 4 −3
a) f ( ), f ( ), g(−4), g(11), h(−2), i( )
7 5 4
b) f ◦ g
c) f ◦ f
d) g ◦ h
e) f ◦ i
f) g◦f ◦h

5. Sean f, g : R → R dadas por:

f (x) = 2x2 + 4x − 1 g(x) = 3 − 4x

Encuentre:

a) f ◦ g
b) f ◦ f
c) g ◦ f

89
 d) g ◦ g ◦ g

6. Sea f : RxR → R, definida como:

p
f (x, y) = x2 + 3y 4 − 5x + 3

Encuentre:

a) f (0, 0)
b) f (1, 5)
c) f (−3, 4)
1 −3
d) f( , )
2 4
7. Sea g : R2 → R, definida como:

g(x, y) = −2x3 + 3y 4 − 5x + 3yx − 4

Encuentre:

a) g(0, 0)
b) g(−1, 4)
c) g(−2, 5)
2 −1
d ) g( , )
3 4
8. Sea f : R3 → R, definida como:
p
h(x, y, z) = x2 + y 2 + z 2 − 2xyz + 1

Encuentre:

a) h(0, 0, 0)
b) h(1, 5, 0)
c) h(1, −3, 4)
−1 −3
d ) h( , , 1)
3 5

90
4.4. Referencias Bibliográficas
1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

3. Ramos, Dennis. Estructuras Discretas.

4. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

5. Sáenz, Jorge; y otros. Fundamentos de la matemática. Hipotenusa. Se-

gunda edición, Barquisimeto, 2001.

91
Capı́tulo 5

ÁLGEBRAS DE BOOLE

En este tema veremos una introducción a las Álgebras de Boole. Posterior

a la definición, veremos ejemplos, teoremas hasta llegar a los polinomios
booleanos, circuitos y forma normal disyuntivas. El lector podrá observar
similitudes con esta teorı́a y la del cálculo proposicional.

5.1. Álgebras de Boole

Definición 5.1.1 Un Álgebra de Boole es una sextupla (B, +, ·,0 , 0, 1),
donde B es un conjunto, 0(llamado elemento cero) y 1 (llamado elemento
identidad) son elementos distintos de B, +, · son operaciones binarias

+ : BxB → B

(a, b) → a + b (suma de a y b)

· : BxB → B

(a, b) → a · b (producto de a y b)
0
es una operación unitaria
0
:B→B

a → a0 ( a a0 se le llama complemento de a)

tales que para todo a, b ∈ B se cumplen los siguientes axiomas:

B1) a + b = b + a, a · b = b · a (leyes conmutativas)

92
B2) a + 0 = a, a · 1 = a (leyes de identidad)

B3) a · (b + c) = (a · b) + (a · c), a + (b · c) = (a + b) · (a + c) (leyes distributivas)

B4) a + a0 = 1, a · a0 = 0 (leyes de complementación)

Observación 5.1.1 1. En un Álgebra de Boole (B, +, ·,0 , 0, 1), cuando se

sobreentienden quienes son +, ·,0 , 0, 1, se suele decir por comodidad el
Álgebra de Boole B.

2. Debe quedar claro que en un Álgebra de Boole (B, +, ·,0 , 0, 1), 0 y 1 son
simbolos, no debe creerse que necesariamente los ’números’ 0, 1 están
en B, sino que en B existen dos elementos que se simbolizan por 0, 1
que cumplen con los axiomas B2, B4 anteriores.

3. El 0 es el único elemento que cumple con los axiomas B2 y B4, igual-

mente 1.

4. Para cada a existe sólo un a0 que cumple con B4.

Ejemplo 5.1.1 Sea B un conjunto de proposiciones tales que si p, q ∈ B,

entonces p ∧ q, p ∨ q, ∼ p, ∼ q ∈ B. Entonces (B, ∨, ∧, ∼, F, V ) es un Álgebra
de Boole.

∨ = +, ∧ = ·, ∼=0 , 0 = F (una contradicción), 1 = V (una tautologı́a).

Sabemos que B satisface los axiomas B1, B2, B3, B4 por la teorı́a del capitulo
1.

Observación 5.1.2 Las leyes del álgebra proposicional se dan en términos

de la relación de equivalencia lógica y no en términos de la relación de igual-
dad, como se exigen el los axiomas B1, B2, B3, B4. Este problema se resuelve
tomando en lugar de B, el conjunto cociente de B por la relación (de equiv-
alencia) equivalencia lógica.
S T
Ejemplo 5.1.2 Sea U un conjunto no vacı́o. (P(U ), , , {, ∅, U ) es un
Álgebra de Boole.

= ·, { =0 , 0 = ∅, 1 = U . Sabemos que P(U )

S T
P(U ) = B, = +,
satisface los axiomas B1, B2, B3, B4 por la teorı́a del capitulo 2.

93
Ejemplo 5.1.3 Sea B un conjunto con sólo dos elementos, digamos B =
{a, b}. Definamos las operaciones +, ·,0 como sigue:

a + a = a, b + b = b, a + b = b + a = b

a · a = a, b · b = b, a · b = b · a = a
a0 = b, b0 = a
Entonces (B, +, ·,0 , a, b) es un Álgebra de Boole, llamada Álgebra de Boole
de todo o nada.
S T
Si U = {x} (un conjunto con sólo un elemento), entonces (P(U ), , , {, ∅, U )
es un Álgebra de Boole de todo o nada.

De igual manera si B = {F, V } (contradicción, tautologı́a), entonces

(B, ∨, ∧, ∼, F, V ) es un Álgebra de Boole de todo o nada también.

Teorema 5.1.1 Sea (B, +, ·,0 , 0, 1) un Álgebra de Boole.

1. a + b = 1 ∧ a · b = 0 ⇒ b = a0 (unicidad del complemento)

2. (a0 )0 = a (ley de involución)

3. b · a = c · a ∧ b · a0 = c · a0 ⇒ b = c

Definición 5.1.2 Sea (B, +, ·,0 , 0, 1) un Álgebra de Boole. El dual de un

enunciado en esta Álgebra de Boole, es el enunciado que se obtiene inter-
cambiando + con · y 0 con 1 en el enunciado original.

Ejemplo 5.1.4 1. El dual de a + 1 = 1 es a · 0 = 0

2. El dual de a · (b + c) = (a · b) + (a · c) es a + (b · c) = (a + b) · (a + c)

3. El dual de a + a0 = 1 es a · a0 = 0

Teorema 5.1.2 (Principio de dualidad)

En un Álgebra de Boole, el dual de un teorema es un teorema.

Veamos la importancia de este teorema.

Teorema 5.1.3 Sea (B, +, ·,0 , 0, 1) un Álgebra de Boole. Entonces para todo
a, b, c ∈ B se cumple que:

94
 1. a + a = a, a · a = a (leyes de idempotencia)

2. a + 1 = 1, a · 0 = 0 (leyes de identidad)

3. 10 = 0, 00 = 1 (leyes de complementación)

4. a · (a + b) = a, a + (a · b) = a (leyes de absorción)

5. a + (b + c) = (a + b) + c, a · (b · c) = (a · b) · c (leyes asociativas)

6. (a + b)0 = a0 · b0 , (a · b)0 = a0 + b0 (leyes de De Morgan)

Según el principio de dualidad si se demuestran, cada propiedad de la izquier-
da, se tiene automaticamente la propiedad de la derecha (o viceversa). De-
mostraremos 1, 3 y dejamos el resto como ejercicio al lector (5 la demostraremos
en el ejercicio resuelto 1).
Demostración:

1)

a = a+0 (B2)
0
= a + (a · a ) (B4)
0
= (a + a) · (a + a ) (B3)
= (a + a) · 1 (B4)
= a+a (B2)

3)

0 = 1 · 10 (B4)
= 10 · 1 (B1)
= 10 (B2)

Definición 5.1.3 Sea (B, +, ·,0 , 0, 1) un Álgebra de Boole. Definimos la relación

≺ en B, como sigue
a≺b⇔a·b=a

95
Esta es una relación de orden. Dejamos la prueba de esto como ejercicio al
lector.

Observación 5.1.3 Un Álgebra de Boole finita tiene 2n elementos, donde

n es un entero positivo. S
TalTÁlgebra de Boole se puede identificar con un
Álgebra de Boole (P(U ), , , {, ∅, U ) donde U es cualquier conjunto finito
de n elementos.

5.2. Polinomios Booleanos y Circuitos Lógi-

cos
Definición 5.2.1 Sean x1 , ..., xn un conjunto de sı́mbolos, que llamaremos
variables booleanas. Un polinomio booleano en x1 , ..., xn es una ex-
presión formada con las constantes 0, 1 y las variables x1 , ..., xn usando las
operaciones booleanas +, ·,0 de acuerdo a las siguientes reglas:

1. 0, 1, x1 , ..., xn son polinomios booleanos.

2. Si P y Q son polinomios booleanos, entonces

P + Q, P · Q, Q0

son también polinomios booleanos.

Observación 5.2.1 Algunos autores no consideran a 0 y a 1 como poli-

nomios booleanos.

Ejemplo 5.2.1 Son polinomios booleanos en las variables x, y, z:

1. (x + y) · z

2. (x · y) + (x · (z 0 ))

3. [(x · y) · z 0 ] + (1 · x)0

Con el objeto de simplificar la notación eliminando algunos paréntesis, le

daremos a la operación de complementación prioridad sobre la multiplicación,
y a la multiplicación prioridad sobre la adición. De esta manera los ejemplos
anteriores se pueden escribir como:

96
 1. (x + y) · z

2. x · y + x · z 0

3. x · y · z 0 + (1 · x)0

Observación 5.2.2 Con el objeto se simplificar la notación, escribiremos

xy en lugar de x · y.

Definición 5.2.2 Dos polinomios booleanos P, Q con igual número de vari-

ables, son equivalentes o iguales, denotado como P = Q, si P se puede
transformar en Q mediante propiedades de Álgebra de Boole (o si Q se puede
transformar en P ).

Ejemplo 5.2.2 Demuestre que (x + z 0 )0 (y + x0 z) = x0 z

Demostración:

(x + z 0 )0 (y + x0 z) = (x0 z 00 )(y + x0 z) (DeM organ)

= (x0 z)(y + x0 z) (invol.)
= (x0 z)(x0 z + y) (conmut.)
= x0 z (absor.)


Un polinomio booleano puede ser considerado como una función. Por ejemplo
si B = {0, 1} es el Álgebra de Boole de boole de todo o nada y P es un
polinomio en las variables x1 , ..., xn , entonces se obtiene una función

P : Bn → B

al reemplazar cada variable por 0 ó 1.

Ejemplo 5.2.3 Si P = xy + x0 y 0 , se tiene

P : BxB → B

dada por:
P (1, 1) = 1 · 1 + 10 · 10 = 1 + 10 = 1 + 0 = 1
P (1, 0) = 1 · 0 + 10 · 00 = 0 + 0 · 1 = 0 + 0 = 0

97
P (0, 1) = 0 · 1 + 00 · 10 = 0 + 1 · 0 = 0 + 0 = 0
P (0, 0) = 0 · 0 + 00 · 00 = 0 + 00 = 0 + 1 = 1
Podemos resumir esto en una tabla (de verdad), como sigue:
x y P
1 1 1
1 0 0
0 1 0
0 0 1
Los polinomios booleanos, vistos como funciones, tienen interpretación en
el diseño de los llamados circuitos lógicos . Un circuito lógico se puede
pensar como una máquina que tiene uno o más dispositivos de entradas y un
dispositivo de salida. En cada instante, cada entrada acepta un bit (0 ó 1)
de información. Esta información es procesada por el circuito lógico para dar
un bit (0 ó 1).

Todo circuito lógico puede ser construido combinando unos pocos cir-
cuitos elementales, a los que llamaremos compuertas lógicas. Tres de estas
compuertas son las compuertas AND, OR y NOT.
Definición 5.2.3 Llamaremos compuerta AND a cualquier circuito lógi-
co de dos entradas, x, y, que da como salida el producto xy, es decir, esta
compuerta realiza el polinomio P (x, y) = xy. Su tabla de verdad es como
la de la conjunción. La compuerta AND se representa mediante el siguiente
sı́mbolo:

x y xy
1 1 1
1 0 0
0 1 0
0 0 0
Como un caso particular de esta compuerta tenemos un circuito de dos in-
terruptores conectados en serie.

98
Definición 5.2.4 Llamaremos compuerta OR a cualquier circuito lógico
de dos entradas, x, y, que da como salida la suma x + y, es decir, esta com-
puerta realiza el polinomio P (x, y) = x + y. Su tabla de verdad es como la de
la disyunción. La compuerta OR se representa mediante el siguiente sı́mbolo:

x y x+y
1 1 1
1 0 1
0 1 1
0 0 0
Como un caso particular de esta compuerta tenemos un circuito de dos in-
terruptores conectados en paralelo.

Definición 5.2.5 Llamaremos compuerta NOT a cualquier circuito lógi-

co de una entrada, x, que da como salida el complemento x0 , es decir, esta
compuerta realiza el polinomio P (x) = x0 . Su tabla de verdad es como la de
la negación. La compuerta NOT se representa mediante el siguiente sı́mbolo:

x x’
1 0
0 1
Como un caso particular de esta compuerta tenemos un circuito de dos in-
terruptores conectados en serie.

99
Cualquier polinomio booleano que no contenga 0 ni 1 se puede representar
por un circuito lógico compuesto de las compuertas AND, OR, y NOT. Lo
reciproco también se cumple.

Ejemplo 5.2.4 Diseñar el circuito lógico que realiza el polinimio booleano

P (x, y, z) = (xy)0 + x0 z

Solución:

Definición 5.2.6 Sean x1 , ..., xn variables booleanas. Un producto com-

pleto es un producto de la forma

b1 · ... · x
x bn

bi es xi ó x0i
donde cada x

Ejemplo 5.2.5 Considerando los polinomios en las variables x, y, z, son pro-

ductos completos:

1. xyz

2. x0 yz

3. x0 y 0 z

Ejemplo 5.2.6 Considerando los polinomios en las variables x, y, z, no son

productos completos:

1. yz

2. x0 zy

100
 3. xy

Definición 5.2.7 Un polinomio booleano P esta en forma normal disyun-

tiva si es 0 oúna suma de productos completos distintos.

Ejemplo 5.2.7 Considerando los polinomios en las variables x, y, z, estan

en forma normal disyuntiva:
1. xyz

2. x0 yz + xyz

3. x0 y 0 z + x0 yz + x0 y 0 z 0
no están en forma normal disyuntiva:
1. yz

2. x0 yz + xyz + x0 yz

3. xyz + zxy

Teorema 5.2.1 Todo polinomio booleano es equivalente a un único poli-

nomio que está en forma normal disyuntiva.

Ejemplo 5.2.8 Dado P (x, y) = xy+y+x0 . Encuentre el polinomio en forma

normal disyuntiva equivalente a P .

Solución:

P (x, y) = xy + y + x0
= xy + 1 · y + x0 · 1 (B2)
= xy + (x + x )y + x (y + y 0 )
0 0
(B4)
= xy + xy + x0 y + x0 y + x0 y 0 (B3)
= xy + x0 y + x0 y 0 (idemp.)

Por supuesto la unicidad es en términos de equivalencia, ya que los poli-

nomios.
P (x, y) = xy + x0 y + x0 y 0 , Q(x, y) = x0 y + x0 y 0 + xy
son ’iguales’.

101
5.3. Ejercicios Resueltos
1. Demuestre la ley asociativa a + (b + c) = (a + b) + c
Demostración: Sea x = a + (b + c), y sea y = (a + b) + c, debemos
probar que x = y

x·a = a·x (B1)

= a · (a + (b + c))
= a (parte4)

y·a = a·y (B1)

= a · ((a + b) + c)
= (a · (a + b)) + (a · c) (B3)
= a + (a · c) (parte4)
= a (parte4)

Entonces, x · a = y · a (i)

x · a0 = a0 · x (B1)
0
= a · (a + (b + c))
= (a0 · a) + (a0 · (b + c)) (B3)
0
= 0 + (a · (b + c)) (B4)
0
= a · (b + c) (B2)

y · a0 = a0 · y (B1)
0
= a · ((a + b) + c)
= ([a0 · (a + b)] + (a0 · c) (B3)
0 0 0
= [(a · a) + (a · b)] + (a · c) (B3)
0 0
= [0 + (a · b)] + (a · c) (B4)
0 0
= (a · b) + (a · c) (B2)
0
= a · (b + c) (B3)

Entonces, x · a0 = y · a0 (ii).

De (i), (ii) y del teorema 5.1.1 parte tres tenemos que x = y.

102
 2. Dado P (x, y, z) = xy + zx + x0 z + z. Encuentre el polinomio en forma
normal disyuntiva equivalente a P .
Solución:

P (x, y, z) = xy + zx + x0 z + z
= xy · 1 + xz + x0 · 1 · z + 1 · z (B2, conmut.)
0 0 0
= xy(z + z ) + x · 1 · z + x (y + y )z
+ (y + y 0 )z (B4, B2)
= xyz + xyz + x(y + y 0 )z + x0 (yz + y 0 z)
0

+ yz + y 0 z (B3, B4)
= xyz + xyz + x(yz + y 0 z) + x0 yz + x0 y 0 z
0

+ 1 · yz + 1 · y 0 z (B3, B4, B2)

= xyz + xyz + xyz + xy 0 z + x0 yz + x0 y 0 z
0

+ (x + x0 )yz + (x + x0 )y 0 z (B3, B4)

= xyz + xyz + xyz + xy z + x yz + x0 y 0 z
0 0 0

+ xyz + x0 yz + xy 0 z + x0 y 0 z (conmut., B3)

= xyz + xyz + xyz + xyz + xy z + xy 0 z
0 0

+ x0 yz + x0 yz + x0 y 0 z + x0 y 0 z (conmut.)
0 0 0 0 0
= xyz + xyz + xy z + x yz + x y z (idemp..)

5.4. Ejercicios Propuestos

1. Probar que:

a) (x0 + y 0 + xy)0 = 0
b) (x + z 0 )0 (y + x0 z) = x0 z
c) [(x + y 0 )z 0 + z(x + y 0 )]0 = x0 y
d ) xy + x0 y + xy 0 = x + y

2. Diseñar circuitos lógicos que realicen los polinomios booleanos sigu-

ientes:

103
 a) (xy 0 + x0 y)0
b) xy 0 + (xy)z 0
c) (x + yz)0 + y
d ) (x + (y + z 0 ))0 + (x0 y)0
e) (xy + yx0 )z + y 0 z

3. Hallar para los siguientes polinomios, el polinomio equivalente que

está en forma normal disyuntiva:

a) P (x, y) = (x + y 0 )x
b) P (x, y, z) = (x0 + z)0 + y
c) P (x, y) = ((xy)0 x0 )0
d ) P (x, y, z) = ((x + y 0 )z)0
e) P (x, y, z) = xyx + xyx0 + yz

5.5. Referencias Bibliográficas

1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

2. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

3. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

104
Capı́tulo 6

GRAFOS

En este (último) capı́tulo veremos una introducción a la teorı́a de Grafos,

comenzamos con la definición de grafos y los elementos de tal ası́ como
la definición de distintos tipos de grafos, luego haremos todo esto con los
dı́grafos (grafos dirigidos).

6.1. Grafos no Dirigidos

Definición 6.1.1 Un grafo (no dirigido) es una trı́ada de objetos G =
(V, A, f ), donde:

1. V es un conjunto, cuyos elementos se llaman vértices de G.

2. A es un conjunto, cuyos elementos se llaman aristas de G.

3. f es una función, llamada función de incidencia, que asigna a ca-

da arista x de A un par no ordenado de vértices {vi , vj } (no necesari-
amente distintos), llamados extremos de la arista x. En tal caso se
escribe
f (x) = {vi , vj }

105
 y se dice que la arista x incide en el vértice vi y en el vértice vj
Si vi = vj , se escribe f (x) = {vi } y decimos que x es un lazo.

Ejemplo 6.1.1 Graficar el grafo G = (V, A, G), donde

1. V = {v1 , v2 , v3 , v4 , v5 }

2. A = {a, b, c, d, e, f, g}

3. f viene dada por:

a) f (a) = {v1 , v3 }
b) f (b) = {v1 }
c) f (c) = {v4 , v3 }
d) f (d) = {v1 , v3 }
e) f (e) = {v5 , v2 }
f) f (f ) = {v2 , v4 }
g) f (g) = {v1 , v4 }

Solución:

106
Definición 6.1.2 Sea G = (V, A, f ) un grafo. Diremos que:

1. El número de incidencia de una arista aj en un vértice vi es:

a) 0, si la arista aj no incide en el vértice vi .

b) 1, si la arista aj incide en el vértice vi y no es un lazo.
c) 2, si la arista aj incide en el vértice vi y es un lazo.

2. Un vértice vi es adyacente a un vértice vj , si existe una arista que

tenga por extremos a vi y vj . Si vi es adyacente a vj , entonces vj es
adyacente a vi , por lo que es común decir en tal caso que vi y vj son
adyacentes.

3. El grado de un vértice vi , denotado por gr(vi ), es el número de aristas

de G que inciden en vi , en donde un lazo que incide en vi es contado dos
veces. Si un vértice tiene grado 0, decimos que el vértice es aislado.

4. Si V = {v1 , ..., vn }, la matriz de adyacencia de G, denotada por

MG , es la matriz
MG = [aij ]nxn
donde aij es igual al número de aristas que conectan vi y vj .

5. Si V = {v1 , ..., vn }, A = {a1 , ..., am }, la matriz de incidencia de G,

denotada por IG , es la matriz

IG = [bij ]nxm

donde bij es igual al número de incidencia de la arista aj en el vértice

vi .

6. Una cadena de G, denotada por (w0 , b1 , w1 , b2 , w2 , ..., bk , wk ), es una

sucesión alternada de vértices (wi ) y aristas (bj ) de G de la forma
antes escrita que comienza y términa con un vértice, tal que cumple las
siguientes condiciones:

a) Cada arista tiene por extremos el vértice que lo antecede y el

vértice que lo sigue.

107
 b) Las aristas (de la cadena) son todas distintas. Al número k de aris-
tas se le llama longitud de la cadena. A w0 se le llama vértice
inicial de la cadena y a wk se le llama vértice final de la cadena.
Una cadena también puede denotarse más simplemente mediante
la sucesión de sus vértices (w0 , w1 , w2 , ..., wk ), o la sucesión de sus
aristas (b1 , b2 , ..., bk ).

7. Una cadena simple es una cadena que tiene todos sus vértices dis-
tintos.

8. Un ciclo es una cadena que tiene al menos una arista tal que el vértice
inicial y el vértice final de la cadena son iguales (w0 = wk ). Si todos sus
vértices son distintos, excepto el inicial y el final, se dice que el ciclo
es simple.

9. vi es accesible desde vj , si existe una cadena que tiene a vi como

vértice inicial y a vj como vértice final. Si vi es accesible desde vj , en-
tonces vj es accesible desde vi , más aún esta es una relación de equiv-
alencia.

Ejemplo 6.1.2 Si G es el grafo del ejemplo anterior, entonces:

1. El número de incidencia de a en v1 y v3 es 1, mienstras que el número

de incidencia de a en v2 , v4 , v5 es 0. El número de incidencia de b en
v1 es 2.

2. Los vértices v1 y v3 son adyacentes, también lo son v5 y v2 . v1 y v2 no

son adyacentes.

3. gr(v1 ) = 5, gr(v2 ) = 2, gr(v3 ) = 3, gr(v4 ) = 3, gr(v5 ) = 1 (no hay

vértices aislados).

4.  
1 0 2 1 0

 0 0 0 1 1 

MG = 
 2 0 0 1 0 

 1 1 1 0 0 
0 1 0 0 0

108
 5. Tomaremos el orden de las aristas de forma natural a, b, c, d, e, f, g.
 
1 2 0 1 0 0 1
 0 0 0 0 1 1 0 
 
IG =  1 0 0 1 0 0 0 

 0 0 1 0 0 1 1 
0 0 1 0 1 0 0

6. Cadenas del grafo serı́an:

a) {v1 , a, v3 }.
b) {v1 , a, v3 , c, v4 , f, v2 , e, v5 }.
c) {v4 , c, v3 , d, v1 , g, v4 }.
d) {v3 , a, v1 , b, v1 , d, v3 }.

de longitudes 1,4,3,3 respectivamente. La primera y la segunda son ca-

denas simples. La tercera y cuarta son ciclos. La tercera es un ciclo
simple

7. De las cadenas anteriores concluimos que v1 es accesible desde v3 , que

v1 es accesible desde v5 . Se puede demostrar que cada vértice es accesible
a cualquier otro vértice.

Definición 6.1.3 Sea G = (V, A, f ) un grafo. Diremos que:

1. G es un grafo simple, si G no tiene lazos y cada par de vértices dis-

tintos están unidos a lo más por una arista.

2. G es un grafo completo, si es simple y todo par de vértices distintos

son adyacentes, si tal grafo tiene n vértices el grafo se denota por Kn .

3. G es regular de orden k, si cada vértice del grafo tiene orden k.

4. G es conexo, si cualquier vértice de G es accesible desde cualquier otro

vértice.

5. G es euleriano, si posee un ciclo euleriano.

6. G es un árbol, si es conexo y no tiene ciclos.

109
El grafo del ejemplo anterior no es simple (tiene un lazo, además no era
inyectiva porque hay dos aristas que unen v1 y v3 ), no es completo (v5 por
ejemplo no es adyacente a v1 ), no es regular (no todos los vértices tienen
igual grado), es conexo.
Ejemplo 6.1.3 El siguiente grafo es simple, conexo y regular de orden 2.

Ejemplo 6.1.4 Los siguientes grafos son conexos, simple, completos, y reg-
ulares de orden 0,1,2,3 respectivamente.

Ejemplo 6.1.5 El siguiente grafo no es conexo.

110
Dejamos como ejercicio al lector el identificar cuales de los grafos anteriores
son árboles.

Definición 6.1.4 Sean G = (V, A, f ) G0 = (V 0 , A0 , f 0 ) grafos. Diremos que

G0 es subgrafo de G si se cumple que:

1. V 0 ⊂ V .

2. A0 ⊂ A.

3. f 0 = f /A0 .

Ejemplo 6.1.6 Un subgrafo del ejemplo anterior serı́a G0 = (V 0 , A0 , f 0 ),

donde

1. V 0 = {v1 , v3 , v4 , v5 }

2. A0 = {a, b, c, d}

3. f 0 (a) = {v1 , v3 }, f 0 (b) = {v1 }, f 0 (c) = {v4 , v3 }, f (g) = {v1 , v4 }

G0 es subgrafo de G, otro subgrafo de G viene dado por:

111
Este grafo es un árbol, G0 no lo es.

Definición 6.1.5 Sea G = (V, A, f ) un grafo. Un árbol generador de G, es

un subgrafo de G que es conexo y tiene todos los vértices del grafo G.

Teorema 6.1.1 Sea G = (V, A, f ) un grafo. Entonces:

1. La suma de los grados de todos los vértices de G es igual al doble del
número de sus aristas.

2. Si G es conexo. G es euleriano si y sólo si todos los vértices tienen

grado par.

3. Si G es conexo. G tiene una cadena euleriana si y sólo si G tiene

exactamente dos vértices de grado impar (la cadena une los vértices de
grado impar).

Ejemplo 6.1.7 El grafo del ejemplo anterior tiene 7 aristas.

gr(v1 ) + gr(v2 ) + gr(v3 ) + gr(v4 ) + gr(v5 ) = 5 + 2 + 3 + 3 + 1

= 14

El grafo no es euleriano porque no todos tienen grado par, tampoco tiene

cadena euleriana porque hay 4 vértices con grado impar.

Teorema 6.1.2 Las siguientes proposiciones son equivalentes (es decir, si

una es verdadera, todas son verdaderas y si una es falsa, entonces todas son
falsas).

112
 1. G es un árbol.
2. G no tine ciclos y que tiene n vértices u n − 1 aristas.
3. Cualquier par de vértices de G pueden ser unidos por una única cadena
simple.
Teorema 6.1.3 Todo grafo conexo tiene uno o más árboles generadores.
En un grafo G = (V, A, f ) (conexo), a las aristas se las puede representar
por ’números’ (lo cual será llamada longitud de la arista) que representen
a cierta unidad de medida; por ejemplo, si G es el grafo cuyos vértices rep-
resentan las ciudades de un paı́s y las aristan representan las autopista que
unen las ciudades de tal paı́s, dichas aristas se pueden representar por medio
del número de kilometros que tiene. Teniendo esto presente nos preguntamos
¿ por qué autopistas se debe ir de una ciudad a otra de tal forma que se
llegue más rapido?, el resto de la sección aborda este asunto.
Definición 6.1.6 Sea G un grafo cuyas aristas poseen longitud, la longitud
se define como la suma de las longitudes de todas sus aristas.
Definición 6.1.7 Sea G un grafo conexo. Un árbol generador económi-
co de G o un árbol generador de G de longitud mı́nima, es un árbol
de longitud mı́nima de G.
PROCEDIMIENTO PARA CONSTRUIR UN ÁRBOL
GENERADOR ECONÓMICO DE UN GRAFO CONEXO G DE
n VÉRTICES
1. Se elige una arista que no sea un lazo, digamos a1 , que tenga la menor
longitud de las aristas de G. Sea G1 el grafo compuesto por la arsita a1
y sus dos vértices por arista.
2. Se construye un grafo G2 , agregando al grafo G1 una arista (distinta a
a1 obviamente), digamos a2 , que tenga la menor longitud de las aristas
de G junto con sus dos vértices, y de tal manera que el grafo G2 no
tenga un ciclo. Este grafo no es necesariamente conexo.
3. Se procede de manera similar al paso 2, hasta obtener un grafo Gn−1 ,
este grafo es un árbol generador económico de G.
Observación 6.1.1 Un grafo conexo puede tener distintos árboles gener-
adores económicos, pero estos tendrán la misma longitud.

113
6.2. Dı́grafos
Definición 6.2.1 Un dı́grafo (o grafo dirigido) es una trı́ada de objetos
G = (V, A, f ), donde:

1. V es un conjunto, cuyos elementos se llaman vértices de G.

2. A es un conjunto, cuyos elementos se llaman aristas (dirigidas) de G.

3. f es una función, llamada función de incidencia, que asigna a cada

arista x de A un par ordenado de vértices (vi , vj ) (no necesariamente
distintos). En tal caso se escribe

f (x) = (vi , vj )

El vértice vi se llama vértice inicial de la arista x y el vértice vj

vértice final de la arista x.

Si vi = vj , diremos que x es un lazo. Si f (y) = (vj , vi ), diremos que

las aristas x, y tienen direcciones opuestas.

Ejemplo 6.2.1 Graficar el dı́grafo G = (V, A, G), donde:

1. V = {v1 , v2 , v3 , v4 , v5 }

2. A = {a, b, c, d, e, f, g}

3. f viene dada por:

a) f (a) = (v1 , v3 )
b) f (b) = (v1 , v1 )
c) f (c) = (v4 , v3 )
d) f (d) = (v1 , v3 )
e) f (e) = (v5 , v2 )
f) f (f ) = (v2 , v4 )
g) f (g) = (v1 , v4 )

Solución:

114
Definición 6.2.2 Sea G = (V, A, f ) un grafo. Diremos que:
1. El grado positivo de un vértice vi , denotado por gr+ (vi ), es el número
de aristas de G que salen de vi . El grado negativo de un vértice vi ,
denotado por gr− (vi ), es el número de aristas de G que llegan a vi . El
grado total de un vértice vi , denotado por gr(vi ), es el número dado
por:
gr(vi ) = gr+ (vi ) + gr− (vi )

2. Si V = {v1 , ..., vn }, la matriz de adyacencia de G, denotada por

AG , es la matriz
AG = [aij ]nxn
donde aij es igual al número de aristas con vértice inicial vi y vértice
final vj .

3. Una cadena de G, denotada por (w0 , b1 , w1 , b2 , w2 , ..., bk , wk ), es una

sucesión alternada de vértices (wi ) y aristas (bj ) de G de la forma
antes escrita que comienza y términa con un vértice, tal que cumple las
siguientes condiciones:

a) Cada arista tiene por extremos el vértice que lo antecede y el

vértice que lo sigue.
b) Las aristas (de la cadena) son todas distintas. Al número k de aris-
tas se le llama longitud de la cadena. A w0 se le llama vértice
inicial de la cadena y a wk se le llama vértice final de la cadena.

115
 Una cadena también puede denotarse más simplemente mediante
la sucesión de sus vértices (w0 , w1 , w2 , ..., wk ), o la sucesión de sus
aristas (b1 , b2 , ..., bk ).

4. Una cadena simple es una cadena que tiene todos sus vértices dis-
tintos.

5. Un ciclo es una cadena que tiene al menos una arista, tal que el vértice
inicial y el vértice final de la cadena son iguales (w0 = wk ). Si todos sus
vértices son distintos, excepto el inicial y el final, se dice que el ciclo
es simple.

6. vi es accesible desde vj , si existe una cadena que tiene a vi como

vértice inicial y a vj como vértice final (Esta relación no es simétrica).

7. Una cadena euleriana es una cadena que pasa por todas las aristas.
Un ciclo euleriano es un ciclo que contiene a todas las aristas del
grafo.

Ejemplo 6.2.2 Si G es el dı́grafo del ejemplo anterior, entonces:

1. gr(v1 ) = gr+(v1 ) + gr− (v1 ) = 4 + 1 = 5

2. gr(v3 ) = gr+ (v3 ) + gr− (v3 ) = 0 + 3 = 3

3.  
1 0 2 1 0

 0 0 0 1 0 

AG = 
 0 0 0 0 0 

 0 0 1 0 0 
0 1 0 0 0

Definición 6.2.3 Sea G un dı́grafo.

1. Diremos que G es débilmente conexo si G considerado como grafo

(ignorando la dirección de sus aristas) es conexo.

2. Diremos que G es unilateralmente conexo si dados dos vértices

cualesquiera v, v 0 de G se cumple que: v es accesible desde v 0 , o que v 0
es accesible desde v.

116
 3. Diremos que G es fuertemente conexo si dados dos vértices cualesquiera
v, v 0 de G se cumple que v es accesible desde v 0 y que v 0 es accesible
desde v.

Teorema 6.2.1 Sea G es un dı́grafo.

1. Si G es fuertemente conexo, entonces G es unilateralmente conexo y

débilmente conexo.

2. Si G es unilateralmente conexo, entonces G es débilmente conexo.

6.3. Ejercicios Resueltos

1. Encuentre un árbol generador económico del grafo G dado por:

Solución: Apliquemos el algoritmo para obtener un árbol generador

económico.

117
 Otro árbol generador económico de G serı́a

2. El dı́grafo del ejemplo 6.2.1 es débilmente conexo, ya que su grafo

asociado es claramente conexo, no es unilateralmente conexo porque
no hay camino de v1 a v2 ni de v2 a v1 , y como no es unilateralmente
conexo tampoco será fuertemente conexo.

118
6.4. Ejercicios Propuestos
1. Dado el grafo G = (V, A, G), donde:

a) V = {v1 , v2 , v3 , v4 , v5 }
b) A = {a, b, c, d, e, f, g}
c) f viene dada por:
1) f (a) = {v1 , v3 }
2) f (b) = {v3 }
3) f (c) = {v4 , v3 }
4) f (d) = {v2 , v3 }
5) f (e) = {v5 , v2 }
6) f (f ) = {v2 , v1 }
7) f (g) = {v1 , v4 }
Dibuje el grafo.
Diga si es simple, conexo, regular, completo, o árbol.
Encuentre dos subgrafos distintos de G.
Encuentre la matriz de adyacencia y de incidencia del grafo,
ası́ como el grado de cada vértice.
Encuentre una cadena de longitud 5, y encuentre un ciclo
simple de longitud 3.
¿ Se puede encontrar una cadena euleriana en G ? De ser
ası́ encuentrela.
¿ Se puede encontrar una ciclo euleriano en G ? De ser ası́ en-
cuentrelo.

2. Dado el grafo G = (V, A, G), donde:

a) V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }
b) A = {a, b, c, d, e, f, g, h, i}
c) f viene dada por:
1) f (a) = {v1 , v3 }
2) f (b) = {v3 , v6 }
3) f (c) = {v4 , v3 }

119
 4) f (d) = {v2 , v6 }
5) f (e) = {v5 , v2 }
6) f (f ) = {v3 , v1 }
7) f (g) = {v1 , v4 }
8) f (h) = {v3 , v5 }
9) f (i) = {v2 , v4 }
Dibuje el grafo.
Diga si es simple, conexo, regular, completo, o árbol.
Encuentre dos subgrafos distintos de G.
Encuentre la matriz de adyacencia y de incidencia del grafo,
ası́ como el grado de cada vértice.
Encuentre una cadena de longitud 5, y encuentre un ciclo
simple de longitud 3.
¿ Se puede encontrar una cadena euleriana en G ? De ser
ası́ encuentrela.
¿ Se puede encontrar una ciclo euleriano en G ? De ser ası́ en-
cuentrelo.

3. Dado el grafo G = (V, A, G), donde:

a) V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }
b) A = {a, b, c, d, e, f, g, h, i}
c) f viene dada por:
1) f (a) = {v1 , v3 }
2) f (b) = {v3 , v6 }
3) f (c) = {v4 , v3 }
4) f (d) = {v2 , v5 }
5) f (e) = {v5 , v2 }
6) f (f ) = {v7 , v1 }
7) f (g) = {v1 , v4 }
8) f (h) = {v2 , v7 }
9) f (i) = {v6 , v4 }
Dibuje el grafo.

120
 Diga si es simple, conexo, regular, completo, o árbol.
Encuentre dos subgrafos distintos de G.
Encuentre la matriz de adyacencia y de incidencia del grafo,
ası́ como el grado de cada vértice.
Encuentre una cadena de longitud 5, y encuentre un ciclo
simple de longitud 3.
¿ Se puede encontrar una cadena euleriana en G ? De ser
ası́ encuentrela.
¿ Se puede encontrar una ciclo euleriano en G ? De ser ası́ en-
cuentrelo.

4. Dado el grafo G:

a) Encuentre la función de incidencia del grafo.

b) Diga si es simple, conexo, regular, completo, euleriano o árbol. Si
es conexo, encuentre un árbol generador económico de G. Si es
euleriano encuentre un ciclo euleriano en G.
c) Encuentre un subgrafo de G con 5 vértices y 5 aristas.
d ) Encuentre la matriz de adyacencia y de incidencia del grafo, ası́ co-
mo el grado de cada vértice.

121
5. Dado el grafo G:

a) Diga si es simple, conexo, regular, completo, euleriano o árbol. Si

es conexo, encuentre un árbol generador económico de G. Si es
euleriano encuentre un ciclo euleriano en G.
b) Encuentre un subgrafo de G con 5 vértices y 5 aristas.

6. Dada la matriz  
1 1 0 0 1 0 1
 0 0 1 1 0 0 0 
 
 1 1 0 1 0 1 0 
0 0 1 0 1 1 1
Encuentre el grafo que tiene a esta matriz como su matriz de incidencia.

7. Dada la matriz  
1 1 0 0 1 0 0
 1 0 0 1 1 0 1 
 
 0 1 0 1 0 1 0 
0 0 2 0 0 1 1
Encuentre el grafo que tiene a esta matriz como su matriz de incidencia.

8. Dada la matriz  
1 1 0 0
 1 0 1 2 
 
 0 1 0 3 
0 2 3 1
Encuentre el grafo que tiene a esta matriz como su matriz de adyacen-
cia.

122
 9. Dada la matriz  
1 1 0 0 1 0 0

 1 0 0 1 1 0 1 


 0 0 0 2 0 1 2 


 0 1 2 0 0 0 1 


 1 1 0 0 1 0 0 

 0 0 1 0 0 0 0 
0 1 2 1 0 0 1
Encuentre el grafo que tiene a esta matriz como su matriz de adyacen-
cia.

10. Dado el dı́grafo G = (V, A, G), donde:

a) V = {v1 , v2 , v3 , v4 , v5 }
b) A = {a, b, c, d, e, f, g}
c) f viene dada por:
1) f (a) = (v1 , v2 )
2) f (b) = (v3 , v4 )
3) f (c) = (v5 , v3 )
4) f (d) = (v1 , v1 )
5) f (e) = (v5 , v2 )
6) f (f ) = (v2 , v4 )
7) f (g) = (v4 , v1 )

Dibuje el dı́grafo.
Halle la matriz de adyacencia de G, ası́ como los grados positivos,
negativos, totales de sus vértices.
Encuentre un ciclo simple de longitud 3 y una cadena simple de
longitud 4 en el grafo.
Determine el (los) tipo(s) de conexidad del dı́grafo.

11. Dado el dı́grafo G = (V, A, G), donde:

a) V = {v1 , v2 , v3 , v4 , v5 , v6 , v7 }
b) A = {a, b, c, d, e, f, g, h, i, j, k}

123
 c) f viene dada por:
1) f (a) = (v1 , v2 )
2) f (b) = (v3 , v4 )
3) f (c) = (v5 , v3 )
4) f (d) = (v6 , v6 )
5) f (e) = (v5 , v2 )
6) f (f ) = (v2 , v7 )
7) f (g) = (v2 , v1 )
8) f (h) = (v6 , v7 )
9) f (i) = (v2 , v3 )
10) f (j) = (v4 , v7 )
11) f (k) = (v7 , v3 )

Dibuje el dı́grafo.
Halle la matriz de adyacencia de G, ası́ como los grados positivos,
negativos, totales de sus vértices.
Encuentre un ciclo simple de longitud 3 y una cadena simple de
longitud 4 en el grafo.
Determine el (los) tipo(s) de conexidad del dı́grafo.

12. Dado el dı́grafo:

124
 a) Encuentre la función de incidencia de G.
b) Halle la matriz de adyacencia de G, ası́ como los grados positivos,
negativos, totales de sus vértices.
c) Determine el (los) tipo(s) de conexidad del dı́grafo.

13. Dibuje el dı́grafo que tiene como función de adyacencia a la matriz

 
0 1 1 0 0
 0 0 1 0 1 
 
 0 0 0 0 1 
 
 0 0 0 0 1 
1 2 0 0 0

Determine además el (los) tipo(s) de conexidad del dı́grafo.

6.5. Referencias Bibliográficas

1. Gutiérrez, Ronald. Guı́a Didáctica de Estructuras Discretas. Barquisime-
to, 2011.

125
2. Ramos, Dennis. Estructuras Discretas.

3. Johnsonbaugh, Richard. Matemáticas Discretas. Prentice Hall. Cuarta

edición, 1997.

4. Sáenz, Jorge. Introducción a las Estructuras Discretas. Hipotenusa.

126