UNIDAD 2_CONCEP FUND_2015

Vista previa del material en texto

UNIDAD II 
CONCEPTOS FUNDAMENTALES 
PARA PROGRAMACION 
TEORIA 
 
MATEMATICA DISCRETA 
2015 
CONTENIDO 
2 
Teoría de Conjuntos 
Métodos de Conteo 
Sucesiones numéricas: 
División en los Enteros. 
 
 TEORIA DE CONJUNTOS 
 Los conjuntos fueron estudiados formalmente por 
primera vez por George Cantor (1845-1918). 
 Nuestro interés en los conjuntos se debe tanto al 
papel que representan en las matemáticas como a su 
utilidad en la modelización e investigación de 
problemas en la informática 
3 
CONJUNTOS 
 Definición: Un conjunto es la reunión de objetos de cualquier 
naturaleza bien definidos y diferenciables entre si. A dichos objetos 
se les llama elementos del conjunto 
 
 Notación: 
 Para conjuntos , letras mayúsculas : A 
 Para elementos , letras minúsculas : a 
 Se indican como una lista encerrada entre llaves, con elementos 
no ordenados y sin repetir: A = { a , b , c } 
 Si un elemento pertenece a un conjunto: a  A. 
 Si un elemento no pertenece a un conjunto: x  A. 
 
4 
FORMAS DE DEFINIR UN CONJUNTO 
Por extensión, enumerando todos y cada uno de sus elementos. 
 
Por comprensión, diciendo cuál es la propiedad que caracteriza a los 
elementos. 
Se expresa A = { x / P(x) } 
 
Ejemplos: 
A = { x / x + 1 = 5 } = { 4 } 
 
B = { x / x2 = 2 } = { -2 , 2} 
 
C = {x Z / x es positivo y par } = {2, 4, 6, 8,…} 
 
 
5 
Se lee: El conjunto A 
esta formado por los 
números reales x tal 
que sumados a 1 da 
por resultado 5 . 
CONJUNTOS FINITOS E INFINITOS 
 Un conjunto A se dice finito si tiene n elementos distintos 
donde n  N. 
 Se dice que n es el cardinal de A y se lo indica: A = n. 
 Ejemplos: 
 Si A={ x / x es una letra del abecedario} , entonces |A|=27 
 
 Un Conjunto se dice infinito si no es finito. 
 A su vez los conjuntos infinitos se clasifican en numerables y 
no numerables 
 Ejemplos: N , Z y R son conjuntos infinitos. N y Z numerables 
y R no numerable 
 
 
6 
CONJUNTO VACIO, UNITARIO Y UNIVERSAL 
 Un conjunto se dice vacio si no tiene elementos. Su cardinal 
es 0 y se lo indica con  . 
 
 Un conjunto se dice Unitario si tiene exactamente un 
elemento. Su cardinal es 1 
 
 Al conjunto que contiene todos los elementos del tema de 
referencia se le llama Conjunto universal y se denota con la 
letra U. 
 
7 
Para el estudiante: Dé ejemplos de cada uno 
ACTIVIDAD Nº1 
8 
¿Cuál de los siguientes conjuntos son vacios? Cual es 
unitario? ¿Cuál puede considerarse el universo al que 
pertenecen todos? 
a) A = { x / x es decano de la FRT } 
b) B = { x / x es alumno de la FRT que viajo a la Luna} 
c) C = { x / x es profesor de la FRT que trabaja en la UNT} 
DIAGRAMAS DE VENN 
 
Una forma de representación gráfica para los conjuntos es 
el diagrama de Venn. El conjunto universal U se representa 
por el interior de un rectángulo y todos los demás conjuntos 
se representan por regiones cerradas incluidos en el 
universo. 
 
9 
IGUALDAD DE CONJUNTOS 
Se dice que dos conjuntos A y B son iguales si y solo si tienen 
los mismos elementos y se escribe: 
 
 A = B. 
Ejemplo: 
 a)Si A ={1, 2, 3} y B = {x Z/0<x<4 } entonces A = B. 
 
 b)Si A ={1, 2, 3} y B = {x Z /0x<4 }entonces A  B. 
 
 
10 
 CONJUNTOS DISJUNTOS 
 
 Se dice que A y B son disjuntos si A y B no tienen 
elementos en común . 
 En un diagrama de Venn la región que representa a A 
puede dibujarse separada de la región que 
representa a B . 
 
