Separata de Matematica Discreta

MATEMATICA DISCRETA
(Material de apoyo de clase)
Facultad de Ingeniería Industrial y de Sistemas

Universidad Nacional de Ingeniería
Mg.Osmar A. Bermeo Carrasco
Lima-Perú
2019
Osmar A. Bermeo Carrasco Página 1

“La genialidad del ser humano no solamente
es buscar el benefició para algunas personas
sino para toda la humanidad”

Índice general

Capítulo 1
1.1.-Sistema de Numeración
Conjunto ordenado de símbolos llamados dígitos, con reglas para realizar operaciones
aritméticas. La Base b del sistema numérico indica la cantidad total de dígitos (símbolos)
permitidos en dicho sistema.
Los sistemas numéricos que más se utilizan en el diseño de sistemas digitales y la

programación de computadoras son los siguientes.
Decimal (b=10)
Binario (b=2)
Octal (b=8)
Hexagesimal (b=16)
Cualquier número en un sistema dado puede tener una parte entera y una parte fraccionaria.
1.1.1.-Notación posicional
Los dígitos de un número N tienen asignado un peso o valor según su lugar que ocupa,
todo número N representa en el sistema por una sucesión de dígitos en base b.
Es decir 𝑁 = (𝑎𝑛−1 𝑎𝑛−2 𝑎𝑛−3 … . . 𝑎2 𝑎1 𝑎0. 𝑎−1 𝑎−2 … … 𝑎−𝑚 )𝑏
Ejemplos
Binario: 𝑁 = (1101.101)2 Pesos: 23 22 21 20 2−1 2−2 2−3 son potencias de 2
Octal: 𝑁 = (436.43)8 Pesos: 82 81 80 8−1 8−2 son potencias de 8
1.1.2.-Notación Polinomial
Cualquier número N con base b se puede escribir como un polinomio de la forma.
𝑁 = (𝑎𝑛−1 𝑏 𝑛−1 + ⋯ … + 𝑎2 𝑏 2 + 𝑎1 𝑏1 + 𝑎0 𝑏0 + 𝑎−1 𝑏−1 𝑎−2 𝑏−2 … … 𝑎−𝑚 𝑏−𝑚 ) = ∑𝑛−1

𝑖=−𝑚 𝑎𝑖 𝑏
𝑖
Dónde:
n: Numero de dígitos enteros m: Numero de dígitos fraccionarios

b: Base del sistema numérico 𝑎−𝑚 : Dígito menor significado
𝑎𝑛−1 : Dígito más significado (mayor peso)

Ejemplos
Binario: N= (1001.11)2 = 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20 + 1 * 2-1 + 1 * 2-2
Decimal: N= (123.45)10 = 1 * 102 + 2 * 101 + 3 * l00 + 4 * 10-1 + 5 * 10-2
Hexadecimal: N= (3A.2F)16 = 3 * 161 + A * 160 + 2 * 16-1 + F * 16-2
Donde: A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15
1.2.-Sistema binario
Es un sistema de numeración posicional su base es 2 y sus elementos son 0 y 1, se

denomina bits (binary digit). Es el sistema de numeración más usado para realizar
operaciones aritméticas en un computador
1.2.1.- El bit
Es el acrónimo de Binary Digit (dígito binario). Un bit es la unidad mínima de información empleada
en informática. Representa un uno o un cero (abierto o cerrado, blanco o negro, cualquier sistema de
codificación sirve). A través de secuencias de bits, se puede codificar cualquier valor discreto como,
por ejemplo, números, palabras e imágenes.
1.2.2.-El byte
Se describe como la unidad básica de almacenamiento de información, siendo equivalente a ocho

bits.
Se suelen escribir los números binarios como una secuencia de grupos de cuatro bits, también
conocidos como NIBBLES. Según el número de estas agrupaciones los números binarios se clasifican
como:
Unidad: Núm. bits Ejemplo:

Bit 1 1
Nibble 4 0101
Byte (Octeto) 8 0000 0101
Palabra 16 0000 0000 0000 0101
Doble Palabra 32 0000 0000 0000 0000 0000 0000 0000 0101
Los computadores personales con el sistema operativo MS DOS utilizaban palabras de 16 BITS. Los
sistemas operativos actuales sobre los que corre AutoCAD 2000 utilizan Palabras de 32 BITS.

Los prefijos kilo, mega, giga, etc. se consideran potencias de 1024 en lugar de potencias de 1000.
Esto es así porque 1024 es la potencia de 2 (210) más cercana a 1000.
Nombre Abrev. Factor
kilo K 210 = 1024
mega M 220 = 1 048 576
giga G 230 = 1 073 741 824 1 byte: 8 bits
1 Kilobyte: 1024 bytes

tera T 240 = 1 099 511 627 776
1 Megabyte: 1024 Kilobytes (Kb)
peta P 250 = 1 125 899 906 842 624 1 Gigabyte: 1024 Megabytes (Mb)
1 Terabyte: 1024 Gigabytes (Gb)
exa E 260 = 1 152 921 504 606 846 976
zetta Z 270 = 1 180 591 620 717 411 303 424
yotta Y 280 = 1 208 925 819 614 629 174 706 176
1.3.-El sistema octal
El sistema numérico en base 8 se llama octal y utiliza los dígitos 0 a 7.
Los números octales pueden construirse a partir de números binarios agrupando cada tres dígitos
consecutivos de estos últimos (de derecha a izquierda) y obteniendo su valor decimal.
Por ejemplo, el número binario para 74 (en decimal) es 1001010 (en binario), lo agruparíamos como
1 001 010. De modo que el número decimal 74 en octal es 112.
En informática, a veces se utiliza la numeración octal en vez de la hexadecimal. Tiene la ventaja de

que no requiere utilizar otros símbolos diferentes de los dígitos.
Es posible que la numeración octal se usara en el pasado en lugar de la decimal, por ejemplo, para
contar los espacios interdigitales o los dedos distintos de los pulgares.
Un número octal puede ser:
45.328 ó 45.32octal
Representación Octal
Para obtener la representación decimal de un número Octal se puede utilizar

1
N10   ai 8i  4 * 81  5 * 80  3 * 8 1  2 * 8 2  32  5  3 / 8  2 / 64  37.40625
i  2
1.4.-Conversión entre los sistemas binario y octal
Como se ha planteado, son fácilmente transformables, basta reagrupar 3 cifras binarias de derecha a
izquierda y convertirlas a su equivalente octal, como se puede apreciar a continuación:
011011001112 = 15478
Donde, de derecha a izquierda:
1112 = 78, 1002 = 48, 1012 = 58 y 0012 = 18.
Nótese como en el dígito de la izquierda pueden faltar bits, sustituyéndolos por cero(s).
Para realizar el proceso inverso, transformar de octal a binario, basta sustituir cada cifra en octal por
las tres equivalentes en binario, como se muestra a continuación:
34208 = 0111000100002
Donde, de derecha a izquierda:
08 = 0002, 28 = 0102, 48 = 1002 y 38 = 0112
La base de operaciones de una microcomputadora está organizada en 8, 16 ó 32 cifras binarias, las

cuales constituyen 3, 6 y 11 cifras octales respectivamente.
DECIMAL BINARIO OCTAL

0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 10
9 1001 11
10 1010 12
11 1011 13
12 1100 14
13 1101 15
14 1110 16
15 1111 17

1.5.-El sistema hexadecimal
El sistema hexadecimal es un sistema de numeración vinculado a la informática, ya que las

computadoras interpretan los lenguajes de programación en bytes, que están compuestos de ocho
dígitos.
Como veremos en la unidad de Hardware, el procesador 80386 hace ya más de una década
manipulaba sin problemas números de 32 bits. Un humano necesita manejarlo de otra manera y por
eso se inventó el sistema hexadecimal, con 16 símbolos, ya que si uno agrupa cuatro bits obtiene 16
combinaciones posibles (24 = 16).
Esto tiene una razón. Nuestro sistema decimal no se corresponde en la cantidad de dígitos con el
binario en cambio, el hexadecimal si, porque cada cuatro bits representan un dígito hexadecimal
exacto.
En un sistema hexadecimal, necesitamos 16 símbolos. Ya que somos muy buenos manejando

números decimales, adoptamos esos diez símbolos (0, 1, 2, 3, 4, 5, 6, 7, 8 y 9) para empezar, pero
hay que agregar otros seis: A, B, C, D, E y F
Cada trozo de información recibe un nombre propio según la cantidad de bits que posea:
Decimal Binario Octal Hexadecimal

0 0000 0 0
1 0001 1 1
2 0010 2 2
3 0011 3 3
4 0100 4 4
5 0101 5 5
6 0110 6 6
7 0111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F

Ejemplo de número en hexadecimal:
1C6E.316 = 1C6E.3hexadecimal
Representación hexadecimal.
Para su conversión al sistema decimal, aplicando
3
N10   ai 16 i  1 *16 3  12 *16 2  6 *161  14 *16 0  3 *16 1  32  5  3 / 8  2 / 64  37.40625
i  1
= 1*4096+ 12*256+ 6*16+ 14*1+ 3*1/16
= 7278.1875
Nótese como hay que hacer las sustituciones basándose en las igualdades:
A=10, B=11, C=12, D=13, E=14 y F=15.
1.6.-Conversión entre los sistemas binario y hexadecimal.
La equivalencia entre las cifras hexadecimales y binarias se muestra en la tabla anterior. En

este caso se requieren de cuatro cifras binarias por cada cifra hexadecimal (cuatro cifras
binarias generan 24=16 posibles combinaciones, que corresponden con 16 cifras en el sistema
hexadecimal).
El método de conversión de binario a hexadecimal es semejante al de binario a octal, sólo que ahora
se agrupan de 4 en 4 bits de derecha a izquierda, así:
01011011010.10112 = 2DA.B16
Donde (de derecha a izquierda):
10112 = B16, 10102 = A16, 11012 = D16 y 0102 = 216
En la conversión de hexadecimal a binario se sustituye cada cifra del sistema hexadecimal por las
correspondientes cuatro cifras que la identifican en el sistema binario como puede apreciarse en el
siguiente ejemplo:
23E.F16 = 001000111110.11112
Donde (de derecha a izquierda):
216 = 00102, 316 = 00112, E16 = 11102 y F16 = 11112

Existen otros sistemas según su base: Trinario (0 al 2), Cuaternario (0 al 3), Duodecimal (0 al B). En
todos ellos, los sistemas numéricos de base menor que 10 utilizan los símbolos de las primeras cifras
del sistema decimal, los mayores o iguales a 10 las letras del alfabeto latino (A, B, C, etc.).
1.7.-Conversión del sistema numérico decimal al resto de los sistemas de numeración.
Para transformar del sistema numérico decimal a cualquier otro sistema hay que trabajar por
separado con la parte entera y la parte fraccionaria.
Parte entera
Para transformar la parte entera del número decimal se divide por la base del sistema al que
se quiere transformar tantas veces como sea necesario hasta que el último cociente sea cero.
El primer resto obtenido (r0) constituye la cifra menos significativa (la de menor peso) del
número que se busca, mientras que el último resto (rn-1, donde n es el número de divisiones
a ejecutar o el número de cifras del sistema destino) constituye la cifra más significativa (la
de mayor peso) del número en cuestión.
El número resultante sería:
rn-1 rn-2 rn-3 .... r0
Ejemplos:
1. Convertir a binario el número 250.
Como se realizan sucesivas divisiones entre la base del sistema destino, se dividirá entre 2
(base del sistema binario):
250 / 2 = 125 resto 0 r0 (Cifra menos significativa del número binario).
125 / 2 = 62 resto 1 r1
62 / 2 = 31 resto 0 r2
31 / 2 = 15 resto 1 r3
15 / 2 = 7 resto 1 r4
7 / 2 = 3 resto 1 r5
3 / 2 = 1 resto 1 r6
1 / 2 = 0 resto 1 r7 (Cifra más significativa del número binario).
El número resultante sería:
r7 r6 r5 r4 r3 r2 r1 r0 = 111110102

Por lo tanto:
25010 = 111110102
Existe un método alternativo de conversión decimal a binario denominado "potencias de

dos", este consiste en "examinar" en primer lugar el número decimal para descubrir la mayor
potencia de dos que se le puede restar, continuando el proceso hasta reducir el número
decimal original a cero.
En el ejemplo al número 250 la primera potencia de dos que se le puede restar es 128( la
próxima de mayor orden es 256 que supera el número) por lo que la cifra del número binario
que posea ese peso debe ser seteada, 250-128=122 y a 122 la próxima potencia de dos que
se le puede restar es 64, la sustracción puede ser realizada por lo que la cifra binaria cuyo
peso sea 64 debe ser seteada; así se continúa hasta que el resulta sería:
Potencias de dos: 128 64 32 16 8 4 2 1
Número binario: 1 1 1 1 1 0 1 0
Lo que corresponde con la solución del ejemplo.
2. Convertir a octal el número 160.
Se realiza, para la conversión exigida, sucesivas divisiones entre la base del sistema octal (8).
160 / 8 = 20 resto 0 r0 (Cifra octal menos significativa)
20 / 8 = 2 resto 4 r1
2/8=0 resto 2 r2 (Cifra octal más significativa)
La solución sería:
r2 r1 r0 = 2408
Por tanto:
16010 = 2408
3. Repita ejemplo 1 pero a través del sistema octal.
Una forma más sencilla de convertir de decimal a binario es a través del sistema octal, que al
tener mayor base, se necesitan menos divisiones y una vez que tenga el valor en octal,
transferirlo a binario.
En el caso del ejemplo 1:
Primero se transferirá 250 a octal:

250 / 8 = 31 resto 2 r0
31 / 8 = 3 resto 7 r1
3 / 8 = 0 resto 3 r2
Tenemos pues:
25010 = 3728
Basta entonces transferir el valor octal a binario de manera directa y como ya conocemos,
utilizando la tabla:
3728 = 0111110102
Como puede comprobarse, el resultado es idéntico al del ejemplo 1
4. Convertir a hexadecimal el número 155.
Como la base del sistema hexadecimal es 16, se realizan sucesivas divisiones entre esta base.
155 / 16 = 9 resto 11 r0 (Cifra menos significativa)
9 / 16 = 0 resto 9 r1 (Cifra más significativa)
Como el número 11 constituye la cifra B en hexadecimal, el resultado sería:
r1 r0 = 9B16
Por lo tanto:
15510 = 9B16
Un método alternativo de transformar de decimal a hexadecimal lo constituye el transformar

el número decimal a octal, este a binario y por último a hexadecimal.
En el caso del ejemplo 4, llevaremos el valor a octal:
155 / 8 = 19 resto 3
19 / 8 = 2 resto 3
2/8 =0 resto 2
El valor en octal sería:
15510 = 2338
El valor octal a binario:
2338 = 0100110112
El valor binario a hexadecimal:
0100110112 = 9B16
Por lo que 15510 = 9B16, lo que puede ser comprobado según el resultado del ejemplo 4.
Un mismo número decimal convertido a los distintos sistemas numéricos estudiados ilustra
lo expresado anteriormente, de que mientras mayor es la base, menor número de cifras para
representar un número. El valor 15510 posee 8 cifras en el sistema binario (base 2), 3 cifras
en el sistema octal (base 8), 3 cifras en el sistema decimal (base 10) y 2 cifras en el sistema
hexadecimal (base 16).
Parte fraccionaria
Para transformar la parte fraccionaria de un número decimal a otro sistema, en lugar de

dividirla, hay que multiplicarla por la base. Cada vez que se multiplique la fracción decimal
por la base se obtiene una parte entera. La primera la denominamos p1 y se extrae del
resultado para que solo quede la parte fraccionaria. Esta parte fraccionaria que queda se
multiplica nuevamente por la base y se extrae la parte entera, que denominamos p2 y así
sucesivamente hasta que sea necesario o se indique.
El número resultante en la nueva base será:
0.p1 p2 p3 p4 ... pm
Donde m es el número de cifras de la parte fraccionaria.
Ejemplos:
1. Transforme en octal el número 0.32.
0.32*8=2.56 (p1=2)
0.56*8=4.48 (p2=4)
0.48*8=3.84 (p3=3)
0.84*8=6.72 (p4=6)
0.72*8=5.76 (p5=5)
. . .
. . .
El método ejecutado ha sido el siguiente:

En primer lugar el número a convertir ha sido multiplicado por la base del sistema que se
desea (8), al resultado (2.56) se le ha extraído la parte entera (2) y este constituirá la cifra
más significativa de la parte fraccionaria, al extraérsele a 2.56 la parte entera queda 0.56, al
que se le multiplica la base; al resultado (4.48) se le extrae la parte entera (4) y constituirá la
próxima cifra de la fracción del número, este proceso continúa sucesivamente.
Se puede plantear entonces que:
0.4210 = 0.24365...8
Note como el resultado no ha sido exacto, a nosotros corresponde seleccionar el número de

cifras fraccionarias para una precisión deseada.
2. Convertir el número 0.12510 a binario.
Como la base del sistema binario es 2, ahora las multiplicaciones sucesivas serán por este
término:
0.125*2=0.250 (p1=0) (Cifra más significativa de la parte fraccionaria)
0.250*2=0.500 (p2=0)
0.500*2=1.000 (p3=1)
0.000*2=0.000 (p4=0)
Y las cifras sucesivas seguirán siendo cero. Por tanto:
0.12510 = 0.0012
Un método más rápido puede ser el transformar la fracción decimal a octal y posteriormente
a binario. En el ejemplo:
0.125*8=1.000 (p1=1)
0.000*8=0.000 (p2=0) Y las cifras sucesivas seguirán siendo cero.
Se puede entonces afirmar:
0.12510 = 0.18
Y de octal a binario:
0.18=0.0012
Como habíamos calculado.
Para realizar la conversión de números fraccionarios decimales a números fraccionarios

hexadecimales, es conveniente utilizar el octal como intermediario.

1.8.-Operaciones en el sistema binario
a) Suma binaria
Las tablas 1.1a y b muestran las tablas de suma y multiplicación, respectivamente, para el
sistema numérico binario. Las tablas son muy pequeñas ya que sólo hay dos dígitos, o bits,
en el sistema. En consecuencia, la aritmética binaria es muy sencilla. Observe que la suma
1 + 1 produce un bit se suma de 0 y un bit de acarreo de 1. El acarreo debe sumarse a la
siguiente columna de bits para realizar la suma en el patrón normal, de derecha a izquierda.
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 10 1 0 1
Tabla 1.1 a Tabla 1.1 b
1.- 1010101+ 2.- 101010111+

10111 100111011
1 101100 1010010010
b) Resta Binaria
La resta se puede visualizar como el inverso de la suma. Las reglas para la resta binaria se
derivan directamente de la tabla de suma binaria y son:
1-0=1
1-1=0
0-0=0
0 - 1 = 1 tomando prestado 1, o 10 - 1 = 1
La última regla muestra que si se resta un bit 1 de un bit 0, hay que tomar prestado un 1 de
la siguiente columna más significativa. Los préstamos se propagan hacia la izquierda de
columna en columna, como se ilustra a continuación.
Ejemplos
1.-Restar los dos números binarios (1001101)2 y (10111)2
10
10 - 1 = 1 0 1 10 0 0 10
100 - 1 = 11 1 0 0 1 1 0 1
1000 - 1 = 111 1 0 1 1 1 -
0 1 1 0 1 1 0

2.- 10011012 -
101112
____________
1101110
c) Multiplicación Binaria
La multiplicación binaria se realiza en forma similar a la multiplicación decimal, excepto que las
operaciones de multiplicación binaria son mucho más sencilla. No obstante, se debe tener mucho
cuidado al sumar los productos parciales, como se ilustra en el siguiente ejemplo.
Ejemplo
Multiplicar (10111)2 por (1010)2
Observe que hay un producto parcial por cada bit del multiplicador. Este procedimiento puede
realizarse con mayor eficiencia si sólo recorremos una columna a la izquierda, en vez de anotar un
producto parcial con ceros para un bit 0 del multiplicador. Este ejemplo nos sirve para ver lo sencillo
de este procedimiento.
d) División Binaria
La división binaria se realiza utilizando el mismo procedimiento de prueba y error de la

división decimal. Sin embargo, la división binaria es más sencilla pues sólo hay que intentar
con dos valores. Se restan del dividendo copias de los términos del divisor, de lo cual se
obtienen residuos intermedios positivos. El siguiente ejemplo ilustra la división binaria.

Ejemplo 1.4
Dividir (1110111)2 entre (1001)2
1.9.-Representación de Datos
Los datos pueden ser numéricos y alfanuméricos
Sin signo
Numéricos: Enteros: Con signo
BCD(Decimal codificado en binario)
Punto Fijo
Reales: Punto flotante y Normalizado
Alfanuméricos: *ASCII (7 bits: Representa 128 símbolos)

*EBCDIC(8bits: Representa 256 símbolos)
1.9.1.- Números Enteros:
z- z+
R
0
Dado que ningún ordenador puede almacenar los enteros se han desarrollado dos categorías
de representación que se detallara a continuación, que en efecto para hacerlo requerimos
un número infinito de bits, lo cual significa tener un ordenador con capacidad infinita.

Para usar la memoria de un ordenador de manera más eficiente se han desarrollado dos
categorías de representación de los enteros, donde lo representaremos en el siguiente
esquema.
NUMEROS ENTEROS
CON SIGNO
SIN SIGNO
SIGNO-MAGNITUD COMPLEMENTO A UNO COMPLEMENTO A DOS
a) Números sin signo
Los números sin signo se representan en binario, si se dispone de “n” bits se puede
codificar 2n números (combinaciones).
Ejemplo.
Si n=4 se pueden codificar de 0-15
N Binario
0 → 0000
1 → 0001
2 → 0010
3 → 0100
. . .
. . .
. . .
15 → 1111
En general el rango es 0 ≤ 𝑁 ≤ 2𝑛 − 1

Complemento a uno y complemento a dos de números binarios
i) Complemento a uno (ca1)
Consiste en complementar cada bit, es decir se cambia 1 por 0, y 0 por 1

Ejemplo.
Sea el número binario 100111012 → 01100010 (ca1)
ii) Complemento a dos (ca2)
Consiste en aplicarle el complemento a uno al número binario y luego sumarle uno

Ejemplo.
Sea el número binario 100111012 → 01100010 (ca1)+1→ 01100011 (ca2)
b) Números con signo

Si se dispone de “n” bits, se designa un bit para indicar el signo, este siempre ocupa la
posición más significativa, el resto de (n-1) bits se emplean para indicar la magnitud.
Existen varios formatos para codificar números enteros con signo, para números positivos
el bit más significativo es 0, para números negativos el bit más significativo es 1
Bit de signo
0: Positivo
1:Negativo
Existen los siguientes formatos para números con signo
c) Formato signo magnitud

Si se dispone de “n” bits, el primer bit de la izquierda representa el signo, donde cero
representa positivo, y uno representa negativo. El valor absoluto del número se representa
en base 2, en los (n-1) restantes.
Ejemplo 1
-5 se representa por: 1101
5 se representa por: 0101
Ejemplo 2
Interpretar 101110112 en el sistema decimal si el número se almacena como un entero de
signo y magnitud.
1 0111011 = -59
S M N

Ejemplo 3
Representar los números -27 y +27 en signo-magnitud usando 8 bits.
-27 1 0011011
+27 0 0011011
Rango −(2𝑛−1 − 1) ≤ 𝑁 ≤ +(2𝑛−1 − 1), donde n es el número de bits a utilizar.
d) Complemento a uno
Si se dispone de “n” bits y sea N el número.

Si 𝑁 ≥ 0, se le representa igual que el formato signo magnitud.
Si 𝑁 < 0, se le representa como el complemento a uno, es decir se cambia uno por cero y
cero por uno, de la representación del valor absoluto de N.
Ejemplo
Exprese +27 y -27 como complemento a uno con n=8 bits
+27 se representa por: 00011011

-27 se representa por: |−27| → 00011011 → 11100100
Rango: -(2𝑛−1 − 1) ≤ 𝑁 ≤ +(2𝑛−1 − 1)
e) Complemento a dos
Si se dispone de “n” bits y sea N el número.

Si 𝑁 ≥ 0, se le representa igual que el formato signo magnitud.
Si 𝑁 < 0, se le representa como el complemento a dos, es decir se cambia uno por cero y
cero por uno y luego se le suma uno, de la representación del valor absoluto de N.
Ejemplo 1
Exprese +27 y -27 como complemento a dos con n=8 bits

-27 se representa por: |−27| → 00011011 → 11100100 + 1 = 11100101(ca2)
Ejemplo 2
Exprese +100 y -100 como complemento a dos con n=8 bits

-100 se representa por: |−100| → 01100100 → 10011011(𝑐𝑎1) + 1 = 10011100 (ca2)

f) Formato en exceso
Un numero N en exceso se expresa como 𝑁 + 2𝑛−1 , siendo “n” el número de bits
Ejemplo
Expresar +5 y -4 en formato exceso utilizando 4 bits
 +5 + 24−1 = 5 + 8 = 13 → 1101
 −4 + 24−1 = −4 + 8 = 4 → 0100
 −8 + 24−1 = −8 + 8 = 0 → 0000
Rango: −(2𝑛−1 − 1) ≤ 𝑁 ≤ +(2𝑛−1 − 1)
Representación de enteros con n=4.
Entero sin Signo Complemento Complementó Formato en

Representación signo Magnitud a uno con a dos con exceso
signo signo
0000 0 +0 +0 +0 -8
0001 1 +1 +1 +1 -7
0010 2 +2 +2 +2 -6
0011 3 +3 +3 +3 -5
0100 4 +4 +4 +4 -4
0101 5 +5 +5 +5 -3
0110 6 +6 +6 +6 -2
0111 7 +7 +7 +7 -1
1000 8 -0 -7 -8 0
1001 9 -1 -6 -7 1
1010 10 -2 -5 -6 2
1011 11 -3 -4 -5 3
1100 12 -4 -3 -4 4
1101 13 -5 -2 -3 5
1110 14 -6 -1 -2 6
1111 15 -7 -0 -1 7

1.9.2.-Operaciones aritméticas en complemento a dos
Suma y resta
La operación de suma de números representados en complemento a dos se realiza usando

las reglas de suma de binario natural, independientemente del signo de los operandos y
descartando el acarreo final. Es decir, da igual que se sumen dos positivos o dos negativos,
o un positivo y un negativo, simplemente se suman. Y además, el resultado de la suma se
encuentra representado en complemento a dos. Esta es la principal ventaja de esta
representación y la razón de que el 100% de los sistemas informáticos lo utilicen para la
representación de números enteros. La operación de resta se realiza mediante una suma, a la
que se le cambia el signo al sustraendo. Es decir, A - B = A + (-B). A continuación se
muestra como ejemplo una suma y una resta de números representados en binario
complemento a dos con 4 bits (y sus equivalentes en decimal):
Ejemplo
Desbordamiento en la suma y la resta
Al realizar una suma de números enteros es posible que el resultado exceda el rango de
representación. En este caso se dice que no hay resultado o que el resultado no es
representable.
Con operandos representados en complemento a dos se produce desbordamiento al

realizar una suma si el último y el penúltimo acarreo son distintos. A continuación tienes
unos ejemplos donde se produce desbordamiento. En el primer ejemplo los acarreos
aparecen en letra cursiva:
Ejemplo 1
Ejemplo 2
Utilizando un formato de 4 bits sumar
+3 → 0011 +6 → 0110
+4 → 0100 +5 → 0101
----- ------- ----- -------
+7 0111 +11 1011
Desbordamiento, la suma de dos números positivos (+6 y +5) da como resultado un

numero negativo. El resultado requiere un bit adicional para indicar el signo correcto.
Obs
Al sumar:
– Cuando los operandos tienen el mismo signo y se obtiene un resultado con signo
contrario.
Al restar:
– Cuando se resta un número negativo de un número positivo y el resultado es negativo

(A-(-B))=A+B debe ser positivo.
– Cuando se resta un número positivo a uno negativo y el resultado da positivo.
(-A)-B= -(A+B) debe ser negativo.
Extensión de signo
En algunos casos es necesario operar datos con diferentes tamaños. Para aumentar el
número de bits con que se representa un dato se realiza la operación llamada extensión de
signo. En el caso de la representación en complemento a dos, la extensión de signo se
realiza replicando el bit de signo.

Ejemplo: dados los números enteros 00102 y 11102 representados en complemento a dos
con 4 bits, extiende el signo para representarlos con 8 bits.
1.9.3. Códigos binarios
1.9.3.1 Codigo BCD (binary code decimal)
En un ambiente de sistemas digitales se denomina codificación a la asignación de un

significado a una configuración de bits.
Al modelar problemas es usual encontrar variables que pueden tomar múltiples valores, se
denomina codificación al proceso de convertir esas variables en señales binarias. La
elección adecuada del código puede conducir a redes lógicas más simples.
Consideremos, por ejemplo, el estado de un semáforo: éste puede tomar uno de tres valores:
verde, amarillo o rojo. Una posible codificación es considerar cada color como una señal
binaria; así si la variable color toma valor rojo, estará en nivel alto la señal rojo y el resto de
las señales (la verde y amarilla) serán ceros.
Es un código que se utiliza 4 bits para codificar directamente los diez primeros números
decimales, se emplea para ingresar datos numéricos enteros a un sistema digital y también
para representar resultados directamente en decimal.
Ejemplo. Sumar los números 2 y 6 en BCD
0010+
0110
-----------
1000
1.9.3.2 Tipos de códigos BCD
i) BCD natural
Es un código ponderado con pesos: 8 4 2 1
ii) BCD exceso tres (sin pesos)
BCD natural +3=BCD exceso tres
iii) BCD Aiken

