Estructuras Discretas by Wilber Ramos PDF
Estructuras Discretas by Wilber Ramos PDF
Estructuras Discretas by Wilber Ramos PDF
Escribı́ este libro con el fin de ofrecer una introducción de los Fundamentos
Matemáticos para la Ciencia de la Computación, que estimula a pensar que las
Matemáticas no son sólo una deducción de teoremas, sino también una meto-
dologı́a de modelamiento.
Por lo tanto, la cuestión es de artı́cular matemáticamente el fenómeno de
la Computación. Se que ésta es una tarea compleja, que demanda reflexiones
a propósito del fenómeno de la computación y de la metodologı́a matemática;
comprensiones difı́ciles, que en gran medida aún deben ser elaboradas; pero
que hoy, cuando la computación precisa una Ingenierı́a de corte cientı́fico, son
ineludibles.
El término “Matemáticas Discretas”se utiliza extensamente para describir
un tipo de Matemáticas donde no tiene cabida propiedades tales como cercanı́a
y suavidad, ideas fundamentales del cálculo. Se trata de un curso hı́brido, cuyo
contenido fundamental es de matemáticas, aunque muchas de sus aplicaciones
pertenecen a la Ciencia de la Computación.
Para la comprensión integral de la ciencia de la computación se requiere
comprender muchos tópicos de Matemáticas Discretas, entre los cuales, en un
nivel de introducción, creo que los mas adecuados son: algoritmos, conjuntos,
inducción matemática, relaciones y estructuras de orden.
Agradezco a la Universidad Católica San Pablo por su incondicional apoyo.
Fue Luis Dı́az Basurco, quien sugirió en primer lugar que deberı́a escribir un
texto de Matemáticas Discretas para estudiantes del segundo semestre del Pro-
grama Profesional de Ingenierı́a Informática de la USP que el entusiastamente
dirige. Una vez puesta en marcha mi proyecto (por su puesto) duró mas de lo
que se esperaba. La composición final fue efectuada por Abigail Parisaca Var-
gas y Liliana Mamani Sánchez, que trabajaron en LaTeX apoyados por Jesús
Mena Chalco en la composición de gráficos. A todos ellos mi más sincero agra-
decimiento, agradecimiento que hago extensivo a todos mis alumnos que han -
¿deberı́a decir sufrido o disfrutado? - de mis cursos de Matemáticas Discretas y
que han contribuı́do decisivamente a su depuración y mejora.
3
4
Índice general
1. Lógica de predicados 7
1.1. Componentes sintácticos de la Lógica de Predicados . . . . . . . 7
1.2. Interpretación y validez . . . . . . . . . . . . . . . . . . . . . . . 12
1.3. Derivaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4. Teorema de deducción . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5. Lógica de ecuaciones . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5.1. Regla de sustitución . . . . . . . . . . . . . . . . . . . . . 25
1.6. Forma normal PRENEX . . . . . . . . . . . . . . . . . . . . . . . 28
1.7. Lista de ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3. Relaciones 69
3.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.2. Manipulación de relaciones . . . . . . . . . . . . . . . . . . . . . 72
3.2.1. Relación Inversa . . . . . . . . . . . . . . . . . . . . . . . 72
3.2.2. Composición de Relaciones . . . . . . . . . . . . . . . . . 73
3.3. Trayectorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4. Propiedades de las relaciones . . . . . . . . . . . . . . . . . . . . 79
3.5. Particiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.6. Cerradura de las relaciones . . . . . . . . . . . . . . . . . . . . . 85
3.6.1. Algoritmo de Warshall . . . . . . . . . . . . . . . . . . . . 87
3.7. Lista de ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4. Estructuras de Orden 93
4.1. Conjuntos Parcialmente ordenados . . . . . . . . . . . . . . . . . 93
4.2. Látices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3. Álgebras Booleanas . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4. Redes Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5
6 ÍNDICE GENERAL
Lógica de predicados
• Antonio no es tonto.
• Sólo los tontos se dejan engañar por los vendedores ambulantes.
• Antonio se deja engañar por Juan.
De estas frases uno deberı́a poder concluir que Juan no es vendedor am-
bulante.
Para evitar las cosas triviales se considera que el dominio es diferente del
vacı́o.
7
8 CAPÍTULO 1. LÓGICA DE PREDICADOS
• ¿Qué se afirma?
• ¿De quién se afirma?
• Mayte es bonita.
Por sustitución
Por cuantificación
∀xi P (x1 , x2 , a3 . . . x1 . . . xn )
∃xi P (x1 , x2 , a3 . . . xi . . . xn )
a) P (U, O, S) .
b) P (X, M, D), Se puede cuantificar.
c) P (X, M, D), No se puede cuantificar.
d) ∀x P (X, M, D).
e) ∃x P (X, M, D).
bLa aparición de x como libre en los casos d y c puede entenderse en dos sentidos:
1. En el sentido general (caso b), x representa un elemento genérico del do-
minio, en este sentido b y d tienen el mismo contenido de información.
2. En el sentido condicional (caso c), x es una forma de denominar en ele-
mento incógnito del dominio. En este sentido x representa un elemento
único desconocido.
Observación 1.1.3. El nombre de un predicado seguido por una lista de térmi-
nos se denomina una formula atómica. Las formulas atómicas pueden combinarse
mediante conexiones lógicas como si fuesen proposiciones. ∀x y ∃x, deben tra-
tarse como conexiones unarias los cuantificadores tienen una propiedad superior
a la de todas las conexiones binarias.
10 CAPÍTULO 1. LÓGICA DE PREDICADOS
Solución
Ejemplo 1.1.5.
Z x
(P (x) → Q(x)) ≡ P (a) → Q(a)
a
Z y
(P (y) ∨ Q(y)) ≡ P (b) ∨ Q(b)
b
Z a
(Q(y)) ≡ Q(a)
y
Definición R1.3. Se dice que una expresiónR es una variante de ∀xA si tiene la
x x
forma de ∀y y A. Análogamente ∃xA y ∃y y son variantes una de otra.
c) Nadie es perfecto.
Solución
El dominio es el conjunto de todas las personas
a) M (t1 , t2 ) = t1 es madre de t2 .
∀y, ∃xM (x, y)
b) K(t1 , t2 ) = t1 conoce a t2
∃x ∀yK(x, y)
En español hay muchos cuantificadores tales como “unos pocos”, “la ma-
yorı́a”y “alrededor de la tercera parte”que resultan útiles en el lenguaje
usual, pero que no son lo suficientemente precisos para utilizarlos en lógica
de predicados.
La particularización sólo afecta a variables libres. RConcretamente si A es
x
una expresión, particularización de A de x en t ( y A) sólo afecta a las
apariciones libres de la variable x.
Ejemplo 1.1.7.
Z x
∀xP (x) ≡ ∀xP (x)
y
Dos cosas sólo serán idénticas si ambas se tratan idénticamente. Esto im-
plica que si una variable aparece tanto libre como ligada, tenemos de hecho
dos variables que casualmente poseen el mismo nombre.
Podemos considerar que las variables ligadas son locales para el ámbito
del cuantificador.
M (t1 , t2 ) = t1 es madre de t2
∃xM (x, y)
Y es madre de y (absurdo)
M (J, M ) es verdadero
Observación 1.1.5. Si todas las apariciones de x en una expresión A están
ligadas, diremos que A no contiene a x libre. Si A no contiene a x libre, entonces
el valor de verdad de A no cambia si x se particulariza con una constante
individual. En este sentido A es independiente de x.
∀P (x)
P (Oscar)
A(t1 , t2 ) = t1 admira a t2
∃x∀yA(x, y)
Supongamos la siguiente asignación:
R E L ∀yA(x, y) ∃yA(x, y)
R V V F F V
E F F V F V
L F V F F V
∀yA(x, y) F F F F
∃yA(x, y) V V V V
Por lo tanto:
∃x∀yA(x, y)
Existe alguien que admire a todo el mundo: F
∀x∀yQ(x, y) ≡ ∀y∀Q(x, y)
∃x∃yQ(x, y) ≡ ∃y∃xQ(x, y)
∀xR ≡ ∃xR ≡ R
14 CAPÍTULO 1. LÓGICA DE PREDICADOS
Solución
V →A≡A
F →A≡V
Válido
A→B No es válida
V F
16 CAPÍTULO 1. LÓGICA DE PREDICADOS
P (t1 , t2 ) = t1 es madre de t2
absurdo
Demostración.
a, b P (a) = V
P (b) = V
∀xP (x) = V
∀x¬P (x) = F
1.3. DERIVACIONES 17
1.3. Derivaciones
Rx
La expresión ∀xA ⇒ t A es válida si la sustitución x = t no da a lu-
gar una colisión de variables. En otras palabras t no debe transformarse
en una variable ligada de ningún cuantificador que pudiera quedar. Esta
implicación se puede convertir en una regla de inferencia en la siguiente
forma:
R∀xA
x
t A
∀x(gato(x) → tieneCola(x))
gato(Tom) → tieneCola
Solución
Demostración.
H(t1 ) = t1 es humano
M (t1 ) = t1 es mortal
Demostración.
Padre (t1 , t2 ) = t1 es padre de t2
Hijo (t1 , t2 ) = t1 es hijo de t2
Hija (t1 , t2 ) = t1 es hijo de t2
Demostración.
CC (t1 ) = t1 es alumno de CC
Programa (t2 ) = t1 le gusta la programación
1. ∀x CC (x) Premisa
2. ∀x( CC (x) → Prog (x)) Premisa
Z x
3. CC (x) P.U (1)
Zxx
4. CC (x) → Prog (x) P.U (2)
x
5. Prog (x) M.P (3,4)
6. ∀xProg (x) G.U.(5)
1.4. TEOREMA DE DEDUCCIÓN 19
Solución
Demostración.
Solución
E(t1 ) = t1 ha estudiado
A(t2 ) = t2 ha aprobado
20 CAPÍTULO 1. LÓGICA DE PREDICADOS
P (x, y, z) → P (y, x, z)
P (x, 0, x)
P (0, x, x)
Solución
Demostración. Observar que x, y, z son variables verdaderas
Demostración.
M (t1 , t2 ) ≡ t1 es la madre de t2 .
H(t1 , t2 ) ≡ t1 es la hermana de t2 .
T (t1 , t2 ) ≡ t1 es la tı́a de t2 .
Demostración.
R∃xA
x
b
A
Demostración.
1. ∃x(G(x) Premisa
2. ∀x(G(x) → R(x)) Premisa
3. G(b) PE (1)x := b
4. G(b) → R(b) PU (2)x := b
5. R(b) MP (3,4)
6. ∃xR(b) G.E. (5)
1.4. TEOREMA DE DEDUCCIÓN 23
Ejemplo 1.4.9.
Considere la frase:
R(1)xy (x = x) ≡y = x
R(2)xy (x = x) ≡x = y
R(3)xy (x = x) ≡x = y
Solución
R(1)x+1
2y (x < x + 1) ≡ x < 2y
∀x∀y(x = y → y = x)
1. x = y ∧ y = z Premisa
2. x = y L.S (1)
3. y = z L.S (1)
4. x = z R(1)yx (y = z) del ejemplo anterior es conmutativa
5. x = y ∧ y = z → x = z con un supuesto previo
A⊢B→C T. Deducción
A, B ⊢ C
A, B ⊢ C A⊢B→C
26 CAPÍTULO 1. LÓGICA DE PREDICADOS
Solución
1. s > 3i Premisa
2. i = 10 Premisa
3. s > 3x10 R(1)i10 (s > 3i)
γ) El hecho de que ahora existe un individuo, pero uno solo que tiene la
propiedad p se puede expresar de la forma:
∃x(P (x) ∧ ∀y(P (y) → y = x) ≡ ∃!xP (x)
∃xP (x) ∧ ∀x∀y(P (x) ∧ P (y) → x = y) ≡ ∃!xP (x)
Ejemplo 1.5.5. Para las siguientes expresiones.
a) “Sólo Juan podrı́a haber olvidado la reunión”
b) “la universidad tiene exactamente un rector”
c) “Todas los paı́ses tienen exactamente una capital”
solución
∀x (olvidado(x) → x = J)
∃x∃ySiguiente(x, y) ∧ Cine(x)
b. D = N
P roducto(t1 , t2 , t3 ) = t1 ∗ t2 es igual a t3
P rimo(t1 ) = t1 es primo
∃ψ Igual(ψ(a), b)
28 CAPÍTULO 1. LÓGICA DE PREDICADOS
Ejemplo 1.6.1.
A → B = ¬A ∨ B
¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B
¬∀xA(x) ≡ ∃x¬A(x)
¬∃xA(x) ≡ ∀x¬A(x)
x no esta libre en A.
∗2 La formula parcial conectada contiene libre la variable cuantificada.
En este caso, las expresiones serı́an del tipo:
Ejemplo 1.6.2.
Eliminación de la negación
7. Demostrar:
(P (x) → Q(y)) ∧ (Q(y) → R(z)) → (P (z) → Q(z)) no es válida.
8. En el dominio de los animales, ¿Cómo traducirı́a las expresiones siguien-
tes?
a) Todos los leones son depredadores.
b) Algunos leones viven en África.
c) Sólo rugen los leones.
d) Algunos leones comen cebras.
e) Algunos leones sólo comen cebras.
1.7. LISTA DE EJERCICIOS 31
Razonamiento: Lógico -
Matemático
2.1. Introducción
Comenzaremos con el concepto más fundamental en computación: el de al-
goritmo.
El estudio de los algoritmos comenzó como una tarea de matemáticas; de he-
cho, la búsqueda de algoritmos era una actividad importante de las matemáticas
mucho antes de que se inventaran las computadoras actuales, y el objetivo prin-
cipal de dicha búsqueda era decubrir un conjunto único de dichas instrucciones
para resolver cualquier problema de cierto tipo.
El nombre algoritmo proviene del matemático persa del siglo IX Alkhowãriz-
mi. El algoritmo más famoso de la historia procede de un tiempo anterior al de
los griegos; se trata del algoritmo de Euclides para calcular el máximo común
divisor de dos enteros.
Una vez descubierto un algoritmo para resolver un problema, el siguiente pa-
so es representar el algoritmo de modo que se pueda comunicar a una máquina o
a otras personas. Esto significa que debemos transformar el algoritmo conceptual
en un conjunto claro de instrucciones y representar ésta última sin ambigúedad.
Los estudios que se ocupan de esto se basan en nuestro conocimiento del lenguaje
y la gramática, y ha dado lugar a un gran número de esquemas para representar
algoritmos (llamados lenguajes de programación) fundados en diversos enfoques
del proceso de programación (denominados paradigmas de programación).
La figura 2.1 representa la evolución histórica de los paradigmas de progra-
mación:
33
34 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
Funcional
Lisp ML Scheme
GPSS Prolog
Declarativo
2.2. Algoritmos
Definición 2.1. Un algoritmo es una secuencia finita de pasos ejecutables que,
de seguirla, debe terminar en un momento.
♠ El empleo del término no ambiguo, significa que, en cada paso, la acción
que debe realizarse a continuación debe quedar determinada de manera
única por la construcción por sı́ sola debe bastar para determinar la acción
deseada.
♠ El requisito de que todos los pasos del algoritmo sean ejecutables descar-
ta la posibilidad de que un algoritmo contenga pasos cuya ejecución sea
imposible. Los cientı́ficos de la computación emplean el término efectivo
para capturar este concepto de ser ejecutable.
♠ El requisito de que una secuencia de pasos terminará no es superflúo pues
que la lista de instrucciones contenga sólo un número finito de pasos no
significa necesariamente que la tarea concluirá alguna vez si se siguen las
instrucciones.
♠ El concepto de calcular la solución de un problema implica la capacidad
de reconocer cuándo ya se obtuvo la solución, para entonces terminar
el proceso de cómputo. Ası́ pues, en este sentido, sólo nos interesan los
procesos de cómputo que tarde o temprano terminan.
Observación 2.2.1. Recuerde que
a) Un algoritmo en si es algo puramente conceptual, de modo que para co-
municar un algoritmo a una persona o a un computador debemos de hallar
una forma de representarlo.
b) La distinción entre sintaxis y semántica es primordial en el tema de la
representación de algoritmos. El término sintaxis se refiere a la represen-
tación, en tanto que semántica se refiere al concepto que se representa.
La estructura sintáctica “aire”sólo un conjunto de letras; pero el objeto
representado, la semántica, es una sustancia gaseosa que rodea el planeta.
Un objetivo importante de la representación de algoritmos es asegurar
que la sintaxis refleje con precisión la semántica deseada. Otro aspecto
importante es que la sintaxis debe reflejar la semántica subyacente de
manera accesible. La búsqueda de estructuras sintácticas para representar
algoritmos de manera accesible y no ambigua es una labor continua en las
ciencias de la computación.
36 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
1 if (condicion)
2 actividad - verdadero
3 else
4 actividad -falso
1 while (condicion)
2 repetir-actividad
Procedure-Maximo(n1 , n2 , n3 )
1 max := n1
2 if n2 > max
3 max := n2
4 if n3 > max
5 max := n3
6 return (max)
Procedure Area-Triangulo(a, b, c)
1 p := (a + b + c)/2 // Semiperı́metro
2 if (p > a) and (p > b) and (p > c)
3 Area := (a × (p − a) × (p − b) × (p − c))1/2
4 else
5 print (”Datos no forman un triángulo”)
6 return (Area)
7 end Area-Triangulo
Procedure Cuadrado(n)
1 x := n
2 i := 1
3 while (i 6= n)
4 x := x + n
5 i := i + 1
6 return (x)
7 end Cuadrado
Procedure Cuadrado2(N )
1 x := n
2 i := 1
3 until (i < n)
4 x := x + n
5 i := i + 1
6 return (x)
7 end Cuadrado2
Procedure Suma(n)
1 Sum := 0
2 for i := 1 to n
3 Sum := Sum + 1/(8 ∗ i + 1)
4 return (Sum)
5 end Suma
Procedure Ordenacion-Burbuja(A)
1 for i := 1 to length(A) − 1
2 for j := 1 to length(A) − i
3 if A[j] > A[j + 1]
4 intercambiar A[j] con A[j + 1]
5 end Ordenacion-Burbuja
Fase 3:
Entrada: a, b, c
Salida: R1 , R2
2.3. Conjuntos
Muchos conceptos en la matemática y en la ciencia de la computación pueden
ser convenientemente expresados en el lenguaje de los conjuntos.
Las definiciones son importantes en cualquier ciencia, pues contribuyen a
una comunicanión sin ambigúedad. Por lo tanto, tener un punto de partida
para nuestras definiciones en el cual los significados estén claros es de suma
importancia, nuestro punto de partida será la idea de un conjunto.
Aún cuando revisemos aquı́ los principales conceptos que se utilizan en la
Teorı́a de Conjuntos, suponemos que el lector ya está familiarizado con el len-
guaje de los conjuntos.
Un conjunto es una colección ordenada de objetos distintos que por lo general
se denominan elementos o miembros. Por ejemplo tenemos los conjuntos:
A = {a, b, c}
B = {x/x es la capital del Perú}
N = {0, 1, 2, 3, 4, . . .}
Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}
Z+ = {1, 2, 3, 4, . . .}
Q = Conjunto de todos los números racionales.
R = Conjunto de todos los números reales.
C = Conjunto de todos los números comlejos.
φ = {} “Conjunto vacı́o”.
|P (A)| = 2n
Si A, B ∈ P (U ) se define la:
A ∪ B = {x ∈ U/x ∈ A ∨ x ∈ B} Unión
A ∩ B = {x ∈ U/x ∈ A ∧ x ∈ B} Intersección
A = {x ∈ U/x ∈ A 6∈ A} Complemento
A−B = A∩B Diferencia
A ⊕ B = (A − B) ∪ (B − A) Diferencia simétrica
A △ B = (A ∪ B) − (A ∩ B)
Las operaciones definidas para realizarse con conjuntos satisfacen las siguien-
tes propiedades:
Propiedades Idempotentes
A∪A = A
A∩A = A
Propiedades Conmutativas
A∪B = B∪A
A∩B = B∩A
Propiedades Asociativas
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C
Propiedades Distributivas
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ B)
Propiedades del Complemento
A = A
A∪A = U
A∩A = φ
φ = U
U = φ
Leyes de Morgan
)
A∪B = A∩B
Leyes de Morgan
A∩B = A∪B
Propiedades del Conjunto Universal
A∪U = U
A∩U = A
Propiedades del Conjunto Vacı́o
2.3. CONJUNTOS 45
A∪φ = A
A∩φ = φ
Propiedades de Absorción
A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A
Observe que los nombres y las formas de éstas propiedades son muy parecidas
con las equivalencias lógicas de la lógica de proposiciones. Veremos más adelante
que ésta semejanza no es una coincidencia.
El producto cartesiano de dos conjuntos A y B, representado por A × B,
es el conjunto de todos los pares ordenados de la forma (a, b), donde a ∈ A y
b ∈ B, observe que por lo general, A × B 6= B × A ya que la disposición de los
componentes de un par ordenado es significativa.
Es posible generalizar el concepto del producto cartesiano de conjuntos pa-
ra obtener el producto de más de dos conjuntos. Por ejemplo, A × B × C =
{(a, b, c)/a ∈ A, b ∈ B, c ∈ C}. Es común utilizar la abreviatura A2 para repre-
sentar A × A. Ası́, de manera general An representará la colección de todas las
n-tuplas de elementos de A.
Dados los conjuntos A y B, una función de A en B es un subconjunto de
A×B, tal que cada elemento de A aparece como el primer elemento de uno y sólo
uno de los pares ordenados de la función. Si f es una función de A en B diremos,
que A es el dominio de f . El conjunto de elementos que aparece como la segunda
componente de los pares ordenados de una función se denomina contradominio
o rango de f . Si cada elemento de B se halla en el rango de f , diremos que f es
una función sobreyectiva. Si cada miembro del rango de f está asociado a sólo
un elemento del dominio, diremos que f es una función inyectiva. Las funciones
que sean inyectivas y sobreyectivas las llamaremos biyectivas.
Por lo general, los elementos del dominio de una función se consideran como
entradas para la función y los elementos del rango como los valores de salida.
Este concepto de entrada y salida origina la notación f : A → B, lo cual
representa una función f de A en B. Dada una función f : A → B, representamos
como f (x) al valor de salida asociado a la entrada x. Por ejemplo, suponga que
f : N → N es la función que consiste en los pares ordenados de la forma (n, n2 ),
es decir f (n) = n2 para cada n ∈ N . Esta función es inyectiva pero no es
sobreyectiva.
Consideremos ahora el concepto intuitivo del número de elementos en un
conjunto.
Es obvio que el conjunto (a, b, c) tiene 3 elementos y que la gente dirı́a
que el conjunto N tiene una infinidad de elementos, pero esto, para nuestros
propósitos, es demasiado simplista. Pues, como veremos enseguida los conjuntos
con una infinidad de elementos, llamados conjuntos infinitos, no contienen la
misma cantidad de elementos. El número de elementos de los conjuntos infinitos
pueden variar, al igual que el número de elementos de los conjuntos finitos. Por
esto, existen varios niveles de infinidad, donde algunos conjuntos infinitos son
mayores que otros.
Ya que nuestro sistema contable tradicional no existen números que repre-
senten el número de elementos de un conjunto infinito, es necesario ampliar
nuestro sistema para tener en cuenta estos conjuntos. En este sistema ampliado
nos referimos al número de elementos de un conjunto como su cardinalidad. La
46 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
| Z+ |=| N | (| P (N |))
Los elementos de algún conjunto pueden ser asignados a las posiciones del
areglo S. El elemento asignado a la posición i será denotado por S[i] , y a la
sucesión S[1] , S[2] , . . . , S[n] se le llamará sucesión de valores del arreglo S y el
número N se denominará el tamaño del arreglo. El punto por observar es que el
arreglo S se considera bien definido, aún cuando a algunas posiciones no se les
haya asignado o si se cambian algunos valores durante la discusión.
Un concepto muy útil para los conjuntos es la Función Caracterı́stica. Si
A es un conjunto de un conjunto universal U, la función caracterı́stica FA de A
se define con:
2.4. CONJUNTOS EN LA PROGRAMACIÓN 49
1 si x∈A
fA (x) =
0 si x 6∈ A
entonces
fA∩B = fA × fB
b. Se tiene los siguientes casos:
fA∪B (x) = 1
Si x ∈ A entonces :
fA (x) + fB − fA × fB (x) = 1 + fA (x) − fA (x) = 1
fA∪B (x) = 1
Si x ∈ B entonces :
fA (x) + fB − fA × fB (x) = fA (x) − fA (x) = 1
fA∪B (x) = 0
Six 6∈ A y x 6∈ B entonces :
fA (x) + fB − fA × fB (x) = 0 + 0 − 0 = 1
Entonces
fA∪B = fA + fB − (fB fA × fB )
U = {a, c, e, i, m, t}
A = {c, e, m, t}
B = {a, i, m}
entonces:
fA corresponde a la sucesión 0, 1, 1, 0, 1, 1
50 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
fB corresponde a la sucesión 1, 0, 0, 1, 1, 0
U= 1 1 1 1 1 1
A= 0 1 1 0 1 1
B= 1 0 0 1 1 0
y recı́procamente, el arreglo:
C= 1 0 0 1 0 1
Procedure Diferencia-Simetrica(A, B)
1 for i := 1 to length(A)
2 if A[i] 6= B[i]
3 C[i] := 1
4 else
5 C[i] := 0
6 return (C)
7 end Diferencia-Simetrica
1 4 •
- -
2.5. Inducción
Uno de los conceptos más útiles de las matemáticas básicas en el diseño y
análisis de algoritmos es la inducción matemática. No sólo nos permitirá demos-
trar propiedades interesantes acerca de la corrección y eficiencia de los algorit-
mos, sino que además puede incluso utilizarse para determinar que propiedades
es preciso probar.
Antes de discutir la técnica, se ha de indicar una digresión acerca de la na-
turaleza del decubrimiento cientı́fico. En la ciencia hay dos enfoques opuestos
fundamentales: Inducción y deducción. La inducción consiste en infe-
rir una ley general a partir de casos particulares, mientras que una
deducción es una inferencia de lo general a lo particular.
Veremos, que aún cuando la inducción puede dar lugar a conclusiones falsas,
no se puede despreciar. La deducción, por otra parte; siempre es válida con tal
de que sea aplicada correctamente.
En general, no se puede confiar en el resultado del razonamiento inductivo.
Mientras que haya casos que no hayan sido considerados, sigue siendo posible
que la regla general inductiva sea incorrecta. Por ejemplo si se observa que:
52 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
13 = 1 = 12
13 + 23 = 9 = 32
13 + 23 + 33 = 36 = 62
13 + 23 + 33 + 43 = 100 = 102
13 + 23 + 33 + 43 + 53 = 225 = 152
p(n) = n2 + n + 41
y observe que:
Por tanto es natural inferir por indución que p(n) es primo para todos los valores
de n. Pero de hecho p(40) = 1681 = 412 no es primo.
Un ejemplo más sorprendente de inducción es el dado por una conjetura de
Euler, que formuló en 1789. ¿Es posible que la suma de tres cuartas potencias
sea una cuarta potencia? Formalmente, es posible encontrar enteros positivos a,
b, c tales que:
a4 + b4 + c4 = d4
Al no poder encontrar un ejemplo de este comportamiento, Euler conje-
turó que ésta ecuación nunca se podrı́a satisfacer. (Esta conjetura está relacio-
nada con el último teorema de Fermat). Transcurrieron más de dos siglos antes
2.5. INDUCCIÓN 53
p(n) = 991 ∗ n2 + 1
n = 12055735790331359447442538767
2. Si usted puede alcanzar una grada, usted puede siempre pasar a la grada
siguiente
a. P(1) es verdadera
Ejemplo 2.5.1. Consideramos un juego de vı́deo que empieza con una nave
espacial a mitad de la pantalla. En 5 segundos aparece un extraterrestre. Cinco
segundos después el extraterrestre se divide en dos, y estos dos extraterrestres se
subdividen en dos, y ası́ sucesivamente. Es decir, cada cinco segundos el número
2.5. INDUCCIÓN 55
P (n) = 2n−1 , ∀n ∈ Z+
Y evidentemente se verifica para los datos de la tabla. ¿cómo podemos estar
seguros de que lo que esperamos es correcto sin hacer todos los cálculos?
Como vimos, la respuesta a esta pregunta es utilizando el Principio de In-
ducción. Ası́:
Demostración. P (n) = 2n−1 , ∀n ∈ Z+
Paso Base
P (1) = 2t−1
= 20
= 1 es verdadera
Paso Inductivo
Se debe demostrar ahora que P (k) es verdadera para k > 1, entonces P (k+1)
también debe ser verdadera.
Se supone que para algún valor fijo k > 1, P (k) = 2k−1 llamada también
hipótesis de inducción es verdadera.
2 = 1∗2
2+4 = 2∗3
2+4+6 = 3∗4
2+4+6+8 = 4∗5
Es decir, P (k + 1) es verdadera.
Por lo tanto por el principio de inducción
2 + 4 + 6 + 8 + . . . + 2n = n(n + 1) ∀n ∈ Z+
21 > 1! 25 < 5!
22 > 2! 26 < 6!
23 > 3! 27 < 7!
24 < 4! 28 < 8!
2.5. INDUCCIÓN 57
Paso Base
entonces P (k + 1) es verdadera.
a. P(1) es verdadera
58 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
b. P(k) es verdadera par todo n K < n implica que P (n) sea verdadera
Observemos que:
Demostración. P (n) = (n + 1) + (n + 2) + . . . + 2 + 1
Paso Base
P (1) = 1−1
= 0 apretones de manos de saludo, es verdadera
Paso Inductivo
2.6. INDUCCIÓN EN LA VERIFICACIÓN DE PROGRAMAS 59
Para que usted pueda probar la equivalencia entre estos dos principios de
inducción, le presentamos otro principio llamado principio del buen orden.
Toda colección de números enteros que contenga por lo menos un elemento
tiene un elemento mı́nimo. Debemos entonces verificar que las siguientes sean
verdaderas.
Procedure Producto(m, n)
1 j := 1
2 x := n
3 while (j < n)
4 x := x + n
5 j := j + 1
6 return (x)
7 end producto
Paso Base
I(0) = X0 = 0
= J0 ∗ N es verdadera
2.7. LISTA DE EJERCICIOS 63
Paso Inductivo
Supongamos que para algún valor fijo k¿0, I(k) es verdadera, es decir:
I(k) = Xk ∗ N Ahora debemos demostrar que I(k+1) es verdadera:
I(k + 1) = Xk+1 = Xk + N
= Jk ∗ N + N, por hipótesis de inducción
= (Jk + 1) ∗ N
= Jk + 1 ∗ N
Entonces, I(k+1) es verdadera. Por lo tanto I(n) es verdadera, para todo n ≥ 0,
es decir {I}C{I}.
Lo más habitual es que el invariante del bucle sea precursor de la postcondi-
ción, lo que significa de que alguna manera debe ser parecido a la postcondición.
Además de esto, en cada iteración debe progresarse hacia la postcondición, lo
que significa que el invariante del bucle debe contener todas la variables que son
modificadas dentro del bucle.
El concepto de invariante del bucle también es útil en la construcción de
programas. En la construcción de programas normalmente hay un objetivo que
indica lo que hay que realizar al final de cada bucle. Este objetivo se puede
formalizar y esta formalización dá como resultado el invariante del bucle. Por
lo tanto, la verificación y la programación van codo a codo. En particular, si el
objetivo que hay que alcanzar al final de cada bucle se especifica claramente, es
mucho más fácil hallar el invariante del bucle. En este sentido el invariante del
bucle solamente es una formalización de los objetivos del programador.
22. Sean A y B arreglos de longitud N con ceros y unos, y suponga que repre-
sentan subconjuntos, que también llamaremos A y B, de algún conjunto
universal U con N elementos. Escriba un algoritmo en pseudocódigo para
especificar el arreglo C que represente al conjunto C = A ∩ (A ⊕ B)
23. Obtenga una fórmula para la suma de los n primeros enteros positivos
pares.
a) 20 + 21 + 22 + 23 + · · · + 2n = 2n+1 − 1; ∀n ∈ N
b) 12 + 32 + 52 + · · · + (2n − 1)2 = n(2n+1)(2n−1)
3 ; ∀n ∈ Z+
an −1
c) 1 + a + a2 + · · · + an−1 = a−1 ; ∀n ∈ Z+
a(1−r n )
d) a + ar + ar2 + · · · + arn−1 = 1−r ; r 6= 1 ; ∀n ∈ Z+
e) 1 + 2n < 3n ; n ≥ 2
f) n < 2n ; n > 1
(2n+1)2
g) 1 + 2 + 3 + · · · n < 8 ; ∀n ∈ Z+
h) 3n < n! ; n ≥ 6
i) n! < nn ; ∀n ∈ Z+
n−1 n−1 n(n+1)
j) 12 − 22 + 32 − · · · + (−1) n2 = (−1) 2 ; ∀n ∈ Z+
1 1 1 1
k) 1 + 4 + 9 + ···+ n2 <2− n ;n>1
l) Si un conjunto A tiene n elementos, entonces P(A) tiene 2n elemen-
tos.
m) 3| n3 − n ; ∀n ∈ Z+
66 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
n
T
n) Si A1 , A2 , · · · , An son n conjuntos cualesquiera, entonces Ai =
i=1
n
S
Ai .
i=1
n
S
o) Si A1 , A2 , · · · , An son n conjuntos cualesquiera, entonces Ai =
i=1
n
T
Ai .
i=1
Tn
S
p) Si A1 , A2 , · · · , An , y B son conjuntos cualesquiera, entonces Ai B=
i=1
n
T S
(Ai B).
i=1
q) Si p es un número primo y p|an para n ≥ 1 , entonces p|a .
r) Si M CD (a, b) = 1 , entonces M CD (an , bn ) = 1 ; ∀n ∈ Z+ .
27. Encuentre el entero positivo más pequeño n0 tal que 2n0 > n20 . Luego
demuestre por inducción matemática que 2n > n2 para todos los valores
n ≥ n0 .
30. Use inducción matemática para demostrar que n lı́neas rectas en el plano
(n2 +n+2)
lo dividen en 2 regiones. Suponga que no hay dos lı́neas paralelas
y que no hay tres lı́neas con un punto en común.
31. Demuestre que las regiones del ejercicio anterior pueden colorearse de rojo
y verde de modo que no haya dos regiones que comparten una orilla que
sean del mismo color.
Procedure Potencia(n, m)
1 r := n
2 p := 2 ∗ m
3 while p > 0
4 r := r ∗ n
5 p := p − 1
6 return (r)
7 end Potencia
68 CAPÍTULO 2. RAZONAMIENTO: LÓGICO - MATEMÁTICO
Capı́tulo 3
Relaciones
3.1. Relaciones
Los elementos de un conjunto o los elementos de conjuntos diferentes frecuen-
temente presentan comparaciones especiales entre si, que pueden ser descritas
como una relación.
Definición 3.1. Una relación binaria R del conjunto A en el conjunto B es un
subconjunto de A × B.
Si R es una relación binaria en A×B, entonces R consistirá en un conjunto
de pares ordenados de la forma (a, b) y escribiremos R : A ↔ B.
si (a, b) ∈ R diremos que a esta relacionada con b bajo la relación R y
escribiremos aRb.
la relación R ⊆ A × B define dos subconjuntos, uno de A y otro de B,
estos son:
69
70 CAPÍTULO 3. RELACIONES
A B A B
b b
b
b
b b b
b b b b
b b b
b b b b
A B A B
b b
b
b
b b b
b b b b
b b b
b b b b
R p q r
a 1 0 1
b 0 1 1
1 2
3 4
aRb ⇔ a 6 Rb
R = {(α, 1), (α, 2), (β, 2), (β, 3), (γ, 2), (θ, 1)}
S = {(α, 2), (β, 3), (γ, 2), (θ, 2)}
Entonces:
R−1 = {(1, α), (2, α), (2, β), (3, β), (2, γ), (1, θ)}
S = {(α, 1), (α, 3), (β, 1), (β, 2), (γ, 1), (γ, 3), (θ, 1), (θ, 3)}
R ∪ S = {(α, 1), (α, 2), (β, 2), (β, 3), (γ, 2), (θ, 1), (θ, 2)}
R ∩ S = {(α, 2), (β, 3), (γ, 2)}
R = {(1, b), (2, d), (4, c), (5, d)}, S = {(b, x), (d, y), (b, z)},
entonces:
R ◦ S = {(1, x), (1, z), (2, y), (5, y)}
se tiene:
0 1 1
A ∨ B = 1 1 0
1 0 1
0 1 1
A ∧ B = 1 1 0
1 0 1
1 0 1
A ⊙ B = 1 1 1
0 1 1
A∨B =B∨A
A∧B =B∧A
3.2. MANIPULACIÓN DE RELACIONES 75
2) Asociatividad
A ∨ (B ∨ C) = (A ∨ B) ∨ C
A ∧ (B ∧ C) = (A ∧ B) ∧ C
3) Distributividad
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
4) Asociatividad
A ⊙ (B ⊙ C) = (A ⊙ B) ⊙ C
5) (AT )T = A
6) (A ∨ B)T = AT ∨ B T
7) (A ∧ B)T = AT ∧ B T
8) (A ⊙ B)T = B T ⊙ AT
c) Una matriz es denominada simétrica si AT = A. En consecuencia, si A
es simétrica, debe ser cuadrada. Es fácil demostrar que A es simétrica si
sólo si aij = aji . Es decir, A es simétrica si y solamente si las entradas de
A son simétricas con respecto de la diagonal principal de A.
Observación 3.2.3. Se debe enfatizar:
a) Sean R y S dos relaciones de A en B, entonces;
MR∩S = MR ∩ MS
MR∪S = MR ∪ MS
MR−1 = (MR )T
entonces:
MR = MR
MR◦S = MR ⊙ MS
Entonces,
76 CAPÍTULO 3. RELACIONES
1 0 0 1
MS = 0 1 1 0
0 0 1 1
S = {(1, a), (1, d), (2, b), (2, c), (3, c), (3, d)}
0 1 0 0
MR∪S = 0 0 0 1
1 1 0 0
R ∪ S = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, d), (3, a), (3, b), (3, c)}
1 0 1
T
1 0 1
MR−1 = (MR ) =
0
0 1
1 1 0
R−1 = {(a, 1), (a, 3), (b, 1), (b, 3), (c, 3), (d, 1), (d, 2)}
R S R◦S
A B C A C
a m a m
b n b n
c o c o
Figura 3.4: R, S y R ◦ S
Observe que:
MR◦S = MR ⊙ MS
Además, es claro que:
R ◦ S = {(a, o), (b, m), (b, n), (c, m), (c, n), (c, o)}
a)
R ⊆ S ⇒ R−1 ⊆ S −1
3.2. MANIPULACIÓN DE RELACIONES 77
b)
R⊆S⇒S⊆R
c)
(R ∪ S)−1 = R−1 ∪ S −1
(R ∩ S)−1 = R−1 ∩ S −1
d)
(R ∪ S) = R ∪ S
(R ∩ S) = R ∩ S
3.3. Trayectorias
Definición 3.7. Sea R unaQ relación en A. Una trayectoria de de longitud n de
a a b, es una sucesión finita = a, x1 , x2 , . . . , xn−1 , b; que inicia en a y termina
en b, tal que:
a c
b d
Solución
1 3 6 9 12
1 1 1 1 1 1
3
0 1 1 1 1
MR = 6 0 0 1 0 1
9 0 0 0 1 0
12 0 0 0 0 1
R es reflexiva
Demostración. MR tiene unos en toda su diagonal principal.
R no es irreflexiva
Contraejemplo
m11 = 1
R no es simétrica
Contraejemplo
3.5. PARTICIONES 81
R no es asimétrica
Contraejemplo
m22 = 1
R es antisimétrica
i 6= j =⇒ mij = 0 ∨ mji = 0
3.5. Particiones
Una partición o conjunto cociente de un conjunto no vacı́o A es la colección
de subconjuntos no vacios {A1 , A2 , . . . , An } de A tal que
a) Ai ∩ Aj = ∅ ∀i 6= 1
n
[
b) Ai = A
i=1
A1 =A
A2
A3
[a] = {x ∈ A/aRx}
aRb ⇐⇒ a ≡ b , ∀a ∈ Z
⇐⇒ 2|(a − b)
Solución:
• R es reflexiva
2|0 ⇐⇒ 2|(a − a) , ∀a ∈ Z
⇐⇒ a ≡ a(mod 2) , ∀a ∈ Z
⇐⇒ aRa , ∀a ∈ Z
• R es simétrica
aRb ⇒ a ≡ b(mod 2)
⇒ 2|(a − b)
⇒ 2| − (a − b)
⇒ 2|(b − a)
⇒ b ≡ a(mod 2)
⇒ bRa
3.5. PARTICIONES 83
• R es transitiva
Observe que:
aRb ⇐⇒ a ≡ b(mod n)
Z|R = Z|mod n = Zn
Z2 = {[0], [1]}
Z3 = {[0], [1], [2]}
Z4 = {[0], [1], [2], [3]}
..
.
¿Determine [2] en Z4 ?
Teorema 3.3. Sean R y S relaciones en A, entonces:
84 CAPÍTULO 3. RELACIONES
i) (R ∩ S)2 ⊆ R2 ∩ S 2
Para c:
R es simétrica ⇐⇒ MR = (MR )T
⇐⇒ MR = MR−1
⇐⇒ R = R−1
Para f:
(R−1 )−1 = R
= R−1 por hipótesis y (c)
Para i:
R ⊆ R∞
R∞ = R ∪ R2 ∪ R3 ∪ . . .
R∞ es la relación transitiva más pequeña que contiene a R
∴ la cerradura transitiva de R es Rc = R∞
Método 1:
a b
c d
Rc = R∞
Rc = {(a, c), (a, d), (b, a), (b, c), (b, d), (c, d)}
Método 2:
Rc = R∞
R∞ = R ∪ R2 ∪ R3 ∪ R4 ∪ R5 ∪ . . .
Luego:
0 0 1 0
1 0 1 0
MR = 0
0 0 1
0 0 0 0
0 0 0 1
0 0 1 1
M R2 =
0
0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
M R3 =
0
0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
M R4 =
0
0 0 0
0 0 0 0
M R5 = M R4
..
.
M Rc = M R ∨ M R2 ∨ M R3 ∨ M R4 ∨ M R5 ∨ . . .
= M R ∨ M R2 ∨ MR3 ∨ (MR4 ∨ MR4 ∨ . . .)
= M R ∨ M R2 ∨ M R3
0 0 1 1
1 0 1 1
=0 0 0
1
0 0 0 0
Rc = {(a, c), (a, d), (b, a), (b, c), (b, d), (c, d)}
Teorema 3.5. Sea A un conjunto finito con |A| = n y sea R una relación en
A. Entonces:
R∞ = R ∪ R2 ∪ . . . ∪ Rn
3.6. CERRADURA DE LAS RELACIONES 87
Demostración.
∴ R∞ = R ∪ R2 ∪ . . . ∪ Rn
c) Se acepta W0 = MR
Ejemplo:
(R ∪ S)∞ es reflexiva
(R ∪ S)∞ es simétrica
Calcule:
a) MR2 , MR◦S
b) MR , MR−1
8. Sea A = {1, 2, 3, 4, 5, 6, 7} y R = {(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 7)}.
Calcule las restricciones de R a B para el subconjunto de A dado.
(a) B = {1, 2, 3, 4}
(b) B = {2, 3, 4, 6}
0 1 0 1
1 0 1 1
MR =
0
1 0 0
1 1 0 0
A = Z+ ; aRb si y sólo si |a − b| ≤ 2.
A = Z+ ; aRb si y sólo si |a − b| = 2.
A = el conjunto de todos los pares ordenados de números reales;
(a, b)R(c, d) si y sólo si a = c.
A es el conjunto de todas las lineas que hay en el plano; l1 Rl2 si y
sólo si l1 es paralela a l2 .
3.7. LISTA DE EJERCICIOS 91
Estructuras de Orden
a) (≥, ≤)
b) (P(u),⊆)
93
94 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
c c c b c
b b b b b
a a a b a
Figura 4.1: Un orden parcial
{a, b, c}
b
{a, b} b b
{a, c} b
{b, c}
{b}
{a} b b b
{c}
{}
f a b c
b b b b
d b b e
d b b e
b b b b
a b c f
(A, ≤) (A, ≥)
b c
b b
b a
4 b b
5 b
4
b 5
b b
3
3
b 1
1 b b
2 b
2
(A, ≤) (A, ≺)
8 b b
9
4 b
5 b b
6 b
7
b b b
1 2 3
i
b
g b b
h
b
f
d b b
e
b c
a b b
b
(A, ≤)
Elemento Máximo :i
Elemento Mı́nimo : no existe
Observación
SupB = a ∨ b , Inf B = a ∧ b
4.2. Látices
Definición 4.7. Un conjunto parcialmente ordenado (L; ≤) tal que todo par
de elementos de L tenga supremo e ı́nfimo se denomina retı́cula o látice. 1
Observación 4.2.1. Sean (L1 , ≤1 ) y (L2 , ≤2 ) látices. Si para (a, b), (c, d) ∈
L = L1 × L2 definimos el orden parcial producto ≤ con:
(a, b) ≤ (c, d) ⇐⇒ a ≤1 c ∧ b ≤2 d
(a, b) ∨ (c, d) = (a ∨1 c, b ∨2 d) y
(a, b) ∧ (c, d) = (a ∧1 c, b ∧2 d)
(2, 8)
b
2 8
b b
(2, 2) b b
(1, 8) b
(2, 4)
(2, 1)
2 b b 4 (1, 2) b b b
(1, 4)
b b b
1 1 (1, 1)
(D2 , /1 ) (D8 , /2 ) (L, /2 )
Figura 4.8: D2 , D8 y L = D2 × D8
e b b
f d e b b
f
b b
d
b b b c b b b c b b b c
b b
a a
(L, ≤) (S1 , ≤) (S2 , ≤)
a ≤ b ⇐⇒ a ∨ b = b y a∧b=a
f (a ∨ b) = f (a) ∨′ f (b)
f (b) = f (a) ∨′ f (b) por (a)
∴ f (a) ≤′ f (b)
Esto significa que dos látices son isomorfas si y sólo si el diagrama de Hasse
de una de ellas se puede obtener a partir de la otra reetiquetando los vértices.
Ejemplo 4.2.4. ¿Serán isomorfas las látices (D30 , /) y (P(u), ⊆)?, donde
u = {a, b, c}
Solución:
Analizando (D30 , /) y (P(u), ⊆),
30 {a, b, c}
b b
6 b b
10 b
15 {a, b} b b
{a, c} b
{b, c}
3 {b}
2 b b b
5 {a} b b b
{c}
b b
1 {}
(D30 , /) (P(u), ⊆)
I = a1 ∨ a2 ∨ . . . ∨ an
0 = a1 ∧ a2 ∧ . . . ∧ an
Definición 4.11. Una látice (L, ≤) se dice que es distributiva, si para toda
a, b, c ∈ L se tiene que:
a) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
b) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Ejemplo 4.2.5. La látice (P(u), ⊆) es distributiva ¿Por qué?
102 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
I I
b b
a b
a b b
b b
c b
c
b b
b b
0 0
(L1 , ≤) (L2 , ≤)
A ∪ Ā = U
A ∩ Ā = ∅
4.2. LÁTICES 103
a b
b
c
b b
(L2 , ≤)
I’ = 0
a′ = c
b′ = c
c′ = a
c′ = b
0′ = I
a ∨ a′ = 1 a ∨ a′′ = 1
a ∧ a′ = 0 a ∧ a′′ = 0
luego:
a′ = a′ ∨ 0 a′′ = a′′ ∨ 0
= a′ ∨ (a ∧ a′′ ) = a′′ ∨ (a ∧ a′ )
= (a′ ∨ a) ∧ (a′ ∨ a′′ ) = (a′′ ∨ a) ∧ (a′′ ∨ a′ )
= 1 ∧ (a′ ∨ a′′ ) = 1 ∧ (a′′ ∨ a′ )
= a′ ∨ a′′ . . . . . . 1 = a′′ ∨ a′ . . . . . . 2
f (a′ ) = (f (a))′
a ∨ a′ = 1
a ∧ a′ = 0
(a ∨ b) ∨ (a′ ∧ b′ ) = 1
(a ∨ b) ∧ (a′ ∧ b′ ) = 0
Entonces (a ∨ b)′ = a′ ∧ b′
También
(a ∧ b) ∨ (a′ ∨ b′ ) = 1
(a ∧ b) ∧ (a′ ∨ b′ ) = 0
4.4. REDES LÓGICAS 105
(1, 1)
b 1 b
(1, 0) b b
(0, 1)
b
0 b
(0, 0)
(B, ≤) (B 2 , ≤)
a + b = (a1 + b1 , a2 + b2 , . . . , an + bn )
a · b = (a1 · b1 , a2 · b2 , . . . , an · bn )
0B n = (0, 0, . . . , 0)
1B n = (1, 1, . . . , 1)
Supongamos ahora que llaves mecánicas pueden ser usadas a fin de que se obtiene
la señal 1 cuando la llave esta cerrada y se obtiene la señal 0 con la llave abierta.
x=1 x=0
x1 = 0 x1 = 0
0 1
x2 = 0 x2 = 1
x1 = 1 x1 = 1
1 1
x2 = 0 x2 = 1
x1 x2 x1 + x2
0 0 0
0 1 1
1 0 1
1 1 1
X1
X1 + X2
X2
x1 x2 x1 + x2
0 0 0
0 1 1
1 0 1
1 1 1
X1
X1 · X2
X2
x1 x2 x1 · x2
0 0 0
0 1 0
1 0 0
1 1 1
X1
X1
x1 x1
0 1
1 0
2 bit:Es la abreviatura del ingles binary digit o dı́gito binario en español.
108 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
p(x, y, z) = (x + y) · z
q(x, y, z) = x + ȳ · z + x · (y + 1)
p(x, y) = x + y
q(x, y) = x · y
r(x) = x̄
x y z f (x, y, z)
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
Observación 4.4.3. Combinando las compuertas AND, OR y NOT, podemos
construir una red lógica que representa determinado polinomio booleano.
Ejemplo 4.4.4. El polinomio booleano p(x, y, z) = (xy + z)z se puede
representar por la red lógica:
4.4. REDES LÓGICAS 109
Observación 4.4.4. Las redes lógicas son llamadas también redes combina-
torias. Ellas tienen diversos aspectos que debemos percibir. Primero, las lineas
de entrada o de salida no se cruzan, excepto al pasar por las compuertas. Por
lo tanto las lineas pueden ser divididas a fin de establecer entradas para más
de una compuerta. No hay lazos donde la salida de un componente sirva como
entrada para este mismo componente. Finalmente, la salida de una red es una
función instantánea de la entrada, es decir que cada entrada produce una única
salida. Esta situación hasta ahora establece que:
Polinomio booleano
Función booleana
x y z f (x, y, z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
1. Como existen cuatro filas en la tabla (2, 5, 6, 8) para las cuales f es 1, la
forma básica de nuestro polinomio booleano tendrá la forma de una suma
de 4 términos.
( ) + ( ) + ( ) + ( )
de modo que el primer término asume el valor de 1 para los valores de
entrada de la fila 2, el segundo termino asume el valor de 1 para los
valores de entrada de la fila 5, y ası́ en adelante. Por lo tanto, el polinomio
booleano tiene valor 1 para esas entradas y ninguna otra, precisamente lo
que deseamos. (Otras entradas hacen que los términos y por lo tanto toda
la suma, tenga el valor 0).
2. Cada término en la suma será un producto de la forma l1 · l2 · l3 , donde
l1 , l2 , l3 son llamados literales y l1 es x o x̄, l2 es y o ȳ y l3 es z o z̄.
110 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
f +g = f¯ · ḡ
2. “Leyes de Morgan”
f ·g = f¯ + ḡ
f +g = g+f
3. “Leyes conmutativas”
f ·g = g·f
f + (g + h) = (f + g) + h
4. “Leyes asociativas”
f · (g · h) = (f · g) · h
f +g·h = (f + g) · (f + h)
5. “Leyes distributivas”
f · (g + h) = f ·g+f ·h
f +f = f
6. “Leyes de indempotencia ”
f ·f = f
f +0 = f
7. “Leyes de identidad”
f ·1 = f
4.4. REDES LÓGICAS 111
f + f¯ = 1
8. “Leyes de inversos”
f · f¯ = 0
f +1 = 1
9. “Leyes de dominación”
f ·0 = 0
f +f ·g = f
10. “Leyes de absorción”
f · (f + g) = f
Ejemplo 4.4.6. Hallar la fnd de la función f : B 4 −→ B definida por
f (w, x, y, z) = wxȳ + wy z̄ + xy
Solución: Examinando cada término:
wy z̄ = w · 1 · y z̄ “Ley de identidad ”
= w · (x + x̄) · y · z̄ “Ley de inversos”
= wxy z̄ + wx̄y z̄ “Ley distributiva”
xy = 1 · x · y · 1 “Ley de identidad ”
= (w + w̄) · x · y · (z + z̄) “Ley de inversos”
= wxyz + wxy z̄ + w̄xyz + w̄xy z̄ “Ley distributiva”
entonces
f (w, x, y, z) = wxȳz + wxȳ z̄ + wxy z̄ + wx̄y z̄ + wxyz + wxy z̄ + w̄xyz + w̄xy z̄ (5)
por la ley de idempotencia (6) se tiene la fnd,
x y z f (x, y, z)
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
solución:
Aplicando el concepto de dualidad, se tiene que:
Q
f= M (0, 2, 6)
donde M significa maxtérminos.
Ejemplo 4.4.9. Hallar la fnc para f : B 4 −→ B definida por:
f (w, x, y, z) = (w + x + y)(x + ȳ + z)(w + ȳ)
Solución:
x + ȳ + z = 0 + x + ȳ + z “Ley de identidad ”
= ww̄ + x + ȳ + z “Ley de inversos”
= (w + x + ȳ + z)(w̄ + x + ȳ + z) “Ley distributiva”
w + ȳ = w + 0 + ȳ + 0 por (7)
= w + xx̄ + ȳ + z z̄ por (8)
= (w + x + ȳ)(w + x̄ + ȳ) + z z̄ por (5)
= (w + x + ȳ + z z̄)(w + x̄ + ȳ + z z̄) por (5)
= (w + x + ȳ + z)(w + x + ȳ + z̄)(w + x̄ + ȳ + z)(w + x̄ + ȳ + z̄) por (5)
de donde
4.5. Aplicaciones
4.5.1. Arreglos lógicos programables
Un circuito integrado, es una red lógica que representa una o más funciones
booleanas, como si algunas compuertas lógicas estuviesen debidamente interli-
gadas en un paquete. Estos circuitos integrados son entonces combinados a fin
114 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
de obtener el resultado deseado. Los chips cuadrados de silicio en los cuales los
circuitos integrados son constrı́dos, no pueden tener más de 6 milı́metros de
lado, sin embargo pueden contener el equivalente a medio millón de transistores
que implementan funciones booleanas.
En vez de proyectar un chip dedicado a implementar algunas funciones boo-
leanas en particular, podemos usar un PLA (Programable Logic Array). El PLA
es un chip que contiene un arreglo de compuertas AND, OR, NOT. Una vez que
tengamos determinada la forma de suma de productos de las funciones boolea-
nas deseadas, los elementos correspondientes al PLA son activados. A pesar de
que este chip no es muy eficiente, y ser práctico apenas para circuitos lógicos de
pequeña escala, el PLA puede ser producido en masa y apenas es una pequeña
cantidad de tiempo y dinero.
x y z f1 f2 f3 f4
x y z f1 f2 f3 f4
• • • •
• • • •
• • • •
• • • •
S = x̄y + xȳ
= x⊕y , recuerde que ⊕ denota la o exclusiva
= (x + y)xy
C = xy
116 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
La figura 4.22 es una red de compuertas con dos salidas. Este dispositivo,
por motivos que se aclaran más adelante, es llamado semisumador (SS).
x x+y
y
S = x + y(xy)
x xy xy
y
C = xy
Si = Si′ ⊕ Ci−1
Ci−1 S.S.
Si′ = xi ⊕ yi Ci−1 (xi ⊕ yi )
xi
yi S.S. Ci′ = xi yi
Ci = xi yi + Ci−1 (xi ⊕ yi )
x0 S0
y0 S.S. C0
S1
x1 S.C.
y1 C1
S2
x2 S.C.
y2 C2
x y x↑y
0 0 1
0 1 1
1 0 1
1 1 0
118 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
X1
X1 · X2
X2
X1
X1 + X2
X2
x̄ = xx
= x↑x
x+y = x̄¯ + ȳ¯
= x̄ȳ
= x̄ ↑ ȳ
= (x ↑ x) ↑ (y ↑ y)
Las entradas de la red representan los cuatro productos que pueden ser
ordenados. Vamos a llamarlos:
w = Loción
x = Perfume
y = Maquillaje
z = Esmalte de Uñas
w x y z f (w, x, y, z)
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Ejemplo 4.5.4. Una ley del corredor es controlada por dos interruptores,
uno en cada extremo. La tabla de verdad que permite que la luz sea prendida y
apagada en ambos interruptores es:
x y f (x, y)
0 0 0
0 1 1
1 0 1
1 1 1
120 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
4.6. Minimización
Naturalmente, la equivalencia de polinomios booleanos es una relación de
equivalencia en el conjunto de todos los polinomios booleanos de n−variables.
Cada clase de equivalencia está asociada a una función booleana distinta.
Si deseamos diseñar una red lógica para una función booleana, lo ideal es
que tengamos un procedimiento que obtenga el polinomio booleano más simple
de la clase de equivalencia. Lo que llamamos simple dependerá de la tecnologı́a
que estamos empleando en la construcción de la red, que tipos de componentes
lógicos serán usados, etc. De cualquier forma, probablemente deseemos minimi-
zar el número total de conexiones que precisan ser hechas y el número total de
componentes usados. (Al discutir procedimientos de minimización, recordemos
que otros facotres pueden influenciar el costo del circuito. Si la red fuera cons-
truida apenas una vez, el tiempo utilizado para la minimización posiblemente
sea mayor el de la cosntrucción de la red. Sin embargo si la red fuera construida
en gran escala el costo de tiempo de la minimización se justifica.)
p1 (w, x, y, z) “fnd de f”
p2 (w, x, y, z)
p3 (w, x, y, z) “suma minimal de productos”
son equivalentes.
Las siguientes figuras muestran la red lógica para cada uno de estos polino-
mios booleanos respectivamente. A partir de ahora consideramos una entrada
de la forma w̄ como una entrada exacta, que no ha pasado por compuerta algu-
na, en vez de considerarla como el resultado de introducir w y pasarla por un
inversor.
4.6. MINIMIZACIÓN 121
w̄
x w̄xȳz
ȳ
z
w̄
x w̄xyz
y
z
w
x̄ wx̄ȳz̄
ȳ
z̄ f (w, x, y, z)
w
x̄ wx̄ȳz
ȳ
z
w
x̄ wx̄yz
y
z̄
w̄
x w̄xȳ z̄
ȳ
z̄
w̄ w̄xz
x
z
w̄ w̄xȳ
x
ȳ
f (w, x, y, z)
w wx̄ȳ
x̄
ȳ
w wx̄z
x̄
z
w̄ w̄x(ȳ + z)
x
ȳ f (w, x, y, z)
z •
w wx̄(ȳ + z)
x̄
Observación 4.6.1. La red lógica de la figura 4.28 sólo tiene cuatro compuertas
lógicas, mientras que la primera 4.27 tiene 7 y 4.29 presenta 5 en consecuencia,
podrı́amos pensar que la segunda red 4.28 es mejor respecto a la minimización de
costos, puesto que cada compuerta adicional incrementa el costo de producción.
En el estudio de las redes de compuertas, las salidas se consideran funciones
instantáneas de la entrada. Esto significa que cada nivel de compuertas añade
un retraso en el desarrollo de la función. En el equipo digital de alta velocidad
queremos minimizar el retraso, por lo que optamos por más velocidad. Esta
necesidad de maximizar la velocidad nos hace desear la representación de una
función booleana como una suma minimal de productos, en nuestro ejemplo la
última red lógica .
Ya vimos en el ejemplo la simplificación de f (w, x, y, z) a través del uso de
las propiedades del álgebra booleana, en tanto, no tenemos un procedimiento
que aplicar, apenas resolver el problema en forma individual. Lo que deseamos
ahora es un procedimiento sistemático que podamos usar sin la necesidad de ser
tan ingeniosos.
En esta sección discutiremos dos procedimientos para la reducción de una
fnd a una suma minimal de productos. Por tanto, podemos minimizar dentro
del contexto de forma de suma minimal de productos.
Observación 4.6.2. En el ejemplo anterior
a) La equivalencia,
xy + x̄y = (x + x̄)y
= 1·y
=y
significa, que
w̄xȳ z̄ + w̄xȳz = w̄xȳ
Por lo tanto, cuando tenemos una suma de dos productos que difieren ape-
nas en una literal, podemos eliminar esta literal. Sin embargo, la emphfnd
4.6. MINIMIZACIÓN 123
Y 0 1
X
0 1
1 1
x y f (x, y)
0 0 0
0 1 1
1 0 0
1 1 1
En una rápida inspección, podemos identificar los 1s en las localidades ad-
yacentes (x̄y + xy = y) que marcaremos en el mapa de Karnaugh. Entonces la
suma minimal de productos es:
f (x, y) = y
Ejemplo 4.6.3. En el mapa de Karnaugh,
Y 0 1
X
0 1
1 1 1
YZ 00 01 11 10
X
0 1 1
1 1 1
x̄ȳz̄ + xȳ z̄ = ȳ z̄
x̄y z̄ + xy z̄ = z̄
ȳ z̄ + y z̄ = z̄
YZ 00 01 11 10
X
0 1 1
1 1 1
f (x, y, z) = z̄
4.6. MINIMIZACIÓN 125
P
c) f = m(0, 1, 2, 3)
YZ 00 01 11 10
X
0 1 1 1 1
f (x, y, z) = x̄
P
d) f = m(1, 2, 3, 5, 6, 7) “Hay que buscar todas las adyacencias”
YZ 00 01 11 10
X
0 1 1 1
1 1 1 1
f (x, y, z) = y + z
YZ 00 01 11 10
WX
00 1 1 1 1
01
11
10 1 1 1
YZ 00 01 11 10
WX
00 1
01 1 1 1
11 1 1 1
10 1
YZ 00 01 11 10
WX
00 1
01 1 1 1
11 1 1 1
10 1
Y
f (w, x, y, z) = M (1, 5, 7, 9, 10, 13, 14, 15)
Solución:
Aplicando el Concepto de dualidad, se tiene
YZ 00 01 11 10
WX
00 0
01 0 0
11 0 0 0
10 0 0
a) Recordemos que el punto básico para la reducción de una fnd a una suma
minimal es el reconocimiento de las adyacencias. En el mapa de Karnaugh
determinamos donde existen esas adyacencias. Un segundo método para
minimizar, es el procedimiento de Quine McCluskey 3 , que organiza la fnd
en una tabla a fin de simplificar la búsqueda de adyacencias.
3 Quine McCluskey
128 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
w x y z f (w, x, y, z)
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
Las ocho 4-uplas de ceros y unos producen el valor 1 son listadas en una
tabla, que es separada en cuatro grupos, de acuerdo con el número de unos.
Número de 1s w x y z
Tres 1 0 1 1
Dos 0 0 1 1
0 1 0 1
0 1 1 0
Uno 0 0 1 1
0 0 1 0
1 0 0 0
Cero 0 0 0 0
Comparamos el primer término 1011, con cada uno de los tres términos del
segundo grupo a fin de encontrar términos adyacentes. Un término de este tipo
es 0011, que determina que variable w es eliminada. Escribimos este término
reducido con un trago en la posición w en dos términos 1011 y 0011 en la
tabla original con un ı́ndice 1; este ı́ndice es un puntero que indica la linea
del término reducido que es formada por esos dos elementos (numerar estas
localidades equivale a trazar los grupos en un mapa de Karnaugh).
Continuamos este proceso con todos los términos. Un término numerado
puede ser usado otras combinaciones, de la misma forma que podemos agrupar
un término ya agrupado en un mapa de Karnaugh. Cuando hayamos terminado
se obtendrá las siguientes tablas.
Número de 1s w x y z
Tres 1 0 1 1 1
Dos 0 0 1 1 1,2,3
0 1 0 1 4
0 1 1 0 5
Uno 0 0 0 1 2,4,6
0 0 1 0 3,5,7
1 0 0 0 8
Cero 0 0 0 0 6,7,8
4.6. MINIMIZACIÓN 129
Tabla (a)
Número de 1s w x y z
Dos - 0 1 1
Uno 0 0 - 1
0 0 1 -
0 - 0 1
0 - 1 0
Cero 0 0 0 -
0 0 - 0
- 0 0 0
Tabla (b)
Repetimos este proceso en la tabla (b)
Número de 1s w x y z
Dos - 0 1 1
Uno 0 0 - 1
0 0 1 - -
0 - 0 1
0 - 1 0
Cero 0 0 0 - 1
0 0 - 0 1
- 0 0 0
Tabla (c)
Número de 1s w x y z
cero 0 0 - -
Tabla (d)
Observe que el proceso de reducción no puede ser continuado. Los términos que
no fueron numerados son irreductibles, de forma que representan los mintérmi-
nos.
El segundo paso del proceso, consiste en comparar los términos irreductibles.
Una marca en la tabla de comparación (Tabla (a)) indica que el término original
en una columna acaba por llevar al término irreductible a esta linea, o que puede
ser determinado siguiendo los punteros.
Si una columna en la Tabla (e) tiene una marca en apenas una fila, el término
irreductible de esta fila es el único que cubre al término original, de forma que
el es un término esencial y precisa aparecer en la forma final de suma minimal
de productos. Por tanto, vemos en la Tabla (e) que los términos -011, 0-01,
0-10, -000, son esenciales y precisan ser parte de la expresión final. También
percibimos que todas las columnas con marcas en la fila 5 también son marcas
130 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
a b b
b b
c
0
4.7. LISTA DE EJERCICIOS 131
x + y + (x̄ + y + z)
12. Para cada una de las funciones booleanas f , encuentre una representa-
ción mediante una suma minimal de productos y luego diseñe una red de
compuertas de dos niveles. Utilice diagramas de Karnaugh.
Q
a) f (x, y, z) = M (0, 4, 5, 6)
P
b) f (w, x, y, z) = m(7, 9, 10, 11, 14, 15)
13. Sea n un entero positivo y se Dn el conjunto de todos los divisores de
positivos de n. Ası́, si n = 20, se tiene Dn = {1, 2, 4, 5, 10, 20}
a) Hacer los diagramas de Hasse de D20 y D30 bajo el orden parcial de
divisibilidad.
b) Determinar si D20 y D30 y D60 son lattices.
132 CAPÍTULO 4. ESTRUCTURAS DE ORDEN
133