11 
ACTIVIDAD Nº2 
12 
Sea U = N 
Analizar si los siguientes pares de conjuntos son disyuntos 
 
a) A = { x / x es par} y B = { x / x es impar} 
 
b) A= { x / 2x es par} y B = { 1} 
 
c) A = { x / x2 – 4 = 0} y B = { x / x2 –8x+15 = 0 } 
 
 
DIAGRAMAS DE VENN DEL CASO GENERAL 
 
 Si A y B son dos conjuntos arbitrarios, entonces es 
posible que algunos elementos estén en A pero no en 
B, algunos en B pero no en A, algunos en los dos: A y 
B, y algunos ni en A, ni en B. Su representación general 
es 
 
13 
ACTIVIDAD Nº3: 
 
14 
Suponga que U={ x / x es alumno de la FRT} , A = { x / x es alumno de la FRT 
que juega futbol } y B ={x / x es alumno de la FRT que juega básquet} 
Diga cuales son las características de cada una de las zonas 
i 
c 
b 
f 
e 
a 
h g 
d 
SUBCONJUNTO DE UN CONJUNTO 
 Se dice que A es un subconjunto de B si y sólo si se cumple que: 
 x, [ xA  x B] 
 Se denota A  B y se lee “Todo elemento de A pertenece a B” 
 
 También se dice que A está incluido en B o que B contiene a A 
 El símbolo  se llama “Símbolo de inclusión amplia” 
 
 
Si A es subconjunto de B pero en B existen elementos que no pertenecen a A, se 
dice que A es subconjunto propio de B 
Se escribe AB 
El símbolo  se llama “ símbolo de inclusión estricta” 
 Si A no es un subconjunto de B, se escribe A B 
 
15 
TEOREMA 1: Propiedades de la Inclusión 
1) 1) Si A es un conjunto cualquiera, se cumple que 
a) A  A b) Ø  A c) A  U 
 
 2) Si A , B y C son conjuntos cualesquiera, se 
cumple que: 
a) Si A  B y B  A entonces A = B 
 
b) Si A  B y B  C entonces A  C 
16 
Demostración de Teorema 1_1º parte 
 1) a) A  A 
 
 
 1b) Ø  A 
 
 
 
 1c) Se deja para el estudiante 
Demostración (por contradicción): 
Suponga lo contrario: Ø  A 
Entonces, debe existir un elemento en el Ø que no pertenezca a A . 
Absurdo !! Ø no tiene elementos. Por lo tanto se concluye que Ø  A 
 
Demostración(directa): 
Es evidente por la definición, ya que gracias a ella se puede afirmar 
que “Todo elemento de A, pertenece a A” 
17 
Demostración de Teorema 1_2º parte 
 2) a) Si A  B y B  A entonces A = B 
 
 
 
Demostración(directa): 
Si A  B , entonces x, [xA  x B] (todos los elementos de A pertenecen a B) 
Si además B  A , entonces x, [xB  x A] (todos los elementos de B pertenecen a A) 
Por lo tanto A y B tienen los mismos elementos , con lo que se concluye A=B 
 2) b) Si A  B y B  C entonces A  C 
 
 
 
 
Demostración(directa): 
Si A  B , entonces x, [xA  x B] (todos los elementos de A pertenecen a B) 
Si además B  C , entonces x, [xB  x C] (todos los elementos de B pertenecen a C) 
Por lo tanto, por Silogismo Hipotético, se tiene que xA  x C , x . 
Por lo tanto A  C 
18 
Conjunto Potencia o 
Conjunto Partes de un conjunto 
Si A es un conjunto, el conjunto de todos los 
subconjuntos de A se denomina conjunto potencia de 
A o conjunto partes de A y se designa por P(A). 
Si |A|=n , entonces |P(A)|=2n 
 Ejemplo: 
Si A = {a,b} entonces P (A) = { Ø , {a} , {b} , A }. 
 
 
 
Observaciones 
Diremos que Ø P(A) , A P(A) ,.. 
También que {Ø}  P(A) , {{a} , {b}}  P(A),… 
 
19 
Operación UNION 
 
 Sean A y B dos conjuntos , llamamos Unión de A y B al 
conjunto formado los elementos de A o de B o de ambos. 
Simbólicamente 
A  B = { x / x A  x  B}. 
 
 
 
 
20 
Observación: La zona sombreada representa al resultado 
Operación INTERSECCION 
 Sean A y B dos conjuntos , llamamos Intersección de A y B 
