Tecnología Superior en Desarrollo de Software

MATEMÁTICA DISCRETA

GUÍA DE ESTUDIO

ESTUDIANTE:

DOCENTES: Lcda. Katty Lourdes Moncerrate Giler

PASAJE, JUNIO 2020

 Guía para el Estudiante

Contenido
OBJETIVO GENERAL .............................................................................................................................4
OBJETIVOS ESPECÍFICOS ......................................................................................................................4
1. Tema. Teoría de conjuntos y tipos de Números......................................................................4
1.1. Introducción a la Teoría de Conjuntos .................................................................................5
Actividades de aprendizaje: .......................................................................................................10
1.2. Determinación de Conjuntos. ............................................................................................11
Actividades de aprendizaje: .......................................................................................................12
1.3. Operaciones con Conjuntos. ..............................................................................................12
Actividades de aprendizaje: .......................................................................................................14
Actividades de aprendizaje: .......................................................................................................14
1.4. Sistema de Numeración (binario, Octal. Hexadecimal, Decimal) .......................................15
1.5. Conversión entre sistemas de numeración. .......................................................................19
1.6. Autoevaluación ..................................................................................................................20
2. Tema. Lógica proposicional...................................................................................................20
2.1. Lógica Matemática, operadores lógicos .............................................................................20
Actividades de aprendizaje: .......................................................................................................23
2.2. Tablas de verdad ................................................................................................................24
Actividades de aprendizaje: .......................................................................................................25
2.3. Inducción matemática .......................................................................................................25
Actividades de aprendizaje: .......................................................................................................26
2.4. Autoevaluación ..................................................................................................................26
3. Tema. Algebra Booleana, Números Reales y Funciones.......................................................26
3.1. Teorema del álgebra de Boole ...........................................................................................27
3.2. Representación de funciones lógicas. ................................................................................28
3.3. Compuertas lógicas ............................................................................................................29
Actividades de aprendizaje: .......................................................................................................31
3.4. Operaciones con números Naturales, Reales, Racionales y Enteros ..................................32
Actividades de aprendizaje: .......................................................................................................34
3.5. Funciones ...........................................................................................................................35
3.6. Tipos de funciones .............................................................................................................36
Actividades de aprendizaje: .......................................................................................................37
3.7. Tasa de cambio ..................................................................................................................38
Actividades de aprendizaje: .......................................................................................................39

ISTJOL | Página 2
 Guía para el Estudiante
4. Tema. Teoría de grafos y árboles ..........................................................................................40
4.1. Grafos, definiciones básicas ...............................................................................................40
Actividades de aprendizaje: .......................................................................................................42
Actividades de aprendizaje: .......................................................................................................43
4.2. Algoritmos de la ruta más corta .........................................................................................44
Actividades de aprendizaje: .......................................................................................................44
4.3. Redes de flujo en grafos .....................................................................................................46
Actividades de aprendizaje: .......................................................................................................47
4.4. Árboles, definiciones básicas .............................................................................................47
Actividades de aprendizaje: .......................................................................................................51
BIBLIOGRAFÍA BÁSICA Y COMPLEMENTARIA ....................................................................52

ISTJOL | Página 3
 Guía para el Estudiante

MATEMÁTICA DISCRETA
Al finalizar la asignatura, el estudiante estará en capacidad de:

OBJETIVO GENERAL

 Resolver problemas de Matemática Discreta con creatividad, mediante el pensamiento

lógico y reflexivo de forma autónoma, que permiten la resolución de importantes y
complejos algoritmos en el desarrollo de software.

OBJETIVOS ESPECÍFICOS

 Comprender el uso y manejo de las nociones básicas de matemática, de los sistemas de

numeración y códigos binarios, con criticidad mediante su conceptualización para la
representación de información en la carrera superior tecnológica.

 Usar con precisión los conectores lógicos, mediante la graficación para la representación
de las proposiciones compuesta, relacionándolas con lenguaje simbólico y expresarlo
en el lenguaje ordinario.

 Definir con claridad qué es álgebra Booleana, números reales y funciones, aplicando
correctamente la simbolización y graficación, para tener una mejor comprensión de los
procesos algebraicos.

 Resolver con criticidad problemas mediante la aplicación de la teoría de grafos y árboles

para que puedan aplicarlos en el ámbito de sus conocimientos, los mismos que les
ayudarán a descubrir nuevos temas relacionados en el campo tecnológico.

UNIDAD I

1. Tema. Teoría de conjuntos y tipos de Números.

Objetivo: Comprender el uso y manejo de las nociones básicas de matemática, de los sistemas
de numeración y códigos binarios, con criticidad mediante su conceptualización para la
representación de información en la carrera superior tecnológica.
Sistema de conocimientos Sistema de habilidades Sistema de valores
1.1 Conjuntos Define nociones básicas de Exactitud al desarrollar
1.2 Determinación de las matemáticas. nociones básicas de
Conjuntos. matemáticas.
1.3 Operaciones con Reconoce la clasificación de
Conjuntos los conjuntos.

ISTJOL | Página 4
 Guía para el Estudiante
1.4 Sistema de Numeración Efectúa operaciones con Criticidad en comprender el
(binario, Octal. conjuntos correctamente. uso y manejo del sistema de
Hexadecimal, Decimal) numeración y códigos.
1.5 Conversión entre Comprende el uso y manejo
sistemas de del sistema de numeración y Muestra paciencia, interés,
numeración. códigos. curiosidad y perseverancia
al efectuar operaciones de
Opera correctamente las
conjunto y de sistema de
conversiones del sistema de
numeración.
numeración.
Puntualidad para presentar
las tareas de los temas
tratados.

1.1.Introducción a la Teoría de Conjuntos

.
¿Qué es conjunto?
Conjunto es una colección, reunión o unión de objetos agrupados por alguna característica o
criterio que tienen en común

Subconjunto: son todos los elementos que están dentro de otro conjunto.
Ejemplos:
a) El conjunto de frutas rojas y el conjunto de frutas amarillas son subconjuntos del
conjunto de frutas

b) El conjunto de los seres vivos es muy grande

ISTJOL | Página 5
 Guía para el Estudiante

1.1.1. Conjuntos relevantes

Los conjuntos se pueden clasificar de acuerdo al número de elementos que puedan tener cada
uno de ellos, entre los cuales mencionamos los siguientes:

ISTJOL | Página 6
 Guía para el Estudiante

1.1.2. Conjunto Potencia

El conjunto potencia es aquel conjunto que contiene todos los elementos del conjunto A. Se
lo representa con el símbolo P(A).
Ejemplo:
a) Sea el conjunto S= {a, b, c}
2n=
23= 2*2*2= 8
P(S) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

b) Sea el conjunto A= {1,2,3,4,5}

2n=
25= 2*2*2*2*2= 32

ISTJOL | Página 7
 Guía para el Estudiante
P(A)= { {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4},
{2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, {5}, {1,5}, {2,5},
{1,2,5}, {3,5}, {1,3,5}, {2,3,5}, {1,2,3,5}, {4,5}, {1,4,5}, {2,4,5},
{1,2,4,5}, {3,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}}

1.1.3. Relación entre conjuntos

Relación es una correspondencia entre los elementos de dos conjuntos. Las relaciones entre
conjunto son las siguientes:

ISTJOL | Página 8
Guía para el Estudiante

ISTJOL | Página 9
 Guía para el Estudiante
Actividades de aprendizaje:

AA1. Represente gráficamente la clasificación de los conjuntos relevantes: (2 ptos. c/ítem)

1. Conjunto unitario

2. Conjunto finito

3. Conjunto infinito

4. Conjunto vacío

5. Conjunto unitario

AA2. Resuelva los siguientes ejercicios de conjunto Potencia. (2,5 ptos. c/u)

a) Sea el conjunto A= {w, x, y, z}

