Matemáticas Discretas

INSTITUTO TECNOLÓGICO DE OAXACA
PORTADA
MATEMÁTICAS DISCRETAS
BENITO GARCÍA ARÉCHIGA
2018
PORTADILLA
INSTITUTO TECNOLÓGICO DE OAXACA
MATEMÁTICAS DISCRETAS
BENITO GARCÍA ARÉCHIGA
AS-2-196/2017
2018
PRÓLOGO
PRÓLOGO
El estudio de las matemáticas discretas ha adquirido cada vez
mayor importancia en la medida en que avanzó la era de las
computadoras digitales, entendiendo que estas son estructuras
finitas y muchas de sus propiedades pueden comprenderse e
interpretarse en el marco de los sistemas matemáticos finitos.
Su comprensión, trascendencia y factibilidad de aplicaciones

cobra mayor importancia sobre todo para los alumnos de las
diferentes ingenierías y en especial para las relacionadas con las
ingenierías computacionales.
Con respecto al presente libro titulado “MATEMÁTICAS

DISCRETAS”, éste refleja en su contenido de seis unidades el
curso del mismo nombre y que se imparte para la carrera de
Ingeniería en Sistemas Computaciones del Instituto Tecnológico
de Oaxaca, toda una gama de interesantes temas como se
muestra más adelante y en donde nos brinda una cobertura por
demás útil e interesante en favor de los estudiantes.
El libro de texto es una herramienta, que permite a los

estudiantes de nivel superior abordar, estudiar y comprender el
posible tema de su interés, ya que el material aquí ofrecido y
como lo detallo para cada una de sus unidades aborda de
manera sencilla y práctica cada uno de los temas
5
PRÓLOGO
específicamente contenidos, buscando en todo momento la

fácil comprensión.
Así mismo, pretende que su contenido sea de apoyo inmediato

y lo guíe de manera fácil, razón por la cual, se incluyen ejemplos
y ejercicios resueltos adicionados a los conceptos teóricos y que
es propio de un curso de matemáticas.
En lo que respecta a la unidad I se enfoca en la definición de los

sistemas numéricos más comunes en el ámbito informático y los
ejercicios numéricos de conversión entre dichos sistemas y en la
solución y explicación de las operaciones aritméticas básicas
entre ellos, sin el apoyo de herramientas digitales.
La unidad II nos introduce a los conceptos de la teoría básica

de conjuntos, atendiendo definiciones, características,
operaciones y propiedades de los mismos, productos
cartesianos, relaciones de equivalencia, funciones y
aplicaciones complementan el contenido de esta unidad.
La unidad III se enfoca en la comprensión de las bases de la

lógica matemática proposicional y de predicados,
equivalencias lógicas y argumentos, incluyendo el uso de tablas
de verdad que permitan al estudiante desarrollar un
pensamiento lógico y capacidad de abstracción, previos a la
fase de creatividad y de diseño propio del campo de acción de
la Ingeniería en Sistema Computacionales.
6
PRÓLOGO
La unidad IV aborda de manera frontal el álgebra Booleana,

partiendo de la base de los teoremas y postulados hasta llegar
a la simplificación de expresiones Booleanas, incluyendo el uso
de los mapas de Karnaugh y por último su relación con los
circuitos lógicos.
En la unidad V, viro hacia la teoría de grafos con la definición,

ejercicios y aplicaciones, que le permitan al estudiante resolver
problemas afines al área computacional.
Y finalmente en la unidad VI, hago lo propio en lo relacionado a

los conceptos básicos de árboles, enfocándolo como un tipo
especial de grafo, algoritmos de recorrido, forma de
representarlos como estructura de datos y concluir con flujos
máximos y mínimos y redes de Petri.
De todo lo mencionado, considero que es de gran utilidad e

interés para los lectores y estudiantes, comprendiendo que los
contenidos del presente libro son todos imprescindibles en el
campo de la ingeniería digital, ya que están íntimamente
ligados al desarrollo de algoritmos y técnicas informáticas, que
van desde la simple conversión de sistemas numéricos hasta las
aplicaciones y diseños de circuitos digitales que serán de gran
beneficio en el fortalecimiento de su plataforma de
conocimientos que les habrán de servir en futuras empresas.
7
AGRADECIMIENTOS
Al Tecnológico Nacional de México
Al Instituto Tecnológico de Oaxaca
A la presente Administración
Al Departamento y a la Academia de Ciencias

Básicas que apoyaron el presente proyecto.
A mis compañeros Maestros que intervinieron

en la revisión del mismo.
DEDICATORIAS
A mis hijos Rafael, Germán

y Pablo García Quezada de quienes
he aprendido tanto.
ÍNDICE
ÍNDICE
UNIDAD I. SISTEMAS NUMÉRICOS

1.1 Sistemas numéricos (binario, octal, decimal, hexadecimal) 18
1.2 Conversiones entre sistemas numéricos 19
1.3 Operaciones básicas (Suma, Resta, Multiplicación
y División) 27
1.4 Aplicación de los sistemas numéricos en la computación 36
UNIDAD II. CONJUNTOS Y RELACIONES

2.1 Características de los conjuntos y subconjuntos 45
2.2 Operaciones de conjuntos 47
2.3 Propiedades y aplicaciones de los conjuntos 50
2.4 Conceptos básicos: producto cartesiano y relación binaria 53
2.5 Representación de las relaciones 56
2.6 Propiedades de las relaciones 57
2.7 Relaciones de equivalencia 58
2.8 Funciones 61
2.9 Aplicaciones de las relaciones y las funciones en la
computación 63
UNIDAD III. LÓGICA MATEMÁTICA

3.1 Lógica proposicional 69
3.1.1 Proposiciones simples y compuestas 70
3.1.2 Tablas de verdad 78
3.1.3 Tautología, contradicción y contingencia 81
3.1.4 Equivalencias Lógicas 83
3.1.5 Reglas de inferencia 85
3.1.6 Argumentos válidos y no válidos 86
3.1.7 Demostración formal (Directa por contradicción) 90
3.2 Lógica de predicados 91
3.3 Álgebra declarativa 93
3.4 Inducción Matemática 94
3.5 Aplicaciones de la lógica matemática en la computación 95
10
ÍNDICE
UNIDAD IV. ÁLGEBRA BOOLEANA

4.1 Teoremas del álgebra Booleana 103
4.2 Optimización de expresiones Booleanas 107
4.3 Aplicación del álgebra Booleana 126
4.3.1 Mini y maxitérminos (minterms y maxterms) 136
4.3.2 Representación de expresiones Booleanas 141
con circuitos lógicos
UNIDAD V. TEORÍA DE GRAFOS
5.1 Elementos, características y componentes de los grafos 149
5.1.1 Tipos de grafos 153
5.2 Representación de los grafos 163
5.2.1 Matemática 163
5.2.2 Computacional 166
5.3 Algoritmos de recorrido y búsqueda 171
5.3.1 El camino más corto 171
5.3.2 A lo ancho 173
5.3.3 En profundidad 175
UNIDAD VI. ÁRBOLES Y REDES

6.1 Árboles 184
6.1.1 Componentes y propiedades 186
6.1.2 Clasificación por altura y número de nodos 185
6.2 Árboles con peso 189
6.2.1. Recorrido de un árbol 190
6.3 Redes 199
6.3.1. Teorema del flujo máximo 200
6.3.2 Teorema del flujo mínimo 201
6.3.3 Pareo y Redes de Petri 203
CONCLUSIONES 210
BIBLIOGRAFÍA 212
11
ÍNDICE
12
Unidad I
SISTEMAS
NUMÉRICOS
14
COMPETENCIA ESPECÍFICA:
 IDENTIFICAR, MANIPULAR Y APLICAR LOS DIFERENTES
SISTEMAS NUMÉRICOS Y SUS OPERACIONES ARITMÉTICAS
BÁSICAS CON LA MAYOR VENTAJA POSIBLE EN CADA
CASO.
COMPETENCIAS GENÉRICAS:
 HABILIDAD DE RECONOCIMIENTO DE UN SISTEMA
NUMÉRICO EN CUESTIÓN.
 CAPACIDAD DE ABSTRACCIÓN Y ANÁLISIS.
 CAPACIDAD DE INTERPRETAR Y PROYECTAR LAS

APLICACIONES A PARTIR DEL CONOCIMIENTO DE LOS
SISTEMAS NUMÉRICOS.
15
SISTEMAS NUMÉRICOS
Se le llama sistema de numeración a un conjunto de símbolos y

reglas que son utilizados para la representación de datos
numéricos y cantidades. Estos se caracterizan por su base y
cuando hablamos de la base, se hace referencia al número de
símbolos distintos que un sistema numérico utiliza.
Sin duda alguna, el sistema numérico universalmente más

conocido es el sistema numérico decimal, mismo que de
manera casi natural se domina y que permite manipular
números en base diez.
Sobra decir, que el sistema decimal se derivó del sistema indo -

arábigo el cual creó los símbolos conocidos para representar
números. Luego este sistema fue introducido por los árabes en
Europa, aunque, en realidad, su invención surgió en la India.
Ya con el avance del desarrollo tecnológico, se fueron

popularizando otros sistemas numéricos de gran importancia
también, como lo son los sistemas numéricos binario, octal y
hexadecimal.
Se verá poco más adelante, como estos sistemas numéricos

interactúan entre sí, las operaciones, equivalencias y las
aplicaciones que el mundo de los sistemas digitales les ha dado.
16
Se omitirá lo relativo al sistema decimal, obviando su dominio,

pero en el presente caso del sistema de numeración binario,
como ustedes saben, únicamente consta de dos dígitos. Estos
dígitos binarios (bits) son 0 y 1.
La posición de un 1 o de un 0 en un número binario indica su

valor dentro del número y luego su base exponencial nos dará
su valor dentro de la cantidad de dígitos que tenga la cifra.
Así, por ejemplo, un número de cuatro bits 0010 y 1011

corresponden al 2 y al 11 en su equivalencia decimal resultantes
de la base dos y exponente de derecha a izquierda y luego la
sumatoria que nos da el valor equivalente. Partiendo de las
cantidades anteriores se tiene que: 0010 equivale a decir
1 x 21 + 0 x 20, los ceros a la izquierda son nulos y la sumatoria nos
da 2.
Para el segundo caso 1011, la cantidad equivale a decir

1 x 23 + 0 x 2 2 + 1 x 2 1 + 1 x 20 y la sumatoria da como resultado
11 decimal.
Este sistema es de suma importancia para la computación,

porque este permite manipular dos posibilidades o estados (0 y
1) y se considera un sistema extremadamente útil en el mundo
de la computación, aunque cabe decir que es posible
representar fracciones a la derecha del punto decimal, como
se muestra a continuación: 1/2, 1/4, 1/8, etcétera. Así por
17
ejemplo 0.11 binario, aplica 1x(1/2)+1 x (1/4), que equivale a

0.75 decimal.
Por lo que respecta al sistema numérico octal, este sistema solo

utiliza 8 dígitos los cuales son “0, 1, 2, 3, 4, 5, 6, 7”. El sistema de
numeración octal es muy usado en la computación debido a
que la conversión a binario y viceversa es bastante simple, por
la exactitud de la base 2 que a la potencia 3 = 8.
El sistema es considerado de gran utilidad en el mundo de las

computadoras y aplicaciones digitales.
Por último, en cuanto al sistema hexadecimal, que es un sistema

de base 16 el cual consta de 16 números los cuales son
“0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F”. Igual que en el sistema decimal,
cada vez que alcanzas 10 unidades de un determinado nivel, se
obtiene una unidad del nivel superior (diez unidades: una
decena, diez decenas: una centena, etc.) en el sistema
hexadecimal ahora con 16 unidades de un nivel se obtiene una
unidad del nivel superior. En un sistema hexadecimal existen por
lo tanto 16 dígitos distintos.
Este sistema normalmente se usa con la finalidad de ofrecer un

medio eficaz de representación de números binarios grandes
(agrupa cuatro de una sola vez) y esto permite simplificar la
expresión binaria de los objetos u otras variables informáticas en
la medida de un byte que representa un grupo de 8 bits.
18
1.1 Sistemas numéricos (binario, octal, decimal,

hexadecimal)
Binario: Es un sistema de numeración en el que los números se

representan utilizando solamente los dígitos cero y uno. También
es el sistema con el cual trabajan las computadoras debido a
que representan internamente dos niveles de voltaje.
Octal: El sistema numérico en base 8 se llama octal y utiliza los

dígitos 0 a 7.
Decimal: Es un sistema de numeración posicional en el que

las cantidades se representan utilizando como base aritmética
las potencias del número diez. El conjunto de símbolos utilizado
(sistema de numeración arábiga) se compone de diez dígitos,
por todos conocidos.
Hexadecimal: Es el sistema de numeración posicional que tiene

como base el 16. Su uso actual está muy vinculado a la
informática y ciencias de la computación pues las
computadoras suelen representar las direcciones de memoria
mediante este sistema.
Está compuesto por los dígitos 0 al 9 como en el sistema decimal

y adicionalmente por las letras A,B,C,D,E,F.
19
1.2 Conversión entre sistemas numéricos
Decimal:
Decimal-Binario: Consiste en dividir sucesivamente el número

decimal y los cocientes que se van obteniendo entre 2, hasta
que una de las divisiones se haga 0. La unión de todos los restos
obtenidos escritos en orden inverso, nos proporcionan el número
inicial expresado en el sistema binario.
Ejemplo:
Para convertir al binario el número decimal 77 se hace una serie

de divisiones que arrojarán los residuos siguientes:
77 / 2 = 38 Residuo 1
38 / 2 = 19 Residuo 0
19 / 2 = 9 Residuo 1
9/2=4 Residuo 1
4/2=2 Residuo 0
2/2=1 Residuo 0
1/2=0 Residuo 1
20
Luego se toman los residuos en orden inverso, es decir de arriba

hacia abajo y de derecha a izquierda, se obtiene la cifra binaria
resultado:
El decimal 77, entonces es igual al binario 1001101.
Decimal-Octal: La conversión de un número decimal a octal se

hace mediante divisiones sucesivas por 8 y colocando los
residuos obtenidos en orden inverso.
Ejemplo:
Para escribir en octal el número decimal 122 se hacen las

siguientes divisiones:
122 / 8 = 15 Residuo 2
15 / 8 = 1 Residuo 7
1/8=0 Residuo 1
Y tomando los residuos obtenidos en orden inverso se calcula la

cifra octal.
Por lo tanto, el decimal 122 es igual al octal 172.
Decimal-Hexadecimal: Utilizando divisiones sucesivas, la

conversión de un número decimal a hexadecimal.
21
Ejemplo:
Para convertir a hexadecimal del número decimal 1735 se

necesitan hacer las siguientes divisiones:
1735 / 16 = 108 Residuo 7
108 / 16 = 6 Residuo C (es decir 12 en decimal)
6 / 16 = 0 Residuo 6
Y luego se toman los residuos obtenidos en orden inverso y se

obtiene la cifra hexadecimal.
El decimal 1735 es igual al hexadecimal 6C7.
Otro procedimiento consiste en convertir el número decimal en

su equivalente binario y para el caso de 1735 sería igual a: 0110
1100 0111 y agrupados en grupos de 4 en orden de derecha a
izquierda obteniendo la conversión equivalente también a 6C7.
Binario:
Binario-Decimal: Teniendo en cuenta el valor de cada dígito en

su posición, que es el de una base 2 cuyo exponente es 0 en el
bit situado más a la derecha y se incrementa en una unidad en
el recorrido de posiciones hacia la izquierda.
22
Ejemplo:
Para convertir el número binario 1010011 a decimal, se

desarrolla teniendo en cuenta el valor de cada bit:
1*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 83
Por lo tanto, el binario 1010011 es igual al decimal 83.
Binario-Octal: Cada dígito de un número octal se representa

con tres dígitos en el sistema binario. Por tanto, el modo de
convertir un número entre estos sistemas de numeración
equivale a "expandir" cada dígito octal a tres dígitos binarios o
en "contraer" grupos de tres caracteres binarios a su
correspondiente dígito octal, tal como se muestra a
continuación.
Relación Binario-Octal
000 = 0 100 = 4
001 = 1 101 = 5
010 = 2 110 = 6
011 = 3 111 = 7
Ejemplo:
Para convertir el número binario 101001011 a octal se toman

grupos de tres bits de derecha a izquierda y se sustituyen por su
equivalente octal:
23
101 = 5 octal
001 = 1 octal
011 = 3 octal
Por lo tanto, el numero binario 101001011 es igual al octal 513.
Binario-Hexadecimal: La conversión entre números

hexadecimales y binarios se realiza expandiendo o contrayendo
cada dígito hexadecimal a cuatro dígitos binarios, como se
muestra en la relación siguiente:
0000 = 0 0110 = 6 1100 = C

0001 = 1 0111 = 7 1101 = D
0010 = 2 1000 = 8 1110 = E
0011 = 3 1001 = 9 1111 = F
0100 = 4 1010 = A
0101 = 5 1011 = B
Ejemplo:
Para expresar en hexadecimal el número binario 101001110011

bastará con tomar grupos de cuatro bits, empezando por la
derecha y en dirección a la izquierda y reemplazarlos por su
equivalente hexadecimal:
1010 = A
0111 = 7
0011 = 3
24
Por lo tanto, el número binario 101001110011 es igual al

hexadecimal A73.
Octal:
Octal-Decimal: Teniendo en cuenta el valor de cada dígito en

su posición, que es el de una base 8 cuyo exponente es 0 en la
posición situada más a la derecha y se incrementa en una
unidad según se avanzan posiciones hacia la izquierda.
Ejemplo:
Para convertir el número 237 octal a decimal basta con

desarrollar el valor de cada dígito:
2*8^2 + 3*8^1 + 7*8^0 = 128 + 24 + 7 = 159
Por lo tanto, el numero octal 237 es igual al decimal 159.
Octal-Binario: La conversión se realiza expandiendo cada dígito

octal en tres binarios como se muestra en la conversión de
Binario-Octal.
Por ejemplo, sea el número octal 357 obtener su equivalente

binario. Bien, como ya se dijo, agrupando en paquetes de tres
dígitos y comenzando de derecha a izquierda, se tiene que:
7 = 111
5 = 101
3 = 011
25
Respetando el orden mencionado la equivalencia sería: 011 101

111 o bien 11101111.
Octal-Hexadecimal: La forma más práctica de realizar esta

conversión es convertir el número octal en su equivalente
binario en paquetes de tres dígitos de derecha a izquierda y
posteriormente tomar dicha secuencia de dígitos de derecha a
izquierda y agruparlos en paquetes de 4 dígitos. Es el método
más directo de conversión con el cual se puede hacer la
operación Octal-Binario y luego Binario-Hexadecimal.
Por ejemplo, sea el número octal 1234, su equivalente binario

sería:
1 010 011 100 y reagrupados en paquetes de cuatro dígitos de

derecha a izquierda, se obtiene: 10 1001 1100, equivalente a
29C hexadecimal.
Hexadecimal:
Hexadecimal-Decimal: Teniendo en cuenta el valor de cada

dígito en su posición, que es el de una base 16 cuyo exponente
es 0 en la posición situada más a la derecha y se incrementa en
una unidad según se avanzan posiciones hacia la izquierda.
26
Ejemplo:
Para convertir el número hexadecimal 2CA a decimal:
2*16^2+C*16^1+A*16^0 = 512 + 192 + 10 = 714
Por lo tanto, el numero hexadecimal 2CA es igual al número

decimal 714.
Hexadecimal-Binario: La conversión se realiza expandiendo

cada dígito hexadecimal en cuatro binarios como se muestra
en la conversión de Binario a Hexadecimal.
Sea por ejemplo el número hexadecimal 10F, su conversión

directa al sistema binario sería: 1 0000 1111
Hexadecimal-Octal: Por igual, el procedimiento más simple es

convertir la cantidad hexadecimal en su equivalente binario en
paquetes de cuatro dígitos binarios, para posteriormente
reagrupar en paquetes de tres dígitos del sistema octal y
partiendo siempre de derecha a izquierda.
Ejemplo:
Sea el número AB9 hexadecimal, su equivalente binario sería:

1010 1011 1001; se reagrupa en paquetes de tres dígitos binarios
y de derecha a izquierda, tenemos: 101 010 111 001, equivalente
a 5271 octal.
27
1.3 Operaciones básicas (Suma, Resta, Multiplicación y

División)
Decimal:
Este sistema es el más usado en la cotidianidad matemática,

por este motivo doy paso a los siguientes sistemas, en los cuales
considero necesario entrar en materia.
Binario:
Suma: Las posibles combinaciones al sumar dos bits son:
0+0=0 1+0=1
0+1=1 1 + 1 = 10
Se opera como en el sistema decimal, comenzando a sumar

desde la derecha y hacia la izquierda, en nuestro ejemplo
1+1=10 entonces se escribe 0 en la fila del resultado y se lleva 1
(este "1" se llama arrastre). A continuación, se suma el acarreo a
la siguiente columna, 1+0+0=1 y se sigue hasta terminar todas las
columnas.
1111 1 1 (fila que muestra los unos de arrastre)

100110101
+ 11010101
——————
1000001010
28
Resta: El algoritmo de la resta en binario es el mismo que en el

sistema decimal y probablemente más fácil, en la medida en
que uno se familiariza con éste sistema numérico. Los términos
que intervienen en la resta se llaman minuendo, sustraendo y
diferencia en ese orden.
Las restas binarias básicas son:
0-0=0
1-0=1
1-1=0
La resta 0 - 1 se resuelve igual que en el sistema decimal,

tomando una unidad prestada de la posición siguiente, 10-1=
1 y me llevo 1, esa unidad prestada debe devolverse sumándola
a la posición o columna siguiente.
Por ejemplo, en la operación siguiente 217-171=46 en binario.
11011001 minuendo
-10101011 sustraendo
——————
00101110 diferencia
Multiplicación: El algoritmo del producto en sistema binario es

igual que en números decimales, aunque se lleva cabo con más
sencillez ya que el 0 multiplicado por cualquier número da 0 y el
1 es el elemento unidad del producto, por así decirlo.
29
Por ejemplo, si se multiplica 10110 * 1001:
10110
*1001
—————
10110
00000
00000
10110
—————
11000110
O sea el resultado de multiplicar en el sistema decimal 22*9=

198 decimal.
División: La división en binario es similar a la decimal, la única

diferencia es que a la hora de hacer las restas dentro de
la división estas deben ser realizadas en binario.
Por ejemplo, sea la división binaria siguiente, misma que se sabe

equivale a estar dividiendo 10 en el divisor y 40 en el dividendo y
cuyo resultado por adelantado, es 4 en el cociente y 0 en el
residuo.
1 00
1010 101000
1010
______
0000 00
30
Con el divisor a la vista se busca en el dividendo aquella

cantidad igual o inmediata superior a este, que vale 10
decimal. Esa cantidad se encuentra en los primeros cuatro
dígitos binarios del dividendo, partiendo de izquierda a
derecha. Entonces el primer valor del cociente se vuelve 1 y
multiplicando este valor por el divisor, actuando en el modo de
resta con los cuatro primeros dígitos del dividendo.
Posteriormente, se baja uno a uno cada digito del dividendo
hasta igualar o alcanzar el valor del divisor. Por cada digito del
dividendo que no alcance esta condición, habrá de producir
un cero en el cociente. Esta situación sucede dos veces en
nuestro ejercicio, lo que genera dos dígitos cero en el cociente y
arrojando un residuo de 0.
Octal:
Suma: Se empieza a sumar de la columna derecha a la