al conjunto formado por los elementos que pertenecen 
simultáneamente a A y a B . Simbólicamente 
A  B = { x / x A  x  B}. 
Caso particular: Si A B = entonces son disjuntos 
 
 
21 
Observación: La zona sombreada representa al resultado 
 
 Dados dos conjuntos A y B, se define la DIFERENCIA 
A – B como el conjunto formado por los elementos 
de A que no pertenecen a B 
A - B = { x  A / x  B}. 
 
 
22 
Operación DIFERENCIA 
Observación: La zona sombreada representa al resultado 
 Por la definición anterior se tendrá que: 
B - A = { x  B / x  A }. 
 Definimos DIFERENCIA SIMÉTRICA entre A y B al conjunto 
de todos los elementosque pertenecen a solo un conjunto, 
a A o a B, pero no a ambos. Simbólicamente 
A  B = (A - B)  (B - A). 
 
23 
Operación DIFERENCIA SIMETRICA 
Observación: La zona 
sombreada representa 
al resultado 
Operación COMPLEMENTO 
 Si AU, a la diferencia U - A se le llama COMPLEMENTO 
de A respecto de U y se denota A' o Ac . 
 Esto es A' = U – A = { x U / xA} 
 
24 
Observación: La zona sombreada representa al resultado 
ACTIVIDAD Nº4 
1) Expresar en palabras y simbólicamente las 
características de los elementos a , b , c , d, e , f y g 
f 
g 
C 
d 
e 
b 
c 
a 
A 
B 
U 
25 
26 
2) Sea A ={x/x es argentino y jugador de futbol}, 
 B={x/x es argentino y jugador de básquet} y 
 U = ={x/x es argentino} 
 Exprese por comprensión los siguientes conjuntos y 
represente a cada apartado en un diagrama de Venn 
 
BA)f)'BA()e
'B'A)d'A)c
AB)bBA)a



TEOREMA 2: PROPIEDADES DE LAS OPERACIONES 
a) Ley de Idempotencia 
 A  A = A A  A = A 
b) Ley Conmutativa 
 A  B = B  A A  B = B  A 
c) Ley Asociativa 
 A  ( B  C ) = ( A  B )  C A (B  C) = (A  B)  C 
d) Ley de Absorción 
 A  ( A  B ) = A A  ( A  B ) = A 
e) Ley Distributiva 
 A (B  C) = (A  B) (A  C) A (B  C) = (A  B) (A  C) 
f) Ley de los Complementos 
 A  A' = U A  A' = Ø 
 
27 
Demostración: Teorema 2 
28 
a) Ley de Idempotencia: A  A = A 
 Demostración(directa): 
Por definición de Unión se tiene que: A  A ={ x / x A  x A} 
Por propiedad de idempotencia de la disyuncion se puede escribir: 
 x A  x A  x A 
De alli que A  A = A 
b) Ley Conmutativa : A  B = B  A 
 Demostración(directa): 
Por definición de Unión se tiene que: A  B ={ x / x A  x B} 
Por propiedad conmutativa de la disyuncion se puede escribir: 
x A  x B  x B  x A 
De alli que: 
{ x / x A  x B} = {x / x B  x A} , entonces A  B = B  A 
Se deja para el estudiante el resto de las demostraciones 
a) (A')' = A. Prop. de Involución 
b) Ø ' = U y U ' = Ø. 
c) ( A  B )' = A'  B' 
 ( A  B )' = A'  B‘ Leyes de De Morgan 
d) A  Ø = A , A  U = A Prop. de los neutros 
e) A  Ø = Ø , A  U = U Prop. de Dominacion 
 
 
29 
TEOREMA 3: OTRAS PROPIEDADES 
Demostración: Teorema 3 
30 
a) Ley de Involución: (A')' = A 
 
Demostración(directa): 
Por definición de complemento se tiene que: A’ ={ x / ~(xA)} y (A’)’ ={ x / ~[~(xA)]} 
Por propiedad de la negacion se tiene que ~[~(xA)]  xA 
Por lo tanto (A’)’ = A 
c) Ley de De Morgan para la Unión: ( A  B )' = A'  B' 
 Demostración(directa): 
Por definición de Unión y de complemento se tiene que: 
 (A  B)’ ={ x / ~( x A  x B)} 