b) Sea el conjunto C= {a, e, i, o, u}
c) Sea el conjunto A= {coco, mora, cereza, uva}
d) Sea el conjunto K= {perro, gato, loro}

AA3. Indique en los siguientes ejercicios los tipos de relación que existen entre los conjuntos.
(5 ptos. c/u)

a) Dado el diagrama escribe el símbolo ∈; ∉; ⊂;

a……P
c……M
e……Q
h……M
Q……M
P…….M
M…....Q

ISTJOL | Página 10
 Guía para el Estudiante
b) Dado el diagrama escribe (V) si la notación es correcta y (F) si es falsa

1 ∈ A …..( ); B ⊂ A…….( ); 7 ∉ B………( )

5 ∈ B…...( ); 4 ∉ B……..( ); 2 ∉ C…….( )
3 ∉ A…..( ); C ⊂ A…….( ); 8 ∈ C………( )
6 ∈ B…...( ); 9 ∈ A……. ( ); 5 ∉ C……...( )

1.2.Determinación de Conjuntos.

La determinación de conjuntos nos permite diferenciarlos, cada uno de ellos es único.

Existen dos formas de determinar a los conjuntos:

ISTJOL | Página 11
 Guía para el Estudiante
Actividades de aprendizaje:
AA4: Definir por extensión y comprensión cada uno de los siguientes conjuntos (1. Pts. c/u)
a) A= {x /x son números impares menores que 15}
b) C= {x / x es un número natural mayor que 2 y menor que 8}
c) R= {x / x son múltiplos de 3 menores que 18}
d) Q= {x / x es una letra de la palabra calcular}
e) J= {x / x es una letra de la palabra CORRECTO}
f) A = {a, e, i, o, u}
g) M = {2, 4, 6, 8, 10}
h) L = {enero, febrero, marzo, abril, mayo, junio, julio, agosto, septiembre, octubre, …...}
i) B = {lunes, martes, miércoles, jueves, viernes, sábado, domingo}
j) Q = {DO, RE, MI, FA, SOL, LA, SI}

1.3.Operaciones con Conjuntos.

 Unión de conjuntos: es aquella operación que nos permite unir dos o más conjuntos
para formar uno nuevo, teniendo en cuenta que los elementos que se repiten se
escribirán una sola vez. Se representa con el símbolo “U”
Ejemplos:
a) A= {1,2,3,4,5,6,7,} y B= {8,9,10,11}
A∪B= {1,2,3,4,5,6,7,8,9,10,11}.

b)

 Intersección de conjuntos: esta operación se la realiza tomando en cuenta solo los

elementos que tienen en común dichos conjuntos A y B. Se representa con el símbolo
“∩”
Ejemplos:
a) A= {1,2,3,4,5} y B= {4,5,6,7,8,9}
A∩B= {1,2,3,4,5,6,7,8,9}.

b)

 Diferencia de conjuntos: es la operación que permite formar un nuevo conjunto, solo

con los elementos que pertenecen al primer conjunto, pero no al segundo. Es decir, son
todos los elementos del conjunto A sin tomar en cuenta los elementos de B. el símbolo
que se utiliza en esta operación es el mismo de la resta, se lo representa: “- “
Ejemplos:

ISTJOL | Página 12
 Guía para el Estudiante
a) A= {1,2,3,4,5} y B= {4,5,6,7,8,9}
A-B= {1,2,3},
B-A= {6,7,8,9}.

b)

 Diferencia simétrica de conjuntos: es aquella operación que permite formar un

nuevo conjunto con todos los elementos no comunes de dos conjuntos. Se lo representa
con el △.
Ejemplos:
a) A= {1,2,3,4,5} y B= {4,5,6,7,8,9},
A △ B= {1,2,3,6,7,8,9}

b)

Ejemplos:
a) A la entrada de la escuela, se les aplicó a 156 niños una encuesta respecto a sus
juguetes favoritos.
La encuesta arrojó los siguientes resultados:
 A 52 niños les gustaba el balón; a 63 les gustaban los carritos; a 87 les gustaban
los video juegos.
 Además, algunos de ellos coinciden en que les gustaba más de un juguete: 26 juegan
con el balón y carritos; 37 juegan con carritos y video juegos; 23 juegan con el
balón y los video juegos; por ultimo 7 expresaron su gusto por los tres.
a) ¿A cuántos niños les gusta otro juguete no mencionado en la encuesta?
b) ¿A cuántos niños les gusta solamente jugar con los video juegos?
c) ¿A cuántos niños les gusta solamente jugar con el balón?

ISTJOL | Página 13
 Guía para el Estudiante

a) ¿A cuántos niños les gusta otro juguete no mencionado en la encuesta?

156 – (10+16+7+19+7+30+34= 33
R= A 33 niños les gusta jugar con otros juguetes.

b) ¿A cuántos niños les gusta solamente jugar con los video juegos?
R= A 34 niños les gusta jugar con los videos juegos.

c) ¿A cuántos niños les gusta solamente jugar con el balón?

R= Solamente a 10 niños les gusta jugar con el balón.

Actividades de aprendizaje:
AA5: De acuerdo al siguiente diagrama representa las siguientes operaciones (1.5. Pts. c/u )

 M∪N
 N∩P
 P-N
 M△N
 N∪P
 N△P
 N-M

Actividades de aprendizaje:
AA6: Resolver los siguientes ejercicios de operaciones entre conjuntos (5. Pts. c/u)
a) Se encuesta a 150 familias consultando por el nivel educacional actual de sus hijos.
Los resultados obtenidos son:
 10 familias tienen hijos en Enseñanza Básica, Enseñanza Media y Universitaria.
 16 familias tienen hijos en Enseñanza Básica y Universitaria.
 30 familias tienen hijos en Enseñanza Media y Enseñanza Básica.

ISTJOL | Página 14
 Guía para el Estudiante
 22 familias tienen hijos en Enseñanza Media y Universitaria.
 72 familias tienen hijos en Enseñanza Media.
 71 familias tienen hijos en Enseñanza Básica.
 38 familias tienen hijos en Enseñanza Universitaria.
Con la información anterior, deducir:
a) El número de familias que solo tienen hijos universitarios.
b) El número de familias que tienen hijos solo en dos niveles.
c) El número de familias que tienen hijos que no estudian.

b) Una encuesta sobre 200 personas acerca del consumo de tres detergentes
 Albino, Blancura y Claridad- reveló los siguientes datos:
 126 personas consumían Claridad. ▪ 124 personas no consumían Albino.
 36 usuarios de detergente no consumían ni Albino ni Blancura.
 170 personas consumían por lo menos uno de los tres productos.
 60 personas consumían Albino y Claridad.
 40 personas consumían los tres productos.
 56 personas no consumían Blancura.
A) ¿Cuántas personas consumían solamente Blancura?
B) ¿Cuántas personas consumían Albino y Blancura?
C) ¿Cuántas personas consumían solamente Albino?