izquierda y luego se procede sumar los dígitos que se
encuentran en la primera columna y se coloca el resultado
debajo de la misma.
En caso de que la suma exceda la base del sistema, se restan 8

y se coloca un acarreo en la siguiente columna, el valor del
acarreo depende de las veces que haya superado la base del
sistema y el valor que se obtiene de la resta se coloca debajo
de la columna.
31
Ejemplo:
1 1 1 (fila que muestra los unos de arrastre)

740352
+24567
_________
765141
Un procedimiento alternativo y muy práctico se aplica para los

tres tipos de operaciones siguientes.
Este consiste en obtener el equivalente binario del minuendo

(fila superior) y del sustraendo (fila inferior) y una vez obtenido el
resultado, se realiza la conversión correspondiente al sistema
origen del problema.
Resta:
Sea por ejemplo la operación siguiente:
1230
- 653
_______
103
El equivalente binario sería
1010011000
-110101011
__________
1 000 011 equivale a 103 octal en grupo de 3 dígitos de
derecha a izquierda.
32
Multiplicación: Se aplica el mismo procedimiento simple de

conversión hacia el sistema binario de los datos involucrados.
Por ejemplo, la operación octal siguiente.
123
* 16
2212
Es decir
1010011
* 1110
0000000
1010011
1010011 después de los productos binarios
1010011 se procede a la suma binaria
10 010 001 010
Y reagrupando en paquetes de tres dígitos de derecha a

izquierda, obtenemos: 2212.
División: La división octal y siguiendo con el mismo

procedimiento de conversión de los datos hacia el sistema
binario, se tiene por ejemplo la operación octal siguiente:
40 230
33
La conversión equivalente al sistema binario se muestra a

continuación y procediendo a la división binaria se obtiene:
100
100000 10011000
100000
________
00011000
Que equivale al cociente 4 octal con residuo de 30 octal.
Suma Hexadecimal: De la misma manera, existe mucha similitud

que con el sistema octal, primeramente, se convierte el
minuendo y el sustraendo a su equivalente binario y
posteriormente se regresa el resultado al sistema origen del
problema planteado.
Sea por ejemplo la suma de
17A
+3C
_____
1B6
El resultado obtenido con el procedimiento descrito se muestra

a continuación.
1 0111 1010
+ 11 1100
___________
1 1011 0110 (1B6 hexadecimal)
34
Que equivale en paquete de cuatro dígitos de derecha a

izquierda al resultado mostrado en la operación inmediata
anterior.
Resta Hexadecimal: El mismo procedimiento de conversión al

sistema binario y la aplicación de la resta en dicho sistema.
Ejemplo:
17 A
-3C
_____
13E
Convirtiendo se tiene:
101111010
- 111100
__________
1 0011 1110 (13 C hexadecimal)
Que equivale en paquete de cuatro dígitos al resultado

mostrado en la operación anterior.
Multiplicación Hexadecimal: El mismo procedimiento de

conversión al sistema binario y la aplicación de la multiplicación
en dicho sistema.
Ejemplo:
34D
*A
________
2102
35
Convirtiendo se tiene
1101001101
* 1010
____________
0000000000
1101001101
000000000
1101001101
________________
10 0001 0000 0010 (2102 decimal)
Que equivale en paquete de cuatro dígitos al resultado

mostrado en la operación anterior en sistema hexadecimal.
División hexadecimal: De la misma manera que en el sistema

octal, se puede proceder previamente a la conversión de los
datos en su equivalente binario para resolver el problema y
después el resultado transformarlo de nuevo al sistema numérico
original.
Sea por ejemplo la división hexadecimal
A9 7BD
36
Su equivalente binario se vería como sigue
1 011
10101001 111 1011 1 101
- 101 0101
100111 010
- 10101001
100100011
- 10101001
1111010
Equivalente a un cociente de B y un residuo de 7A y que en

sistema decimal significaría dividir 169 entre 1981 con un residuo
de 122.
1.4 Aplicación de los sistemas numéricos en la

computación
Binario: El sistema binario se aplica para todos los

microprocesadores en los cuales, tiene el trabajo de ordenar
encendido y apagado a los pines de un integrado. También
sirve para almacenar grandes volúmenes de información como:
 Imágenes
 Textos
 Códigos
37
Las telecomunicaciones y redes de computadoras son

aplicaciones de este sistema, ya que se ocupa para la
transmisión, encriptación y desencriptación de datos.
Octal: El sistema de numeración octal es muy usado en la

computación por tener una base que es potencia exacta de 2.
En informática, a veces se utiliza la numeración octal en vez de
la hexadecimal y tiene la ventaja de que no requiere utilizar
otros símbolos diferentes de los ya utilizados por el sistema
decimal.
Decimal: Naturalmente se utiliza el sistema numérico decimal

para indicar magnitudes o cantidades, el sistema consta de diez
símbolos llamados cifras, que son: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. El
sistema numérico decimal es el sistema de uso y conocimiento
universal por excelencia y tiene todos los usos posibles,
expresando cantidades y dimensiones tales como dinero, peso,
longitud, temperatura, superficies, velocidad, capacidad,
proporcionalidad, etc.
Hexadecimal: Conforme los ordenadores y programas

aumentan su capacidad de procesamiento, van aumentando
con múltiplos de ocho, como 16 o 32. Por este motivo, el sistema
hexadecimal es un estándar en la informática en el proceso de
dimensionar y manipular cantidades cada vez mayores.
38
En términos muy generales, pudiera considerarse infinita la

cantidad de aplicaciones en donde intervienen los sistemas
numéricos, toda vez que vivimos en una era digital en donde el
uso de las computadoras y los sistemas y tecnologías de
software, han invadido prácticamente todos los campos de la
ciencia.
39
Ejercicios propuestos y solución a problemas nones.
1.- Convierta la cantidad octal 317 a su equivalente decimal y

hexadecimal.
Respuesta: Sea 317 octal, se convierte digito a digito y de derecha a

izquierda a su equivalente binario.
11 001 111 y luego se potencia a la dos y de derecha a izquierda para

obtener la sumatoria 1 + 2 + 4 + 8 + 64 + 128 = 207 decimal.
Ahora la conversión hacia el sistema hexadecimal, procede a partir de la

misma equivalencia binaria, es decir 11001111 y agrupando en grupo de
cuatro dígitos de derecha a izquierda, se obtiene: CF
2.- Convierta la cantidad 45A hexadecimal a su equivalente decimal.
3.- Retomando el ejercicio uno, compruebe que 207 decimal, equivale a

317 octal. Respuesta: se toma la cantidad 207 y mediante divisiones
sucesivas entre dos se obtiene el equivalente binario.
207 2 De abajo hacia arriba se tiene

11001111 y luego agrupando en
grupo de tres dígitos de derecha
izquierda 237 octal.
103 1
51 1
25 1
12 1
6 0
3 0
1 1
0 1
40
4.- Convierta la cantidad binaria a su equivalente octal, decimal y

hexadecimal. 1001010000101
5.- Conversión del número decimal 28 a binario, octal y hexadecimal.

Respuesta. Apoyándonos con la tabulación siguiente, se tiene.
Sistema de numeración Base Ejemplo (número decimal 28) Resultado

Binario 2 1x 24 + 1x 23 + 1x 22 + 0x 21 + 0x20 11100
Octal 8 3x 81 + 4x 80 34
Decimal 10 2x 101 + 8x 100 28
Hexadecimal 16 1x 161 + 12x 160 1C
6.- Obtenga la suma binaria de las cantidades siguientes:
1011001 100000 1111000

+110001 + 10111 + 11111
7.- Calcule los productos binarios siguientes:

100011 10001
X 101 x 1010
100011 00000
000000 10001
100011 00000
____________ 1 00 01
1 0 10 1 1 1 1 _______________
1 01 0 1010
8.- Obtenga la resta correspondiente ente los números octales: 550–270
9.- Obtenga la resta o diferencia correspondiente entre los números

octales: 500–200. Respuesta. Convertimos a su equivalente binario en
grupos de tres dígitos y de derecha a izquierda.
41
101000000–10000000 y aplicamos las reglas del sustraendo binario,

obteniendo 011000 000 y reagrupando en paquete de tres dígitos y de
derecha a izquierda tenemos ahora: 300
10.- Obtenga el resultado de las divisiones binaria y hexadecimal
correspondientes:
a) 10001 / 1001 b) 122 / A
42
UNIDAD II
CONJUNTOS
Y
RELACIONES
44
 RESOLVER PROBLEMAS QUE IMPLIQUEN LAS OPERACIONES

Y LAS PROPIEDADES DE CONJUNTOS.
 CAPACIDAD PARA INTERPRETAR Y APLICAR LA TEORÍA DE

CONJUNTOS EN LA PRÁCTICA.
 CAPACIDAD DE ABSTRACCIÓN AL HABLAR DE LOS

CONCEPTOS DE CONJUNTOS Y LAS MAGNITUDES CAPACES
DE REPRESENTAR MEDIANTE SU USO.
 CAPACIDAD ANALÍTICA EN LA RELACIÓN DEL TEMA CON

ENFOQUE ALGORÍTMICO.
45
2.1 Características de los conjuntos y subconjuntos
Primeramente, hay que definir a un conjunto como cualquier

colección de objetos que pueda tratarse como una entidad. A
cada objeto de la colección se le llamará elemento o miembro
de ese conjunto.
Notación:
1.- Normalmente, se usan las letras mayúsculas para representar

a un conjunto y minúsculas para representar a sus elementos.
Ejemplo:
2.- Los elementos que forman a un conjunto se encierran entre

llaves y cada elemento se separa con un coma ( , ).
3.-El orden de sus elementos es irrelevante.
Ejemplo:
4.- La repetición de uno o más de los elementos de un conjunto

es irrelevante.
46
Ejemplo:
5.- Forma de representar a un conjunto:
1) Por enumeración de sus elementos.
2) Por especificación de una o más propiedades que tienen sus

elementos.
Ejemplos:
El conjunto de x tal que x es un digito.
C= {2,4,6,8,…,100}
Conjuntos especiales: Indudablemente son:
Conjunto universo. Denotado por U.
Conjunto vacío. Denotado por { }.
47
Cardinalidad: Al conjunto de elementos que tiene un conjunto

cualquiera “A” se le llama cardinalidad del conjunto.
Notación: |A|= Cardinalidad de A.
Un subconjunto, propiamente dicho es un conjunto cuyo uno

más elementos pertenecen a otro conjunto en cuestión.
2.2 Operaciones de conjuntos
Sean las operaciones siguientes.
1.- Intersección:
Si A y B son conjuntos la intersección de A con B, es otro

conjunto, formado por los elementos que son comunes a ambos
conjuntos.
Notación:
Ejemplo 1:
U = { 0, 1, 2, 3, … 9 }
A= { 0, 2, 4, 6, } dígitos pares.
B= { 1, 3, 5, 7, 9 } dígitos nones.
O simplemente { }
48
Ejemplo 2:
¿En dónde intersecta el conjunto A compuesto por los primeros

diez números de Fibonacci con el conjunto universo U?
Respuesta: Intersecta en A, dado que los elementos que solo

pertenecen al conjunto A son también parte del universo U.
2.- Unión:
En la teoría de conjuntos, la unión de dos o más conjuntos, es

una operación que resulta en otro conjunto, cuyos elementos
son los mismos de los conjuntos iniciales.
Notación:
Así partiendo del ejemplo anterior, el resultado de la unión sería:
A U B = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
3.- Complemento:
Sean U el conjunto universal y A un conjunto formado

(contenido) en U ó sea, . La diferencia U - A, o un conjunto
formado por los elementos de U que no están en A.
Ejemplo:
A= { 3, 5, 7, 9 } y U = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
49
De donde Ac = { 1, 2, 4, 6, 8 }
Al conjunto formado por todos los subconjuntos de un conjunto

A se le llama conjunto potencia. I P I
Por ejemplo, sea el conjunto M = { p, q, r }, el conjunto potencia

de M sería Ι P(M) Ι = { {p}, {q},{ r}, { p,q }, { p,r }, { q,r }, { p, q, r }, { } }
Notación:
4.- Diferencia:
Si A y B son conjuntos, la diferencia: A - B será otro conjunto

conformado por los elementos de A que no están en B.
Notación:
Ejemplo:
Sea el conjunto A = { 1, 2, 3, 5, 9 } y sea el conjunto

B = { 8, 2, 3, 7, 4 }
A – B = { 1, 5, 9 } y por lo tanto B – A = { 4, 7, 8 }
Podemos ver claramente que la operación NO es conmutativa.
Diferencia simétrica:
La diferencia de A y B es el conjunto que contiene todos los

elementos del conjunto A y del conjunto B, salvo aquellos que
pertenecen a ambos. Se denota por Δ.
50
Ejemplo:
Sea el conjunto A = { 4, 6, 8, 10 } y sea B = { 4, 8, 12, 16, 20 }
A ∆ B = { 6, 10, 12, 16, 20 }
2.3 Propiedades y aplicaciones de los conjuntos
Propiedades de unión.
Asociativa: Si en una unión de tres o más conjuntos se

reemplazan dos conjuntos por su unión efectuada, se obtiene el
mismo resultado.
R∪S∪T=(R∪S)∪T
R∪S∪T=R∪(S∪T)
Conmutativa: Si en una unión se altera el orden de los conjuntos,

el resultado no varía.
R∪S∪T=S∪R∪T
R∪S∪T=T∪R∪S
Propiedades de la intersección
Asociativa: Si en la intersección de tres o más conjuntos se

reemplazan dos de ellos por su intersección efectuada, el
resultado final es el mismo.
51
R∩(S∩T)=(R∩S)∩T
Conmutativa: cambiando el orden de los conjuntos, la

intersección no se altera.
R∩S∩T=R∩T∩S
R∩S∩T=T∩R∩S
Distributiva:
La unión es distributiva con respecto a la intersección.
(R∩S)∪T=(R∪T)∩(S∪T)
La intersección de conjuntos es distributiva con respecto a la

unión.
(R∪S)∩T=(R∩T)∪(S∩T)
Propiedades de la diferencia
La diferencia de conjuntos no es asociativa, ni conmutativa.
Aplicaciones de Conjuntos
Los objetos del conjunto pueden ser cualquier cosa: personas,

números, colores, letras, figuras, etc. Cada uno de los objetos en
la colección es un elemento o miembro del conjunto.
52
Ejemplo: El conjunto de los colores del arcoíris es:
A = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}
Un conjunto suele definirse mediante una propiedad que todos

sus elementos poseen.
Ejemplo: Para los números naturales, si se considera la

propiedad de ser un número primo, el conjunto de los números
primos es:
P = {2, 3, 5, 7, 11, 13, …}
Un conjunto queda definido por los miembros que lo componen.
En particular, un conjunto puede escribirse como una lista de

elementos, pero cambiar el orden de dicha lista o añadir
elementos repetidos no define un conjunto nuevo.
Ejemplo:
Sea S = {lunes, martes, miércoles, jueves, viernes} =
{martes, viernes, jueves, lunes, miércoles}
Sea C = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} =
{Amarillo, Naranja, Rojo, Verde, Violeta, Añil, Azul}
53
Los conjuntos pueden ser finitos o infinitos. El conjunto de los

números naturales es infinito, pero el conjunto de los planetas en
el Sistema Solar es finito (aceptando ocho elementos). Además,
los conjuntos pueden combinarse mediante operaciones, de
manera similar a las operaciones con números.
Los conjuntos son un concepto primitivo, en el sentido de que no

es posible se definin en términos de nociones más elementales,
por lo que su estudio puede realizarse de manera informal,
apelando a la intuición y a la lógica.
Por otro lado, son el concepto fundamental de la matemática:

mediante ellos puede formularse el resto de objetos
matemáticos, como los números y las funciones, entre otros.
Su estudio detallado requiere la introducción de axiomas y
conduce a la teoría de conjuntos.
2.4 Conceptos básicos: producto cartesiano y relación

binaria
El producto cartesiano de dos conjuntos cualesquiera A y B, será

un nuevo conjunto, identificado como A x B y consistirá de un
conjunto de parejas ordenadas, (x, y), donde x pertenece al
conjunto A e y pertenece al conjunto B.
54
Expresión extensiva de un producto cartesiano
Sean los conjuntos A y B.
A = {a, b, c}
B = {m, n, o}
El producto cartesiano A x B estará definido como:
A x B = {(a,m), (a,n), (a,o), (b,m), (b,n), (b,o), (c,m), (c,n), (c,o)}
El producto cartesiano B x A estará definido como:
BxA = {(m,a), (m,b), (m,c), (n,a), (n,b), (n,c), (o,a), (o,b), (o,c)}
Expresión gráfica de un producto cartesiano
Las parejas ordenadas representarán puntos coordenados en el

plano, tomando como primera coordenada un elemento del
primer conjunto y como segunda coordenada a un elemento
del segundo conjunto, independientemente que sean números
u otras entidades.
En la siguiente gráfica se ilustra el desarrollo gráfico del producto

cartesiano A x B:
55
Gráfica 2.1 Producto cartesiano A x B
Se puede comparar con el desarrollo gráfico del producto

cartesiano B x A, referido anteriormente:
Gráfica 2.2 Producto cartesiano B x A
56
Por lo que respecta a la relación binaria definida en un conjunto

A, es un subconjunto del producto cartesiano A x A.
Por ejemplo, sea el conjunto A={y,z,w}, constituyen un

subconjunto de A x A y el grafo siguiente representa una
relación binaria definida en A, puesto que los pares (z, y) (w, y)
(w, z) constituyen un subconjunto de A x A, se dice que dos
elementos cualesquiera a y b están relacionados y se escribe
a R b “a está relacionado con b, mediante la relacion binaria
R“.
z w
Figura 2.1 relación binaria definida en A
2.5 Representación de las relaciones
Un conjunto suele definirse mediante una propiedad que todos

sus elementos comparten.
Por ejemplo, para los números naturales, si se considera la

propiedad de ser un número primo, el conjunto de los números
primos es:
P = {2, 3, 5, 7, 11, 13, …, n primo}
57
Un conjunto queda definido únicamente por sus miembros y

nada más. En particular, el orden en el que se representen es
irrelevante. Además, cada elemento puede aparecer de
manera idéntica una sola vez, esto es, no puede haber
elementos totalmente idénticos repetidos.
2.6 Propiedades de las relaciones
Relación
Una relación es la correspondencia entre los elementos de dos

conjuntos que forman parejas ordenadas. Cuando se formula
una expresión que liga dos o más objetos entre sí, se conoce
como una relación, como las que definiremos a continuación.
Relación reflexiva
Una relación R en un conjunto A es reflexiva si (a, a) £ R para

todas las a £ A, esto es, si a R e para todas las a e A.
Ejemplo: Sea Δ = [(a, a) \ a £ A], de modo que A es la relación

de igualdad en el conjunto A. Entonces A es reflexiva, ya que (a,
a) £ Δ para todas las a e A.
Relación antireflexiva
Una relación R en un conjunto A es irreflexiva si a R a para toda

a £ A.
58
Ejemplo: Sea R = {(a, b) e A x A | a + b}, R es la relación de

desigualdad en el conjunto A. Entonces R es irreflexiva, ya que
(a, a) £ R para todas las x € A.
Relación simétrica
Si cuando un elemento está relacionado con un segundo

elemento, el segundo también se relaciona con el primero, con
símbolos: (x, y) ∈ R ⇒ (y, x) ∈ R
Relación Antisimétrica
Cuando una relación es lo opuesto a una simétrica, es decir,

cuando se da el caso que un elemento está relacionado con
otro mediante R, entonces ese otro no está relacionado con el
primero, entonces se habla de una relación antisimétrica; es
decir x R y, pero y ~R x. En donde ~ denota la negación.
Relación Transitiva
Se dice que una relación R en un conjunto A es transitiva si

cuando (a R b) y (b R c), entonces (a R c). Se dice que R no es
transitiva si y sólo si se puede encontrar un elemento a, b y
c, en A tal que (a R b) y (b R c), pero también (a R c).
2.7 Relaciones de equivalencia
Una relación de equivalencia es reflexiva, simétrica y transitiva.

Un ejemplo claro, puede ser la equivalencia lógica, la igualdad
59
de conjuntos o la relación entre conjuntos de tener la misma

cardinalidad.
Por ejemplo, si consideramos el conjunto de los polígonos

regulares y la relación de semejanza, en la que un polígono se
relaciona con otro si tienen el mismo número de lados, sus
ángulos respectivos son iguales y sus lados proporcionales,
primero es una relación reflexiva, pues un polígono es semejante
a sí mismo, luego es simétrica, pues si un polígono es semejante
a otro, el otro lo es al uno ya que los ángulos son iguales y los
lados proporcionales con el factor de proporcionalidad inverso
del primero y por último, si un polígono es semejante a un
segundo y este a un tercero, el primero es semejante al tercero,
pues tienen el mismo número de lados, ángulos iguales y lados
proporcionales con factor el producto de los dos factores
originales.
Esto genera el teorema siguiente, que dice que: Si R es

una relación de equivalencia en un conjunto de A entonces R
particiona al conjunto A en subconjuntos disjuntos llamados
clases de equivalencia.
Una partición de un conjunto está formada por subconjuntos

disjuntos o sea ningún elemento aparece en dos conjuntos, tal
que la unión es igual al conjunto original.
60
Una relación de equivalencia sobre un conjunto C es

una relación R que cumple las siguientes propiedades:
Reflexiva. ∀a ∈ C; a R a
Simétrica. ∀a, b ∈ C; a R b ⇔ b R a
Transitiva. ∀a, b, c ∈ C; (a R b) ∧ (b R c) ⇒ (a R c)
En algunas ocasiones, una relación no cumple alguna de las

propiedades de equivalencia, pero hay relaciones que la
incluyen y que si cumplen la propiedad de todas las relaciones y
la menor posible se llama cerradura.
Clases de Equivalencia
Sea R una relación de equivalencia sobre un conjunto A. Para

cada a ∈ A, llamaremos clase de equivalencia de a, al conjunto
formado por todos los elementos de A que estén relacionados
con él. La denotaremos como [a], es decir, [a] = {x ∈ A : x R a}.
Obsérvese que la clase de equivalencia de un elemento a
nunca es vacía, ya que la reflexividad de R implica que a ∈ [a].
Al conjunto de los elementos del conjunto A que están
relacionados con él se llama clase de equivalencia.
Sea, por ejemplo, la relación a - b = 2 k (múltiplo de 2), siendo a

y b números enteros es una relación de equivalencia porque
cumple las propiedades: Reflexiva: a - a =0 =2 k (k =0). Simétrica:
61
a-b=b-a porque b-a=-(a - b). Si a-b es múltiplo de 2, -(a-b)

