UNLAM - DIIT –MATEMÁTICA DISCRETA

CONJUNTOS
 Conjunto: colección o reunión de elementos con ciertas particularidades o no. Un conjunto es
cualquier agrupación o colección de objetos o entidades.
 Un elemento es cada uno de los objetos que forman un conjunto.
Para denotar conjuntos utilizaremos letras mayúsculas, y para elementos se usarán letras
minúsculas.
Asociado a los conceptos antes mencionados, surge la noción de "pertenencia". La pertenencia es
un concepto que permite observar la posición de un elemento cualquiera, con respecto a un
conjunto, también cualquiera.
Para indicar la pertenencia de un elemento a un conjunto será utilizado el símbolo  . La
proposición a  A se lee a pertenece a A. Su negación es a  A, que se lee a no pertenece a A.

Decimos que pertenencia se da entre elemento y conjunto y nunca entre conjunto y conjunto.

DEFINICIÓN DE UN CONJUNTO Un conjunto está definido o está determinado cuando se conocen

todos y cada uno de los elementos que lo forman.
Se usan dos maneras para definir un conjunto:
 Extensión o enumeración, Un conjunto se determina por extensión si y sólo si se enumeran
todos los elementos que lo constituyen.
 Comprensión. Un conjunto se define por comprensión si y sólo si se da la propiedad que
caracteriza a todos sus elementos.

CONJUNTOS ESPECIALES
 El conjunto universal está formado por todos los elementos que intervienen en el tema de
interés; se denotará con U.
 Un conjunto vacío es aquel que carece de elementos.    x / x  x (Conjunto vacío)

CARDINALIDAD A

Llamaremos cardinal de A, al número de elementos distintos de A

CUANTIFICADORES
Universal x, y,.....
Existencial x, y,......

INCLUSIÓN un conjunto A está incluido en otro conjunto B si, y sólo si, todos los elementos de A lo
son también de B.
 (…está incluido en…)  (…no está incluido en…)

Prof. Lic. Christian L. Staple 1

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Con estos símbolos, podemos enunciar la definición de inclusión así: A  B  x :  x  A  x  B 

PROPIEDADES
 Sea U el conjunto Universal y A un conjunto cualquiera, entonces se verifica A : A  B
 Sea A un conjunto cualquiera, entonces A :   A
 Propiedad reflexiva A : A  A
 Propiedad Transitiva Sean A, B y C conjuntos de un Universal, si
A, B, C :  A  B  B  C  A  C 

 Propiedad antisimétrica Sean A y B dos conjuntos cualesquiera

A, B :  A  B  B  A  A  B 

IGUALDAD DE CONJUNTOS
Dos conjuntos A y B son iguales, si y solo si tienen los mismos elementos. Es decir, Cada elemento
del conjunto A es un elemento del conjunto B y cada elemento de B es un elemento de A

A  B  x :  x  A  x  B    x  B  x  A

Definición: dos conjuntos son iguales si son idénticos, es decir, SI tienen los mismos elementos.
A B  A BB  A
Diremos que dos conjuntos NO son iguales si A  B   x  A  x  B    x  B  x  A

CONJUNTO DE PARTES: El conjunto de partes de A es el conjunto cuyos elementos son TODOS los
subconjuntos de A, lo denotamos P(A)
Si A es un conjunto finito de n elementos, entonces el cardinal de P(A) es 2n

DIAGRAMA DE VENN: Los diagramas de Venn permiten visualizar U

gráficamente las nociones conjuntistas y se representan mediante
A
círculos inscritos en un rectángulo. Los círculos corresponden a los
conjuntos dados y el rectángulo al conjunto universal.

COMPLEMENTO:
El complemento de un conjunto A, son todos los Gráficamente:
Ac A
elementos que no están en el conjunto A y que están
U
en el universo. A=Ac =  x / x  U  x  A

Ejemplo:

U= {1,2,3,...10} A={ 3,4,6,7} Ac= {1,2,5,8,9,10}

Prof. Lic. Christian L. Staple 2

 UNLAM - DIIT –MATEMÁTICA DISCRETA

INTERSECCIÓN DE CONJUNTOS: La intersección de dos conjuntos A y B, es un conjunto cuyos

elementos son comunes a A y B. A  B  x / x  A  x  B

U
B
A

Ejemplo: A={7,8,9,10,11,12} B={5,6,9,11,13,14} A  B={9, 11}

Conjuntos disjuntos: Dos conjuntos son disjuntos si no tienen

elementos comunes. A  B   U A B

UNIÓN DE CONJUNTOS: La unión de dos conjuntos A y B es un conjunto cuyos elementos

pertenecen a A o a B. Notación: A  B   x / x  A  x  B

U
UA B B
A

Ejemplo A={3,4,5,8,9} B={5,7,8,9,10} AB= {3, 4, 5, 7, 8, 9, 10}

DIFERENCIA DE CONJUNTOS: La diferencia de dos conjuntos A y B, es un conjunto cuyos

elementos son aquellos que están en el conjunto A, pero no en el conjunto B.

A  B  {x / x  A  x  B}  A  B

U U U
UA B A
A B
B

Ejemplo: C = {u, v, x, y, z} D = {s, t, z, v, p, q} C - D = {x, y, u}

Prof. Lic. Christian L. Staple 3

 UNLAM - DIIT –MATEMÁTICA DISCRETA

DIFERENCIA SIMÉTRICA: Es el conjunto de elementos que perteneces a A o a B, pero no a ambos.

Es decir, son aquellos que están en A, pero no en B, unidos con aquellos que están en B, pero no en
A.
Notación: AB  x / x  A  x  B


A  B   A  B    B  A    A  B   A  B   A  B  B  A  
A B U
U
) A B
)
)

Ejemplo: A = {1, 3, 4, 5, 6, } B = {2, 6, 3, 7,9} AB = { 1, 4, 5, 7, 2, 9}

PROPIEDADES ALGEBRAICAS
1. IDEMPOTENCIA A  A =A A  A =A
2. CONMUTATIVA A  B =B  A A  B =B  A

3. ASOCIATIVA A   B  C = A  B   C

A   B  C  =  A  B  C

4. ABSORCIÓN A   A  B  A

A   A  B  A

5. DISTRIBUTIVA A   B  C    A  B   A  C 

A   B  C    A  B   A  C 

6. IDENTIDAD A =A A  U=U

A = A  U=A

7. INVOLUTIVA A  C C
A

8. DEL COMPLEMENTO A  AC  U A  AC  
UC   C  U

 A  B  AC  BC
C
9. DE DE MORGAN

 A  B  AC  BC
C

Prof. Lic. Christian L. Staple 4

 UNLAM - DIIT –MATEMÁTICA DISCRETA

LENGUAJE, GRAMÁTICA Y AUTÓMATAS

Un ALFABETO es un conjunto no vacío y finito de símbolos. Los símbolos del alfabeto son las letras,
strings o caracteres. Suele indicarse con la letra V.
Toda secuencia finita de letras de un alfabeto se denomina palabra o cadenas o hileras de V.

PALABRA VACÍA o cadena vacía, es la cadena que no contiene símbolos, se denota con la letra
griega λ
A partir de V, se puede formar el conjunto V * formado por todas las secuencias finitas de los
elementos de V

V*   v i
i 0

También se define el conjunto V+ formado por todas las hileras NO nulas de V


V    vi  V*    
i 1

LONGITUD DE LA CADENA Es la cantidad de símbolos de V que tiene la cadena, contadas tantas

veces como aparezcan. Se denota long w  w “número de letras de w”

CONCATENACIÓN: w V * , y V * la concatenación o el producto de palabras es otra palabra de

V * palabra formada por los símbolos de x seguidos por los símbolos de y.

Ejemplo: Sea V = {0,1} alfabeto binario, sean v, w e y palabras de V*. Sean v=0111, w=1110
La palabra y= vw que leemos “v concatenado con w” queda: y = 01111110

PROPIEDADES DE LA CONCATENACIÓN
1. Elemento neutro, la hilera nula λ es el neutro de la concatenación w V * se verifica
  w  w   w
2. Asociativa, w V * , y V * , z V * se verifica que  w  y   z  w   y  z 

3. No es conmutativa w V * , y V * se verifica que w  y  y  w

4. La longitud de la concatenación es igual a la suma de las longitudes de dichas palabras

long  w  y   long w  long y

Prof. Lic. Christian L. Staple 5

 UNLAM - DIIT –MATEMÁTICA DISCRETA
n
POTENCIACIÓN: si concatenamos n veces una cadena x, 
x.x.x.x
.x. x obtendremos x .
x.x.x.......
n veces

Si n  0  w0  

n 1  w1  w

n2  wn  w  wn1
Propiedad la longitud de la potencia n-ésima de la palabra w es igual a n veces la longitud de w
long wn  n  long w

REFLEXIÓN, INVERSA O TRASPOSICIÓN: si la palabra x está formada por los símbolos a1, a2, ...., an,
entonces la palabra inversa de x, que indicamos xR, se forma invirtiendo el orden de los símbolos en
la palabra; xR = an, ...., a2, a1.
Sea w = abc entonces wR = cba

PROPIEDADES
1. La inversa de la hilera nula es la misma palabra nula  R  

2. Involución, la inversa de la inversa de una palabra, es la misma palabra w 

R R
w

3. La inversa de la concatenación de dos palabras es igual a la concatenación de la inversa de la

segunda por la inversa de la primer palabra w V * , y V * se verifica  w  y   y R  wR

R

4. La longitud de la inversa de una palabra es igual a la longitud de la palabras

w V * se verifica que long wR  long w

UN LENGUAJE es un subconjunto de todas las palabras que se pueden formar con las letras de un
alfabeto
V, es decir es L  V*.

LENGUAJE VACIO: No tiene elementos L  

LENGUAJE NULO: Es el que tiene como único elemento la hilera nula L    

CONCATENACIÓN: Dados dos lenguajes L1 y L2, su concatenación, L1  L2 contendrá todas las

palabras que se puedan formar por la concatenación de una palabra de L1 y otra de L2.

Por ejemplo: Dados L1 = {nana, napa, lana} y L2 = {  , nana, napa, pana, palabra, papa, pala}
L1 . L2 = {nana, napa, lana, nananana, napanana,...}

Prof. Lic. Christian L. Staple 6

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDADES

1. ASOCIATIVA L1  P V *  , L2  P V *  , L3  P V *  se verifica  L1  L2   L3  L1   L2  L3 

2. NEUTRO el lenguaje nulo es el neutro de la concatenación

L  P V *  se verifica L     L  L

3. NO ES CONMUTATIVA L1  L2  L2  L1

4. ELEMENTO ABSORBENTE el lenguaje vacio es elemento absorbente de la concatenación

L  P V *  se verifica L   L  

5. DISTRIBUTIVA
1. La concatenación de lenguajes se distribuye respecto de la unión de lenguajes.

L1  P V *  , L2  P V *  , L3  P V *  se verifica L1   L2  L3    L1  L2    L1  L3 

2. La concatenación de lenguajes NO se distribuye respecto de la intersección de lenguajes.

L1   L2  L3    L1  L2    L1  L3 

3. La unión de lenguajes NO se distribuye respecto de la concatenación de lenguajes.

L1   L2  L3    L1  L2    L1  L3 

4. La de intersección lenguajes NO se distribuye respecto de la concatenación de lenguajes.

L1   L2  L3    L1  L2    L1  L3 

POTENCIA DE LENGUAJES: La potencia i-ésima de un lenguaje corresponde a la concatenación i

veces del lenguaje en él mismo; lo indicamos Li  
L.L.L.L.L.L.......L
i veces

Tengamos en cuenta que si i=0, obtenemos el lenguaje nulo que indicamos  = {  } y que si i = 1 se
obtiene el mismo lenguaje.

REFLEXIÓN, INVERSIÓN O TRASPOSICIÓN: La reflexión de un lenguaje L está formada por la

aplicación de la reflexión a cada una de las palabras del lenguaje; la indicamos

LR  x R tal que x  L

Por ejemplo: Dado L = { 0, 1 , 00, 10 }, entonces LR = { 0, 1, 00, 01 }

CLAUSURA DE KLEENE: sea V un alfabeto, sea N el conjunto de los números naturales, sea n ∈ N ∪
{0} y sea L un lenguaje de V* entonces:
n
L*=  L = L0 ∪ L¹ ∪ L² ∪ L³ ∪.... ∪ Ln es la clausura de Kleene del lenguaje L.
i 0

Prof. Lic. Christian L. Staple 7

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDADES
1. La clausura del lenguaje nulo es el lenguaje nulo

*   i   0  ¹ ²  ....  
i 1

2. La clausura del lenguaje vacio es el lenguaje nulo


*   i  0  ¹²  ....  
i 1

CLAUSURA POSITIVA: sea V un alfabeto, sea N el conjunto de los números naturales, sea n ∈ N y
sea L un lenguaje de V * entonces:
n
L+=  L = L¹ ∪ L² ∪ L³ ∪.... ∪ Ln es la clausura positiva del lenguaje L.
i 1

COMPLEMENTACIÓN Sea un alfabeto V, sea L V * el complemento de un lenguaje es el conjunto

de hileras de V * que no pertenecen al lenguaje L V *  L

RELACIONES
PAR ORDENADO: Llamamos par ordenado a b y lo indicamos (a; b) al conjunto de elementos a, b
con un criterio de orden que indica cuál es el primer elemento y cuál es el segundo.

PRODUCTO CARTESIANO: Sean A y B dos conjuntos, llamamos producto cartesiano entre A y B y lo

indicamos A x B al conjunto: C  A x B  {  a; b  tal que a  A  b  B }

RELACIÓN BINARIA: Una relación binaria R de un conjunto A en un conjunto B es un subconjunto

del producto cartesiano A x B. Si (x; y)  R se escribe x R y se dice que x está relacionado con y. En el
caso de A = B se afirma que R es una relación (binaria) sobre A.

COMO SE REPRESENTAN LAS RELACIONES

DOMINIO: Se llama dominio al conjunto formado por los primeros elementos de los pares
ordenados de la relación DR  x  A tal que  x; y   R para algún y  B

Prof. Lic. Christian L. Staple 8

 UNLAM - DIIT –MATEMÁTICA DISCRETA

IMAGEN: Se llama imagen o contradominio, al conjunto formado por los segundos elementos de los
pares ordenados de la relación I R   y  B tal que  x; y   R para algún x  A

