Capítulo 2

Estructuras Básicas

2.1 Introducción
Las palabras conjunto y elemento son términos indefinidos de la teoría de conjuntos tales
como frase, verdadero y falso son términos indefinidos de la lógica.

2.2 Conjunto
Un conjunto es una colección de objetos. Algunas veces se hace referencia a los objetos como
elementos o miembros. Las letras mayúsculas A, B, X, Y, ..., denotan conjuntos y las minúsculas
a, b, c, d, ..., x, y, ..., denotan elementos de conjuntos. Algunos sinónimos de conjunto son “clase”,
“colección” y “familia”.
Veremos dos formas de describir un conjunto. Una es enumerar todos los miembros del con-
junto cuando esto sea posible. Para esto utilizamos una notación en la que todos los miembros
se enumeran entre llaves; esta forma es conocida también como la determinación de un conjunto
por extensión. Otra forma es usando la notación de construcción de conjuntos. Caracterizamos
todos los elementos del conjunto declarando la propiedad o propiedades que deben tener sus
miembros. Esta forma también se denomina la determinación por comprensión de un conjunto.
Dos ejemplos de lo anterior son

A = {1, 3, 5, 7, 9} y B = {x; x es un entero par, x > 0}

Es decir, A consta de los elementos 1, 3, 5, 7, 9. El segundo conjunto se lee B es el conjunto de

todos los x tal que x es un entero par y x es mayor que 0, denota el conjunto B, cuyos elementos
son los enteros pares positivos. Observemos que para denotar un miembro del conjunto se usa
una letra, casi siempre x; la recta oblícua / se lee “tal que” y la coma “y”. Si hacemos

P (x) = x es un entero par, x > 0,

el conjunto B se escribe en la forma

B = {x; P (x)} .

En general, si S es un conjunto y P (x) es una propiedad que los elementos de S pueden o no

tener, entonces podremos definir un conjunto como

B = {x ∈ S; P (x)} .

En Matemática Discreta son muy importantes los conjuntos: N, Z, Z+ , Q y R, muy conocidos

por nosotros.
 El conjunto que no tiene elementos, se le llama el ”conjunto vacío” y se lo denota por
∅ = {}.
Se dice que dos conjuntos A y B son ”iguales” si ellos tienen los mismos elementos; escribimos
A = B. En símbolos
A = B ⇔ ∀x [(x ∈ A) ⇔ (x ∈ B)]
Supongamos que todo elemento de un conjunto A también es un elemento de un conjunto B; es
decir, si a ∈ A implica que a ∈ B. Entonces se dice que A es un subconjunto de B. También se
dice que A está contenido en B o que B contiene a A. Esta relación se escribe A ⊆ B o B ⊇ A.
Todo conjunto tiene dos subconjuntos triviales: el conjunto vacío y el propio conjunto.
Un subconjunto propio de un conjunto es un subconjunto que no es igual al conjunto que
lo contiene. Si A es un subconjunto propio de B escribimos A ⊂ B. Esto significa que por lo
menos un elemento de B no pertenece al conjunto A.
El conjunto de todos los subconjuntos (propios o no) de un conjunto A, denotado por P(A),
se llama el conjunto potencia de A. Por ejemplo, si A = {a, b, c}, entonces

P (A) = {∅, {a} , {b} , {c} , {a, b} , {a, c} , {b, c} , {a, b, c}}

2.3 Operaciones con conjuntos

La mayoría de los análisis matemáticos se realizan dentro de algún contexto. Por ejemplo,
en una determinada situación todos los conjuntos que se consideran podrían ser conjuntos de
números reales. En esta situación, para este análisis el conjunto de números reales se llamaría
el conjunto universo o universo del discurso.
Sean A y B subconjuntos de un conjunto universo U .
La unión de A y B, denotada por A∪B es el conjunto formado al tomar todos los elementos
de A y los de B. Esto es
A ∪ B = {x; x ∈ A ∨ x ∈ B}
La intersección de dos conjuntos A y B, denotada por A∩B , es el conjunto de los elementos
que pertenecen tanto a A como a B; es decir