también lo será. Transitiva: a-b=2 k1, b-c=2 k2. Sumando queda
a-c=2 k3, entonces a-c es múltiplo de 2. En el ejemplo anterior,
la clase de equivalencia del número cero (uno de los elementos
del conjunto de los números enteros) C(0)={... -4, -2, 0, 2, 4, ...},
pues 0-(-4) es múltiplo de 2, 0-(-2) es múltiplo de 2 y así
sucesivamente. La clase de equivalencia del número 1 será C(1)
= {... -5, -3, -1, 1, 3, 5, ...} pues la diferencia entre 1 y los números
indicados es múltiplo de 2.
2.8 Funciones
Euler fue el primero en emplear la expresión f(x) para representar

una función f asociada a un valor x. Es decir, con esta
representación que es empleada actualmente, refiere a la
utilización del concepto de función tal y como hoy se entiende.
Es uno de los conceptos más importantes en Matemáticas, ya

que se puede aplicar en numerosas situaciones de la vida
cotidiana y determinar las relaciones que existen entre
magnitudes de Matemáticas, Física, Economía, etc., para citar
algunos ejemplos y poder calcular el valor de una de ellas en
función de otras de las que depende.
Las funciones también se consideran herramientas para

relacionar elementos de un conjunto, llamado inicial, con
elementos de otro conjunto, llamado final. El concepto es
62
parecido al de relación, donde se relacionan elementos de un

conjunto entre sí. Sin embargo, hay una diferencia esencial, ya
que en una función se exige que cada elemento del conjunto
inicial esté relacionado sólo con uno del conjunto final. La
consecuencia inmediata es que la inversa de una función (es
decir, los elementos del conjunto final asociados con los que les
corresponden de la inicial) no es, en general, una función; así
podemos utilizar las funciones como herramientas para asignar
a cada elemento de un conjunto un elemento de otro. Como
en el caso de las relaciones, vamos a expresar esta asignación
por parejas, pero ahora formadas por un elemento del conjunto
inicial y un elemento del conjunto final. Como se ha dicho, se
exige además que a cada elemento del conjunto inicial no se le
asigne más de uno del final.
En una función f, el conjunto A se llama inicial, y el conjunto B,

final y se denotan con el símbolo f: A ⇒ B.
Ejemplo: Sea A = {a, b, c} y consideremos los subconjuntos de:
A×A, f={(a, a), (b, b), (b, c)}, g={(a, b), (b, c), (c, a)}, h={(a, a), (b,
a)}.
63
Los tres conjuntos son relaciones en A, pero f no es una función

porque el elemento b aparece como primer elemento en dos
parejas. Sin embargo, g y h sí son funciones.
2.9 Aplicaciones de las relaciones y funciones en la

computación
Pudieran ser tan extensas las aplicaciones y muy difícil de enlistar

tantas, pero como referencia se tienen algunos ejemplos como
una función en cinemática, en donde el problema consiste en
expresar la relación entre el espacio recorrido y el tiempo
invertido en ello. También la función que representa el espacio
recorrido por un móvil, con velocidad uniforme que parte del
reposo e(t )=v*t y que es una función del tipo f(x)=m*x.
Otro problema muy común y de uso muy estudiado, es el

lanzamiento de proyectiles. Las funciones son de tipo
cuadrática de la forma y=ax2+bx+c. Por ejemplo, si se quiere
calcular la distancia que alcanza un objeto que es lanzado
hacia arriba con una inclinación determinada α y una
velocidad inicial de lanzamiento v0, en función del tiempo, se
puede representar de forma gráfica y algebraica: x = x0 + v0xt
y = y0 + v0yt − gt2
vx = v0 x
vy = v0y – gt
64
Según las magnitudes que se quieran relacionar, las expresiones

tanto gráficas como algebraicas serán las adecuadas:
También por la ley de Hooke F=K*X se puede determinar por

medio de una tabla de valores o por una gráfica la fuerza o
peso que se debe aplicar para que el muelle se desplace una
cierta distancia.
Por ejemplo, si se tiene un muelle con una constante de

elasticidad k=0.5, podemos ir representando la relación entre las
magnitudes fuerza-distancia y su ecuación es de la forma
f(x)=a*(1−e–bx) con a>0.
Una aplicación más cotidiana de las funciones, sería en bancos

y su correspondiente registro, donde a cada persona se le
asigna únicamente un solo número de identificación y sólo a
esa persona le corresponde tal número.
Otro ejemplo, sería en las escuelas, donde a cada estudiante le

corresponde un grupo conforme a su carrera, pero solamente
uno a la vez. Esta combina las dos anteriores, donde no debe
haber elementos solos en B y pueden corresponderle uno o más
elementos de A.
65

1. Sea A el conjunto compuesto por los dígitos del sistema octal y sea B
el conjunto de los dígitos del sistema hexadecimal, obtenga la
diferencia simétrica en .
Respuesta. Esta contiene los elementos que contiene a A o B, pero
no a ambos, por lo tanto se tiene que F={A,B,C,D,E,F}, siendo A…F,
elementos del sistema numérico hexadecimal, pertenecientes a B,
pero no a A.
2. Sean los subconjuntos finitos A y B del conjunto universal U, investigue
y demuestre el principio de adición.
3. Una empresa de software, necesita emplear a 10 diseñadores de
sistemas y 15 para diseñadores de bases de datos; de estos futuros
empleados se busca que 5 realicen ambas tareas. Cuantos
programadores deberá contratar dicha empresa.
Respuesta: ΙAΙ = 10, ΙBΙ= 15 ΙABΙ. Es decir, el resultado se

obtiene de la unión de A y B, menos la intersección de A y B.
Esto resulta en 10+15–5=20, como el número de personas que se
deberán contratar.
4.- En donde intersectará el conjunto C={0,1} con el conjunto { }.
5.- Sea el conjunto A = {1,2,3,4} y sea la partición del mismo {{1,2,3},{4}},
determine la relación de equivalencia correspondiente R en A.
Respuesta: ya que las clases de equivalencia de los elementos de A
son los bloques de la partición, se tiene que [1]={1,2,3} y [4]={4},
entonces se dice que (1,1), (1,2), (2,1), (2,2), (1,3), (3,1), (2,3), (3,2),
(3,3)€R y de igual manera (4,4)€R y de aquí que:
R = {(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3),(4,4)}
6.- Sea el conjunto A = {a,b,c,d} y sea R la relación simétrica, tal que R =
{(a,b),(b,a),(a,c),(c,a),(a,d),(d,a)}, dibuje el grafo de R.
66
7.-Reescriba al siguiente conjunto B={1,2,3,4,5,6,7,8,9}, en notación

específica P(x), es decir, en función de una o más propiedades
matemáticas que este contenga exhaustivamente.
Respuesta: B={x Ι tal que x es un entero positivo menor que 10}
8.- Obtenga el conjunto potencia del conjunto B del ejercicio anterior.
9.- Sean los conjuntos A={2,4,6,8} y B={x,y,z,w} y sea
f={(2,x),(4,x),(6,w),(8,z), determine si f es una función. Respuesta si lo
es, en virtud de que ningún elemento de A aparece como primer
elemento de dos pares ordenados diferentes.
10.- Sean los conjuntos disjuntos M={10,20,30,40} y N={15,25,35,45},
verifique el teorema del principio de adición siguiente
ΙAUBΙ=ΙAΙ+ΙBΙ-ΙAΙ.
67
UNIDAD III
LÓGICA
MATEMÁTICA
68
 COMPRENDER LAS BASES DE LA LÓGICA MATEMÁTICA,

PARTIENDO DE LAS OPERACIONES BÁSICAS,
DESARROLLANDO UN NIVEL DE ABSTRACCIÓN QUE LE
PERMITA AL ALUMNO INTERACTUAR CON OPERACIONES
MÁS COMPLEJAS POR INDUCCIÓN MATEMÁTICA.
 CAPACIDAD DE SOLUCIÓN DE PROBLEMAS.
 CAPACIDAD DE APLICAR LOS CONOCIMIENTOS

ADQUIRIDOS.
 AUTOEVALUAR SUS CAPACIDADES ANALÍTICAS Y LÓGICAS.
 TRASCENDER A NUEVAS PLATAFORMAS DE CONOCIMIENTO

CON ENFOQUE ALGORÍTMICO.
 ADQUIRIR MAYOR POTENCIAL DE ANÁLISIS LÓGICO

MATEMÁTICO.
 CAPACIDAD DE PERCEPCIÓN EN EL PROCESO SIMPLE DEL

CONOCIMIENTO COGNITIVO QUE INVOLUCRA ATENCIÓN,
MEMORIA Y APRENDIZAJE QUE TIENE QUE VER CON LA
INTELIGENCIA, EL LENGUAJE Y EL PENSAMIENTO.
69
3.1 Lógica proposicional
La lógica proposicional específicamente trata sobre la verdad o

la falsedad de las proposiciones y de cómo la verdad se
transmite de unas proposiciones, digamos premisas a otras
concluyentes. Visto así, una proposición es la unidad mínima de
significado susceptible de ser falsa o verdadera.
Una palabra aislada, por sí misma, nos dice poco. Por ejemplo,
la palabra roca, nos dice muy poco y aunque tiene una
referencia nos dice poco; sin embargo, decir la roca es muy
antigua, ya constituye una proposición que da lugar a que esta
sea falsa o verdadera.
Existen dos tipos de proposiciones: las proposiciones atómicas y

las proposiciones moleculares. Las proposiciones atómicas son
aquéllas que no se componen de otras proposiciones. Por
ejemplo, la proposición todos los hombres son mortales es una
proposición atómica porque ninguno de sus elementos
componentes es una proposición. Como se puede observar,
una proposición atómica es verdadera o falsa y su verdad o
falsedad no depende de otras proposiciones, sino de cómo es
la realidad. Si hubiera algún hombre inmortal, la proposición del
ejemplo sería falsa.
En cambio, las proposiciones moleculares son aquéllas que

están compuestas por proposiciones atómicas. Un ejemplo de
70
proposición molecular sería: Voy a leer un libro y a tomar un

café. La proposición del ejemplo es molecular porque se
compone de dos proposiciones atómicas:
1.- Voy a leer un libro y 2.- Voy a tomar un café. Estas dos
proposiciones atómicas están conectadas mediante la
conectiva "y". Una proposición molecular será verdadera o falsa,
pero a diferencia de lo que ocurre con las proposiciones
atómicas, su verdad o falsedad no depende directamente de
la realidad, sino que depende o es función de la verdad o
falsedad de las proposiciones atómicas que la componen. Esto
significa que si quiero saber si es verdadero o falso que voy a
leer un libro y a tomar un café, es necesario que conozca la
verdad o falsedad de "voy a leer un libro" y de "voy a tomar un
café" por separado.
3.1.1 Proposiciones simples y compuestas
Después de vertidos los conceptos anteriores, se puede decir

que las proposiciones atómicas se conocen también como
simples y las moleculares como compuestas; es decir, son
también una oración que puede ser falsa o verdadera pero no
ambas a la vez.
Adicionalmente, toda proposición consta de tres partes: un

sujeto, un verbo y un complemento referido al verbo. La
71
proposición es un elemento fundamental de la lógica

matemática.
A continuación, se tienen algunos ejemplos de proposiciones

válidas y no válidas, se explicará por qué algunos enunciados
no son proposiciones. Las proposiciones se indican por medio de
una letra minúscula, dos puntos y la proposición propiamente
dicha.
Ejemplos:
p: México no se encuentra en Europa

q: 15–6=9
r: 2x –3>7
s: Los precios de los teléfonos celulares bajaran a fin de año
t: Hola, ¿Cómo estás?
w: ¡Comete esa fruta!
Los enunciados p y q pueden tomar un valor falso o verdadero,
por lo tanto, son proposiciones válidas. El inciso r también es una
proposición valida, aunque el valor falso o verdadero depende
del valor asignado a la variable x en determinado momento. La
proposición del inciso s también está perfectamente expresada,
aunque para decir si es falsa o verdadera se tendría que esperar
a que terminara el año.
72
Sin embargo, los enunciados t y w no son válidos, ya que no

pueden tomar un valor de falso o verdadero; uno de ellos es un
saludo y el otro es una orden.
En general las proposiciones pueden ser:
 Simples si solo tienen un sujeto, un verbo y un compuesto.

En caso contrario, son proposiciones compuestas.
 Cerradas si tienen determinado al sujeto y abiertas si no lo
tienen determinado.
 Afirmativas o negativas según lo afirmen o lo nieguen.
 Verdaderas o falsas según correspondan o no a la
realidad.
Existen conectivos u operadores lógicos que permiten formar
proposiciones compuestas, es decir, formadas por varias
proposiciones. Los operadores o conectores básicos son:
Conjunción
(Operador AND) Se utiliza para conectar dos proposiciones que

se deben cumplir para que se pueda obtener un resultado
verdadero y su símbolo es ∧ y muchas veces simplemente el
vacío (A B), implicando la operación por mero
convencionalismo e igualmente para la disyunción.
Ejemplo: Sea el siguiente enunciado: ”Voy al cine cuando hay

una buena película y cuando tengo dinero”.
73
Sea por ejemplo:

p: tengo dinero.
q: hay una buena película.
Su tabla de verdad queda como sigue:
p Q p^q
v v v
v f f
f v f
f f f
Tabla 3.1 Conjunción lógica
Donde: v = Verdadero y f = Falso
En la tabla anterior el valor de q = v significa que hay una buena

película, p = v significa que tengo dinero y q ^ r = v significa que
voy a ir al cine. Se puede notar que con cualquiera de las dos
proposiciones que valga f implica que el resultado es no
asistencia al cine.
También se puede trabajar con ceros y unos, interpretándose

que f=0 y v=1, como falso y verdadero respectivamente.
Disyunción:
Si p y q son dos proposiciones cualesquiera (or lógico), la

disyunción de p y q es la proposición que se lee “p o q” y se
simboliza como v. El valor de verdad de la proposición p v q
está determinada por el valor de verdad de las proposiciones p
y q.
74
p Q p vq
v v v
v f v
f v v
f f f
Tabla 3.2 Disyunción lógica.
Ejemplo:
La disyunción de la proposición “5 es menor que 4” y la

proposición “2+4=8”, se obtiene la proposición “5 es menor que
4 o 2+4=8”. Como la proposición “5 es menor que 4” es
verdadera y la proposición “2+4=8” es falsa, la proposición
compuesta “5 es menor que 4 o 2+4=8” es falsa, en cualquier
otro caso será verdadera.
Condicional:
Si p y q son dos proposiciones cualesquiera, el condicional de p

y q es la proposición que se lee “Si p entonces q” y se simboliza
p→q. El valor de verdad de la proposición p→q está
determinada por el valor de verdad de las proposiciones p y q
según la siguiente tabla:
p Q p→q
v v v
v f f
f v v
f f v
Tabla 3.3 Operación lógica condicional.
75
En el condicional p→q, la proposición p se llama antecedente y

la proposición q se llama consecuente. Existen otras formas de
leer ambas proposiciones.
p implica q.
p solo si q.
q es condición necesaria para p.
p es condición suficiente para q.
Ejemplos:
1.- Me alegraría mucho, si me acompañaras.
2.- Si quieres, paso por ti a las seis.
3.- Te llevaré al baile; si me prometes ser puntual.
4.- Si pones atención, aprenderás más pronto.
5.- Podría llevar dos materias, si asisto por las tardes.
Observe cada caso y constata que la proposición indica una

condición para que se lleve a cabo lo aseverado en la oración
principal:
CONDICIÓN
1.- Si me acompañaras
2.- Si quieres
3.- Si me prometes ser puntual
4.- Si pones atención
5.- Si asisto por las tardes
76
ASEVERACIÓN
1.- Me alegraría mucho
2.- Paso por ti a las seis
3.- Te llevaré al baile
4.- Aprenderás más pronto
5.- Podría llevar dos materias
Las proposiciones condicionales funcionan sintácticamente

como modificadores circunstanciales del núcleo del verbo de la
oración principal. La conjunción si, que funciona como
subordinante es el encabezado que aceptan las oraciones
subordinadas condicionales, en la mayoría de los casos. Los
sintagmas conjuntivos; siempre que, con tal que, etc., también
funcionan como cabezales de este tipo de proposiciones.
Bicondicional:
Si p y q son dos proposiciones cualesquiera, el bicondicional de

p y q es la proposición que se lee “p y solo si q” y se simboliza
p↔q. El valor de verdad de la proposición p↔q está
determinado por el valor de verdad de las proposiciones p y q
p Q p↔q
v v v
v f f
f v f
f f v
3.4 Proposición lógica bicondicional.
77
Ejemplos:
Como la proposición “5 es menor que 6” es verdadera y la

proposición “2+4=8” es falsa, la proposición “5 es menor que 6 o
2+4=8” es falsa observar que la proposición “2+4=8 si y solo si 5 es
menor que 6” también es falsa.
Otros ejemplos serían:
1.- 3+2=7, si y solo si 4+4=8
Si se toma p como: 3+2=7 y q como 4+4=8, entonces el valor de

verdad de p es falso, pero el valor de verdad de q es
verdadero, luego entonces la bicondicional p↔ es falsa.
2.- Londres está en Inglaterra si y solamente si, París está en

Francia.
Sea p Londres está en Inglaterra y q París está en Francia,
entonces tanto el valor de p, como de q, son verdaderos, es
decir tienen el mismo valor de verdad, luego entonces la
bicondicional p ↔ q es verdadera.
3.- 10 es un número impar si y solamente si, 6 es un número

primo. Si p es: 10 es un número impar y q es: 6 es un número
primo, entonces se observa que tanto el valor de verdad de p,
como de q, son falsos, es decir tienen el mismo valor de verdad,
luego entonces la bicondicional p ↔ q es verdadera.
78
Negación
Si p es una proposición cualquiera, la negación de p es la

proposición que se lee “no p” y se simboliza ~p. También puede
decirse “es falso que p”. El valor de verdad de la proposición ~p
está determinado por el valor de verdad de las proposiciones p
P ~p
v f
f v
Tabla 3.5 Negación Lógica
Ejemplos:
Como la proposicion “5 es menor que 6” es verdadera, la

proposicion “5 no es menor que 6” es falsa.
La proposicion 3+5<>9 es la negación de la proposicion

3+5=9.
3.1.2 Tablas de verdad
Una tabla de verdad, es una tabla que muestra el valor de

verdad de una proposición compuesta, para cada
combinación de verdad que se pueda asignar.
79
Fueron desarrolladas por Charles Sanders Peirce por los años

1880, pero el formato más popular es el que introdujo Ludwig
Wittgenstein en su tratado lógico–filosófico, publicado en 1921.
En efecto, todas las reglas de verdad funcional que se utilizan

para proposiciones moleculares pueden resumirse en forma de
tabla.
Estas tablas básicas de verdad indican rápidamente si una

proposición molecular es cierta o falsa, si se conoce la verdad a
o falsedad de las proposiciones que la forman.
Se dan a continuación las tablas básicas de verdad para los

cinco términos de enlace de proposiciones. Si se conocen los
valores de verdad de una proposición p y de una proposición q,
se busca la línea que presenta esta combinación particular de
valores de verdad y en la misma línea en la columna de la
proposición molecular se encontrará su valor de verdad.
Verdadero: El valor verdadero se representa con la letra v, si se

emplea notación numérica se expresa con un uno y representa
en un circuito eléctrico que está cerrado.
Falso: El valor falso se representa con la letra f, si se emplea

notación numérica se expresa con un cero y representa en un
circuito eléctrico que está abierto.
80
Tablas de verdad:
Conjunción o producto lógico (AND)
p Q z
f F f
f V f
v F f
v V v
Producto lógico negado (NAND)
p Q z
f F v
f V v
v F v
v V f
Disyunción o suma lógica (OR)
p q z
f f f
f v v
v f v
v v v
Suma lógica negada (NOR)

p q z
f f v
f v f
v f f
v v f
81
Condicional (p → q)
p q z
v v v
v f f
f v f
f f f
Negación Lógica (NOT lógico)
p ˜p
V f
f v
Bicondicional lógico (p ↔ q)
p q z
V v v
V f f
f v f
f f v
3.1.3 Tautología, contradicción y contingencia
Tautología es un término que proviene de un vocablo griego y

que hace referencia a la repetición de un mismo pensamiento a
través de distintas expresiones. Es una afirmación redundante.
En la lógica matemática es una preposición siempre verdadera

independientemente del valor de verdad de sus enunciados.
82
No es como podría pensarse, un inútil objeto de lujo en la lógica

matemática. Desempeñan un papel importante en esta, ya que
se consideran leyes en las cuales nos podemos apoyar.
Ejemplo: La expresión (pΛq)→(pVq), genera un resultado

tautológico.
P q pΛq pvq (pΛq)→(pVq)

V v v v v
V f f v v
F v f v v
F f f f v
Contradicción:
La contradicción es una proposición compuesta: 𝑃 (𝑞, 𝑟, 𝑠,…,t),
opuesta a la tautología y que se caracteriza por tener sólo el
valor de verdad f, como resultado de la evaluación de la
expresión de que se trate.
Si una proposición compuesta es falsa para todas las

asignaciones entonces es una contradicción.
Ejemplo:
Tabla de verdad para: a ∧ ~a
A ~a a ∧ ~a
V f F
F v F
83
Contingencia: Se entiende por verdad contingente, o verdad

de hecho, aquella proposición que puede ser verdadera o
falsa, (combinación entre tautología y contradicción) según los
valores de las proposiciones que la integran.
Sea por ejemplo el caso a^(b v c)
a b c bvc a^(bvc)
v v v v v
v v f v v
v f v v v
v f f f f
f v v v f
f v f v f
f f v v f
f f f f f
3.1.4 Equivalencias Lógicas
Dos fórmulas lógicas son equivalentes si tienen los mismos valores

de verdad para todos los posibles valores de verdad de sus
componentes atómicos.
Dos proposiciones p y q son lógicamente equivalentes si es una

tautología, es decir, si las tablas de verdad de p y q son iguales.
A modo ilustrativo se demuestra continuación que en virtud de

la ley asociativa de la conjunción o producto lógico, la fórmula
p^(q^r) es lógicamente equivalente a (p^q)^ r.
84
Para ello no hay más que hacer la tabla de verdad de cada

una de esas expresiones y comprobar si en efecto, todas sus
interpretaciones son iguales para la conectiva dominante.
Si dos fórmulas lógicas son equivalentes entonces la fórmula que

se obtiene al operarlas con la bicondicional es una tautología.
Cabe decir, que cualquier suma a la unidad lógica uno, el

resultado será invariablemente una tautología y en
consecuencia, toda expresión que por sí misma genere una
tautología será una equivalencia lógica a la unidad.
Sea por ejemplo una equivalencia lógica en la ley asociativa de

la conjunción, a modo ilustrativo demostraremos a continuación
que, en virtud de la ley asociativa de la conjunción, la fórmula
~p→~q es lógicamente equivalente a p^v~q.
Para ello y mediante la tabla de verdad de cada una de esas

expresiones se comprueban todas sus interpretaciones y son
iguales para la conectiva dominante.
~p→~q
p q ~p ~q ~p→~q
v v f F v
v f f V v
f v v F f
f f v V v
85
p ^ v~q
p q ~q pv~q
v v f v
v f v v
f v f f
f f v v
Tabla de verdad resultante de una equivalencia lógica.
3.1.5 Reglas de inferencia
Regla de inferencia es un esquema para construir inferencias válidas.

Estos esquemas establecen relaciones sintácticas entre un
conjunto de fórmulas llamados premisas y una aserción
llamada conclusión. Las reglas también se aplican a la lógica
informal y a las discusiones, pero la formulación es mucho más
difícil y polémica.
Reglas de Inferencia Deductiva. Sea:
MPP Modus ponendo ponens

A→B
A
–––––
B
MTT Modus tollendo tollens
A→B
˜B
–––––
Ã
SD Silogismo Disyuntivo
A∨B
Ã
–––––
˜B
86
SH Silogismo hipotético
A→B
B→C
–––––
A→C
LS Ley de simplificación
A∧B
–––––
A
Ley de adición
A
–––––
A∨B
Contra Positiva
A→B
–––––
˜B → Ã
3.1.6 Argumentos válidos y no válidos
Un argumento es una secuencia de afirmaciones y todas las

afirmaciones, excepto la última se llamarán premisas,
suposiciones o hipótesis, la declaración final se llamará
conclusión.
Argumentar consiste en deducir una conclusión a partir de una

premisa que se tiene por verdadera. Un argumento, por lo tanto,
estará compuesto de varias premisas y de una conclusión.
87
Lo que hace que se pueda hablar de razonamiento, es la

relación que existe entre los enunciados que llamamos
premisas y conclusión.
Se puede decir que un argumento es válido si para cualquier

valor de las variables proposicionales involucradas en las
fórmulas que hacen verdaderas las premisas, la conclusión es
verdadera.
 Un argumento puede ser válido con premisas y conclusión

verdaderas.
 Pero también puede ser válido con premisas falsas y
conclusión verdadera, o incluso con premisas y conclusión
falsas.
Nunca será válido un argumento con premisas verdaderas y
conclusión falsa.
Entonces, por propia definición de argumento válido, se puede

deducir una metodología para verificar la validez de un
argumento.
1.- Identificar las premisas y la conclusión.

2.- Construir una tabla de verdad que incluya las premisas y la
conclusión.
3.- Señalar de la tabla sólo aquellos renglones que hacen que
todas las premisas sean verdaderas.
Estos se llamarán renglones críticos.
88
4.- Verificar que, para los renglones críticos, la conclusión es

verdadera. En tal caso se tiene un argumento válido.
5.- Detectar si existe un renglón crítico con conclusión falsa. En
cuyo caso se dirá argumento inválido.
Las premisas pueden ser verdaderas o falsas, la conclusión

puede ser verdadera o falsa y el argumento puede ser válido o
inválido.
Evaluación de los argumentos mediante tablas de verdad:
Todos los argumentos pueden convertirse en un condicional, ya

que después de todo lo que un argumento está afirmando, es
que, si las premisas son verdaderas, entonces la conclusión
también lo es. Dicho de otro modo: P1∧P2∧ … ∧Pn→C.
Es decir, un argumento es, en realidad, un condicional en el que

el antecedente es la conjunción de todas las premisas
(P1∧P2∧…∧Pn) y el consecuente es la conclusión. Como bien se
sabe, la tabla de verdad del operador condicional nos dice que
este solo es falso cuando el antecedente es verdadero y el
consecuente es falso y verdadero en el resto de los casos. Esto
coincide completamente con la definición de argumento
válido, según la cual un argumento será válido exactamente en
los mismos casos en que el condicional que le corresponde lo
sea. Como un condicional no puede ser verdadero si el
89
antecedente es verdadero y el consecuente falso, un

argumento no podrá ser válido si las premisas son verdaderas y
la conclusión falsa.
No siempre es fácil averiguar intuitivamente si un argumento es

válido o no, por lo que en ocasiones es necesario recurrir a
métodos más fiables que la intuición. Dado que se puede
convertir cualquier argumento en un condicional, se puede usar
el método de las tablas de verdad para averiguar si un
argumento dado es válido o no.
Evidentemente, un argumento sólo será válido cuando el

condicional correspondiente sea una tautología y no será válido
en el resto de casos (si es una contradicción o si es una
contingencia). Veamos los casos siguientes:
Premisa 1) Si estudio entonces aprobaré.