Es un código ponderado con pesos. 2 4 2 1
Código
Decimal BCD Natural BCD exceso tres BCD Aiken (2421)
0 0000 0011 0000

1 0001 0100 0001
2 0010 0101 0010
3 0011 0110 0011
4 0100 0111 0100
5 0101 1000 1011
6 0110 1001 1100
7 0111 1010 1101
8 1000 1011 1110
9 1001 1100 1111
1.9.3.3 Código BCD desempaquetado
Este sistema está ligado al código BCD natural, como se podrá apreciar a continuación
La codificación BCD desempaquetada utiliza un byte (8bits) para almacenar un digito

decimal de la siguiente forma.
Cuarteto de bits de zona.-Los bits son todos uno, excepto en el último digito del número a
representar donde toma la representación 1100 si el número es positivo y 1101 si el número
es negativo.
Cuarteto de bits de digito.- Estos cuatro bits representa el digito decimal codificado en
BCD
1 1 1 signo
Cuarteto de bits de zona Cuarteto de bits de digito
Ejemplo
Codificar los siguientes números 1992 y -1992 en BCD desempaquetado
i) +1992
1111/ 0001 1111/1001 1111/1001 1100/0010
ii) -1992

1111/ 0001 1111/1001 1111/1001 1101/0010
1.9.3.4 Código BCD empaquetado
Dado que el sistema de codificación BCD desempaquetado no optimiza la capacidad de

memoria, se diseña el sistema de codificación BCB empaquetado. Esta codificación elimina
los bits de zona, excepto en la última cifra, en este caso cada cuarteto lleva una cifra en
BCD salvo el ultimo que es el signo.
Ejemplo
Codificar el número +1992 en BCD empaquetado
0 1
9 9
2 +
0000/ 0001 1111/1001 1111/1001 0010/1100
El formato BCD (Binary Coded Digit) consiste en utilizar 4 bits para representar los números del 0
al 9 (010 = 00002 y 910 = 10012). Dado que los microcontroladores trabajan en bloques de 8 bits (1
byte), hay dos representaciones: BCD empaquetado y BCD desempaquetado. La idea del BCD
empaquetado es utilizar 1 byte para representar 2 dígitos BCD, mientras que en BCD desempaquetado
se utiliza 1 byte para cada digito BCD.
Ejemplo 1: 4710 = 0100 0111 BCD Empaquetado = 0000 0100 0000 0111 BCD Desempaquetado
Ejemplo 2: Representar los siguientes números en base 10 en BCD empaquetado y desempaquetado:

a) 236
b) 27984
1.9.4. Códigos Alfanuméricos
Código ASCII (del inglés de American Standard Code for Information Interchange - Código
Estándar Estadounidense para el Intercambio de Información), pronunciado generalmente
[áski], es un código de caracteres basado en el alfabeto latino, tal como se usa en inglés
moderno y en otras lenguas occidentales. Fue creado en 1963 por el Comité Estadounidense
de Estándares (ASA, conocido desde 1969 como el Instituto Estadounidense de Estándares
Nacionales o ANSI) como una evolución de los conjuntos de códigos utilizados entonces en
telegrafía. En 1967 se incluyeron las minúsculas y se redefinieron algunos códigos de control
para formar el código conocido como US - ASCII.

El código ASCII utiliza 7 bits para representar los caracteres, aunque inicialmente empleaba
un bit adicional (bit de paridad) que se usaba para detectar errores en la transmisión. A
menudo se llama incorrectamente ASCII a otros códigos de caracteres de 8 bits, como el
estándar ISO-8859-1 que es una extensión que utiliza 8 bits para proporcionar caracteres
adicionales usados en idiomas distintos al inglés, como el español.
ASCII fue publicado como estándar por primera vez en 1967 y fue actualizado por última
vez en 1986. En la actualidad define códigos para 33 caracteres no imprimibles, de los cuales
la mayoría son caracteres de control obsoletos que tienen efecto sobre cómo se procesa el
texto, más otros 95 caracteres imprimibles que les siguen en la numeración (empezando por
el carácter espacio). Casi todos los sistemas informáticos actuales utilizan el código ASCII o
una extensión compatible para representar textos y para el control de dispositivos que
manejan texto como el teclado.
Este código comprende los números decimales del 0 al 255.

Del 0 al 31 corresponde a instrucciones. El número 32 corresponde a la orden de ejecutar
espacios entre palabras cuando oprimimos la barra espaciadora en el teclado.
Del 33 al 127 corresponde a los caracteres alfanuméricos más utilizados. A partir del número
128 aparecen otras letras y algunos signos que generalmente no aparecen en el teclado del
ordenador.
Si quieres escribir cualesquiera de los caracteres alfanuméricos incluidos entre el número 33
y el 255, sólo tienes que abrir el procesador de textos y activar el teclado numérico.
Si ese teclado no se encuentra activado, sólo tienes que oprimir la tecla “Bloq Num” en el
propio teclado (cuando está activado se reconoce porque se enciende el primer LED, situado
encima de esa tecla que aparece con el nombre “N/Lock”o en la misma tecla, Bloq Num)
Seguidamente se oprime la tecla “Alt” y se teclea, simultáneamente, sin soltarla, el número
decimal correspondiente a la letra, número o signo del Código ASCII que queremos obtener.
Ejemplos:
~ = Alt 126 ½ = Alt 171
_ = Alt 95 ¼ = Alt 172
A continuación soltamos la tecla “Alt” y el carácter aparecerá escrito en el procesador.
En el código binario, el número “0” corresponde igualmente al "0" y el “255” al "1111 1111".
Cada uno de los caracteres alfanuméricos del Código ASCII equivale a un Byte de
información, aunque el número binario correspondiente al decimal no ocupe ocho cifras.
El código ASCII comprende sólo hasta el número decimal 255, porque a partir de ahí, el
número 256 en binario pasa a ser 1 0000 0000, sobrepasando los ocho dígitos requeridos para
completar un byte de información

Decimal Signif. Código Binario Decimal Signif. Código Binario
32 Espacio 10 0000 95 _ 101 1111
33 ! 10 0001 96 ` 110 0000
34 " 10 0010 97 a 110 0001
35 # 10 0011 98 b 110 0010
36 $ 10 0100 99 c 110 0011
37 % 10 0101 100 d 110 0100
38 & 10 0110 101 e 110 0101
39 ' 10 0111 102 f 110 0110
40 ( 10 1000 103 g 110 0111
41 ) 10 1001 104 h 110 1000
42 * 10 1010 105 i 110 1001
43 + 10 1011 106 j 110 1010
44 , 10 1100 107 k 110 1011
45 - 10 1101 108 l 110 1100
46 . 10 1110 109 m 110 1101
47 / 10 1111 110 n 110 1110
48 0 11 0000 111 o 110 1111
49 1 11 0001 112 p 111 0000
50 2 11 0010 113 q 111 0001
51 3 11 0011 114 r 111 0010
52 4 11 0100 115 s 111 0011
53 5 11 0101 116 t 111 0100
54 6 11 0110 117 u 111 0101
55 7 11 0111 118 v 111 0110

56 8 11 1000 119 w 111 0111
57 9 11 1001 120 x 111 1000
58 : 11 1010 121 y 111 1001
59 ; 11 1011 122 z 111 1010
60 < 11 1100 123 { 111 1011
61 = 11 1101 124 | 111 1100
62 > 11 1110 125 ¦ 111 1101
63 ? 11 1111 126 ~ 111 1101
64 @ 100 0000 127 ¦ 111 1110
65 A 100 0001 128 Ç 1000 0000
66 B 100 0010 130 é 1000 0010
67 C 100 0011 144 É 1001 0000
68 D 100 0100 157 Ø 1001 1101
69 E 100 0101 160 á 1010 0000
70 F 100 0110 161 í 1010 0001
71 G 100 0111 162 ó 1010 0010
72 H 100 1000 163 ú 1010 0011
73 I 100 1001 164 ñ 1010 0100
74 J 100 1010 165 Ñ 1010 0101
75 K 100 1011 166 ª 1010 0110
76 L 100 1100 167 º 1010 0111
77 M 100 1101 168 ¿ 1010 1000
78 N 100 1110 169 ® 1010 1001
79 O 100 1111 171 ½ 1010 1010
80 P 101 0000 172 ¼ 1010 1100
81 Q 101 0001 173 ¡ 1010 1101

82 R 101 0010 181 Á 1011 0101
83 S 101 0011 184 © 1011 1000
84 T 101 0100 214 Í 1101 0110
85 U 101 0101 224 Ó 1110 0000
86 V 101 0110 225 ß 1110 0001
87 W 101 0111 230 µ 1110 0110
88 X 101 1000 233 Ú 1110 1001
89 Y 101 1001 241 ± 1111 0001
90 Z 101 1010 243 ¾ 1111 0011
91 [ 101 1011 246 ÷ 1111 0110
92 \ 101 1100 248 ° 1111 1000
93 ] 101 1101 252 ³ 1111 1100
94 ^ 101 1110 253 ² 1111 1101
Nota: Es conveniente tener a mano el conjunto de símbolos sin las letras del teclado.
De esta forma el conjunto cabe en un solo folio:
Decimal Signif. Código Binario Decimal Signif. Código Binario

32 Espacio 10 0000 123 { 111 1011
33 ! 10 0001 124 | 111 1100
34 " 10 0010 125 ¦ 111 1101
35 # 10 0011 126 ~ 111 1101
36 $ 10 0100 127 ¦ 111 1110
37 % 10 0101 128 Ç 1000 0000
38 & 10 0110 130 é 1000 0010
39 ' 10 0111 144 É 1001 0000
40 ( 10 1000 157 Ø 1001 1101
41 ) 10 1001 160 á 1010 0000
42 * 10 1010 161 í 1010 0001

43 + 10 1011 162 ó 1010 0010
44 , 10 1100 163 ú 1010 0011
45 - 10 1101 164 ñ 1010 0100
46 . 10 1110 165 Ñ 1010 0101
47 / 10 1111 166 ª 1010 0110
58 : 11 1010 167 º 1010 0111
59 ; 11 1011 168 ¿ 1010 1000
60 < 11 1100 169 ® 1010 1001
61 = 11 1101 171 ½ 1010 1010
62 > 11 1110 172 ¼ 1010 1100
63 ? 11 1111 173 ¡ 1010 1101
64 @ 100 0000 181 Á 1011 0101
91 [ 101 1011 184 © 1011 1000
92 \ 101 1100 214 Í 1101 0110
93 ] 101 1101 224 Ó 1110 0000
94 ^ 101 1110 225 ß 1110 0001
95 _ 101 1111 230 µ 1110 0110
96 ` 110 0000 233 Ú 1110 1001
241 ± 1111 0001
243 ¾ 1111 0011
246 ÷ 1111 0110
248 ° 1111 1000
252 ³ 1111 1100
253 ² 1111 1101
A continuación presentamos un ejemplo del código de ASCII con paridad
Caracteres ASCII 7 bits ASCII 8 bits (con paridad)

@ 1000000 0 1000000 (par)
A 1000001 1 1000001(impar)
B 1000010 0 1000010(par)

1.9.5. Representación de Números Reales
Un número real se puede representar mediante:
𝑁 = 𝑠𝑀𝑟 𝑒 . Denominada notación científica binaria
Donde
s: signo M: mantisa r: base e: exponente
Ejemplo
Sea el número 𝑁 = −37.625
Entonces 𝑁 = −0.37625𝑥102 , notación científica decimal
s: (-) M: 37625 r: 10 e: 2
Ahora N en el sistema binario 𝑁 = −100101.101
Entonces 𝑁 = −0.100101101𝑥26 notación científica binaria
s: (-) M: 100101101 r: 2 e: 6
Mantisa.-Es un número real con el punto decimal implícito a la izquierda de sus bits, se
codifica normalmente en el formato signo-magnitud.
Exponente.-Es un numero entero se codifica generalmente en el formato signo-magnitud o

exceso a 2𝑛−1.
a) Formato para números reales
Los computadores no almacenan los números con precisión infinita sino de forma
aproximada empleando un número fijo de bits (apócope del término inglés Binary Digit) o
bytes (grupos de ocho bits). Prácticamente todos los computadores permiten al programador
elegir entre varias representaciones o 'tipos de datos'. Los diferentes tipos de datos pueden
diferir en el número de bits empleados, pero también (lo que es más importante) en cómo el
número representado es almacenado: en formato fijo (también denominado 'entero') o en
punto flotante (denominado 'real'). Es decir
-Punto fijo
-Punto flotante: -Precisión simple
- Precisión doble
-IEEE-754

Punto fijo. -Los primeros computadores almacenaban los números reales en un formato
llamado punto fijo, se puede representar enteros o reales con signo, se designa un numero
de bits fijo para la parte entera y el resto a la parte fraccionaria.
Ejemplo
Sea el 𝑁 = 25.125 expresar en formato punto fijo de 32 bits
00000000000011001.0010000000000000
16 bits parte entera 16 bits parte fraccionaria
En esta representación, el punto que separa la parte entera de la parte fraccionaria, siempre
se ubica en una posición fija y de allí el nombre de esta representación. Un numero se
puede codificar en S-M, complemento a 1 o complemento a 2
Punto flotante.-Sea 𝑁 = ±(𝑎𝑛−1 … 𝑎0 . 𝑎−1 … . . 𝑎−𝑚 )𝑟 , en punto flotante
𝑁 = ±(𝑎𝑛−1 … 𝑎0 . 𝑎−1 … . . 𝑎−𝑚 )𝑟 , al codificar un número en punto flotante, la mantisa y el

exponente se codifican por separado. La base es implícita y no se incluye en la
representación, los formatos de punto flotante que se utilizan en los sistemas de cómputo de
los diversos fabricantes difieren con frecuencia en la cantidad de bits que se usan para
representar la mantisa y el exponente así como el método de codificación.
b) Tipos de formatos
Precisión simple
Emplea un campo de 32 bits, 1 bits para el signo, 8 bits para el exponente, y 23 bits para la
matinsa.
Signo Exponente Mantisa

1 bits 8 bits 23 bits
Ejemplo
Sea el número 𝑁 = −37.625, codificar en precisión simple.
N en el sistema binario 𝑁 = −100101.101
Entonces 𝑁 = −0.100101101𝑥26 Notación científica binaria
Ahora codificando
Signo: 1
Exponente en exceso: 6 + 28−1 = 134 → 𝑁 = 10000110

1 10000110 100101101 000000000000000
Signo exponente mantisa Bits agregados
Precisión doble
Emplea un campo de 64 bits, 1 bits para el signo, 11 bits para el exponente, y 52 bits para la
matinsa.
Signo Exponente Mantisa

c) Formato normalizado
El formato estándar IEEE (Institute of Electrical and Electronics Engineers), es conocido

como IEEE-754, ha sido aceptado como la forma normalizada para números reales donde se
emplean 32 bits. Al normalizar un número, este se ajusta de tal manera que su valor es de
por lo menos 1, pero menor que 2. La mantisa es de 24 bits y contiene un bit escondido igual
a 1 que permite representar 24 bits, aunque sea almacenado con 23 bits. El bit escondido es
el primero del número normalizado. El exponente se almacena como exponente polarizado,
en forma de precisión sencilla del número real, la polarización es dada a continuación.
Precisión sencilla: 127 = 𝑒 + (28−1 − 1), e:exponente
Doble precisión: 1023 = 𝑒 + (211−1 − 1)
Ejemplo 1
Codificar los números 1.5 y 0.375 en IEEE-754
i) N=1.5
decimal binario Notación científica

1.5 1.1 1.1x20
Exponente polarizado: 0 + (28−1 − 1) = 127 ≈ 1111111
Codificando
0 01111111 10000000000000000000000
ii) N=0.375

decimal binario Notación científica
0.375 0.011 1.1x2-2
Exponente polarizado: −2 + (28−1 − 1) = 125 ≈ 1111101
Codificando
0 01111101 10000000000000000000000
Ejemplo 2
Restar los números 1.5 y 0.375 en IEEE-574, dar el resultado en el mismo formato.
Pasos seguir
Paso 1: Restar los exponentes polarizados |127 − 125| = 2
Paso 2: Elegir la mantisa del menor número, luego se desplazar a la derecha la mantisa una
cantidad de dígitos de acuerdo al resultado de la resta de exponentes polarizados, es decir
El menor numero
0.375 0.011 1.1x2-2

Mantisa Mantisa desplazada
1 0.011
Paso 3: Restar las mantisas del número mayor con la mantisa desplazada, es decir
1.100 (-)
0.011
1.001
El resultado de la resta será 1.001. 20 → 1.0012 → en decimal 20 + 2−3 = 1.12510
Paso 4: Normalizando
1.001. 20 → 0 + 127 = 127 ≡ 01111111
Finalmente codificando
0 01111111 00100000000000000000000

Resumen de Operaciones en punto flotante
Para sumar o restar dos números representados en punto flotante se debe seguir los
siguientes pasos.
1.- seleccionar el número con menor exponente y desplazar su mantisa a la derecha, tantos
pasos como la diferencia en valor absoluto de los exponentes de los operandos.
2.-Igualar el exponente del resultado al mayor de los exponentes de los operandos
3.-Sumar o restar mantisas y determinar el signo del operando.
4.-Normalizar el resultado si es necesario

Capítulo 2
Lógica proposicional
2.1.-Lógica.- La lógica estudia la forma del razonamiento. La Lógica es la disciplina que

trata de métodos de razonamiento. En un nivel elemental, la Lógica proporciona reglas y
técnicas para determinar si es o no valido un argumento dado. El razonamiento lógico se
emplea en Matemáticas para demostrar teoremas, sin embargo, se usa en forma constante
para realizar cualquier actividad en la vida.
2.1.1.-Razonamiento
Razonamiento es un proceso mental que se caracteriza porque en él se produce el paso de uno
o más enunciados (las denominadas premisas) a otro posterior (lo que denominamos
conclusión) que se deriva necesariamente de aquellos.
2.1.2.-Las premisas
Denominamos premisas de nuestro razonamiento (simbolizadas P1 , P 2 , P3 ... Pn) a cada uno

de los enunciados que utilizamos para defender la idea o enunciado que queremos demostrar.
Por ejemplo:
P1: En el mes de enero cada día anochece un poco más tarde.

P2: Estamos en el mes de enero.
__________________
C: Por lo tanto, mañana anochecerá un poco más tarde que hoy.

2.1.3.-Conclucion
Denominamos la conclusión de nuestro razonamiento (simbolizada C) al enunciado que

intentamos demostrar o defender y para el que hemos construido nuestro razonamiento.
Ver ejemplo anterior
2.2.-Proposición.- Una proposición es todo enunciado al que se le puede asignar uno y sólo
uno de los valores de verdad, que son verdadero (V) o falso (F).
Por lo general, las proposiciones se representan con las letras minúsculas del alfabeto,
desde la letra p en adelante, es decir, p, q, r, s, t, ... etc.
Ejemplo

i) La expresión 18 + 5 = 21 es una proposición que se puede indicar brevemente de la
forma
p: 18 + 5 = 21
Cuyo valor de verdad es falso, lo que se indica mediante
V (p) = F
ii) Sea la proposición

q: Lima es la capital del Perú V(q) = V
Las proposiciones pueden ser simples o compuestas, estas últimas constan de dos o más
enunciados simples.
Ejemplo
Sea la siguiente proposición r
r: Pitágoras era griego y era geómetra.
p y q
Se observan dos proposiciones simples. La primera, p, nos afirma que Pitágoras era griego
y la segunda, q, que Pitágoras era geómetra.
2.3.-Funciones proposicionales,- Si en la proposición "cinco es mayor que tres" (en

símbolos es 5 > 3) reemplazamos al número 5 por la letra x, se obtiene la expresión "x es
mayor que tres" (x > 3), y si convenimos que x no represente necesariamente al número 5,
sino a un número real cualquiera, entonces el enunciado x > 3 se denomina función
proposicional y se anota p(x) o p(x).
Una función proposicional en una variable o indeterminada x es un enunciado en el que
aparece x como sujeto y que se convierte en una proposición cuando se le asigna un valor
específico a la variable.
Ejemplo
Sea la función proposicional p(x): 2x-5 = 3. Si se remplaza x por 4 y x por 2, se obtienen,
respectivamente, los siguientes valores de verdad: p(4) = V y p(2) = F

2.4.-Conectivos lógicos
A partir de proposiciones simples es posible generar otras, las compuestas. Es decir, se

puede operar con proposiciones utilizando para ello ciertos símbolos llamados conectivos
lógicos.
Conectivo lógico Símbolo significado
Negación ~ “No….”, “No es cierto

que”
Conjunción o producto lógico ∨ “ ..y..”
Disyunción o suma lógica ∧ “..O.. “ (en sentido

incluyente)
Implicación ⇒ “..implica…”, o “si
entonces”
Doble implicación ⇔ “..si y solo si”
Diferencia simétrica o Disyunción excluyente ∆ O ⊕ “..O.. “ (en sentido

excluyente)
Tablas de verdad
Sean las proposiciones p y q
p q p∧q p∨q p⇒q p⇔q p⊕q
V V V V V V F
V F F V F F V
F V F V V F V
F F F F V V F
2.5.-Proposiciones compuestas
Al conjunto de proposiciones, conectivos lógicos y símbolos de agrupación lo denominamos

forma lógica.
Ejemplo ~ {(p  q)  (s  t)}

2.5.1.-Proposición tautológica
Si al evaluar una fórmula lógica, resulta que todos los valores de verdad son siempre
verdaderos para cualquier combinación de los valores de verdad de las proposiciones
componentes, se dice que dicha fórmula es una Tautología o Ley lógica.
Ejemplo
Analizando la proposición p  ~p mediante la tabla de verdad, se tiene:
p ~p p  ~p
V F V
F V V
2.5.2.-Proposicion de contradicción
Si al estudiar una fórmula lógica, a diferencia de los ejemplos anteriores resulta que para
cualquier valor de verdad de las proposiciones intervinientes el resultado de dicha fórmula
es siempre falso, se dice que dicha fórmula es una Contradicción.
Ejemplo
Analicemos la fórmula lógica p  ~p
p ~p p  ~p
V F F
F V F
2.5.3.-Proposicion condicional
Implicación de las proposiciones p y q es la proposición p  q (se lee “p implica q”, “si p

entonces q” o “p solo si q”)
Dónde: p (hipótesis o antecedente) y q (conclusión o consecuente)

2.5.4.-Implicaciones asociadas al condicional
-Si tenemos la proposición p⇒q, la proposición reciproca será q⇒p
-Si tenemos la proposición p⇒q, la proposición inversa o contraria será ∼ 𝒑 ⇒∼p
-Si tenemos la proposición p⇒q, la proposición contrareciproca será ∼ 𝒒 ⇒∼p
p q p  q ~p ~q ~q  ~p
V V V F F V
V F F F V F
F V V V F V
F F V V V V
Equivalencias lógicas
1. Ley de doble negación: c) p  (q  r )  ( p  q)  r

a)  ( P)  P 5. Leyes de Morgan
2. Ley de Idempotencia: a)  ( p  q )   p   q
a) p  p  p
b)  ( p  q )   p   q
b) p  p  p 6. Leyes del condicional
3. Leyes conmutativas: a) p  q   p  q
a) ( p  q )  (q  p )
b)  ( p  q )  p   q
b) ( p  q )  (q  p ) 7. Leyes del Bicondicional
c) ( p  q)  (q  p) a) ( p  q)  ( p  q )  (q  p )
4. Leyes asociativas: b) ( p  q)  ( p  q)  ( q  p)
a) p  (q  r )  ( p  q)  r c) ( p  q)  ( p  q)  ( p   q)
b) p  (q  r )  ( p  q)  r

a) ( p  q )   q   p
8. Leyes distributivas
b) ( p  q )   q   p
a) p  (q  r )  ( p  q)  ( p  r )
11. Elementos Neutros para la
b) p  (q  r )  ( p  q)  ( p  r )
conjunción y disyunción
c)
a) p  V  p
p  (q  r )  ( p  q)  ( p  r )
b) p  F  p
d)
p  (q  r )  ( p  q)  ( p  r )
9. Leyes de absorción 12. Leyes adicionales

a) p  ( p  q)  p a) ( p  q)  ( p  q)  p
b) p  ( p  q)  p  q b) ( p  q)  ( p   q )  p
c) p  ( p  q)  p c) ( pq )   ( p  q )
d) p  ( p  q)  p  q d)  p  p  V
10. Leyes de transposición
e)  p  p  F
2.6.- Cuantificadores
A partir de funciones proposicionales es posible obtener proposiciones generales mediante un

proceso llamado de cuantificación. Asociados a la indeterminada x, introducimos los símbolos
“x” y “x”, llamados cuantificador universal y cuantificador existencial, respectivamente.
Las expresiones
“para todo x, se verifica p(x) ” se denota en símbolos por  x : p(x)
”existe x, tal que se verifica p(x)” se denota en símbolos por  x : p(x)

Corresponden a una función proposicional p(x) cuantificada universalmente en el primer caso, y
existencialmente en el segundo.
Una función proposicional cuantificada universalmente es V si y sólo si son V todas las
proposiciones particulares asociadas a ella.

2.6.1.-Negación de cuantificadores
En el conjunto de los números enteros (Z) consideremos la proposición:
p: Existen múltiplos de dos que son múltiplos de cuatro (verdadero)
La negación de p es:
~p: No existen múltiplos de dos que son múltiplos de cuatro (falso)
Equivalentemente:
~p: Todos los múltiplos de dos no son múltiplos de cuatro.
En símbolos:
p: " n Z / n es múltiplo de 2 y n es múltiplo de 4"
~p: "n Z, n no es múltiplo de 2 ó n no es múltiplo de 4"
en esta negación se usa las leyes de De Morgan.
En general, en relación a los cuantificadores tenemos:
~ [  xU / p(x)]  [xU, ~p(x)]
~ [xU, p(x)]  [  xU / ~p(x)]
2.7.-Metodos de demostración
2.7.1.-Metodo directo
Una seria de premisas que deben ser verdaderas, se basa en.
(𝑝1∧ 𝑝2 ∧ 𝑝3 ∧ … . .∧ 𝑝𝑛)→𝑞
Premisas o hipótesis conclusión

Esquema
1) P antecedente de la implicación que se quiere demostrar
2) 𝑝2 justificación
m) q
La implicación está demostrada
Ejemplo
Demostrar que si n es par, entonces n2 es par
P: n es par
q: n2 es par
n es par → n2 es par
Demostración
1.-n es par
2.-n=2k para algún entero por 1 definición de par
3.- n2=(2k)2=4k2
4.- n2=(2k)2=2(2k2)
5.- n2 es par

2.7.2 Método indirecto
Se basa en la equivalencia
p⇒q≡ ∼ 𝒒 ⇒∼ 𝒑
Se debe demostrar que: ∼ 𝒒 ⇒∼ 𝒑 (contrareciproca)
Esquema
1) ∼ 𝒒
m) ∼ 𝒑
La implicación está demostrada
Ejemplo
Si x+y=100 solo una de las variables puede ser mayor que 50
Demostración
1.-(x>50 ∧ y>50) negación del consecuente
2.-x+y>100
3.-𝑥 + 𝑦 ≠ 100
4.-∼ ( 𝑥 + 𝑦 = 100) negación de antecedente
La implicación esta demostrada

Ejemplo
Sea la implicación directa “siendo n entero, si n2 es par entonces n es par”
La implicación contrarrecíproca es “siendo n entero, si n es impar entonces n2 es impar”
Demostrando la verdad del enunciado contrarrecíproco se demuestra la verdad de la implicación

directa.
Demostración
Si n es impar, puede escribirse de la forma n = 2k+1, siendo k un número entero, luego
n2 = (2k + 1)2
= 4 k2 + 4k + 12
= 2 (2 k2 + 2k) + 1, que es un número impar, luego, si n2 es
par entonces n es par.
2.7.3 Método del absurdo o la contradicción
Se basa en (𝒑 ⇒ 𝒒) ∧ (𝒑 ⇒∼ 𝒒) ≡∼ 𝒑
Para demostrar p se demuestra que ∼ 𝑝 es falso
(𝒑 ≡∼ 𝒑 → 𝑭)
Esquema
1) ∼ 𝒑 se empieza con la negación de p
2) 𝑝2
3) 𝑝3
m) 𝐹
Queda demostrado p
Ejemplo
Demostrar que √2 no es racional.