Por ley de De Morgan para las proposiciones se tiene que: 
 ~( x A  x B)  ~ x A  ~ x B 
Entonces { x / ~( x A  x B)} = { x / ~ x A  ~ x B} 
Por lo tanto ( A  B )' = A'  B' 
 
Se deja para el estudiante el resto de las demostraciones 
Partición de un conjunto 
31 
 Una partición o conjunto cociente de un conjunto 
no vacío A es una colección P={A1 , A2 …, AK } de 
subconjuntos no vacíos de A tales que: 
a) Cada elemento de A pertenece a uno de los 
conjuntos en P. Simbólicamente se escribe 
 
 
b) Si Ai y Aj son elementos distintos de P, 
entonces Ai ∩ Aj= Ø, para todo i , j = 1,…,k 
 En otras palabras, Ai y Aj deben ser disjuntos 
 
 
 
A1 
A2 
A3 A4 
A5 A6 
A 
Gráficamente 
ACTIVIDAD Nº5 
32 
Sea A = { 0,1,2 ,3,4,5,6,7,8,9} 
Determine si las siguientes son particiones de A 
a) {{0,2,4,6,8},{1,3,5,7,9}} 
b) {{0,1,2,3},{3,4,5,6},{6,7,8,9}} 
c) {{1,2,3},{4,5,6},{7,8,9}} 
CALCULO DEL CARDINAL 
Se quiere calcular el 
cardinal de un conj 
conocidos los datos de 
otros conjuntos 
Se quiere calcular el 
cardinal de un conj. del que 
se conoce la estructura de 
los elementos 
De 40 estudiantes se sabe que 30 de 
ellos practican futbol , 25 practican 
básquet y 2 alumnos ninguno de los 
dos deportes. 
Cuantos practicam futbol y basquet? 
Con los números dígitos , 
 cuantos claves de cuatro cifras 
distintas se pueden formar?. 
Dos situaciones problematicas distintas 
Ejemplo Ejemplo 
CALCULO DEL CARDINAL DE UN CONJUNTO 
 Situación problemática motivadora: 
 Suponga que en su aula hay 40 alumnos, que 30 de 
ellos practican futbol , 25 practican básquet y 2 
alumnos no practican deportes. 
33 
Puede responder las siguientes 
preguntas? : 
 ¿Cuántos alumnos practican al menos 
un deporte¿ 
Cuántos alumnos practican ambos 
deportes? 
¿Cuantos alumnos practican 
exàctamente un deporte? 
 
 
PRINCIPIO DE ADICIÓN 
 Teorema 1: 
 Si A y B son conjuntos finitos, entonces 
 AB = A + B - A B  
 
 Caso particular: 
 Si A y B son conjuntos disjuntos entonces |AB = A + B  
 Ejemplos: 
 |U|= AA’  = A + A’  |A| = |U|- |A’| 
 
 |A|=|(A – B)  (A B)|=|A – B | + |A B|  
 
 |A – B | =|A|- |A B| 
 
35 
Teorema 2: 
Si A, B y C son conjuntos finitos entonces 
 AB  C = A |+ B + C - A B - B  C - A  C + A  B  C  
 
35 
ACTIVIDAD Nº6 
 En una encuesta realizada por una empresa de Turismo se preguntó a 
110 personas sobre cuales eran los destinos preferidos por cada una. 
Bariloche fue uno de los mas preferidos, 72 personas asi lo manifestaron. 
Luego 60 personas dijeron preferir Tafi del Valle y 52 personas 
manifestaron gustar de Ushuaia. Gustaron de Bariloche y Tafi del Valle, 
30 personas; de Tafi del Valle y Ushuaia , 36 ; y de Bariloche y Ushuaia 
, 28 personas. Ademas 16 personas gustaron de los tres destinos. 
 
Responda: 
¿Cuántas personas eligieron al menos uno de estos destinos? 
¿Cuántas personas no eligieron ninguno de estos destinos? 
¿Cuántas personas eligieron Bariloche y Tafi del Valle pero no 
Ushuaia? 
¿Cuántas personas eligieron Bariloche solamente? 
 
36 
METODOS DE CONTEO - COMBINATORIA 
 Las TÉCNICAS DE CONTEO son importantes en matemáticas y en las 