A ∩ B = {x; x ∈ A ∧ x ∈ B}

La diferencia de A y B, denotada por A \ B, es el conjunto que tiene por elementos los

elementos de A que no están en B; esto es

A \ B = {x; x ∈ A, x ∈
/ B}

También se la llama el complemento relativo de un conjunto B respecto de un conjunto A.

El complemento de A, que se denota por Ac , es el conjunto de todos los elementos en U que
no están en A. Es decir
Ac = {x; x ∈ U, x ∈ / A}.
La diferencia simétrica de los conjuntos A y B, denotada por A∆B, es el conjunto de los
elementos de A y de B, excepto los que pertenecen a la intersección. Esto es

A∆B = {x; (x ∈ A, x ∈
/ B) ∨ (x ∈
/ A, x ∈ B)}

El producto cartesiano de A y B es el conjunto de parejas cuya primera componente está

en A y la segunda en B. Esto se escribe de la siguiente forma

A × B = {(a, b) ; a ∈ A ∧ b ∈ B}

2
Al conjunto A × A × · · · × A, producto cartesiano de A consigo mismo n veces, lo denotamos
por An , n entero positivo.
El cardinal de A es el número de elementos de A. Lo denotamos por n (A) , #(A) , |A| o
card(A).

Teorema 2.1 Sea U un conjunto universal y sean A, B y C subconjuntos de U . Las siguientes

propiedades se cumplen

1. Leyes asociativas

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

2. Leyes conmutativas

A∪B = B∪A
A∩B = B∩A

3. Leyes distributivas

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

4. Leyes de identidad
A ∪ ∅ = A, A ∩ U = A

5. Leyes de complemento
A ∪ Ac = U, A ∩ Ac = ∅

6. Leyes de idempotencia
A ∪ A = A, A ∩ A = A

7. Leyes de acotación
A ∪ U = U, A ∩ ∅ = ∅

8. Leyes de absorción
A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A

9. Leyes de involución
(Ac )c = A

10. Leyes 0/1

∅c = U, U c = ∅

11. Leyes de De Morgan para conjuntos

(A ∪ B)c = Ac ∩ B c , (A ∩ B)c = Ac ∪ B c .

3
 Uniones e intersecciones de una colección indexada de conjuntos.