𝑝
r es racional si existen dos enteros p y q tales que 𝑟 = 𝑞 , 𝑞 ≠ 0
p: √2 no es racional
∼ 𝑝: √2 es racional
1.- √2 es racional, negación de lo que se quiere demostrar
𝑎
2.- √2 = 𝑏 para algún entero a y algún entero b, sin factores comunes
𝑎2
3.- 2 = 𝑏2
4.- 𝑎2 = 2𝑏 2
5.- 𝑎2 es par
6.- a es par
7.- a=2k para algún entero k
8.- (2k)2=2b2
9.-
4k2=2b2
10.-
2k2=b2
11.- b2 es par
12.- b es par
13.- a y b tienen factor común
14.- a y b no tienen factor común ∧ a y b tienen factor común
15.-F
Queda demostrado que √2 no es racional
2.8.-Predicados
Un predicado es un enunciado que expresa una propiedad entre ciertos objetos. Un predicado se
denota con el símbolo p(x) (también usamos q(x), s(x), P(x), Q(x), etc.) donde p representa la
propiedad en cuestión, y x es una variable que representa a los objetos a los que se refiere el
predicado p. En general, si un predicado se refiere a n objetos, entonces escribimos p(x1, ..., xn).
Usamos predicados para representar propiedades de un solo objeto, o bien propiedades y relaciones
entre diversos objetos.

Ejemplos
1.- 𝑃(𝑥): 𝑥 2 − 6𝑥 + 8 = 0
2.- 𝑃(𝑥, 𝑦): 𝑥 𝑒𝑠 𝑚𝑒𝑛𝑜𝑟 𝑞𝑢𝑒 𝑦
3.- ∀𝑋: 𝑋 ∈ 𝑅 ∶ −(−𝑋) = 𝑋 𝑒𝑠 𝑇 ( 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑜)
4.- Todos los estudiantes del curso de matemática discreta estudian

( ∀ 𝑋: 𝑋 , estudiante del curso de matemática discreta: 𝑋 estudia)
2.8.1.- Predicados con cuantificadores
i) Cuantificador existencial
Es la expresión “existe” que se representa por ∃
∃ 𝑋: 𝐷(𝑋) ∶ 𝑃(𝑋)
Dónde: ∃ 𝑋 ∶ Cuantificador existencial
𝐷(𝑋) ∶ Dominio del predicado
𝑃(𝑋) : Cuerpo del predicado
Sera verdadero, si para algún 𝑋, cumple que 𝐷(𝑋), 𝑃(𝑋) es verdadero.

Sera falso, si para ninguna 𝑋, cumple que 𝐷(𝑋), 𝑃(𝑋) es falsa.
Ejemplo
( ∃ 𝑋, 𝑋 ,entero ∧ 0 < 𝑋 ≤ 3: 𝑋 2 ≥ 9 )
Para 𝑋 = 3 que cumple 𝐷(𝑋), se cumple 𝑃(𝑋)
ii) Cuantificador universal
Es la expresión “para todo” que se representa por ∀
∀ 𝑋: 𝐷(𝑋) ∶ 𝑃(𝑋)
Afirma que para todo X que cumple 𝐷(𝑋), se cumple 𝑃(𝑋)
Sera verdadero, si se demuestra que para todo 𝑋, que cumple 𝐷(𝑋), 𝑃(𝑋) es verdadero.
Sera falso, si se encuentra algun 𝑋, cumple que 𝐷(𝑋), 𝑃(𝑋) es falsa.

Ejemplo
( ∀ 𝑋, 𝑋 entero ∧ 0 < 𝑋 ≤ 3: 𝑋 2 ≤ 9 ) es verdadero
Se cumple en todos los valores del rango {1,2,3}
iii) Leyes de predicados
1.- ∀𝑥 ∀ 𝑦 𝑃(𝑥, 𝑦) ≡ ∀𝑦 ∀ 𝑥 𝑃(𝑥, 𝑦)
2.- ∃𝑥 ∀ ∃ 𝑃(𝑥, 𝑦) ≡ ∃𝑦 ∃ 𝑥 𝑃(𝑥, 𝑦)
3.- ∼ (∀ 𝑥 𝑃(𝑥)) ≡ ∃𝑥 (∼ 𝑃(𝑥)
4.- ∼ (∃ 𝑥 𝑃(𝑥)) ≡ ∀𝑥 (∼ 𝑃(𝑥))
5.- ∀𝑥 (𝑃(𝑥) ∧ 𝑄(𝑥)) ≡ ∀𝑥 𝑃(𝑥) ∧ ∀𝑥𝑄(𝑥)
6.- ∃𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) ≡ ∃𝑥 𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥)
2.9.-Induccion Matemática
Principio de inducción matemática
Sea 𝑃(𝑛) un predicado, donde 𝑛 es un entero positivo, talque:
i) 𝑃(1) es verdadero (paso base)
ii) para 𝑘 ≥ 1, si 𝑃(𝑘) es verdadero entonces 𝑃(𝑘 + 1) es verdadero (paso inductivo)
(Hipótesis Inductiva) (Tesis)
Entonces 𝑃(𝑛) es verdadero ∀ 𝑛 ∈ 𝑍 + ( Conclusion)
Ejemplo 1
Demostrar que 𝑛 es un número natural entonces:
1 + 3 + 5 +………………..+(2𝑛 − 1) = 𝑛2
Solución
1) Si 𝑛 = 1 la proposición 2.1 − 1 = 1 es verdadera

2) Debemos demostrar que 𝑃(𝑘) → 𝑃(𝐾 + 1)
Donde 𝑃(𝑘): 1 + 3 + 5 +………………..+(2𝑘 − 1) = 𝑘 2
Y 𝑃(𝑘 + 1): 1 + 3 + 5 +………………..+(2(𝑘 + 1) − 1) = (𝑘 + 1)2
Usaremos la demostración directa. Supongamos que
𝑃(𝑘): 1 + 3 + 5 +………………..+(2𝑘 − 1) = 𝑘 2 es verdadera. Entonces
1 + 3 + 5 +………………..+(2𝑘 − 1)) + (2(𝑘 + 1) − 1) =
𝑘 2 + (2(𝑘 + 1) − 1) = 𝑘 2 + 2𝑘 + 1
𝑘 2 + (2(𝑘 + 1) − 1) = (𝑘 + 1)2
Así 1 + 3 + 5 +………………..+(2(𝑘 + 1) − 1) = (𝑘 + 1)2
Esto demuestra 𝑃(𝑘) → 𝑃(𝐾 + 1)
Es decir se ha demostrado por inducción que 1 + 3 + 5 +………………..+(2𝑛 − 1) = 𝑛2 .
Ejemplo 2

Capítulo 3
3.1. Pares Ordenados
El orden de los elementos en un conjunto no interesa, por ejemplo: dados A = {1, 2} y B = {2, 1},
representan el mismo conjunto; o sea que para ser iguales nos importa únicamente que los conjuntos
contengan los mismos elementos, sin importar el orden en que éstos se enumeren.
Definamos un nuevo concepto: Un par ordenado consiste en dos componentes, de los cuales a uno
se le designa como el primer componente, y al otro, como el segundo. Dado un par ordenado donde
a es el primer componente y b es el segundo, ésta se escribe (a, b).
De lo expuesto, se deduce entonces que, dadas dos pares ordenados: (a, b) y (c, d) son iguales si y
solo si se cumple que a = c y b = d .
El concepto de par ordenado se puede extender para el caso de tres componentes (a, b, c) donde a es
el primer componente de la terna, b el segundo y c el tercero. En general se puede extender el
concepto para n componentes (n-tuplas).
3.1.1. Producto cartesiano.
Dados dos conjuntos A y B, llamamos producto cartesiano al conjunto de todos los pares posibles
de elementos, tomando el primer elemento del par del conjunto A y el segundo elemento del par
del conjunto B. Por esta razón decimos que los pares son ordenados. Simbólicamente expresamos:
A x B = {(x, y) / x  A, y  B}
Los conjuntos A y B pueden ser un único conjunto, en cuyo caso tendremos A x A qué se puede
expresar con A2 . En consecuencia: A x B  B x A, dado que el par (x, y) no es igual al par (y,
x) por ser ordenados. Luego el producto cartesiano no es conmutativo.
Ejemplos
Sean los conjuntos A = {a, b} y B = {1, 2} donde

A x B = {(a, 1), (a, 2), (b, 1), (b, 2)} y B x A = {(1, a), (2, a), (1, b), (2, b)},
Queda claro que los conjuntos tienen elementos (pares ordenados) distintos.

3.1.2. Formas de representación
Sean los conjuntos: A = {a, b, c} y B = {1, 2, 3, 4}, su producto cartesiano resulta:
A x B = {(a, 1), (a, 2), (a, 3), (a, 4), (b, 1), (b, 2), (b, 3), (b, 4), (c, 1), (c, 2), (c, 3), (c, 4)}
Se puede representar gráficamente por medio de puntos en un plano, como se muestra a continuación.
Cada punto P representa una pareja ordenada (a, b) de valores y viceversa. En el eje horizontal
representamos los elementos del primer conjunto y en el vertical los valores del segundo conjunto.
A esta representación se le conoce como diagrama cartesiano.
A
a b c
Otra manera de visualizar, es a través de una representación gráfica, donde se destaquen los
elementos que pertenecen al conjunto A y los que pertenecen a B (diagrama de VENN). Se trazan
flechas que indican la relación que existe entre cada elemento del conjunto A y su pareja en el
conjunto B.
A esta representación gráfica se le conoce como diagrama de flechas.
A B
1
a
2
b
3
c
4

Una tercera forma de representar, es la conocida como diagrama de árbol, que consiste en escribir
los elementos según un orden jerárquico partiendo de un punto inicial, al que se subordinan los
elementos del primer conjunto y a cada uno de éstos los del segundo.
4
a
1
2
b
3
1
c
2
4
3.2. Relaciones binarias
Dados dos conjuntos A y B, definimos una relación entre los elementos de estos dos conjuntos,
cuando damos una propiedad que vinculen elementos del primer conjunto con elementos del
segundo. Así por ejemplo, si
A = {estudiantes de FIIS} = {María, Juan, Luis, Raúl} y
B = {cursos de la carrera de Ingeniería Industrial por ciclo}= {1, 2, 3,..., 10}, podemos definir una
relación "x tiene por ciclo y", donde x representa uno cualquiera de los estudiantes mencionados e
y será el ciclo correspondiente. La relación estará definida entonces por el conjunto:
R = {(María; 1), (Juan; 2), (Luis; 4), (Raúl; 5)}
Como se ve una relación entre los elementos de dos conjuntos A y B es un conjunto de pares
ordenados de elementos pertenecientes a esos conjuntos que verifican una propiedad.

3.2.1. Definición
Una relación binaria 𝑅, de un conjunto A en un conjunto B, es un subconjunto de 𝐴𝑥𝐵.
𝑅: 𝐴 → 𝐵, R = {(x, y) / x  A, y  B; x, y verifican una propiedad}, 𝑅 ⊂ 𝐴𝑥𝐵
Si (𝑎, 𝑏) ∈ 𝑅, se denota 𝑎𝑅𝑏 ( 𝑎 está relacionado con 𝑏)
Dominio: Dom 𝑅 = {𝑥 ∈ 𝐴/(𝑥, 𝑦) ∈ 𝑅, 𝑝𝑎𝑟𝑎 𝑦 ∈ 𝐵 }
Rango: Ran 𝑅 = {𝑦 ∈ 𝐵/(𝑥, 𝑦) ∈ 𝑅, 𝑝𝑎𝑟𝑎 𝑥 ∈ 𝐴 }
Ejemplo
Sean los conjuntos A = {a, b, c}, B = {1, 2, 3, 4} y R = {(a, 2), (b, 2), (b, 3), (b, 4)}
R es una relación entre elementos de los conjuntos A y B, ya que R  (AxB).

Los elementos de la relación son:
Conjunto de Partida = {a, b, c}

Conjunto de Llegada = {1, 2, 3, 4}
Dominio R = {a, b}
Imagen R = {2, 3, 4}
3.2.2. Representación de una relación binaria
Diagramas ( ver en producto cartesiano)
Dígrafos
Matriz booleana
3.2.2.1. Dígrafo (Grafo dirigido)
Los elementos del conjunto se representan como vértices y los pares ordenados como flechas.
Ejemplo
La relación R sobre 𝐴 = {1,2,3,4}, está definida por “(𝑥, 𝑦) ∈ 𝑅 si 𝑥 ≤ 𝑦 es:

R = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3); (3,4); (4,4)}
El dominio de R es el conjunto {1,2,3,4}
El rango de R es el conjunto {1,2,3,4}

Se concluye que: el dominio y rango son iguales porque la relación está definida sobre el mismo
conjunto A.
El digrafo de la relacion R es el siguiente
3.3. Propiedades de las relaciones binarias
Si tenemos una relación R entre los elementos de un mismo conjunto A, podemos enunciar las
siguientes propiedades:
 Reflexiva: Cuando todo elemento del conjunto está relacionado con sí mismo.
- Simbólicamente:  a  A  a R a.
Ejemplo. Sea A = {-2, 1, 2, 3} y una relación R definida en A como: “igual a...”
R = {(-2, -2), (1, 1), (2, 2), (3, 3)}
 Simétrica: Cuando cada vez que un elemento está relacionado con otro, éste segundo también está
relacionado con el primero.
- Simbólicamente:  a  A y b  A (a≠b), si a R b  b R a.
Ejemplo.-Sea A = {-2, 1, 2, 3} y una relación R definida en A como: “elementos distintos cuya

suma sea mayor o igual que 1”
R = {(-2, 3), (1, 2), (1, 3), (2, 1), (2, 3), (3, -2), (3, 1), (3, 2)}
 Transitiva: Cuando cada vez que un elemento está relacionado con otro, y éste está relacionado
con un tercero, el primer elemento está relacionado con el tercero.
- Simbólicamente:  a  A, b  A y c  A distintos, si a R b y b R c  a R c.

Ejemplo.- R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
 Antireflexiva:
Cuando todo elemento del conjunto no está relacionado con sí mismo.
- Simbólicamente:  a  A  a R a.
Ejemplo.-Sea A = {-2, 1, 2, 3} y una relación R definida en A como: “menor que”
R = {(-2, 1), (-2, 2), (-2, 3), (1, 2), (1, 3), (2, 3)}
 Antisimétrica: Cuando cada vez que un elemento está relacionado con otro, éste segundo no está
relacionado con el primero.
- Simbólicamente:  a  A y b  A (a≠b), si a R b  b R a.
(También se puede decir que:  a  A y b  A si a R b y b R a  a = b)
Ejemplo.-Sea A = {-2, 1, 2, 3} y una relación R definida en A como: “menor que”
R = {(-2, 1), (-2, 2), (-2, 3), (1, 2), (1, 3), (2, 3)}
Relación Inversa
Dados dos conjuntos A y B, y una relación R entre ellos, se denomina relación inversa de R, y se
representa por R -1, a la correspondencia que asocia a los elementos del conjunto final con los del
conjunto inicial de R; es decir, tiene como Dominio el conjunto Imagen de R, y como conjunto Imagen
el Dominio de R.
Simbólicamente: 𝑅 −1 = {(𝑦, 𝑥)/(𝑥, 𝑦) ∈ 𝑅}

Ejemplo.-Sea la relación R = {(2,1); (3,1); (4,1); (4,3); (5,1); (5,3)} y su relación inversa estará
dado por R-1 = {(1,2); (1,3); (1,4); (1,5); (3,4); (3,5)}
Relación compuesta
Sea 𝑅 es una relación entre A y B, S una relación entre B y C, se define la relación compuesta de R
y S como el conjunto
𝑆°𝑅 = {(𝑥, 𝑧) ∈ 𝐴𝑥𝐶/(∃𝑦 ∈ 𝐵)((𝑥, 𝑦) ∈ 𝑅 ∧ (𝑦, 𝑧) ∈ 𝑆)}
Es decir 𝑥(𝑆°𝑅)𝑧 equivale a (∃𝑦 ∈ 𝐵)(𝑥𝑅𝑦 ∧ 𝑦𝑆𝑧)
Matriz de una relacion binaria
Sean los conjuntos 𝐴 = {𝑎1, 𝑎2 … … . . 𝑎𝑛 }, 𝐴 = {𝑏1, 𝑏2 … … . . 𝑏𝑚 }
Y la relacion 𝑅: 𝐴 → 𝐵, la matriz de la relacion R se representa por
𝑀𝑅 = [𝑚𝑖𝑗 ], la cual se define por:

1, 𝑠𝑖 (𝑎𝑖 , 𝑏𝑗 ) ∈ 𝑅
𝑚𝑖𝑗 = {
0, 𝑠𝑖 (𝑎𝑖 , 𝑏𝑗 ) ∉ 𝑅
Donde la matriz es de orden 𝑚𝑥𝑛
𝑛: numero de elementos de A
𝑚: numero de elementos de B
Ejemplo
Sean los conjuntos A = {a, b, c}, B = {1, 2, 3, 4} y la relación R = {(a,2), (b,2), (b,3), (b,4)}, la
matriz asociada a la relación R estará dado por.
B
1 2 3 4
A
a 0 1 0 0
b 0 1 1 1
c 0 0 0 0
3.4.Operaciones con matrices booleanas
Sean las matrices booleanas 𝐴 = [𝑎𝑖𝑗 ] y 𝐵 = [𝑏𝑖𝑗 ] de orden 𝑚𝑥𝑛
i) La operación union (∨) de las matrices A y B se define
𝐶 = 𝐴 ∨ 𝐵 = [𝑐𝑖𝑗 ]
1, 𝑠𝑖 𝑎𝑖𝑗 = 1 𝑜 𝑏𝑖𝑗 = 1
donde 𝐶𝑖𝑗 = {
0, 𝑠𝑖 𝑎𝑖𝑗 , 𝑦 𝑏𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 𝑐𝑒𝑟𝑜𝑠
Ejemplo.
Sean la matrices booleanas
1 0 0 1 1 1
𝐴 = [0 0 1] y 𝐵 = [1 1 1]
1 0 1 1 0 0
1 1 1
Entonces 𝐴 ∨ 𝐵 = [1 1 1]
1 0 1

ii) La operación conjuncion (∧ ) de las matrices A y B se define
𝐷 = 𝐴 ∧ 𝐵 = [𝑑𝑖𝑗 ]
1, 𝑠𝑖 𝑎𝑖𝑗 , 𝑦 𝑏𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 𝑢𝑛𝑜𝑠

donde 𝐷𝑖𝑗 = {
0, 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Ejemplo.
1 0 0 1 1 1
𝐴 = [0 0 1] y 𝐵 = [1 1 1]
1 0 1 1 0 0
1 0 0
Entonces 𝐴 ∧ 𝐵 = [0 0 1]
1 0 0
iii) La operación producto de las matrices (⊙)
Sean las matrices booleanas 𝐴 = [𝑎𝑖𝑗 ] de orden 𝑚𝑥𝑝 y 𝐵 = [𝑏𝑖𝑗 ] de orden 𝑝𝑥𝑛, se define la
operación, 𝐸 = 𝐴 ⊙ 𝐵 = [𝑒𝑖𝑗 ]
1, 𝑠𝑖 𝑎𝑖𝑘 = 1 𝑜 𝑏𝑘𝑗 = 1 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑛 𝑘, 1 ≤ 𝑘 ≤ 𝑝

donde 𝑒𝑖𝑗 = {
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
Ejemplo.
1 0 0 1 1 1
𝐴 = [0 0 1] y 𝐵 = [1 1 1]
1 0 1 1 0 0
1 0 0 1 1 1 1 1 1
Entonces 𝐴 ⊙ 𝐵 = [0 0 1] ⊙ [1 1 1] = [1 0 0]
1 0 1 1 0 0 1 1 1
Donde
𝑒11 = (1 ∧ 1) ∨ (0 ∧ 1) ∨ (0 ∧ 1) = 1 ∨ 0 ∨ 0 = 1

𝑒12 = (1 ∧ 1) ∨ (0 ∧ 1) ∨ (0 ∧ 0) = 1 ∨ 0 ∨ 0 = 1
.
.
.
p q 𝑝∧𝑞 𝑝∨𝑞
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
3.5.Propiedades de las matrices booleanas
Sean las matrices booleanas A, B, C, donde tenemos las siguientes propiedades.
a) 𝐴 ∨ 𝐵 = 𝐵 ∨ 𝐴
b) 𝐴 ∧ 𝐵 = 𝐵 ∧ 𝐴
c) 𝐴 ∨ (𝐵 ∨ 𝐶) = (𝐴 ∨ 𝐵) ∨ 𝐶
d) 𝐴 ∧ (𝐵 ∧ 𝐶) = (𝐴 ∧ 𝐵) ∧ 𝐶
e) 𝐴 ∨ (𝐵 ∧ 𝐶) = (𝐴 ∨ 𝐵) ∧ (A ∨ 𝐶)
f) 𝐴 ∧ (𝐵 ∨ 𝐶) = (𝐴 ∧ 𝐵) ∨ (A ∧ 𝐶)
g) 𝐴 ∨ (𝐵 ∨ 𝐶) = (𝐴 ∨ 𝐵) ∨ 𝐶
3.6.Clasificacion de las relaciones
Según las propiedades mostradas anteriormente, clasificaremos las relaciones en:
Relacion de equivalencia
Una relacion binaria 𝑅 sobre un conjunto A es de equivalencia si se cumple las propiedades.
Reflexiva
Simetrica
Transitiva
Ejemplo 1
Consideremos un conjunto de rectas incluidas en un plano con la relacion
𝐿1 𝑅𝐿2 ↔ 𝐿1 , 𝑒𝑠 𝑝𝑎𝑟𝑎𝑙𝑒𝑙𝑎 𝑎 𝐿2
Cumple las propiedades:

a) Reflexiva: toda recta 𝐿 es paralela 𝐿 sí misma.
b) Simétrica: si 𝐿1 es paralela 𝐿2  𝐿2 es paralela 𝐿1 .
c) Transitiva: si 𝐿1 es paralela 𝐿2 y 𝐿2 es paralela 𝐿3  𝐿1 es paralela 𝐿3 .
Por lo tanto esta relación es una relación de equivalencia.

Ejemplo 2
Sobre el conjunto 𝐴 = {1,2,3,4,5} se da una relación definida por el dígrafo que se muestra en la
figura 1.
1 3
5
2
4
Figura 1
¿R es una relación de equivalencia?
Veamos si cumple las condiciones de equivalencia
i) Reflexiva
Del dígrafo observamos que:
(1,1) (2,2) (3,3) (4,4) (5, 5) ∈ 𝑅, entonces la relación binaria 𝑅 es reflexiva
ii) Simetría

(1,3) ∧ (3,1) ∈ 𝑅, (5,2) ∧ (2,5) ∈ 𝑅, (3,4) ∧ (4,3) ∈ 𝑅, (1,4) ∧ (4,1) ∈ 𝑅 Entonces la
relación binaria 𝑅 es simétrica
iii) Transitiva
(1,3) ∧ (3,4) → (1,4) ∈ 𝑅
(3,1) ∧ (1,4) → (3,4) ∈ 𝑅
(3,4) ∧ (4,1) → (3,1) ∈ 𝑅
(4,3) ∧ (3,1) → (4,1) ∈ 𝑅
.
.
.
.
(5,5) ∧ (5,2) → (5,2) ∈ 𝑅
(5,2) ∧ (2,2) → (5,2) ∈ 𝑅
Entonces la relación binaria 𝑅 es transitiva.
Por lo tanto 𝑅 es una relación de equivalencia.
3.7. Clases de equivalencia
Dada un relación de equivalencia R definida en un conjunto A, si a  A, se llama clase de

equivalencia de a, se escribe [a], al subconjunto formado por todos los elementos de A relacionados
con a por la relación de equivalencia R.
Simbólicamente: [a] = {x / x  A y x R a}.
Las clases de equivalencia determinan una partición en el conjunto donde se define la relación dado
que:
Ninguna clase de equivalencia es vacía

Las clases de equivalencia son disjuntas dos a dos.
Todo elemento de A pertenece a alguna clase de equivalencia.

3.7.1. Conjunto cociente
Dada una relación R en un conjunto A, se llama cociente de A respecto a R, al conjunto formado por
todas sus clases de equivalencia y se representa por A / R.
𝑨/𝑹 = {[𝒂]/𝒂 ∈ 𝑨}
Ejemplo:
Sean el conjunto A = {1, 2, 3, 4, 5} y la relación de equivalencia

R = {(1,1), (2,2), (3,3), (2,3), (3,2), (4,5), (4,4), (5,5), (5,4)}
La clase de equivalencia de cada elemento es:
[1] = {1}
[2] = {2, 3}
[3] = {2, 3}
[4] = {4, 5}
[5] = {4, 5}
En definitiva, dado que se repiten [2] con [3] y [4] con [5], las clases de equivalencia son:
{1} {2, 3} {4, 5}
Es decir que A / R = {[1], [2], [4]} ={[1], [2], [4]} = {{1}, {2, 3}, {4, 5}}
3.7.2. Partición de un conjunto
Una partición de un conjunto no vacío 𝐴, es una colección 𝑃 = {𝐴1 , 𝐴2 , … … … 𝐴𝑛 }, de

subconjuntos de A talque:
a) 𝐴𝑖 ∩ 𝐴𝑗 = ∅, 𝑠𝑖 𝐴𝑖 ≠ 𝐴𝑗
b) 𝐴𝑖 ∪ … … … 𝐴𝑗 = 𝐴
Los subconjuntos 𝐴𝑖 ∈ 𝑃 son llamados bloques de partición
3.7.3. Relación de orden
Relación de orden parcial: Es toda relación binaria en un conjunto A, que sea:
Reflexiva
antisimétrica
transitiva.
Permite ordenar los elementos a través de la relación.

Pueden definirse dos tipos de relación: de orden amplio y de orden estricto.
3.7.4. Relación de orden amplio
Una relación de orden amplio es aquella que cumple las propiedades reflexiva, antisimétrica y
transitiva.
Ejemplo:
Sea el conjunto A = {1, 2, 3, 4, 5}, y en él la Relación: “menor o igual “
3.7.5. Relación de orden estricto
Una relación de orden estricto es aquella que cumple con las propiedades antireflexiva, antisimétrica
y transitiva
Ejemplo:
Sea el conjunto A = {1, 2, 3, 4, 5}, y en él la Relación: “menor que “
3.7.6. Elementos comparables
Si (𝐴, ≤) es un conjunto parcialmente ordenado, los elementos a y b son comparables, si 𝑎 ≤

𝑏𝑜𝑏≤𝑎
3.8. Orden total
Si cada par de elementos de un conjunto parcialmente ordenado A son comparables se dice que A es
un conjunto ordenado, y al orden parcial se le llama orden total.
En otras palabras, si (𝐴, 𝑅) es un conjunto parcialmente ordenado decimos que A, es totalmente

ordenado, si para todo elemento 𝑥, 𝑦 ∈ 𝐴 ocurre que 𝑥𝑅𝑦 𝑜 𝑦𝑅𝑥. En este caso decimos que R es un
orden total.
Ejemplo 1
1.- Demostrar que la relación “mayor o igual que” (≥) es un orden parcial en el conjunto de los
enteros
i) Reflexiva
Como 𝑎 ≥ 𝑎 para cada entero a (𝑎 ∈ 𝑍), luego ≥ es reflexiva
ii) Antisimetrica

Si 𝑎 ≥ 𝑏 𝑦 𝑏 ≥ 𝑎, entonces 𝑎 = 𝑏 por lo tanto ≥ es antisimetrica
iii) Transitiva
Si 𝑎 ≥ 𝑏 y 𝑏 ≥ 𝑐, entonces 𝑎 ≥ 𝑐, por lo tanto ≥ es transitiva
Por lo tanto ≥ es orden parcial en el conjunto de los enteros y (𝑍, ≥) es un conjunto parcialmente
ordenado.
Ejemplo 2
Sea el conjunto 𝐴 = {2,3,4,5} y 𝑅: 𝐴 → 𝐴. R es una relación “ a divide exactamente a b”, averiguar

si es de orden parcial o una relación de orden total.
𝑅 = {(2,2), (2,4), (3,3), (4,4), (5,5)}
i) Reflexiva
(2,2), (3,3), (4,4), (5,5) ∈ 𝑅, por tanto R es reflexiva
ii) Antisimetrica
(2,4) ∈ 𝑅 ∧ (4,2) ∉ 𝑅, por tanto R es antisimetrica
iii) Transitiva
(2,2) ∧ (2,4) ∈ 𝑅 → (2,4) ∈ 𝑅
(2,4) ∧ (4,4) ∈ 𝑅 → (2,4) ∈ 𝑅, por lo tanto R es transitiva
Por lo tanto R es de orden parcial
Ahora veamos si R es de orden total, usando la definición observamos que (2,4) no son
comparables.
3.8.1. Diagrama de Hasse
Es un diagrama simplificado para representar una relación orden. Para trazar el diagrama de hasse se
borran todos los lazos, porque la relación es reflexiva, se eliminan las aristas que están implicadas
por la propiedad transitiva, los vértices se remplazan por puntos.

Ejemplo
Sea el conjunto 𝐴 = {1,2,3,4}, y R, aRb, “a divide a b”, entonces
𝑅 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}, es un orden parcial y (𝐴, 𝑅) es un conjunto
parcialmente ordenado.
2 4
1 3 2
Dígrafo Diagrama de Hasse
3.8.2.Elementos extremos de un conjunto parcialmente ordenado
Sea (𝐴, ≤) un conjunto parcialmente ordenado se definen los siguientes elementos.
a) Elemento máximo
Un elemento 𝑎 ∈ 𝐴 es un elemento máximo de A si 𝑥 ≤ 𝑎, para todo 𝑥 ∈ 𝐴
b) Elemento mínimo
Un elemento 𝑎 ∈ 𝐴 es un elemento máximo de A si 𝑎 ≤ 𝑥, para todo 𝑥 ∈ 𝐴
Ejemplo
Sea el conjunto 𝐴 = {0,2,4,7,12,14}, donde la relación orden parcial sobre el conjunto A es