Ejemplo: Sea R la relación en A  1, 2 , 3, 4 definida por  x; y   R si x  y .

Entonces, la relación resultante es: R  1; 2 , 1; 3 , 1; 4  ,  2; 3 ,  2; 4  , 3; 4 

El conjunto dominio de la relación R: DR  1, 2,3

Y el conjunto imagen: I R  2,3, 4

RELACIÓN RECÍPROCA O INVERSA: Sean A y B dos conjuntos y la relación R: A → B, llamamos

relación recíproca o inversa de R a R-1: B → A tal que R-1 = {(b; a) / (b; a)  R}
DR  I R1
I R  DR1

R1   2;1 ,  3;1 ,  4;1 ,  3;2  ,  4;2  ,  4;3

El conjunto dominio de la relación R: DR1  2,3, 4 Y el conjunto imagen: I R1  1, 2,3

RELACIÓN COMPLEMENTARIA: Sean A y B dos conjuntos y sea la relación R: A → B, llamamos

relación complementaria de R a:

R : A  B tal que R  { x; y  /  x; y   R}
R   AxB   R
R  1; 1 ,  2;1 ,  2; 2  ,  3;1 ,  3; 2  ,  3;3 ,  4;1 ,  4; 2  ,  4;3 ,  4; 4 

REPRESENTACIÓN MATRICIAL

Matrices Booleanas son aquellas cuyos elementos pertenecen al conjunto 0,1

Dados dos conjuntos finitos, no vacios A  a1 , a2 ,......am  y B  b1, b2 ,......bn  y una relación

R, llamamos matriz de adyacencia Booleana de la relación a:

Prof. Lic. Christian L. Staple 9

 UNLAM - DIIT –MATEMÁTICA DISCRETA

1 si  ai , bj   R

M R   mij   
0 si  ai , bj   R


Ejemplo:
Sea R la relación en A  1, 2 , 3, 4 definida por  x; y   R si x  y

R  1; 2 , 1; 3 , 1; 4  ,  2; 3 ,  2; 4  , 3; 4  R1   2;1 ,  3;1 ,  4;1 ,  3;2  ,  4;2  ,  4;3

0 1 1 1 0 0 0 0
   
0 0 1 1 1 0 0 0
MR   M R1 
0 0 0 1 1 1 0 0
   
0 0 0 0 1 1 1 0

Observaciones:

 La matriz de la relación inversa es igual a la transpuesta de la matriz de la relación M R1   M R 

t

 La matriz de la relación complemento se puede obtener intercambiando unos por ceros de la matriz
de la relación.

R  1; 1 ,  2;1 ,  2;2  ,  3;1 , 3;2  , 3;3 ,  4;1 ,  4;2  ,  4;3 ,  4;4

1 0 0 0
 
1 1 0 0
MR  
1 1 1 0
 
1 1 1 1

REPRESENTACIÓN A TRAVÉS DE UN DÍGRAFO

Una manera útil de representar una relación sobre un conjunto es

trazar su dígrafo. Para establecer el dígrafo de una relación en un
conjunto A, se marcan primero puntos o vértices que representan los
elementos del conjunto A. Si el elemento (a; b) está en la relación se
traza una flecha, llamada arco dirigido desde a hasta b.

OPERACIONES ENTRE RELACIONES

Las operaciones que usaremos son unión, intersección y diferencia
UNIÓN R1  R2  a, b   AxB /  a, b   R1 ó  a, b   R2 ó a ambos

Sean A  1, 2,3 ; B  a, b y las relaciones R1 1, a  , 1, b  ,  2, a  , 3, b  definidas de A en B.

R2  1, b  ,  2, a  ,  3, a  ,  3, b 

Por extensión R1  R2 1, a  , 1, b  ,  2, a  ,  3, a  ,  3, b 

Prof. Lic. Christian L. Staple 10

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Matricialmente

1 1   0 1  1 1 
     
M R1  R2  M R1  M R2  1 0    1 0   1 0 
1 0   1 1  1 1 


INTERSECCIÓN R1  R2  a, b   AxB /  a, b   R1 y  a, b   R2 

Por extensión R1  R2 1, b  ,  2, a  ,  3, a 

Matricialmente

1 1 0 1 0 1
     
M R1  R2  M R1  M R2  1 0  1 0  1 0
1 0   1 1   1 0 


DIFERENCIA R1  R2  a, b   AxB /  a, b   R1 y  a, b   R2   R1  R2

Por extensión R1  R2 1, a  1 1 1 0 1 0

     
M R1  R2  M R1  M R2  1 0  0 1  0 0
1 0   0 0   0 0 


PRODUCTO BOOLEANO Dadas A 0;1 , B 0;1 se define C  A  B tal que

nxm mxp

C  0;1
nxp
y además

m
Cij   a ik  bkj  i :1, 2,......, n j :1, 2,......, m
k 1

Prof. Lic. Christian L. Staple 11

 UNLAM - DIIT –MATEMÁTICA DISCRETA

COMPOSICIÓN DE RELACIONES
Sean A, B y C tres conjuntos y R1: A →B y R2: B → C dos relaciones, llamamos composición de R1
seguida de R2 e indicamos R2 o R1 a: R2oR1   a; c   AxC / b  B   a; b   R1  b; c   R2

Por ejemplo:
Sean los conjuntos A = {a, b } B = { x, y, z, t } C = { 1, 2, 3 } y las relaciones binarias:
R : A → B / R = { (a; x) , (a; z) , (b; y) , (b; z) , (b; t) }
S : B → C / S = { (x; 2) , (x; 3) , (y; 1) , (z; 2), (t; 2) }
Hallemos la composición SoR por extensión: SoR = { (a; 2) , (a; 3) , (b; 1), (b; 2) }

Matricialmente
La relación entre las matrices es: M SoR  M R  M S siendo  el producto matricial booleano

Prof. Lic. Christian L. Staple 12

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDADES DE LA RELACIÓN
PROPIEDAD REFLEXIVA: Una relación R sobre un conjunto A recibe el nombre de reflexiva si
a : a  A  aRa o a  A :  a ; a   R , es decir todos los elementos se relacionan consigo

mismo
 R es reflexiva   A  R siendo  A   a; a  / a  A

 El dígrafo de una relación reflexiva tiene un lazo en cada vértice.

 La matriz de la relación tiene sólo 1 en la diagonal principal, es decir aii  1 i

 I  MR

Por ejemplo: Sea X = {1, 2, 3, 4}

R1 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 2), (2; 3), (2; 4), (3; 3), (3; 4), (4; 4)}
La relación R1 es reflexiva porque para cada elemento x  X, se tiene que (x; x)  R1; es decir, que
(1; 1)  R1, (2; 2)  R1, (3; 3  R1 y (4; 4)  R1.
El dígrafo correspondiente a esta relación es: Su matriz de adyacencia es

En su dígrafo todos los vértices tienen bucle, y en su matriz los todos los elementos de la diagonal
principal son “1”, por la tanto la relación es reflexiva.

R2 = {(1; 1), (1; 2), (2; 1), (2; 4), (3; 3), (4; 2), (4; 4)}
La relación R2 no es reflexiva porque para el elemento 2  X, el par (2; 2)  R2 . En su dígrafo el
vértice 2 no tiene bucle, y en su matriz de adyacencia el elemento a22  1

1 1 0 0
 
1 0 0 1
M R2 
0 0 1 0
 
0 1 0 1

PROPIEDAD ARREFLEXIVA: Ningún elemento se relaciona consigo mismo

 En su dígrafo ningún elemento tiene bucle
 R es arreflexiva   A  R  

 En la matriz de adyacencia, la diagonal principal son todos “0” es decir

I  M R  N  matriz nula 

Prof. Lic. Christian L. Staple 13

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDAD SIMÉTRICA
Una relación R sobre un conjunto X se conoce como simétrica si   x; y   R se tiene que  y; x   R

 R es simétrica  R  R1

 El dígrafo de una relación simétrica tiene la propiedad de que si existe un arco dirigido de x a y
existe también un arco dirigido de y a x.
 La matriz de la relación deberá ser simétrica, es decir, espejada respecto de la diagonal

principal. Es decir R es simétrica  M R  M R1   M R 

t

Respecto del ejemplo anterior:

Sea X = {1, 2, 3, 4} R1 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 2), (2; 3), (2; 4), (3; 3), (3; 4), (4; 4)}
R1 no es simétrica porque
(1; 2)  R1 y (2; 1)  R1 , (1; 4)  R1 y (4; 1)  R1 ,

(1; 3)  R1 y (3; 1)  R1 , (2; 3)  R1 y (3; 2)  R1 ,

(2; 4)  R1 y (4; 2)  R1 , (3; 4)  R1 y (4; 3)  R1 .

En el dígrafo de esta relación se ve que la relación posee la propiedad de que si existe un arco
dirigido de x a y, no existe un arco dirigido de y a x.

1 1 1 1 1 0 0 0
   
0 1 1 1 1 1 0 0
M R1   M R 1 
0 0 1 1 1 1 1 1 0
   
0 0 0 1 1 1 1 1

M R  M R1

R2 = {(1; 1), (1; 2), (2; 1), (2; 4), (3; 3), (4; 2), (4; 4)} es simétrica ya que   x; y   R se tiene que

 y; x   R
Observemos el dígrafo de esta relación que posee la propiedad de que si existe un arco dirigido de x
a y, entonces también existe un arco dirigido de y a x.

1 1 0 0 1 1 0 0
   
1 0 0 1 1 0 0 1
M R2  M R 1 
0 0 1 0 2 0 0 1 0
   
0 1 0 1 0 1 0 1

M R  M R1

Prof. Lic. Christian L. Staple 14

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDAD ANTISIMÉTRICA
Una relación R sobre un conjunto X se conoce como antisimétrica si  x; y   R   y; x   R  x  y

 El dígrafo de una relación antisimétrica tiene la propiedad de que entre dos vértices
cualesquiera hay, a lo sumo, un arco dirigido.
 Si una relación R no tiene elementos de la forma (x; y) con x  y entonces R es antisimétrica.
 R es antisimétrica  R  R1   A con  A   a; a  / a  A

 R es antisimétrica  M R  M R1  I (matriz identidad )

Respecto del ejemplo anterior: Sea X = {1, 2, 3, 4}

 Para R1 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 2), (2; 3), (2; 4), (3; 3), (3; 4), (4; 4)}
R1 es antisimétrica porque 1;2   R1 y  2;1  R1 , lo mismo para el resto de los pares de la

relación.
También vemos en el dígrafo que hay, a lo sumo, un arco dirigido entre cada par de vértices.
1 1 1 1  1 0 0 0 1 0 0 0
     
? 0 1 1 1 1 1 0 0 0 1 0 0
M R1  M R 1  I    I
1 0 0 1 1 1 1 1 0 0 0 1 0
     
0 0 0 1 1 1 1 1 0 0 0 1

 Para R2 = {(1; 1), (1; 2), (2; 1), (2; 4), (3; 3), (4; 2), (4; 4)}
La relación R2 no es antisimétrica porque por ejemplo: 1; 2   R2 y  2;1  R2 pero 1  2

En el dígrafo podemos ver que hay más de un arco dirigido entre algunos pares de vértices.
1 1 0 0 1 1 0 0 1 1 0 0
     
? 1 0 0 1 1 0 0 1 1 0 0 1
M R2  M R 1  I    I
2 0 0 1 0 0 0 1 0 0 0 1 0
     
0 1 0 1 0 1 0 1 0 1 0 1

PROPIEDAD ASIMÉTRICA R es asimétrica si   x; y   R :  y; x   R

 R es asimétrica  R  R1  

 Gráficamente, ninguna flecha de ida tiene otra de vuelta, y no hay bucles

 R es asimétrica  M R  M R1  N (matriz nula)

Respecto del ejemplo anterior:

 R1 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 2), (2; 3), (2; 4), (3; 3), (3; 4), (4; 4)}
 R2 = {(1; 1), (1; 2), (2; 1), (2; 4), (3; 3), (4; 2), (4; 4)}
No son asimétrica

Prof. Lic. Christian L. Staple 15

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDAD TRANSITIVA
Una relación R sobre un conjunto X se conoce como transitiva si
x, y, z :  x; y   R   y; z   R   x; z   R

 El dígrafo de una relación transitiva tiene la propiedad de que siempre que existan arcos
dirigidos de x a y y de y a z entonces también existe un arco dirigido de x a z.
 R estransitiva  R  R  R

 R estransitiva  M R  M R  M R

Respecto del ejemplo anterior:

 R1 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 2), (2; 3), (2; 4), (3; 3), (3; 4), (4; 4)} es transitiva
1 1 1 1  1 1 1 1  1 1 1 1
     
? 0 1 1 1  0 1 1 1  0 1 1 1
M R1  M R1 M R1      M R1
0 0 1 1  0 0 1 1  0 0 1 1
     
0 0 0 1  0 0 0 1  0 0 0 1

 R2 = {(1; 1), (1; 2), (2; 1), (2; 4), (3; 3), (4; 2), (4; 4)} no es transitiva

1 1 0 0 1 1 0 0 1 1 0 1
     
? 1 0 0 1 1 0 0 1 1 1 0 1
M R2  M R2 M R2     M R2
0 0 1 0 0 0 1 0 0 0 1 0
     
0 1 0 1 0 1 0 1 1 1 0 1

RELACIONES DE EQUIVALENCIA
Una relación binaria es de equivalencia si es reflexiva, simétrica y transitiva.
Sea X = {1, 2, 3} R1 = {(1; 1), (1; 2), (2; 2), (2; 1), (3; 3)}
1 0 0 1 1 0
1 1 0
  Es reflexiva, ya que I  M R  0 1 0    1 1 0 
M R1   1 1 0 
0 0 1 0 0 1
0 0 1    
 

1 1 0 Es simétrica ya que M R   M R 
t

 
M 
t
R1  1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
0 0 1 Es transitiva M R  M R  M R        
  1 1 0  1 1 0  1 1 0  1 1 0
0 0 1 0 0 1 0 0 1 0 0 1
       

Prof. Lic. Christian L. Staple 16

 UNLAM - DIIT –MATEMÁTICA DISCRETA

CLASES DE EQUIVALENCIA Sea A un conjunto y R una relación de equivalencia en A. Para cada