Premisa 2) No he estudiado.
Conclusión: No aprobaré.
Lo primero que hay que hacer para evaluar o decidir si el

argumento es válido o no, es formalizarlo:
Formalización de la premisa 1): p→q (si estudio entonces

aprobaré)
Formalización de la premisa 2): ˜p (no estudio)
Formalización de la concusión: ˜q (no apruebo)
90
En segundo lugar, se tiene que convertir el argumento en un

condicional. Como se ha visto, el antecedente del condicional
estará formado por la conjunción de todas las premisas y el
consecuente por la conclusión, de modo que se obtiene lo
siguiente:
[( p → q ) ^˜p] → q
Éste es en consecuencia, el condicional que le corresponde al

argumento del ejemplo. La tabla de verdad, quedará como
sigue:
p q ˜p P→q (p→q) ^˜p [ (p→q) ^ ˜p] → q

1 1 0 1 0 1
1 0 0 0 0 1
0 1 1 1 1 1
0 0 1 1 1 0
dicha tabla de verdad revela que el condicional analizado es

una contingencia, lo que significa que puede ser verdadero o
no, es decir, que es posible que sus premisas sean verdaderas y
su conclusión falsa. Por lo tanto, el argumento correspondiente
no será válido, como se dedujo intuitivamente en el apartado
anterior.
3.1.7 Demostración formal (Directa por contradicción)
Como ya se dijo con anterioridad en esta misma unidad, la

contradicción es aquella proposición que siempre es falsa para
91
todos los valores de verdad, una de las más usadas y más

sencilla es p∧~p, tal como lo muestra su correspondiente tabla
de verdad.
p ~p p∧~p
f v f
v f f
Entonces, para el caso de ilustrar una demostración formal, se

puede partir del siguiente ejemplo:
Si se tiene p: “El coche es verde”, la proposición p∧~p equivale

a decir que “El coche es verde y el coche no es verde”. Por lo
tanto, se está contradiciendo, es decir, se está frente a una
falacia.
3.2 Lógica de predicados
La lógica de predicados estudia las frases declarativas con

mayor grado de detalle, considerando la estructura interna de
las proposiciones. Se distingue:
 Que se afirma (predicado o relación).

 De quien se afirma (objeto).
El alfabeto de la lógica de predicados estará formado por los

siguientes conjuntos simbólicos:
92
• Conjunto de Símbolos de Variables (VAR): Es un conjunto de

las últimas letras del alfabeto en minúsculas. Se utilizan
subíndices, por ejemplo:
• Conjunto de símbolos de Constantes (CONS): Este conjunto lo

forman las primeras letras del alfabeto en minúsculas, también
se utilizan los subíndices:
• Conjunto de letras de función (FUNC): Se representa a este

conjunto por las letras f,g,h,L. Se Incluyen subíndices para poder
diferenciar las funciones:
• Conjunto de letras de Predicado (PRED): Se representan
mediante letras mayúsculas,
Símbolos de conectivas:
˜ = Negación
∨ = Conectiva “o”
∧ = Conectiva “y”
→ = implicación
↔ = Doble implicación o equivalencia
Cuantificadores:
∃ = existencial
∀ = Universal
Ejemplo:
1.- Todo número es imaginario.
∀(x)(N (x)→I(x)) se lee: “Para todo x tal que x es un número,

entonces x es imaginario”.
93
2.- Algún número no es par.
∃(x) (N (x)∧˜p(x)) se lee: “existe un x tal que x es un número y no

es par.
3.3 Álgebra declarativa
Lo que algunos llaman álgebra declarativa no es otra cosa que

el álgebra proposicional, o sea la estructura algebraica que se
forma con expresiones utilizando los conectivos lógicos.
Se empieza por definir formalmente cómo se construye una

fórmula en lógica matemática. Una expresión sintácticamente
correcta se le llama fórmula bien formada (fbf) o simplemente
fórmula.
Una fórmula en lógica de proposiciones se obtiene al aplicar

una o más veces equivalencias lógicas.
Por ejemplo, simplificar: (p^q)^˜q.
Para esto se utilizan las siguientes equivalencias lógicas:
(a^b)^c ↔ a^(b^c)
a^~a↔f
a^f↔f
(p^q)^~q↔f
94
3.4 Inducción Matemática
Es un razonamiento que permite demostrar una infinidad de

proposiciones, este método se utiliza para problemas como los
dos que se presentan a continuación:
Sea la expresión siguiente:
1+2 * n<=3 * n
Para resolver este problema con la inducción matemática se

deben seguir los siguientes pasos:
1. Que se cumple para n=1
2. Se asume que se cumple para n=k (Hipótesis de inducción)
3. Se concluye que se cumple para n=k+1 (Tesis de Inducción) se

demuestra que el teorema se cumple para cualquier valor de n.
Sea la expresión dos siguiente, demuestre que 1+2+3..+n=n(n+1) /2
1. Paso Base n=1

2. Desarrollo 1*(1+1)/2=1
3. Inducción. Se asume que se cumple para el entero positivo n.
1+2+3…+n = n(n+1)/2
4. Se debe probar que se cumple para n+1, es decir
1+2+3…+n + n+1 = ((n+1) (n+2))/2 es verdadero
95
3.5 Aplicaciones de la lógica matemática en la

computación
La lógica computacional es la misma lógica matemática

aplicada al contexto de las ciencias de la computación. Su uso
es fundamental a varios niveles: en los circuitos
computacionales, en la programación lógica y en el análisis y
optimización de recursos temporales y espaciales algorítmicos.
Circuitos computacionales
Los circuitos computacionales como el nivel menos abstracto

dentro de una computadora están constituidos por circuitos
electrónicos que responden a diferentes señales eléctricas,
siguiendo los patrones de la lógica booleana; esto es,
compuertas lógicas que devuelven un valor dependiendo de
las entradas que se le dan al sistema.
Existen ocho compuertas lógicas básicas con las cuales se

pueden formar sistemas muy complejos: AND, OR, NOT, Buffer,
NAND, NOR, XOR y XNOR. Todas ellas son representadas
mediante un símbolo y una tabla de valores de verdad, que son
simplemente un cuadro donde se ubican todas las posibles
entradas y los valores que devolvería la compuerta dados
dichos valores.
96
Todo sistema computacional, por muy complejo que sea, no

está compuesto por más que circuitos electrónicos que
únicamente entienden un lenguaje binario. La lógica
computacional se encarga de modelar y optimizar tales
sistemas a este micronivel.
Algoritmos
En matemáticas, ciencias de la computación y disciplinas

relacionadas, un algoritmo, es un conjunto prescrito de
instrucciones o reglas bien definidas, ordenadas y finitas que
permiten realizar una actividad mediante pasos sucesivos que
no generen dudas a quien deba realizar dicha actividad.
Dados un estado inicial y una entrada, siguiendo los pasos

sucesivos se llega a un estado final y se obtiene una solución. Los
algoritmos son el objeto de estudio de la algoritmia y resultan ser
independientes del lenguaje de programación y la
computadora que tenga que utilizarse.
El pseudocódigo, es una herramienta algorítmica que permite

escribir pseudoprogramas (una imitación de un programa real)
utilizando un lenguaje de pseudoprogramación que es una
imitación de los lenguajes de programación de alto nivel.
Así, un pseudocódigo es una combinación de símbolos y

términos comunes tales como leer, imprimir, abrir, cerrar, hacer-
97
hasta, mientras-hacer, etc., y otras características comúnmente

utilizadas en los lenguajes de alto nivel.
Programación lógica
La programación lógica consiste en la aplicación del cuerpo de

conocimiento sobre lógica para el diseño de lenguajes de
programación.
La programación lógica es un tipo de paradigmas de

programación dentro del paradigma de programación
declarativa. El resto de los subparadigmas de programación
dentro de la programación declarativa son: programación
funcional, programación basada en restricciones, programas
DSL (de dominio específico) e híbridos. La programación lógica
gira en torno al concepto de predicado, o relación entre
elementos. La programación funcional se basa en el concepto
de función (que no es más que una evolución de los
predicados), de corte más matemático.
La programación lógica encuentra su hábitat natural en

aplicaciones de inteligencia artificial o relacionadas:
 Sistemas expertos, donde un sistema de información imita las

recomendaciones de un experto sobre algún dominio de
conocimiento.
98
 Demostración automática de teoremas, donde un programa

genera nuevos teoremas sobre una teoría existente.
 Reconocimiento de lenguaje natural, donde un programa es
capaz de comprender (con limitaciones) la información
contenida en una expresión lingüística humana.
99
1.- A que deducción lógica equivale el enunciado siguiente: “NO ES

CIERTO QUE HOY NO LLOVERÁ”. Respuesta. Equivale a una doble negación,
es decir que se habla de la verdad lógica. Si lloverá.
2.- De cuatro corredores de atletismo, sabemos que el corredor C ya
alcanzó la meta y que B y D han llegado en medio de A y C. Podría
calcular el orden de llegada.
3.- Represente la sintaxis de al menos tres predicados cuantificados.
Respuesta: a) “X, [niño(X)] => le gusta (X, helados).
b) “Y, [mamífero(Y)] => nace (Y, vivo)
c) “Z, [cartero(Z)] => trabaja (Z, calle)
4.- Probar que para dos subconjuntos X1 y X2 de un conjunto X dado, se
verifica que (X1 U X2) ∩ X1 = X1
5.- Ejemplifique el concepto de tautología más simple. Respuesta Z=A+1.
Lógicamente el resultado bajo ninguna circunstancia puede cambiar a
falso.
6.- Construya la tabla de verdad de la expresión siguiente: (pUq) ∩ (p~q)
7.- Si un argumento lógico es válido con premisas y conclusión verdaderas,
lo puede ser también con premisas falsas y conclusión verdadera, explique
al respecto de la solución no válida. Respuesta. Nunca será válido con
premisas verdaderas que arrojen una conclusión falsa.
8.- Explique y/o ejemplifique a través de un ejercicio cuando se habla de
una equivalencia lógica.
9.- Explique a través de un ejercicio el concepto de contradicción lógica.
Respuesta. Sea Y = estamos en el año 2018 y sea la proposición Y v Y~, que
equivale a decir no estamos en el año 2018. Por lo tanto, la contradicción
representa una falacia.
10.- Sea p=José es alto y sea q=José es flaco. Utilizando lógica
matemática, como traduciría “José no es alto ni flaco”.
100
UNIDAD IV ÁLGEBRA BOOLEANA
UNIDAD IV
ÁLGEBRA
BOOLEANA
102
 APLICA LOS CONCEPTOS, POSTULADOS Y TEOREMAS DEL

ÁLGEBRA BOOLEANA, LOGRANDO OPTIMIZAR EXPRESIONES
BOOLEANAS Y DISEÑA E INTERPRETA EL FUNCIONAMIENTO
DE UN CIRCUITO LÓGICO.
 HABILIDAD DE RECONOCER Y MANIPULAR EXPRESIONES
BOOLEANAS.
 CAPACIDAD DE ABSTRACCIÓN, ANÁLISIS Y REFLEXIÓN

RESPECTO AL TEMA.
 CAPACIDAD DE INTERPRETAR Y PROYECTAR LAS

APLICACIONES A PARTIR DEL CONOCIMIENTO DEL ÁLGEBRA
BOOLEANA.
103
El álgebra Booleana se denomina así en honor a su creador

George Boole matemático inglés (1815 – 1864), que fue el
primero en proponer un sistema de expresiones simplificadas
lógicas. Es decir, con dos estados denominados falso y
verdadero
Resulta ser una herramienta matemática relativamente simple

que nos permite describir la relación entre la o las “n“ salidas de
un circuito lógico y sus entradas en forma de ecuación
algebraica (expresión Booleana) y que conforma la base para
el análisis y diseño de sistemas digitales.
4.1 Teoremas del álgebra Booleana
Por cuestión de orden y para facilitar su explicación y se pueda

entender más rápido, se ordenan las propiedades y teoremas
más comunes, en función del número de variables discretas
utilizadas; es decir una, dos y tres variables y que representan la
base de las funciones lógicas que habrán de simplificarse a su
más óptima expresión más adelante.
Se adopta también para esta unidad el formato de letras

mayúsculas, la negación está representada por la tilde (˜) sobre
la variable o inmediatamente a ella y significa que su valor
actual es falso, obviamente en su forma lógica representa que
la variable tiene un valor de verdadero; y dos o más variables
juntas representan un producto.
104
Propiedades o reglas de una variable lógica
1.- A = A
2.- Ã = Ã
2.1 A~~ = A
3.- A + 1 = 1
3.1 Ã + 1 = 1
4.- A (1) = A
4.1 Ã (1) = Ã
5.- A (0) = 0
5.1 Ã (0) = 0
6.- A + 0 = A
6.1 Ã + (0) = Ã
7.- A + A = A
7.1 Ã + Ã = Ã
8.- A A = A
8.1 Ã Ã = Ã
9.- A + Ã = 1
10.- A Ã = 0
11.- 0~ = 1
11.1 1~ = 0
Teoremas de dos variables
1.- A + B = B + A
2.- A + AB = A
105
2.1 Ã + ÃB~ = Ã
3.- A + ÃB = A + B
4.- Ã + ÃB~ = Ã
5.- A + AB~ = A
6.- Ã + AB~ = Ã + B~
7.- A (AB)= AB
7.1 (A + B) (Ã + B) = B
7.2 (A + B) (A + B~) = A
8.- A (ÃB) = 0
9.- ÃB~ + ÃB = Ã
10.- AB~ + AB = A
11.- ÃB~ + AB~ = B~
12.- ÃB + AB = B
13.- Ã + B~ + AB~ + ÃB = Ã + B~
14.- AB~ + ÃB + AB = A + B
Teoremas de tres variables. A saber, tenemos los siguientes.
1.- AB + AC = A (B + C) ley distributiva

2.- (A + B) (Ã + C) = AC + ÃB
3.- (AB + ÃC + BC) = AB + ÃC por extensión de variables
4.- (A + B) (Ã + C) (B + C) = (A + B) (Ã + C)
5.- (AB + AC) = A (B + C) factorizando una variable común
6.- (A + B) (A + C) = A + BC
106
Teorema de De Morgan.
1.- Las dos formas básicas a comprender son la conversión de
un producto en suma y viceversa, es decir la conversión de
suma en producto y la primera o segunda negación de una
variable según sea el caso de la condición inicial de una
variable, vista a continuación.
A + B = ÃB~ y AB = Ã + B~ , con sus respectivas variantes

respecto a que si la variable esta en modo verdadero o modo
falso.
Los postulados se resumen en la tabla 4.1 siguiente.
Identidad: A+0=A A(1)=A

Conmutativa: A+B=B+A AB=BA
Asociativa: A+(B+C)=(A+B)+C A(BC)=(AB)C
Distributiva: A+(BC)=(A+B)(A+C) A(B+C)=(AB)+(AC)
Existencia de
complemento: Para A+Ã= 1 A(Ã)=0
la variable A existe un
elemento único
denotado por Ã
complemento tal
que:
Tabla 4.1 postulados del algebra Booleana.
107
4.2 Optimización de expresiones Booleanas
Las expresiones Booleanas se usan para determinar si un

conjunto de una o más condiciones es verdadero o falso y el
resultado de su evaluación es un valor de verdad.
Los operandos de una expresión Booleana pueden ser

cualquiera de los siguientes:
 Expresiones relacionales: Se comparan dos valores y se

determinan si existe o no una cierta relación entre ellos.
 Función Booleana: Es una función cuyo dominio son las
palabras conformadas por los valores binario (1 y 0) y cuyo
condominio son ambos valores ( 1 y 0 )
Símbolo Significado
Expresiones relacionales
8>4 la expresión es > Mayor que
verdadera por lo cual
< Menor que
devuelve 1 o cierto, en
cambio 8<4 es falso por lo = Igual que
cual devuelve 0 o falso. <= Menor o igual que
>= Mayor o igual que
<> Distinto que
Tabla 4.2 Expresiones relacionales
108
Hasta este punto, se puede decir que se cuenta con las

herramientas básicas necesarias para poder trabajar en la
optimización o simplificación de expresiones Booleanas y sin
importar su grado de complejidad que representen utilizando,
dos, tres, cuatro, cinco o más variables lógicas y normalmente
será posible obtener una reducción significativa que representa
uno de los objetivos trascendentales de la presente unidad, por
lo que resulta de toral importancia comprender y saber utilizar
eficazmente los teoremas y postulados del álgebra Booleana,
inclusive alcanzando el nivel de abstracción que nos otorgue la
capacidad de aplicar estas herramientas, sin cometer el error
de memorizarlas o algo por el estilo; no es el enfoque, aquí se
debe desarrollar esa lógica que permita entrever de manera
implícita cuál es el mejor teorema que nos ayudará en nuestra
tarea de optimizar y/o simplificar expresiones Booleanas.
También, en este apartado es de singular importancia recordar

y comprender las tablas de verdad de las operaciones lógicas
más comunes, su expresión matemática y su símbolo lógico,
como veremos a continuación.
Operador AND
Expresión matemática Z = AB
109
Tabla de verdad:
A B F
0 0 0
0 1 0
1 0 0
1 1 1
Símbolo:
________________________________________________
operador NAND
expresión matemática Z = AB
Tabla de verdad:
A B F
0 0 1
0 1 1
1 0 1
1 1 0
Símbolo:
________________________________________________
Operador OR
Expresión matemática Z = A + B
110
Tabla de verdad:
A B F
0 0 0
0 1 1
1 0 1
1 1 1
Símbolo:
________________________________________________
Operador NOR
Expresión matemática Z = A + B
Tabla de verdad:
A B F
0 0 1
0 1 0
1 0 0
1 1 0
Símbolo:
________________________________________________
Operador OR –EX (or exclusiva)

Expresión matemática Z = A B = ÃB + AB~
111
Tabla de verdad
A B F
0 0 0
1 0 1
0 1 1
1 1 0
Símbolo:
________________________________________________
Operador OR –EX NEGADO (nor exclusiva)

Expresión matemática Z = A B = ÃB + AB~
Tabla de verdad
A B F
0 0 1
1 0 0
0 1 0
1 1 1
Símbolo:
________________________________________________
Negación lógica o inversor.
Expresión matemática NOT (A)
Tabla de verdad
X F
0 1
1 0
112
Expresión matemática
Z = NOT (A)
Símbolo:
Una vez visto lo relacionado a la operación lógica expresada, su

significado y demás, se procede a resolver una serie de
ejercicios, tratando de explicar lo más detallada posible la
solución, que es aquella que permita manipular la expresión
Booleana original y mediante el uso de los teoremas vistos
simplificar a su mejor equivalencia posible.
Ejercicio 1. Sea la función Booleana siguiente, simplifique a su

mínima expresión.
Sea F= ÃB + AB
De donde la variable común es B, se factoriza esta variable B (A
+ Ã) y se aplica la regla correspondiente (página 104 y 105 ),
con valor de 1, entonces se tiene que B (1), que a su vez
representa otro teorema que resulta en B. Por lo tanto, se
puede afirmar que F= ÃB + AB = B
Ejercicio 2. Sea la función Booleana siguiente, Z = ABC + ABD,