1.4.Sistema de Numeración (binario, Octal. Hexadecimal, Decimal)

Sistema de numeración. Conjunto de reglas y convenios que permiten la representación de todos

los números naturales, en principio, a partir de una colección limitada de símbolos básicos.
El sistema de numeración es de gran importancia en el estudio de un tecnólogo ya que el
sistema binario y hexadecimal está incluido en el sistema informático de una computadora.
Los sistemas que se estudiaran a continuación son: binario, octal, decimal y hexadecimal.
1.4.1. Sistema de numeración Binario
El sistema de numeración binario utiliza sólo dos dígitos, el cero (0) y el uno (1).
En una cifra binaria, cada dígito tiene distinto valor dependiendo de la posición que ocupe. El
valor de cada posición es el de una potencia de base 2, elevada a un exponente igual a la
posición del dígito menos uno. Se puede observar que, tal y como ocurría con el sistema
decimal, la base de la potencia coincide con la cantidad de dígitos utilizados (2) para
representar los números.

ISTJOL | Página 15
 Guía para el Estudiante

Recuerda:
Para convertir un numero octal a binario se debe representar los dígitos que se
encuentran en la tabla

Ejemplos:
a) 356(8): 011101110(2)

b) 1347(8): 001011100111(2)

c) 35712(8): 011101111001010(2)

AA7: Realizar las siguientes conversiones (1. Pts. c/ literal)

Conversión de octal a binario.
 3723(8) a (2)
 00011111100111(2) a (8)
 155(8) a (2)
 10011001101(2) a (8)
 3246(8) a (2)
 7523(8) a (2)
 6452(8) a (2)
 3241(8) a (2)
 1342(8) a (2)
 4637
 532
 615

1.4.2. Sistema de numeración Octal

El sistema numérico en base 8 se llama octal y utiliza los dígitos 0 a 7. Los números octales
pueden construirse a partir de números binarios agrupando cada tres dígitos consecutivos de
estos últimos (de derecha a izquierda) y obteniendo su valor decimal

Recuerda: Para convertir un numero binario a octal se debe agrupar los dígitos de
tres en tres para formar el numero octal, y si hace falta se debe agregar tantos
cero como sea necesario

ISTJOL | Página 16
 Guía para el Estudiante
Ejemplos:
a) 111000011(2): 703(8)

b) 001010100100011111(2): 124437(8)

AA8: Realizar las siguientes conversiones (1. Pts. c/ literal)

Conversión de binario a octal.
 1100011(2) a (8)
 00011111100111(2) a (8)
 010101010(2) a (8)
 10011001101(2) a (8)
 111000011011(2) a (8)
 1101011100(2) a (8)
 101110011(2) a (8)
 110011000110(2) a (8)
 0101001001001(2) a (8)
 001111110011(2) a (8)

1.4.3. Sistema de numeración Decimal

Nuestro sistema de numeración tiene dos características esenciales: es decimal y es posicional.

 Es decimal porque:
o Utilizamos 10 dígitos: 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9
o Agrupamos de 10 en 10 en órdenes cada vez mayores:
 10 U = 1 D
 10 D = 1 C
 10 C = 1 UM
 10 UM = 1DM
 Es el esquema que ya conoces de otros cursos, ¿te suena de algo?

 En números de nueve cifras esta es la manera como se ordena:

 Es posicional porque el valor de cada cifra en un número depende del lugar que
ocupa.
En el número 370.241 la cifra 2 ocupa el orden de las centenas, por lo tanto, 2C = 20D
= 200U
 La cifra 7 ocupa el orden de las decenas de millar, por lo tanto 7DM = 70UM = 700C
= 7.000D = 70.000U

ISTJOL | Página 17
 Guía para el Estudiante

Ejemplos:
Conversion de decimal a binario

Figura 1. Conversión decimal a binario

Tabla 1. Conversión de decimal a binario.

1 0 0 0 0 1 1 0 1 1
29 28 27 26 25 24 23 22 21 20
512 256 128 64 32 16 8 4 2 1

Conversión de decimal a octal

Figura 2. Conversión de decimal

)
Actividades de aprendizaje:
AA9: Realizar las siguientes conversiones (5. Pts. c/ literal)
1) Conversión de decimal a binario y viceversa.
 456(10) a (2)
 1100110(2) a (10)
 3200(10) a (2)
 0110001(2) a (10)
 1525(10) a (2)
2) Conversión de decimal a octal y viceversa.
 1077(10) a (8)
 2364(8) a (10)
 768(10) a (8)
 8756(8) a (10)
 6435 (10) a (8)
1.4.4. Sistema de numeración Hexadecimal
El sistema hexadecimal es un método de numeración posicional que utiliza como base el
número 16 (Base-16), es decir, que existen 16 símbolos de dígitos posible.
Sus números están representados por los 10 primeros dígitos de la numeración decimal y
el intervalo del número 10 al número 15 se representa por las letras del alfabeto: A, B, C,
D, E y F.

ISTJOL | Página 18
 Guía para el Estudiante

Ejemplo:

De octal a hexadecimal

De hexadecimal a octal

1.5.Conversión entre sistemas de numeración.

Actividades de aprendizaje:
AA10: Realizar las siguientes conversiones (2. Pts. c/ literal)
1) Conversión de binario a hexadecimal y viceversa.
 11010101110(2) a (16)
 48BF3E (16) a (2)
 010111001(2) a (16)
 6E8D5F (16) a (2)
 100001111011(2) a (16)

ISTJOL | Página 19
 Guía para el Estudiante
Actividades de aprendizaje:
AA11: Realizar las siguientes conversiones (2. Pts. c/ literal)
2) Conversión de hexadecimal a octal y viceversa.
 2534(8) a (16)
 B3F76A (16) a (8)
 6735(8) a (16)
 9436DE2(16) a (8)
 74561(8) a (16)

1.6.Autoevaluación

¿Qué es conjunto? (2 ptos.)

¿Cómo se clasifican los conjuntos relevantes? (2 ptos.)
¿Qué es el sistema de numeración? (2 ptos.)
¿Qué es un sistema hexadecimal? (2 ptos.)
¿Cómo se clasifica el sistema de numeración? (2 ptos.)

UNIDADA II
2. Tema. Lógica proposicional

Objetivo: Usar con precisión los conectores lógicos, mediante la graficación para la
representación de las proposiciones compuesta, relacionándolas con lenguaje simbólico y
expresarlo en el lenguaje ordinario.

Sistema de conocimientos Sistema de habilidades Sistema de valores

2.1 Lógica Matemática, Usar correctamente los Precisión en usar conectores
operadores lógicos conectores lógicos. lógicos.
2.2 Tablas de verdad Efectúa operaciones Honestidad al realizar
2.3 Leyes del algebra utilizando tablas de trabajos intra y extra clase
proposicional verdad. de los temas tratados en esta
2.4 Razonamiento lógico Desarrollar ejercicios unidad.
aplicando las leyes de
algebra proposicional y
razonamiento lógico.

2.1.Lógica Matemática, operadores lógicos

Lógica matemática. Es la disciplina que trata de métodos de razonamiento. En un nivel

elemental, la lógica proporciona reglas y técnicas para determinar si es o no valido un
argumento dado. El razonamiento lógico se emplea en matemáticas para demostrar teoremas;
en ciencias de la computación para verificar si son o no correctos los programas; en las
ciencias física y naturales, para sacar conclusiones de experimentos; y en las ciencias sociales
y en la vida cotidiana, para resolver una multitud de problemas.