elemento a  A definimos clase de equivalencia de a como el conjunto de todos los elementos de
A que están relacionados con a. Cla   a   x  A / xRa

En el ejemplo anterior

1   x  A / xR1  1, 2   2

 2   x  A / xR2  1, 2  1
3   x  A / xR3  3

CONJUNTO COCIENTE Sea un conjunto A donde hay definida una relación de equivalencia. Se
A
define conjunto cociente provocado por la relación al conjunto  Cl (a) / a  A
R
PARTICION Sea un conjunto A y sea P un conjunto formado por subconjuntos de A. Decimos que
P   Ai  , i Ai  A si verifica que

1. i Ai  P  Ai   los elementos de la partición son no vacías.

2. Ai , Aj  P  Ai  Aj   si i  j dos elementos distintos de la partición son disjuntos.

3. a  A Ai  P / a  Ai todo elemento de A pertenece a algún elemento de la partición.

Teorema Si R es una relación de equivalencia en un conjunto A, entonces la familia de todas las

clases de equivalencia de los elementos de A produce una partición de A.
Teorema Dado la partición de un conjunto A, puede definirse en él una relación de equivalencia R
tal que el conjunto cociente A/R coincida con partición dada.

CONGRUENCIA MÓDULO n En el conjunto de los enteros se define la relación:

aRb  a  b n  n | a – b, n  N Se lee “a es congruente con b módulo n”

 Reflexiva: x  : xRx
x   : x  x  0  x  x  0  n  n | x  x  x  xn

 Simétrica: x, y   : xRy  yRx

x, y   : xRy  x  yn  n | x  y  x  y  n  k  k      x  y   n  k 
y  x  n   k    k     y  xn  yRx

 Transitiva: x, y, z   : xRy  yRz  xRz

x, y, z   : xRy  yRz  x  yn  y  zn  n | x  y  n | y  z 

x  y  n k  k   y  z  nt  t  

Prof. Lic. Christian L. Staple 17

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Sumando M.A.M.
x  y  y  z  n  k  n  t  x  z  n   k  t    k  t     n | x  z  x  zn  xRz

Ejemplo Consideremos el caso a  b3

Las clases de equivalencia son:

Cl0  xR0  x  03  3| x  0  x  0  3  k  k    x  3  k  0  ...  6, 3,0,3,6,9... o sea

todos los múltiplos de 3.

Cl1  xR1  x  13  3| x  1  x  1  3  k  k    x  3  k  1  ...  5, 2,1, 4,7,10... o sea

todos los que al dividirlos por 3 tienen resto 1.

Cl2  xR2  x  23  3| x  2  x  2  3  k  k    x  3  k  2  ...  4, 1, 2,5,8,11... o sea

todos los que al dividirlo por 3 tienen resto 2.

 
El conjunto cociente es    3  Cl0 , Cl1 , Cl2 
R 3

CLAUSURAS O CIERRES
Sea R una relación definida en un conjunto A, supongamos que R no es de equivalencia pues no
cumple alguna propiedad. Queremos agregarle aquellos pares necesarios para que la cumpla, pero
no más de los necesarios. Es decir queremos encontrar la menor de las relaciones que incluyen a R y
que cumplen la propiedad especificada. A esta nueva relación se la llama clausura o cerradura.
 La clausura o cerradura reflexiva es la menor de las relaciones que incluyen a R y que es
reflexiva.
 La clausura o cerradura simétrica es la menor de las relaciones que incluyen a R y que es
simétrica.
 La clausura o cerradura transitiva es la menor de las relaciones que incluyen a R y que es
transitiva

CLAUSURA REFLEXIVA: r(R) es la mínima relación reflexiva que contiene a R y que se obtiene
uniendo R con los pares ordenados cuyos componentes son iguales  A   a; a  / a  A

r  R  R  A matricialmente Mr  R  M R  I

CLAUSURA SIMÉTRICA: s(R) es la mínima relación simétrica que contiene a R y que se obtiene
uniendo R con los pares ordenados invertidos de R.
s  R   R  R1 matricialmente M s R  M R  M R1

Prof. Lic. Christian L. Staple 18

 UNLAM - DIIT –MATEMÁTICA DISCRETA

CLAUSURA TRANSITIVA: t(R) es la mínima relación transitiva que contiene a R y que se obtiene
hallando la relación de conectividad
n
t  R   R    Ri
i 1

n
t  R   R   Ri  R  R 2  R3  R 4 .......  R n y M R  M R  M R2  M R3  M R4 .......  M Rn
i 1

Donde M R2  M R  M R

ALGORITMO DE WARSHALL

W0 es la matriz de la relación
Para obtener W1
Hay que analizar la columna 1: tiene unos en las posiciones1 y 3; y la
fila 1 tiene unos en las posiciones 1, 2, 3.Por lo tanto la matriz W1 tiene
que tener unos en la posición 11, 12, 13, 31, 32, 33

Luego, queda W1:

Para obtener W2
Hay que analizar la columna 2: tiene unos en las posiciones 1 y 3; y la
fila 2 tiene uno en la posición 3.Por lo tanto la matriz W2 tiene que
tener unos en la posición 13, 33 .Entonces W2 queda igual a W1

Para obtener W3
Hay que analizar la columna 3: tiene unos en las posiciones 1, 2 y 3; y la
fila 3 tiene unos en las posiciones 1, 2, 3. Por lo tanto la matriz W3 tiene
que tener unos en la posición 11,12,13,21,22,23,31,32, 33 .

Por lo que W3 es igual a:

CLAUSURA REFLEXIVA Y TRANSITIVA R*  R   a

Prof. Lic. Christian L. Staple 19

 UNLAM - DIIT –MATEMÁTICA DISCRETA

CONJUNTOS ORDENADOS  A,  
RELACIÓN DE ORDEN 
1. Reflexiva: a  A  a  a a precede a a
2. Antisimétria: a  b y b a  a  b
3. Transitiva a b y b c  a  c

Ejemplos de conjuntos ordenados

 El conjunto de partes y la relación “inclusión#
 El conjunto de los números naturales y la relación “ es divisor de ”
 El conjunto de los números naturales y la relación “es menor que”

ELEMENTOS COMPARABLES En un conjunto ordenado  A,   dos elementos a, b A si dicen

comparables sii a  b o b a , es decir,  a, b   o  b, a  

Ejemplo En el conjunto A y la relación “divide a...”  A  1, 2,3, 4,5,6 ,|

¿Qué elementos son comparables con 4? 1, 2 y 4 ya que 1|4, 2|4 y 4|4

¿Qué elementos son comparables con 6? 1, 2, 3 y 6 ya que 1|6, 2|6 , 3|6 y 6|6

 Relación de orden amplio Una relación R es de orden (orden amplio) si y sólo si es reflexiva,
antisimétrica y transitiva. Ejemplo:  P  A ,  

 Relación de orden estricto Una relación R es de orden estricto si y sólo si es a-simétrica y

transitiva.
Ejemplo:  , 

 Relación de orden parcial Una relación R es de orden parcial, si algunos elementos no son
comparables entre sí.
Ejemplo:  P  A ,  

 Relación de orden total Una relación R es de orden total si todos los elementos son
comparables a, b  A : a  b  b a Ejemplo: la relación “menor o igual que…”

CONJUNTOS BIEN ORDENADOS si está totalmente ordenado y todo subconjunto no vacio tiene
primer elemento

Prof. Lic. Christian L. Staple 20

 UNLAM - DIIT –MATEMÁTICA DISCRETA

DIAGRAMA HASSE consiste en la forma simplificada de un dígrafo para representar la relación de

orden.
 Se eliminan las aristas que pueden ser deducidas de otras por transitividad
 Se eliminan los lazos
 Se ubican los vértices de modo que todas las flechas van hacia arriba

Ejemplo  A  1, 2,3,6 ,|  P( A),   con A  x, y, z

Para tener en cuenta: Dado un número n, entero positivo, su descomposición factorial tiene la
forma n  p1k1  p2k2  pmkm , donde los pi son distintos números primos, se llama d(n) a la cantidad

de divisores positivos de n, la cual se obtiene d (n)   k1  1   k2  1   ki  1

Ejemplos

 D  30 ,| para saber la cantidad de divisores  D 18 ,| Para saber la cantidad de
factoreamos 30  51  31  21 , la cantidad de divisores factoreamos 18  32  21 ,
divisores positivos de 30 es D 18  1, 2, 3,6,9,18 y su HASSE es:
1  1  1  1  1  1  8
D  30   1, 2, 3, 5,6,10,15,30 y su HASSE es:

 A,| con A  1, 2, 3, 4,6,8,9,12,18, 24 y su  A,  con A  1, 2, 3, 4,6 y su HASSE es:
HASSE es:

Prof. Lic. Christian L. Staple 21

 UNLAM - DIIT –MATEMÁTICA DISCRETA

ORDEN DEL PRODUCTO Sean ( A;1 ) y  B; 2  dos conjuntos ordenados. Sea AXB el producto

cartesiano.
En AXB se define la siguiente relación  x1 , y1    x2 , y2   x11 x2  y1 2 y2 Se la denomina Orden

del Producto.

Ejemplo Sean ( D15 ;|) y 2, 4 ;   conjuntos ordenados, realizar el orden del producto  D15 X 2, 4

 D X2, 4  1, 2 , 1, 4 , 3, 2 , 3, 4  , 5, 2  , 5, 4  , 15, 2  , 15, 4 
15

 
Ejemplo Sean ( A  1,3,5,9 ;|) y B  , a;  conjuntos ordenados, realizar el orden del

producto BXA

BXA   ,1 ,  ,3 ,  ,5 ,  ,9  , {a},1 , {a},3 , {a},5  , {a},9 

¿Es un orden total? NO, ya que  ,1 y  ,5 No están relacionados

ELEMENTOS CARACTERÍSTICOS DE UN CONJUNTO ORDENADO Sea  A,   un conjunto ordenado,

se define:
 Maximal m  A es maximal de A  x  A : m  x  x  m Un elemento es maximal si

ningún otro lo sigue excepto sí mismo.

 Minimal m  A es minimal de A  x  A : x  m x  m Un elemento es minimal si ningún

otro lo precede excepto sí mismo.

 Máximo Si el maximal es único, se lo llama máximo o último elemento
 Mínimo Si el minimal es único, se lo llama mínimo o primer elemento.

Prof. Lic. Christian L. Staple 22

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Sea  A,   un conjunto ordenado, se define un subconjunto no vacio B  A

 Cota Superior s  A es cota superior de B  x  B : x  s Las cotas superiores de un

subconjunto ordenado son los elementos que siguen a todos los elementos del subconjunto.
 Cota Inferior i  A es cota inferior de B  x  B : i  x Las cotas inferiores de un
subconjunto ordenado son los elementos que preceden a todos los elementos del subconjunto.
 Supremo La primera de las cotas superiores se denomina supremo, y si pertenece al
subconjunto es el máximo. La “menor” de las cotas superiores.
 Ínfimo La última de las cotas inferiores se denomina ínfimo, y si pertenece al subconjunto es el
mínimo. La “mayor” de las cotas inferiores

Ejemplo Sea el conjunto A = {a, b, c, d, e, f, g, h, i} ordenado de la siguiente forma:

Tomamos como subconjunto B = {d, e, h}

Cotas superiores = {g, i}
Cotas inferiores ={ a, b, d }
El supremo es g (no es máximo) y el ínfimo es: d(es mínimo de B)

REDES – RETÍCULOS - LATIS

¿Qué es una Red, Retículo, Reticulado, Lattice o Latis? Es un conjunto ordenado que verifica para
todo par de elementos debe existir el supremo y el ínfimo en el conjunto.
Al supremo entre a y b lo vamos a denotar: sup {a, b} = a  b
Al ínfimo entre a y b lo vamos a denotar: ínf {a,b} = a  b

Propiedad Si a  b  a  b  b y a  b  a O sea que SIEMPRE existen a  b y a  b entre

elementos que están relacionados. Solamente hay que fijarse si existen entre los que son
incomparables.

Ejemplos (D12, |) es red? Construyamos el Hasse

Prof. Lic. Christian L. Staple 23

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Red Algebraica Una red algebraica es una terna  A, ,   con A  0 y cumple con:

EQUIVALENCIA ENTRE LAS DEFINICIONES

 A,     A, ,  
 ,|   , mcm, dcm 
 P  A ,     P( A), , 
SUB RED O SUB RETÍCULO Sea  A,   un retículo y B  A , es un subretículo de A sii verifica

  B,   es red
 a, b  B : sup B a, b  sup A a, b e inf B a, b  inf A a, b

Prof. Lic. Christian L. Staple 24

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo:

 D  30 ,| es red 23  6 y 23 1 2  5  10 y 25 1

2  15  30 y 2  15  1 3  10  30 y 3  10  1
3 5  5 y 55 1 1  10  10 y 1  10  1
1  15  15 y 1  15  1 1 6  6 y 1 6  1
5  30  30 y 5  30  5 5  6  30 y 5 6 1
6  10  30 y 6  10  2 6  15  30 y 6  15  3
15  10  30 y 15  10  5
Sean L1 = {3, 6, 15, 30}, L2 = {1, 2, 3, 5, 15}, L3 = {1, 6, 10, 30}. ¿Son subredes? Sus diagramas de
Hasse son

Entonces L1 es subrretículos de  D  30  ,| , mientras que L2 y L3 no lo son. L2 no es subrretículo

porque el supremo de 2 y 3 es no existe, L2 no es red. L3 no es subrretículo porque el ínfimo de 6 y

10 vale 2, que no pertenece a L3. Nótese que L3, con el orden que hereda de  D  30  ,| es un

retículo, pero no es subrretículo.

L1 es red y
6  30  30 y 6  30  6 3 6  6 y 3 6 1 6  15  30 y 6  15  3
15  3  15 y 15  3  3 15  30  30 y 15  30  15 3  30  30 y 3  30  3

L2 NO es red ya que 2  3  no existe

L3 es red pero
6  10  1 en L3 y 6  10  2 en  D30 ,|

TIPOS DE RED
 Acotado Se dice que una red  A,   es acotada si posee máximo y mínimo, que se designan con

1 y 0 respectivamente

Definición: Sea  A,   una red acotada. Dado a  A , se dice que a  A es complemento de a si:

a  a 1 y aa  0

 Complementado Si todos sus elementos poseen complemento

Prof. Lic. Christian L. Staple 25

 UNLAM - DIIT –MATEMÁTICA DISCRETA

( D18 ;|) Analizo los elementos no comparables

a  a  1 a  a  18
1  18 pues1  18  1 y 1  18  18  1  18
2  9 pues 2  9  1 y 2  9  18  2  9
6 no existe ya que 6  3  1 y 6  3  3 

6  9  3 y 6  9  18

3 no existe ya que 3  2  1 y 3  2  6 
3  6  3 y 3  6  18 
como hay elementossin complemento,la RED es NO complementada

Para la red a, b, c, d , e ,  sus complementos son

xx a x x e
a  e pues a  e  a y a  e  e  a  e
b  c pues b  c  a y b  c  e  b  c
b  d pues b  d  a y b  d  e  b  d
c  d pues c  d  a y c  d  e  c  d
e  a pues e  a  a y e  a  e  e  a
Como cada elemento del retículo tiene complemento, la red es
complementada

Una red puede tener un complemento, más de uno o ninguno

 Distributiva que la Red es distributiva si y sólo si:
 a, b, c  A : a  ( b  c )  ( a  b )  ( a  c )
 a, b, c  A : a  ( b  c )  ( a  b )  ( a  c )
 Propiedad En toda red distributiva, el complemento, si existe, es único. Esto significa que si
existe un elemento con más de un complemento, la Red no será distributiva.

Prof. Lic. Christian L. Staple 26

 UNLAM - DIIT –MATEMÁTICA DISCRETA

 Propiedad Toda red finita es distributiva sii no contiene ninguna subred isomorfa a alguna
de las siguientes:

Reticulo1 Reticulo 2
d  c  b  d  e  d d  c  b  d  e  d
d  c  d  b  c  a  c d  c  d  b  a  a  a
d  c  b   d  c  d  b d  c  b  d  c   d  b

Propiedad: En toda red distributiva, el complemento, si existe, es único. Entonces si existe un

elemento con más de un complemento, La Red no será distributiva.

ALGEBRAS DE BOOLE
B es un Algebra de Boole si B es una red distributiva y complementada.
Podemos decir que un conjunto parcialmente ordenado en el cual dos elementos cualesquiera
tienen una única cota superior mínima y una única cota inferior máxima, complementado y
distributivo se conoce como Álgebra de Boole
En  B, ,   un álgebra de Boole se cumple:

 Operaciones binarias  : B2  B  : B2  B

 Conmutativa ab  ba a b  b a

 Distributiva  a, b, c  B : a  ( b  c )  ( a  b )  ( a  c )
a  (b  c)  (a  b)  (a  c)

 Existencia de Neutro 0B  B tal que  a  B: a  0B = a

1B  B tal que  a  B: a  1B = a

 Involutiva a  a

 De Morgan  a  b   a  b  a  b  a  b

ÁTOMO: Sea  B, ,   una red con mínimo m, un elemento x  B es un átomo si es

inmediatamente posterior al mínimo m.

Ejemplo: Los siguientes diagramas de Hasse representan álgebras de Boole.

Propiedad: Sea n = p1 . p2 . p3 ……. pn donde p son números primos distintos, se verifica de D n es

Algebra de Boole.

Prof. Lic. Christian L. Staple 27

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo  D28 ,1 NO es un Algebra de Boole. Su diagrama de Hasse es el siguiente:

Como D28 no es una red complementada ya que hay dos elementos que no tienen complemento �
no es Álgebra de Boole.

MORFISMOS
Un homomorfismo, (o a veces simplemente morfismo) de un objeto matemático a otro de la misma
categoría, es una función que es compatible con toda la estructura relevante.
 Un homomorfismo que es también una biyección se llama isomorfismo; dos objetos isomorfos
son totalmente indistinguibles por lo que a su estructura se refiere (tengamos en cuenta que la
función inversa también es un homomorfismo biyectivo)
 Un homomorfismo de un conjunto a sí mismo se llama endomorfismo; si es también un
isomorfismo se llama automorfismo.

Prof. Lic. Christian L. Staple 28

 UNLAM - DIIT –MATEMÁTICA DISCRETA

La siguiente es la definición formal de homomorfismos para álgebras de Boole

Ejemplo: Sean dos conjuntos ordenados (D1o, |) y (D21, |), cuyo diagrama Hasse son:

Como 10 = 5 . 2 y 21 =7 . 3 (D1o, |) y
(D21, |), son Algebras de Boole

En D10 En D21
1  10  10  1 1  21  21  1 Probemos que es un homomorfismo
25 5 2 37 73


I a  A : f a  f  a 


f 2  f  5  7 f  2  3  7 
f 1  f 10   21 f 1  1  21


De acá inferimos f 2  f  2  
De acá inferimos f 2  f  2 


f 5  f  2  3 f  5  7  3  
f 10  f 1  1 f 10   21  1


De acá inferimos f 5  f  5   
De acá inferimos f 10  f 10 

II- a  A, b  A : f  a  b   f  a  f  b 
f 1  1  f 1  1 f 1 ´ f 1  1 ´1  1
f 1  2   f  2   3 f 1 ´ f  2   1 ´3  3
f 1  5   f  5   7 f 1 ´ f  5   1 ´7  7
f 1  10   f 10   21 f 1 ´ f 10   1 ´21  21
f  2  5   f 10   21 f  2  ´ f  5   3 ´7  21
f  2  10   f 10   21 f  2  ´ f 10   3 ´21  21
f  5  10   f 10   21 f  5  ´ f 10   7 ´21  21
f 10  10   f 10   21 f 10  ´ f 10   21 ´21  21

III- a  A, b  A : f  a  b   f  a ´ f b  de forma similar a la propiedad II

Prof. Lic. Christian L. Staple 29

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Por la forma en que definimos f se verifican los puntos 4 y 5 de dicha definición.

f  0 A   0B f (1A )  1B
f 1  1 f 10   21
1 1 21  21

Como por definición es biyectiva, resulta ser un isomorfismo.

TEORÍA DE GRAFOS
El problema de los puentes de Königsberg, consistía en buscar si existía un camino para poder
cruzar todos los puentes pasando una sola vez por cada uno. Si bien esto era solamente un
entretenimiento dominical para muchos, en 1736 el matemático Leonhard Euler descubrió y
desarrolló la teoría de Grafos, con la cual pudo responder este interrogante.

La teoría de Grafos actualmente se utiliza en diversos campos y tiene muchas aplicaciones, tanto en
Ciencias Sociales, Lingüística, Física, Química, Arquitectura y, tal vez lo que más nos interesa a
nosotros, en Comunicaciones, Ingeniería e Informática.

DEFINICIÓN FORMAL: Un grafo es una estructura formada por vértices unidos a través de aristas.
Formalmente es una terna G=  V; A; φ  siendo

V: el conjunto de vértices V   A: el conjunto de aristas

φ : La función de incidencia φ: A  V

DEFINICIONES
 VÉRTICES ADYACENTES: vi es adyacente a vj   ak  A tal que φ (ak) = {vi, vj} Es decir son

aquellos vértices unidos por alguna arista.

 VÉRTICE AISLADO: el que no es adyacente a ningún otro. es aislado.
 ARISTAS PARALELAS: ai es paralela a aj  φ (ai) = φ (aj) siendo ai  aj. Es decir son aquellas
comprendidas entre los mismos vértices.
 ARISTAS ADYACENTES: las que tienen un único vértice en común siendo distintas y no paralelas.
 BUCLES o LAZOS: las aristas comprendidas en un mismo vértice.
 ARISTAS INCIDENTES EN UN VÉRTICE: las que tienen a dicho vértice por extremo.
 GRAFO SIMPLE: el que no tiene aristas paralelas ni bucles.
Prof. Lic. Christian L. Staple 30
 UNLAM - DIIT –MATEMÁTICA DISCRETA

Es importante observar que en la definición de grafo no se especifica la longitud o forma de las

aristas ni su posición, como así tampoco el orden o ubicación de los vértices. Por ello, NO EXISTE
un ÚNICO DIAGRAMA que represente un grafo.

V = {v1, v2, v3, v4, v5} A = {a1, a2, a3, a4, a5}
φ (a1)={v1,v2} , φ (a2) ={v3} , φ (a3)={v4,v2} , φ (a4)={v1,v3 } , φ (a5)={ v1,v2}

g(v1) = 3
g(v2) = 3
g(v3) = 3
g(v4) = 1
g(v5) = 0

Grado de un vértice o valencia de un grafo g(vi): Es el numero de aristas incidentes en él

 g(v) = 0, es un vértice aislado
 g(v)=1, se trata de un vértice colgante
 g(v)= K, para todo vértice del grafo, entonces es un grafo k-regular.
Nota: los bucles se cuentan doblemente.

Propiedad: En todo grafo se cumple que la suma de los grados de los vértices es igual al doble de la
cantidad de aristas.
n
En símbolos:  g (v ) 
i 1
i 2A

Ejemplo: ¿Cuál es la cantidad total de vértices de un grafo que tiene 2 vértices de grado 4, 1 de
grado 3, 5 de grado 2 y el resto colgantes (de grado 1) sabiendo que en total hay 12 aristas?
Solución: Usando la propiedad anterior: 2  4 + 1  3 + 5  2 + x  1 = 2  12 Resolviendo: 21 + x = 24
 x = 3 (cantidad de vértices colgantes) Por lo tanto la cantidad total de vértices es: V = 11

Ejemplo: En una fiesta hay 8 personas que en un determinado momento llenan sus copas de sidra
y brindan entre ellos, todos con todos. ¿Cuántos choques de copas hay en total?
Solución: Podemos considerar en K8, donde los vértices son las personas y las aristas representan
los choques de copas, ya que cada persona choca su copa con todos los demás excepto con sí
mismo.
n
Utilizando la propiedad:  g (v ) 
i 1
i 2A

Como todos los vértices tienen grado 7, nos queda: 87  2 A  A  28 En total hay 28 choques de

copas.

Prof. Lic. Christian L. Staple 31

 UNLAM - DIIT –MATEMÁTICA DISCRETA

MATRIZ DE ADYACENCIA Es un matriz cuyas filas y columnas, representan los vértices de grafo.

Sea un grafo G=  V, A,   con V= v1 , v2, ....., vn  y A= a1 , a2 ,......, an 

Se define la matriz de adyacencia de G a una matriz booleana nxn


 1 si vi es adyacente con v j
 
M a  G    mij  tal que mi  

 0 si vi es adyacente con v j

Propiedades:
 existe una única matriz de adyacencia para cada grafo
 los lazos se indican con “1” en la diagonal principal
 al sumar cada fila o cada columna se obtiene el grado de cada vértice, salvo en el caso del bucle
a la cual le corresponde 1 en la matriz de adyacencia pero su grado es 2.

MATRIZ DE INCIDENCIA: es una matriz rectangular de n vértices por m aristas. Cuyas filas
representan a los vértices y las columnas las aristas.

Sea un grafo G=  V, A,   con V= v1 , v2, ....., vn  y A= a1 , a2 ,......, an 

Se define la matriz de adyacencia de G a una matriz booleana nxm


 1 si vi es adyacente con a j
 
M a  G    mij  tal que mi  

 0 si vi es adyacente con a j

Propiedades
 cada columna sumara 2 ya que toda arista es incidentecon 2 vértices, salvo que sea un lazo
(bucle)
 la suma de los elementos de cada fila corresponde al grado de cada vértice, menos para el lazo.

TIPOS DE GRAFOS
Grafos simples son los que no tienen aristas paralelas ni bucles
Grafo nulo es cuando los vértices que los componen no están conectados. Son vértices aislados.
Prof. Lic. Christian L. Staple 32
 UNLAM - DIIT –MATEMÁTICA DISCRETA

Grafo k-regular es aquel que tiene el mismo grado en todos los vértices.
Grado de un grafo k-regular: Un grafo es k-regular sii v V , g  v   k

Grafo completo es un grafo simple en el cual cada pareja de vértices está conectada por una arista.
Sea n  N : K n =  V; A; φ  tal que  v, w  V: v  w  a  A :  (a) = {v, w}

O sea, los Kn son grafos simples de n vértices en los cuales cada vértice es adyacente a todos los
demás.

Grafos bipartitos Es decir, los grafos BIPARTITOS son grafos cuyo conjunto de vértices está
particionado en dos subconjuntos no vacíos y disjuntos: V1 y V2 tales que los vértices de V1 pueden
ser adyacentes a los vértices de V2 pero los de un mismo subconjunto no son adyacentes entre sí.

GRAFOS BIPARTITOS COMPLETOS Kn,m.

Como su nombre lo indica deben ser bipartitos y además completos. Es decir, el conjunto de
vértices debe estar particionado en dos subconjuntos, cada arista debe tener un vértice de cada
subconjunto y por demás del subconjunto al que él no pertenece.
Por lo tanto son grafos bipartitos de n+m vértices con TODAS las aristas posibles.
Ejemplos: K3,2 K3,3

Prof. Lic. Christian L. Staple 33

 UNLAM - DIIT –MATEMÁTICA DISCRETA

DÍGRAFO
DEFINICIÓN FORMAL: Un dígrafo es una terna D G=  V; A;   siendo

V: el conjunto de vértices V   A: el conjunto de aristas

 : La función de incidencia  : A  VxV es la función de incidencia dirigida, que le asigna a cada
arco un par ordenado de vértices.

Observaciones:
 La función de incidencia  le hace corresponder a cada arista un PAR ORDENADO de vértices, al
primero se lo llama EXTREMO INICIAL de la arista, y el segundo es el VÉRTICE FINAL.
 Los caminos y los ciclos se definen de la misma forma que para los grafos no dirigidos, pero hay
que respetar el sentido de las aristas.
 Si todos los vértices son distintos se trata de un camino simple.
 Si todas las aristas son distintas, se trata de un camino elemental.

FUNCIÓN GRADO EN UN DÍGRAFO:

Comencemos por enunciar algunas definiciones relativas al grado de un vértice.
 GRADO POSITIVO: cantidad de aristas que inciden positivamente en el vértice (son las que
“entran” al vértice). Se denota g +(v)
 GRADO NEGATIVO: cantidad de aristas que inciden negativamente en el vértice (son las que
“salen” del vértice). Se denota g-(v)
 GRADO TOTAL: es la suma de los grados positivo y negativo. Se denota g t(v)
 GRADO NETO: es la diferencia entre el grado positivo y el negativo. Se denota g N(v)