simplemente se factorizan las variables comunes AB y se tiene
que Z = AB (C + D)
113
Ejercicio 3. Sea la expresión siguiente Z = A (Ã + BC) + AC + 1. La

solución es muy simple, porque cualquier expresión Booleana
más uno, simplemente es Z = 1, de acuerdo al teorema de una
variable que dice que Z = A + 1 = 1.
Ejercicio 4. Sea la expresión Booleana Z=(Ã+B) (A+B).

Procediendo con productos directos se tiene ÃA+ÃB+AB+ BB.
(AÃ = 0). Simplificando 0 + ÃB + AB + B, de donde B + BA = B, por
teorema de dos variables, queda B + ÃB, y aplicando
nuevamente el teorema de dos variables por absorción en
modo suma en donde predomina el componente menor se
tiene que el resultado es igual a Z=B, o bien se puede demostrar
si se hace que B = (1 + Ã), de donde (1 + Ã) = 1, queda B (1) = B;
y el resultado como Z = B.
Ejercicio 5. Sea la expresión Booleana siguiente Z = ÃBC (ABC).
Observe y analice, la simplicidad del resultado en cero, debido
a que se multiplica AÃ, que resulta en cero e involucra al
producto BC y así, en cualquier caso. Z = 0.
Ejercicio 6. Demuestre la igualdad del teorema catorce (

página 105 )que dice:
ÃB~ + AB~ + AB = A + B. Bien, factorizando A tenemos ÃB + A,
luego aplicando el teorema de De Morgan sobre la nueva
expresión tenemos que Z = A + ÃB , resolviendo Ã (A + B~) = 0 +
ÃB~, reaplicando Morgan (la regla dice que si utilizas el teorema
114
una vez, deberá aplicarse una vez más y así sucesivamente),

quedando entonces:
Z= ÃB~ = A + B
Ejercicio 7. Si se parte de la regla para una variable que dice
que A +Ã = 1; entonces a partir de esta lógica resuelva:
ABC + ABC; evidentemente el resultado es 1; pero lo
demostraremos eliminando el teorema de De Morgan del
segundo miembro de la ecuación, tenemos Ã + B~ + C~, se
continua reagrupando Ã + ABC y haciendo álgebra con el
teorema de De Morgan se obtiene Ã +BC + B~ + C~, ahora bien,
se reagrupa B~ + BC y se obtiene B~ + C + C~ + Ã, donde C +
C~ es igual a 1, y por fin se llega a Ã + B~ + 1 y por
consecuencia el resultado final de 1.
Ejercicio 8. Sea un problema que contiene un doble teorema de
De Morgan que a continuación se muestra, simplifique a su
menor expresión posible.
Z = A+BC + ÃBC , eliminado el teorema de De Morgan de
ambas partes de la ecuación, se tiene que: Ã (B~+C~) + A + B~
+ C~, eliminando el producto tenemos ÃB~ + ÃC~ + A + B~ + C~
y simplemente reagrupando B~+ÃB~, resulta B~ y reagrupando
ÃC~+C~ tenemos C~, y luego sumando A que no ha
participado hasta ahorita, se llega a A + B~+ C~, lo que significa
que el resultado final es Z= A + B~ + C~
115
Ejercicio 9. Simplificar Z = (A + B +C) (A + B~ +C) (C~ + D) (A + D).

Se hacen productos simples de las dos primeras partes de la
expresión y se obtiene (A + C). Queda ahora (A + C) (C~ + D)
(A + D) y se hacen productos de los miembros tres y cuatro y se
obtiene (AC~+D) y se reescribe el problema como (A + C)
(AC~ + D), que sería igual a AC~ + AD + CD.
Ejercicio 10. Simplificar (A + B) (A B).

Recordando la suma exclusiva, se tiene que la segunda parte
de la ecuación equivale a (ÃB + AB~), luego entonces se hace
el producto con (A + B), tenemos finalmente (A B ).
Ejercicio 11. Sea la expresión Booleana Z = AB+(Ã+B~) C~

Se elimina el teorema de De Morgan y se hace el producto de
la segunda parte de la expresión, se tiene: Ã + B~ + ÃC~ + B~C~,
se reordena la expresión y se tiene ahora a la vista un teorema
de dos variables. Ã + ÃC~ + B~ + B~C~, de la primera parte de
la expresión se obtiene simplemente Ã y de la segunda parte B~,
por lo que el resultado simplificado obtenido es Z = Ã + B~.
Ejercicio 12. Sea la expresión Z = AB~C + B, se aplica De Morgan

a toda la expresión para buscar la simplificación, se tiene:
AB~C+B y resolviendo (Ã+B+C~) B~, se desarrolla el producto
ÃB~ + 0 + B~C~, o sea ÃB~ + B~C~, se factoriza B~ (Ã+C~) y se
reaplica ahora el teorema de De Morgan por regla, recordar
116
que se ocupó una vez y tiene que duplicarse dicha operación,

se tiene que: B~ (Ã+C~ = B + AC, o sea Z = B + AC
Ejercicio 13. Sea Z = (B + C~) (A + C~), simplifique. Se desarrollan

los productos Booleanos, se tiene ahora AB + BC~ + AC~ + C~, a
la vista un teorema muy útil ya visto con anterioridad, en donde
la sumatoria absorbe los componentes mayores comunes y que
en este ejemplo es C~, común a dos productos, por lo que
ahora se tiene simplemente Z = AB + C~
Ejercicio 14. Simplifique la expresión Booleana siguiente de cinco

variables, planteada con De Morgan inicial.
Z = (AB~C) (D + E) + ABC~ + E~, se elimina por teorema de De
Morgan Ã + B + C~ + D~E~ + ABC~ + E~, se simplifica expresión
cuatro con seis, tenemos ahora: Ã + B + C~ +ABC~ + E~,se
simplifican ahora las expresiones tres y cuatro y ahora se obtiene
Z = Ã + B + C~ + E~
Ejercicio 15. Sea Z = ABC~ + BC + ÃBC~, de igual manera, se

elimina de De Morgan de la segunda expresión B~ + C~, la
variable común a tres miembros de la expresión, resulta ser C~,
por lo que Z = B~ + C~
Aquí es muy importante mencionar otro método no menos

importante de simplificación de expresiones Booleanas
conocido como diagramas de Karnaugh, (diagramas K), que se
basa en la estrategia de asociar filas o columnas o extremos de
117
ellas en numerales potencias de dos. Así, por ejemplo, puede

agruparse, una, dos, cuatro, ocho, dieciséis, etc., posiciones
adyacentes no diagonales y eliminar automáticamente a todas
aquellas variables que cambien de valor (0,1) al menos una vez.
Veamos a continuación como funciona este método.
Diagrama K de una variable:

A 0 1 equivale a Z= Ã
x
A 0 1 y ahora equivale a Z= A
x
A 0 1 y ahora equivale a ( A + Ã ), o sea Z= 1

x X
Con dos variables tendríamos el diagrama siguiente:
A 0 1
B
0 X
1
Z= Ã B~
118
A 0 1
B
0 x
1
Z= AB~
A 0 1
B
0
1 X
Z= ÃB
A 0 1
B
0
1 x
Z= AB
Y ahora con dos posiciones adyacentes, horizontalmente se

simplifica:
A 0 1
B
0 X X
1
Como la variable que cambia de valor en ese agrupamiento

horizontal es A, esta se elimina y se obtiene entonces el
resultado de Z = B~
Y lo mismo sería con dos posiciones adyacentes verticales.

119
A 0 1
B
0 x
1 x
La variable que ahora cambia de valor es B, por lo que se

elimina y se obtiene Z= Ã ; si los espacios marcados con x
estuvieran a la derecha, se hubiera obtenido que Z = A.
Siguiendo con esa misma lógica para un diagrama de tres

variables, se tiene ahora el diagrama siguiente, en donde sobre
la horizontal se etiqueta A y B y sobre la primer columna de
izquierda a derecha, se etiqueta a C. Se comprende que la
primera columna denota que A y B valen 0 y 0 respectivamente,
en la segunda columna 0 y 1 y así sucesivamente y lo mismo
para la variable C con valor de cero en la primera fila y con
valor de uno en el segundo renglón.
AB 00 01 11 10
C
0
1
En donde ya se pueden agrupar posiciones adyacentes en

potencias de dos hasta ocho posiciones, si ese fuera el caso y
en donde por lógica el resultado sería igual a 1.
120
Veamos los ejercicios siguientes:
AB 00 01 11 10
C
0 X X
1 X X
Al agrupar las cuatro posiciones adyacentes, se obtiene Z = Ã

(es la única variable que no cambia de valor.)
AB 00 01 11 10
C
0 X X
1
De este ejercicio se entiende y se aprende que los extremos de

la misma fila o misma columna se consideran adyacentes, la
variable A muta su valor en los extremos y desaparece y se
obtiene por lo tanto que Z = B~C~
AB 00 01 11 10
C
0 X X
1 x X
La solución nos dice para este ejercicio, que solo es posible

agrupar dos pares de dos posiciones adyacentes entre sí, pero
121
no es posible más, debido a que ambos pares no son

adyacentes. El resultado y observando como la variable C sobre
la primera columna cambia de valor en ambos casos, será Z =
ÃB~ + AB
AB 00 01 11 10
C
0 X X
1 X X X X
En este nuevo diagrama se visualiza un caso muy completo

debido a la cantidad de cuadros o direcciones utilizados y que
nos permite simplificar con mayor eficiencia. En primer lugar, se
puede agrupar toda la fila inferior compuesta por cuatro
posiciones adyacentes y obtenemos solo C, posteriormente se
agrupa un paquete de cuatro posiciones al centro, recordar
que una posición cualquiera se puede ocupar cuantas veces
sea necesario. De esta segunda operación se obtiene solo B,
quedando nuestro resultado finalmente como Z = B + C.
AB 00 01 11 10
C
0 X X X
1 X X
122
Este ejercicio nos enseña que los extremos o esquinas en la

relación fila-columna se consideran también adyacentes y la
única posición al centro forma adyacencia con la del ángulo
superior izquierdo. Quedando como B~ + ÃC~
AB 00 01 11 10
C
0 X X X X
1 X X X
Un último ejercicio muy ilustrativo también nos muestra una serie

de combinaciones que permite obtener resultados óptimos.
Primero agrupar cuatro posiciones de la fila superior y
obtenemos C~, posteriormente agrupar las cuatro posiciones
centrales y se obtiene simplemente B, pero no hemos terminado
aún, porque falta evaluar la posición de la esquina inferior
derecha y eso se hace reagrupándola en paquete de cuatro
con las posiciones adyacentes superior e izquierda y se obtiene
solo A; de donde se pasa hacia el resultado final como Z = A + B
+ C~.
En los diagramas K de cuatro variables, también se encuentra

mucha facilidad y eficiencia en la simplificación, como se ve a
continuación.
123
AB 00 01 11 10
CD
00
01 X
11
10
Así por ejemplo la dirección marcada corresponde a los valores

de A= 1, B= 1, C= 0 y D = 1.
AB 00 01 11 10
CD
00 X X X
01 X X X X
11 X
10 X
Del diagrama K anterior, se tiene el ejercicio siguiente. Si se

observa bien el planteamiento y de acuerdo a las reglas vistas,
se ve en la columna de los ceros cuatro posiciones adyacentes
y se agrupan de una vez, se obtiene como resultado parcial
ÃB~, posteriormente se observa una fila al centro con cuatro
posiciones adyacentes también y se procede a agruparlas y se
obtiene un segundo parcial C~D, pero aún no se concluye
porque falta empaquetar las direcciones de las columnas tres y
cuatro centrales y fila uno, las cuales se agrupan con sus
124
adyacentes de la fila 2 y así obtener un tercer parcial de BC~,

para que finalmente se obtenga el resultado de Z= ÃB~ + C~D +
BC~.
AB 00 01 11 10
CD
00 X X X X
01 X X X X
11 X X X
10 X X X X
Si fuera el caso para un nuevo ejercicio, con un mapa

exhaustivo el resultado es lógicamente Z = 1
Veamos otro ejercicio. Sea el diagrama K siguiente:
AB 00 01 11 10
CD
00 X X
01 X X
11 X
10 X X X X
Aplicando lo aprendido, rápidamente se percibe que la base

de la solución consiste en agrupar en cuatro la última columna y
la fila inferior y se obtiene AB~ +C D~ respectivamente.
125
No se termina aún, porque falta evaluar dos posiciones anexas

al centro del diagrama. Al hacerse se obtiene ÃBC~. Se suman
todos los parciales para concluir con Z = AB~ + CD~ + ÃBC~.
El ejercicio siguiente sigue las mismas reglas. Se resuelve

obviamente agrupando las cuatro posiciones extremas
externas, es decir para identificarlas de las cuatro posiciones
internas que también se agruparan de acuerdo a las reglas de
los diagramas K. se obtiene entonces de afuera hacia dentro
que Z = B~D~ +AB
AB 00 01 11 10
CD
00 X X
01 X X
11 X X
10 X X
Y para concluir este tema, se trabaja un último ejercicio.
AB 00 01 11 10
CD
00 X X
01 X X X X
11 X X X X
10 X X
126
A detalle se observa la solución, misma que consiste en agrupar

hasta ocho direcciones tanto de manera vertical como de
manera horizontal, importante recordar que se puede utilizar
una dirección cuantas veces sea posible. Se obtiene
horizontalmente de las dos filas D y luego se obtiene
verticalmente de las dos columnas B; es decir que Z = B + D.
4.3 Aplicación del álgebra Booleana
Entre una expresión lógica y los diagramas de circuitos lógicos

existe una estrecha relación. Las compuertas lógicas son
dispositivos que operan con estados lógicos y funcionan igual
que una calculadora, de un lado ingresas los datos, ésta realiza
una operación y finalmente arroja un resultado.
Figura 4.1 Recorrido de datos lógicos.
Como ya se vio, cada una de las compuertas lógicas se

representa mediante un símbolo y la operación que realiza
(operación lógica) y su correspondiente tabla de verdad. La
ventaja que se tiene ahora es que resulta posible combinar las
operaciones lógicas (AND, OR NAND, NOR, NOT, XOR) y
127
representarlas mediante los símbolos apropiados hasta reflejar

cualesquier expresión lógica original. Así por ejemplo sea:
Z=AB + CD, puede representarse como:
A
B
C
D
O bien sea F = w (x~ + xy), genera el diagrama lógico siguiente.
128
O también si Z = (ÃB~) (C) + C~D, toda la expresión bajo de De

Morgan, se tiene el diagrama siguiente.
Z
C
Es decir, qué a partir del conocimiento del álgebra Booleana, se

tiene al alcance de nuestra mano la capacidad de
conformación de circuitos lógicos simples que pueden realizar
alguna tarea aritmética o lógica, toda vez que trabajan bajo la
condición de dos estados lógicos (falso y verdadero) y a una
gran velocidad. A partir de la facilidad de esta simbología y sus
aplicaciones, los circuitos lógicos se dividieron en circuitos
lógicos combinacionales y circuitos lógicos secuenciales.
Los circuitos lógicos combinacionales mayormente conocidos

son los siguientes: Decodificadores, codificadores, multiplexores
y demultiplexores.
Atendiendo a estos circuitos en su conjunto, se dice que un

circuito lógico decodificador cuenta con su característica más
129
importante que entre sus “n “salidas, una y solo una es uno

lógico en un instante de tiempo; es decir que, en algún
momento, una de sus salidas se distingue de todas las demás,
por su carácter individual y seleccionable.
Figura 4.2 Decodificador binario a octal .
Misma que muestra el circuito decodificador en su función de

conversor binario a octal y su correspondiente tabla de verdad.
DEC A B C O0 O1 O2 O3 O4 O5 O6 O7
0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0
2 0 1 0 0 0 1 0 0 0 0 0
3 0 1 1 0 0 0 1 0 0 0 0
4 1 0 0 0 0 0 0 1 0 0 0
5 1 0 1 0 0 0 0 0 1 0 0
6 1 1 0 0 0 0 0 0 0 1 0
7 1 1 1 0 0 0 0 0 0 0 1
130
El circuito lógico codificador realiza la función inversa del

decodificador. Este se diseña para que entre sus entradas
siempre haya una con un nivel lógico distinto a todas las demás
(las entradas de un codificador, son por lo general las salidas de
un decodificador). Por cada línea de entrada, aparece en las
líneas de salida la palabra código correspondiente, cuya línea
de bits aparecen en O0, O1, O2, etc.
En la figura 4.3 de la página 132 se muestra el diagrama lógico

de un codificador.
Una aplicación asociada a este circuito es que sus salidas se

pueden interpretar como señales indicadoras y realizar alguna
acción en consecuencia.
Por ejemplo, suponer que se equipa un tanque de agua con un

mecanismo conmutador, que opera cuando el nivel del agua
está excesivamente alto y hay peligro de desborde. Fácilmente
se puede disponer una línea que en condiciones normales
indique un cero lógico, pero que cambie a uno lógico cuando
opere el conmutador. Entonces el cambio de cero a uno lógico
es una indicación de que es necesario hacer algo; es decir, hay
una petición de servicio distintiva (código de dirección), que
mediante un decodificador acceden a un componente de
servicio.
131
Otra aplicación muy común en donde participan estos dos

circuitos decodificador y codificador, es en el diseño de
visualizadores de siete segmentos, muy populares en la práctica
y en donde la relación decodificador a codificador logra el
diseño de esta aplicación. Se concluye que se utilizará
normalmente un codificador para aceptar como entradas a “n
“líneas de servicio y obtener como salida el código de bits
correspondiente a la dirección del componente que atenderá
la petición, ya que este circuito está diseñado para que cada
vez que tenga una entrada diferente se atienda solamente una
y solo una petición de servicio.
El codificador BCD (Binary Code Decimal)/7 segmentos, es por

ejemplo el circuito integrado 7446; la entrada es un número BCD
de 4 bits (A, B, C y D). El número BCD se transforma en un
código de 7 segmentos que ilumina los segmentos adecuados
del visualizador tipo LED. Además, hay que considerar otras 3
entradas que forman parte del circuito integrado. La entrada de
test de lámpara (LT), enciende todos los segmentos del
visualizador, de esta forma comprobamos que el visualizador
funciona correctamente; esta entrada se activa por nivel bajo
(0 lógico), pero el funcionamiento normal del decodificador
siempre debe estar a nivel alto (1 lógico). Las entradas de
borrador (BI/RBO y RBI) de dicho circuito, desconectan los
elementos activos, aunque presentan alguna particularidad que
132
se añade en las notas de la tabla de verdad de este circuito

integrado; estas dos entradas se activan y desactivan de modo
similar a la entrada del test de lámparas. Las salidas del
decodificador se activan por nivel bajo.
Figura 4.3 Diagrama del circuito lógico codificador.
El multiplexor (MUX) es un circuito lógico combinacional que

consta de varias entradas y una salida y mediante un
mecanismo de selección, una y solo una de las dichas entradas
se transfiere a la salida. Es decir, este circuito nos permite
seleccionar una de las “n “entradas y transferirla hacia la única
salida. Las aplicaciones dependerán de la implementación que
se haga de esta propiedad del circuito y cuyo diagrama se
muestra a continuación.
133
Figura 4.4 diagrama lógico de un multiplexor.
El demultiplexor es un circuito combinacional que consta de

una entrada de datos, varias señales de control y las líneas de
salida.
Es un circuito destinado a transmitir una señal binaria a una

determinada línea, elegida mediante un seleccionador, de
entre las diversas líneas existentes.
La analogía mecánica de un demultiplexor sería como un

selector con una entrada y varias posiciones de salida.
Un decodificador se convierte en un demultiplexor añadiéndole

una señal más a su circuitería interna. Si se aplica esta señal, la
salida será el complemento de dicha señal, ya que la salida es 0
si todas las entradas son 1, y aparecerá únicamente en la línea
seleccionada.
Se puede ver de otra manera en qué consiste la función de un

circuito demultiplexor. Estos son circuitos que realizan una
función contraria a la de los multiplexores, es decir, tienen una
única entrada de datos que, mediante unas entradas de
134
control, se ponen en comunicación con una de entre varias

salidas de datos.
La salida seleccionada depende de la combinación de valores

lógicos presentados en las entradas de control.
De la definición, se desprende que cualquier decodificador que

elija sólo una salida entre varias y esté provisto de entrada de
inhibición o “enable”, puede utilizarse como demultiplexor, ya
que las entradas del código se pueden emplear como entradas
de control y la señal de inhibición como entrada de datos.
En la práctica, no existen circuitos integrados demultiplexores,

sino que se fabrican circuitos decodificadores/demultiplexores,
que en realidad son decodificadores con entrada de inhibición
(“enable” o “strobe”).
La figura 4.5 siguiente, muestra el diagrama lógico de un circuito

demultiplexor.
Figura 4.5 Diagrama lógico de un demultiplexor.
135
Por lo que respecta a los circuitos lógicos secuenciales y cuya

principal diferencia respecto de los circuitos lógicos
combinacionales, es que sus salidas están determinadas por sus
entradas, es decir existe un estado de retroalimentación que les
confiere una característica lógica muy especial y que es la de
retener o almacenar un bit (0,1) y que determinará la respuesta
en otro instante de tiempo t.
Es decir, si en el instante t = t0 cambia alguna de las entradas,

consecuentemente las salidas deben de cambiar, pero estas
dependen solamente de las entradas posteriores a t 0. y no del
valor que tuvieran antes de ese instante. Esto significa, que los
circuitos combinacionales no tienen esta propiedad de
memoria, en donde las salidas actuales solo dependen de las
entradas actuales y punto.
Cada etapa que atraviesa un circuito secuencial se denomina

estado. En cada uno de ellos, el circuito almacena un recuerdo
de su historia pasada, para saber que hacer a continuación.
Un estado se distingue de otro por sus recuerdos almacenados y

parecerá que a medida que progresa el tiempo es necesario
añadir nuevos elementos a la memoria y por consiguiente
desarrollar una secuencia ilimitada de estados nuevos y
diferentes, sin embargo, parece que ni toda la historia pasada
es relevante, ni todos los estados por los que progresa son
136
diferentes entre sí y que el número total de estados es bastante

limitado.
Los sistemas secuenciales más comunes a partir del uso y

aplicación de los circuitos secuenciales son los sistemas
contadores síncronos y registros a base de flip-flops, es decir una
estructura lógica retroalimentada a partir de las salidas de
manera inmediata y que tiene la capacidad de generar el
efecto memoria en una aplicación lógica secuencial y cuyo
diagrama aparece en la figura 4.6 siguiente.
Circuito lógico flip–flop con compuertas NAND, de dos entradas

y tabla de verdad.
Figura 4.6 Circuito lógico secuencial flip-flop con compuertas NAND y tabla
de verdad
4.3.1 Mini y maxitérminos (minterms y maxterms)
En la presente unidad, habiendo visto los teoremas y las

estructuras lógicas de las expresiones Booleanas, la simbología y
los métodos para simplificarlas, se trata ahora de conocer un
método para numerar los minterms (productos completos) y los
maxterms (sumas completas).
137
Minterms: Para expresar una función Booleana de n variables

{x_1,…x _n}, representa una suma de productos completa, en
cada una de las n variables debe aparecer una sola vez
(negada o sin negar) y es llamado minitérmino. Es decir, un
minitérmino es una expresión lógica de n variables consistente
únicamente en el operador de producto lógico (AND), sumado
(OR) y el operador complemento o negación (NOT).
Por ejemplo, ABC, AB~C y ABC~ son

ejemplos de minitérminos (Sm) para una
función booleana con las variables A, B,
y C. (´ equivale a negación)
La forma completa de expresar la

función lógica mediante el criterio de
minterms se vería de la siguiente manera:
f (A,B,C) = ÃBC + AB~C~ + ABC + ÃBC~ igual a decir f(A,B,C)=

Sm( 3,4,7,2)
En general, se asigna a cada minitérmino (escribiendo las

variables que lo componen en el mismo orden), un índice
basado en el valor binario del minitérmino. Un término negado
como Ã es considerado como el número binario cero y el
término no negado A es considerado como un uno.
138
Ahora se considera el concepto de maxterms (PM) y para

referirse a ellos, la regla para asignar cero y uno se invierte. A la
variable complementada se le asignará el valor de uno y a la
variable sin complementar se le asignará el valor de cero. Así
por ejemplo al maxtérmino Ã + B + C, equivaldría a asignar el
valor lógico de 1, 0, 0 respectivamente, es decir 100=4 y se
representa como M 4.
La relación entre minterms y maxterms se puede mostrar

mediante el uso de la siguiente tabla de verdad con tres
variables. Las filas tienen asignados números que corresponden
a las entradas lógicas en el orden A, B, C y la función definida
por la tabla se expresa en ambas formas equivalentes, es decir,
como minterms (suma de productos) y como maxterms
(producto de sumas)
Fila A B C f (A,B,C)
0 0 0 0 1
1 0 0 1 0
2 0 1 0 1
3 0 1 1 1
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1
Tabla 4.1 Tabla de verdad de tres variables que muestra la

equivalencia de minters – maxterms.
139
Para cuando f = 1, la función de minterms es igual a:
F(A,B,C) = ÃB~C~ + ÃBC~ + ÃBC + ABC~ + ABC = F Sm *(0,2,3,6,7)
Y para los maxterms queda igual a:
F(A,B,C) = (A + B + C~) (Ã + B + C) (Ã + B + C~) = F PM † (1,4,5),

misma que satisface de manera exhaustiva las ocho entradas
posibles para las tres variables lógicas.
Por otra parte, si se quiere calcular el complemento de una

función. En la tabla de verdad debe intercambiarse cada f=0
por f=1. Por consiguiente, se necesitan sustituir solamente los
minterms por los maxterms con la misma numeración o
viceversa. Así dada f=Sm(0,3,6,7), tenemos f~PM(0,3,6,7).
En resumen, una función lógica arbitraria como la del ejemplo,

representa también un circuito combinacional arbitrario, que
como en este caso se puede expresar por una de minterms,
cuya numeración coincide con la de las filas de la tabla de
verdad en las que la función tiene el valor de uno. O bien, la
función, se puede expresar por un producto de maxterms, cuya
numeración coincide con la de las filas de la tabla de verdad
para las que la función es cero.
*
Sm sumatoria de minterms.
†
PM producto de maxterms.
140
4.3.2 Representación de expresiones booleanas con circuitos

lógicos.
Existe una estrecha relación entre las expresiones Booleanas y

los circuitos lógicos, ya que como se vio en la presente
unidad, para cada operación lógica existe un símbolo
asociado que representa exactamente la operación
correspondiente.
La expresión Booleana involucra en un grado de complejidad

que va de menos a más, desde una sola operación hasta un
complejo conjunto de operaciones contenidas en una
función.
El circuito lógico, mediante la simbología convencional, va

representando en dicho circuito exactamente la misma
operación original a partir del símbolo de cada compuerta
lógica.
En un diseño que vaya orientado a una aplicación en

particular, es posible conformar un circuito lógico que realice
alguna tarea aritmética lógica o simplemente probar la
veracidad de los resultados que arroja la tabla de verdad
correspondiente y comprobar que los resultados son
exactamente los mismos.
141
La diferencia sería que la expresión arroja resultados sucesivos

en modo falso y verdadero y el circuito físico, mediante el uso
de leds u otro tipo de señales, nos arrojaría el resultado
correspondiente a falso o verdadero, a través de un led
encendido como verdadero y apagado como falso o
mediante un sonido probablemente. Un diseño más complejo
muy probablemente generaría una secuencia de bits como
una clave preestablecida, la visualización de un texto o el
resultado de una operación matemática.
Las posibilidades son casi infinitas, ya que toda expresión

lógica es susceptible de ser convertida en un diagrama o
circuito lógico, tal como se vio paso a paso en el transcurso
de la presente unidad.
142
Ejercicios propuestos de la unidad IV y solución a ejercicios nones.
1. Sea la expresión Booleana Z = ÃBC + B~ + AB, simplifique con álgebra

de Boole y demuéstrelo mediante la tabla de verdad.
Respuesta Z = A + B~+ C
2. Demuestre la igualdad de este teorema cuatro de tres variables.

Z = (A + B) (Ã + C) (B + C) = (A + B) (Ã + C), página 105.
3. Simplifique Z = (Ã + BC) (B+ C~D). Respuesta Z = Ã (B + C~D) + BC
4. Utilizando un diagrama K de tres variables simplifique la expresión

siguiente: Z = AB~C + AC~+ BC
5. Utilizando un diagrama K de tres variables simplifique la expresión

siguiente: Z = A (BC + AB) + AC.
Respuesta Z = A(B+C)
6. Sea la función F = (A,B,C,D) = ÃB~C~D~ + BC~D + ÃC, que como se

sabe está expresada como una suma de mintérminos, represéntela en
un diagrama K.
7. Obtenga la expresión Boolena generada por el circuito lógico

siguiente. Respuesta Z = AB~C + Ã (B + C~)
143
8. Investigar el diagrama lógico de un circuito sumador.
9. Sea el flip-flop con dos compuertas NOR como lo muestra el diagrama

siguiente, obtenga su correspondiente tabla de verdad, considerando
un estado inicial de S = 0 y R = 1.
R
Q
Q˜
S
S
Respuesta: Tabla de verdad
R S Q Q~
0 0 0o1 1o0
0 1 0 1
1 0 1 0
1 1 n/a n/a
10. Investigar el circuito lógico de un visualizador de siete segmentos.
144
UNIDAD V
TEORÍA DE
GRAFOS
146
 APLICA LOS CONCEPTOS BÁSICOS DE GRAFOS PARA

RESOLVER PROBLEMAS AFINES AL ÁREA COMPUTACIONAL,
RELACIONADOS CON EL RECORRIDO, BÚSQUEDA Y
ORDENAMIENTO DE ÁRBOLES E IDENTIFICACIÓN DE
GRAFOS.
 HABILIDAD DE RECONOCER Y MANIPULAR ALGORITMOS

SOBRE RECORRIDOS DE ÁRBOLES.

RESPECTO AL USO DE LOS GRAFOS.
 MEJORA DE HABILIDADES CREATIVAS, INVESTIGACIÓN Y

FACILIDAD DE COMUNICACIÓN ORAL Y ESCRITA.
147
En matemáticas y ciencias de la computación, un grafo, del

griego grafos, dibujo o imagen, se define como una colección
de objetos que permiten representar relaciones binarias entre
elementos de un conjunto. Son objeto de estudio de la teoría de
grafos y permiten estudiar las interrelaciones entre unidades que
interactúan unas con otras. Por ejemplo, una red de
computadoras puede representarse y estudiarse mediante un
grafo, en el cual los vértices representan terminales y las aristas
representan conexiones (las cuales, a su vez, pueden
ser cables o conexiones inalámbricas).
La teoría de grafos, que involucra grafos dirigidos, multigrafos,

árboles, árboles binarios, etc., se utilizan en muchas áreas de las
matemáticas y de la computación y se presentará en esta
unidad, partiendo de una definición matemática que dice que
un grafo G consta de dos partes:
a) Un conjunto V=V(G) cuyos elementos se