𝑥𝑅𝑦 𝑠𝑖 𝑥 ≤ 𝑦, y el diagrama de Hasse de la relación dado por:

14
Elemento máximo: 14
12
Elemento mínimo: 0 22
7
2
4
0
c) Elemento maximal
Un elemento 𝑎 ∈ 𝐴 es un elemento máximal de A, si no existe un elemento 𝑐 ∈ 𝐴, tal que 𝑎 < 𝑐
d) Elemento minimal
Un elemento 𝑎 ∈ 𝐴 es un elemento máximal de A, si no existe un elemento 𝑐 ∈ 𝐴, tal que 𝑐 < 𝑎
Teoremas
1.-Un conjunto parcialmente ordenado tiene a lo más un elemento máximo y a lo más un elemento
mínimo.
2.- Un conjunto parcialmente ordenado tiene al menos un elemento máximal y al menos un

elemento mínimal.
Ejemplo
Sea un conjunto A parcialmente ordenado, cuyo diagrama de hasse se muestra en la figura.

Determinar los elementos maximal, minimal, maximo y minimo.
𝑎2 𝑎3
𝑎1 𝑏3 𝑏5
𝑏4
𝑏2
𝑏1 𝑑4
𝑑2 𝑑3
𝑑1

Elementos maximales: 𝑎1 , 𝑎2 , 𝑎3
Elementos minimales: 𝑑1 , 𝑑2 , 𝑑3
Elemento maximo: ∄
Elemento minimo: ∄
e) Supremos e ínfimos
Sea (𝑨, ≤) un conjunto parcialmente ordenado y B un subconjunto de A se definen los siguientes

elementos.
Cota superior
Un elemento 𝑎 ∈ 𝐴 es una cota superior de B, si 𝑥 ≤ 𝑎, ∀𝑥 ∈ 𝐵
Cota inferior
Un elemento 𝑎 ∈ 𝐴 es una cota inferior de B, si 𝑥 ≤ 𝑎, ∀𝑥 ∈ 𝐵
Supremo
Es la mínima cota superior de B
Infimo
Es la mínima cota superior de B
Ejemplo
Consideremos el conjunto parcialmente ordenado 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ}, cuyo diagrama
de Hasse se muestra en la figura. Determine las cotas superiores e inferiores de los siguientes
subconjuntos de A. h
a) 𝐴1 = {𝑎, 𝑏} a) 𝐴2 = {𝑐, 𝑑, 𝑒}
g
f
a) cotas superiores de 𝑨𝟏 : c, d,e,f,g,h
Cotas inferiores de 𝑨𝟏 : no existe e
d c
b) cotas superiores de 𝑨𝟐 : f,g,h
Cotas inferiores de 𝑨𝟐 : a, b ,c a b

c) Supremo de 𝑨𝟏 : c
Infimo de 𝑨𝟏 : no existe
c) Supremo de 𝑨𝟐 : no existe
Infimo de 𝑨𝟐 : c

Capítulo 4
Teoría de graficas
4.1. Grafo
Un grafo es un par G = (V, A), donde V es un conjunto finito no vacío (a cuyos elementos
llamaremos vértices o nodos) y A es una familia finita de pares no ordenados {u, v} de vértices de V
(a cuyos elementos llamaremos aristas o arcos).
4.1.1. Grafo simple

Un grafo simple es un par G = (V, A), donde V es un conjunto finito no vacío y A es un conjunto
finito de pares no ordenados {u, v} de vértices distintos de V. Grafo que acepta una sola arista uniendo
dos vértices cualesquiera.
Si a = {u, v} es una arista de G, escribiremos sólo a = uv = vu, y diremos que:
Los vértices u y v son adyacentes
La arista uv es incidente con los vértices u y v (también diremos que uv une los vértices u y v).
Los vértices u y v son incidentes con la arista uv (también diremos que u y v son extremos de uv).
El vértice u (o el vértice v) y la arista uv son incidentes
Además, diremos que:
Dos aristas son adyacentes si y sólo si tienen algún extremo común
Un vértice es aislado si no tiene otros vértices adyacentes
Ejemplo Sea un grafo G = (V, A) con V = {a, b, c, d, e, f} y con A = {ab, ad, bc, bf, cd, cf} se puede
representar gráficamente como en la siguiente figura:
b c
a d
f e
Figura: un grafo
De este grafo podemos decir, por ejemplo, que los vértices a y b son adyacentes y son incidentes
con (o son extremos de) la arista ab, que la arista ab es incidente con (o une) los vértices a y b, que

el vértice a y la arista ab son incidentes, que las aristas ab y bc son adyacentes (en este caso, el
extremo común es el vértice b) y que el vértice e es aislado.
4.1.2. Multígrafo
El grafo G = (V, A), es un multígrafo si acepta más de una arista entre dos vértices cualesquiera.
Una arista que aparece repetida en A se llama arista múltiple.
Ejemplo
La siguiente figura se representa un grafo que tiene tres aristas múltiples cuyos extremos son los
vértices a y d, un bucle sobre el vértice c y dos bucles sobre el vértice b. Estos dos últimos bucles
son también aristas múltiples.
a b
d c
Figura: Grafo con bucles y aristas múltiples (Multigrafo)
4.1.3. Grafo etiquetado

Un grafo G = (V, A), es etiquetado si se le ha añadido un peso a las aristas.
4.1.4. Subgrafo
Un subgrafo de G = (V, A) es otro grafo H = (V’, A’) tal que V’  V y A’  A. Si V’ = V, se dice que
H es un subgrafo generador.
El subgrafo inducido por un subconjunto de vértices W  V es el grafo cuyo conjunto de vértices es
W y cuyas aristas son todas las de G cuyos extremos están en W.
En la siguiente figura se muestra:
un grafo G
un subgrafo G1 de G inducido por el subconjunto de vértices {a, b, c, e}
un subgrafo generador G2 de G
a b c a b c a b c
G G1 G2
d e f e d e f
Figura: Un grafo G y dos subgrafos G1 y G2 de G

4.1.5. Grado de un vértice o nodo
Sea G = (V, A) un grafo o multígrafo, el grado de un vértice 𝑣 de G, que se denota por 𝒈𝒓𝒂𝒅(𝒗),
es el número de aristas que inciden en 𝑣
Ejemplo
Para el multígrafo que se muestra en siguiente figura, tendremos los siguientes grados
a b
𝑔𝑟𝑎𝑑(𝑎) = 4
𝑔𝑟𝑎𝑑(𝑏) = 2
𝑔𝑟𝑎𝑑(𝑐) = 1
𝑔𝑟𝑎𝑑(𝑑) = 5
d c
Figura: Multígrafo
4.1.6. Clases de grafos

a) Grafo regular
Un grafo G = (V, A), es regular si todos sus vértices tienen el mismo grado. Si 𝑔𝑟𝑎𝑑(𝑣) = 𝑘
Para todos los vértices entonces el grafo es 𝑘-regular.

Ejemplo
Sea el grafo G = (V, A), mostrado en la siguiente figura, donde se observa que cada vértice tiene
grado 3, en consecuencia diremos que el grafo es 3-regular
a b
d c
b) Grafo completo
Un grafo G = (V, A), es completo si existen aristas uniendo todos los pares posibles de vértices. Es
decir, todo par de vértices (a, b),(𝑎 ≠ 𝑏) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo

de n vértices.
Un Kn, es decir, grafo completo de n vértices tiene exactamente aristas.
Ejemplo
Sean los grafos mostrados en la siguiente figura.

K4
K1 K2 K3
Grafo 𝐾1 es llamado grafo trivial
c) Grafo conexo
Un grafo G = (V, A), es conexo si para cada par de vértices u y v existe un camino de u a v. En caso
contrario se dirá que el grafo es no conexo (o disconexo).

Ejemplo
Sean los grafos mostrados en la siguiente figura.
Figura: Grafo conexo
Figura 1: Grafo no conexo (disconexo) con 6 componentes conexas

4.1.6. Teorema
Sea G = (V, A), un grafo o multígrafo entonces ∑𝑣∈𝑉 𝑔𝑟𝑎𝑑(𝑣) = 2|𝐸|. Es decir la sumatoria de los grados
de todos los vértices es igual al doble del número de aristas.
|𝐸|: Número de aristas
Ejemplo.
V5
Sea el grafo mostrado en la siguiente figura V6 V4
𝑔𝑟𝑎𝑑(𝑣1 ) = 2 , 𝑔𝑟𝑎𝑑(𝑣5 ) = 3
𝑔𝑟𝑎𝑑(𝑣2 ) = 3 , 𝑔𝑟𝑎𝑑(𝑣6 ) = 3
V2
𝑔𝑟𝑎𝑑(𝑣3 ) = 1 , ∑𝑣∈𝑉 𝑔𝑟𝑎𝑑(𝑣) = 14 = 2|𝐸| = 2(7) V1 V3
𝑔𝑟𝑎𝑑(𝑣4 ) = 2 ,
4.1.7. Matriz de adyacencia de un grafo
Sea G = (V, A), un grafo de n-vértices, la matriz de adyacencia de G es la matriz de orden 𝑛𝑥𝑛 con
entradas 𝐴 = 𝑎𝑖𝑗 donde.
𝒂𝒊𝒋 = 𝟏, 𝒔𝒊 {𝒊, 𝒋} ∈ 𝑮
{
𝒂𝒊𝒋 = 𝟎, 𝒆𝒏 𝒄𝒖𝒂𝒍𝒒𝒖𝒊𝒆𝒓 𝒐𝒕𝒓𝒐 𝒄𝒂𝒔𝒐

Las matrices de adyacencia nos indican la relación que tiene un vértice con otro.
En donde para poder armarla se empiezan a colocar los nodos o vértices como columnas y filas.
Ejemplo
Sea el grafo que se muestra en la siguiente figura
V4
V3 V5
V1 V6
V2
V1 V2 V3 V4 V5 V6
V1 0 1 1 0 0 0
V2 1 0 1 1 0 0
V3 1 1 0 1 0 0
V4 0 1 1 0 1 0
V5 0 0 0 1 0 1
V6 0 0 0 0 1 0
0 1 1 0 0 0
1 0 1 1 0 0
1 1 0 1 0 0
La matriz adyacente del grafo es A= 0 1 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
4.2. Relación de congruencia modulo
Sea 𝑚 un entero positivo, 𝑚 > 1, la relación 𝑅 = {(𝑎, 𝑏)/𝑎 ≅ 𝑏(𝑚𝑜𝑑(𝑚)} se denomina relación
de equivalencia modulo, la cual se define por.
𝑎−𝑏
𝑎 ≅ 𝑏(𝑚𝑜𝑑(𝑚) ↔ = 𝑘, 𝑘 𝑒𝑛𝑡𝑒𝑟𝑜
𝑚
(𝑎𝑅𝑏 ↔ 𝑎 𝑦 𝑏 𝑑𝑎𝑛 𝑒𝑙 𝑚𝑖𝑠𝑚𝑜 𝑟𝑒𝑠𝑖𝑑𝑢𝑜 𝑟 𝑎𝑙 𝑠𝑒𝑟 𝑑𝑖𝑣𝑖𝑑𝑖𝑑𝑜𝑠 𝑒𝑛𝑡𝑟𝑒 𝑚) (Definición)
Es decir 𝑎 es congruente con 𝑏 modulo 𝑚 si solamente si 𝑎 − 𝑏 es múltiplo de 𝑚

4.3. Clases de equivalencia
Las clases de equivalencia en este caso, cada elemento a ∈ Z define la clase de equivalencia: [a]m =
{x ∈ Z : x ≡ a (mod m)} = {. . . , a – 2k, a − k, a, a + k, a + 2k, . . . } quedando Z dividido en m
clases de equivalencia correspondientes a los posibles m restos de dividir un número cualquiera
entre m : [0]m, [1]m, [2]m, . . . , [m − 2]m, [m − 1]m
Ejemplos.
9 ≡ 27 (mod 3) ⇒ [9]3 = [27]3 = [0]3 16 ≡ 21 (mod 5) ⇒ [16]5 = [21]5 = [1]5
Para m = 2 el conjunto Z queda dividido en las clases [0] y [1] que se corresponden con los
números pares y los impares respectivamente.
Ejemplo 1
Si 4 divide a 𝑧 − 𝑦, 𝑅 es la relación de congruencia mod(4).
Si 𝑅 es una relación de equivalencia determinar las clases de equivalencia [0] y [1] donde 𝑅: 𝑧 →
𝑧
Solución
Sea 𝑧 ≅ 𝑦(𝑚𝑜𝑑(4), 𝑧, 𝑦 ∈ 𝑍
𝑧 − 𝑦 = 4𝑘, 𝑘 𝑒𝑛𝑡𝑒𝑟𝑜 → 𝑧 = 𝑦 + 4𝑘
[0]: 𝑎 = 0 + 4𝑘
[0] = {… … . . −12, −8, −4, 0, 4,8, 12 … … … … . }
[1] = { } 𝑎 = 𝑏 + 4𝑘 𝑎 = 1 + 4𝑘
[1] = {… … . . , −7, −3, 1, 9,13 … … … … . }
Ejemplo
Demuestre que la congruencia de modulo 2 es una relación de equivalencia
Solucion
i) Es claro 𝑎 ≅ 𝑎(𝑚𝑜𝑑(2) por tanto R reflexiva
ii) si 𝑎 ≅ 𝑎(𝑚𝑜𝑑(2) entonces, por definición 𝑎 ≅ 𝑟(𝑚𝑜𝑑(2), 𝑏 ≅ 𝑟(𝑚𝑜𝑑(2) de tal manera
𝑏 ≅ 𝑎(𝑚𝑜𝑑(2). Por tanto R es simétrica.

iii) Si 𝑎 ≅ 𝑏(𝑚𝑜𝑑(2), 𝑏 ≅ 𝑐(𝑚𝑜𝑑(2), entonces 𝑎 ≅ 𝑟(𝑚𝑜𝑑(2), 𝑏 ≅ 𝑟(𝑚𝑜𝑑(2)
𝑐 ≅ 𝑟(𝑚𝑜𝑑(2), es decir los tres dan el mismo residuo al ser divididos entre dos. En consecuencia
𝑎 ≅ 𝑐(𝑚𝑜𝑑(2), congruencia de modulo 2.
Por lo tanto R es transitiva
En consecuencia la congruencia de módulo 2 es una relación de equivalencia
4.4. Trayectorias
4.4.1. Definiciones
Sean vértices V, W de un grafo G
Camino simple (o trayectoria).- Es una sucesión finita de aristas de V a W sin vértices repetidos.
Ciclo o circuito.-Es un camino de V a W sin aristas repetidas
Ciclo simple.-Es ciclo de V a W sin vértices repetidos, excepto por los vértices inicial y final que
son iguales.
Ejemplo
Sea la gráfica G (V, E)
Camino simple : 6,5,2,4
Ciclo: 2, 6, 5, 2, 4, 3, 2
Camino simple: 5, 6, 2, 5
4.4.2. Trayectorias y circuitos de EULER
Los problemas de graficas nos permiten establecer aplicaciones dentro del contexto real utilizando
las trayectorias, circuitos, donde se puede empezar en un determinado vértice y terminar no
necesariamente en el mismo vértice, por ejemplo la distancia más corta en un determinado circuito
o trayectoria. Para este tipo de casos consideramos las siguientes definiciones y teoremas.
4.4.3. Trayectoria de EULER
Es una trayectoria que incluye a cada una de las aristas solo una vez

4.4.4. Ciclo de EULER
Un ciclo de Euler es una trayectoria de Euler, que es a la vez un circuito
Ejemplo sean las graficas
Trayectoria de Euler: A, B, C, D, E, B Circuito de Euler: 5, 3, 1, 2, 3, 4, 5
4.4.5. Teorema
a) Si una gráfica G tiene un vértice de grado impar, entonces no puede existir un circuito de Euler
en G.
b) Si G es una gráfica conexa y todos sus vértices tienen grado par, entonces existe un circuito de
Euler en G
4.4.6. Teorema 2
a) Si una gráfica G tiene más de dos vértices de grado impar, entonces no puede existir una
trayectoria de Euler en G.
b) Si G es una gráfica conexa y tiene exactamente dos vértices grado impar, entonces existe una
trayectoria de Euler en G
Ejemplos
1.- En la siguiente figura existe una trayectoria de Euler, ya que tiene dos vértices de grado impar.
Trayectoria de Euler: A, B, D, A, C, D, E, G, D, F, G
2.- En la siguiente figura existe un circuito de Euler, ya que el grado es par en todos los vértices.

Circuito de Euler: 𝑉1 , 𝑉2 , 𝑉3 , 𝑉4 , 𝑉6 , 𝑉7 , 𝑉5 , 𝑉3 , 𝑉7 , 𝑉6 , 𝑉1 , 𝑉4 , 𝑉2 , 𝑉1
Isomorfismos de graficas
Definición 1.- Las gráficas isomorfas son aquellas que tienen forma diferente, pero representas las
mismas gráficas.
Definición 2.-Las graficas 𝐺1 y 𝐺2 son isomorfas si existe una función biyectiva f de los vértices
de 𝐺1 a los vértices de 𝐺2 y una función biyectiva g de las aristas de 𝐺1 a las aristas de 𝐺2 . De
manera que una arista 𝑒 es incidente en V y W en 𝐺1 si y solo si la arista g(e) es incidente en f(v) y
f(w) en 𝐺2 .
El par de funciones f y g es un isomorfismo de 𝐺1 sobre 𝐺2
Sean las siguientes graficas 𝐺1 y 𝐺2 mostrada en la siguiente figura

Capitulo 5
5.1. Arboles
Definición.-Un árbol es un grafo no dirigido, conexo y sin ciclos. Puesto que un árbol no puede
contener ciclos, es un grafo acíclico, tampoco puede tener bucles o aristas múltiples. Por lo tanto,
un árbol es necesariamente un grafo simple.
Ejemplo
Sea 𝐺 = (𝑉, 𝐸) un grafo no dirigido, sin lazos como se muestra en la figura
Donde 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ} y 𝐸 = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 }

5.2. Teorema.- Sea G un grafo con n vértices, entonces las siguientes afirmaciones son
equivalentes:
i. G es un árbol.
ii. G tiene n-1 arcos y es conexo.
iii. G tiene n-1 arcos y no tiene ciclos.
Definición. Un bosque es un grafo en el cual cada componente conexa es un árbol.
5.3.Subárbol
Definición.- Sea G = (V, E) 𝑦 𝐺1 = (𝑉1 , 𝐸1 ) dos árboles, se dice que 𝐺1 es subárbol de 𝐺 si y solo
si 𝑉1 ⊆ 𝑉, 𝐸1 ⊆ 𝐸.

Ejemplo
Árbol G Subárbol de G
5.4.Árbol con raíz
Un árbol con raíz es un árbol en el que un vértice específico se designa como raíz.
Ejemplo
Sea el árbol mostrado siguiente figura donde la raíz será el vértice 𝑉1 = 𝑎

5.4.1. Definiciones
i) Altura de un árbol con raíz.- La altura de un árbol se define como la altura de la raíz.
La altura de un árbol determina la eficiencia de la mayoría de operaciones definidas sobre árboles.
ii) La profundidad de un nodo.- se define como la longitud del camino (único) que comienza en
la raíz y termina en el nodo. La profundidad de la raíz es cero, y la profundidad de un nodo se
puede calcular como la profundidad de su padre más uno.
iii) Nivel de un nodo.- A la profundidad de un nodo también se la denomina nivel del nodo en el
árbol.
Ejemplo.-sea el árbol que se muestra en la siguiente figura
Raíz
Nivel=1
Nivel=2
Vértice
Interno
Ancestro
Descendiente Hoja o
Padre Vértice terminal
Hijo
Altura=3+1

5.5.Arbol binario
Definicion.- Es un árbol con raíz en el que cada nodo tiene como

máximo dos hijos. Un árbol binario está formado por un nodo raíz y un subárbol izquierdo I y un
subárbol derecho D. Donde I y D son árboles binarios.
Ejemplo
5.6.Arbol binario completo
5.6.1.Definicion.-Es un arbol en el que cada nodo tiene 0 o dos hijos
Ejemplo
2
3
4
5 6 7
8 9

5.7.Árbol binario total
5.7.1.Definición.-Es un árbol en el que cada nodo tiene cero o dos hijos. Además se denomina
árbol binario total, a aquél que tiene presentes todas las hojas en el menor nivel. La raíz es de nivel
cero, los hijos de la raíz están en nivel 1; y así sucesivamente.
Deduciremos, de manera inductiva la altura de las hojas en función del número de nodos. El caso
más simple de un árbol completo tiene tres nodos, un nivel y altura dos. Hemos modificado
levemente la definición de altura, como el número de nodos que deben ser revisados desde la raíz a
las hojas, ya que la complejidad de los algoritmos dependerá de esta variable.
Árbol de nivel 1.
Nodos = 3 = 22 -1
Altura = 2
Árbol completo de nivel 1

Árbol de nivel 2.
Nodos = 7 = 23 -1
Altura = 3

Árbol de nivel 3.
Nodos = 15 = 24 -1
Altura = 4

Se deduce para un árbol de m niveles:
Árbol de nivel m.
Nodos = n = 2h -1
Altura = h = m+1
Hojas = 2m
Nodos internos = n – Hojas

5.8.Árbol ponderado.
5.8.1. Definición.-Es aquel que a cada arista se le asigna un número llamado peso.
Ejemplo
Arbol binario completo etiquetado
0 A
1
B
0 C
1 1
0
D
E
F G
5.9. Códigos prefijos
5.9.1. Definición.- Un conjunto P de sucesiones binarias (que representa un conjunto de símbolos)

es un código prefijo si ninguna de las sucesiones de p es el prefijo de otra sucesión de P
Ejemplos
1.-Sea el conjunto 𝐸 = {000, 001, 011, 10, 11} es un código prefijo
2.- Sea el conjunto 𝐹 = {1, 00, 01, 000, 0001} no es un código prefijo
3.-Consideremos un subconjunto del alfabeto 𝑆 = {𝑎, 𝑒, 𝑛, 𝑟, 𝑡} y representemos los elementos de S

mediante las siguientes sucesiones binarias.
𝑎: 01 𝑒: 0 𝑛: 101 𝑟: 10 𝑡: 1
Si transmitimos el mensaje “ata” se enviara la sucesión binaria 01101 pero también se puede
transmitir los mensajes con esta sucesión 𝒆𝒕𝒏, 𝒂𝒕𝒆𝒕, 𝒂𝒏 en consecuencia no es código prefijo
Si consideramos un segundo esquema de codificación

𝑎: 111 𝑒: 0 𝑛: 1100 𝑟: 1101 𝑡: 10 , ahora si transmitimos el mensaje “ata” se enviara la
sucesión binaria 11110111 donde no hay posibilidades de confusión, en consecuencia es un código
prefijo

Además podemos usar el árbol binario completo etiquetado para decodificar la sucesión 11110111
de la siguiente forma.
Raiz
0
1
𝑒: 0 0 1
𝑡: 100 1
0
𝑎: 111
1
0
𝑛: 1100
𝑟: 1101
5.9.2.Codificación de Huffman
Es una técnica para comprensión de datos. Este algoritmo le asigna secuencias binarias (códigos) a
los símbolos del alfabeto de manera de utilizar la menor cantidad de bits posibles
La idea del algoritmo del algoritmo de Huffman es que los datos a ser comprimidos, contienen
símbolos que aparecen con mayor frecuencia y otros muy poco, asignándoles el código mas corto a
los que más aparecen.
A continuación los pasos a seguir
Paso 1.
Se coloca los caracteres en orden creciente de acuerdo a la frecuencia de repetición
Paso 2.
Fusionar los nodos de menor frecuencia hasta obtener un solo árbol manteniendo el ordenamiento
creciente
Paso 3.
En el árbol obtenido en el paso 2 las hojas representan los símbolos o caracteres, los caminos o
trayectorias de la raíz a las hojas se codifica con 0 a la izquierda y con 1 a la derecha
Paso 4.
Finalmente de árbol se obtiene el código prefijo

Ejemplo
Supongamos que en un cierto archivo con 100 000 caracteres, donde aparecen 6 caracteres
diferentes y la frecuencia de aparición de cada uno de ellos es la siguiente
a b c d e f
Frecuencia 45 13 12 16 9 5
( en miles )
Solución
Fase 1. : Caracteres colocados en orden creciente de frecuencia.
f:5 e:9 c:12 b:13 d:16 a:45

Fase 2. y posteriores : Fusionar hasta obtener un sólo árbol
Manteniendo la ordenación creciente.
c:12 b:13 14 d:16

0 1
f:5 e:9
14 d:16 25 a:45
0 1 0 1
f:5 e:9 c:12 b:13

25
30
0 1
0 1
c:12 b:13
14 d:16
0 1
f:5 e:9
a:45 55
0 1
25 30
0 1 0 1
c:12 b:13 14 d:16
0 1
f:5 e:9

0 100 1
a:45 55
0 1
25 30
0 1 0 1
c:12 b:13 14 d:16
0 1
f:5 e:9
Dado finalmente el árbol binario ponderado podemos codificar y decodificar
Codificación: Basta con concatenar el código de cada uno de los caracteres.
Ejemplo : aabacd  001010100111 001010100111
Descodificación: ningún código es prefijo de otro código
Ejemplo :101011101111011100  badadcf
5.10.Árboles generadores
Un árbol generador de un grafo G (también llamado árbol recubridor o árbol expandido), es un

subgrafo de G que es árbol y contiene a todos los vértices de G.
G T F
Un grafo G, un árbol T generador de G

5.11.Árbol de expansión mínimo (recubridor)
Dado un grafo 𝐺 = (𝑉, 𝐸), no dirigido ponderado. Un árbol de expansión mínima es un árbol
compuesto por todos los vértices y cuya suma de los pesos las aristas sea mínimo. El árbol
generador mínimo de un grafo, no necesariamente es único.
Ejemplo 1
Para el grafo G de la siguiente figura existen dos árboles generadores mínimos T1 y T2:
G T1 T2
1 1 1
2 2 2
5 3 3 5 3 5 3
4
6
Un grafo ponderado G y dos árboles generadores mínimos de G (T1 y T2)
Ejemplo 2
Una compañía de teléfonos móviles da servicio a ciertas áreas geográficas, considerando la

distancia en kilómetros. Dichas áreas se representan por el siguiente grafo.
B
6
D
5
20
7
30
E
A
20 C 8
50 F
15 10
40
16
16
G 12
H
Determinar cuál sería la ruta del mensaje óptimo

El árbol de expansión mínima que me indica la ruta del mensaje óptimo se muestra en la siguiente
figura.
6
D
5
E
A
C 8
F
15 10
G 12
H
Los algoritmos que permiten hallar un árbol de expansión mínima son el algoritmo de PRIM y el
algoritmo de KRUSKAL
5.13. Algoritmo de PRIM
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol
recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos
los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es
conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes
conexos que forman dicho grafo no conexo.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera
independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra
en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al

que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto
significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya
pertenecen al árbol. El árbol recubridor mínimo está completamente construido cuando no quedan
más vértices por agregar.

Descripción detallada del algoritmo
Sea un grafo 𝐺 = (𝑉, 𝐴) ponderado donde se va ir construyendo sucesivamente conjunto de vértices

𝑉0 , 𝑉1 , 𝑉2 … … … … ⊆ 𝑉 y de aristas 𝐴0 , 𝐴1 , 𝐴2 … … … … ⊆ 𝐴, siguiendo los siguientes pasos.
Paso 1.- Se elige un vértice 𝑣 de G y formamos 𝑉0= {𝑣}, donde en este paso el conjunto de aristas
𝐴0 = 𝜙 .
Paso 2.-Se examina todas las aristas que tienen a 𝑣 como uno de sus extremos y de entre ellas
seleccionamos la que tenga un peso menor. Consideremos la arista 𝑎 y sea el vértice 𝑤 su otro
extremo de la arista donde se forman los conjuntos 𝑉1 = {𝑣, 𝑤} y 𝐴1 = {𝑎}
Paso 3.- Repetimos el paso 2 hasta construir los conjuntos 𝑉𝑖−1 con 𝑖-vertives y 𝐴𝑖−1 con 𝑖 − 1 aristas
Paso 4.-Finalmente si en el paso 𝑡 no se puede encontrar una arista para continuar el procedimiento
el algoritmo acaba y la salida es el grafo 𝐺𝑡 = (𝑉𝑡−1 , 𝐴𝑡−1 ).
Ejemplo 1
La siguiente figura muestra cómo se construye, paso a paso, un árbol generador mínimo aplicando el
algoritmo.
Construcción de un árbol generador mínimo (algoritmo de Prim)
Ejemplo 2
Consideremos que el grafo que se muestra en la figura representa un pequeño distrito, que no
cuenta con agua potable donde los vértices 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹 representas las viviendas y las aristas
representan la separación entre las viviendas medida en kilómetros
A
1 6
2
B
C
3 2
5
D
1 E
2
4
Determine la ruta que tenga el mínimo costo de habilitación de agua potable para el distrito
Construyendo la ruta de mínimo costo de habilitación se obtendrá el siguiente árbol que se muestra
en la siguiente figura, donde se observa que es de 8 kilómetros.
A
1
C
B
2
E
D
1
2 F
5.14. Algoritmo de KRUSKAL
El algoritmo de Kruskal consiste en la obtención de un árbol cuyas aristas al ser sumados sus pesos
el valor obtenido es el mínimo, tomando el nombre de algoritmo voraz. El algoritmo está basado en
una propiedad de los árboles que permite estar seguros de sí un arco debe pertenecer al árbol o no, y
usar esta propiedad para seleccionar cada arco. Se debe tener en cuenta en el algoritmo que siempre
que se añade una arista, ésta será siempre la conexión más corta (menor peso) alcanzable desde el
nodo que se parte al resto del grafo.

Descripción detallada del algoritmo
Paso 1.- Seleccionar el arco o arista de menor valor
Paso 2.- Seleccionar la arista con menor valor de toda la red incluyendo los nodos que la conforman
Paso 3.- Los dos pasos anteriores se lo debe hacer con todo el grafo y cuando se empiezan a formar
ciclos, estos se deben eliminar.
Paso 4.-El algoritmo finalizara cuando todos los arcos o aristas estén conectados
Ejemplo 1
La siguiente figura muestra cómo se construye, paso a paso, un árbol generador mínimo aplicando el
algoritmo. Nótese que antes de añadir la última arista, de peso 6, se encuentra una arista de entre las
no incorporadas hasta el momento de peso 5; sin embargo, esta arista no se añade debido a que forma
un ciclo con dos aristas incorporadas previamente (concretamente con las dos aristas cuyos pesos son
4 y 2, respectivamente).

Ejemplo 2
Sea el grafo que se muestra en la siguiente figura.
Figura 1. Grafo G
1.-Seleccionar el arco o arista de menor valor
Figura 2. Selección de arco o arista de menor valor

2.-Seleccionar la arista con menor valor de toda la red incluyendo los nodos que la conforman
Figura 3. Selección de nodos unidos por la arista
3.-Los dos pasos anteriores se lo debe hacer con todo el grafo y cuando se empiezan a formar
ciclos, estos se deben eliminar
Figura 4. Eliminar ciclos

En este caso se han generado dos soluciones como se observa a continuación
Solución 1
Figura 5. Solución 1 Algoritmo Kruskal
Solución 2
Figura 6. Solución 2 Algoritmo Kruskal

Se deben sumar el valor de las aristas de las dos soluciones encontradas Solución 1
Figura 7. Suma de aristas
Solución 2
Figura 8. Suma de aristas
En este caso se encontraron 2 soluciones óptimas del algoritmo de Kruskal.

5.14.1Diferencias de los algoritmos PRIM y KRUSKAL
1.-El algoritmo PRIM va creando un árbol en todo el proceso de las iteraciones, en cambio el
algoritmo de KRUSKAL, crea uno o varios árboles en cada iteración, en ambos casos finaliza
con solo árbol de expansión mínima.
2.-El algoritmo de PRIM inicia desde un vértice cualesquiera, en cambio el algoritmo de

KRUSKAL, se inicia desde el arco o arista de menor peso.
3.-Las soluciones halladas en ambos algoritmos son óptimas e iguales.
4.- En ambos casos se pueden generar más de un árbol de expansión mínima. En el caso de que
todos los pesos fueran diferentes se genera como solución un único árbol de expansión
mínima. Pero si hubiera al menos dos aristas o arcos con pesos iguales existe la posibilidad
de generar dos soluciones óptimas, es decir dos árboles de expansión mínima.

Capítulo 6
6.1. Algebra de Boole
En 1847, George Boole desarrolla el álgebra, que lleva su nombre, como un análisis matemático.
Su objetivo era describir las operaciones mentales mediante las cuales se realizan razonamientos.
Desarrollo un método sistemático para resolver problemas de lógica en su obra las leyes del
pensamiento.
Propuso un sistema o esquema para la expresión simplificada de problemas lógicos a través de

dos estados (falso o verdadero) mediante un procedimiento matemático. A esta estructura se le
denomina algebra booleana.
El sistema ideado por Boole se utilizó símbolos para el desarrollo de las operaciones lógicas
El álgebra de Boole es una estructura algebraica consistente de un conjunto B, de dos elementos,

y dos operaciones binarias; tales que se cumplen los axiomas de clausura, conmutatividad,
asociatividad, distributividad, identidad y complementariedad.
6.1.1. Definición.- El álgebra de Boole es un sistema algebraico cerrado que contiene un

conjunto B de dos elementos, {0, 1}; y dos operadores {·, +}. Los operadores también suelen
representarse según: {AND, OR}. Además se considera la operación lógica negación {𝑛𝑜𝑡}
considerado el complemento.
La clausura implica que si a y b pertenecen a B, entonces: a·b y a+b también pertenecen a B.
6.1.2. Postulados o axiomas
B: Se le denomina conjunto booleano formado por los elementos 0, y 1.
𝑨𝟏 .-Elementos únicos
Existen elementos únicos (0 y 1) en B tal que para cada a en B se tienen:
a+0=a
a. 1 = a

𝑨𝟐 .-Conmutatividad
Si a y b pertenecen a B:
a+b=b+a
a. b = b. a
𝑨𝟑 .-Asociatividad
Si a, b y c pertenecen a B:
a + (b + c) = (a + b) + c
a. (b. c) = (a. b). c
𝑨𝟒 .-Distributividad
Si a, b y c pertenecen a B:
a + (b. c) = (a + b)(a + c)
a. (b + c) = (a. b) + (a. c)
Nótese que en la distribución para la suma en el producto, la expresión a la derecha es diferente

de la empleada habitualmente para números reales y enteros.
𝑨𝟒 .-Complementariedad
Si a pertenece a B, existe complemento único de a que se representa por 𝑎 ! y también por 𝒂

̅
a + 𝑎̅ = 1
a. 𝑎̅ = 0
𝑨𝟓 .-Igualdad
Dos expresiones son iguales si una puede ser substituida por la otra.
6.1.3. Teorema complemento de 1
Sea el conjunto booleano B, si 1 ∈ 𝐵 entonces el complemento de 1 es cero
1̅ = 0

6.1.4. Teorema complemento de 0
Sea el conjunto booleano B, si 0 ∈ 𝐵 entonces el complemento de 0 es uno
0̅ = 1
6.1.5. Teorema de evolución
Sea el conjunto booleano B, si 𝑎 ∈ 𝐵 entonces
𝑎̿ = 𝑎
6.1.6. Teorema de idempotencia
Si a es un elemento del conjunto booleano B entonces
a+a=a
a. a = a
Demostración
Usando los axiomas mencionados tenemos
𝑎 = 𝑎 + 0 = 𝑎 + (𝑎. 𝑎̅) = (𝑎 + 𝑎)(𝑎 + 𝑎̅)𝑎 𝑎 = 𝑎(1) = 𝑎(𝑎 + 𝑎̅) = 𝑎. 𝑎 + 𝑎. 𝑎̅

= (𝑎 + 𝑎)(1) = (𝑎 + 𝑎) = 𝑎. 𝑎 + 0 = 𝑎. 𝑎
6.1.7. Teorema
Si a es un elemento del conjunto booleano B entonces
a+1=1
a. 0 = 0
Demostración
𝑎 + 1 = 𝑎 + 𝑎 + 𝑎̅ = 𝑎 + 𝑎̅ = 1 𝑎. 0 = 𝑎(𝑎. 𝑎̅) = (𝑎. 𝑎). 𝑎̅ = 𝑎. 𝑎̅ = 0

6.1.8. Teorema de absorción
Si a y b elementos del conjunto booleano B entonces
a + a. b = a
a. (a + b) = a
Demostración
𝑎 + 𝑎. 𝑏 = 𝑎. 1 + 𝑎. 𝑏 = 𝑎(1 + 𝑏) = 𝑎. 1 𝑎. (𝑎 + 𝑏) = 𝑎. 𝑎 + 𝑎. 𝑏 = 𝑎
=𝑎
6.1.9. Teorema de Morgan
̅̅̅̅̅̅̅
𝑎 + 𝑏 = 𝑎. ̅ 𝑏̅
̅̅̅ = 𝑎̅ + 𝑏̅
𝑎𝑏
Demostración
̅̅̅ = 𝑎̅ + 𝑏̅
i) 𝑎𝑏
Si 𝑎. 𝑏 ∈ 𝐵, entonces tiene complemento único, por lo tanto
̅̅̅ = 1
𝑎𝑏 + 𝑎𝑏 ̅̅̅̅̅ = 0
(𝑎𝑏). (𝑎𝑏) (*)
Por otro lado
(𝑎𝑏)(𝑎̅ + 𝑏̅) = 𝑎. 𝑏. 𝑎̅ + 𝑎. 𝑏. 𝑏̅ = 𝑎. 𝑎̅. 𝑏 + 𝑎. 0 = 0 (**)
(𝑎𝑏) + (𝑎̅ + 𝑏̅) = (𝑎̅ + 𝑏̅) + (𝑎𝑏) = ((𝑎̅ + 𝑏̅) + 𝑎) ((𝑎̅ + 𝑏̅) + 𝑏)
(𝑎 + 𝑎̅ + 𝑏̅)(𝑎̅ + 𝑏̅ + 𝑏) = (1 + 𝑏̅)(1 + 𝑎̅) = (1)(1) = 1 (***)

Ahora de (*), (**), y (***) tenemos.
̅̅̅̅̅ = (𝑎𝑏)(𝑎̅ + 𝑏̅)

(𝑎𝑏). (𝑎𝑏)
̅̅̅ = (𝑎𝑏) + (𝑎̅ + 𝑏̅)

𝑎𝑏 + 𝑎𝑏
Por lo tanto concluimos que ̅̅̅

𝑎𝑏 = 𝑎̅ + 𝑏̅
ii) ̅̅̅̅̅̅̅ ̅ 𝑏̅
𝑎 + 𝑏 = 𝑎.
Si (𝑎 + 𝑏) ∈ 𝐵, entonces tiene complemento único, por lo tanto
(𝑎 + 𝑏) + ̅̅̅̅̅̅̅
𝑎+𝑏 =1 ̅̅̅̅̅̅̅̅
(𝑎 + 𝑏). (𝑎 + 𝑏) = 0 (*)
Por otro lado
(𝑎 + 𝑏) + (𝑎̅. 𝑏̅) = (𝑎 + 𝑏 + 𝑎̅) + (𝑎 + 𝑏 + 𝑏̅ ) = (𝑏 + 1) + (𝑎 + 1) = 1 (**)
(𝑎 + 𝑏)(𝑎̅. 𝑏̅) = (𝑎̅ + 𝑏̅) + (𝑎𝑏) = (𝑎. 𝑎̅. 𝑏̅) + (𝑏. 𝑎̅. 𝑏̅) = 0 (***)
Ahora de (*), (**), y (***) tenemos.
̅̅̅̅̅̅̅
(𝑎 + 𝑏) + 𝑎 + 𝑏 = (𝑎 + 𝑏) + (𝑎̅. 𝑏̅)
̅̅̅̅̅̅̅̅
(𝑎 + 𝑏). (𝑎 + 𝑏) = (𝑎 + 𝑏)(𝑎̅. 𝑏̅)
Por lo tanto concluimos que ̅̅̅̅̅̅̅ ̅ 𝑏̅

𝑎 + 𝑏 = 𝑎.
A continuación veremos que el uso de tablas de verdad permite corroborar la demostración de los
teoremas del algebra de Boole.
Por ejemplo el teorema de Morgan
̅̅̅̅̅̅̅
𝑎 + 𝑏 = 𝑎.̅ 𝑏̅
̅̅̅
𝑎𝑏 = 𝑎̅ + 𝑏̅
Consideremos los valores de la tabla de verdad para 𝑎 𝑦 𝑏 codificados por:

a b
0 0
0 1
1 0
1 1
Ahora mostraremos la prueba del teorema en las siguientes tablas.
a b 𝑎̅ 𝑏̅ ̅̅̅
𝑎𝑏 𝑎̅ + 𝑏̅ a b 𝑎̅ 𝑏̅ ̅̅̅̅̅̅̅
𝑎+𝑏 𝑎̅. 𝑏̅
0 0 1 1 1 1 0 0 1 1 1 1
0 1 1 0 1 1 0 1 1 0 0 0
1 0 0 1 1 1 1 0 0 1 0 0
1 1 0 0 0 0 1 1 0 0 0 0
6.2. Definiciones
6.2.1. Variable booleana.-Una variable lógica o booleana es un elemento de conjunto booleano

B
es decir 𝑎 ∈ 𝐵 que puede tomar 0 o 1.
6.2.2. Función booleana
La función booleana de se define por:
𝑓: 𝐵 𝑛 → 𝐵
Donde 𝑓(𝑎1 , 𝑎2 … … . . 𝑎𝑛 ) = 𝑏, 𝑐𝑜𝑛 (𝑎1 , 𝑎2 … … . . 𝑎𝑛 ) ∈ 𝐵 𝑛 , 𝑏 ∈ 𝐵
La función puede definirse de manera que dando los valores de verdad toma cada posible
combinación de entradas. Esta representación se llama tabla de verdad.
Ejemplo

Sea la función 𝑓: 𝐵 3 → 𝐵
Definida por 𝑓(𝑎, 𝑏, 𝑐) = 𝑐(𝑎 + 𝑏)
a b b 𝑓(𝑎, 𝑏, 𝑐) = 𝑐(𝑎 + 𝑏)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
6.3. Operaciones lógicas
6.3.1. Suma lógica: (OR)≡ 𝑂 ≡ (∨)
0 , 𝑠𝑖 𝑎 = 0 , 𝑏 = 0
𝑓(𝑎, 𝑏) = 𝑎 + 𝑏 = {
1 , 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
6.3.2. Producto lógico: (AND)≡ 𝑌 ≡ (∧)
1 , 𝑠𝑖 𝑎 = 1 , 𝑏 = 1
𝑓(𝑎, 𝑏) = 𝑎𝑏 = {
0 , 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Negación: (NOT)≡ (∼)
Sea la función 𝑓: 𝐵 → 𝐵
1 , 𝑠𝑖 𝑎 = 1
𝑓(𝑎) = 𝑎̅ = {
0 , 𝑠𝑖 𝑎 = 0
Ilustración de las operaciones lógicas suma y producto en una tabla de verdad

Suma Producto
a b 𝑓(𝑎, 𝑏) = 𝑎 + 𝑏 a b 𝑓(𝑎, 𝑏) = 𝑎𝑏
0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1
6.4. Funciones booleanas a partir de tablas de verdad
Para describir una función booleana donde nos proporcionan los valores de salida parta todas las
combinaciones de las entradas es necesario los postulados y teoremas del algebra de Boole.
Ejemplo
Determinar la función booleana a partir de siguiente tabla de verdad
a b 𝑓(𝑎, 𝑏)
0 0 0
0 1 1
1 0 1
1 1 0
La función booleana estará dado por la siguiente regla de correspondencia
𝑓(𝑎, 𝑏) = 𝑎̅. 𝑏 + 𝑎. 𝑏̅
6.4.1. Principio de dualidad
Si analizamos los postulados veremos que los mismos se presentan de a pares y en tal forma que
uno de la pareja se obtiene de otro cambiando "0" por "1" junto con las operaciones "+" por "."
( y viceversa). Esto asegura que cada propiedad que se demuestre en esta Álgebra tiene una

"dual" que también es cierta (para demostrar la dual bastaría con repetir la demostración realizada
sustituyendo cada postulado o propiedad utilizada por su dual).
Ejemplos
Postulado Dualidad
𝑎 + 𝑎̅=1 𝑎. 𝑎̅ = 0
a.0=0 𝑎+1=1
0+0=0 1.1=1
6.4.2. Termino producto
Es un grupo de expresiones que se encuentran relacionadas entre sí, por el termino AND que
indica producto (.).
Ejemplo
𝐴. 𝐵, 𝐶. 𝐴, 𝑥̅ . 𝑦. 𝑧
6.4.3. Termino suma
Es un grupo de expresiones que se encuentran relacionadas entre sí, por el termino OR que indica
suma (+).
Ejemplo
𝐴 + 𝐵, 𝐶 + 𝐴, 𝑥̅ . 𝑦 + 𝑦𝑧
6.4.4. Termino canónico
Es aquel término que es exactamente uno de cada uno de los literales o expresiones de las
funciones booleanas.
6.4.5.Termino normal
Termino normal es aquel termino producto o termino suma en el que un literal no aparece más
de una vez.

6.4.6. Mintérmino
Es un producto booleano en la que cada variable aparece sólo una vez; es decir, es una expresión
lógica que se compone de variables y los operadores lógicos AND y NOT.
Ejemplo
X.Y.Z y 𝑋. 𝑌̅. 𝑍
6.4.7. Maxtérmino
Es una expresión lógica que se compone de variables y los operadores lógicos OR y NOT.
Ejemplo
X+Y+Z y 𝑋 + 𝑌̅ + 𝑍
6.4.8. Forma normal de una función booleana
Es aquella forma que está constituida por términos normales, puede estar en la forma suma de
términos producto o producto de términos suma.
Ejemplo
i) 𝑓(𝑥, 𝑦, 𝑧) = 𝑥̅ . 𝑦. 𝑧 + 𝑥̅ . 𝑦. 𝑧̅
ii) 𝑓(𝑥, 𝑦, 𝑧) = (𝑥̅ + 𝑦 + 𝑧) + (𝑥 + 𝑦̅ + 𝑧̅)
6.4.9. Forma canónica de una función booleana
Es aquella forma constituida exclusivamente por términos canónicos que aparecen una sola vez.
Ejemplo
𝑓(𝑥, 𝑦, 𝑧) = 𝑥̅ . 𝑦. 𝑧̅ + (𝑥̅ + 𝑦 + 𝑧) + (𝑥̅ + 𝑦̅ + 𝑧̅)

6.5. Formas canónicas de funciones booleanas
a) Forma canónica suma de productos: (forma suma de minterminos)
Es aquella constituida exclusivamente por términos canónicos producto (mintermino) sumandos

que aparecen una sola vez.
Ejemplo
𝑓(𝑥, 𝑦, 𝑧) = (𝑥̅ . 𝑦̅. 𝑧) + (𝑥. 𝑦̅. 𝑧̅) + (𝑥. 𝑦̅. 𝑧) + (𝑥. 𝑦. 𝑧̅) + (𝑥. 𝑦. 𝑧)
Simplificaron de la escritura forma canónica suma de productos
Para simplificar la escritura en forma de suma canónica de productos, se utiliza la notación

binaria, es decir que a cada termino (mintermino) se le asocia un numero binario de “n” bits,
considerando como 0 las variables complementarias y 1 a las variables no complementarias.
Consideremos el ejemplo anterior
Mintermino Binario Decimal

(𝑥̅ . 𝑦̅. 𝑧) 001 1
(𝑥. 𝑦̅. 𝑧̅) 100 4
(𝑥. 𝑦̅. 𝑧) 101 5
(𝑥. 𝑦. 𝑧̅) 110 6
(𝑥. 𝑦. 𝑧) 111 7
Donde se puede expresar de la siguiente forma
𝑓(𝑥, 𝑦, 𝑧) = ∑ (1,4,5,6,7)
𝑚
Quiere decir la suma de los minterminos 1,4,5,6,7.
b) Forma canónica de producto de sumas: (forma de productos maxterminos)