2.1.1. Proposiciones simples y compuestas

Proposición es la oración afirmativa que puede ser verdadera o falsa, pero no ambas.

ISTJOL | Página 20
 Guía para el Estudiante
En la lógica se distinguen dos tipos de proposiciones, siendo estas: Simples o atómicas y
compuestas o moleculares.
Como ejemplos de proposiciones se dan los siguientes:
1. 4 es menor que ocho
2. Carlos es alto
3. México es un país de América
5. María es inteligente

Ahora se dan algunas expresiones que no son proposiciones:

1. ¿Cómo te llamas?
2. ¿Qué hora es?
4. El árbol
5. ¡Levanta esa pluma!
Estas expresiones no son proposiciones porque no afirman nada que sea verdadero o falso, es
decir, la 1 y 2 son preguntas, la 3 es una frase y la 5 es una orden.

Las proposiciones simples o atómicas son aquellas que no tienen otras oraciones dentro de
sí mismas, es decir, que sólo tienen un sujeto, un verbo y un predicado, y por lo tanto, carecen
de conectiva lógica (una partícula que nos permite unir proposiciones), por ejemplo:

 La Revolución Francesa fue en 1789.

 Las plantas generan oxígeno.
 Sócrates fue un filósofo griego.

Las proposiciones compuestas son aquellas que contienen dentro de sí más de una
proposición simple. Estas se relacionan a través de una conectiva lógica, por ejemplo:

 El amor y el odio son sentimientos opuestos.

 Si escribo diariamente algo, entonces redactaré mejor.
 Compro el vestido negro o el rojo.

Actividades de aprendizaje:
AA12: Escribir 5 proposiciones simples y 5 proposiciones compuestas. (1. Pts. c/u)

2.1.2. Operadores lógicos

Los Operadores Lógicos son utilizados por la lógica proposicional para admitir o rechazar
proposiciones. En programación de ordenadores se utilizan para combinar valores lógicos
(Verdadero/Falso) y obtener nuevos valores lógicos que determinen el flujo de control de un
algoritmo o programa.

Los operadores lógicos se clasifican en:

CONJUNCIÓN: Es aquel conectivo lógico que, al unir dos o más proposiciones el
resultado será verdadero cuando las dos son verdaderas caso contrario serán falsas. Se
representa con el símbolo . Las palabras que se utilizan para unir las proposiciones son:
“y”, “pero” entre otras

La tabla de verdad de la conjunción es la siguiente:

Tabla 2. Conjunción
P Q p q
0 0 0

ISTJOL | Página 21
 Guía para el Estudiante
0 1 0
1 0 0
1 1 1
Ejemplo:
P: María canta y Pedro baila.
Q: Hace frío y está lloviendo.
DISYUNCIÓN INCLUSIVA: es aquel conectivo que, al unir dos o más proposiciones, el
resultado será falso si ambas proposiciones son falsas, sino caso contrario serán verdaderas.
Se la representa con el símbolo . Las palabras de enlace que se usa es “o”. La tabla de
verdad es:
Tabla 3.Disyunción Inclusiva.
P Q p q
0 0 0
0 1 1
1 0 1
1 1 1
Ejemplo:
R: Es de noche o está lloviendo.
S: La tierra es plana o es redonda.
DISYUNCIÓN EXCLUSIVA: es aquella proposición que será verdadera cuando su
antecedente es verdadero y su consecuente falso o viceversa. Caso contrario serán falsas. Su
símbolo es ⊻. Las palabras de enlace que se utilizan en este operador es “o…….o”
Tabla 4. Disyunción Exclusiva
P Q p⊻q
0 0 0
0 1 1
1 0 1
Ejemplo: 1 1 0
P: O es una roca o es una piedra.
R: O es pobre o es millonario.
CONDICIONAL: es aquel conectivo que será falso cuando su antecedente sea verdadero y
su consecuente sea falso, es decir cuando se forme el 10 será falso, caso contrario será
verdadero. Su símbolo es →
Su frase de enlace es “entonces”
Tabla 5. Condicional
P Q p→q
0 0 1
0 1 1
1 0 0
1 1 1
Ejemplo:
T: Si está lloviendo entonces no salgo al parque

ISTJOL | Página 22
 Guía para el Estudiante
U: Si compro la lotería entonces me compro un carro.
BICONDICIONAL: es aquella proposición que será verdadera cuando ambas
proposiciones tengan el mismo valor de verdad caso contrario serán falsas. Su frase es “si
solo si”. Su conector lógico es ↔
Tabla 6. Bicondicional
P Q p↔q
0 0 1
0 1 0
1 0 0
1 1 1
Ejemplo:
R: Tienes todas tus notas si solo si tienes todas las actividades.
S: Está lloviendo si y solo si está nublado.
NEGACION: si una proposición es verdadera se formará otra proposición que será falsa y
viceversa. Su frase es “no”
Tabla 7. Negación
p ~p
0 1
1 0
Ejemplo:
P: El perro cuida la casa
~ P: No es verdad que el perro cuida la casa.
Q: El piano no está nuevo.

Actividades de aprendizaje:
AA13. Tienes dos imágenes (proposiciones simples) combínalas, escribe en el cuadro
correspondiente la proposición compuesta resultante de éstas imágenes. Recuerda que tienes
que unirlas a través de conectivas lógicas. (2.5. pts. c/u)

ISTJOL | Página 23
 Guía para el Estudiante

2.2.Tablas de verdad

Tablas de verdad o tabla de valores de verdad, es una tabla que muestra el valor de verdad
de una proposición compuesta, para cada combinación de valores de verdad que se pueda
asignar a sus componentes.
Fue desarrollada por Charles Sanders Peirce por los años 1880, pero el formato más popular
es el que introdujo Ludwig Wittgenstein en su Tractatus logico-philosophicus, publicado en
1921.
La tabla de los "valores de verdad", es usada en el ámbito de la lógica, para obtener la verdad
(V) o falsedad (F), valores de verdad, de una expresión o de una proposición.

Ejemplos:
Identificamos las proposiciones simples y les asignamos una variable:
P: Tu hermano hace el examen.
Q: Tu hermano pasará el examen.

P Q ¬𝐩 ¬𝐪 ¬𝐩 → ¬𝐪
2n
0 0 1 1 1
22= 2*2=4 0 1 1 0 0
1 0 0 1 1
1 1 0 0 1
2.2.1. Tautología, contingencia y contradicción.
Las tablas se clasifican en:

ISTJOL | Página 24
 Guía para el Estudiante

Actividades de aprendizaje:
AA14. En los problemas siguientes se pide construir la tabla de verdad de cada una de las
proposiciones compuestas. Indicando si es una contradicción, tautología o una contingencia.
(2.5. pts. c/u)

2.3.Inducción matemática

La inducción matemática: Es un procedimiento o método de demostración que se utiliza para

probar y/o demostrar que algunas operaciones o proposiciones se verifican para cualquier
número natural, es decir, (n N).
Principio de inducción matemática Si una propiedad p se cumple para un número natural k
cualquiera, también se cumplirá para su sucesor k+1 y por consiguiente se cumplirá para
cualquier número natural.
Pasos para probar una proposición por inducción matemática
1.- Se prueba la proposición dada para n=1
2.- Se prueba para n=k, lo cual se acepta como verdadero por ser la hipótesis de la inducción.
3.- Si la propiedad se cumple para n=1 y para n=k, entonces se prueba para n=k+1.
Ejemplo:

ISTJOL | Página 25
 Guía para el Estudiante

Actividades de aprendizaje:
AA15. Demostrar por inducción los siguientes ejercicios.

2.4.Autoevaluación

1. ¿Qué son operadores lógicos? (2 ptos.)

2. ¿Qué es proposición simple? (2 ptos.)
3. ¿Qué es proposición compuesta? (2 ptos.)
4. ¿Qué es inducción matemática? (2 ptos.)
5. ¿Cómo se clasifican las tablas de verdad? (2 ptos.)

UNIDAD III
3. Tema. Algebra Booleana, Números Reales y Funciones

Objetivo: Definir con claridad qué es álgebra Booleana, números reales y funciones, aplicando
correctamente la simbolización y graficación, para tener una mejor comprensión de los procesos
algebraicos.

ISTJOL | Página 26
 Guía para el Estudiante
Sistema de conocimientos Sistema de habilidades Sistema de valores
3.1 Teorema del álgebra de Precisión al emplear el Objetividad al emplear el
Boole álgebra Booleana. álgebra Booleana en la
3.2 Representación de resolución de ejercicios
funciones lógicas Efectuar ejercicios
matemáticos.
3.3 Compuertas lógicas aplicando el álgebra de
3.4 Operaciones con Boole. Claridad al definir los
números Naturales, conceptos de los temas
Crear ejemplos utilizando
Reales, Racionales y tratados en la unidad.
Enteros las compuertas lógicas.
3.5 Funciones Definir que son números
3.6 Tipos de funciones reales. Puntualidad para presentar
y representación gráfica
las tareas intra y extra clase
Graficar los tipos de
3.7 Tasa de cambio de la unidad.
funciones.
Diferenciar entre que es tasa
de cambio mediano y tasa de
cambio actual.

3.1.Teorema del álgebra de Boole

Es una rama especial del álgebra que se usa principalmente en electrónica digital. El álgebra
booleana fue inventada en el año 1854 por el matemático inglés George Boole.
El álgebra de Boole es un método para simplificar los circuitos lógicos (o a veces llamados
circuitos de conmutación lógica) en electrónica digital.
Por lo tanto, también se llama como "Cambio de álgebra". Podemos representar el
funcionamiento de los circuitos lógicos utilizando números, siguiendo algunas reglas, que son
bien conocidas como "Leyes del álgebra de Boole".

Como se mencionó anteriormente, el álgebra de Boole se inventó en el año de 1854, por el

matemático inglés George Boole. Primero declaró la idea del álgebra de Boole en su libro
"Una investigación de las leyes del pensamiento".
Después de esto, el álgebra de Boole es bien conocida como la forma perfecta para representar
los circuitos lógicos digitales.
A fines del siglo XIX, los científicos Jevons, Schroder y Huntington utilizaron este concepto
para términos modernizados. Y en el año de 1936, MHStone demostró que el álgebra de Boole
es 'isomorfo' para los conjuntos (un área funcional en matemáticas).
En la década de 1930, un científico llamado Claude Shannon desarrolló un nuevo método de
álgebra tipo "Cambio de álgebra" utilizando los conceptos de álgebra de Boole, para estudiar
los circuitos de conmutación.

ISTJOL | Página 27
 Guía para el Estudiante

3.2. Representación de funciones lógicas.

Operadores básicos
Con las expresiones booleanas A y B, podemos generar nuevas expresiones a partir de ellas
combinándolas con los llamados operadores booleanos

Una Compuerta Lógica es un circuito electrónico que está conformado internamente por
receptores que tienen arreglos especiales con los que pueden otorgar señales de voltaje como
resultado o una salida de forma booleana, aplicando operaciones lógicas binarias (suma,
multiplicación). Además, niegan, afirman, incluyen o excluyen según sus propiedades lógicas.
Estas compuertas se pueden aplicar en otras áreas de la ciencia como mecánica, hidráulica o
neumática.
Las operaciones básicas del álgebra de Boole son tres:
a. Producto lógico, puerta AND o función intersección,
b. Suma lógica, puerta OR o función unión.
c. Negación lógica, puerta NOT o función complemento.

Además, hay funciones no básicas o auxiliares:

ISTJOL | Página 28
 Guía para el Estudiante
a. Negación del producto lógico, puerta NAND
b. Negación de la suma lógica, puerta NOR.
c. Suma lógica exclusiva, puerta XOR.
d. Negación de la suma lógica exclusiva, puerta XNOR.

3.3.Compuertas lógicas

Compuerta AND. - La salida de esta compuerta estará en estado alto siempre y cuando las dos
entradas estén en estado alto, caso contrario estarán en estado bajo.

Figura. Compuerta AND

Compuerta OR. – Si las dos entradas están en estado bajo la salida estará en estado bajo,
caso contario estará en estado alto.

Figura3. Compuerta OR

Compuerta NOT. - En esta compuerta la salida es inversa a la de la entrada, es decir que si

la entrada está en estado alto la salida estará en estado bajo y viceversa.

Figura. Compuerta NOT

Compuerta NAND. – La salida estará en estado bajo, solo si las dos entradas están en
estado alto, la compuerta NAND es la negación de la compuerta AND.

Figura4. Compuerta NAND

Compuerta NOR. - La salida estará en estado bajo siempre y cuando las entradas estén en
estado alto. La compuerta NOR es la negación de la compuerta OR.

ISTJOL | Página 29
 Guía para el Estudiante

Figura. Compuerta NOR

Compuerta XOR (EXOR). - La salida de esta compuerta estará en estado alto si una de las dos
entradas está en estado alto, es decir si son iguales es cero y si son diferentes es uno.

Figura. Compuerta XOR

Compuerta XNOR (EXNOR). – La salida estará en estado alto solo si las dos entradas tienen el
mismo valor de verdad caso contrario estarán en estado alto, es decir si son iguales es uno y si son
diferentes es cero.

Figura. Compuerta XNOR

Compuerta BUFFER, YES, SEPARADOR. - Esta compuerta solo realiza la función de igualdad
o amplificación.

Figura. Compuerta BUFFER

Representación algebraica
La notación algebraica es la que se compone de la escritura de variables y operadores del
algebra booleana. A continuación, se muestran dos ejemplos, uno para una función con 3
variables de entrada y otro para 4 variables de entrada:

 F = ABC’ + (A+B’+C)’ + AC’

 Z = xy’ + (y+w’) + (z’+w)’

Representación mediante tabla de verdad

La tabla de verdad es una forma muy sencilla de definir una función. Consiste en colocar en
una tabla todas las posibilidades de las variables de entrada junto con el valor que debe
tener la salida. A continuación se muestra un ejemplo:

ISTJOL | Página 30
 Guía para el Estudiante

Ejemplo:

Actividades de aprendizaje:
AA16. Encontrar el valor de verdad de los siguientes circuitos lógicos haciendo uso de las
tablas de verdad. (2,5. Pts. c/u)

a) b)

ISTJOL | Página 31
 Guía para el Estudiante

c) d)

3.4.Operaciones con números Naturales, Reales, Racionales y Enteros

Históricamente, la matemática surge con la finalidad de hacer los cálculos en el comercio, y