denominan vértices o nodos de G.
b) Un conjunto E=E(G) de pares no ordenados de

vértices distintos denominados aristas de G.
Cuando se desea recalcar las dos partes de un grafo G, se

denota como G(V,E). Ahora bien, los grafos se representan
mediante diagramas en el plano de forma natural.
148
Específicamente cada vértice v en V se representa por un

punto o circulo pequeño y cada arista se representa por una
línea recta o curva que une sus puntos extremos v1 y v2.
En la presente unidad, se reconocerán y definirán sus

componentes, la forma de representarlos y los algoritmos de
recorrido y búsqueda sobre un grafo.
5.1 Elementos, características y componentes de los grafos
Como se dijo en la introducción, sin duda alguna los dos

elementos componentes básicos de un grafo son los nodos o
vértices (puntos) y las aristas (caminos) del mismo.
Los vértices x,y de un árbol son adyacentes o vecinos si hay

una arista e={x,y}, en esta caso x y y se denomina extremos de e
y se dice que e conecta una x con y, o también se dice que la
arista es incidente en cada de los extremos de x,y.
Por ejemplo, la figura 5.1 siguiente representa al grafo simple G

(V,E), donde:
1) V consta de los vértices A, B, C y D.
2) E consta de la aristas e1={A,B}, e2={B,C}, e3 ={C,D},
e4={A,C}, e5={B,D}.
149
De hecho, un grafo suele denotarse al trazar su diagrama en

lugar de enumerar explícitamente sus vértices y aristas.
A B
0 0 vértices
0 0 aristas
C D
Figura 5.1 Grafo simple con vértices y aristas.
Así, un grafo simple o grafo, es aquel que no tiene lazos ni lados

paralelos. Por otra parte, un multígrafo es aquel que puede
tener uno o más lazos o aristas paralelas con respecto a dos
vértices que se unen.
Un multígrafo es un grafo que consta de segmentos múltiples y

lazos. Otra definición similar es que un multígrafo es un grafo en
el que hay pares de vértices unidos por más de una arista, es
decir, que tiene aristas múltiples, tal como lo muestra la figura
5.2 siguiente.
A e1 D e6
O O
e2 e3
B e5 C
O e4 O
Figura 5.2 Multigrafo con aristas múltiples e4 y e5, con lazo e6.
150
Grado de un grafo. El grado de un grafo G, es igual al número

de aristas que empiezan en v y el grado de entrada de v, es el
número de aristas que terminan en v, puesto que cada arista
empieza y termina en un vértice, se obtiene el teorema 5.1
siguiente: la suma de los grados de salida de los vértices de un
grafo dirigido G es igual a la suma de los grados de entrada de
los vértices, que es igual al número de aristas de G. Sea por
ejemplo el grafo de la figura 5.3 siguiente:
A D
O O
O O
B C
Figura 5.3 Grafo dirigido con aristas paralelas del vértice B al vértice A.
Se tiene de este grafo la relación que se muestra en la tabla

siguiente.
Vértice No. entradas No. salidas No. aristas

A 2 1
B 2 4
C 2 0
D 1 2 7
Total 7 7 7
Tabla 5.1 Relación de igualdad de entradas y salidas en un grafo.
151
Que prueba con certeza el teorema 5.1 mencionado.
El grado de un vértice v en un grafo G. se escribe como grd (v),

es igual al número de aristas en G que contienen a v; es decir,
que inciden sobre v. puesto que cada arista se cuenta dos
veces al contar el grado de los vértices de G, se obtiene el
siguiente teorema:
Teorema 5.2 La suma de los grados de los vértices de un grafo G

es igual al doble del número de aristas en G. tomando como
ejemplo el grafo de la figura 5.2 tenemos grd(A)=2, grd(B)=3,
grd(C)=3, grd(D)=4 y la suma de los grados es igual a doce,
entonces es de anticipar que el número de aristas del grafo es
igual a seis. Es importante recordar que un lazo es también una
arista y se cuenta doble.
La distancia (d) y diámetro (diam) de un grafo conexo G, se

refieren, primero a la distancia entre los vértices u y v en G, que
se escribe d(u,v), es la longitud de la ruta más corta entre u y v.
El diámetro de G, lo cual se escribe diam(G), es la distancia
máxima entre dos puntos cualesquiera en G. Por ejemplo, sean
los grafos de la figura 5.4.
152
B E A E
O O O O
D C D
AO O OH O O
O O O O
C F B F
(a) (b)
Figura 5.4 Distancia y diámetro de dos grafos conexos.
En primer plano se tiene que d(A,F)=2 y diam(G)=3, en segundo

plano tenemos que d(A,F)=3 y diam(G)=3.
Puntos de corte y puentes. Tomando como base el mismo

ejemplo, se dice que un vértice v en G se denomina punto de
corte si G–v es disconexo. Es decir que G–v es el grafo obtenido
a partir de G al eliminar v y todas las aristas que contienen a v.
una arista e de G se denomina puente si G–e es disconexo. En la
figura 5.4 (a), D es un punto de corte y en 5.4 (b), la arista {C,D}
es un puente. Sus vértices extremos C y D son necesariamente
puntos de corte.
5.1.1 Tipos de grafos
Una vez hecha la definición formal de un grafo, se tiene en el

punto presente los tipos de grafos más conocidos
popularmente, resaltando sus propiedades y características que
153
de manera especial tiene cada grafo. El orden no es relevante,

pero si el hecho de que primero se sepa que se está hablando
en lo general de representaciones geométricas de un tipo de
relaciones, que es especialmente importante para soportar los
teoremas mencionados y sus demostraciones y en donde el
lector deberá estar consciente de que en algunos casos las
soluciones gráficas son muy sencillas.
Pseudografo. Es aquel grafo facultado para tener aristas

múltiples; es decir, aristas que relacionan los mismos nodos. De
esta forma, dos nodos pueden estar conectados por más de
una arista.
Subgrafos. Por ejemplo sea G=(V,E) un grafo dirigido y sea V´ un

subconjunto del conjunto V de vértices de G. Suponga que E´
es un subconjunto de E tal que los puntos terminales de las
aristas de E´ pertenecen a V´. entonces H(V´,E´) es un grafo
dirigido y se denomina subgrafo de G. En particular, si E´
contiene todas las aristas de E cuyos puntos terminales
pertenecen a V, entonces H(V´,E´) se denomina subgrafo de G
generado o determinado por V´. por ejemplo sea el grafo G=G
(V,E), entonces H(V´,E´) es el subgrafo de G determinado por el
conjunto de vértices de V´, donde V´=(B,C,D) y E´={(D,B),
(B,C),(D,C),(B,B)}
154
Grafos Dirigidos: Las aristas o arcos en el grafo tienen una

dirección asociada. El primer elemento del arco es el origen y el
segundo es considerado el destino.
A B
C D
Del grafo anterior, se desprende la relación R de la siguiente

forma:
R = {( a,c), (a,d), ( b,a), ( b,d ), (c,a), (c,d), (d,a), (d,b)}
Y de ahí mismo, puede definirse el concepto de trayectoria,

como aquel recorrido que va de un vértice a otro. Si la
trayectoria inicia y termina en el mismo vértice, se llama ciclo
(TC) Así, partiendo del vértice A, se tiene una trayectoria TR de
longitud 3 para alcanzar el vértice B; TR = A,C,D,B.
Un ciclo del mismo ejemplo sería TC = B,A,C,D,B de longitud 4. En

cualquier caso, un lazo tendrá un ciclo de longitud 1.
155
Grafo conexo. En matemáticas y ciencias de la computación es

aquel grafo que entre cualquier par de sus vértices existe un
Camino (Grafo) que los une. Ejemplo de él, la figura siguiente.
A B C
O O O
O O
D E
Sea G = (V, E) un grafo dirigido, donde V es un conjunto y E es

un multiconjunto de pares ordenados de V V. G es llamado un
multígrafo dirigido y geométricamente se puede representar
como un conjunto de vértices V y un conjunto de flechas E entre
los vértices, donde no existe restricción en el número de flechas
de un vértice a otro y lo representa el diagrama anterior. Otros
ejemplos serían los gráficos siguientes, con la inclusión de un
grafo inconexo.
P1 P2 A C
O O O O
O O O O O
P3 P4 B E F
Grafo conexo. Grafo inconexo.
156
Un grafo etiquetado como el de la figura anterior, lo es

mediante la asignación de etiquetas y representado mediante
enteros, a las aristas o vértices o ambos de un grafo. El término
grafo etiquetado generalmente se refiere a un grafo con
vértices etiquetados con todas las etiquetas distintas.
Los grafos pueden ser equivalentemente etiquetados mediante

enteros consecutivos desde 1 hasta n, donde n es el número de
vértices en el grafo.
Para muchas aplicaciones, a las aristas y los vértices le

corresponden etiquetas que tienen un significado en el dominio
asociado. La figura siguiente, muestra un etiquetado elegante.
Las etiquetas de los vértices están en negro, las etiquetas de las
aristas en rojo.
157
Etiquetado armonioso: Un grafo armonioso es un grafo con “k”

aristas que permiten una inyección de
los vértices de “G” al grupo de enteros
modulo “k” que induce una bisección
entre las aristas de “G” y los enteros
positivos hasta n finito. Para cualquier
arista e, los etiquetados de e son la
suma de las etiquetas de dos vértices
incidentes con e.
Coloración de grafos: La coloración de grafos es un caso muy

especial para los grafos etiquetados, los vértices adyacentes y
las aristas coincidentes deben tener diferentes etiquetas.
Grafo completo: Dícese del grafo

no orientado que entre cualquier
par de sus nodos existe al menos
una arista que los une.
La familia de grafos Kn es la más

simple de los grafos completos,
aunque en el concepto general
no excluye la presencia de
multiaristas y/o lazos, haciendo
que los grafos completos no sean necesariamente simples.
158
Esto produce caminos mínimos entre cualquier par de vértices,

aunque debe significarse que para el caso de las aristas
etiquetadas la minimalidad de los caminos no correspondería
necesariamente a arcos que unen el par de vértices, sino
posiblemente a caminos con más aristas en dependencia de la
suma total de sus valores.
Como ya se dijo, un grafo G se denomina grafo etiquetado si sus

aristas y/o vértices son datos asignados de un tipo o del otro. En
particular un grafo se denomina grafo ponderado si a cada
arista G se asigna un número no negativo w(e) denominado
peso o longitud de v. La figura siguiente muestra un grafo
ponderado con peso en las aristas, así, el peso o la longitud de
un camino en tal grafo ponderado G se define como la suma
de los pesos de las aristas en el camino. El ejercicio sería, el de
tratar de encontrar el camino más corto entre dos vértices
arbitrarios. Así en dicha figura, se muestra la longitud de un
camino más corto entre P y Q, que es 14 y un camino que es (P,
A1, A2, A3, A4, A5, Q).
A1 A2 A3
2 3
1 O O O 4
P O 9 10 11 12 13 14 O Q
8 O O O 5 Figura 5.5 grafo etiquetado y

7 6 ponderado.
A4 A5 A6
159
Los grafos regulares son aquellos cuyos vértices tienen el mismo

grado. El grafo conexo 0 regular es el grafo trivial con un vértice
y con cero aristas, pero es regular. El grafo conexo 1 regular es el
grafo con dos vértices y una arista que los une. El grafo conexo
2 regular con n vértices es el grafo que consta de un solo ciclo n
y los podemos en las figuras siguientes.
K1 vértice aislado grado cero. (trivial)
O O
K2 segmento de línea grado uno
O O
K3 triángulo grado dos.
Los grafos bipartidos. Un grafo G es bipartido si sus vértices v

pueden partirse en dos subconjuntos M y N tales que cada arista
de G une un vértice de M con un vértice de N.
Un grafo plano es simplemente aquel grafo que puede trazarse

en el plano de modo que ninguna de sus aristas se cruce. Los
grafos árboles son el mejor ejemplo de grafos planos. Esto da
lugar a una representación plana denominada mapa. Se dice
160
que el mapa es conexo si el multigrafo subyacente es conexo.

Un mapa dado divide el plano en varias regiones. Por ejemplo,
el mapa de la figura 5.6 con 6 vértices y 9 aristas divide el plano
en cinco regiones. Observe que cuatro de las regiones están
acotadas y que la quinta región, fuera del diagrama, no está
acotado. Así, no hay pérdida de generalidad al contar el
número de regiones, si se supone que el mapa está contenido
en algún gran rectángulo, en lugar de estarlo en todo el plano.
Observe además que la frontera de cada región de un mapa

consta de aristas que algunas veces forman un ciclo. De la
misma figura las fronteras de todas las regiones son ciclos,
excepto para r3, no obstante, si se realiza un movimiento en el
sentido contrario de las manecillas del reloj alrededor de r 3,
empezando por ejemplo en el vértice C, entonces se obtiene el
camino cerrado (C,D,E,F,E,C), donde la arista {E,F} ocurre dos
veces. Por el grado de una región r, se escribe grd (r), se
entiende la longitud del ciclo o camino cerrado que rodea a r.
Observe que cada arista delimita dos regiones o está contenida
en una región y/u ocurre dos veces en cualquier recorrido a lo
largo de la frontera de la región. Por tanto, se tiene un teorema
para regiones semejante al teorema 5.1 de aristas.
Teorema 5.3 la suma de los grados de las regiones de un mapa

es igual al doble del número de aristas.
161
C
O
B
AO O r2 r3 FO OE
r1
r4 O D r5
Figura 5.6 Grafo de 6 vértices y 9 aristas.
Háganse entonces los cálculos: grd(r1)=3, grd(r2)= 3, grd(r3)=5,

grd(r4)=3, grd(r5)=4, así la suma de los grados es igual a 18, es
decir el doble del número de aristas.
Al respecto, Euler proporcionó el teorema 5.3 siguiente que dice,

siendo V el número de vértices, E el número de aristas y R el
número de regiones de cualquier mapa conexo, se cumple
que: V–E+R=2 y que en nuestro ejemplo sería: V=6, E=9 y R=5,
entonces resulta en 6–9+5=2, recalcando que el grafo
subyacente de un mapa debe ser conexo para que se cumpla
el mencionado teorema.
Un grafo denso, es un grafo en el que el número de aristas está

cercano al número máximo de aristas. Lo opuesto sería un grafo
disperso, es decir aquel que cuenta con solo unas pocas aristas,
aunque, a decir verdad, matemáticamente la distinción entre
ambos es relativamente vaga.
162
5.2 Representación de los grafos
Hay dos formas normales para mantener un grafo en la

memoria de la computadora y que están muy ligadas en el
aspecto matemático y computacional a la vez, toda vez que
una aplicación computacional tiene inevitablemente bases
matemáticas.
5.2.1 Matemática
Este modo de representar un grafo, se enfoca mediante una

representación secuencial de G, por medio de una matriz de
adyacencia, ya que están tienden a usarse cuando un grafo G
es muy denso, es decir cuando un grafo con G con m vértices y
n aristas es igual m=O(n2).
Supóngase que G es un grafo con m vértices y que los vértices

se han ordenado como v1, v2,…, vm, entonces, la matriz de
adyacencia queda así:
A = [a i,j] del grafo G y queda definida por:

Ai,j = 1 si vi es adyacente a vj.
Ai,j = 0 en otro caso.
La figura 5.7 siguiente contiene la matriz de adyacencia del