Es aquella constituida exclusivamente por términos canónicos sumas (maxtermino)
multiplicadas que aparecen una sola vez.
Ejemplo
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦 + 𝑧). (𝑥 + 𝑦̅ + 𝑧)(𝑥 + 𝑦̅ + 𝑧̅)
Simplificaron de la escritura forma canónica suma de productos
Para simplificar la escritura en forma de suma canónica de productos, se utiliza la notación

binaria, es decir que a cada termino (maxtermino) se le asocia un numero binario de “n” bits,
considerando como 1 las variables complementarias y 0 a las variables no complementarias.
Consideremos el ejemplo anterior
Maxtermino Binario Decimal

(𝑥 + 𝑦 + 𝑧) 000 0
(𝑥 + 𝑦̅ + 𝑧) 010 2
(𝑥 + 𝑦̅ + 𝑧̅) 011 3
Donde se puede expresar de la siguiente forma
𝑓(𝑥, 𝑦, 𝑧) = ∏ (0,2,3)
𝑀
Quiere decir el producto de los maxterminos 0,2,3.
Resumen para cada mintermino que se asocia con la combinación de entradas de la tabla de
verdad, la función producirá una salida de 1, y para maxtermino que se asocia con la combinación
de entradas de la tabla de verdad, la función producirá una salida de 0, a continuación se ilustrara
en la siguiente tabla.

Tabla de maxterminos y minterminos asociados con cada combinación en una tabla
de verdad de tres variables
Decimal x y z Mintermino 𝑚𝑖 Maxtermino 𝑀𝑖
0 0 0 0 𝑥.
̅ 𝑦.
̅ 𝑧̅ = 𝑚0 1 𝑥 + 𝑦 + 𝑧 = 𝑀0 0
1 0 0 1 𝑥.
̅ 𝑦.
̅ 𝑧 = 𝑚1 1 𝑥 + 𝑦 + 𝑧̅ = 𝑀1 0
2 0 1 0 𝑥.
̅ 𝑦. 𝑧̅ = 𝑚2 1 𝑥 + 𝑦̅ + 𝑧 = 𝑀2 0
3 0 1 1 𝑥.
̅ 𝑦. 𝑧 = 𝑚3 1 𝑥 + 𝑦̅ + 𝑧̅ = 𝑀3 0
4 1 0 0 𝑥. 𝑦.
̅ 𝑧̅ = 𝑚4 1 𝑥̅ + 𝑦 + 𝑧 = 𝑀4 0
5 1 0 1 𝑥. 𝑦.
̅ 𝑧 = 𝑚5 1 𝑥̅ + 𝑦 + 𝑧̅ = 𝑀5 0
6 1 1 0 𝑥. 𝑦. 𝑧̅ = 𝑚6 1 𝑥̅ + 𝑦̅ + 𝑧 = 𝑀6 0
7 1 1 1 𝑥. 𝑦. 𝑧 = 𝑚7 1 𝑥̅ + 𝑦̅ + 𝑧̅ = 𝑀7 0
Ejemplo 1.-Expresar la siguiente función como una suma de minterminos
𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧
Solución
Hay dos formas de resolver el problema
i) Establecer la tabla de verdad de la expresión, luego tomar los minterminos, es decir se evalúa
la función para todas las combinaciones de entrada, luego se toma los minterminos, para la cual
la función tiene como salida 1
Decimal x y z 𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧 Mintermino

0 0 0 0 0
1 0 0 1 1 𝑥.
̅ 𝑦.
̅ 𝑧 = 𝑚1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1 𝑥. 𝑦.
̅ 𝑧̅ = 𝑚4
5 1 0 1 1 𝑥. 𝑦.
̅ 𝑧 = 𝑚5
6 1 1 0 1 𝑥. 𝑦. 𝑧̅ = 𝑚6
7 1 1 1 1 𝑥. 𝑦. 𝑧 = 𝑚7

Luego la función expresada en suma de minterminos estará dada por
𝑓(𝑥, 𝑦, 𝑧) = 𝑥.
̅ 𝑦.
̅ 𝑧 + 𝑥. 𝑦.
̅ 𝑧̅ + 𝑥. 𝑦.
̅ 𝑧 + 𝑥. 𝑦. 𝑧̅ + 𝑥. 𝑦. 𝑧
En forma literal simplificada estará por
𝑓(𝑥, 𝑦, 𝑧) = ∑𝑚(1,4,5,6,7), que quiere decir la suma de los minterminos 1,4,5,6,7.
ii) Aplicando los teoremas de expansión canónica para las variables faltantes
6.6. Teorema
Para obtener la forma canónica de una función suma de productos (minterminos), se multiplica
por un término de la forma (𝑎 + 𝑎̅), donde falta un literal para que el término sea canónico.
En efecto
Si 𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧 entonces
̅ + 𝑦̅. 𝑧. (𝑥 + 𝑥̅ )
𝑓(𝑥, 𝑦, 𝑧) = 𝑥. (𝑦 + 𝑦̅). (𝑧 + 𝑧)
̅ + 𝑦̅. 𝑧. 𝑥 + 𝑦̅. 𝑧. 𝑥̅
𝑓(𝑥, 𝑦, 𝑧) = (𝑥. 𝑦 + 𝑥. 𝑦̅). (𝑧 + 𝑧)
𝑓(𝑥, 𝑦, 𝑧) = 𝑥. 𝑦. 𝑧 + 𝑥. 𝑦. 𝑧̅ + 𝑥. 𝑦̅. 𝑧 + 𝑥. 𝑦̅. 𝑧̅ + 𝑦̅. 𝑧. 𝑥 + 𝑦̅. 𝑧. 𝑥̅
Por tanto el resultado.
Ejemplo 2.-Expresar la siguiente función como una suma de maxterminos
𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧
Solución
De igual manera que el caso anterior hay dos formas de resolver el problema
i) Establecer la tabla de verdad de la expresión, luego tomar los maxterminos, es decir se evalúa
la función para todas las combinaciones de entrada, luego se toma los maxterminos, para la
cual la función tiene como salida 0

Decimal x y z 𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧 Maxtermino
0 0 0 0 0 𝑥 + 𝑦 + 𝑧 = 𝑀0
1 0 0 1 1
2 0 1 0 0 𝑥 + 𝑦̅ + 𝑧 = 𝑀2
3 0 1 1 0 𝑥 + 𝑦̅ + 𝑧̅ = 𝑀3
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 1
Luego la función expresada como producto de maxterminos estará dada por
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦 + 𝑧)( 𝑥 + 𝑦̅ + 𝑧)(𝑥 + 𝑦̅ + 𝑧̅)
En forma literal simplificada estará por
𝑓(𝑥, 𝑦, 𝑧) = ∏𝑀(0,2,3), que quiere decir el producto de los maxterminos, 0,2,3.
ii) Aplicando los teoremas de expansión canónica para las variables faltantes
6.7. Teorema
Para obtener la forma canónica de una función productos sumas (maxterminos), se suma un
término de la forma (𝑎. 𝑎̅), donde falta un literal para que el término sea canónico.
En efecto
Si 𝑓(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅. 𝑧 entonces
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦̅). (𝑥 + 𝑧)
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦̅ + 𝑧. 𝑧̅). (𝑥 + 𝑧 + 𝑦. 𝑦̅)
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦̅ + 𝑧)(𝑥 + 𝑦̅ + 𝑧̅). (𝑥 + 𝑧 + 𝑦)(𝑥 + 𝑧 + 𝑦̅)
𝑓(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦̅ + 𝑧)(𝑥 + 𝑦̅ + 𝑧̅). (𝑥 + 𝑧 + 𝑦)
Por tanto el resultado.

6.8. Puertas lógicas
Se ha definido anteriormente que una función lógica es una combinación de operaciones lógicas
aplicadas sobre variables que sólo pueden tomar valores 0 ó 1. Dichas variables pueden
representar el estado de un sistema tal como: apagado o encendido, funcionando o sin funcionar,
sí o no, etc. En cualquier caso, tomamos 1 como un estado cualquiera y 0 como el estado
contrario. Una puerta lógica es el dispositivo que realiza una determinada operación lógica
elemental.
La decisión tomada por una puerta lógica consiste en situar su salida en 0 ó en 1, dependiendo
del estado de sus entradas y de la función lógica para la cuál ha sido diseñada.
Dentro de la electrónica son dispositivos cuyo funcionamiento se basa en las operaciones lógicas
suma, producto y complementación (OR, AND, NOT). Los elementos básicos con los que se
construyen puertas lógicas son componentes semiconductores, como el diodo y el transistor.
Diodo.-Dispositivo electrónico de dos terminales (electrodos) por la que circula la corriente en

un solo sentido.
Transistor.-Pequeño dispositivo semiconductor que cierra o abre un circuito o amplifica una

señal, se emplea en circuitos integrales para generar bits (0, 1).
Principales puertas lógicas
a) Puerta OR (suma)
Comportamiento:
Si al menos una de sus entradas es uno, su salida será uno.

Si todas sus entradas son cero, su salida será cero.
Símbolo
a
Puerta dos 𝑓(𝑎, 𝑏) = 𝑎 + 𝑏
entradas b

Tabla de verdad
a b 𝑓(𝑎, 𝑏) = 𝑎 + 𝑏
0 0 0
0 1 1
1 0 1
1 1 1
b) Puerta AND (producto)
Comportamiento:
Si todas sus entradas son uno, su salida será uno.

Si al menos una de sus entradas es cero, su salida será cero.
Símbolo
a
Puerta dos 𝑓(𝑎, 𝑏) = 𝑎. 𝑏
entradas b
Tabla de verdad
a b 𝑓(𝑎, 𝑏) = 𝑎. 𝑏
0 0 0
0 1 0
1 0 0
1 1 1
c) Puerta NOT (inversor)
Comportamiento:
Si su entrada es cero, su salida será uno.

Si su entrada es uno, su salida será cero.

Símbolo
Puerta una a 𝑓(𝑎) = 𝑎̅

entrada
Tabla de verdad
a 𝑓(𝑎) = 𝑎̅
0 1
1 0
d) Puerta NORD (suma negada)
Comportamiento:
Si sus entradas son cero, su salida será uno.