también con la de medir la Tierra y predecir los acontecimientos astronómicos. Estas tres
necesidades pueden ser relacionadas, en cierto modo, con la subdivisión amplia de la
matemática en el estudio de los números, el espacio y el cambio. El estudio de los números
comienza con los naturales y los enteros y nos lleva finalmente a las estructuras algebraicas.
Con los números se pueden realizar varias operaciones, pero las principales operaciones
básicas son suma, resta, multiplicación y división.
Los números se clasifican en:

Números naturales
Los números naturales son los que desde el principio de los tiempos se han utilizado para
contar. En la mayoría de países han adoptado los números arábigos, llamados así porque
fueron los árabes quienes los introdujeron en Europa, pero fue en la India donde se inventaron.
El conjunto de los números naturales se denota como y se representan así:

Números reales
El conjunto formado por los números racionales y los números irracionales se denomina
conjunto de los números reales y se denota como
Así pues tenemos que:

ISTJOL | Página 32
 Guía para el Estudiante

Números Racionales
Son aquellos que resultan de la razón (división), entre dos números naturales. A este grupo
se lo representa con la letra “Q”. Además, los números racionales pueden ser sumados,
restados, multiplicados o divididos y el resultado de ellos puede ser un entero, un decimal o
un fraccionario positivo o negativo.
Ejemplo:
𝟖
− = −𝟐
𝟒

𝟓
= 𝟎, 𝟓𝟓𝟓𝟓𝟓𝟓𝟓𝟓𝟓𝟓
𝟗

𝟗𝟒
= 𝟑, 𝟕𝟔
𝟐𝟓

Números Irracionales
Son aquellos números los cuales no pueden ser expresados en fracciones porque incluyen
elementos decimales indeterminados y se los utiliza en procesos matemáticos complejos
como ecuaciones algebraicas y formulas físicas. Es decir, estos números no se pueden
expresar como fracciones.
Los números irracionales se representan con la letra “I”
Ejemplo:
El número Pi =3.141592653589…;
El número áureo= 1,618033988749…;
El número de Euler = 2,718281828459…
Números Enteros
Es aquel conjunto que está formado por todos los números naturales y sus opuestos incluido
el cero. Se representan con la letra “Z”

Ejemplos:

a)

ISTJOL | Página 33
 Guía para el Estudiante

b)

c) Un padre reparte entre sus hijos 1 800 €.

Al mayor le da 4/9 de esa cantidad, al mediano 1/3 y al menor el resto.
¿Qué cantidad recibió cada uno?
¿Qué fracción del dinero recibió el tercero?

Actividades de aprendizaje:
AA17. Resolver los siguientes ejercicios.
1) Realiza las siguientes operaciones (1. Pts. c/u)

2) Efectúa las siguientes operaciones y, si es posible, simplifica el resultado: (1 pts. c/u)

3) Calcula. (1.5. pts. c/u)

ISTJOL | Página 34
 Guía para el Estudiante

3. Resolver los siguientes problemas planteados. (1 pts.)

a) Hace unos años Pedro tenía 24 años, que representan los 2/3 de su edad actual.
¿Qué edad tiene Pedro?

3.5.Funciones

En matemáticas, una función f es una relación entre un conjunto dado X (el dominio) y otro
conjunto de elementos Y (el codominio) de forma que a cada elemento x del dominio le
corresponde un único elemento del codominio f(x). Se denota por:

Una primera idea de función es la de una fórmula que relaciona algebraicamente varias
magnitudes.
La representación gráfica mediante diagramas cartesianos permite la visualización de las
funciones. De este modo, el concepto de función se generaliza a cualquier relación numérica
que responda a una gráfica sobre unos ejes coordenados.

La expresión f(x) indica el valor de la función f asociado al número x. Las funciones describen
fenómenos cotidianos, económicos, psicológicos, científicos...Tales funciones se obtienen
experimentalmente, mediante observación. Las funciones definidas a trozos, requieren de varias
fórmulas, cada una de las cuales rige el comportamiento de la función en un cierto tramo.

ISTJOL | Página 35
 Guía para el Estudiante
3.6.Tipos de funciones

Funciones polinómicas lineales o afines: están definidas por polinomios de primer grado.
Son de la forma: f(x) = mx + b. Su representación gráfica en el plano cartesiano es una recta
oblicua, que queda definida por dos puntos de la función. Ejemplos: f(x) = x (función
identidad); f(x) = 4x - 8

Función afín Función lineal

Funciones cuadráticas: son funciones definidas por polinomios de segundo grado. Son de la
forma: f(x) = ax² + b x + c. Su representación gráfica en el plano cartesiano corresponde a una
parábola. Ejemplo: f(x) = 3x2 - x – 6

Ejemplos:

Resolver los siguientes ejercicios de funciones lineales y cuadráticas.

ISTJOL | Página 36
 Guía para el Estudiante

Ejemplo

Hacemos una tabla para calcular dos puntos de la gráfica:

Actividades de aprendizaje:
AA18. Resolver los siguientes ejercicios planteados con su respectiva grafica e indicando
si es una función cuadrática o lineal. (1.pts. c/u)
a) Resolver y representar la función cuadrática y = x² + x + 1
b) Resolver y representar la función cuadrática y = x² − 5x + 3
c) Resolver y representar la función cuadrática 2 y = 2x² − 5x + 4
d) Resolver y representar la función cuadrática 3 y = x² − 2x + 4
e) Resolver y representar la función cuadrática 4 y = −x² − x + 3
f) Resolver y representar la función lineal y = 2x – 1
g) Resolver y representar la función lineal 2y = 4x + 12
h) Resolver y representar la función lineal f(x) = 3x + 2
i) Resolver y representar la función lineal y= = -3x+7
j) Resolver y representar la función lineal y= x- 2x+ 1

ISTJOL | Página 37
 Guía para el Estudiante
3.7.Tasa de cambio

La tasa de cambio es la relación de proporción que existe entre el valor de una y la otra. Dicha tasa
es un indicador que expresa cuántas unidades de una divisa se necesitan para obtener una unidad de
la otra.
En otras palabras, el tipo o tasa de cambio es la reciprocidad que existe entre dos monedas en
función de una oferta y una demanda. Es decir, cuantifica el precio de compra o venta sobre
la base de un par de moneda o divisa.

En ese sentido, el tipo o tasa de cambio es la manera de interpretar el vínculo comercial

que se da entre monedas partiendo de cuánto representa la divisa base en divisa
transaccional.

3.5.1. Tipos de cambio

La oferta y la demanda de divisas determina el tipo o tasa de cambio en el mercado
cambiario. Éstas surgen ante la necesidad de relacionar las monedas de distintos países que es
la vía para las transacciones económicas internacionales. Dentro de ellas encontramos dos
tipos tipo de cambio “nominal” y “real”.

 Cambio nominal
El tipo de cambio o tasa “nominal” es la representación del valor de una unidad de moneda
de otro país expresado en términos de la moneda nacional. Es un precio relativo, y sus cambios
influyen también en los precios de los bienes y servicios producidos en el país con respecto a
los producidos en otro.

 Es el precio relativo de la “moneda” de dos países.

 Es aquel al cual se compra o se venden divisas en el mercado.
 Es la cotización oficial del tipo o tasa de cambio.

 Cambio real