grafo G, en donde el orden de los vértices es A,B,C,D,E. Observe
que cada arista {vi,vj} de G está representado dos veces por
163
Ai,j=1 y Aj,i =1. Así es en particular porque la matriz de

adyacencia es simétrica.
A B C
O O O.
O O
D E
A B C D E
A 0 1 0 1 0
B 1 0 1 0 1
C 0 1 0 0 0
D 1 0 0 0 1
E 0 1 0 1 0
Figura 5.7 Grafo y matriz de adyacencia generada.
También, la matriz de adyacencia aplica para grafos dirigidos,

tal que A=[ai,j] define a la matriz tal que A con un número de
aristas empiezan en vi y terminan en vj. así, las entradas de A son
enteros no negativos.
A la inversa, toda matriz A, mxm, con entradas enteras no

negativas define de manera única un grafo dirigido con m
vértices.
Sea por ejemplo el grafo dirigido de la figura 5.8 siguiente con

vértices v1, v2, v3, v4.
164
V2 O O V1
V3 O O V4
Figura 5.8 Grafo dirigido con cuatro vértices.
Entonces la matriz de adyacencia A de G se muestra a

continuación, definiendo el grado de la matriz cuadrada; por
cierto, el número de vértices del grafo de la figura anterior es
cuatro.
0 0 0 1
1 0 1 1
1 0 0 1
1 0 1 0
Por ejemplo, sea el grafo no dirigido siguiente, obténgase su
matriz de incidencias.
165
La respuesta sería:
5.2.2 Computacional
La representación de los grafos en su forma computacional, se

enfoca como una representación enlazada o estructura de
adyacencia de G, usando listas ligadas de vecinos y que se usa
normalmente cuando G es disperso, es decir cuando m=O‡ (n) o
inclusive m=O(nlog(n)). La letra O se refiere a la cota superior
asintótica, que en análisis de algoritmos representa a una
función que sirve de cota superior de otra función cuando el
argumento tiende a infinito. Usualmente al respecto, se utiliza la
notación de Landau O(g(x), orden de g(x), coloquialmente
llamada O grande, para referirse a las funciones acotadas
superiormente por la función g(x).
‡
Cota superior asintótica.
166
Sea un grafo dirigido con m vértices y supóngase que G es

disperso, entonces la matriz de adyacencia A de G contiene
muchos ceros; por tanto, se desperdicia mucho espacio de
memoria. En consecuencia, cuando G es disperso, G suele
representarse computacionalmente en la memoria por medio
de una estructura de adyacencia, tal como se visualiza en el
ejemplo de la figura 5.9 siguiente.
A O OD vértices lista de adyacencia

A B,C,D
OE B C
C Ø (vacío)
B O O C D C,E
E C
Figura 5.9 Grafo disperso y lista de adyacencia de G.
En donde vemos al grafo G y su lista de adyacencia, también

denominada de sucesores o vecinos. Observe que cada arista
de G corresponde a un vértice único en una lista de
adyacencia y viceversa. Acercándonos un poco a una
descripción algorítmica, también puede decirse que la lista
siguiente es válida.
G = [A: B,C,D; B: C; C:Ø; D: C,E; E: C]
167
La representación ligada de un grafo dirigido G mantiene a G

en memoria mediante el uso de listas ligadas para sus listas de
adyacencia. Con más brevedad, la representación enlazada
normalmente contiene dos archivos (conjuntos de registros), uno
llamado Vertex file y el otro Edge file, como sigue:
a) Vertex File: Este archivo contiene la lista de vértices del

grafo G usualmente mantenida por medio de un arreglo o
por una lista ligada. Cada registro del archivo tiene la
forma
Vertex Next–V PTR
Vertex es el nombre del vértice, Next–V apunta al siguiente

vértice en la lista de vértices en el Vertex File y PTR apunta al
primer elemento de la lista de adyacencia del vértice que
aparece en la región Edge File. El área sombreada indica que
en el registro correspondiente al vértice puede haber otra
información.
b) Edge File: Este archivo contiene las aristas de G y todas las

líneas de adyacencias de G, donde cada lista se mantiene
en memoria por medio de una lista ligada. Cada registro
del Edge File representa una arista única en G y por tanto,
corresponde a un vértice único en la lista de adyacencia.
Normalmente, el registro tiene la forma:
168
Edge Beg-V End-V Next–E
Aquí Edge es el nombre de la lista. Beg–V apunta a la ubicación

del Vertex File del vértice inicial de la arista. End–V apunta a la
ubicación del Vertex File del vértice terminal de la arista. Las
listas de adyacencia aparecen en este campo; y por último
Next–E apunta a la ubicación en el Edge File del siguiente
vértice en la lista de adyacencia.
Recuerde que las listas de adyacencia constan de vértices

terminales, por lo que se mantienen mediante el campo End–V.
El área sombreada indica que en el registro correspondiente a
la arista puede haber otra información. Se observa que el orden
de los vértices en una lista de adyacencia no depende del
orden en que las aristas (pares de vértices) aparecen en los
datos de entrada.
El cuadro siguiente muestra la forma en que el grafo G de la

figura anterior puede aparecer en memoria. Aquí los vértices de
G se mantienen en memoria por medio de una lista ligada
usando la variable START para apuntar al primer vértice. De
manera alterna, podría usarse un arreglo lineal para la lista de
vértices, haciendo innecesario Next–V.
La elección de ocho ubicaciones para el Vertex file y diez

localizaciones para el Edge File es arbitraria. El espacio adicional
169
en los archivos se usa en caso de que en el grafo se inserten

vértices o aristas adicionales.
Start 3 archivo vértice
1 2 3 4 5 6 7 8
Vertex C A E B D
Next–V 8 6 0 1 5
PTR 0 3 10 6 1
Archivo arista
1 2 3 4 5 6 7 8 9 10
Beg–V 8(D) 3(A) 3(A) 6(B) 8(D) 3(A) 5(E)
End–V 1(C) 6(B) 6(D) 1(C) 1(C) 1(C) 1(C)
Next-E 7 9 0 0 4 4 0
Un ejemplo más, sería representar la lista de incidencias sobre un

arreglo de objetos que contienen los números de vértices sobre
los que inciden las aristas de la forma siguiente:
[(0,1), (0,6), (0,8), (1,4), (1,6), (1,9), (2,4), (2,6), (3,4), (3,5), (3,8),
(4,5), (4,9), (7,8), (7,9)]
Generando así una lista de adyacencia como la que se muestra

a continuación, en donde cada vértice i,j almacena un arreglo
de los vértices adyacentes a él.
170
5.3 Algoritmos de recorrido y búsqueda
Sea G un grafo dirigido con m vértices V 1, V2, …, Vm. y suponga

que desea encontrar la matriz de caminos P del grafo G.
El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy,
es un algoritmo de análisis sobre grafos para encontrar el
camino mínimo en grafos dirigidos ponderados. El algoritmo
encuentra el camino entre todos los pares de vértices en una
única ejecución y es un ejemplo de programación dinámica.
5.3.1 El camino más corto
Sea un grafo dirigido simple con m vértices y suponga que G es

ponderado; es decir, supóngase que a cada arista e de G se
asigna un número no negativo w(e) denominado peso o
longitud de e, entonces G puede mantenerse en la memoria de
la computadora por medio de su matriz de pesos W=[w i,j]
definida como sigue:
171
wi,j = {w(e) si hay una arista e de vi a vj; 0 si no la hay}
La matriz de caminos P indica si entre los vértices hay o no

caminos. Ahora se desea encontrar una matriz Q de las
longitudes de los caminos más cortos entre los vértices, o más
exactamente, una matriz Q=[qij], donde [qij]=longitud del
camino más corto de vi a vj.
Partiendo del algoritmo de Warshall, se tiene que:
Qk[i, j]=MIN((Qk-1)[i, j], Qk-1[I, k]+Qk-[k,j]), la matriz inicial Q0 es la

misma que la matriz de pesos W, excepto que cada cero en w
se sustituye por (o por un número muy grande). La matriz final
Qm es la matriz buscada Q.
Por ejemplo, en la figura 5.10 siguiente se muestra un grafo

ponderado G y su matriz de pesos W, donde se supone que:
v1=R y v2=S, v3=T, v4 = u, suponga que en el modelo del algoritmo
de Warshall se aplica el grafo ponderado G y se obtienen las
matrices Q0,Q1,Q2,Q3 de la misma figura 5.10.
7 7 4 Y la matriz asociada:
7 5 0 0
RO OU W= 7 0 0 2
5 7 2 1 0 3 0 0
4 0 1 0
en función del algoritmo de
Warshall.
SO O T
3
Figura 5.10 Grafo ponderado y matriz asociada y su matriz de pesos W.
172
Obtenemos: Q1[4,2]=MIN(Q0[4,2], Q0[4,]+Q0[1,2])=MIN(
Q2[1,3]=MIN(Q1[1,3], Q1[1,2]+Q1[2,3])=MIN(
Q3 [4,2]=MIN(Q2[4,2], Q2[4,3]+Q2 [3,2])=MIN(9,3 + 1)=4
Q4[4,1]=MIN(Q3[3,1], Q3[ 3,4]+Q3[ 4,1])=MIN(
La última matriz Q4=Q, representa la matriz buscada con el

camino más corto.
5.3.2 A lo ancho
El algoritmo aplica para un grafo G dado, que se mantiene en

la memoria de la computadora, mediante su estructura de
adyacencia. Muchas aplicaciones de grafos requieren el
examen sistemático de los vértices y las aristas. Hay dos formas
algorítmicas normales para hacer lo anterior. Una forma se
denomina en anchura (BFS: breadth first search) y la otra en
profundidad (DFS: depth first search) y se presentan a
continuación.
Algoritmo BFS: Este algoritmo ejecuta una búsqueda de anchura

sobre un grafo dirigido G, empezando en un vértice inicial A.
All vertex inician en estado ready (status = 1)

Vertex initial A introducing en QUEUE y el status de A se cambia
al estado waiting (status = 2)
Repeat steps 4 y 5 until QUEUE is empty.
173
Sacar the first vertex N de QUEUE. Processing N y se

establece status N=3, status processed.
Se examina cada vecino J de N:
If status(j)=1 (status ready), se coloca en la parte

trasera de QUEUE y se restablece status (J)=2 (status
waiting);
If status (j)=2 (status waiting) OR status (j=3), (status

processed), ignorar vértice j.
Until {fin de ciclo paso 3}
Salir.
Suponga el grafo G siguiente y su estructura de adyacencia.
A O
E
FO O OB
C
DO O O L
JO O K
Lista de adyacencia asociada.
A B C D E F J K L
B,E,F E,L D,E,J E F D D,K C,L C,E
174
La tabla siguiente:
VÉRTICE A BA EA FA LB DF CL JC
QUEUE A FA,EA,BA LB,FA,LA LB,FA DF,LB CL,DF CL JC
Muestra la secuencia de listas de espera de QUEUE y los vértices

que se están procesando hasta el momento en que se
encuentra el vértice j. Luego se trabaja hacia atrás a partir de j
para obtener el siguiente camino deseado y que se muestra en
la figura siguiente:
A O
E
FO O OB
C
DO O O L
O O
Jc CL LB BA A oA B L C J. Así, por ejemplo, un

vuelo de la ciudad A a la ciudad J hará tres escalas intermedias
en B, L y C. Observe que el camino no incluye todos los vértices
procesados por el algoritmo.
5.3.3 En profundidad. La idea general en una búsqueda de

profundidad que empieza en un vértice inicial A es: primero se
175
procesa el vértice inicial A. luego se procesará cada vértice N a

lo largo del camino P, que empiece en A; es decir, se procesa
un vecino de A, luego un vecino del vecino de A y así
sucesivamente. Después de llegar a un punto muerto, es decir a
un vértice sin vecino no procesado, se retrocede sobre el
camino P, hasta que sea posible continuar a lo largo de otro
camino P´ y así se continua del mismo modo.
El retroceso se logra usando un STACK para mantener los

vértices iniciales de futuros caminos posible. También se requiere
un campo STATUS que indica el estado actual de cualquier
vértice, de modo que ningún vértice sea procesado más de una
vez. Se muestra a continuación dicho algoritmo.
Algoritmo de profundidad DFS: este algoritmo ejecuta una

búsqueda de profundidad sobre un grafo dirigido G,
empezando en un vértice inicial A.
All vertex initial in status ready (STATUS=1)

The vertex initial A se introduce en STACK y el status de A
change to state waiting (STATUS=2).
REPEAT {pasos 4 y 5 UNTIL STACK IS EMPTY}
The vertex superior N se saca del STATUS. Se procesa N y se
establece STATUS N = 3. STATUS PROCESSED.
Examinar cada vecino J de N.
176
IF STATUS J = 1 (STATUS READY), J se coloca sobre STACK y se

restablece STATUS j = 2 (STATUS WAITING)
IF STATUS J = 2 (STATUS WAITING), el J previo se elimina de
STACK y EL J actual se coloca sobre STACK.
IF STATUS J = 3 (STATUS PROCESSED), se ignora el vértice J.
{fin del ciclo del paso 3}
Salir. {end interno}
Considere el grafo de prueba G de la figura 5.11 siguiente y
suponga que desea encontrar todos los vértices alcanzables
desde el vértice j (incluso a j). Una forma de hacerlo es aplicar
un algoritmo en profundidad de G empezando en el vértice J. la
respuesta será: J, K, L, E, F, D, C
A O
E
FO O OB
C
DO O O L
J O OK
Figura 5.11 Grafo de prueba G.
La tabla siguiente muestra la secuencia de las listas de espera

en STACK y los vértices que están en proceso, la diagonal indica
que un vértice se elimina de la lista de espera. Recuerde que
cada vértice, excepto J, proviene de una lista de adyacencia,
177
por lo tanto, es el vértice terminal de una arista única del grafo.

La arista se ha indicado al etiquetar el vértice terminal con el
vértice inicial de la arista como un subíndice. Por ejemplo, Dj
significa que D está en la lista de adyacencia de J y entonces
que D es el vértice terminal de una arista que empieza en j.
Vértice J KJ LK EL FE DF CL
STACK J KJ,DJ LK,CK,DJ EL,CL,CK,DJ FE,CL,DJ DF,CL,DJ CL Ø
Estas aristas constituyen un árbol T cuya raíz es J y se muestra en

la figura siguiente a partir del grafo problema.
A O
E
FO 4 O OB
5 C 3
DO O 6 O L
2
J O OK
1
Los números significan el orden en que las aristas se agregan al

árbol. Este árbol T, genera un subgrafo G´ de G que consta de
los vértices alcanzables desde J y representan la solución del
problema en las aristas etiquetadas.
178
Ejercicios propuestos de la unidad V y solución a problemas nones.
1) Sea el grafo G de la figura siguiente:
X O OY
Z O OW
1.1 Describa formalmente a G. Respuesta: G tiene cuatro vértices y siete

aristas, tal que: V={X,Y,Z,W} y sea E= al conjunto de aristas, de donde
E={( X,Y), (X,Z), (X,W), (Y,W), (Z,Y), (Z,W), (W,Z )}
1.2 Encuentre todos los caminos simples de X a Z.
1.3 Encuentre todos los caminos simples de Y a Z. Respuesta. Solo hay un

camino simple que es (Y,W,Z)
1.4 Encuentre todos los ciclos en G. Respuesta. En G solo hay un ciclo, que
es (Y,W,Z, Y).
1.5 ¿Es G unilateralmente conexo?. Respuesta. Si. G es unilateralmente

conexo, ya que (X,Y,W,Z), es un camino de expansión.
1.6 ¿Es G fuertemente conexo?
1.7 Partiendo del mismo grafo del ejercicio 1. Calcular el grado de

entrada y el grado de salida de cada vértice de G. Respuesta:
Ingrd (X) = 0, Outgrd (X) = 3
Ingrd (Y) = 2, Outgrd (Y) =1
179
Ingrd (Z) = 2, Outgrd (Z) = 2
Ingrd (W) = 3, Outgrd (W) = 1
1.8 Encuentre el subgrafo H de G determinado por el conjunto de vértices

V´ = X,Y,Z.
1.9 Sea el grafo G siguiente:
B O
A O OC
E O D O
Describa formalmente a G. Respuesta: hay cinco vértices, de modo

que V(G) = {A,B,C,D,E}. Hay siete pares {x,y} de vértices, donde el
vértice x está unido al vértice y; así que: E (G) = [{A,B}, {A,C}, {A,D},
{B,C}, {B,E}, {C,D}, {C,E}]}
1.10 Demuestre que la suma de los grados de cada nodo, es igual a dos
veces el número de aristas.
180
UNIDAD VI
ÁRBOLES Y
REDES
182
 APLICAR LA ORGANIZACIÓN Y RELACIÓN ENTRE LOS DATOS

MEDIANTE PROCESOS DE ORDENAMIENTO, PARA RESOLVER
PROBLEMAS DE PROGRAMACIÓN MATEMÁTICA,
UTILIZANDO LOS CONOCIMIENTOS SOBRE ÁRBOLES, REDES Y
OTRAS ESTRUCTURAS DE MANIPULACIÓN Y
ALMACENAMIENTO DE DATOS.
 HABILIDAD DE RECONOCER Y MANIPULAR ALGORITMOS

SOBRE RECORRIDOS DE ÁRBOLES Y OTRO TIPO DE GRAFOS.

RESPECTO AL USO DE LOS GRAFOS, CUANDO SON ÁRBOLES.
 MEJORA DE HABILIDADES CREATIVAS, INVESTIGACIÓN Y

FACILIDAD DE COMUNICACIÓN ORAL Y ESCRITA.
 RECONOCIMIENTO DE LA RELACIÓN TEÓRICO–PRÁCTICA

DEL CONCEPTO DE REDES EN EL ÁMBITO COMPUTACIONAL.
183
Matemáticamente hablando, un árbol es un tipo de grafo, con

la diferencia de que no tiene ciclo o lazo alguno y que se verá
más adelante. Más aún, un árbol binario es una estructura
fundamental en las matemáticas y ciencias de la computación
manejando términos como raíz, arista, camino, rama, hoja,
profundidad, etc., necesarios para poder entender dicha
estructura lógica, recorrido y aplicaciones.
6.1 Árboles
En las matemáticas y más específicamente en la teoría de

grafos, un árbol es un grafo no dirigido en el que cualesquiera
de los dos vértices están conectados por exactamente un
camino simple. En otras palabras, cualquier gráfico que utiliza
vértices y aristas, ausente de ciclos simples es un árbol.
Otras definiciones, dicen que un árbol es una estructura de

datos no lineales, también es una colección de nodos donde
cada uno almacena información y guarda direcciones de sus
sucesores.
Un árbol consiste en un nodo (r denominado nodo raíz) y una

lista o conjunto de nodos (B, C, D, etc.) que componen por si
mismos un conjunto de subárboles.
184
La figura 6.1 siguiente representa un diagrama de árbol.
Figura 6.1 Representación de un árbol.
Otra definición gráficamente representada se visualiza en las

figuras siguientes, en donde se habla de un Árbol binario lleno, o
sea aquel en el que todos los nodos tienen cero o 2 hijos con
excepción de la Raíz.
185
Y otros grafos que definen un árbol binario perfecto, en donde

todos los vértices están en el mismo nivel y en el árbol binario no
perfecto los vértices del nivel 4 rompen la perfección.
6.1.1 Componentes y propiedades
El primer componente es un único elemento llamado raíz del

árbol. El árbol está compuesto por nodos lo cuales pueden tener
muchos hijos o ninguno, el único nodo que no tiene padre es el
nodo raíz del árbol, también se encuentra el nodo hoja o
externo, que es como se le denomina a un nodo sin hijos. Los
nodos hermanos son todos aquellos descendientes directos de
un mismo nodo.
La altura es un componente muy importante y es la longitud del
camino más largo que comienza en el nodo y termina en una
hoja.
186
La profundidad es la medida de la longitud que comienza en la

hoja y termina en el nodo y la hoja es aquel nodo sin
descendientes.
El grado es el número de descendientes directos de un
determinado nodo.
Figura 6.2 Árbol y sus elementos componentes.
Dicho de otra manera, la altura o profundidad de un árbol es el

largo del mayor camino de la raíz a una hoja.
Dado un camino < v0, v1, v2, ..., vk > el largo de este camino es
k. Por lo cual el largo de un camino es igual al número de arcos
del camino.
Así mismo, el peso de un árbol en un nodo dado, es el número

de nodos en el árbol sin contarse el mismo. El peso de un nodo
en un árbol es la longitud del camino más largo del nodo a una
187
hoja y a los descendientes de cualquier vértice se les llama

sucesores inmediatos.
6.1.2 Clasificación por altura y número de nodos
Figura 6.3 Altura o profundidad de un árbol.
Un árbol T, se dice que es completo si todos sus niveles, excepto

posiblemente el último, tienen el mismo número de nodos
posibles y si todos los nodos en el último nivel se encuentran lo
más posible a la izquierda.
De la figura anterior, se puede deducir que un árbol podría

tener un número infinito de vértices (diferentes del nivel cero),
de hecho, cualquier vértice podría tener un número infinito de
descendientes. Sin embargo, en nuestro caso de estudio no será
así.
188
6.2 Árboles con peso
partiendo del teorema 6.1 que dice que siendo (T, v0) un árbol
arraigado, entonces: no existen ciclos en T. V 0, es la única raíz de
T y cada vértice en T, diferente de V 0, tiene una entrada y V0, no
tiene entradas.
Lo que entonces permite entender y definir que el peso de un

árbol en un nodo dado es el número o valor positivo asignado a
cada arista en su totalidad, inclusive cero.
Normalmente, al peso de una arista se le designa por w y así la

suma de todos los vértices de un árbol con peso se le llama el
peso del grafo.
También el peso de un árbol está directamente ligado al

número de nodos contenido en cada nivel.
Por ejemplo, sea la figura 6.4 siguiente
PESO
O 1
O O 2
O O O O 4
O O O O O O O O 8
Figura 6.4 Peso de un árbol igual a 15 (suma de vértices por cada nivel)
189
O bien, a decir de la figura 6.5, que el peso de cada arista a

partir de la raíz (r), hacia el vértice v 1 y hacia el vértice v2,
equivale a 5 y 8 respectivamente.
r O
6 5
v0 O O v1
2 4 4 9
v2 O v3 O O v4 O v5
Figura 6.5 Peso de las aristas de r a v1 y v2
6.2.1 Recorrido de un árbol
El recorrido del árbol se refiere al procedimiento algorítmico de

visitar cada nodo de la estructura de datos que este árbol
representa.
De una manera sistemática, estos algoritmos de recorrido están

clasificados por el orden en el que se visitan todos y cada uno
de los nodos del árbol en cuestión.
Hay tres tipos de recorrido en profundidad:
Pre-orden (Raíz, Izquierdo, Derecho)

Para recorrer un árbol binario no vacío en pre orden, hay que
realizar las siguientes operaciones recursivamente en cada
nodo, comenzando con el nodo de raíz:
190
 1. Visite la raíz
 2. Atraviese el sub-árbol izquierdo
 3. Atraviese el sub-árbol derecho
In-orden o sub-orden (Izquierdo, Raíz, Derecho)
Para recorrer un árbol binario no vacío en in-orden (simétrico),
hay que realizar las siguientes operaciones recursivamente en
cada nodo:
 Atraviese el sub-árbol izquierdo
 Visite la raíz
 Atraviese el sub-árbol derecho
Post-orden (Izquierdo, Derecho, Raíz)
Para recorrer un árbol binario no vacío en post orden, hay que
realizar las siguientes operaciones recursivamente en cada
nodo:
 Atraviese el sub-árbol izquierdo

 Atraviese el sub-árbol derecho
 Visite la raíz
Mismos que visualizamos en el diagrama 6.6 siguiente.
Figura 6.6 Los tres tipos de recorridos de un árbol.
191
Un ejercicio más, se aprecia en la figura 6.7 siguiente para el

recorrido pre-orden de un árbol binario; recordando la
secuencia algorítmica raíz, izquierda y derecha.
Figura 6.7 Recorrido pre-orden de un árbol binario.
Y los diagramas 6.8 y 6.9 los recorridos post-orden e in-orden

respectivamente, haciendo uso del mismo árbol.
Figura 6.8 Recorrido post-orden de un árbol binario (I-D-R).
192
Figura 6.9 Recorrido in-orden de un árbol binario (I-R-D).
Otra técnica menos común, o quizá menos requerida, es la

llamada búsqueda en amplitud, en donde empezando por la
raíz del árbol, se recorren los demás nodos ordenados por el
nivel al que pertenecen en orden de Izquierda a derecha.
Este tipo de búsqueda se caracteriza porque se hace nivel por

nivel y de izquierda a derecha. En la imagen siguiente, se
observa cómo es que un nodo es buscado mediante la
búsqueda en profundidad.
En dicha imagen, se observa perfectamente que el árbol es

recorrido en su totalidad; pero esto no siempre puede ser así, ya
que el algoritmo se detiene cuando el elemento buscado es
encontrado o con la salvedad que como en el caso de
cualquier otra estructura de datos, el elemento o dato a buscar
exista más de una vez, con la consecuente modificación del
algoritmo.
193
Figura 6.10 Recorrido o búsqueda por amplitud de un árbol binario.
Por ejemplo, sea la expresión algebraica siguiente enmarcada

entre paréntesis. (3–(2xX))+((X–2)–(3+X)), se supone, que, en esta
expresión, ninguna operación puede ejecutarse hasta que sus
dos argumentos sean ejecutados. Resulta fácil ver que en tales
operaciones existe un operador que corresponde al último
cálculo que puede ejecutarse. El operador + es el operador
central de dicha expresión, lo que hace posible representarla en
modo de árbol binario etiquetado, así dicho grafo se etiqueta
con el operador central como raíz y los dos descendientes de
ella se etiquetan con los operadores centrales de las expresiones
de los argumentos izquierdo y derecho, respectivamente.
Si algún argumento es una constante o una variable y no una

expresión, ésta se usa para etiquetar el descendiente
correspondiente. El algoritmo de recorrido empleado, dicho sea
de paso es en modo in-orden.
194
Este proceso continúa hasta que la expresión termina. La figura

6.11 siguiente muestra el árbol de la expresión original
planteada.
(3–(2 x X))+((X–2)–(3+X))
raíz
O +
O - O-
O3 Ox O- O+
O OO O O O
2 x x 2 3 x
Figura 6.11 Árbol binario conteniendo una expresión algebraica.
El ejemplo siguiente muestra un árbol etiquetado binario y que

sirve de repaso en la comprensión de los algoritmos de
recorrido.
Recorreremos el árbol en el orden siguiente:
195
• Recorrido Pre Orden (R-I-D)

• RESPUESTA: 15, 6, 4, 10, 20, 17, 22
• Recorrido En Orden(I-R-D)
• RESPUESTA: 4, 6, 10, 15, 17, 20, 22
• Recorrido Post Orden(I-D-R)
• RESPUESTA: 4, 10, 6, 17, 22, 20, 15
Otra técnica en la búsqueda y recorrido de árboles, es la

conocida como la búsqueda en profundidad y es otro
procedimiento para visitar sistemáticamente todos los vértices
de un grafo. Es adecuado especialmente para resolver
problemas de optimización, en los que se deba elegir la mejor
solución entre varias posibles.
Al igual que en la búsqueda en amplitud se comienza en un

vértice r (la raíz), que es el primer vértice activo.
En el siguiente paso, se etiquetan como visitados todos los

vecinos del vértice activo que no han sido etiquetados. Se
continúa etiquetando a todos los vecinos de los hijos del vértice
en cuestión (que no hayan sido visitados aún). En este proceso
nunca se visita un vértice dos veces, por lo que se construye un
grafo sin ciclos, que será un árbol. Esta técnica la visualizamos
en el grafo de la figura siguiente.
196
Figura 6.12 Búsqueda o recorrido en profundidad sobre un árbol.
La cantidad de aplicaciones haciendo uso de los árboles

binarios, propiamente como estructura de datos, pueden ser
muy útiles, por ejemplo, cuando se trata de hacer modelos de
procesos en donde se requiere tomar decisiones en uno de dos sentidos
en cada parte del proceso.
Suponiendo, que se tiene un arreglo en donde se quieren encontrar

todos los datos duplicados. Esta situación es bastante útil en el manejo
de las bases de datos, para evitar un problema que se llama
redundancia. Una manera de encontrar los elementos duplicados en
un arreglo es recorrer todo el arreglo y comparar con cada uno de los
elementos del arreglo. Esto implica que, si el arreglo tiene muchos
elementos, se deben hacer demasiadas comparaciones.
Con una estructura de árbol binario, el número de comparaciones se

puede reducir considerablemente. Un bosquejo del algoritmo podría
verse así:
197
Colocar el primer dato del arreglo en el nodo raíz del árbol.
Comparar cada elemento del arreglo con el dato raíz.
Si el elemento del arreglo es igual al del nodo raíz, notificar duplicidad

de dato.
Si el elemento es menor, entonces crear hijo nodo izquierdo, en caso

contrario crear nodo hijo por derecha.
Una vez concluido este proceso y haber creado un árbol binario, se

deben buscar los elementos repetidos, haciendo:
Si x es el dato a buscar y sea k la información del nodo actual p;
Si x > k, entonces cambiar el nodo actual a der (p);
Sino, Si x = k informar de una duplicidad;
Sino, Si x < k, entonces cambiar el nodo actual a izq (p).
También es factible una rutina para proceder en sentido contrario, en

donde los elementos del árbol T, se transfieren a un vector V,
procediendo como una rutina de ordenamiento del vector, pero ahora
mediante un recorrido post-orden del árbol T.
198
5 8
1 36 7
1
3
5
6
7
8
9
Figura 6.13 Transferencia y ordenamiento de datos del árbol T hacia el vector V.
6.3 Redes
Considerando que el término redes es ambiguo, se define el
concepto de red como aquella gráfica dirigida, simple y con
pesos, que debe cumplir las siguientes condiciones:
 Poseer una fuente o vértice fijo que no tiene aristas de
entrada.
 Poseer un sumidero o vértice fijo que no tiene arista de
salida.
 El peso Ci,j de la arista dirigida de i a j llamado capacidad
de “ij”, es un número no negativo.
199
6.3.1 Teorema del flujo máximo

Se puede considerar un grafo como una red de flujo, donde un
nodo fuente produce o introduce en la red cierta cantidad de
algún tipo de material (datos) y un nodo sumidero lo consume.
Cada arco, por tanto, puede considerarse como un conducto
que tiene cierta capacidad de flujo.
Una red de flujo es un grafo dirigido G=(V, E) donde cada arco
(u, v) perteneciente a E tiene una capacidad no negativa.
(valores entre paréntesis). Se distinguen dos nodos: la fuente o
nodo S, y el sumidero o nodo T. Si existen múltiples fuentes y
sumideros, el problema se puede simplificar añadiendo una
fuente común y un sumidero común.
La figura 6.14 siguiente representa este concepto.
1 (7.6) 2
O O (0.5)
(5.5)
O (0.1) (4.3) (1.1) O T
S (0.1)
(3.2) (0.7)
O O
3 (8.0) 4
Figura 6.14 Red de representación de flujos y peso de aristas.
El algoritmo en cuestión, depende de tres conceptos

principales: un camino de aumento es una trayectoria desde el
nodo fuente S al nodo sumidero T que puede conducir más flujo,
200
que deriva en el teorema de Ford–Fulkerson que dice: En

cualquier red, el flujo máximo que fluye de la fuente al destino
es igual a la capacidad del corte mínimo que separa a la
fuente del destino.
6.3.2 Teorema del flujo mínimo
La teoría de flujo de mínimo y el costo o peso asociado al arco,

tiene una posición medular entre los problemas de optimización
de redes; primero, abarca una clase amplia de aplicaciones y
segundo, su solución es muy eficiente. Igual que el problema del
flujo máximo, toma en cuenta un flujo en una red con
capacidades limitadas en sus arcos.
Sea un problema de la ruta más corta, considera un costo

(distancia o peso), para el flujo a través de un arco o arista. Es
factible también manejar varios orígenes (nodos fuente) y varios
destinos (nodos demandas) para el flujo lógico, de nuevo
con costos asociados.
A continuación, están listadas las condiciones básicas ante un

problema del flujo de costo mínimo:
1. La red es una red dirigida conexa.

2. Al menos uno de los nodos es nodo fuente.
3. Al menos uno de los nodos es nodo demanda.
4. El resto de los nodos son nodos de trasbordo.
201
5. Se permite el flujo a través de un arco sólo en la dirección

indicada por la flecha, donde la cantidad máxima de flujo
está dada por la capacidad del arco. (Si el flujo puede
ocurrir en ambas direcciones, debe representarse por un
par de arcos con direcciones opuestas.)
6. La red tiene suficientes arcos como suficiente capacidad
para permitir que todos los flujos generados por los nodos
fuente lleguen a los nodos demanda.
7. El costo del flujo a través del arco es proporcional a la
cantidad de ese flujo, donde se conoce el costo por
unidad.
8. El objetivo es minimizar el costo total de enviar el suministro
disponible a través de la red para satisfacer la demanda
dada. (Un objetivo alternativo es maximizar la ganancia
total del envío.)
En la siguiente tabla se muestran algunos tipos de aplicaciones
comunes del problema de flujo mínimo:
Tipo de Aplicación Nodos Fuentes Nodos de Trasbordo Nodos de Demanda

Operación de una red de Fuentes de bienes Almacenes intermedios Consumidores
distribución
Administración de Fuente de desechos Instalaciones de Rellenos
desechos sólidos sólidos procesamiento
Operación de una red de Agentes de ventas Almacenes intermedios Instalaciones de
suministros procesamiento
Coordinación de mezcla Plantas Producción de u Mercado del
de productos en plantas artículo específico producto específico
Administración de flujo de Fuentes de efectivo en Opciones de inversión a Necesidades de
efectivo tiempos específicos corto plazo efectivo en tiempos
específicos
202
6.3.3 Pareo y Redes de Petri
El término pareo se refiere a un grafo dado y se define como un

subconjunto de aristas los cuales no tienen vértices en común.
El grafo de la figura 6.14 siguiente representa este concepto.
Pareos: AB, AG, FE, GE, JK, HI.
A G H I
O O O O
B O OC
D
O
O O O O
F E J K
Figura 6.14 Grafo y pareos sin vértices comunes.
Dicho de otra manera, dado un grafo G = (V,E) con V vértices y

E aristas, un apareamiento M en G es un conjunto de aristas no
adyacentes entre sí. Un vértice está apareado (acoplado
saturado) si es incidente con una arista en el apareamiento. En
otro caso, el vértice está libre.
La figura 6.15 (a) siguiente muestra un ejemplo de

apareamiento libre y 6.15 (b), un caso de vértice saturado por
incidencia con una arista en el apareamiento.
203
Vértice saturado.
O O O O O
O O O
O O O O
(a) (b)
Figura 6.15 Grafos con pareos marcados con línea gruesa entre dos vértices.
Una red de Petri o gráficas modelo del procesamiento

concurrente, son un método para modelar y estudiar el
procesamiento concurrente. Es una gráfica dirigida y bipartita,
en la cual las dos clases de vértices se llaman lugares y
transiciones y esta permite la existencia de aristas paralelas.
Una red de Petri, se define también como un grafo dirigido

bipartito, con un estado inicial, llamado marcación inicial. Los
dos componentes principales de la red de Petri son los sitios
(también conocidos como estados) y las transiciones.
Gráficamente, los sitios son pequeños círculos y las transiciones

barras o rectángulos. Las aristas del grafo se conocen como
arcos. Estos tienen un peso específico, el cual es indicado por un
número entero positivo que van del sitio a la transición y
viceversa. Por simplicidad, el peso de los arcos no se indica
cuando éste es igual a 1. Un arco que esté etiquetado con k
puede ser interpretado como k arcos paralelos.
204
Debe recordase que un grafo G es bipartito si sus vértices V

pueden partirse en dos subconjuntos M y N, tales que cada
arista de G une un vértice de M con un vértice de N y este grafo
se denota como Km,n.
La figura 6.15 siguiente muestra una representación de una red

de Petri.
Figura 6.15 Representación de una red de Petri.
De la figura anterior, se dice que si una arista va del lugar (L) al

estado de transición (T), entonces L es un lugar de entrada para
la transición T.
Un lugar de salida se define de manera análoga. Si cada lugar

de entrada de una transición T tiene al menos un elemento,
decimos que T está activada.
205
Ejercicios propuestos de la unidad VI y solución a problemas nones.
1) Sea el grafo G de la figura siguiente, que tiene 8 árboles de