Si al menos una de sus entradas es uno, su salida será cero.
Símbolo
a
Puerta dos 𝑓(𝑎, 𝑏) = ̅̅̅̅̅̅̅
𝑎+𝑏
entradas b
Tabla de verdad
a b 𝑓(𝑎, 𝑏) = ̅̅̅̅̅̅̅
𝑎+𝑏
0 0 1
0 1 0
1 0 0
1 1 0

e) puerta NAND (producto negado)
Comportamiento:
Si al menos una de sus entradas es cero, su salida será uno.

Si todas sus entradas son uno, su salida será cero.
Símbolo
a
̅̅̅
𝑓(𝑎, 𝑏) = 𝑎𝑏
Puerta dos
entradas b
Tabla de verdad
a b ̅̅̅
𝑓(𝑎, 𝑏) = 𝑎𝑏
0 0 1
0 1 1
1 0 1
1 1 0
f) Puerta XOR (suma exclusiva)
Comportamiento:
Si el número de entradas en alto es impar, la salida será alta. De otra manera será baja.
Símbolo
a
Puerta dos 𝑓(𝑎, 𝑏) = 𝑎̅𝑏 + 𝑎𝑏̅ = 𝑎 ⊕ 𝑏
entradas b

Tabla de verdad
a b 𝑓(𝑎, 𝑏) = 𝑎̅𝑏 + 𝑎𝑏̅ = 𝑎 ⊕ 𝑏
0 0 0
0 1 1
1 0 1
1 1 0
g) puerta XNOR (suma exclusiva negativa)
Comportamiento:
Si el número de entradas en alto es par, la salida será alta.

Si el número de entradas en alto es impar, la salida será baja.
Símbolo
a
̅̅̅̅̅̅ = (𝑎 + 𝑏̅)(𝑎̅ + 𝑏) = 𝑎 ⊙ 𝑏
𝑓(𝑎, 𝑏) = 𝑎⨁𝑏
Puerta dos
entradas b
Tabla de verdad
a b ̅̅̅̅̅̅ = (𝑎 + 𝑏̅)(𝑎̅ + 𝑏) = 𝑎 ⊙ 𝑏
𝑓(𝑎, 𝑏) = 𝑎⨁𝑏
0 0 1
0 1 0
1 0 0
1 1 1
Ejemplo 1
Determine la salida booleana del siguiente circuito y escribir una tabla de vedad para el mismo

Resolución
Escribiendo sobre el diagrama la salida de cada puerta lógica tenemos la función logica
𝑓(𝐴, 𝐵) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅
𝐴̅. 𝐵 + ̅̅̅̅̅
𝐴. 𝐵
Tabla de verdad
A B 𝑓(𝐴, 𝐵) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅
𝐴̅. 𝐵 + ̅̅̅̅̅
𝐴. 𝐵
0 0 0
0 1 0
1 0 0
1 1 1
Ejemplo 2.-Determine la salida booleana del siguiente circuito y escribir una tabla de vedad para
el mismo

Resolución
Escribiendo sobre el diagrama la salida de cada puerta lógica tenemos la función logica
𝑓(𝐴, 𝐵) = 𝐴. 𝐵̅ + ̅̅̅̅̅
𝐴̅. 𝐵 + ̅̅̅̅̅̅̅̅
𝐴+𝐵
Tabla de verdad
A B ̅̅̅̅̅
𝑓(𝐴, 𝐵) = 𝐴. 𝐵̅ + 𝐴 ̅. 𝐵 + ̅̅̅̅̅̅̅̅
𝐴+𝐵
0 0 1
0 1 0
1 0 1
1 1 1
6.9. Simplificación de funciones booleanas
La simplificación de funciones booleanas consiste en implementar una función con el menor

número de puertas lógicas posible. En múltiples ocasiones a la hora de aplicar el álgebra booleana, hay
que reducir una expresión a su forma más simple o cambiarla a una forma más conveniente que permita
conseguir una implementación eficiente.
Métodos de simplificación
a) Método algebraico o reducción algebraica
Este método consiste en la aplicación analítica de los axiomas y teoremas de algebra de Boole.

Ejemplo
Simplificar la siguiente función F(A, B, C) = AC + BC + A’C + A’B’
F = (A+A’) C + BC + A’B’ = 1.C + BC + A’B’ = C + BC + A’B’
F = C (1+B) + A’B’ = C.1 + A’B’
F (A, B, C) = A’B’+C
b) Método gráfico: Método del mapa de Karnaugh
Una función booleana expresada en forma algebraica puede aparecer de muchas formas
diferentes, sin embargo, la representación con una tabla de verdad es única. Se pueden utilizar
los postulados y teoremas booleanos para simplificar una función booleana expresada en forma
algebraica, pero no existe un mecanismo específico utilizando este método.
El método de mapas representa una forma simple y directa de minimizar las funciones booleanas
expresadas en su tabla de verdad. El mapa es un diagrama compuesto por cuadros, cada uno de
los cuales representa un minitérmino. La cantidad de celdas del mapa es 2𝑛 ; donde n representa
la cantidad de variables
Un mapa de Karnaugh es una representación gráfica de la tabla de verdad, donde la tabla de

verdad tiene un renglón por cada minitérmino. El mapa de Karnaugh tiene una celda por cada
minitérmino, a continuación veremos el método de acuerdo a la cantidad de variables de la
función booleana.
Mapa de karnaugh para dos variables
Sea f una función de dos variables 𝑓: 𝐵 2 → 𝐵, para este caso se forma un mapa de
22 = 4 , 𝑛 = 2 minterminos (celdas). Una forma más sencilla de representar el mintermino en

la celda es señalando su valor decimal.
A B Mintermino
0 0 𝐴̅. 𝐵̅ = 𝑚0
0 1 𝐴̅. 𝐵 = 𝑚1
1 0 𝐴. 𝐵̅ = 𝑚2
1 1 𝐴. 𝐵 = 𝑚3

Ejemplo
Simplificar la siguiente función 𝑓(𝑎, 𝑏) = ∑𝑚(0,1,3)
a b Mintermino
0 0 𝑎̅. 𝑏̅ = 𝑚0
0 1 𝑎. 𝑏 = 𝑚1
1 0
1 1 𝑎. 𝑏 = 𝑚3
i) Por el método algebraico de acuerdo a la tabla tendremos
𝑓(𝑎, 𝑏) = ∑ (0,1,3) = 𝑚0 + 𝑚1 + 𝑚3
𝑚
𝑓(𝑎, 𝑏) = 𝑚0 + 𝑚1 + 𝑚3 = 𝑎̅. 𝑏̅ + 𝑎̅. 𝑏 + 𝑎𝑏 = 𝑎̅. 𝑏̅ + 𝑏(𝑎̅ + 𝑎) = 𝑎̅. 𝑏̅ + 𝑏
𝑓(𝑎, 𝑏) = (𝑎̅ + 𝑏)(𝑏̅ + 𝑏) = (𝑎̅ + 𝑏), por tanto la función simplificada sera
𝑓(𝑎, 𝑏) = (𝑎̅ + 𝑏)
ii) Método de carnaugh
a 0 ≈ 𝑎̅ 1≈𝑎
b
0 ≈ 𝑏̅ 𝑚0 𝑚2
1 0
1≈𝑏 𝑚1 𝑚3
1 1

De acuerdo a la tabla se toma dos cuadros (rectangulo) o celdas adyacentes y acuerdo a la
codificación binaria, se considera la variable que no cambian de signo, y se aplica la definición
de mintermino, es decir será 0 cuando la variable es complementaria y 1 cuando no es
complementaria. Quedando la función simplificada de la siguiente forma
𝑓(𝑎, 𝑏) = (𝑎̅ + 𝑏)
Primer rectángulo Segundo rectángulo

00 01
01 11
𝑎̅ 𝑏
Mapa de karnaugh para tres variables
Sea f una función de tres variables 𝑓: 𝐵 3 → 𝐵, para este caso se forma un mapa de
23 = 8 , 𝑛 = 3 minterminos (celdas). Una forma más sencilla de representar el mintermino en

la celda es señalando su valor decimal.
Es importante colocar las variables en el orden indicado de más a menos significativo (𝐴, 𝐵, 𝐶),
ya que de otra forma el valor decimal será diferente.
A B C Mintermino
0 0 0 𝐴̅. 𝐵̅ . 𝐶̅
= 𝑚0
0 0 1 𝐴̅. 𝐵̅ . 𝐶
= 𝑚1
0 1 0 𝐴̅. 𝐵. 𝐶̅
= 𝑚2
0 1 1 𝐴̅. 𝐵. 𝐶
= 𝑚3
1 0 0 𝐴. 𝐵̅ . 𝐶̅
= 𝑚4

1 0 1 𝐴. 𝐵̅ . 𝐶
= 𝑚5
1 1 0 𝐴. 𝐵. 𝐶̅
= 𝑚6
1 1 1 𝐴. 𝐵. 𝐶
= 𝑚7
Cabe resaltar que en las columnas AB no se sigue el orden progresivo de valores, 00, 01, 10 y
11; sino 00, 01, 11 y 10. Esto se debe a que el proceso de minimización depende de la
ubicación de las celdas en el mapa; ya que, entre una celda y otra (en forma horizontal o en
forma vertical) sólo debe cambiar 1 variable (adyacencia lógica).
Ejemplo 1
Simplificar la siguiente función 𝑓(𝑎, 𝑏, 𝑐) = ∑𝑚(0,1,2,4,6)
A B C Mintermino
0 0 0 𝐴̅. 𝐵̅ . 𝐶̅ = 𝑚0
0 0 1 𝐴̅. 𝐵̅ . 𝐶 = 𝑚1
0 1 0 𝐴̅. 𝐵. 𝐶̅ = 𝑚2
0 1 1
1 0 0 𝐴. 𝐵̅ . 𝐶̅ = 𝑚4
1 0 1
1 1 0 𝐴. 𝐵. 𝐶̅ = 𝑚6
1 1 1

Resolución
Por el método de carnaugh, de la tabla la función booleana está definida por
𝑓(𝑎, 𝑏, 𝑐) = ∑ (0,1,2,4,6) = 𝑚0 + 𝑚1 + 𝑚2 + 𝑚4 + 𝑚6
𝑚
𝑓(𝑎, 𝑏, 𝑐) = 𝑚0 + 𝑚1 + 𝑚2 + 𝑚4 + 𝑚6
𝑓(𝑎, 𝑏, 𝑐) = 𝐴̅. 𝐵̅ . 𝐶̅ + 𝐴̅. 𝐵̅ . 𝐶 + 𝐴̅. 𝐵. 𝐶̅ + 𝐴. 𝐵̅ . 𝐶̅ + 𝐴. 𝐵. 𝐶̅
00 01 11 10
0
1 (0) 1 (2) 1 (6) 1 (4)
1
1 ( 1)
De acuerdo a la tabla se toma dos o cuatro cuadros, (celdas adyacentes) y acuerdo a la

codificación binaria, se considera la variable que no cambian de signo, y se aplica la definición
de mintermino, es decir será 0 cuando la variable es complementaria y 1 cuando no es
complementaria. Quedando la función simplificada de la siguiente forma
𝑓(𝑎, 𝑏) = 𝑎̅. 𝑏̅ + 𝑐̅
Primer rectángulo Segundo rectángulo

000 000
001 010
100
110
̅ 𝑏̅
𝑎. 𝑐̅

Ejemplo 2
Simplificar la función booleana expresada en la siguiente tabla de verdad por medio del método
de mapas de karnaugh
x y z ∑𝑚 𝑚𝑖 (Minterminos)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
Resolución
De acuerdo a la tabla tenemos la función está definida por
𝑓(𝑥, 𝑦, 𝑧) = 𝑥̅ 𝑦̅𝑧 + 𝑥̅ 𝑦𝑧 + 𝑥𝑦̅𝑧̅ + 𝑥𝑦̅𝑧 + 𝑥𝑦𝑧, donde simplificada literalmente será
𝑓(𝑥, 𝑦, 𝑧) = ∑𝑚(1,3,4,5,7)
El mapa de karnaugh estará por
i) Sí agrupamos los términos donde la salida es igual 1, de dos en dos minterminos, como se
muestra en la siguiente tabla

𝑥̅ 𝑦̅𝑧 + 𝑥̅ 𝑦𝑧 = 𝑥̅ 𝑧(𝑦 + 𝑦̅) = 𝑥̅ 𝑧
𝑥𝑦̅𝑧 + 𝑥𝑦𝑧 = 𝑥𝑧(𝑦̅ + 𝑦) = 𝑥𝑧
𝑥𝑦̅𝑧̅ + 𝑥𝑦̅𝑧 = 𝑥𝑦̅(𝑧̅ + 𝑧) = 𝑥𝑦̅
La función booleana simplificada será
𝑓(𝑥, 𝑦, 𝑧) = 𝑥̅ 𝑧 + 𝑥𝑦̅ + 𝑥𝑧
ii) Sí agrupamos los términos donde la salida es igual 1, de 4 y 2 minterminos, como se muestra
en la siguiente tabla
𝑥̅ 𝑦̅𝑧 + 𝑥̅ 𝑦𝑧 + 𝑥𝑦̅𝑧 + 𝑥𝑦𝑧 = 𝑥̅ 𝑧(𝑦 + 𝑦̅) + 𝑥𝑧(𝑦 + 𝑦̅) = 𝑥̅ 𝑧 + 𝑥𝑧 = 𝑧(𝑥̅ + 𝑥) = 𝑧
𝑥𝑦̅𝑧̅ + 𝑥𝑦̅𝑧 = 𝑥𝑦̅(𝑧 + 𝑧̅) = 𝑥𝑦̅
La función booleana simplificada será
𝑓(𝑥, 𝑦, 𝑧) = 𝑥𝑦̅ + 𝑧
Mapa de karnaugh para cuatro variables
Sea f una función de cuatro variables 𝑓: 𝐵 4 → 𝐵, para este caso se forma un mapa de
24 = 16 , 𝑛 = 4 , minterminos (celdas), donde se sigue el mismo procedimiento que para una

función de tres variables.

00 01 11 10
00 𝑚0 𝑚4 𝑚12 𝑚8
01 𝑚1 𝑚5 𝑚13 𝑚9
11 𝑚3 𝑚7 𝑚15 𝑚11
10 𝑚2 𝑚6 𝑚14 𝑚10
Considerar el orden de las variables de acuerdo a las significancia
Las filas siguen el mismo orden de las columnas (00, 01, 11 y 10) para que haya adyacencia
lógica.
Ejemplo
Simplificar por el método de mapas de karnaugh la siguiente función booleana
𝑓(𝐴, 𝐵, 𝐶, 𝐷) = ∑ (1,5,7,9,13,15)
𝑚
𝑓(𝐴, 𝐵, 𝐶, 𝐷) = 𝐴̅𝐵̅ 𝐷
̅ 𝐸 + 𝐴̅𝐵𝐷
̅ 𝐸 + 𝐴̅𝐵𝐶𝐸 + 𝐴𝐵̅ 𝐶̅ 𝐷 + 𝐴𝐵𝐶̅ 𝐷 + 𝐴𝐵𝐶𝐷
Resolución
El mapa de karnaugh de acuerdo a los minterminos estará dado por la siguiente tabla
00 01 11 10
00
01
1 1 1 1
11
1 1
10

La función simplificada siguiendo el método estará dado por
𝑓(𝐴, 𝐵, 𝐶, 𝐷) = 𝐶̅ 𝐷 + 𝐵𝐷
Mapa de karnaugh para cinco variables
Sea f una función de cinco variables 𝑓: 𝐵 5 → 𝐵, 𝑓(𝐴, 𝐵, 𝐶, 𝐷, 𝐸), para este caso se forma un
mapa de 25 = 32 , 𝑛 = 5 , minterminos (celdas), como se muestra el siguiente tabla.
ABC
DE 000 001 011 010 110 111 101 100
00 𝑚0 𝑚4 𝑚12 𝑚8 𝑚24 𝑚28 𝑚20 𝑚16
01 𝑚1 𝑚5 𝑚13 𝑚9 𝑚25 𝑚29 𝑚21 𝑚17
11 𝑚3 𝑚7 𝑚15 𝑚11 𝑚27 𝑚31 𝑚23 𝑚19
10 𝑚2 𝑚6 𝑚14 𝑚10 𝑚26 𝑚30 𝑚22 𝑚18
Se sigue el mismo procedimiento que para una función de cuatro variables.
Ejemplo
Simplificar por el método de mapas de karnaugh la siguiente función booleana
𝑓(𝐴, 𝐵, 𝐶, 𝐷, 𝐸) = ∑ (0,2,4,7,10,12,13,18,23,26,28,29)
𝑚

Resolución
El mapa de karnaugh de acuerdo a los minterminos estará dado por la siguiente tabla
ABC
DE 000 001 011 010 100 101 111 110
00 11 11 11 11
01 11 11
11 11 11
10 11 11 1 1 11
ABC
DE 000 001 011 010 110 111 101 100
00 0 4 12 8 24 28 20 16
01 1 5 13 9 25 29 21 17
11 3 7 15 11 27 31 23 19
10 2 6 14 10 26 30 22 18
La función simplificada siguiendo el método, estará dado por
𝑓(𝐴, 𝐵, 𝐶, 𝐷, 𝐸) = 𝐵̅ 𝐶𝐷𝐸 + 𝐴̅𝐵̅ 𝐷 ̅ + 𝐶̅ 𝐷𝐸̅

̅ 𝐸̅ + 𝐵𝐶𝐷
Metodología para simplificar expresiones mediante mapas de karnaugh
Paso1. Convertir la expresión a una suma de productos (si es necesario):
a. Algebraicamente
b. Construyendo la tabla de verdad
Paso2. Dibujar el mapa

Paso3. Cubrir todos los unos del mapa mediante rectángulos de 2𝑛 elementos (donde n=0..
número de variables), es decir, 2, 4, 8, 16, etc.
a. Ningún rectángulo debe tener un 0
b. Usar la mínima cantidad de rectángulos
c. Hacer cada rectángulo tan grande como sea posible
Paso4. Encontrar la suma de productos minimal
a. Cada rectángulo es un término producto
b. Cada término se define encontrando las variables que hay en común en dicho rectángulo
Paso5. Agrupar los rectángulos
a. Para simplificar la expresión, se agrupan los 1’s de celdas adyacentes en bloques cuadrados o
rectangulares de 2, 4, 8, 16,…, 2𝑛 . Estos se llaman implicantes primos.
b. Si alguno de los rectángulos contiene algún 1 que no aparece en ningún otro rectángulo,
entonces es un implicante primo esencial, los cuales deben aparecer de manera obligatoria en el
resultado final.
NOTA:
Cuando se desea obtener una “suma de productos”, entonces se agrupan los 1’s.
Cuando se desea obtener un “producto de sumas”, entonces se agrupan los 0’s.
Aunque las expresiones resultantes no son iguales, son lógicamente equivalentes.

Capítulo 7
7.1. Estructuras matemáticas
Una estructura matemática es una serie de objetos matemáticos con la definición de las
operaciones que se realizan con estos y las propiedades que las acompañan, también llamado un
sistema matemático, para matemática discreta se estudian únicamente las estructuras
matemáticas discretas.
Ejemplos
La colección de los conjuntos con las operaciones, unión, intersección y complemento, y las
operaciones relacionadas, es una estructura matemática discreta. S e denota esta estructura por
[𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜𝑠,∪,∩, − ].
La colección de matrices de orden 3x3 con las operaciones de adición, multiplicación y

𝑇]
transpuesta es una estructura matemática que se denota por [𝑚𝑎𝑡𝑟𝑖𝑐𝑒𝑠 3𝑥3, +,∗,
7.2. Propiedades de una estructura matemática
cerradura
Una estructura es cerrada con respecto de una operación si esa operación produce otro elemento
de la colección de objetos.
Ejemplo
La estructura de los números enteros impares con las operaciones suma y multiplicación
[𝑒𝑛𝑡𝑒𝑟𝑜𝑠 𝑖𝑚𝑝𝑎𝑟𝑒𝑠, +,∗]
La estructura no es cerrada con respecto a la adición, dado que la suma de dos enteros impares
es un entero par.
La estructura es cerrada con respecto a la multiplicación, dado que el producto de dos enteros
impares es un número impar.

conmutativa
La propiedad conmutativa es el orden de los objetos que no cambia el resultado de la operación.
Ejemplo
i) La unión y la conjunción para las matices booleanas son operaciones conmutativas, es decir
𝐴∨𝐵 =𝐵∨𝐴𝑦𝐴∧𝐵 =𝐵∧𝐴
ii) La multiplicación ordinaria de matrices no es una operación conmutativa, decir 𝐴𝐵 ≠ 𝐵𝐴
Asociativa
La propiedad asociativa es aquella donde los objetos matemáticos se pueden asociar sin que
cambie el resultado
Ejemplo
La unión de conjuntos es una operación asociativa dado que (𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶)
Distributiva
Si una estructura matemática tiene dos operaciones binarias entonces la distribución de los
objetos matemáticos no cambia el resultado.
Ejemplo
En el álgebra de Boole tenemos, si a, b y c pertenecen a B entonces
a + (b. c) = (a + b)(a + c)
a. (b + c) = (a. b) + (a. c)
Nótese que en la distribución para la suma en el producto, la expresión a la derecha es diferente

de la empleada habitualmente para números reales y enteros.
Observación
Una operación que combina dos objetos matemáticos es una operación binaria
Una operación que requiere solo un objeto matemático en una operación unaria

7.3. Leyes de Morgan
Las leyes son aplicables para algunas estructuras matemáticas pero no en general.
Ejemplo
i) La estructura [𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑏𝑜𝑜𝑙𝑒𝑎𝑛𝑜, +,∗ , 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜]
̅̅̅̅̅̅̅
𝑎 + 𝑏 = 𝑎. ̅ 𝑏̅
̅̅̅ = 𝑎̅ + 𝑏̅
𝑎𝑏
ii) La estructura [𝑛𝑢𝑚𝑒𝑟𝑜𝑠 𝑟𝑒𝑎𝑙𝑒𝑠, +,∗ , √ ], no satisface las leyes de Morgan, ya que
√𝑥 + 𝑦 ≠ √𝑥 ∗ √𝑦
7.4. Ley de composición interna (operación binaria)
Es una aplicación o función definida en un conjunto no vacío A, es decir
∗ ∶ 𝐴𝑥𝐴 → 𝐴
(𝑎1 , 𝑎2 ) → 𝑎1 ∗ 𝑎2
Donde como una operación binaria es una función entonces solo se le asigna un elemento de A
a cada pareja ordenada.
Ejemplos
La operación binaria de suma en 𝑍 es conmutativa es decir
𝑎∗𝑏 =𝑎+𝑏 = 𝑏+𝑎 = 𝑏∗𝑎
La operación binaria de resta en 𝑍 no es conmutativa es decir
2−3≠3−2
7.5. Semigrupo
Un semigrupo es un subcojunto no vacio A con una operación binaria asociativa (*) definida en
en A. se denota el semigrupo como (S,*).

Por otro lado el semigrupo (S,*) es conmutativo si (*) es una operación conmutativa.
Ejemplo
La operación binaria de suma en 𝑍 es asociativa por lo tanto (𝑍, +) es un semigrupo
7.5.1. Elemento identidad en un semigrupo
Un elemento 𝑒 de un semigrupo (𝑆;∗), es un elemento identidad si se cumple
𝑒∗𝑎=𝑎∗𝑒=𝑎
Ejemplo
Los siguientes semigrupos tienen elemento identidad
(𝑍, . ), y (𝑍, +)
7.5.2. Monoide
Un moniode es un semigrupo (𝑆;∗) que tiene elemento identidad
Ejemplo
Los siguientes semigrupos (𝑍, . ), y (𝑍, +) son monoides
7.5.3. Isomorfismo
Sean (𝑆;∗) y (𝑇;∗! ), dos semigrupos, una función 𝑓: 𝑆 → 𝑇es un isomorfismo de (𝑆;∗) a (𝑇;∗! )
si es una correspondencia biyectiva de S a T y si
𝑓(𝑎 ∗ 𝑏) = 𝑓(𝑎) ∗! 𝑓(𝑏), ∀𝑎, 𝑏 ∈ 𝑆
Ejemplo
Sea T el conjunto de todos los enteros pares, probar que los semigrupos (𝑍; +) y (𝑇; +) son
isomorfos.
Prueba
Definimos la función 𝑓: 𝑍 → 𝑇 donde para cada 𝑎 ∈ 𝑍 le corresponde 𝑓(𝑎) = 2𝑎

i) Probaremos que la función f es biyectiva
a) Inyectividad
Si 𝑓(𝑎) = 𝑓(𝑏) entonces 2𝑎 = 2𝑏 implicando 𝑎 = 𝑏 por lo tanto f es inyectiva
b) suryectividad
𝑏
Sea b un entero par 𝑏 ∈ 𝑇, entonces consideremos 𝑎 = 2 ∈ 𝑍 entonces
𝑏
𝑓(𝑎) = 2𝑎 = 2 (2) = 𝑏, por lo tanto f es sobreyectiva
Ahora de a) y b) la función f es biyectiva
ii) si 𝑓(𝑎 + 𝑏) = 2(𝑎 + 𝑏) = 2𝑎 + 2𝑏 = 𝑓(𝑎) + 𝑓(𝑏)
Finalmente de i) y ii) los semigrupos (𝑍; +) y (𝑇; +) son isomorfos.
7.5.4. Homomorfismo
Sean (𝑆;∗) y (𝑇;∗! ) dos semigrupos, una función 𝑓: 𝑆 → 𝑇 definida para todo punto, es un
homomorfismo de (𝑆;∗) a (𝑇;∗! ) si
𝑓(𝑎 ∗ 𝑏) = 𝑓(𝑎) ∗! 𝑓(𝑏), ∀𝑎, 𝑏 ∈ 𝑆
Ejemplo
Sea el conjunto 𝐴 = {0,1}, y consideremos los semigrupos (𝐴∗ , . ) a (𝐴, +)
Donde 𝑓: 𝐴∗ → 𝐴 está definido por
1, 𝑠𝑖 𝑎 𝑡𝑖𝑒𝑛𝑒 𝑢𝑛 𝑛𝑢𝑚𝑒𝑟𝑜 𝑖𝑚𝑝𝑎𝑟 𝑑𝑒 𝑢𝑛𝑜𝑠