Ejemplo:

Prof. Lic. Christian L. Staple 34

 UNLAM - DIIT –MATEMÁTICA DISCRETA

PROPIEDADES
n n

 g v    g v  
i 1

i
i 1

i A
n

 g v   0
i 1
n i donde g n  vi   g   vi   g   vi 
n

 g  v   2 A
i 1
t i donde gt  vi   g   vi   g   vi 

Un dígrafo DG  V , A,   es k  regular sii v V , g   vi   g   vi   k

MATRIZ DE ADYACENCIA Sea un dígrafo DG=  V, A, δ  con V= v1 , v2, ....., vn  y A= a1 , a2 ,......, an 

Si no tiene bucles ni aristas paralelas, se define la matriz de incidencia de DG a una matriz de nxn

 1 si a  A:  (a)   vi ,v j 

 
M a  DG    mij  tal que mi  

 0 en caso contrario

Al sumar las columnas se obtiene el grado de entrada, y al sumar las filas el grado de salida.

MATRIZ DE INCIDENCIA Sea un dígrafo DG=  V, A, δ  con V= v1 , v2, ....., vn  y A= a1 , a2 ,......, an 

Si no tiene bucles ni aristas paralelas, se define la matriz de incidencia de DG a una matriz de nxm
 1 si vi es vértice final a j


M i  DG    mij   tal que mi  1 si vi es inicial final a j

 0 si vi y a j no son incidentes

 1 1 0 1 0 0 0 0
 
 1 0 1 0 0 1 0 0 
M i  DG    0 0 1 0 0 0 1 1
 
 0 0 0 1 1 1 1 0 
 0 1 0 0 1 0 0 1 
 

Prof. Lic. Christian L. Staple 35

 UNLAM - DIIT –MATEMÁTICA DISCRETA

SUBGRAFOS:
Dado un grafo G  (V ; A; ) , se denomina subgrafo al grafo G´  (V ´; A´;´) tal que
V ’  V  A’  A y ´  / A´ es la función  restringida a A’.
Para obtener subgrafos de un grafo dado se puede:
 suprimir uno o varios vértices y las aristas incidentes en ellos
 suprimir solamente una o varias aristas.

Si se suprime un vértice v, el subgrafo restante es Gv

Si se suprime una arista a, el subgrafo restante es Ga
Prof. Lic. Christian L. Staple 36
 UNLAM - DIIT –MATEMÁTICA DISCRETA
Ejemplos: Dado el grafo: G  (V ; A; )

CAMINOS, CIRCUITOS Y CICLOS

 CAMINO: sucesión finita cuyos términos son alternativamente vértices y aristas.

 v1; a1; v2 ; a2 ; v3 ; a3 ;...............; vn1 ; an ; vn 

 LONGITUD del camino: cantidad de aristas que lo componen.
 CAMINO SIMPLE: si todos los vértices son distintos.
 CAMINO ELEMENTAL: si todas las aristas son distintas
 CIRCUITO O CAMINO CERRADO. El vértice inicial coincide con el final.
 CIRCUITO SIMPLE no repite vértices salvo v0  vn

 CICLO circuito simple donde todas las aristas son distintas

Ejemplo
a) Grado de cada vértice
Tenemos que: g(a) = 2 ; g(b) = 2 ; g(c) = 4 ; g(d) = 4 ; g(e)
= 4 ; g(f) = 3 ; g(g) =1

Prof. Lic. Christian L. Staple 37

 UNLAM - DIIT –MATEMÁTICA DISCRETA

b) 3 caminos de “a” hacia “f”

Un posible camino es: C1= (a; 1; b; 2; c; 3; f)

Long(C1) = 3 porque usamos 3 aristas

C1= (a; 5; d; 6; c; 4; e; 8; e; 9; f)
Long(C2) = 5

Algunos ciclos

Prof. Lic. Christian L. Staple 38

 UNLAM - DIIT –MATEMÁTICA DISCRETA

GRAFO CONEXO Un grafo es conexo si y solo si tiene una única componente conexa, es decir, si
existe algún camino entre todo par de vértice

DEFINICIONES
 es no
 ISTMO O PUNTO DE CORTE Dado un grafo G  (V ; A; ) conexo, v V es istmo  Gv

conexo Es decir, un istmo es un vértice tal que su supresión desconecta al grafo.

 es no conexo
 PUENTE Dado un grafo G  (V ; A; ) conexo, a  A es puente  Ga
 CONJUNTO DESCONECTANTE Dado un grafo G  (V ; A; ) conexo, B  A es desconectante

 G B es no conexo. Es decir, un conjunto de aristas es desconectante si y sólo si su supresión

desconecta al grafo.
 CONJUNTO DE CONECTIVIDAD Es el menor número de vértices cuya supresión desconecta al
grafo.

Prof. Lic. Christian L. Staple 39

 UNLAM - DIIT –MATEMÁTICA DISCRETA

b) no tiene itsmos ya que no es posible obtener una subgráfica no conexa eliminando un vértice
c) No tiene puentes ya que no es posible obtener una subgráfica no conexa eliminando una arista
d) conjunto desconectante {a1, a2, a5} y conjunto de corte {a7, a3}
e) conjunto de conectividad {v1, v2, v3}

Prof. Lic. Christian L. Staple 40

 UNLAM - DIIT –MATEMÁTICA DISCRETA

GRAFOS EULERIANOS
Se denomina camino euleriano al camino que pasa por todas las aristas una sola vez; y ciclo
euleriano al ciclo que pasa por las aristas una sola vez.
 La condición necesaria y suficiente para que en un grafo exista camino euleriano es:
 El grafo debe ser conexo, y
 todos los vértices deben tener grado par, o a lo sumo dos grado impar.
 La condición necesaria y suficiente para que en un grafo exista ciclo euleriano es:
 El grafo debe ser conexo, y
 todos los vértices deben tener grado par.

EN DÍGRAFOS
El dígrafo DG tiene ciclo euleriano dirigido si y solo si G es conexo y g +(v) = g-(v) para todo vértice.

a) no admite porque v4 es vértice aislado

b) no admite porque cualquier ciclo utilizará la arista e1 dos veces
c) (v1, e1, v2, e2, v1) es euleriano
d) (v3, e3, v1, e1, v2, e2, v3) es euleriano
e) no admite circuito euleriano
f) (v1,e1, v2, e2, v3, e3, v4, e4, v2, e5, v5, e6, v1) es un circuito euleriano

CAMINOS Y CICLOS HAMILTONIANOS

Se denomina c o al camino hamiltoniano al camino que pasa una vez por cada vértice.
Importante: no necesariamente va a pasar por todas las aristas, pues en muchos casos repetiría
vértices y no sería hamiltoniano.

Prof. Lic. Christian L. Staple 41

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Teorema: Sea G un grafo conexo con n vértices, donde n  3 . Si la suma de los grados de cada par
de vértices no adyacentes es mayor o igual a n , entonces G tiene circuito hamiltoniano.

ISOMORFISMOS DE GRAFOS:
Dados dos grafos: G1  (V1; A1;1 ) y G2  (V2 ; A2 ;2 ) Se dice que son isomorfos si y solo si

existen dos funciones biyectivas f : V1  V2 y g : A1  A2 tales que:

a  A1 : 2  g  a    f 1  a  

Si no hay aristas paralelas, entonces es suficiente: u, v V1 : u, v  A1   f  u  , f  v    A2

En pocas palabras, dos grafos son isomorfos cuando tienen la misma estructura, es decir sus
vértices están relacionados de igual forma aunque estén dibujados de manera distinta.
Condiciones necesarias para que dos grafos sean isomorfos:
 Deben tener la misma cantidad de vértices.
 Deben tener la misma cantidad de aristas.
 Deben tener los mismos grados de los vértices.
 Deben tener cadenas de las mismas longitudes.
 Si uno tiene ciclos, el otro también debe tenerlos.

Observación: las condiciones mencionadas son necesarias (es decir que sí o sí se deben cumplir
para que los grafos sean isomorfos) pero no son suficientes ( o sea que aunque se cumplan puede
ser que los grafos no sean isomorfos)
Para estar seguros que dos grafos son isomorfos, una condición suficiente es que tengan la misma
matriz de adyacencia.

Ejemplo Sean los grafos

gr  A   4 gr  X   2
gr  B   3 gr  Z   3
gr  C   2 gr W   1
gr  D   1 gr Y   4

Ambos tienen 4 vértices y 5 aristas.

Definamos la función biyectiva, haciendo corresponder los vértices con iguales grados:
f(A) = Y ; f(B) = Z ; f(C) = X ; f(D) = W
La definición dice que si entre dos vértices del primer grafo hay una arista, también debe haber una
arista entre los vértices correspondientes en el segundo grafo.
Por ejemplo entre A y B hay una arista en G1, y también hay una arista entre f(A) y f(B) en G2.
Prof. Lic. Christian L. Staple 42
 UNLAM - DIIT –MATEMÁTICA DISCRETA

Lo mismo habría que comprobar para cada arista. Podemos comprobarlo para todas las aristas
juntas con la matriz ORDENANDO CONVENIENTEMENTE los vértices, de acuerdo a la función
biyectiva definida entre los vértices

Como las matrices son iguales podemos asegurar que G 1 es isomorfo a G2.

Importante: Si dadas dos matrices de adyacencia correspondientes a dos grafos, ellas no son
iguales, no significa que los grafos no sean isomorfos, pues tal vez reordenando una de ellas se
pueda lograr que sean iguales. Para poder afirmar que dos grafos no son isomorfos hay que mostrar
alguna propiedad estructural no compartida o bien probar que todos los ordenamientos posibles de
las matrices no coinciden.

ARBOLES
Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente
en computación.
Llamaremos árbol a todo grafo conexo y sin ciclos.
CONDICIÓN NECESARIA Y SUFICIENTE: Un árbol es un grafo en el cual entre todo par de vértices
existe un único camino simple.

Prof. Lic. Christian L. Staple 43

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Propiedades básicas de los árboles:

 Si a un árbol se le agrega una arista entre dos de sus vértices, deja de ser árbol.
 Todas las aristas de un árbol son puentes.
 En todo árbol se cumple que: V  A  1

Se denomina BOSQUE al grafo no conexo en el cual cada una de las componentes es un árbol.
Propiedad: En un bosque de k componentes se cumple que V  A  k

En el ejemplo anterior G3 es un bosque con k = 2

ÁRBOLES DIRIGIDOS
Un dígrafo se denomina dirigido cuando su grafo asociado es un árbol.
El árbol con raíz es un árbol dirigido en el cual el grado entrante (positivo) de cada vértice es igual a
salvo un único vértice con grado positivo igual a cero, llamado raíz.

Definición: Sea el dígrafo DG = {V, A,  }. Decimos que DG es un árbol dirigido o árbol con raíz si
existe un vértice v0 ∈ V tales que desde v0 hasta cualquier otro vértice v ∈ V existe un único camino
que los une. v0 se llama raíz del árbol dirigido

Definiciones
Un vértice v de un árbol se dice que es HOJA cuando Gr(v) = 1
Los VÉRTICES INTERNOS son todos aquellos que no son la raíz ni las hojas.
Se llama RAMA a todo camino que va desde la raíz a alguna hoja.

Otras definiciones
 Antecesor: v es antecesor de w  existe un único camino simple de v a w.
 Sucesor: w es sucesor de v en el caso anterior
 Padre: v es padre de w  existe una arista de v a w.
 Hijo: w es hijo de v en el caso anterior.
 Hermanos: v y w son hermanos si tienen el mismo padre.

Prof. Lic. Christian L. Staple 44

 UNLAM - DIIT –MATEMÁTICA DISCRETA

En este árbol, la raíz es: a

Las hojas son: i, j, o, p, f, g, l, m
El padre de k es e.
Los hijos de c son f, g, h
Todos los antecesores de j son e, b, a

El NIVEL DE UN VÉRTICE se define en forma recursiva:

1) El nivel de la raíz es cero: n(r) = 0
2) Cada vértice tiene un nivel más que su padre: si p es padre de v  n(v) = n(p) + 1

ALTURA de un árbol: es el mayor NIVEL alcanzado por las HOJAS.

Se dice que un árbol está BALANCEADO cuando todas las hojas están en el nivel MAYOR o en UNO
MENOS.
En el ejemplo anterior, la altura del árbol es: h = 4 ¿Es balanceado? No, pues las hojas f y g están en
el nivel 2.

ARBOLES N-ARIOS
Un árbol con raíz es n-ario  v V : g  (v)  n Es decir, cada vértice puede tener a lo sumo n
hijos.

CLASIFICACIÓN DE LOS N-ARIOS

 Si n=2 entonces se dice árbol BINARIO.
 Si n=3 entonces se dice árbol TERNARIO.
 Un árbol se dice n-ario regular cuando todos los vértices tienen la misma cantidad de hijos,
salvo las hojas que no tienen hijos.
 Un árbol se dice n-ario regular pleno o completo cuando además de ser n-ario regular, todas las
hojas se hallan en el mismo nivel.

RECORRIDOS DE ÁRBOLES
Recorrer un árbol significa nombrar todos los vértices del árbol siguiendo un determinado orden.
Ello es muy importante si consideramos una base de datos de forma arborescente.

Prof. Lic. Christian L. Staple 45

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo

Recorrido en orden previo: a b d e h i k l c f g j

Recorrido en orden simétrico: d b h e k i l a f c j g
Recorrido en orden posterior: d h k l i e b f j g c a

NOTACIÓN INFIJA, PREFIJA Y POSFIJA Los arboles binarios se emplean a menudo para representar
expresiones aritméticas, en la que los vértices internos representan a los operadores (+ suma, -

resta, * producto, / cociente,  potencia) y las hojas números o variables.

 Notación usual o infija: es el orden SIMÉTRICO (IN ORDEN)

 Notación Polaca o prefija: es el orden PREVIO (PRE ORDEN)
 Notación polaca inversa o posfija: es el orden POSTERIOR (POST ORDEN)

* * /  23 2122 Notacion Polaca

23  21  2 / 2* Notacion Polaca Inversa
/ 2
 2  3   2  1 / 2 * 2 Notacion InfijaUsual

 2

 