ciencias de la computación, particularmente para el análisis de algoritmos. 
 Vimos anteriormente el PRINCIPIO DE ADICION, que es aplicable a casos 
donde participan las operaciones entre conjuntos. 
 Veremos ahora otras técnicas las cuales permiten contar la cantidad de 
elementos de un conjunto, sin contarlos uno por uno. Uno de los principios 
más importantes es el PRINCIPIO DE LA MULTIPLICACION 
 Dichos conjuntos pueden ser de objetos de cualquier naturaleza o pueden 
ser eventos o sucesos posibles. 
 Se dice que la COMBINATORIA es una rama de la matemática 
perteneciente al área de MATEMATICAS DISCRETAS que estudia la 
enumeración, construcción y existencia de propiedades de configuraciones 
que satisfacen ciertas condiciones establecidas. 
37 
ACTIVIDAD Nº7 
 Un identificador de etiqueta para un programa de 
computadoras, consta de una letra seguida de tres 
dígitos. Si se permiten repeticiones ¿cuántos 
identificadores distintos de etiquetas será posible 
tener? 
C998 A000 
Z123 12M3 
Razone: Los siguientes 
 son resultados posibles? 
39 
Principio de Multiplicación 
 
 Suponga que se va a efectuar los 
trabajos T1,T2 , …, Tk. Si T1 puede 
realizarse de n1 maneras, T2 puede 
hacerse de n2 maneras,…, y Tk puede 
hacerse de nk maneras, entonces la 
secuencia T1T2 …Tk puede hacerse de 
n1n2 …nk maneras 
 
T1 
T2 
Tk 
Tk 
Tk 
Tk 
Tk 
Tk 
T2 
38 
Ejemplos: las tres situaciones problemáticas siguientes 
ACTIVIDAD Nº 8 
 Cuántos passwords de cuatro letrasdistintas se 
pueden diseñar con las letras de la palabra 
MEMORIA? 
 
40 
PERMUTACIONES 
 A cada secuencia formada con todos o algunos 
elementos de A, sin repetir, se le llama Permutación 
de elementos de A 
 La cantidad de permutaciones depende del tamaño 
de A y del tamaño de la secuencia formada. 
 
 Observación: El orden de los elementos en una 
permutación es importante. Si dos secuencias tienen 
los mismos elementos pero varían en el orden son 
distintas 
41 
42 
CANTIDAD DE PERMUTACIONES 
Notación: Se usa: nPr , Pn,r o P(n,r) 
 TEOREMA 
 Sea A un conjunto de n elementos y r natural tal 
que 1r n. 
 Entonces el número nPr , el número de 
permutaciones de n objetos tomados r a la vez 
es: 
nPr = n . ( n – 1 ) . ( n – 2 ) … (n- r + 1 ) 
 
 
Caso particular : 
 Si en nPr se cumpliera que n = r , se tendrá 
 
 nPn = n . ( n – 1 ) . ( n – 2 ) … 1 = n! 
 
 Se lee: permutaciones de n en n o simplemente, 
permutaciones de n 
 A la expresión n! se le llama Factorial de un número y 
se puede demostrar que 
 0! = 1 
 n! = n.(n-1)! 
 
43 
 1.Con los cinco dígitos 1,2,3,4,5 , se pueden formar : 
5x4x3=60 números de tres cifras diferentes. 
 
2. ¿De cuántas formas pueden colocarse los 11 jugadores 
de un equipo de fútbol teniendo en cuenta que el arquero 
no puede ocupar otra posición distinta que en el arco? 
 
44 
ACTIVIDAD Nº 9 
COMBINACIONES 
 A cada subconjunto formado con todos o algunos 
elementos de A, sin repetir, se le llama Combinación de 
elementos de A 
 La cantidad de combinaciones depende del tamaño de 
A y del tamaño del subconjunto formado. 
 
 Observación: El orden de los elementos en una 
combinación no es importante, ya que una combinación 
es un conjunto. Por lo tanto, para que dos combinaciones 
sean distintas deben tener al menos un elemento distinto 
45 
 Sea A un conjunto de n elementos y r  N tal que 
1r n. Entonces el número nCr , el número de 
combinaciones de n objetos tomados r a la vez es: 
 
 
 Notación: Se usa: nCr , Cn,r o C(n,r) 
 A la expresión se le llama número combinatorio 
n sobre r 