𝑓(𝑎) = {
0, 𝑠𝑖 𝑎 𝑡𝑖𝑒𝑛𝑒 𝑢𝑛 𝑛𝑢𝑚𝑒𝑟𝑜 𝑝𝑎𝑟 𝑑𝑒 𝑢𝑛𝑜𝑠
Donde
+ 0 1
0 0 1
1 1 0

Por demostrar
𝑓(𝑎. 𝑏) = 𝑓(𝑎) + 𝑓(𝑏)
En efecto
𝑓(0.1) = 1 = 𝑓(0) + 𝑓(1)
𝑓(1.1) = 1 = 𝑓(1) + 𝑓(1)
𝑓(0.0) = 0 = 𝑓(0) + 𝑓(0)
𝑓(0) = 0, 𝑓(1) = 1
Por lo tanto f es un homomorfismo
7.5.5. Teorema
Sean (𝑆;∗) y (𝑇;∗! ) monoides con identidades 𝑒, 𝑒 ! , respectivamente. Sea 𝑓: 𝑆 → 𝑇 un

isomorfismo. Entonces 𝑓(𝑒) = 𝑒 !
Demostración
Sea 𝑏 un elemento cualesquiera de 𝑇. Como 𝑓 es sobreyectiva existe 𝑎 ∈ 𝑆 talque 𝑓(𝑎) = 𝑏,

entonces 𝑎 = 𝑎 ∗ 𝑒
𝑏 = 𝑓(𝑎) = 𝑓(𝑎 ∗ 𝑒) = 𝑓(𝑎) ∗! 𝑓(𝑒)
𝑏 = 𝑏 ∗! 𝑓(𝑒) …….𝛼
De manera análoga si 𝑎 = 𝑒 ∗ 𝑎
𝑏 = 𝑓(𝑎) = 𝑓(𝑒 ∗ 𝑎) = 𝑓(𝑒) ∗! 𝑓(𝑎)
𝑏 = 𝑓(𝑒) ∗! 𝑏………𝛽
Así para cualquier 𝑏 ∈ 𝑇 y de 𝛼 𝑦 𝛽, tenemos
𝑏 = 𝑏 ∗! 𝑓(𝑒) = 𝑓(𝑒) ∗! 𝑏

Lo que significa que 𝑓(𝑒) es una identidad para 𝑇. Esto implica que 𝑓(𝑒) = 𝑒 ! ∎
7.5.6. Teorema
Sean (𝑆;∗) y (𝑇;∗! ) monoides con identidades 𝑒, 𝑒 ! , respectivamente. Sea 𝑓: 𝑆 → 𝑇 un

homomorfismo de (𝑆;∗) sobre (𝑇;∗! ) . Entonces 𝑓(𝑒) = 𝑒 !
Demostración
Si 𝑓 es un homomorfismo entonces
𝑓(𝑎 ∗ 𝑏) = 𝑓(𝑎) ∗! 𝑓(𝑏), ∀𝑎, 𝑏 ∈ 𝑆
Consideremos 𝑎 = 𝑒
𝑓(𝑒 ∗ 𝑏) = 𝑓(𝑒) ∗! 𝑓(𝑏) 𝑓(𝑏) = 𝑓(𝑒) ∗! 𝑓(𝑏)……………… (1)
De manera análoga si consideramos 𝑏 = 𝑒
𝑓(𝑎 ∗ 𝑒) = 𝑓(𝑎) ∗! 𝑓(𝑒) 𝑓(𝑎) = 𝑓(𝑎) ∗! 𝑓(𝑒); ∀𝑎 ∈ 𝑆…….. (2)
Luego dado que en (2) es para todo 𝑎 ∈ 𝑆
En particular sea 𝑎 = 𝑏 tendremos
𝑓(𝑏) = 𝑓(𝑏) ∗! 𝑓(𝑒)……………………………………………(3)
Finalmente de (1) y (3), obtenemos que 𝑓(𝑒) ∗! 𝑓(𝑏) = 𝑓(𝑏) ∗! 𝑓(𝑒) lo que significa que 𝑓(𝑒) =
𝑒 !∎
7.5.7. Teorema
Si 𝑓 es un homomorfismo de un semigrupo conmutativo (𝑆;∗), sobre un semigrupo (𝑇;∗! ),

entonces (𝑇;∗! ) también es conmutativo.
Demostración
Sea 𝑓: 𝑆 → 𝑇; si 𝑥1 ; 𝑥2 ∈ 𝑇, entonces existen 𝑦1 ; 𝑦2 ∈ 𝑆 tal que 𝑥1 = 𝑓(𝑦1 ); 𝑦 𝑥2 = 𝑓(𝑦2 ) por

lo tanto

𝑥1 ∗! 𝑥2 = 𝑓(𝑦1 ) ∗! 𝑓(𝑦2 ), ahora dado que 𝑓 es un homomorfismo y 𝑆 es conmutativo entonces
se cumple que:
𝑥1 ∗! 𝑥2 = 𝑓(𝑦1 ) ∗! 𝑓(𝑦2 ) = 𝑓(𝑦1 ∗ 𝑦2 ) = 𝑓(𝑦2 ∗ 𝑦1 ) = 𝑓(𝑦2 ) ∗! 𝑓(𝑦1 ) = 𝑥2 ∗! 𝑥1
𝑥1 ∗! 𝑥2 = 𝑥2 ∗! 𝑥1
Finalmente concluimos que (𝑇;∗! ) es conmutativo.
7.6. Teoría de grupos
7.6.1. Grupo
Definición.- Sea (𝐺;∗), un monoide entonces (𝐺;∗) es un grupo si cumple las siguientes
condiciones.
1.- ∀ 𝑎, 𝑏 ∈ 𝐺 , 𝑎 ∗ 𝑏 ∈ 𝐺 (cerradura)
2.- ∀ 𝑎, 𝑏, 𝑐 ∈ 𝐺 , 𝑎 ∗ (𝑏 ∗ 𝑐) = (𝑎 ∗ 𝑏) ∗ 𝑐 (asociatividad)
3.- Existe un elemento 𝑒 ∈ 𝐺 talque
𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎, ∀𝑎 ∈ 𝐺
4.- Para todo elemento en 𝐺 tiene un inverso en 𝐺, respecto al operador (∗)
Además si (𝐺;∗), cumple las cuatro condiciones mencionadas anteriormente y es conmutativo

entonces se llama grupo abeliano.
Ejemplo
Sea (𝑅;∗), donde 𝑅 es el conjunto de los números reales diferentes de cero, y definimos la
operación (∗) como
𝑎𝑏
𝑎∗𝑏 = 2
Verificar si (𝑅;∗), cumple con las condiciones de grupo.
1.-Sea 𝑎, 𝑏 ∈ 𝑅 entonces 𝑎 ∗ 𝑏 ∈ 𝑅

𝑎𝑏 𝑎𝑏
En efecto si 𝑎 ∗ 𝑏 = entonces ∈𝑅
2 2
2.-Sea 𝑎, 𝑏, 𝑐 ∈ 𝑅 entonces 𝑎 ∗ (𝑏 ∗ 𝑐) = (𝑎 ∗ 𝑏) ∗ 𝑐
𝑏𝑐 𝑎(𝑏𝑐) 𝑎𝑏 𝐶
En efecto 𝑎 ∗ ( 2 ) = = ( 2 ) . 2 = (𝑎 ∗ 𝑏) ∗ 𝑐
4
Luego la operación (*) es asociativa
3.-Existencia del elemento identidad 𝑒 es decir, ∃ 𝑒 ∈ 𝑅, talque 𝑎 ∗ 𝑒 = 𝑎 = 𝑒 ∗ 𝑎, ∀𝑎 ∈ 𝐺
𝑎.𝑒
Luego por definición del operador 𝑎 ∗ 𝑒 = =𝑎→𝑒=2∈𝑅
2
Implicando que existe el elemento 𝑒 = 2
4.-Existencia del elemento inverso 𝑎−1
𝑎.𝑎−1
En efecto si 𝑎−1 ∈ 𝑅, entonces 𝑎 ∗ 𝑎−1 = 𝑒 → = 𝑒, además si 𝑒 = 2, tendremos
2
4
Que el elemento será 𝑎−1 = 𝑎 ∈ 𝑅
Por lo tanto (𝑅;∗) es un grupo
Por otro lado verificaremos que (𝑅;∗), es conmutativo es decir 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎
𝑎𝑏 𝑏𝑎
𝑎∗𝑏 = = = 𝑏∗𝑎
2 2
Por lo tanto (𝑅;∗) es un grupo abeliano ∎
7.7. Teorema
Si (𝐺,∗) es un grupo entonces cada elemento 𝑎 ∈ 𝐺 tiene un único elemento inverso en 𝐺.
Prueba
Sean 𝑎,
̅ 𝑎̿ , inversos de 𝑎, entonces 𝑎. 𝑎̅ = 𝑒, 𝑎. 𝑎̿ = 𝑒
𝑎̅(𝑎. 𝑎̿) = 𝑎̅𝑒 = 𝑎̅ ………………(𝛼)
𝑎̅(𝑎. 𝑎̿) = (𝑎̅. 𝑎)𝑎̿ = 𝑒𝑎̿ = 𝑎̿……(𝛽)

Ahora de (𝛼) y (𝛽) concluimos que 𝑎̅ = 𝑎̿
7.8. Teorema
Si (𝐺,∗) es un grupo y sean 𝑎, 𝑏, 𝑐 elementos de 𝐺entonces.
a) Si 𝑎𝑏 = 𝑎𝑐 entonces 𝑏 = 𝑐
b) Si 𝑏𝑎 = 𝑐𝑎 entonces 𝑏 = 𝑐
Prueba
a)Si 𝑎𝑏 = 𝑎𝑐 y dado que (𝐺,∗) es un grupo tiene elemento inverso 𝑎−1 , luego
𝑎−1 (𝑎𝑏) = 𝑎−1 (𝑎𝑐) → (𝑎. 𝑎−1 )𝑏 = (𝑎. 𝑎−1 )𝑐 → 𝑒. 𝑏 = 𝑒. 𝑐 → 𝑏 = 𝑐
Para el caso b) de manera análoga
7.9. Teorema
Si (𝐺,∗) es un grupo y sean 𝑎, 𝑏 elementos de 𝐺 entonces.
a) (𝑎−1 )−1 = 𝑎
b) (𝑎𝑏)−1 = 𝑏 −1 . 𝑎−1
Prueba
a) Dado que (𝐺,∗) es un grupo, 𝑎, 𝑎−1 ∈ 𝐺 entonces existe un elemento inverso para 𝑎−1
Es decir (𝑎−1 )(𝑎−1 )−1 = 𝑒 → 𝑎(𝑎−1 )(𝑎−1 )−1 = 𝑎. 𝑒 → (𝑎. 𝑎−1 )(𝑎−1 )−1 = 𝑎. 𝑒
𝑒(𝑎−1 )−1 = 𝑎 → (𝑎−1 )−1 = 𝑎 ∎
b) Dado que (𝐺,∗) es un grupo, 𝑎𝑏, (𝑎𝑏)−1 ∈ 𝐺 entonces existe un elemento inverso para (𝑎𝑏)−1,
es decir ((𝑎𝑏)−1 )((𝑎𝑏)−1 )−1 = 𝑒 → ((𝑎𝑏)−1 )𝑎𝑏 = 𝑒
((𝑎𝑏)−1 )𝑎𝑏𝑏 −1 𝑎−1 = 𝑒𝑏 −1 𝑎−1
((𝑎𝑏)−1 )𝑒 = 𝑒𝑏 −1 𝑎−1 → (𝑎𝑏)−1 = 𝑏 −1 𝑎−1 ∎

7.10. Teorema
Si (𝐺,∗) es un grupo y sean 𝑎, 𝑏 elementos de 𝐺 entonces.
a) La ecuación 𝑎𝑥 = 𝑏 tiene una única solución en 𝐺
b) La ecuación 𝑦𝑎 = 𝑏 tiene una única solución en 𝐺
Prueba
a) Dado que (𝐺,∗) es un grupo, si 𝑎−1 , 𝑏 ∈ 𝐺 → 𝑎−1 . 𝑏 ∈ 𝐺, luego 𝑥 = 𝑎−1 . 𝑏 es una solución
de la ecuación 𝑎𝑥 = 𝑏, es decir 𝑎(𝑎−1 𝑏) = (𝑎𝑎 −1 )𝑏 = 𝑏
Ahora supongamos que 𝑥1 , 𝑦 𝑥2 son dos soluciones de la ecuación 𝑎𝑥 = 𝑏, entonces
𝑎𝑥1 = 𝑏 𝑦 𝑎𝑥2 = 𝑏 → 𝑎𝑥1 = 𝑎𝑥2 → 𝑎−1 𝑎𝑥1 = 𝑎 −1 𝑎𝑥2 → 𝑒𝑥1 = 𝑒𝑥2 → 𝑥1 = 𝑥2 ∎
De manera análoga para el caso b)
7.11. Subgrupo
A continuación presentaremos dos definiciones de subgrupo
Definición.-Sea (𝐺,∗) un grupo y 𝐻 ≠ 0 subconjunto de 𝐺 (𝐻 ⊆ 𝐺), se dice que 𝐻 es un

subgrupo de 𝐺, si 𝐻 con la operación definida sobre 𝐺 verifica las siguientes propiedades.
1.- El elemento identidad 𝑒 de 𝐺 es un elemento de 𝐻
2.- Si 𝑎, 𝑏 ∈ 𝐻 entonces 𝑎 ∗ 𝑏 ∈ 𝐻
3.-Si ℎ ∈ 𝐻, entonces ℎ−1 ∈ 𝐻
Definición.-Sea (𝐺,∗) un grupo, el conjunto 𝐻 es un subgrupo de 𝐺 si cumple las siguientes

condiciones.
1.-𝐻 ≠ ∅
2.-𝐻 ⊆ 𝐺
3.-∀ 𝑎, 𝑏 ∈ 𝐻 → 𝑎 ∗ 𝑏 ∈ 𝐻

Ejemplo
Dados dos subgrupos (𝐻1,*), (𝐻2 *) e un mismo grupo (𝐺,∗) , entonces la intersección de los
subgrupos 𝐻 = 𝐻1 ∩ 𝐻2, es también otro subgrupo del mismo grupo (𝐺,∗).
En efecto
1.- Veamos si H es no vació
Dado que tenemos como hipótesis que (𝐻1,*), (𝐻2 *) son subgrupos por lo tanto en cada uno
está el elemento neutro de grupo, es decir 𝑒 ∈ 𝐻1 , 𝑒 ∈ 𝐻2
Entonces por definición de intersección 𝑒 ∈ 𝐻1 ∩ 𝐻2 → 𝑒 ∈ 𝐻 → 𝐻 ≠ ∅
2.-Para todo 𝑥 ∈ 𝐻 → 𝑥 ∈ 𝐻1 ∩ 𝐻2 → 𝑥 ∈ 𝐻1 ∧ 𝑥 ∈ 𝐻2 por hipótesis tenemos
(𝐻1 ⊆ 𝐺 ∧ 𝐻2 ⊆ 𝐺) → 𝑥 ∈ 𝐺 ∧ 𝑥 ∈ 𝐺 → 𝑥 ∈ 𝐺, por lo tanto queda probado (𝐻 ⊆ 𝐺)
3.-∀ 𝑎, 𝑏 ∈ 𝐻 → 𝑎 ∈ (𝐻1 ∩ 𝐻2 ) ∧ 𝑏 ∈ (𝐻1 ∩ 𝐻2 ) → (𝑎 ∈ 𝐻1 ∧ 𝑎 ∈ 𝐻2 ) ∧ (𝑏 ∈ 𝐻1 ∧ 𝑏 ∈ 𝐻2 )
Ahora por la conmutatividad y asociatividad de la conjunción
(𝑎 ∈ 𝐻1 ∧ 𝑏 ∈ 𝐻1 ) ∧ (𝑎 ∈ 𝐻2 ∧ 𝑏 ∈ 𝐻2 )
Luego por condición necesaria de subgrupo y definición de intersección tendremos
(𝑎 ∈ 𝐻1 ∧ 𝑏 ∈ 𝐻1 ) ∧ (𝑎 ∈ 𝐻2 ∧ 𝑏 ∈ 𝐻2 ) → ((𝑎 ∗ 𝑏) ∈ 𝐻1 ) ∧ ((𝑎 ∗ 𝑏) ∈ 𝐻2 )
(𝑎 ∗ 𝑏) ∈ (𝐻1 ∩ 𝐻2 ) → (𝑎 ∗ 𝑏) ∈ 𝐻
Por lo tanto (𝐻1 ∩ 𝐻2 ,∗), es un subgrupo de (𝐺,∗).
7.12. Grupos productos y cocientes
7.12.1. Teorema
Sean (𝐺1 ,∗1 ) y (𝐺2 ,∗2 ) dos grupos con elementos identidad 𝑒1 , 𝑒2 , respectivamente. En el conjunto
𝐺1 𝑥𝐺2 se define la operación ∗ talque
(𝑎, 𝑏) ∗ (𝑐, 𝑑) = (𝑎 ∗1 𝑐; 𝑏 ∗2 𝑑) , entonces (𝐺1 𝑥𝐺2 ;∗) es un grupo y se denomina grupo producto.

7.12.2. Teorema
Sea 𝑅 una relación de congruencia sobre el grupo (𝐺,∗). Entonces el semigrupo (𝐺/𝑅,⊛) es un
grupo, donde la operación ⊛ se define en 𝐺/𝑅 como
[𝑎] ⊛ [𝑏] = [𝑎 ∗ 𝑏] y se denomina grupo cociente.

Capítulo 8
8.1. Teoría de códigos
8.1.1. Codificación
Una comunicación de datos consiste en la transmisión de una secuencia de caracteres de algún

alfabeto finito B (normalmente B = {0, 1}) desde una localización física (fuente) a otra (receptor)
a través de un canal de comunicación. En la mayoría de los casos, imperfecciones del canal,
denominadas ruido, provocan que algunos caracteres transmitidos sean incorrectamente recibidos
por el receptor. Por ello se introducen, de modo sistemático, redundancias en la información, las
cuales permiten detectar, e incluso corregir, los errores cuando el mensaje recibido es
descodificado. Un sistema general de comunicación consta de cinco partes. Una fuente o emisor,
un codificador, un canal de comunicación, un descodificador y un destino o receptor.
Una fuente de información: es un proceso que genera símbolos pertenecientes a un alfabeto

finito, en forma discreta, o valores reales, en forma continua. Los símbolos o los valores
generados son de interés para un destino.
Un codificador: es un mecanismo que opera sobre la salida de la fuente para ponerla en
una forma adecuada a la transmisión.
Un canal: es un modelo del medio usado para la transmisión de los mensajes. En particular,
puede modelar un cable eléctrico, una banda de frecuencias de radio, un rayo de luz, una
superficie magnética, etc.

Un decodificador: es un mecanismo que normalmente realiza la operación inversa del
codificador, intentando recuperar en la forma más exacta posible el mensaje originalmente
emitido por la fuente.
Ejemplo 4.1.1. Supongamos que un centro de control marítimo debe transmitir a los barcos la ruta
que deben seguir para llegar a puerto utilizando un canal binario cuya probabilidad de transmitir
incorrectamente un bit es del uno por mil, uno de cada mil bits se recibirá mal. El alfabeto fuente
consta de 4 símbolos {Norte, Sur, Este, Oeste}, cada uno de ellos significa navegar una milla
náutica en esa dirección. Si usamos como código el conjunto de pares binarios C = {00, 01, 10,
11} y se codifica Norte por 00, Oeste por 01, Este por 10 y Sur por 11, la distancia mínima del
código es 1 (no detecta errores). Si la ruta que se desea enviar es NNOO
quedaría codificada como 00 00 01 01, para facilitar su lectura se insertan espacios entre las
palabras. Supongamos que por efecto de las interferencias es recibida como 00 01 01 11, lo que
sería interpretado como la ruta NOOS. La probabilidad de que un símbolo fuente sea interpretado
correctamente es la misma que la probabilidad de que su palabra correspondiente sea recibida
correctamente; para este caso, es del 99, 8001 por ciento; aproximadamente dos de cada mil
palabras serán erróneas, lo cual no parece mucho. Sin embargo, si pensamos que el mensaje
completo consta de cien símbolos fuente, la probabilidad de que éste sea recibido correctamente
en su totalidad es del 81, 865 por ciento.
Si se utiliza el código C = {000, 011, 101, 110}, codificando Norte por 000, Oeste por 011, Este
por 101 y Sur por 110, la distancia mínima es 2 (detecta errores simples), la ruta quedaría
codificada como 000 000 011 011. Si se recibe la transmisión 000 010 011 111 se detecta que la
segunda y la cuarta palabra son incorrectas, pidiéndose una retransmisión del mensaje. La
probabilidad de que una palabra se reciba correctamente es de 99, 7003 por ciento y la de una
recepción correcta de un mensaje de cien símbolos fuente desciende hasta un 74, 071 por ciento;
pero en un 25, 907 por ciento de los casos se detectara que el mensaje es incorrecto; pidiendo su
repetición. En consecuencia, la probabilidad de interpretar mal la recepción de un mensaje baja
del 18, 135 por ciento a menos de 0, 025 por ciento. En el caso de que no fuese posible pedir la
retransmisión de la ruta, sería preferible la utilización de un código corrector de errores simples;
por ejemplo, C = {00000, 01101, 10110, 11011}, codificando Norte por 00000, Oeste por 01101,
Este por 10110 y Sur por 11011, la ruta quedaría codificada como 00000 00000 01101 01101. Al
recibir la transmisión 00000 01000 01101 11101, de nuevo las palabras segunda y cuarta se
detectan como incorrectas, pero debido a las capacidades del código son substituidas por 00000 y
01101 respectivamente, obteniendo la ruta correcta. Un símbolo fuente se interpretara
correctamente siempre que la palabra correspondiente se reciba correctamente o con un error
simple, lo que ocurre en un 99, 999 por ciento de los casos. A costa de incrementar el número de
bits transmitidos, la probabilidad de que un mensaje de cien símbolos fuente sea correctamente
interpretado aumenta hasta el 99, 9 por ciento.
8.1.2. Definición.-Un código (bloque) C para un alfabeto fuente S y un alfabeto del canal B es
una aplicación inyectiva, 𝐶: 𝑆 → 𝐵 𝑛 . La imagen de la aplicación C se denomina conjunto de
palabras código, y sus elementos son las palabras código. El valor n es la longitud del código, y
el número de palabras código, que coinciden con el número de símbolos fuente, es el tamaño del
código. Un código de longitud n y tamaño M se denomina un [n, M]-código. Un código sobre el
alfabeto B = {0, 1} se llama código binario, si el alfabeto es A = {0, 1, 2} se llama código ternario.
También suele denominarse código al conjunto de palabras código, denotándolo igualmente por
C.
8.2. Codificación binaria
En la codificación binaria es necesario conocer, el sistema binario, la teoría del algebra de Boole,
estructuras matemáticas y los teoremas.
El conjunto binario 𝐵 es un grupo bajo la operación ⊕ donde dicha operación se muestra en la

siguiente tabla.
⊕ 0 1
0 0 1
1 1 0
El conjunto 𝐵 𝑚 = 𝐵𝑥𝐵𝑥 … … … . 𝑥𝐵 es un grupo bajo la operación ⨁ definida por
(𝑥1 , 𝑥2 … … . . 𝑥𝑛 )⨁(𝑦1 , 𝑦2 … … … 𝑦𝑚 ) = (𝑥1 + 𝑦1 , 𝑥2 + 𝑦2 … … … … 𝑥𝑛 + 𝑦𝑚 )
Donde el elemento identidad es 𝑒 = (0,0,0 … . .0) y cada elemento es su propio inverso.

8.3. Función de codificación
Sea 𝑒: 𝐵 𝑚 → 𝐵 𝑛 una función, diremos que 𝑒 es una función de codificación si representa cada
palabra en 𝐵 𝑚 , como una palabra en 𝐵 𝑛 . Es decir si 𝑏 ∈ 𝐵 𝑚 entonces 𝑒(𝑏) es la palabra
codificada que representa a 𝑏, y su notación es dado por 𝑒(𝑚. 𝑛).
Palabra Palabra codificada Palabra
𝑏 ∈ 𝐵𝑚 𝑥 = 𝑒(𝑏) ∈ 𝐵𝑛 𝑥𝑡 ∈ 𝐵𝑛
(Emisión de mensaje) (Recepción de mensaje)
𝑒: Medio de transmisión
(canal)
Función de codificación
Ejemplo
Sea la función de codificación 𝑒(3,9), es decir 𝑒: 𝐵 3 → 𝐵 9 , donde la función de codificación, 𝑒

repite tres veces cada palabra de 𝐵 3
Palabra sin codificar Palabra codificadas

𝑒(000) = 000000000
000
𝑒(001) = 001001001
001
010 𝑒(010) = 010010010
𝑒:
011 𝑒(011) = 011011011
100 Función de codificación 𝑒(100) = 100100100
110 𝑒(110) = 110110110
111
𝑒(111) = 111111111
8.3.1. Definición.- Sea función de codificación 𝑒: 𝐵 𝑚 → 𝐵 𝑛 , si 𝑥 ∈ 𝐵 𝑛 , entonces el número de

unos de elemento 𝑥, se le denomina peso de 𝑥, y se denota como |𝑥|.
Ejemplo
Determinar el peso de cada una de las siguientes palabras en 𝐵 5
a) 𝑥 = 11100 b) 𝑦 = 00000
Aplicando la definición |𝑥| = 3, |𝑦| = 0

8.3.2. Definición.-Una palabra código 𝑏 ∈ 𝐵 𝑛 es una palabra código de paridad, si los dígitos
igual a uno de la palabra código 𝑏 es par.
Ejemplo
𝐶 = {011,101,110}
8.4. Distancia mínima
La distancia mínima de una función de codificación 𝑒: 𝐵 𝑚 → 𝐵 𝑛 , es la mínima de las distancias

entre todas las distintas parejas de palabras codificadas es decir.
𝑑(𝑥, 𝑦)𝑚𝑖𝑛 = 𝑚𝑖𝑛 {𝑑 (𝑒(𝑥𝑗 ), 𝑒(𝑦𝑗 )) , 𝑥𝑗 ≠ 𝑦𝑗 1 ≤ 𝑗 ≤ 𝑛}
Ejemplo
Sea la función de codificación 𝑒(2,5) definida mediante la siguiente codificación
𝑒: 𝑒1 (00) = 00000
𝑒2 (01) = 01110
𝑒3 (10) = 00111
𝑒4 (11) = 11111
Hallar la distancia mínima de la función de codificación
Solución
Realizando las operaciones con el operador suma directa y la definición, obtenemos los siguientes
resultados que se muestran a continuación
𝑑(𝑒1 , 𝑒2 ) = |𝑒1 ⨁𝑒2 | = 3

𝑑(𝑒2 , 𝑒3 ) = |𝑒2 ⨁𝑒3 | = 2
𝑑(𝑒3 , 𝑒4 ) = |𝑒3 ⨁𝑒4 | = 2
𝑑(𝑒1 , 𝑒3 ) = |𝑒1 ⨁𝑒2 | = 3
𝑑(𝑒1 , 𝑒4 ) = |𝑒1 ⨁𝑒2 | = 4
𝑑(𝑒2 , 𝑒4 ) = |𝑒1 ⨁𝑒2 | = 2
Donde la distancia mínima será 2.

8.5. Teorema
Una función de codificación 𝑒: 𝐵 𝑚 → 𝐵 𝑛 , puede detectar 𝑘 o menos errores si y solo si su distancia

mínima es al menos 𝑘 + 1.
Ejemplo
𝑒: 𝑒1 (000) = 00000000
𝑒2 (001) = 10111000
𝑒3 (010) = 00101101
𝑒4 (011) = 10010101
𝑒5 (100) = 10100100
𝑒6 (101) = 10001001
𝑒7 (110) = 00011100
𝑒8 (111) = 00110001
Cuantos errores detecta la función de codificación
Solución
i) Hallando la distancia mínima entre las 28 distintas parejas de palabras codificadas obtenemos
que la distancia mínima igual 3.
ii) Por el teorema la función de codificación detecta 𝑘 o menos errores si y solo si su distancia
mínima es al menos 𝑘 + 1, entonces de acuerdo al dato de i) y teorema tenemos.
𝑘+1≤3→𝑘 ≤2
Así la función detectara dos o menos errores.
8.6. Distancia de Hamming
Sean 𝑥, 𝑦 palabras códigos en 𝐵 𝑛 . La distancia de Hamming denotada por 𝑑(𝑥, 𝑦), entre 𝑥 y 𝑦 es
el peso |𝑥 ⊕ 𝑦| de 𝑥 ⊕ 𝑦. Así la distancia entre 𝑥 = (𝑥1 , 𝑥2 … … . . 𝑥𝑚 ) y 𝑦 = (𝑦1 , 𝑦 … … . . 𝑦𝑚 ) es
el número de los valores 𝑖 talque 𝑥𝑗 ≠ 𝑦𝑗 , es decir el número de posiciones que difieren 𝑥, y 𝑦.

Ejemplo
Determinar la distancia entre 𝑥, 𝑦 palabras códigos en 𝐵 𝑛 , dadas a continuación.
a) 𝑥 = (110110), 𝑦 = (000101)
b) 𝑥 = (001100), 𝑦 = (010110)
Solución
a) 𝑥 ⊕ 𝑦 = 110011 → |𝑥 ⊕ 𝑦| = 4
b) 𝑥 ⊕ 𝑦 = 011010 → |𝑥 ⊕ 𝑦| = 3
8.6.1. Propiedades de la función distancia
Sea 𝑥, 𝑦, 𝑧 elementos de 𝐵 𝑛 entonces
a) 𝑑(𝑥, 𝑦) = 𝑑(𝑦, 𝑥)
b) 𝑑(𝑥, 𝑦) ≥ 0, 𝑥, 𝑦 ∈ 𝐵 𝑛
c) 𝑑(𝑥, 𝑦) = 0 ↔ 𝑥 = 𝑦
d) 𝑑(𝑥, 𝑦) ≤ 𝑑(𝑥, 𝑧) + 𝑑(𝑧, 𝑦) (desigualdad triangular)
8.7. Grupos de código
Consideremos que (𝐵𝑛 ,⊕) sea un grupo, luego utilizando la propiedad de 𝐵 𝑛 definimos lo
siguiente.
Una función de codificación 𝑒: 𝐵 𝑚 → 𝐵 𝑛 es un grupo de código si
𝑒(𝐵 𝑚 ) = {𝑒(𝑏) ∕ 𝑏 ∈ 𝐵 𝑚 } = 𝑟𝑎𝑛(𝑒), es un subgrupo de 𝐵 𝑛
Es decir 𝑒(𝐵𝑚 ) = 𝑁 ⊆ 𝐵 𝑛 , es un subgrupo de 𝐵 𝑛 si cumple las condiciones
a) La identidad de 𝐵 𝑛 es también de 𝑁
b) si 𝑥 y 𝑦 pertenecen a 𝑁, entonces 𝑥 ⊕ 𝑦 ∈ 𝑁
c) si 𝑥 ∈ 𝑁 entonces su inverso está en 𝑁

Ejemplo
𝑒: 𝑒1 (000) = 000000
𝑒2 (001) = 001100
𝑒3 (010) = 010011
𝑒4 (011) = 011111
𝑒5 (100) = 100101
𝑒6 (101) = 101001
𝑒7 (110) = 110110
𝑒8 (111) = 111010
Probar que la función de codificación es un grupo de código
Prueba
Por demostrar que conjunto de palabras codificadas
𝑁 = {000000,001100,010011,011111,100101,101001,110110,111010} es un subgrupo
de 𝐵 6.
a) si (𝐵 6 ,⊕) es un grupo entonces tiene elemento identidad 𝑒 ∈ 𝐵 6 dado por 𝑒 = 000000,y
si observamos en conjunto 𝑁 el elemento identidad 𝑒 ∈ 𝑁.
b) si 𝑥, 𝑦 ∈ 𝑁 → 𝑥 ⊕ 𝑦 ∈ 𝑁
En efecto haciendo todas las operaciones de cerradura con el operador ⊕ obtenemos que
cumple que para todos los elementos 𝑥, 𝑦 ∈ 𝑁, 𝑥 ⊕ 𝑦 ∈ 𝑁
c) Cada elemento 𝑥 ∈ 𝑁 tiene inverso en 𝑁, dado que es su propio inverso es decir
𝑥 ⊕ 𝑥 = 𝑒 = 000000, por lo tanto 𝑁 es un subgrupo de 𝐵 6 y en consecuencia la función de