2 3 2 1

Prof. Lic. Christian L. Staple 46

 UNLAM - DIIT –MATEMÁTICA DISCRETA

/ 

*  * 6

 3  2 3 

3 1 9 5 7 4
Recorrido inorden 3  1*3 / 9  5  2  3*7  4  6

Notacion InfijaUsual 3  1 *3 / 9  5  2 3* 7  4  6

Notacion Polaca  / **313  952  *3  746
Notacion Polaca Inversa 31  3*95  2  /374  *6  

GRAMÁTICAS
Un lenguaje es un conjunto de palabras y métodos para combinar palabras, que es usado y
entendido por un extenso grupo de personas.
Concretando, los lenguajes pueden clasificarse en naturales y formales.
Los lenguajes naturales se caracterizan por:
- una semántica, es decir, un significado
- una sintaxis, es decir, un conjunto de reglas gramaticales.
Son ejemplos de este tipo de lenguaje, los lenguajes de seres humanos, tales como: chino, español,
inglés.

LOS LENGUAJES FORMALES se caracterizan por tener reglas gramaticales preestablecidas. Son
ejemplo de este tipo de lenguaje los lenguajes de programación.

LAS GRAMÁTICAS son descripciones de las sentencias de los lenguajes, establecen la estructura que
deben tener las sentencias para que estén bien formadas y para que pueda entenderse su
significado.
Las gramáticas permiten describir de forma intencional a los lenguajes; proporcionan reglas para la
estructura de las frases y su significado.

Prof. Lic. Christian L. Staple 47

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Informalmente podemos decir que una gramática es un modelo matemático que consta de:
 un alfabeto, llamado alfabeto de elementos terminales que representa el conjunto de letras que
tendrán las palabras del lenguaje que genera esa gramática
 un conjunto de símbolos especiales, denominados no terminales, que son elementos auxiliares
y permiten representar estados intermedios antes de llegar al de la generación de las palabras
del lenguaje.
 un símbolo inicial del que se partirá para la obtención de cualquiera de las palabras del lenguaje,
denominado cabeza del lenguaje, que es uno de los elementos no terminales.
 un conjunto de producciones o reglas gramaticales que permitirán realizar las transformaciones
desde los símbolos no terminales a las palabras del lenguaje.

Se define a la Gramática formal G, como la cuádrupla: G = (Vt; Vn ; S ; P) donde:

 Vn es un conjunto de elementos llamados no terminales, que suele llamarse vocabulario de
elementos no terminales. Suelen ser representados con letras mayúsculas.
 Vt es un conjunto de elementos llamados terminales, suele denominarse vocabulario de
elementos terminales. Suelen usarse letras minúsculas, dígitos, operadores, etc.
 P es un conjunto de producciones (reglas de sustitución)
 S es un elemento de Vn llamado símbolo inicial.

Ejemplo 1 Sea G = (Vt, Vn, S, P) una gramática en la cual: Vt = {a, b} Vn = {S, A, B}, donde S es el
símbolo inicial.
Las reglas gramaticales o producciones son
S  aB/ bA
A  a/ aS/ bAA
B  b/bS/aBB
Aplicando las reglas gramaticales y teniendo en cuenta que esta gramática genera palabras con las
letras a, b, debemos plantearnos como objetivo eliminar las letras S, A, B. Tenemos que comenzar
con S, eso no podemos elegirlo, pero si podemos seleccionar cualquiera de las opciones que S nos
ofrece, por ejemplo: S  aB
A continuación, para eliminar B elegimos B  b, reemplazamos en la expresión anterior y queda:
S  aB  ab que es una palabra del lenguaje ya que ambas letras pertenecen al vocabulario
terminal. W1 = ab
Veamos otra palabra (si hay que reemplazar una letra por más de una conviene poner un
paréntesis), S  aB  a(bS)  ab(bA)  abb(bAA)  abbb(AA)  abbb(aa)
Finalmente la palabra es w2 = abbbaa
Prof. Lic. Christian L. Staple 48
 UNLAM - DIIT –MATEMÁTICA DISCRETA

ÁRBOL DE DERIVACIÓN
Una forma práctica de representar las derivaciones son los árboles de derivación que se utilizan en
la construcción de compiladores para representar el análisis sintáctico de los programas fuente y
sirven de base para la generación de un código.
En los árboles de derivación:
 La cabeza del lenguaje se representa en la raíz del árbol
 Los nodos hojas del árbol son símbolos terminales de la gramática

Para el ejemplo 1
S S

a B b B

b b S

b A

A A

a a

Ejemplo 2: Sea la G = ({a, b}, {A, B, S}, S, P) donde P es:

S → AB
A → aA | a
B → bB | b
La cadena w = aabbb puede ser derivada

Prof. Lic. Christian L. Staple 49

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Algunas observaciones que tendremos que tener en cuenta son las siguientes:
1. El lenguaje generado por una gramática G se denomina L(G).
2. Si la gramática G genera un lenguaje L se indica G  L(G)
3. Ninguna regla gramatical puede comenzar con la palabra nula, 
4. Dos gramáticas G1 y G2 son equivalentes si L(G1) = L(G2); es decir, si generan el mismo lenguaje.
5. El proceso para obtener las palabras del lenguaje que genera la gramática se llama derivación
5.1. Se comienza con el símbolo inicial S.
5.2. Se aplican las producciones de P al símbolo inicial s hasta obtener sólo elementos terminales.
5.3. Cualquier hilera que se consigue usando el 5.2. es un elemento del lenguaje L(G).

ÁRBOL DE DERIVACIÓN DE UN LENGUAJE

Sea la G2 = ({c, d}, {A, S}, S, P) donde P es:

S→  A
A → cAd |cd

Sea la G4 = ({c, d}, {A, T, S}, S, P) donde P es:

S→cA
A → cA |d |Td
T → Td |d

Prof. Lic. Christian L. Staple 50

 UNLAM - DIIT –MATEMÁTICA DISCRETA

CLASIFICACIÓN DE GRAMÁTICAS:
Noam Chomsky definió cuatro tipos de gramáticas formales, en función de las producciones, es
decir de las reglas gramaticales.
Esta clasificación comienza con las más generales para finalizar en las que presentan más
restricciones, siempre teniendo en cuenta las producciones.

GRAMÁTICAS DE TIPO 0 (SIN RESTRICCIONES): Las reglas de derivación son del tipo w1  w2

siendo w1 VT ,VN  y w2 VT ,VN  , es decir la única restricción posible es la producción del tipo
 *

  w2

GRAMÁTICAS DE TIPO I (SENSIBLES DEL CONTEXTO): Se denominan gramáticas dependientes del

contexto porque en ellas se tiene en cuenta que es lo que viene antes y después del símbolo que se
está sustituyendo.
Las reglas de derivación son del tipo w1  w2 , donde la longitud de w2 es mayor o igual que la de

w1 , o bien w1  

También generan los lenguajes dependientes de contexto. Contienen reglas de producción de la

forma:  A     , donde A es un no terminal ,  y  son cadenas de terminales y no

terminales.  y  pueden ser vacíos, pero  ha de ser distinto del vacío

Ejemplos
Son de TIPO I
G1 = ({0, 1}; {A, B}, A, P), donde P: G2 = ({a, b}; {A, S}, S, P), donde P:
A  1B1 | 11 S  ab | bA
1B1  101 | 111 A  a | aS

No son de TIPO I
G3 = ({a, b}; {A, S}, S, P), donde P:
No es de TIPO ya que la producción abA  baab no
S  ab SA
mantiene constante lo que esta antes del símbolo A.
abA  baab
La regla debería ser abA  abab
Sa
Ab

Prof. Lic. Christian L. Staple 51

 UNLAM - DIIT –MATEMÁTICA DISCRETA

GRAMÁTICAS DE TIPO II (INDEPENDIENTES DEL CONTEXTO) Estas gramáticas se denominan de

contexto libre, porque a la hora de transformar una palabra en otra, el símbolo no terminal que se
transforma no depende de los que estén a la izquierda o derecha.
Generan los lenguajes libres de contexto. Están definidas por reglas de la forma: A  
A es un no terminal y  es una cadena de terminales y no terminales.

Ejemplos
G1 = ({a, b}; {A, B, S}, S, P), donde P: G2 = ({a, b}; {A, B, S}, S, P), donde P:
S  aB | bA A  aAAS  aB | bA
A  a | aS B  b | aS |aBB

GRAMÁTICAS TIPO III (GRAMÁTICAS REGULARES) Generan los lenguajes regulares. Las reglas se
restringen a un único no terminal en la parte izquierda y una parte derecha compuesta por un único
terminal que puede estar seguido o no de un único no terminal. Es decir, normas del tipo: A a B ó
Aa ó A 
Ejemplos
G1 = ({a, b}; {A, S}, S, P), donde P: G2 = ({a, b}; {A, B, S}, S, P), donde P:
S  aA | bA S  bB | bA
A  a | aA B  aB | 
A  a| 

Prof. Lic. Christian L. Staple 52

 UNLAM - DIIT –MATEMÁTICA DISCRETA

AUTÓMATAS. DEFINICIONES
Los autómatas son entes o máquinas abstractas que prueban la pertenencia o no de cada cadena de
símbolos sobre un vocabulario dado a un cierto lenguaje. En el área de los intérpretes,
compiladores, traductores y procesadores, es de notable importancia la simulación de procesos
encargados del tratamiento de la información.
La información se codifica en cadenas de símbolos y un autómata es una máquina formal, es decir
sin componentes físicas, que manipula cadenas de símbolos que lee en su entrada generando
cadenas de símbolos en su salida.

AUTÓMATAS, LENGUAJES Y GRAMÁTICAS. LA JERARQUÍA DE CHOMSKY

Dado que las gramáticas proporcionan las reglas utilizadas en la generación de las cadenas de un
lenguaje, se puede establecer una conexión entre las clases de lenguajes generados por ciertos
tipos de gramáticas y las clases de lenguajes reconocibles por ciertas máquinas.

AUTÓMATA FINITO Un AF es una máquina “reconocedora”, ya que a partir de una cadena de

entrada, solo dice “si” o “no”. Lo cual indica si esa cadena pertenece o no al lenguaje reconocido o
aceptado por la máquina. Un AF es una máquina con un número finito de estados definida
formalmente es la 5-upla AF = (Q; V;  ; q0; F) donde:
Q = {q1,q2, ...,qn} es el conjunto finito de estados de la máquina
V es el alfabeto de entrada.
 : Q x V →Q es la relación de transición
q0  Q se dice estado inicial y es único.
F  Q es el conjunto de estados finales.

Prof. Lic. Christian L. Staple 53

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Los AF se pueden representar mediante

1. Un diagrama de transiciones, que es un grafo.
2. Una tabla de transiciones, que es una enumeración tabular (tabla) de la función  , que a la vez
describe el conjunto de estados, y el alfabeto de entrada.

DIAGRAMAS DE TRANSICIONES
Un diagrama de transiciones para un AF, es un grafo definido de la siguiente forma:
 Hay un nodo para cada estado de Q.
 El nodo correspondiente al estado inicial q0, tendrá una flecha sin origen.
 Los nodos correspondientes a los estados de aceptación (los que pertenecen a F) están
marcados con un doble círculo. Los que no pertenecen a F tienen un círculo simple.

TABLA DE TRANSICIONES
Una tabla de transiciones es una representación tabular convencional de una función como  , que
recibe dos argumentos y devuelve un valor.
Los AF se dividen en diversas clases, dependiendo de si su control es “determinista” (lo que significa
que el autómata no puede estar en más de un estado simultáneamente) o “no determinista” (lo
que significa que el autómata puede estar en varios estados al mismo tiempo).

Ejemplos AF

AFD = ({q0, q1}; {0, 1};  ; q0; {q1})

AFD = ({q0, q1. q2}; {0, 1};  ; q0; {q1})

Prof. Lic. Christian L. Staple 54

 UNLAM - DIIT –MATEMÁTICA DISCRETA

AFN = ({q0, q1. q2}; {0, 1};  ; q0; {q2})

LENGUAJE ACEPTADO POR UN AUTÓMATA DE ESTADO FINITO

Definición una palabra es aceptada por un autómata si comenzando a calcular en el estado q0 y

leyendo los distintos símbolos de la palabra llega a un estado final.

EXPRESIONES REGULARES Una expresión regular es una forma de representar cierto tipo de
lenguajes sobre un determinado alfabeto.

Como obtener la expresión regular

a
 q1  q2 es equivalente a q1  aq2
a b
 q1  q2 y q1  q3 es equivalente a q1  aq2  bq3
a
 q1  q1 es equivalente a q1  aq1 o q1  a*
a b
 q1  q1 y q1  q2 es equivalente a q1  a*  bq2 o q1  a*q2

 Si q1 es estado final y  la palabra nula, es equivalente a q1  


Ejemplo: AF  q0, q1, q2 , a, b ,  , q0, q2

EXPRESIÓN REGULAR
q0 = a.q1

q1 = b.q1  a.q2
q2 = 

Despejando la variable q2 y Reemplazando en las ecuaciones
q0 = a.q1
q1 = b.q1  (a. )
Aplicando Lema de Arden sobre la variable q1
q1 = b*.((a. ))
Reemplazando q1 en la ecuacion
q0 = (a.(b*.(a. )))
ER a.b*.a

Prof. Lic. Christian L. Staple 55

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo: AF  q0, q1, q2 , 4,5 ,  , q0, q0, q2

EXPRESIÓN REGULAR
q0 = 4.q0  5.q1  

q1 = 4.q2  5.q2=  4  5  .q2
q2 = 

Despejando la variable q2 y reemplazo en q1
q1 =   4  5   
Reemplazando q1 en q0

  
q0 = 4.q0  5.   4  5     

  
q0 = 4*. 5.   4  5     
ER  4*.5.  4  5   

ANÁLISIS COMBINATORIO

La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que

estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen
ciertas condiciones establecidas.

PRINCIPIO MULTIPLICATIVO Suponemos que una primera operación puede realizarse de n1

maneras y una segunda operación se puede realizar de n2 maneras. Entonces, se puede realizar las
dos operaciones sucesivamente de N = n1.n2 maneras. Este principio puede extenderse a más de
dos operaciones: si k operaciones se pueden realizar sucesivamente y que, para cada i ∈ {1, . . . , k},
la i-´esima operación se realiza de ni maneras, entonces hay
N = n1.n2 . . . nk maneras de realizar las k operaciones sucesivamente.