r
n
)!rn(!r
!n
Crn






r
n
46 
El Número de Combinaciones posibles está dado 
por el siguiente Teorema: 
48 
 
 
Un grupo, compuesto por cinco hombres y siete mujeres, 
forma un comité de dos hombres y tres mujeres. De 
cuántas formas puede formarse, si: 
a. Puede pertenecer a él cualquier hombre o mujer. 
b. Una mujer determinada debe pertenecer al comité. 
c. Dos hombres determinados no pueden estar en el 
comité. 
 
 
 
ACTIVIDAD Nº 10 
SUCESIONES 
 Una sucesión es una lista ordenada de objetos. 
 Si la lista finaliza después de n pasos, n N, se dice 
que la sucesión es finita. Si la lista continua 
indefinidamente, se dice que la sucesión es infinita. 
 Notación: 
 S= (an) donde an es el término n-ésimo de la sucesión 
con nN 
 El conjunto correspondiente a una sucesión es el 
conjunto de todos los elementos distintos de la 
sucesión. 
48 
1) La sucesión 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1 es una sucesión 
finita con elementos repetidos. 
 
 
2) La lista 1, 4, 9, 16, 25, … es una sucesión infinita. 
 
 Observe que existe un patrón que nos 
 permite deducir quien sigue ya que 
cada elemento esta relacionado con la 
posición que ocupa. En este caso se 
 tiene que: 
 an = n
2 con nN 
Se dice que una sucesión está dada 
por una fórmula explícita, cuando es 
una fórmula que indica el valor que 
tiene cualquier término con solo 
reemplazar el valor de n. 
 Observe que no existe un patrón para 
los elementos de esta sucesión 
49 
EJEMPLOS 
3) La sucesión: 3, 8, 13, 18, 23,… es infinita. 
 
Observe que hay un patrón de 
comportamiento que nos permite deducir 
quien sigue en la lista ya que cada elemento 
tiene que ver con el anterior; la sucesión se 
puede expresar 
 a1 = 3 , 
 an = an-1 + 5 , 2  n <  
A las fórmulas de este tipo, que se 
refieren al término anterior para definir 
el siguiente término, se la llama fórmulas 
recursivas o recurrentes. Toda fórmula 
recursiva debe tener al menos un valor 
de partida, en este es a1 = 3 
50 
 Completa las siguientes afirmaciones 
 La fórmula recursiva c1 = 5, cn = 2cn-1, 2  n  6, define la 
sucesión finita: …………………………………………….. 
 
 La sucesión infinita 3, 7, 11, 15, 19, 23,…. puede definirse por la 
fórmula recursiva:…………………… 
 
 La fórmula recursiva de la sucesión bn = (-1)
n con nN es : 
………………………………………….. 
 
 En todos los casos dar los conjuntos correspondientes a cada 
sucesión 
51 
ACTIVIDAD Nº 11 
ARREGLOS 
 Un arreglo, puede considerarse como una sucesión de 
posiciones o celdas vacias que pueden ser llenadas por 
cualquier elemento de un conjunto determinado. Los 
arreglos pueden ser sucesiones finitas o infinitas. 
 Sea S el arreglo, el elemento asignado a la posición n 
será denotado por S(n), y a la sucesión S(1), S(2), 
S(3),… se la llamará sucesión de valores del arreglo 
S. S se considera como un objeto bien definido, aun 
cuando a algunas de las posiciones no se les haya 
asignado valores o si se cambian algunos valores 
durante la discusión. 
S(1) S(2) S(3) 
 S 
52 
ALFABETOS Y CADENAS 
 Sea A un conjunto de símbolos. Se define el conjunto A* al 
conjunto formado por todas las sucesiones finitas de los 
elementos de A. 
 A se dice ALFABETO, A* se llama LENGUAJE y a los 
elementos de A* se las llama PALABRAS procedentes de 
A, o CADENAS de A. 
 
 El conjunto A* contiene a la SUCESIÓN VACÍA o CADENA 
VACÍA, que no contiene símbolos, y se designa por  
 
53 
 Sea el alfabeto A = {a, b, c} . 
 Entonces A* = { , a , b , c , aa, ab, ac, ba, bb, bc, ca, 
cb, cc, aaa, aab, …} 
 Responda: 
 ¿Cuál es el cardinal de A*? 
 ¿Cuántas palabras de longitud 3 contiene A*? 
 ¿Cuántas palabras que comiencen con a y de longitud 4 