El tipo de cambio o tasa “real” es el precio de los bienes del país extranjero expresado en
términos de bienes locales. Ambos llevados a una misma moneda.
Si el tipo de cambio real sube, los bienes nacionales serán relativamente más caros y los
extranjeros más baratos. Si, por el contrario, el cambio real baja, los bienes nacionales serán
relativamente más baratos y los extranjeros entonces más caros.

 Es el precio de los “bienes” de dos países.

 Es el poder de compra de una moneda sobre los bienes de dos países.
 Refleja el verdadero poder de compra que tiene la moneda nacional frente a una o
varias monedas extranjeras.
 Representa entonces, el real poder adquisitivo tomando en cuenta los precios del país
de otra divisa.

ISTJOL | Página 38
 Guía para el Estudiante
 Régimen cambiario
Son las políticas adoptadas por un país referidas al valor de su moneda y determinación del
tipo o tasa de cambio. Por supuesto, ese valor, al igual que el de los bienes y servicios, puede
ser influenciado, e incluso intervenido y arreglado, por los gobiernos para favorecer su
economía.

Un régimen cambiario se basa tres tipos de cambios:

 Tipo de cambio fijo: se refiere al anclaje de una moneda al valor de otra, pero de
manera directa y estricta. La política monetaria deriva de la moneda principal. Por lo
tanto, no se permiten cambios en su relación y valor.
 Tipo de cambio flexible: es cuando en un mercado de divisas se pueden producir
cambios en el valor de la moneda producto de la inflación o de algunas actividades
comerciales entre varios países. Pueden establecerse restricciones para moderar esos
cambios.
 Tipo de cambio fluctuante: en este sistema mixto puede haber restricciones, pero
flexibles dependiendo de la oferta y la demanda y respetando los márgenes
establecidos que generalmente son del 1% al 3% para ayudar a estabilizar el mercado
cambiario.

Ejemplos:

Si el 24 de agosto de 2000, el dólar americano cotizaba en Frankfurt a 1,05 euros, en Zurich

a 1,6 francos suizos y en Tokio a 125 yenes.

Calcular:
a) La cotización en euros del franco suizo y del yen.
b) La cotización en francos suizos del euro y del yen
c) La cotización en yenes del franco suizo y del euro

Solución
a) TCHF/EUR = TCHF/USD ÷ TEUR/USD = 1,6 ÷ 1,05 = 1,5238 CHF/EUR
TJPY/EUR = TJPY/USD ÷ TEUR/USD = 125 ÷ 1,05 = 119,05 JPY/EUR

b) TEUR/CHF = 1 ÷ TCHF/EUR = 1 ÷ 1,5238 = 0,6563 EUR/CHF

TJPY/CHF = TJPY/USD ÷ TCHF/USD = 125 ÷ 1,6 = 78,125 JPY/CHF

c) TCHF/JPY = 1 ÷ TJPY/CHF = 1 ÷ 78,125 = 0,0128 CHF/JPY

TEUR/JPY = 1 ÷ TJPY/EUR = 1 ÷ 119,05 = 0,0084 EUR/JPY

Si 1 euro ——————— 9,184 coronas

X euros ——————— 100.000 coronas

Actividades de aprendizaje:
AA19. Resolver los siguientes ejercicios de tasa de cambio (2 pts. c/u)

ISTJOL | Página 39
 Guía para el Estudiante
a) Convertir 6000 pesos colombianos a dólares
b) Calcular el tipo de cambio a un plazo de dos meses de la libra esterlina con relación al yen
sabiendo que: 102,05 JPN = 1 EUR que 0,617 GBP = 1 EUR; que el tipo de interés de los
yenes a dos meses es del 0,75% nominal anual, mientras que el de la libra es de 6,125%
nominal anual.
c) Convertir 500 dólares a euros
d) Convertir 1200 soles a yenes japoneses
e) Convertir 5000 euros a dólares

3.6. Autoevaluación (10. Pts.)

4) ¿Qué es álgebra de Boole?
5) ¿Qué son compuertas lógicas?
6) Realice un cuadro sinóptico sobre la clasificación de los números.
7) ¿Qué es una función lineal?
8) ¿Qué es tasa de cambio?

UNIDAD IV
4. Tema. Teoría de grafos y árboles

Objetivo: Resolver con criticidad problemas mediante la aplicación de la teoría de grafos y árboles para
que puedan aplicarlos en su ámbito de sus conocimientos, los mismos que le ayudarán a descubrir
nuevos temas relacionados en el campo tecnológico.

Sistema de conocimientos Sistema de habilidades Sistema de valores

4.1 Grafos, definiciones Resolver problemas de la Criticidad en reconocer y

básicas teoría de grafos y árboles. definir la teoría de grafos y
árboles.
4.2 Algoritmos de la ruta Detallar las redes de flujo en
más corta grafos. Muestra paciencia, interés,
curiosidad y perseverancia
4.3 Redes de flujo en grafos Definir los conceptos de
desarrollar problemas de
árboles y su clasificación.
4.4 Árboles, definiciones grafos y árboles.
básicas Desarrollar ejemplos con los
temas tratados en la unidad
4.5 Árboles n-arios
4.6 Árboles binarios

4.1. Grafos, definiciones básicas

Para las matemáticas y las ciencias de la computación, un grafo es el principal objeto de

estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un
conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas). Los grafos
permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.

ISTJOL | Página 40
 Guía para el Estudiante

Figura 5. Grafo.

Un grafo está conformado por las siguientes partes:

 Arista: es la unión de dos vértices de un grafo. Si la línea carece de dirección se denota
indistintamente los vértices que une.
 Aristas adyacentes: cuando dos aristas en el mismo vértice confluyen.
 Aristas paralelas: dos aristas son paralelas si los vértices iniciales y el final son iguales.
 Aristas cíclicas: sale y llega de al mismo vértice.
 Cruce: es la intersección de dos aristas sobre un punto.
 Vértice: son los puntos de un grafo.
 Grado de un vértice: total de aristas extremo.
 Vértices adyacentes: es la arista que une un par de vértices.
 Vértice aislado: cuyo grado es cero.
 Vértice terminal: es aquel que tiene un grado 1.
 Caminos: serie de vértices unidos por aristas.
 Circuitos: los vértices iniciales y finales de un camino llegan al mismo sitio.

Grafo Dirigido: como su nombre lo indica es aquel que indica hacia donde sus aristas
deben seguir una dirección.
Grafo no Dirigido: es aquel grafo en el cual sus aristas no apuntan hacia ninguna dirección
es decir sus aristas son bidireccionales.

Matriz de adyacencia.

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de
adyacencia.
Se trata de una matriz cuadrada de n filas xn columnas (siendo n el número de vértices del
grafo).
Para construir la matriz de adyacencia, cada elemento aij vale 1 cuando haya una arista que
una los vértices i y j. En caso contrario el elemento aij vale 0.
La matriz de adyacencia, por tanto, estará formada por ceros y unos.
Ejemplo 1
Vamos a construir la matriz de adyacencia del siguiente grafo:

ISTJOL | Página 41
 Guía para el Estudiante

Matriz de incidencia
En matemáticas , una matriz de incidencia es una matriz que muestra la relación entre dos
clases de objetos. Si la primera clase es X y el segundo es Y, la matriz tiene una fila para cada
elemento de X y una columna para cada elemento de Y. La entrada en la fila x y la columna y
es 1 si x y y están relacionados (llamado incidente en este contexto) y 0 si no lo son.