Ejemplo: Un matrimonio decide comprar una radio y una cocina. Si en el lugar donde harán la
compra hay 4 tipos de radio y 2 tipos de cocina. ¿De cuántas maneras distintas pueden realizar la
compra de ambos objetos a la vez? Respuesta: N = 4 × 2 = 8

PRINCIPIO ADITIVO Suponemos que una primera operación puede realizarse de n1 maneras y que
una segunda operación se puede realizar de n2 maneras. Además, se supone que las dos
operaciones no se pueden realizar simultáneamente. Entonces, se puede realizar la primera o la
segunda operación de N = n1 + n2 maneras. Este principio puede extenderse a más de dos
operaciones: si k operaciones pueden realizarse, pero ninguna simultáneamente, y que, para cada i
∈ {1, . . . , k}, la i-´esima operación se realiza de ni maneras, entonces hay N = n1 + n2 + . . . + nk
maneras de realizar las primera o la segunda o...la k-´esima operación.

Prof. Lic. Christian L. Staple 56

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo: Una pareja quiere ir al sur de Chile. Para ir en avión hay 2 compañías y para ir en bus 3
compañías. Entonces, tienen 2 + 3 = 5 maneras de ir al sur.

DEFINICIÓN: Si n es un número natural, esto es n   , llamaremos factorial de n al producto desde

1 (uno) hasta n
n!  n   n  1   n  2 ......3  2 1
Se define también el factorial de 0 como 0!  1

VARIACIONES SIN REPETICIÓN: Se llama variación de m elementos tomados de a r, al número

total de grupos de r elementos que pueden formarse con los m dados considerando que 2 grupos
son distintos cuando difieren en sus elementos o en el orden en que aparecen. (IMPORTA EL
ORDEN)
Para calcular este número tenemos la siguiente fórmula:

m!
Vmr   m   m  1   m  2  .............  m  r  1 con m  r
 m  r !

Ejemplos
¿De cuántas maneras distintas pueden sentarse 5 personas en un auto con 4 asientos?
Es importante el orden ya que no da lo mismo sentarse en uno o en otro asiento, por lo tanto es
una variación
5!
V54   5.4.3.2  120
 5  4 !
De 120 maneras distintas.

¿Cuántos números distintos de cuatro cifras que no se repitan podrán formarse con los dígitos 1,
2, 7, 8 y 9?
Es importante el orden ya que no da lo mismo formar el número 1278 o el 9872
5!
V54   5.4.3.2  120
 5  4 !
De 120 números distintos.

PERMUTACIONES SIN REPETICIÓN: Una permutación de m elementos es una variación de estos m

elementos tomados de a m grupos.
Luego, para calcularla usamos la fórmula:
Pm  Vmm  m!  m   m  1   m  2 .............3  2 1
Ejemplos
Cuántas permutaciones pueden hacerse con las letras de la palabra MURCIÉLAGO, sin que se
separen las vocales IE?

M
UR
 CIÉ
L A
GO

1 2 3 4 5 6 7 8 9

P9  9!  362880
Pero pueden aparecer tanto IE como EI
P9 .P2  9!.2!  362880.2  725760

Prof. Lic. Christian L. Staple 57

 UNLAM - DIIT –MATEMÁTICA DISCRETA

¿De cuántas maneras se pueden colocar en fila 6 hombres, no pudiendo uno determinado estar
nunca a la cabeza? Rta: 600

P6  P5  6!5!  600

COMBINACIONES SIN REPETICIÓN: Llamaremos combinatoria de m elementos tomados de a r al

número total de grupos distintos que podemos formar con r elementos (sin repetirlos) eligiéndolos
entre los m dados sin importar el orden en que aparecen los elementos en cada grupo. (NO
IMPORTA EL ORDEN)
Vr m!
Esto se calcula con la siguiente fórmula: Cmr  m 
Pr r !  m  r !

Ejemplos
Cuantos productos pueden formarse con 3 factores elegidos entre los números 5, 7, 11, 13.

4! 4! 4. 3!
C43    4
 4  3!.3! 1!.3! 1!. 3!

Tenemos 8 corbatas y 4 camisas disponibles y solo podemos comprar tres corbatas y dos camisas.
¿Cuántas combinaciones podemos efectuar en la realización de la compra?

4! 8!
C42 . C83  
 4  2 !.2! 8  3!.3!
4.3. 2! 8.7.6. 5! 4.3. 8.7.6
C42 . C83      6.56  336
2!. 2! 5! .3! 2.1 3.2.1

VARIACIONES CON REPETICIÓN Dada una colección de m objetos a1, a2, . . . , am−1, am distintos y un
número entero positivo n, llamaremos variación con repetición de orden n a cualquier subconjunto
de n objetos del conjunto dado pudiendo repetirse los mismos.

VRmr  mr con m  r o m  r
Ejemplos
Calcular cuántas palabras de tres letras pueden formarse con las letras A,B,C,D y E en los
siguientes casos:
(a) Comienzan por A.
(b) No contienen la letra A.
(c) Contienen la letra A.

Veamos cuántas palabras comienzan por A.

Bastaría anteponer la letra A a cada una de las variaciones con repetición de segundo orden de las
cinco letras dadas. Consecuentemente, el número de palabras de tres letras construidas con las
cinco dadas y que empiezan por A es
VR5,2 = 52 = 25

Calculamos cuántas palabras no contienen a la letra A.

En este caso, bastaría calcular el número de palabras de tres letras que pueden formarse con B,C,D
y

Prof. Lic. Christian L. Staple 58

 UNLAM - DIIT –MATEMÁTICA DISCRETA

E, es decir,
VR4,3 = 43 = 64

Veamos, finalmente, cuántas palabras contienen la letra A.

El número total de palabras de tres letras es V R5,3 y el numero de palabras que no contienen la
letra A es, según el apartado (b), V R4,3 consecuentemente el número pedido es
VR5,3 − VR4,3 = 53 − 43 = 125 − 64 = 61

Con los dígitos 0 y 1 pueden formarse un total de 256 bytes. Decir cuántos hay que
(a) comiencen por 1100.
(b) se lean exactamente igual de izquierda a derecha que de derecha a izquierda.

Veamos cuántos de ellos comienzan por 1100.

A cada uno de los grupos de cuatro bits que puedan formarse le anteponemos 1100 y tendremos
todos los que comienzan por dicho número. Por tanto, habrá tantos como las variaciones con
repetición de orden cuatro de los dígitos 0 y 1, es decir,
VR2,4 = 24 = 16

Veamos ahora cuántos bytes se leen exactamente igual de izquierda a derecha que de derecha a
izquierda. Para construir un byte que cumpla estas condiciones bastaría añadir a un grupo de cuatro
bits el mismo en sentido contrario. Por ejemplo, si a 1010 le añadimos 0101 tendremos el byte
10100101 que cumple las condiciones exigidas. Por tanto, calcular el número pedido equivale a
calcular cuántos grupos de cuatro bits pueden formarse con los dígitos 0 y 1. Consecuentemente,
habrá
VR2,4 = 24 = 16

PERMUTACIÓN CON REPETICIÓN Llamamos a las permutaciones con repetición de n elementos

tomados de a en a, de b en b, de c en c, etc, cuando en los n elementos existen elementos repetidos
(un elemento aparece a veces, otro b veces, otro c veces, etc) verificándose que a + b + c +... = n.
Para formar un grupo se toman todos los elementos, no hay que seleccionar unos pocos, hay que
tener en cuenta el orden en que se colocan los elementos; si se altera el orden, se tiene un grupo
distinto y hay repetición de los elementos dentro de un mismo grupo. El número de estas
permutaciones será:

m!
PRma ,b,c ,d 
a ! b ! c ! .... d !

Ejemplos

¿Cuál es el número total de permutaciones que se puede formar con las letras de la palabra
MATEMATICA?

n! 10!
PRm( a ,b,c )  PR10(3,2,2)   151200
a !.b !.c ! 3!.2!.2!

Con las letras A, A,M,B,B,E,E,

(a) ¿Cuántas palabras pueden construirse?
(b) ¿Cuantas empiezan y acaban en E?

Prof. Lic. Christian L. Staple 59

 UNLAM - DIIT –MATEMÁTICA DISCRETA

7!
a- PR7(2,1,2,2)   630
2!1! 2! 2!

5!
b- PR5(2,1,2)   30
2!1! 2!

COMBINACIONES CON REPETICIÓN El número de combinaciones con repetición de orden n de una

colección de m objetos lo simbolizaremos por CRm,r y lo llamaremos combinaciones con repetición
de m elementos tomados n a n. Su valor es
 m  r  1  m  r  1!
CRmr   
 n  r !  m  1!

Ejemplos

Se dispone de tres bolsas iguales con caramelos de fresa, de menta y de limón. Cada una de las
bolsas contiene, al menos, diez caramelos. Decir de cuántas formas pueden seleccionarse diez
caramelos en los siguientes casos:
(a) sin ninguna restricción.
(b) en cada selección deben figurar, al menos, un caramelo de fresa, dos de menta y tres de
limón.

Veamos de cuántas formas pueden seleccionarse diez caramelos si no hay ninguna restricción. Una
de las posibles distribuciones de los diez caramelos es ffmflmmfll
Observamos que si en esta distribución elegida al azar, intercambiamos entre sí uno o varios
sabores, la misma no varía, sin embargo si cambiamos uno o varios caramelos por otros de distinto
sabor, tendremos una distribución diferente, por tanto, las distribuciones de los diez caramelos son
combinaciones con repetición de orden diez elegidas entre los tres tipos de caramelos distintos.
Consecuentemente, los diez caramelos pueden seleccionarse de

 3  10  1 12  12!
CR310      66
 10  10  10! 2!

En cada selección fijamos un caramelo de fresa, dos de menta y tres de limón, quedarán, por tanto,
cuatro caramelos de entre los tres sabores para elegir, el mismo razonamiento del apartado
anterior nos conduce a que el número de selecciones distintas es

 3  4  1  6  6!
CR34      15
 4   4  4! 2!

En una confitería hay cinco tipos diferentes de tortas. ¿De cuantas formas se pueden elegir cuatro
tortas pudiéndose elegir varios del mismo tipo?
No importa el orden y puede haber dos o más tortas en un mismo grupo. Entonces es una
combinación con repetición
 5  4  1  8  8!
CR54      70
 4   4  4! 4!

Prof. Lic. Christian L. Staple 60

 UNLAM - DIIT –MATEMÁTICA DISCRETA

LÓGICA PROPOSICIONAL

La lógica estudia métodos de razonamiento que separan los razonamientos válidos de los no
válidos. El interés por el análisis de los razonamientos se debe a que en las ciencias de la
computación deben aplicarse para lograr que los programas realicen lo que se pretende.
Los razonamientos se basan en la enunciación de una secuencia proposiciones, que se conocen
como premisas, para arribar a una conclusión.

Una proposición es un enunciado, un conjunto de palabras que puede ser verdadera o falsa.
Una proposición es atómica si es imposible descomponerla en proposiciones más simples.
Para combinar proposiciones y formar nuevas proposiciones más complejas usamos los llamados
conectivos lógicos.

ALGUNOS CONECTIVOS

NEGACIÓN La negación de una proposición es la que afirma que la proposición original no es

verdadera. Generalmente se obtiene agregando “no” (o “no es verdad que”) antes de la
proposición original.

Ejemplo:
p: hay un premio Nobel de ciencias de la computación.
 p: no hay un premio Nobel de ciencias de la computación.

CONJUNCIÓN La conjunción de dos proposiciones es la que afirma que ambas proposiciones son
verdaderas. Se obtiene intercalando “y” entre las dos proposiciones originales.

Prof. Lic. Christian L. Staple 61

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo:
Sea la declaración:

5 es un número impar y 6es un número par

  
p  q

Vemos que está compuesta de dos proposiciones a las que llamaremos p y q, que son
p: 5 es un número impar q: 6 es un número par
Por ser ambas verdaderas, la conjunción de ellas es verdadera.
Ahora bien, sea la declaración
Hoy es el día 3 de noviembre y mañana es el día de 5 de noviembre
Esta conjunción es falsa, ya que no pueden ser simultáneamente verdaderas ambas proposiciones.

DISYUNCIÓN La disyunción de dos proposiciones es la que afirma que al menos una de las dos
proposiciones es verdadera. Se obtiene intercalando “o” entre las dos proposiciones originales.

Ejemplo:
Sean las proposiciones simples: p: 1 + 1 = 3 y q: una década tiene 10 años.
Entonces la disyunción es: p  q: 1 + 1 = 3 o una década tiene 10 años.

CONDICIONAL La proposición condicional entre dos proposiciones (el antecedente y el

consecuente) es la que afirma que, cada vez que el antecedente es verdadero, el consecuente
también lo es. Puede ser obtenido precediendo el antecedente por “si” e intercalando “entonces”
entre el antecedente y el consecuente.

Ejemplo:
Si apruebo, entonces te prestoel libro
 


p q

Supongamos la implicación
p: apruebo q: te presto el libro
Nos interesa conocer la verdad o falsedad de la implicación, en relación a la verdad o falsedad de las
proposiciones p y q.

Prof. Lic. Christian L. Staple 62

 UNLAM - DIIT –MATEMÁTICA DISCRETA

El enunciado puede pensarse como un compromiso, condicionado por p, y podemos asociar su

verdad al cumplimiento del compromiso.
 Es evidente que si p es F, es decir si no apruebo el examen, quedo liberado del compromiso y
preste o no el apunte la implicación es verdadera.
 Si p es verdadera, es decir si apruebo el examen, y no prestó el libro, el compromiso no se
cumple y la proposición es falsa.
 Si p y q son verdaderas, entonces la proposición es verdadera pues el compromiso se cumple.

BICONDICIONAL La proposición bicondicional entre dos proposiciones es la que afirma que, o

ambas son verdaderas, o ambas son falsas. Puede ser obtenida intercalando la frase “si y sólo si”, o
bien “siempre y cuando” entre las dos proposiciones originales.

Ejemplo:
Sean p: 1 + 1 = 3 y q: una década tiene 10 años.
p  q: 1 + 1 = 3 si y sólo si una década tiene 10 años.