contiene A* ? 
 Observe que las sucesiones de A* no precisan comas. 
 
 
 
ACTIVIDAD Nº 12 
54 
CONCATENACIÓN O COMPOSICION 
DE CADENAS 
 Si w1=s1s2s3..sn y w2=t1t2t3…tk son elementos de A*, se 
define la concatenación de w1 y w2 como la sucesión 
 w1º w2 = s1s2s3..snt1t2t3…tk. 
 Observe que: 
 a) w1º w2  A* 
 b) Si w  A* entonces w   = w y   w = w 
 
Ejemplo 
Sea el alfabeto A = {a, b, c} 
Si w1= aabccc y w2= ccbacba entonces w1º w2 = aabcccccbacba 
55 
DIVISION DE ENTEROS 
 Repasaremos en un breve pantallazo la teoría 
de los números enteros por las importantes 
aplicaciones que surgen en teoría de grupos , 
códigos autoverificadores y autocorrectores, etc 
 La base de todo arranca en la división de 
enteros, sin expresar los resultados como números 
racionales sino indicando el cociente y el resto 
enteros 
58 
DIVISIÓN EN LOS ENTEROS 
 
 TEOREMA: ALGORITMO DE LA DIVISION 
 Si m y n son enteros no negativos, con n 0 y m > n , entonces 
existen dos enteros no negativos únicos q y r , con 0  r < n tal 
que 
m = q.n + r 
 Caso particular: 
 Si r = 0, se tiene que m = q . n y se dice que la división es exacta 
 En este caso se escribe n|m y se lee de diversas formas: 
n divide a m 
n es factor de m 
n es divisor de m 
m es múltiplo de n 
m es divisible entre n 
59 
 Diga verdadero o falso, justificando su respuesta 
a) 4|2 
b) 3|6 
c) 8|8  8|16 
d) 2|3  2|6 
e) Si a|b entonces b|a , cualquiera sean a y b 
f) Si a|b entonces no es cierto que b|a 
 
 
60 
ACTIVIDAD Nº 14 
 TEOREMA: PROPIEDADES DE LA DIVISIBILIDAD 
 
Sean a, b y c son enteros no negativos 
a) a|a y 1|a , para cualquier a natural 
 
b) Si a b y a c, entonces a (b+c) 
 
c) Si a b y a c , entonces a (b-c) 
 
d) Si a b o a c, entonces a (bc) 
 
e) Si a b y b c, entonces a c61 
Se deja las demostraciones para los estudiantes 
NÚMEROS PRIMOS 
 Un número p > 1 en Z+ se llama primo si los únicos enteros 
positivos que dividen a p son p y 1. 
 Los primeros elementos de la sucesión de números primos es: 
 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ,31,… 
 
 Si un número no es primo se dice compuesto. Un número 
compuesto tiene como divisores a si mismo, a la unidad y a 
otros divisores primos 
 Son compuestos los números: 4 , 6 , 8 , 9 , 10 , etc 
 
 Existe una infinidad de números primos 
 
 
62 
 Importancia de los 
Números Primos 
Los teóricos de los números 
consideran a los números 
primos los números más 
importantes de todos, 
porque son los átomos de la 
matemática. Los números 
primos son los bloques de la 
construcción numérica, 
porque los demás números 
pueden ser creados 
multiplicando combinaciones 
de números primos. 
63 
Algoritmo para probar si un entero N>1 es primo 
 Paso 1: Verifique si N es 2. Si lo es, N es primo. Si no 
lo es, prosiga con el paso 2. 
 Paso 2: Verifique si 2|N. Si es afirmativo, N no es 
primo; de lo contrario, prosiga al paso 3. 
 Paso3: Calcule mayor entero k menor a N. Luego 
siga con el paso 4 
 Paso 4: Verifique si D|N, en donde D es cualquier 
número impar tal que 1<D K. Si D|N, entonces N no 
es primo; de lo contrario, N es primo 
64 
Ejemplo: Pruebe que N=113 es primo 
1) 113 no es 2, entonces sigo con el paso 2 
2) 113 no es par, entonces sigo con el paso 3 
3) Calculo el mayor entero k cercano a 113 . Se tiene k=10 
4) Tomo D, los impares tales que 1 < D 10 y calculo si 
D|113 
1) Para D=3 , se tiene que 3 no divide a 113 
2) Para D = 5 , se tiene que 5 no divide a 113 
3) Para D = 7 , se tiene que 7 no divide a 113 
4) Para D = 9 , se tiene que 9 no divide a 113 
FIN 
RESULTADO: 113 es primo 
 
 
65 
TEOREMA FUNDAMENTAL DE LA ARITMÉTICA 
 
 Todo entero positivo n > 1 puede escribirse en forma única 