codificación es un grupo de código.
8.8. Teorema
Sea la función de codificación 𝑒: 𝐵 𝑚 → 𝐵 𝑛 un grupo de código. La distancia mínima de la

función 𝑒 es el peso mínimo distinto de cero de una palabra codificada.

Ejemplo
Considerando el ejemplo anterior donde la función de codificación, 𝑒(3,6) era un grupo

código, aplicando el teorema, la distancia mínima estará dado como el peso menor distinto de
cero de las siete palabras codificadas. Es decir
La distancia mínima será 𝑑(𝑒(𝑥), 𝑒(𝑦)) = 2 con 𝑥, 𝑦 ∈ 𝐵 3
Definición.-Sean las matrices booleanas 𝐷 = [𝑑𝑖𝑗 ] y 𝐸 = [𝑒𝑖𝑗 ] de orden 𝑚𝑥𝑛. Se define la

suma modulo 𝐷 ⊕ 𝐸 como la matriz booleana 𝐹 = [𝑓𝑖𝑗 ] de orden 𝑚𝑥𝑛 y
𝑓𝑖𝑗 = 𝑑𝑖𝑗 ⊕ 𝑒𝑖𝑗 , 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛
Ejemplo
Sean las matrices booleanas
1 0 1 1 1 1 0 1
𝐷 = [0 1 1 0] 𝐸 = [1 1 0 1]
1 0 0 1 0 1 1 1
Hallar la matriz 𝐷 ⊕ 𝐸
0 1 1 0
𝐷 ⊕ 𝐸 = [1 0 1 1]
1 1 1 0
Definición.-Sean las matrices booleanas 𝐷 = [𝑑𝑖𝑗 ] de orden 𝑚𝑥𝑝, y 𝐸 = [𝑒𝑖𝑗 ] de orden 𝑝𝑥𝑛
se define el producto modulo 𝐷⨀𝐸 como la matriz booleana 𝐹 = [𝑓𝑖𝑗 ] de orden 𝑚𝑥𝑛 y
𝑓𝑖𝑗 = 𝑑𝑖1 . 𝑒1𝑗 + 𝑑𝑖2 . 𝑒2𝑗 + ⋯ … … … … . +𝑑𝑖𝑝 . 𝑒𝑝𝑗 , 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛
Ejemplo
Sean las matrices booleanas
1 0
1 1 0
𝐷=[ ] 𝐸 = [1 1 ]
0 1 1
0 1
Hallar la matriz 𝐷 ⊕ 𝐸
0 1
𝐷⨀𝐸 = [ ]
1 0
8.9. Teorema
Sean 𝐷 𝑦 𝐸 matrices booleanas de orden 𝑚𝑥𝑝 y 𝐹 una matriz booleana de orden 𝑝𝑥𝑛 entonces
(𝐷 ⊕ 𝐸) ∗ 𝐹 = (𝐷 ∗ 𝐹) ⊕ (𝐸 ∗ 𝐹), es decir una propiedad distributiva es válida para ⊕ 𝑦 ∗

8.10. Teorema
Sean 𝑚 𝑦 𝑛 enteros no negativos con 𝑚 < 𝑛, 𝑟 = 𝑛 − 𝑚, y sea 𝐻 una matriz booleana de orden
𝑛𝑥𝑟. Entonces la función 𝑓𝐻 : 𝐵 𝑛 → 𝐵 𝑟 , definida por
𝑓𝐻 (𝑥) = 𝑥 ∗ 𝐻, 𝑥 ∈ 𝐵 𝑛
Es un homomorfismo del grupo 𝐵 𝑛 al grupo 𝐵 𝑟
Prueba
Sean 𝑥 y 𝑦 elementos de 𝐵 𝑛 , entonces
𝑓𝐻 (𝑥 ⊕ 𝑦) = (𝑥 ⊕ 𝑦) ∗ 𝐻
𝑓𝐻 (𝑥 ⊕ 𝑦) = (𝑥 ∗ 𝐻) ⊕ (𝑦 ∗ 𝐻), por el teorema anterior
𝑓𝐻 (𝑥 ⊕ 𝑦) = 𝑓𝐻 (𝑥) + 𝑓𝐻 (𝑦)
Por lo tanto, 𝑓𝐻 es un homomorfismo de 𝐵 𝑛 a 𝐵 𝑟
8.11. Matriz de verificación de paridad
8.11.1. Definición.- Diremos que 𝐻 es una matriz de paridad si está definida por
ℎ11 ….. ℎ1𝑟

ℎ21 ….. ℎ2𝑟
. ….. . m
. …… .
. ….. . n
𝐻=
ℎ𝑚1 ….. ℎ𝑚𝑟
1 0 .…. 0
. 1 ….. 0
𝑟 = 𝑛 − 𝑚, 𝑓𝑖𝑙𝑎𝑠 0 …… 0
[ 0 ………0 1 ] 𝑛𝑥𝑟
8.11.2. Definición.-Sea 𝑯 una matriz de paridad donde se define la función de codificación
𝑒𝐻 : 𝐵 𝑛 → 𝐵 𝑟 , asociada a la matriz de paridad si 𝑏 = 𝑏1 𝑏2 … … … . 𝑏𝑚 ∈ 𝐵 𝑚 y
𝑥 = 𝑒𝐻 (𝑏) = 𝑏1 𝑏2 … … . . 𝑏𝑚 𝑥1 𝑥2 … … … . 𝑥𝑟
Donde

𝑥1 ℎ11 … . . ℎ1𝑟
𝑥2 ℎ21 … . . ℎ2𝑟
. . ….. .
. [𝑏1 𝑏2 … … … . 𝑏𝑚 ]1𝑥𝑚 . …… .
. . ….. .
. = . ….. .
. . .…. .
. . ….. .
. . …… .
[𝑥𝑟 ] [ℎ𝑚1 … … ℎ𝑚𝑟 ]𝑚𝑥𝑟
Luego el grupo de código de la función 𝑒𝐻 : 𝐵 𝑛 → 𝐵 𝑟 serán las palabras codificadas por la

función 𝑒.
8.11.3. Corolario
La función de codificación 𝑒𝐻 : 𝐵 𝑚 → 𝐵 𝑛 es un grupo de código si 𝑒𝐻 (𝐵 𝑚 ) = {𝑒𝐻 (𝑏), 𝑏 ∈ 𝐵 𝑚 }
Es un subgrupo de 𝐵 𝑛 .
Ejemplo
Sean 𝑚 = 2, 𝑛 = 5 y la matriz de paridad dado por
1 1 0
0 1 1
𝐻= 1 0 0
0 1 0
[0 0 1]
Determine el grupo de código 𝑒𝐻 : 𝐵 2 → 𝐵 5
Solución
Se tiene que el conjunto 𝐵 2 está compuesto por 22 = 4 combinaciones es decir
𝐵 2 = {00,01,10,11} . Entonces
𝑒(00) = 00𝑥1 𝑥2 𝑥3
Donde
𝑥1 = (00)(10) = 0
𝑥2 = (00)(11) = 0
𝑥3 = (00)(01) = 0
En consecuencia 𝑒(00) = 00000

Ahora 𝑒(01) = 01𝑥1 𝑥2 𝑥3
Donde
𝑥1 = (01)(10) = 0.1 + 1.0 = 0

𝑥2 = (01)(11) = 0.1 + 1.1 = 1
𝑥3 = (01)(01) = 0.0 + 1.1 = 1
En consecuencia 𝑒(01) = 01011
De manera análoga para los elementos 𝑒(10) 𝑒(11) tendremos que
𝑒(10) = 10110 , 𝑒(11) = 11101
Finalmente el grupo de código será 𝑁 = {00000,01011,10110,11101}

Capítulo 9
La teoría de lenguajes y máquinas de estado finito
A continuación presentaremos algunas definiciones respecto a la teoría de lenguajes para luego

definir máquinas de estado finito.
9.1. Alfabeto
9.1.1. Definición.- Un alfabeto es un conjunto finito de símbolos. El símbolo es un primitivo de

la teoría de los lenguajes formales y para representarlos se suelen utilizar o bien las primeras
letras del alfabeto latino o bien dígitos. Por tanto, cualquiera de los conjuntos siguientes es un
alfabeto:
A= {a, b, c} B = {0,1}.
9.1.2. Palabra
9.1.3. Definición.- Una palabra sobre el alfabeto 𝐴 es una sucesión finita de elementos de 𝐴.
Es decir 𝑢 es una palabra sobre 𝐴, si y solo si 𝑈 = 𝑎1 … … … 𝑎𝑛 donde 𝑎𝑖 ∈ 𝐴, ∀𝑖 = 1 … . 𝑛
Ejemplo
Sea 𝐴 = {0,1}, entonces 00111 es una palabra sobre este alfabeto.
9.2. Cadena
9.2.1. Definición.- Una cadena o palabra es una serie arbitrariamente larga de símbolos unidos
por concatenación que representamos disponiendo los diferentes símbolos que la componen en
el orden deseado; por ejemplo: aaabbbccc, es una cadena. Como la definición de cadena es
recursiva, podemos referirnos, si es necesario, a una cadena completa o a una subcadena que
forme parte de una cadena mayor con las letras finales del alfabeto u, v, w, x, y y z. Por tanto,
aaaw o, simplemente, w también son cadenas. Denotamos la cadena vacía con el símbolo ε. La
cadena vacía es el elemento de identidad de la operación de concatenación, de tal modo que

ε ⊕ aaabbb = aaabbb. La operación de concatenación de cadenas no es conmutativa (pero sí
asociativa); por tanto aaabbb ⊕ ab ≠ ab ⊕ aaabbb.
9.3. Clausura sobre el alfabeto A
9.3.1. Definición.- La clausura del alfabeto 𝐴 denotado por 𝐴∗ , el conjunto de todas las palabras
sobre un alfabeto 𝐴, también llamado clausura de kleene.
𝐴∗ =∪ 𝐴𝑖 , 𝑖 = 1,2,3 … … ..
Donde 𝐴𝑖 es el conjunto de todas las cadenas de longitud 𝑖 sobre A
Ejemplo
Sea el alfabeto 𝐵 = {0,1}, calcular 𝐵 ∗
𝐵0 = {𝜀}
𝐵1 = {0,1}
𝐵2 = {00,01,10,11}
𝐵3 = {000,001,010,011,100,101,110,111}
.
.
Luego 𝐵 ∗ = 𝐵 0 ∪ 𝐵1 ∪ 𝐵 2 ∪ 𝐵 3 ∪ … = {ε, 0,1,00,01,10,11000,001,010,011,100,101,110,111 … }
9.4. Longitud de una cadena
9.4.1. Definición.- La longitud de la palabra o cadena 𝑢 es el número de símbolos que contiene

𝑢 y se denota por |𝑢|, es decir si 𝑎1 … … … . 𝑎𝑛 entonces |𝑢| = 𝑛
Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la longitud de una cadena es
igual al “número de símbolos” que contiene; esta proposición está aceptada coloquialmente, sin
embargo, no es estrictamente correcta. Así, en la cadena 01101 sólo hay dos símbolos, 0 y 1,
aunque tiene cinco posiciones para los mismos y su longitud es igual a 5. Sin embargo,
generalmente podremos utilizar la expresión “número de símbolos” cuando realmente a lo que
se está haciendo referencia es al “número de posiciones”. La notación estándar para indicar la
longitud de una cadena w es |w|. Por ejemplo,|011|= 3y| ε |= 0.

9.4.2. Igualdad de cadenas
Dos cadenas son 𝐿1 𝑦 𝐿2 , son iguales si se cumple |𝐿1 | = |𝐿2 | 𝑦 (∀𝑖: 1 ≤ 𝑖 ≤ 𝑛: 𝑎𝑖 = 𝑏𝑖 )
9.4.3. Reversa de una cadena
Sea la cadena 𝐿1 = 𝑎1 … … … . 𝑎𝑛 , su reversa denotada por (𝐿1 )𝑅 , estará dado por
(𝐿1 )𝑅 = 𝑎𝑛 … … … . 𝑎1
9.5. Lenguaje
9.5.1. Definición.- Un lenguaje es un conjunto finito o infinito de cadenas. Los conjuntos

siguientes son, por tanto, lenguajes:
i) L1 = {ε, ab, aabb, aaabbb} L2 = {001, 011,111}.
ii) 𝐿0 = ∅ lenguaje finito vacío
9.5.2. Definición.- (Teoría de lenguajes formales). La Teoría de los lenguajes formales estudia
los lenguajes prestando atención únicamente a sus propiedades estructurales, definiendo clases
de complejidad estructural y estableciendo relaciones entre las diferentes clases.
9.5.2. Definición.- (Teoría de la complejidad computacional). La Teoría de la complejidad

computacional estudia los lenguajes prestando atención a los recursos que utilizaría un
dispositivo mecánico para completar un procedimiento de decisión, definiendo así diferentes
clases de complejidad computacional y las relaciones que existen entre ellas.
9.6. Concatenación de cadenas
Sean 𝑥 e 𝑦 dos cadenas. Entonces, 𝑥𝑦 denota la concatenación de x e y, es decir, la cadena

formada por una copia de x seguida de una copia de y. Dicho de manera más precisa, si x es la
cadena compuesta por 𝑖 símbolos 𝑥 = 𝑎1 𝑎2 … . . 𝑎𝑖 , y es la cadena compuesta por j símbolos y
𝑦 = 𝑏1 𝑏2 … . . 𝑏𝑗 , entonces 𝑥𝑦 es la cadena de longitud i+ j: 𝑥𝑦 = 𝑎1 𝑎2 … . . 𝑎𝑖 𝑏1 𝑏2 … . . 𝑏𝑗 .
Además operación de concatenación de los lenguajes 𝐿1 𝑦 𝐿2 está definido por
𝐿1 . 𝐿2 = {𝑤1 . 𝑤2 ∈ 𝐴∗ /𝑤 ∈ 𝐿1 𝑦 𝑤 ∈ 𝐿2 }, donde de acuerdo a lo definido se omite el punto.

9.7. Propiedades de concatenación
a) 𝐿1 . 𝐿2 es una cadena sobre el alfabeto 𝐴
b) 𝐿1 . 𝜀 = 𝜀𝐿1 = 𝐿1
c) |𝐿1 . 𝐿2 | = |𝐿1 | + |𝐿1 |
d) 𝐿1 . 𝐿2 ≠ 𝐿2 . 𝐿1, no es conmutativa (puede suceder en algunos casos)
e) 𝐿1 . 𝐿1 = 𝐿1 2 (potencia cuadrada de la cadena 𝐿1 )
f) potencia k-esima de la cadena 𝐿1
𝐿0 = {𝜀}
𝐿1 = 𝐿1
𝐿2 = 𝐿1 . 𝐿1
.
.
.
𝐵𝑘 = 𝐿1 . 𝐿1 . 𝐿1 . 𝐿1 … … … 𝐿1 (k-veces)
Ejemplo
Sean x = 01101 e y = 110. Entonces xy = 01101110 e yx = 11001101. Para cualquier cadena w,

tenemos las ecuaciones ε w = w ε = w. Es decir, ε es el elemento neutro de la concatenación,
dado que su concatenación con cualquier cadena proporciona dicha cadena como resultado (del
mismo modo que 0, el elemento neutro de la suma, puede sumarse a cualquier número x y
proporciona x como resultado).
9.8. Lenguajes regulares
Los lenguajes regulares sobre un alfabeto dado 𝐴 son todos los lenguajes que se pueden formar
a partir de los lenguajes básicos 0, {𝜀}, {a} 𝑎 ∈ 𝐴 , por medio de las operaciones de unión,
concatenación y estrella de Kleene (clausura de 𝐴)
9.9. Operaciones con lenguajes
Sean dos lenguajes 𝐿1 𝑦 𝐿2 , sobre 𝐴, donde 𝐿1 ⊆ 𝐴∗ , 𝑦 𝐿2 ⊆ 𝐴∗ y se define las operaciones de

unión, intersección, diferencia y complemento entre los lenguajes 𝐿1 𝑦 𝐿2 de la siguiente forma.

a) 𝐿1 ∪ 𝐿2 = {𝑤 ∈ 𝐴∗ /𝑤 ∈ 𝐿1 𝑜 𝑤 ∈ 𝐿2 }
b) 𝐿1 ∩ 𝐿2 = {𝑤 ∈ 𝐴∗ /𝑤 ∈ 𝐿1 𝑦 𝑤 ∈ 𝐿2 }
c) 𝐿1 − 𝐿2 = {𝑤 ∈ 𝐴∗ /𝑤 ∈ 𝐿1 𝑦 𝑤 ∉ 𝐿2 }
d) ̅̅̅
𝐿1 = {𝑤 ∈ 𝐴∗ / 𝑤 ∉ 𝐿1 } = 𝐴∗ − 𝐿1
Ejemplo
Sean 𝐿1, 𝐿2 los lenguajes sobre el alfabeto 𝐴 = {𝑎, 𝑏, 𝑐} definido por
𝐿1 = {𝑎𝑖 𝑏 𝑗 𝑐 𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0}
𝐿2 = {𝑎𝑖 𝑐 2𝑖 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑖 ≥ 0}
Calcular
a) 𝐿1 ∪ 𝐿2 c) 𝐿1 − 𝐿2 e) ̅̅̅
𝐿1
b) 𝐿1 ∩ 𝐿2 d) 𝐿1 . 𝐿2
Solución
a) 𝐿1 ∪ 𝐿2 = 𝐿1 = {𝑎𝑖 𝑏 𝑗 𝑐 𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0}
b) 𝐿1 ∩ 𝐿2 = {𝑎𝑖 𝑐 2𝑖 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑖 ≥ 0}
c) 𝐿1 − 𝐿2 = {𝑎𝑖 𝑏 𝑗 𝑐 𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖 ≥ 0, 𝑗 > 0}
d) 𝐿1 . 𝐿2 = {{𝑎𝑖 𝑏 𝑗 𝑐 𝑞 𝑎𝑛 𝑐 2𝑛 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗, 𝑛 ≥ 0}}

e) ̅̅̅
𝐿1 = {𝑤 𝑡𝑎𝑙𝑞𝑢𝑒 𝑤 ∈ 𝐴∗ , 𝑦 𝑤 ≠ 𝑎𝑖 𝑏 𝑗 𝑐 𝑞 𝑦 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0 }
9.10. Estado de una maquina
9.10.1Definición.- La condición interna completa de la máquina y de toda su memoria en un

instante particular, constituye el estado de la maquina en ese instante.
9.11. Máquinas de estado finito
Una máquina de estados finitos en un modelo abstracto para la manipulación de símbolos, nos
permiten saber si una cadena pertenece a un lenguaje o nos pueden generar otro conjunto de
símbolos como resultado.

Es un modelo matemático de una maquina con memoria que tiene un conjunto de estados (valores
internos), que puede recibir símbolos de entrada y obtener símbolos de salida
S
I O
f g
Una máquina de estado finito M es dado por 𝑀 = (𝑆, 𝐼, 𝑂, 𝑓, 𝑔, 𝑆0 ), donde
I= {conjunto de entradas finito (símbolos de entrada) o vocabulario de entrada}
O= {conjunto de salidas finito (símbolos de salida) o vocabulario de salida}
S= {conjunto de estados (finitos)}
S0 = {estado inicial}
𝑓: 𝐼𝑥𝑆 → 𝑆 , es la función de transición o función de estado siguiente y para un par del conjunto
𝐼𝑥𝑆 devuelve un estado perteneciente al conjunto 𝑆
𝑔: 𝐼𝑥𝑆 → 𝑂, es la función de salida y para un par del conjunto 𝐼𝑥𝑆 devuelve un símbolo de salida
del conjunto 𝑂
Ejemplo
Sea 𝐼 = {𝑎, 𝑏} entradas posibles 𝑂 = {0,1} conjunto de salidas y 𝑆 = {𝑠0 , 𝑠1 }, conjunto de

estados.
La tabla de transición de datos se muestra en la siguiente tabla.
Estados Función de estados Función de salida g

siguiente f (Símbolos de salida)
𝒂 𝒃 𝒂 𝒃
𝑠0 𝑠0 𝑠1 0 1
𝑠1 𝑠1 𝑠1 1 0
𝑓(𝑠0 , 𝑎) = 𝑠0 𝑔(𝑠0 , 𝑎) = 0
𝑓(𝑠0 , 𝑏) = 𝑠1 𝑔(𝑠0 , 𝑏) = 1
𝑓(𝑠1 , 𝑎) = 𝑠1 𝑔(𝑠1 , 𝑎) = 1
𝑓(𝑠1, 𝑏) = 𝑠1 𝑔(𝑠1 , 𝑏) = 0

9.12. Diagrama de estados
Es un método grafico para describir una máquina de estado finito. Es análogo a un dígrafo.
Ejemplo
Sea la tabla de estados mostrados en tabla siguiente
Estados Función de estados Función de salida g

siguiente f (Símbolos de salida)
𝟎 𝟏 𝟎 𝟏
𝑠0 𝑠1 𝑠0 0 0
𝑠1 𝑠2 𝑠1 1 1
𝑠2 𝑠2 𝑠0 0 1
El diagrama de estados estara dado por el grafico mostrado
𝑓(𝑠0 , 0) = 𝑠1 𝑔(𝑠0 , 0) = 0
𝑓(𝑠1 , 0) = 𝑠2 𝑔(𝑠1 , 0) = 1
𝑓(𝑠2 , 0) = 𝑠2 𝑔(𝑠2 , 0) = 0
𝑓(𝑠0 , 1) = 𝑠0 𝑔(𝑠0 , 1) = 0
𝑓(𝑠1 , 1) = 𝑠1 𝑔(𝑠1 , 1) = 1
𝑓(𝑠2 , 1) = 𝑠0 𝑔(𝑠2 , 1) = 1
Estado Salida

Ejemplo aplicativo
Supongamos que una máquina expendedora tiene dos tipos de productos A y B. El precio de cada
producto es de 10 céntimos. La máquina admite únicamente monedas de 5 y 10 céntimos y
devuelve el cambio necesario. Dispone de un botón rojo que expide el producto A y uno verde
que hace lo mismo con el producto B. Elena quiso comprar el producto A y para ello introdujo
consecutivamente dos monedas de 5 céntimos. Luego apretó el botón rojo y obtuvo el producto
deseado. Representemos el proceso con una tabla, donde 𝑡0 es el instante inicial cuando inserta
su primera moneda y 𝑡𝑖 con 𝑖 = 1,2,3, son los instantes posteriores:
𝑡0 𝑡1 𝑡2 𝑡3
Estado 𝑠0 𝑠1 𝑠2 𝑠0
Entrada 5 5 R
Salida nada nada A
La máquina está en un estado de espera en el estado 𝑠0 . Espera que un cliente comience a insertar
monedas hasta un total de 10 céntimos o más y oprima el botón para obtener el producto deseado.
Si en cualquier momento del proceso, el total de monedas insertadas supera los diez céntimos, la
máquina devuelve el cambio necesario antes de que el cliente oprima el botón correspondiente.
En el instante 𝑡0 , Elena inserta su primera moneda de 5 céntimos. No recibe nada pero en el
instante siguiente (𝑡1 ) la máquina está en el estado 𝑠1 (tiene almacenados cinco céntimos). En
este instante 𝑡1 , la máquina no devuelve nada pero, al depositar una nueva moneda de 5 céntimos,
en el instante 𝑡2 , la máquina se encuentra en un nuevo estado 𝑠2 (tiene almacenados diez
céntimos). Elena todavía no recibe nada puesto que la máquina no sabe qué tipo de producto
quiere. Al oprimir el botón rojo en el instante 𝑡2 , la máquina expide el producto A y en el instante
siguiente 𝑡3 se coloca de nuevo en el estado inicial 𝑠0 (ningún céntimo almacenado). Las
principales características de esta máquina son:
En un instante dado, la máquina sólo puede estar en un estado de un conjunto finito de estados
internos posibles.
La máquina sólo acepta un número finito de entradas (en el ejemplo, monedas de cinco y diez
céntimos, botones rojo y verde).

Mediante cada combinación de entrada y estado interno, se produce una salida y un estado
siguiente. El conjunto de salidas, para nuestra máquina es nada, monedas de cinco y diez
céntimos y productos A y B.
Los procesos de la máquina son secuenciales y se producen en instantes distintos. La máquina
es determinista ya que la salida queda determinada por el estado y la entrada.

Separata de Matematica Discreta

Cargado por

Copyright:

Formatos disponibles

Separata de Matematica Discreta

Cargado por

Información del documento

Título original

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

Separata de Matematica Discreta

Cargado por

Copyright:

Formatos disponibles

MATEMATICA DISCRETA

(Material de apoyo de clase)

Facultad de Ingeniería Industrial y de Sistemas

Mg.Osmar A. Bermeo Carrasco

Osmar A. Bermeo Carrasco Página 1

Osmar A. Bermeo Carrasco Página 2

Osmar A. Bermeo Carrasco Página 3

Los sistemas numéricos que más se utilizan en el diseño de sistemas digitales y la

Es decir 𝑁 = (𝑎𝑛−1 𝑎𝑛−2 𝑎𝑛−3 … . . 𝑎2 𝑎1 𝑎0. 𝑎−1 𝑎−2 … … 𝑎−𝑚 )𝑏

Binario: 𝑁 = (1101.101)2 Pesos: 23 22 21 20 2−1 2−2 2−3 son potencias de 2

Octal: 𝑁 = (436.43)8 Pesos: 82 81 80 8−1 8−2 son potencias de 8

Cualquier número N con base b se puede escribir como un polinomio de la forma.

𝑁 = (𝑎𝑛−1 𝑏 𝑛−1 + ⋯ … + 𝑎2 𝑏 2 + 𝑎1 𝑏1 + 𝑎0 𝑏0 + 𝑎−1 𝑏−1 𝑎−2 𝑏−2 … … 𝑎−𝑚 𝑏−𝑚 ) = ∑𝑛−1

n: Numero de dígitos enteros m: Numero de dígitos fraccionarios

Osmar A. Bermeo Carrasco Página 4

Binario: N= (1001.11)2 = 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20 + 1 * 2-1 + 1 * 2-2

Decimal: N= (123.45)10 = 1 * 102 + 2 * 101 + 3 * l00 + 4 * 10-1 + 5 * 10-2

Hexadecimal: N= (3A.2F)16 = 3 * 161 + A * 160 + 2 * 16-1 + F * 16-2

Donde: A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15

Es un sistema de numeración posicional su base es 2 y sus elementos son 0 y 1, se

Se describe como la unidad básica de almacenamiento de información, siendo equivalente a ocho

Unidad: Núm. bits Ejemplo:

Osmar A. Bermeo Carrasco Página 5

Nombre Abrev. Factor

kilo K 210 = 1024

mega M 220 = 1 048 576

giga G 230 = 1 073 741 824 1 byte: 8 bits

1 Kilobyte: 1024 bytes

zetta Z 270 = 1 180 591 620 717 411 303 424

1.3.-El sistema octal

El sistema numérico en base 8 se llama octal y utiliza los dígitos 0 a 7.

En informática, a veces se utiliza la numeración octal en vez de la hexadecimal. Tiene la ventaja de

Un número octal puede ser:

Para obtener la representación decimal de un número Octal se puede utilizar

Osmar A. Bermeo Carrasco Página 6

1.4.-Conversión entre los sistemas binario y octal

Donde, de derecha a izquierda:

1112 = 78, 1002 = 48, 1012 = 58 y 0012 = 18.

Donde, de derecha a izquierda:

08 = 0002, 28 = 0102, 48 = 1002 y 38 = 0112

La base de operaciones de una microcomputadora está organizada en 8, 16 ó 32 cifras binarias, las

DECIMAL BINARIO OCTAL

Osmar A. Bermeo Carrasco Página 7

El sistema hexadecimal es un sistema de numeración vinculado a la informática, ya que las

En un sistema hexadecimal, necesitamos 16 símbolos. Ya que somos muy buenos manejando

Decimal Binario Octal Hexadecimal

Osmar A. Bermeo Carrasco Página 8

Para su conversión al sistema decimal, aplicando

= 1*4096+ 12*256+ 6*16+ 14*1+ 3*1/16

A=10, B=11, C=12, D=13, E=14 y F=15.

1.6.-Conversión entre los sistemas binario y hexadecimal.

La equivalencia entre las cifras hexadecimales y binarias se muestra en la tabla anterior. En

Donde (de derecha a izquierda):

10112 = B16, 10102 = A16, 11012 = D16 y 0102 = 216

Donde (de derecha a izquierda):

216 = 00102, 316 = 00112, E16 = 11102 y F16 = 11112

Osmar A. Bermeo Carrasco Página 9

1.7.-Conversión del sistema numérico decimal al resto de los sistemas de numeración.

El número resultante sería:

= 14096+ 12256+ 616+ 141+ 3*1/16