Actividades de aprendizaje:
AA20. Construir la matriz de adyacencia de los siguientes grafos. (2.5. pts. c/u)

ISTJOL | Página 42
 Guía para el Estudiante

a) c)

b) d)

Actividades de aprendizaje:
AA21. Construir la matriz de incidencia de los siguientes grafos (2.5. pts. c/u)

a) b)

ISTJOL | Página 43
 Guía para el Estudiante

c) d)

4.2. Algoritmos de la ruta más corta

Algoritmo del camino más corto o ruta más corta (Algoritmo de Dijkstra). El algoritmo de
Dijkstra es un algoritmo eficiente (de complejidad O (n2), donde “n” es el número de vértices)
que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás
nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959. Este algoritmo
es un típico ejemplo de algoritmo ávido, que resuelve los problemas en sucesivos pasos,
seleccionando en cada paso la solución más óptima con el objeto de resolver el problema.

Actividades de aprendizaje:
AA21. Encontrar la ruta más corta en los siguientes grafos. (2.5. pts. c/u)

ISTJOL | Página 44
 Guía para el Estudiante

a)

b)

c)

ISTJOL | Página 45
 Guía para el Estudiante

d)

4.3. Redes de flujo en grafos

Las redes de flujo son modelos matemáticos aplicables a situaciones tales como: sistemas de
tuberías (para fluidos como agua, petróleo o gas), redes de cableado eléctrico, sistemas de
carreteras, sistemas de transporte de mercancías, etc. Un ejemplo de esto sería: Un partido de
fútbol de gran interés tendrá lugar en Valencia. Los aficionados del equipo visitante quieren
ver el partido y animar a su equipo. Hay varias rutas para llegar a la ciudad, y el número
máximo de autos en las autopistas es conocido. ¿Cómo determinar el máximo número de
aficionados que pueden ir y las rutas que deben tomar?
La definición formal de la red de flujo es la siguiente:
Una red N = (V, X) es un grafo orientado conexo que tiene dos nodos distinguidos una fuente
s, con grado de salida positivo y un sumidero t, con grado de entrada positivo.

(Problema del Flujo Máximo) es similar al Problema de Ruta más Corta, pero ahora se
busca determinar el flujo máximo entre un nodo fuente y un nodo destino, los que están
enlazados a través de una red, con arcos con capacidad finita, tal como se presenta en la
siguiente figura. Notar que los números asignados a cada uno de los arcos representan los
flujos máximos o capacidades correspondientes a cada arco.

ISTJOL | Página 46
 Guía para el Estudiante

Actividades de aprendizaje:
AA22: Encontrar la red de flujo máximo de los grafos que se encuentran en la actividad
de aprendizaje 16. (2.5. pts. c/u)

4.4. Árboles, definiciones básicas

Los Árboles son las estructuras de datos más utilizadas, pero también una de las más
complejas, Los Árboles se caracterizan por almacenar sus nodos en forma jerárquica y no en
forma lineal como las Listas Ligadas, Colas, Pilas, etc., de las cuales ya hemos hablado en
días pasados.

ISTJOL | Página 47
 Guía para el Estudiante

Para comprender mejor que es un árbol comenzaremos explicando cómo está estructurado.
Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.
Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.
Nodo Padre: Se utiliza este término para llamar a todos aquellos nodos que tiene al menos
un hijo.
Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.
Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en
común dentro de la estructura.
Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran
en los extremos de la estructura.
Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que además tiene al menos
un hijo.

Los arboles además de los nodos tiene otras propiedades importantes que son utilizadas en
diferentes ámbitos los cuales son:

Nivel: Nos referimos como nivel a cada generación dentro del árbol. Por ejemplo, cuando a
un nodo hoja le agregamos un hijo, el nodo hoja pasa a ser un nodo rama, pero además el árbol
crece una generación por lo que el Árbol tiene un nivel más. Cada generación tiene un número
de Nivel distinto que las demás generaciones.

 Un árbol vacío tiene 0 niveles

 El nivel de la Raíz es 1
 El nivel de cada nodo se calculado contando cuantos nodos existen sobre él, hasta
llegar a la raíz + 1, y de forma inversa también se podría, contar cuantos nodos existes
desde la raíz hasta el nodo buscado + 1.

ISTJOL | Página 48
 Guía para el Estudiante
Altura: Le llamamos Altura al número máximo de niveles de un Árbol.

Peso: Conocemos como peso a el número de nodos que tiene un Árbol. Este factor es
importante porque nos da una idea del tamaño del árbol y el tamaño en memoria que nos
puede ocupar en tiempo de ejecución (Complejidad Espacial en análisis de algoritmos.)

Árbol n-ario
Los arboles n-arios son aquellos arboles donde el número máximo de hijos por nodo es de
N, en la figura 7 podemos apreciar dos árboles con grado 2 y grado 3, estos dos árboles
también los podemos definir como Árbol n-ario con n = 2 y n=3 respectivamente.

Árboles binarios
Esta estructura se caracteriza por que cada nodo solo puede tener máximo 2 hijo, dicho de otra
manera, es un Árbol n-ario de Grado 2.

ISTJOL | Página 49
 Guía para el Estudiante

Árbol binario lleno: Es aquel que el que todos los nodos tienen cero o 2 hijos con excepción
de la Raíz.

Árbol binario perfecto: Es un Árbol lleno en donde todos las Hojas están en el mismo Nivel.

Recorridos en árboles n-arios y binarios

Un recorrido de un árbol consiste en visitar todos los elementos del árbol una sola vez
Recorridos en profundidad de árboles n-arios:

ISTJOL | Página 50
 Guía para el Estudiante
 Recorrido en pre-orden:
a. Se visita la raíz
b. Se recorren en pre-orden todos los subárboles, de izquierda a derecha
 Recorrido en post-orden:
a. Se recorren en post-orden todos los subárboles, de izquierda a derecha
b. Se visita la raíz

Ejemplo:

Actividades de aprendizaje:
AA23: Encontrar los recorridos de los siguientes árboles (grafos). (2.5. PTS. c/u)

ISTJOL | Página 51
 Guía para el Estudiante

BIBLIOGRAFÍA BÁSICA Y COMPLEMENTARIA

 Seymour Lipschutz y Marc Lipson. MATEMÁTICAS DISCRETAS. Tercera Edición.

McGRAW-HILL/INTERAMERICANA. México, 2009. Páginas 490.
URL: https://www.ebooks7-24.com:443/?il=523
 T. Veerarajan. MATEMÁTICA DISCRETAS. Con teoría de gráficas y combinatorias.
Edición. McGRAW-HILL/INTERAMERICANA
LIBROS. Madrid, 2008. Páginas 549
URL: https://www.ebooks7-24.com:443/?il=3116
 Moisés Lázaro Carrión, LÓGICA Y TEORÍA DE CONJUNTOS. MOSHERA, Lima 2012.
Páginas 243.
URL: https://drive.google.com/open?id=0B4ibfsn7QvO9STMyeWY4UkpFbkE.
 Carmen Baena - Manuel Jesús Bellido - Alberto Jesús Molina María del Pilar Parra -
Manuel Valencia, PROBLEMAS DE CIRCUITOS Y PROBLEMAS DIGITALES.
McGRAW-HILL, 2000. Páginas 396.
URL: https://drive.google.com/open?id=0B4ibfsn7QvO9SUtQTzVEclc2a2s

ISTJOL | Página 52