como n = p1
k1.p2
k2.… ps
ks , donde p1<p2<…<ps son primos 
distintos que dividen a n, y las k son enteros positivos. 
 
 Ejemplos 
 
 9 = 3.3 = 32 24 = 8.3 = 23.3 
 30 = 2.3.5 315 = 9.35 = 32.5.7 
 
66 
MÁXIMO COMÚN DIVISOR 
 
 Sean a, b , k Z+ . Se dice que k es un divisor común de a y b si y 
sólo si k a y k b. 
 
 Si d es el mayor de los divisores comunes, a d se le llama máximo 
común divisor o MCD de a y b y se expresa 
d = MCD(a,b) 
 
 Ejemplo: MCD(8,12)=4 
 
 Observe que MCD(a,b) = MCD(b,a) 
 
 Si el MCD(a, b) = 1, se dice que a y b son primos relativos o 
coprimos 
 
 Ejemplo: 15 y 16 son coprimos pues MCD(15,16)=1 
67 
ALGORITMO DE EUCLIDES PARA EL CALCULO DEL MCD 
 
 Sean a,bZ+ con a>b . Sea r el resto de la división 
de a en b. Entonces 
 a) MCD (a,b) = MCD(b,r) 
 b) El MCD(a,b) se obtiene realizando divisiones 
sucesivas entre divisores y restos. El valor de 
MCD (a,b ) es el valor del último resto no nulo . 
Simbólicamente: 
MCD (a,b)=MCD (b,r1)=MCD (r1,r2)=...=MCD (rn-1,rn) = rn 
 
donde r1 es el resto de la división entre a y b, , r2 es el resto de 
la división entre b y r1 , r3 es el resto de la división entre r1 y r2, 
…, rn es el resto de la división entre rn-2 y rn-1 de tal modo que rn 
es el último resto no nulo 
 
69 
Ejemplo 
 Calcule MCD(540 , 514) 
Solución: 
540=514.1+26 
514=26.19+20 
26=20.1+6 
20=6.3+2 
6=2.3 
MCD (540 , 514 )=2 
70 
TEOREMA 
 Si a y b Z+ , entonces MCD(a,b) = MCD(a-b,b) 
Demostración: 
Si c | a y c | b, entonces c | a – b ( por teorema anterior) 
Esto es: los divisores de a y b también son divisores de a – b 
Por otro lado, si k|(a – b ) y k|b, entonces k|(a – b + b) . Esto es k|a 
 
Por lo tanto a , b y a – b comparten los mismos divisores y por lo 
tanto también el MCD 
 
Observación 
Este teorema es particularmente muy importante pues es el que se usa para los 
algoritmos de computadora. El mismo propone que hagamos restas (o sumas ) para el 
calculo del MCD , achicando de esta manera los números intervinientes 
Ejemplo: 
MCD (1000,315)=MCD(315,685) 
71 
Ejemplo 
 Calculo de MCD(540 , 514) 
por restas sucesivas 
MCD (540 , 514 )=2 
72 
a b a-b 
540 514 26 
514 26 488 
488 26 462 
…. …. …. 
46 26 20 
26 20 6 
20 6 14 
14 6 8 
8 6 2 
Obs: Se realizaron 24 restas 
MÍNIMO COMÚN MÚLTIPLO 
 Sean a, b y k  Z+ 
 Si a k y b k, se dice que k es un múltiplo común de 
a y b. 
 
 A la k más pequeña de éstas se la denomina mínimo 
común múltiplo de a y b, y se escribe 
 MCM (a, b) 
 
 
73 
TEOREMA 
Si a y b están en Z+, entonces 
 MCD (a,b) . MCM(a, b) = a .b 
Demostración: Se deja para el estudiante 
 
 
Ejemplo 
Calcule MCM(540 , 514) 
 
Vimos que MCD(540 , 514)=2 , entonces 
 MCM(540 , 514) = 540 . 514 /2 = 277560/2= 138780 
74 
MAPA CONCEPTUAL UNIDAD 2 
73