expansión y que cada uno de ellos debe tener 4–1= 3 aristas, ya que
G tiene cuatro vértices. Gráficamente obtenga la respuesta.
Grafo G O O O
O
Respuesta: 8 árboles de expansión.
O O O O O O O O O O O O
O O O O
1 2 3 4
O O O O O O O O O O O O
O O O O
5 6 7 8
2) Sea un grafo G con más de un vértice. Demuestre que las siguientes

afirmaciones son equivalentes. Respuestas a preguntas nones.
2.1 G sea un árbol. Se implica por pregunta 2.2. Sean u y v dos vértices
en G. Respuesta: puesto que G es un árbol, G es conexo, de modo que
hay por lo menos un camino entre u y v.
2.2 Cada par de vértices está unido por exactamente un camino

simple.
2.3 G es conexo; pero G – e es inconexo para cualquier arista e de G.

Se implica por pregunta 2.4. Respuesta. Si en G hay un ciclo C que
206
contiene una arista e = {u, v}; por hipótesis, G es conexo, pero G´ = G – e

es inconexo, donde u y v pertenecen a componentes distintos de G´.
por tanto, G está libre de ciclos
2.4 G está libre de ciclos, pero si a G se le agrega cualquier arista, el

grafo resultante tiene un ciclo y ya no será un árbol.
3) Sea el árbol de la figura siguiente: identifique el tipo de recorrido

realizado.H,C,D,A,I,J,E,K,F,M,N,L,G,B,R.Respuesta:recorrido postorden.
O R (raíz)
O A B O
O C D O EO F O G O
O H IO J O K O L O
M O N O
4) Sean los grafos conexos siguientes, respecto del flujo máximo y

puntos de articulación del grafo.
1 2 2 5
O O O O
1 O O7
3O 4O O 5 O 6 3 O O O
4 6
O 7 O8
Grafo (A) Grafo (B)
207
4.1 Identifique el nodo crítico de cada uno de ellos. Respuesta. Grafo A

vértice 5 y grafo B vértice 4.
4.2 Explique cuando se dice que el grafo tiene conectividad.
5) Mediante un ejemplo práctico explique:

5.1 ¿Qué entiende por circuito Hamiltoniano? Respuesta. Un circuito
Hamiltoniano en un grafo, es aquel camino en una sucesión de
aristas adyacentes, que visita todos los vértices del grafo una sola
vez. Si además el último vértice visitado es adyacente al primero, el
camino es un ciclo Hamiltoniano.
5.2 Explique mediante un ejercicio práctico el problema de los circuitos
de Euler.
208
CONCLUSIONES
CONCLUSIONES
El mejor conocimiento posible de las matemáticas discretas,

entendiéndolas como aquella área de las matemáticas
encargadas del estudio de los conjuntos discretos finitos o
infinitos numerables, resulta fundamental para el estudio de las
ciencias de la computación, toda vez que son computables las
funciones de conjuntos numerables y que todo estudiante de
ingeniería tiene el compromiso de conocer.
Su conocimiento, nos hace entender, que éstas estudian
aquellas estructuras cuyos elementos pueden contarse uno por
uno separadamente. Es decir, los procesos en matemáticas
discretas son contables, como por ejemplo los números enteros,
los grafos o las sentencias lógicas.
El estudiante dará por entendido, que las matemáticas discretas
no manejan valores intermedios bajo ninguna circunstancia.
En matemáticas discretas el resultado de una incógnita puede
ser cero o uno lógico o falso y verdadero, pero jamás una
aproximación.
Las gráficas en matemáticas discretas sí existen y vienen dadas
por un conjunto finito de puntos y aristas, que se pueden contar
por separado; es decir, sus variables discretas o digitales.
Por todo lo anterior, deduzco que es de vital importancia el
estudio y conocimiento de las matemáticas discretas, por lo que
sinceramente espero que los temas contenidos en el presente
210
CONCLUSIONES
libro coadyuven y orienten a los estudiantes hacia objetivos

concretos y que sus esfuerzos se vean recompensados con las
habilidades adquiridas en lo referente al pensamiento lógico-
algorítmico y mejora de su capacidad de abstracción y así
facilitar el dominio de futuras aplicaciones, dentro del campo
profesional en el que será requerido.
211
BIBLIOGRAFÍA
BIBLIOGRAFÍA
Jiménez José A. “MATEMÁTICAS para la COMPUTACIÓN“

primera edición. México. Ed. Alfaomega.
Johnsonbaugh Richard. “MATEMÁTICAS DISCRETAS” sexta

edición. México. ed. Pearson Prentice Hall.
Seymor Lipschutz and Marc Lipson. “Matemáticas discretas”

tercera edición. México. Editorial Mc Graw Hill.
Bernard Kolman and Robert Busby. “Estructuras de matemáticas

discretas para la computación.” Segunda edición. Ed.
Prentice Hall Hispanoamericana, S.A.
Arrollo Cabrera C. Algebra Booleana. www.monografías.com
Brookshear J. Glenn “Teoría de la computación” Ed. Addison –

Wesley Iberoamericana.
Herbert Taub. Circuitos digitales y microprocesadores.

Traducción de la primera edición. Ed. Mc Graw Hill.
Kenneth Rosen “Matemática discreta y sus aplicaciones”. Ed.

Mc. Graw Hill.
Ralph P. Grimaldi “Matemáticas discreta y combinatorial”. Ed.

Pearson Educación.
Matemática discreta UCLM https://previa.uclm.es
212
BIBLIOGRAFÍA
Matemática discreta y lógica. https://librosuned.com “Una

perspectiva desde la ciencia de la computación”. Ed.
Prentice Hall.
Teoría de grafos. Wikipedia, enciclopedia libre.

https://es.m.wikipedia.org
Tremblay Jean-Paul/Manohar R. “Matemáticas discretas con

aplicación a las ciencias de la computación.” México. Ed.
CECSA.
UNAM, Matemática IV “Matemáticas discretas”

http://fcaenlinea.unam.mx/apuntes/interiores/docs/98/6/m
ate_4.pdfn
213

Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

Matemáticas Discretas

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

INSTITUTO TECNOLÓGICO DE OAXACA

BENITO GARCÍA ARÉCHIGA

INSTITUTO TECNOLÓGICO DE OAXACA

BENITO GARCÍA ARÉCHIGA

Su comprensión, trascendencia y factibilidad de aplicaciones

Con respecto al presente libro titulado “MATEMÁTICAS

El libro de texto es una herramienta, que permite a los

específicamente contenidos, buscando en todo momento la

Así mismo, pretende que su contenido sea de apoyo inmediato

En lo que respecta a la unidad I se enfoca en la definición de los

La unidad II nos introduce a los conceptos de la teoría básica

La unidad III se enfoca en la comprensión de las bases de la

La unidad IV aborda de manera frontal el álgebra Booleana,

En la unidad V, viro hacia la teoría de grafos con la definición,

Y finalmente en la unidad VI, hago lo propio en lo relacionado a

De todo lo mencionado, considero que es de gran utilidad e

Al Tecnológico Nacional de México

Al Instituto Tecnológico de Oaxaca

Al Departamento y a la Academia de Ciencias

A mis compañeros Maestros que intervinieron

A mis hijos Rafael, Germán

UNIDAD I. SISTEMAS NUMÉRICOS

UNIDAD II. CONJUNTOS Y RELACIONES

UNIDAD III. LÓGICA MATEMÁTICA

UNIDAD IV. ÁLGEBRA BOOLEANA

UNIDAD VI. ÁRBOLES Y REDES

 CAPACIDAD DE ABSTRACCIÓN Y ANÁLISIS.

 CAPACIDAD DE INTERPRETAR Y PROYECTAR LAS

Se le llama sistema de numeración a un conjunto de símbolos y

Sin duda alguna, el sistema numérico universalmente más

Sobra decir, que el sistema decimal se derivó del sistema indo -

Ya con el avance del desarrollo tecnológico, se fueron

Se verá poco más adelante, como estos sistemas numéricos

Se omitirá lo relativo al sistema decimal, obviando su dominio,

La posición de un 1 o de un 0 en un número binario indica su

Así, por ejemplo, un número de cuatro bits 0010 y 1011

Para el segundo caso 1011, la cantidad equivale a decir

Este sistema es de suma importancia para la computación,

ejemplo 0.11 binario, aplica 1x(1/2)+1 x (1/4), que equivale a

Por lo que respecta al sistema numérico octal, este sistema solo

El sistema es considerado de gran utilidad en el mundo de las

Por último, en cuanto al sistema hexadecimal, que es un sistema

Este sistema normalmente se usa con la finalidad de ofrecer un

1.1 Sistemas numéricos (binario, octal, decimal,

Binario: Es un sistema de numeración en el que los números se

Octal: El sistema numérico en base 8 se llama octal y utiliza los

Decimal: Es un sistema de numeración posicional en el que

Hexadecimal: Es el sistema de numeración posicional que tiene

Está compuesto por los dígitos 0 al 9 como en el sistema decimal

1.2 Conversión entre sistemas numéricos

Decimal-Binario: Consiste en dividir sucesivamente el número

Para convertir al binario el número decimal 77 se hace una serie

Luego se toman los residuos en orden inverso, es decir de arriba

El decimal 77, entonces es igual al binario 1001101.

Decimal-Octal: La conversión de un número decimal a octal se

Para escribir en octal el número decimal 122 se hacen las

Y tomando los residuos obtenidos en orden inverso se calcula la

Por lo tanto, el decimal 122 es igual al octal 172.

Decimal-Hexadecimal: Utilizando divisiones sucesivas, la

Para convertir a hexadecimal del número decimal 1735 se

12^6 + 02^5 + 12^4 + 02^3 + 02^2 + 12^1 + 1*2^0 = 83

28^2 + 38^1 + 7*8^0 = 128 + 24 + 7 = 159

216^2+C16^1+A*16^0 = 512 + 192 + 10 = 714