DIFERENCIA SIMÉTRICA o disyunción en sentido excluyente. Se lee “p o q” en sentido excluyente

Ejemplo:
O vamos a Córdoba o vamos a Mendoza
Queda claro que sólo podremos ir a uno de los dos lugares, y sólo a uno. Es decir que el enunciado
es verdadero sólo si vamos a una de las dos ciudades. En caso de ir a ambas, o de no ir a ninguna, el
enunciado es Falso.

TAUTOLOGÍA Llamamos tautología a aquella proposición compuesta cuyo valor de verdad es

siempre verdadero en forma independiente del valor de verdad de las proposiciones simples que la
componen.

Prof. Lic. Christian L. Staple 63

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Ejemplo: Si analizamos la proposición t: p   p realizando su tabla de verdad:

p p p  p

V F V
F V V

CONTRADICCIÓN (F) Llamamos contradicción a aquella proposición compuesta cuyo valor de

verdad es siempre falso en forma independiente del valor de verdad de las proposiciones simples
que la componen.

Ejemplo: Analicemos la fórmula lógica p   p

p p p p

V F F
F V F

CONTINGENCIA Se denomina contingencia a aquella proposición compuesta cuyo valor de verdad

depende del valor de verdad de las proposiciones simples que la componen.

CUANTIFICADORES: En lógica, teoría de conjuntos y matemática en general, los cuantificadores son

símbolos utilizados para indicar cuantos elementos de un conjunto dado cumplen con cierta
propiedad.

Hay dos tipos de cuantificadores: universal y existencial.

a) Universal: Partiendo de una proposición simple e indeterminada, a través del cuantificador la
transformamos en una proposición universal (ej. es mecánico; al cuantificarla universalmente nos
da: todos son mecánicos). Cuantificadores universales: todo, cualquier, etc.; y se simboliza con  .

b) Existencial: Se simboliza con  Cuantificadores existenciales: hay, algunos, algún, etc.

A este tipo de proposiciones se las conoce como Proposiciones generales simples ya que tienen un
único predicado y son universalmente existenciales.

Negación de los cuantificadores

~ [x : P  x ]  x /  P  x  ~ [x : P  x ]  x :~ P  x 

Prof. Lic. Christian L. Staple 64

 UNLAM - DIIT –MATEMÁTICA DISCRETA

LEYES LÓGICAS
Sean P y Q dos proposiciones cualesquiera (atómicas o compuestas). Diremos que P y Q son
lógicamente equivalentes si toda asignación de verdad que hace verdadera a P hace verdadera a Q
y viceversa. Denotaremos la equivalencia lógica entre P y Q por P  Q.
1. IDEMPOTENCIA p p  p p p  p

2. CONMUTATIVA pq  q p pq  q p

3. ASOCIATIVA  p  q  r  p  q  r   p  q  r  p  q  r 
4. ABSORCIÓN p   p  q  p p   p  q  p

5. DISTRIBUTIVA p  q  r    p  q   p  r  p  q  r    p  q   p  r 

6. IDENTIDAD p V  p p V  V
pF  F p F  p

7. INVOLUTIVA   p  p

8. DEL COMPLEMENTO  p  p   V  p  p   F
9. DE DE MORGAN   p  q   p   q   p  q   p   q

10. LEYES CONDICIONALES p  q  p  q p  q  q  p

11. LEYES BICONDICIONALES p  q   p  q   q  p  p  q    p  q    p  q 

RAZONAMIENTOS
Un razonamiento es un conjunto de proposiciones en la cual una de ellas, llamada conclusión, se
afirma sobre la base de las demás llamadas premisas. El razonamiento anterior se dice que es válido
si la conclusión Q es verdadera cada vez que todas las premisas P1, P2, . . . , Pn lo sean.

MÉTODOS DE DEMOSTRACIÓN
Todo enunciado puede ser planteado en términos de teoremas. Un teorema por lo general es
resultado de un planteamiento de un problema, que normalmente presenta el siguiente formato:
(p1p2pn)q

Como se establece p1, p2, p3,…….,pn son hipótesis (o premisas) derivadas del mismo problema y que
se consideran válidas. Pero además deberán conectarse con el operador “y” (), lo cual implica que
p1 es cierta y () p2 es verdad y ()...... y pn también es cierta entonces () la conclusión (q) es cierta.

Prof. Lic. Christian L. Staple 65

 UNLAM - DIIT –MATEMÁTICA DISCRETA

MÉTODO DEL CONDICIONAL ASOCIADO es un método mecánico que se basa en las tablas de
verdad.
  p   q  r      q  r     p
p  q  r 
v v v v v f f v f
 q  r 
v f v f f f v v f
p v f f f v f v v f
v f f f f f v v f
  p   q  r     q  r   p f v v v v f f v v
f v v f f v v v v
f v f f v v v v v
f v f f f v v v v

MÉTODO DIRECTO El método de demostración directa parte de la proposición p, que se supone

verdadera, y deducir de ella una nueva proposición q que se pueda ver que es verdadera como
resultado de que p lo es. Es importante resaltar que las proposiciones deducidas de p no deben ser
hechas de cualquier modo, deben estar enfocadas hacia la última proposición obtenida.
El camino que se debe seguir para llevar a cabo una demostración formal usando el método directo
significa que si se sabe que p1 es verdadera, p2 es verdadera,..., y pn también es verdadera,
entonces se sabe que q es verdadera.

p  q  r  Suponemos que las premisas son verdaderas

p   q  r  es verdadera y  q  r  es falsa, entonces p tiene que ser falsa.
 q  r 
  q  r  es verdadera entonces  q  r  es falsa
p
Por lo tanto  p es verdadera.

REDUCCIÓN AL ABSURDO En el método de demostración de reducción al absurdo, se debe

empezar suponiendo que p es verdadera, al igual que se hacía en el método de demostración
directa. Ahora, sin embargo, para llegar a la conclusión buscada, a saber, que q es verdadera se
puede proceder haciendo una pregunta muy simple: “¿Por qué no puede q ser falsa?”. Después de
todo, si q tiene que ser verdadera, debe haber alguna razón por la que no pueda ser falsa. El
objetivo del método de demostración por reducción al absurdo es, precisamente, descubrir esa
razón. La idea es suponer que p es verdadera y q falsa y ver que no puede ocurrir esto

Suponemos que  p es falsa, entonces p es verdadera

p  q  r 
Si p es verdadera  q  r  debe ser verdadera, por lo tanto q y r son
 q  r  verdaderas.
p  q  r  es verdadera entonces   q  r  es falsa ABSURDO ya que
  q  r  es verdadera por hipótesis. Por lo tanto  p es verdadera.
Prof. Lic. Christian L. Staple 66
 UNLAM - DIIT –MATEMÁTICA DISCRETA

INFERENCIA
p  q  r    p   q  r     q  r   p
 q  r  Por Modus Tollens

p

INDUCCIÓN
Prof. Lic. Christian L. Staple 67
 UNLAM - DIIT –MATEMÁTICA DISCRETA

En muchos casos se quiere probar que alguna propiedad relativa a los números naturales es cierta.
Para demostrarlo podemos analizar algunos casos particulares.

Axiomas son verdades reveladas que se aceptan sin demostrar y rigen el comportamiento de los
conceptos primitivos, de ellos se deducen los teoremas.
El Cuerpo Axiomático consiste en los siguientes cinco Axiomas:
 Ax1: 1 es un número natural. Esto significa que existe al menos un número natural
 Ax2: Si n ∈ N entonces n + 1 ∈ N. Todo número natural tiene un sucesor, n + 1 debe ser
entendido como el símbolo sucesor de n
 Ax3: No existe un número natural n, tal que su sucesor sea 1, Esto significa que N posee un
primer elemento
 Ax4: Si n ∈ N y m ∈ N tal que n + 1 = m+ 1 entonces n = m. Esto significa que podemos escribir
sin ambigüedad N = {1, 2, 3, · · · }
 Ax5 : Si S ⊂ N es tal que verifica simultáneamente las dos siguientes propiedades:
 1∈S
 n ∈ S =⇒ n + 1 ∈ S
 entonces S = N
Ax5 se conoce como el axioma de inducción o principio de inducción. Es una de las más bellas
estrategias que utiliza el intelecto humano, para ”hacer finito lo infinito”

Axiomas de Peano y las fórmulas proposicionales Sea F(n) una fórmula proposicional para cada
n ∈ N. Si
◦ F(1) es verdadera, y
◦ F(n) verdadera =⇒F(n + 1) verdadera

Ejemplo 1
n
n   n  1
F ( n) :  i 
i 1 2
Paso base F (1) Hipótesis Inductiva F (h) Hipótesis Inductiva F (h  1)
n
n   n  1 h
h   h  1 h 1
 h  1   h  2
F (1) :  i  F ( h) :  i  F (h  1) :  i 
i 1 2 i 1 2 i 1 2
1 1  1
1 
2
1 1

Prof. Lic. Christian L. Staple 68

 UNLAM - DIIT –MATEMÁTICA DISCRETA

Demostración.
h 1 h
h  h  1 h  h  1  2  h  1
 i  1
i 1
 2  ....... h   h  1   i   h  1
3
h i 1

Por HI 2
  h  1 
2
i
i 1

h 1
 h  1 h  2 
i
i 1

Factor comun 2
n
n   n  1
Por lo tanto F (n) :  i  es verdadera n 
i 1 2

Ejemplo 2
F (n) :15 | 24n  1 F (n) : 24n 1  15  q con q 

Paso base F (1) Hipótesis Inductiva F (h) Hipótesis Inductiva F (h  1)

4 h 1
F (1) : 24  1  F (h) : 24 h  1  15  q2 F (h  1) : 2  1  15  q3
16  1  15  q1 con q2   con q3  
con q1  

Demostración

2
4 h 1
 1  24 h  24  1 
 15  q2  1 16  1  15  q2 16  16  1  15  q2  15  15   q2  1
Por HI

 1  15   q2  1 , con q3  
4 h 1
2

q3

Por lo tanto F(n) es verdadera

Ejemplo 3
F (n) : 3 | n3  n, n   F (n) : n3  n  3  q

Paso base Paso Inductivo

n 1 Hipótesis n  h Tesis n  h  1

F (h  1) : h  1   h  1  3  q1
3
F (1) :13  1  0  3  0 F (h) : h3  h  3  q

Demostración

 h  1   h  1  h3  3h 2  3h  1  h  1   h3  h   3   h 2  h  
 3  q  3   h  h 
3 2

por HI

 h  1   h  1  3   q  h2  h 
3

factor comun 
q2

Por lo tanto F(n) es verdadera

Prof. Lic. Christian L. Staple 69

 UNLAM - DIIT –MATEMÁTICA DISCRETA

NÚMEROS ENTEROS
División entera:
D d
R C

Dados dos números enteros D y d, existen y son únicos otros dos enteros C y R tales que:
D = d C + R con 0  R  d D se llama DIVIDENDO, d es el DIVISOR, C es el COCIENTE y R el RESTO de

la división entera. Esto se llama Algoritmo de la División.

DIVISIBILIDAD Sean a, b  , con a  0 : a | b  k   / b  k a

Se lee: a “divide a” b ó a “es divisor de” b ó b “es múltiplo de” a ó b “es divisible por” a

MCM (MÍNIMO COMÚN MÚLTIPLO) Y MCD (MÁXIMO COMÚN DIVISOR)

Sean a, b  , no simultáneamente nulos, y sea m  , entonces m = m.c.m. (a,b) si y sólo si se
cumplen las siguientes condiciones:
1)a | m
2)b | m
3) Si m’  0 : a | m’  b | m’  m | m’

Sean a, b  no simultáneamente nulos, y sea d  , entonces d = m.c.d. (a,b) si y sólo si se

cumplen las siguientes condiciones:
1)d | a
2)d | b
3) Si d ’  0 : d ’ | a  d ’ | b  d ’ | d
Notaciones: m.c.m.(a,b) = [ a, b ] m.c.d.(a,b) = ( a, b )

PROPIEDAD DEL MCD entre dos enteros: puede ser escrito como combinación lineal entera de
dichos enteros. Si d = m.c.d.(a,b) entonces k1 , k2  tales que d  k1a  k2b

PROPIEDAD DEL MCM Y MCD: el producto de ambos es igual al módulo de a  b ,

 a, b    a, b  a b

Prof. Lic. Christian L. Staple 70

 UNLAM - DIIT –MATEMÁTICA DISCRETA

ALGORITMO DE EUCLIDES PARA CALCULAR EL MÁXIMO COMÚN DIVISOR

Dados dos enteros a y b, el m.c.d.(a,b) = m.c.d.(b,r) siendo r el resto de la división de a por b. Esta
propiedad puede demostrarse.
Volvemos a aplicar esta propiedad, es decir m.c.d.(b,r) = m.c.d.(r, r1) siendo r1 el resto de la división
de b por r. Luego m.c.d.(r, r1) = m.c.d.(r1,r2) siendo r2 el resto de la división de r por r1. Y así
sucesivamente hasta llegar a un resto igual a cero. De esta manera se puede encontrar el m.c.d.
entre dos enteros dados, ya que es el último resto no nulo.

Por ejemplo:
Vamos a calcular el m.c.d.(720, 224). Para ello realizamos las siguientes divisiones enteras sucesivas:
720 224 224 48 48 32 32 16
48 3 32 4 16 1 0 2

Como el ultimo resto no nulo es 16, entonces m.c.d.(720,224) = 16

FORMA MATRICIAL:
Primero se coloca la matriz identidad de orden 2, y en una tercer columna los dos números enteros,
siendo el mayor el de la primera fila.

La idea es ir obteniendo nuevas filas, siempre operando con las últimas dos anteriores, de modo de
restar de la anteúltima la mayor cantidad de veces que entra el término independiente de la última.
En realidad es hacer la división entera y restar el cociente por el elemento de la última fila.
Por ejemplo, en este caso, al dividir 720 por 224, se obtiene cociente 3, entonces vamos a restar 3
veces la fila 2 de la fila 1, la resta se hace en toda la fila:

Y luego seguimos este procedimiento hasta llegar a un valor nulo. El anterior al nulo es el máximo
común divisor.

Obtenemos que m.c.d.(720,224) = 16 y además: 16  5720   16  16

Prof. Lic. Christian L. Staple 71