Dados los conjuntos de A0 , A1 , A2 , .... que son subconjuntos de un conjunto universo U y
dado un número entero no negativo n, se definen
[
n
Ai = {x ∈ U /x ∈ Ai , para al menos una i = 0, 1, 2, . . . , n}
i=0
[∞
Ai = {x ∈ U /x ∈ Ai , para al menos un entero no negativo i}
i=1
\n
Ai = {x ∈ U /x ∈ Ai para todo i = 0, 1, . . . , n}
i=0
\∞
Ai = {x ∈ U /x ∈ Ai para todo entero no negativo i} .
i=0

Los conjuntos A y B son disjuntos si y sólo si, no tiene elementos en común; esto es A y B
disjuntos ⇔ A ∩ B = ∅.
Una partición de un conjunto A es una colección de todos los subconjuntos de A que son
disjuntos dos a dos.

2.4 Funciones
Uno de los conceptos más importantes en matemáticas es el de función. Los términos “ma-
pa”, “mapeo”, “transformación” y muchos otros significan lo mismo. Así, la palabra función
indica la dependencia de una cantidad variable con respecto a otra.
El concepto de función es muy importante en matemática discreta. Las funciones se usan
en definiciones de estructuras discretas tales como sucesiones o cadenas. También se utilizan
para representar cuánto tiempo tarda una computadora en resolver un problema de un tamaño
determinado. Las funciones recursivas, se usan frecuentemente en ciencias de la computación.
Al concepto de función se relaciona el de algoritmo. En este capítulo se incluyen la notación
para representar un algoritmo y un análisis de su complejidad.
Sean X y Y dos conjuntos. Una función f de X a Y es un subconjunto del producto
cartesiano X × Y que tiene la propiedad de que para cada x ∈ X, existe exactamente una
y ∈ Y con (x, y) ∈ f . Una notación muy usual de función f de X a Y es f : X → Y , con
y = f (x) llamada la regla de correspondencia de f.
El conjunto X se llama el dominio de f . El conjunto {y; (x, y) ∈ f } (que es un subconjunto
de Y ) se llama el rango de f .
Sea f : X → Y una función. Se dice que f es inyectiva si f (x1 ) = f (x2 ) implica que x1 = x2 ;
se dice que es sobreyectiva si la imagen o rango de f es todo Y y se dice que es biyectiva si es
inyectiva y sobreyectiva.
Sea g una función de X a Y y sea f una función de Y a Z. La composición de f con g,
denotada por f ◦ g, es la función
(f ◦ g) (x) = f (g (x))
de X a Z.
g f
|X → {z
Y → Z}
f ◦g
Sea f : X → Y una función biyectiva. La función inversa de f es la función que asigna a
un elemento y de Y el único elemento x de X tal que f (x) = y. La denotamos por f −1 ; así,
f −1 (y) = x cuando f (x) = y.

4
2.4.1 Algunas funciones importantes
En esta sección se presentan varias funciones matemáticas que a menudo aparecen en el aná-
lisis de algoritmos y en computación, así como su notación. También se recuerdan las funciones
exponencial y logarítmica, y su relación.
Sea x un número real.
La función parte entera asigna a un número real x el mayor entero que es menor o igual que
x. El valor de la función se denota por ⌊x⌋. La función parte entera por exceso asigna a x el
menor entero que es mayor o igual que x. El valor de ella se denota por ⌈x⌉.Estas funciones se
usan cuando se cuentan objetos y desempeñan un papel importante en el análisis del número
de pasos utilizados por un procedimiento para resolver problemas de un tamaño particular.
La función parte entera de x se la denota muy a menudo por [|x|].
Estas funciones, por ejemplo, se utilizan en el almacenamiento y la trasmisión de datos (en
problemas de base de datos).
Sean k cualquier entero y M un entero positivo. Entonces

k(mód M )

y se lee k módulo M , denota el residuo entero cuando M divide a k. Con mayor precisión,
k(mód M ) es el único entero r tal que

k = Mq + r

donde 0 ≤ r < M .
Por ejemplo
27 (mod 5) = 2
pues 2 es el resto de dividir 27 por 5.
Recordemos las siguientes definiciones para exponentes enteros (donde m es un entero po-
sitivo) a diferente de 0
1
am = a. a · · · a (m veces), a0 = 1, a−m =
am
Los exponentes se extienden para incluir todos los números racionales al definir, para cualquier
número racional m/n, √ √
m
am/n = n am = n a ,
En consecuencia, la función exponencial f (x) = ax está definida para todos los números reales.
La relación de los logaritmos con los exponentes es como sigue. Sea b un número positivo.
El logaritmo de cualquier número positivo x con base b se escribe

logb (x)

y representa el exponente al que debe elevarse b para obtener x. Es decir,

y = logb (x) y by = x

son declaraciones equivalentes.

Además, sabemos que si la base b es el número e, el logaritmo se llama logaritmo natural y
se escribe y = ln (x).
Las funciones exponenciales y logarítmicas son inversas la una de la otra. Es decir

y = logb (x) ⇔ by = x.

5
2.5 Sucesiones y Sumas
Intuitivamente, una sucesión s es una lista de objetos llamados elementos, los cuales forman
un conjunto, donde además los elementos están uno detrás de otro en el orden natural creciente
de los números naturales N.
Una sucesión es una función del conjunto N = {0, 1, 2, 3, ...} de enteros positivos en un
conjunto A. Para indicar la imagen del entero n se usa la notación an . Así, una sucesión se
denota por
a1 , a2 , a3 , ... o {an : n ∈ N} o simplemente {an }.
Por tanto, una sucesión es una función

s:N→A

tal que s (n) = an , al que llamamos el término n − ésimo de la sucesión.

Una diferencia sustancial entre un conjunto cualquiera y una sucesión es que en una sucesión
se pueden tener términos repetidos.
Una sucesión finita sobre un conjunto A es una función de {0, 1, 2, ..., m} en A, y se denota
con a0 , a1 , a2 , ..., am .
Algunas sucesiones importantes se dan en el siguiente ejemplo.

1. 2, 4, 6, 8, ..., 2n, ...

2. 1, 1/2, 1/3, 1/4, ..., que puede definirse mediante an = 1/n;

3. 1, 1/2, 1/4, 1/8, ..., que puede definirse mediante bn = 1/2n ;

4. 1, −1, 1, −1, ..., que puede definirse mediante cn = (−1)n , n ∈ N;

(−1)n
5. 1, −1/2, 1/3, −1/4, 1/5, ..., que puede definirse mediante an = .
n+1
6. Cadenas Suponga que un conjunto A es finito y que A se considera como un conjunto
de caracteres o un alfabeto. Entonces una sucesión finita sobre A se denomina cadena o
palabra, la cual se escribe como a1 a2 ...am , sin paréntesis. El número m de caracteres en la
cadena se denomina su longitud. El conjunto con caracteres cero también es una cadena,
la que se denomina cadena vacía o cadena nula. En el Castellano, por ejemplo, una cadena
es la palabra ”discreta”, usando el alfabeto Castellano; en otro alfabeto cualquiera, por
ejemplo, abbaaba, representa una cadena. la cadena 000000 es una cadena nula.

7. Las progresiones aritméticas y geométricas son dos tipos de sucesiones.

Como podemos observar, hay sucesiones que son crecientes, decrecientes, alternantes (en
cuanto al signo), etc.
Dos operaciones importantes en las sucesiones numéricas son sumar y multiplicar términos.
Si {an } es una sucesión, se definen la suma y el producto de sus términos mediante

X
n
ai = a0 + a1 + a2 + · · · + an
i=0

y
Y
n
ai = a0 a1 a2 · · · an
i=0

6
Ejemplo 2.2 Sea a una sucesión definida por an = 2n, n ≥ 1. Entonces

X
3
ai = a1 + a2 + a3 = 2 + 4 + 6 = 12
i=1

y
Y
3
ai = a1 a2 a3 = 2 · 4 · 6 = 48.
i=1

Ejemplo 2.3 La suma geométrica

a + ar + ar2 + ··· + arn

se puede escribir como

X
n
ari = a + ar + ar2 + ··· + arn
i=0

2.6 Cardinalidad de conjuntos.

Se dice que dos conjuntos A y B son equipotentes, tienen el mismo número de elementos o la
misma cardinalidad, y se escribe A ≃ B, si existe una correspondencia uno a uno f : A → B. Un
conjunto A es finito si A es vacío o si A tiene la misma cardinalidad que el conjunto {1, 2, ..., n}
para algún entero positivo n. Un conjunto es infinito si no es finito. Ejemplos familiares de
conjuntos infinitos son los números naturales N, los enteros Z, los números racionales Q y los
números reales R.
Los “números cardinales” son números que se consideran como símbolos asignados a con-
juntos de modo que a dos conjuntos se les asigna el mismo símbolo si y sólo si tienen la misma
cardinalidad. El número cardinal de un conjunto A se denota por |A|, n(A) o card(A). Aquí se
usará |A|.
El número cardinal del conjunto infinito N de enteros positivos es ℵ0 (“aleph-nada” o “aleph-
cero”). Así, |A| = ℵ0 si y sólo si A tiene la misma cardinalidad que N.

2.7 Matrices
Una matriz es un arreglo rectangular de datos que suele presentarse en la forma
   
a11 a12 a13 · · · a1n a11 a12 a13 · · · a1n
 a21 a22 a23 · · · a2n   a21 a22 a23 · · · a2n 
   
 a31 a32 a33 · · · a3n   a31 a32 a33 · · · a3n 
 ≡ .
 .. .. .. ..   .. .. .. .. 
 . . . .   . . . . 
am1 am2 am3 · · · amn am1 am2 am3 · · · amn

Las matrices se denotan usando las letras mayúsculas.

Sea A una matriz. Las m líneas horizontales de datos se denominan filas de A y las n líneas
verticales de datos se denominan columnas de A. Así, el elemento aij , también se denomina
entrada ij, aparece en la fila i y en la columna j. Una matriz como ésta se identifica al escribir
A = [aij ].
Una matriz con m filas y n columnas se denomina matriz de m por n, y se escribe m × n.
El par de números m y n se denominan orden o tamaño de la matriz. Dos matrices A y B son
iguales, lo cual se escribe A = B, si tienen el mismo tamaño y sus elementos correspondientes

7
son iguales. Por tanto, la igualdad de dos matrices de m × n es equivalente a un sistema de mn
igualdades, una para cada par de elementos correspondientes.
Una matriz que tiene una sola fila se denomina matriz fila o vector fila, y una matriz con
sólo una columna se denomina matriz columna o vector columna. De aquí que una matriz es un
arreglo rectangular de vectores fila y vectores columna.
Una matriz cuyos elementos son todos iguales a cero se denomina matriz cero y suele deno-
tarse por 0.
Una matriz para la que los números de filas y de columnas son iguales se llama una matriz
cuadrada. Si A es una matriz cuadrada de tamaño n × n, entonces la diagonal principal de A
consta de todas las entradas a11 , a22 , . . . , ann .
Una matriz de ceros y unos, es una matriz cuyos elementos son 0 o 1. Estas matrices
se utilizan frecuentemente para representar estructuras discretas como veremos después. En
el siguiente capítulo veremos algoritmos y veremos que los algoritmos en los cuales se usan
estructuras discretas, se basan en la aritmética booleana sobre matrices de ceros y unos.
Para esta aritmética se usan las operaciones booleanas ∧ y ∨ sobre pares de bits; están
definidas por 
 1, si aij = bij = 1
aij ∧ bij =

0, en cualquier otro caso,
y 
 1, si aij = 1 o bij = 1
aij ∨ bij =

0, en cualquier otro caso,
para dos matrices A = [aij ] y B = [bij ] del mismo orden.

2.7.1 Operaciones con matrices

Sean A = [aij ] y B = [bij ] del mismo orden.
La suma de A y B, que se escribe A + B, es la matriz que se obtiene al sumar los elementos
correspondientes de A y B. Esto es A + B = [aij + bij ].
El producto (escalar) de la matriz A por el escalar c, que se escribe cA, es la matriz que se
obtiene al multiplicar cada elemento de A por c. Esto es cA = [caij ].
Se define −A = (−1)A y A − B = A + (−B).
El producto AB de una matriz fila A = [ai ] y una matriz columna B = [bi ] con el mismo
número de elementos se define como sigue
 
b1
 b2  Xn
 
AB = [a1 , a2 , . . . , an ]  ..  = a1 b1 + a2 b2 + · · · + an bn = ak b k .
 .  k=1
bn

Es de notar que este producto da como resultado un escalar, el cual es una matriz 1×1. También,
el producto AB no está definido cuando A y B tienen un número de elementos distinto.
Sean A = [aik ] y B = [bkj ] matrices tales que el número de columnas de A es igual al número
de filas de B; por ejemplo, A es una matriz de m × p y B es una matriz de p × n. Entonces
el producto AB es la matriz de m × n, C = [cij ] cuya entrada ij se obtiene al multiplicar la
i-ésima fila de A por la j-ésima columna de B; es decir

X
p
cij = ai1 b1j + ai2 b2j + · · · + aip bpj = aik bkj
k=1

8
 P
p
para i = 1, . . . , m y j = 1, . . . , n. Escribimos C = AB y [AB]ij = aik bkj . También es de
k=1
observar que el número de columnas de la primera matriz debe ser igual al número de filas de
la segunda.
   
1 3 2 −2
Ejemplo 2.4 Si A = yB= , entonces
2 −1 0 1
      
1 3 2 −2 2 + 0 −2 + 3 2 1
AB = = =
2 −1 0 1 4 + 0 −4 − 1 4 −5
y       
2 −2 1 3 2−4 6+2 −2 8
BA = = =
0 1 2 −1 0+2 0−1 2 −1

Sea A una matriz n × n y p un entero positivo. Definimos la potencia p de A, por

Ap = Ap−1 · A, p ≥ 1,

para p = 0, definimos A0 = In (matriz identidad de orden n × n).

 
1 −3
Ejemplo 2.5 Si A = , hallar A4 .
−2 4

La transpuesta de la matriz A = [aij ]m×n es definida por la matriz B = [bij ]n×m obtenida
intercambiando las filas con las columnas, esto es, bij = aji para i = 1, . . . , n y j = 1, . . . , m.
Escribimos B = At y [At ]ij = aji .
Diremos que una matriz A, n × n, es simétrica si At = A y es antisimétrica si At = −A.
La matriz identidad es la matriz cuadrada In = [I]ij,n×n definida como

1, i = j
Iij = ,
̸ j
0, i =

es decir  
1 0 ··· 0
 0 1 ··· 0 
 
In =  .. .. .
 . ··· . 
0 0 ··· 1
Sean A = [aij ] y B = [bij ] matrices de ceros y unos del mismo orden m × n. Se llama matriz
unión de A y B, denotada por A ∨ B, a la matriz de ceros y unos cuyo elemento ij es aij ∨ bij .
Se llama matriz intersección de A y B, denotada por A ∧ B, a la matriz de ceros y unos cuyo
elemento ij es aij ∧ bij .

Ejemplo 2.6 Calcular las matrices A ∨ B y A ∧ B si

   
1 0 1 0 1 0
A= ,B = .
0 1 0 1 1 0

El producto booleano de las matrices de ceros y unos dadas, A = [aij ] de orden m × p y

B = [bij ] de orden p × n, denotado por A ⊙ B, es la matriz cuyo ij − ésimo elemento es cij ,
dado por
cij = (ai1 ∧ b1j ) ∨ (ai2 ∧ b2j ) ∨ · · · ∨ (aik ∧ bkj ) .

9
Ejemplo 2.7 Dadas las matrices
 
  1 0
1 0 1
A= y B =  0 1 ,
0 1 0
1 0

hallar A ⊙ B.

Dada una matriz de ceros y unos cuadrada A y k ∈ Z+ , la potencia boolena k − ésima de

A es el producto booleano de A consigo misma k veces. Lo denotamos por A[k] . Se tiene que
A[0] = In .

10
2.8 Ejercicios
1. Sea U = {1, 2, ..., 9} el conjunto universo, y sean A = {1, 2, 3, 4, 5}, C = {5, 6, 7, 8, 9}, E =
{2, 4, 6, 8}, B = {4, 5, 6, 7}, D = {1, 3, 5, 7, 9}, F = {1, 5, 9}. Encuentre:

(a) Ac , B c , Dc , E c
(b) A\B, B\A, D\E
(c) A∆B, C∆D, E∆F .

2. Determine el conjunto potencia P(A) de A = {a, b, c, d}.

3. Encuentre todas las particiones de A = {a, b, c, d}.

4. Determine si cada una de las siguientes expresiones es o no una partición del conjunto N
de enteros positivos:

(a) [{n/n > 5}, {n/n < 5}];

(b) [{n/n > 6}, {1, 3, 5}, {2, 4}];
(c) [{n/n2 > 11}, {n/n2 < 11}].

5. Se dice que un conjunto A es finito si existe una correspondencia biunívoca o uno a

uno entre los elementos de A y los elementos de Nn = {1, 2, . . . , n}, donde n es algún
entero positivo fijo. Se dice que un conjunto es infinito contable (o infinito numerable) si
existe una correspondencia biunívoca entre los elementos del conjunto y los elementos de
N = {1, 2, 3, . . .}. Un conjunto es infinito no numerable si no es infinito numerable.
En los ejercicios siguientes, determinar si el conjunto dado es finito, infinito numerable o
infinito no numerable.

(a) A = {x/x ∈ R,2 ≤ x ≤ 3}

(b) A = {x/x ∈ Z, 2 ≤ x < ∞}
(c) A = {x/x ∈ Q,0 ≤ x < ∞}
(d) A = {x/x ∈ Z, −100000 ≤ x ≤ 15}

6. En los ejercicios siguientes, determinar si la función dada es biunívoca para todos los
valores de su dominio.

(a) f (x) = x2 + x
(b) f (x) = x3 + x2
√
(c) f (x) = x − 1, x ≥ 1
(d) f (x) = |x|
(e) f (x) = x
x−5
,x ̸= 5
2
(f) f (x) = ln (x )

7. Sea A = {a, b, c}, B = {x, y, z}, C = {r, s, t}. Sean f : A → B y g : B → C definidas

por f = {(a, y), (b, x), (c, y)} y g = {(x, s), (y, t), (z, r)}. Encuentre: a) la composición de
funciones g ◦ f : A → C; b) Im(f ), Im(g), Im(g ◦ f ).

8. Encuentre: a) ⌊7.5⌋, ⌊-7.5⌋, ⌊-18⌋; b) ⌈7.5⌉ , ⌈-7.5⌉ ,⌈ -18⌉.

11
 9. Si k es negativo, |k| se divide entre M para obtener el residuo r′ . Entonces k (mód M ) =
M − r′ (cuando r′ ̸= 0). Encuentre: a) 25 (mód 7); b) 25 (mód 5); c) -35 (mód 11); d) -3
(mód 8).

10. Sea A = {a, b, c}. Si se hace β1 = b, β2 = a, β3 = a, β4 = c, se obtiene una cadena sobre

A. Esta cadena se escribe como baac.

(a) Haga una lista de todas las cadenas sobre A = {0, 1} de longitud 2.
(b) Haga una lista de todas las cadenas sobre A = {0, 1} de longitud 2 o menos.
(c) Haga una lista de todas las cadenas sobre A = {0, 1} de longitud 3.
(d) Haga una lista de todas las cadenas sobre A = {0, 1} de longitud 3 o menos.

11. Calcule las sumas y productos de los ejercicios siguientes.

P
5
(a) (k + 1)
k=1
Q
4
(b) k2
k=1
P3 1
(c) i
i=0 2
Q
4
(d) (−1)j
j=0

P
4
(e) i (i + 1)
i=1
 
P
10 1 1
(f) −
k=1 k k+1

12. Sean las matrices A y B dadas por

   
0 1 −1 1 −1
A= 2 3 1  y B =  5 9 .
4 −1 6 0 1

Calcular la matriz producto AB.

 
1 −1
13. Sea A = .
0 1

(a) Hallar A2 y A3 .
(b) Hallar An .

14. Hallar A ⊙ B si  
1 0  
  1 1 0
A= 0 1 , B=
0 1 1
1 0

12