Matemática Discreta - 2020

Vista previa del material en texto

Matemática Discreta 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIDAD 1: LÓGICA 3 
PROPOSICIÓN 3 
DEMOSTRACIONES 5 
UNIDAD 2: TEORÍA DE NÚMEROS 8 
DIVISIBILIDAD 8 
MÁXIMO COMÚN DIVISOR Y MÍNIMO COMÚN MÚLTIPLO 9 
CAMBIO DE BASE 10 
ECUACIONES DIOFÁNTICAS 11 
CONGRUENCIA LINEAL 12 
UNIDAD 3: RECURRENCIA 13 
SUCESIÓN: 13 
RELACIÓN DE RECURRENCIA LINEAL CONSTANTE DE GRADO 15 
SOLUCIÓN DE LAS RELACIONES DE RECURRENCIA HOMOGÉNEAS 16 
UNIDAD 4: TEORÍA DE GRUPOS 19 
CLASIFICACIÓN DE GRUPOS 19 
UNIDAD 5: ÁLGEBRA DE BOOLE 21 
CARACTERÍSTICAS DE UN ÁLGEBRA DE BOOLE 21 
FORMAS NORMALES DISYUNTIVAS Y CONJUNTIVAS BOOLEANAS 23 
UNIDAD 6: GRAFOS 24 
GRAFOS 24 
GRAFOS NO DIRIGIDOS 24 
GRAFOS DIRIGIDOS O DIGRAFOS 25 
CLASES DE GRAFOS 26 
REPRESENTACIÓN MATRICIAL DE GRAFOS NO DIRIGIDOS 26 
REPRESENTACIÓN MATRICIAL DE DIGRAFOS 27 
COMPARACIÓN DE GRAFOS 28 
TRAYECTORIA, CICLOS Y CONECTIVIDAD 29 
GRAFOS ESPECIALES 30 
GRAFOS DE ÁRBOL 31 
UNIDAD 7 (EXTRA): TEORÍA DE CONJUNTOS 33 
CONJUNTOS 33 
OPERACIONES CON CONJUNTOS 35 
PARES ORDENADOS Y PRODUCTO CARTESIANO 36 
OPERACIONES 37 
RELACIONES 39 
 
Unidad 1: Lógica 
 
Proposición 
 
Definición: 
Una proposición es un enunciado cuyo sentido es afirmar si es verdadero o 
falso. 
Excepciones: 
Oraciones interrogativas, exclamativas, imperativas, desiderativas o 
indefinidas NO son proposiciones. 
• ¿Aprobaste? 
• ¡Todo está bien! 
• ¡Dormite que ya es tarde! 
• Deseo estar feliz 
• x – 2 > 4 (no sabemos porque x está indefinida) 
Proposición compuesta: 
Las proposiciones simples combinadas por operadores lógicos son 
proposiciones compuestas. 
 
 
Implicaciones asociadas: 
Directa: p → q 
Recíproca: q → p 
Contraria: ¬p → ¬q 
Contrarrecíproca: ¬q → ¬p 
Tautología, contradicción y contingencia: 
Tautología: la proposición compuesta es verdadera independientemente del 
valor de las proposiciones que la componen. 
Contradicción: la proposición compuesta es falsa independientemente del 
valor de las proposiciones que la componen. 
Contingencia: la proposición compuesta NO ES tautología ni contradicción. 
Relaciones lógicas: 
Dos proposiciones son lógicamente equivalentes cuando la doble implicación 
entre ellas es tautología, es decir, si: p  q = Tautología se dice que p = q. 
De la misma forma, una proposición implica lógicamente a otra si dicha 
implicación es tautología, es decir, si: p → q = Tautología 
Equivalencias lógicas: 
Estas son sumamente importantes para las demostraciones, si bien se pueden 
deducir, acá está una tabla que simplifica esto: 
 
 
 
Proposiciones generales y cuantificadores lógicos: 
Si tenemos la expresión P(x) siendo P un predicado (también llamada función 
proposicional) que contiene una variable x dada por un elemento del 
conjunto U, el cual es llamado Universo de Discurso, deducimos que: si 
reemplazamos x por un elemento de U, obtendremos junto con el predicado 
(P) una proposición. 
Una proposición general es un predicado cuantificado en un universo de 
discurso. Lo que quiere decir que debemos utilizar cuantificadores lógicos: 
• ∀x: P(x) Donde ∀ recibe el nombre de cuantificador universal 
• ∃x: P(x) Donde ∃ recibe el nombre de cuantificador existencial 
Al negar una proposición general obtenemos como resultado otra. 
Por ejemplo: ¬[∀x: P(x)]  ∃x: ¬P(x) o ¬[∃x: P(x)]  ∀x: ¬P(x) 
 
Demostraciones 
 
Demostración directa: 
Se parte de la verdad de la proposición general ∀x: P(x) para llegar a 
demostrar la verdad de ∀x: Q(x) utilizando definiciones, leyes y propiedades. 
Base: ∀x: [P(x) → Q(x)] 
 
 
Demostración indirecta: 
Se utiliza la demostración directa pero parte de la verdad de la proposición 
general ∀x: ¬Q(x) para demostrar la verdad de ∀x: ¬P(x). 
Base: ∀x: [¬Q(x) → ¬P(x)] 
 
Demostración por reducción al absurdo: 
Se parte de la verdad de ∀x: [P(x) ∧ ¬Q(x)] y mediante definiciones, leyes y 
propiedades debemos llegar a una contradicción o a un absurdo de la forma R 
∧ ¬R o que se contradiga el mismo enunciado. 
 
 
 
Demostración por contraejemplo: 
En una proposición general que utilice un cuantificador universal como por 
ejemplo: ∀x: P(x), se puede buscar un contraejemplo para demostrar la 
falsedad del enunciado, es decir, un elemento de x que no cumpla con P(x). 
 
Demostración por inducción: 
Dada una proposición general ∀x: P(x), se busca demostrar la veracidad de 
esta, para esto se procede a demostrar la veracidad del paso base o primer 
caso, es decir, probaremos la veracidad de P(1) donde el valor “1”, hace 
referencia al primer valor del universo de discurso. Si es verdadera, 
pasaremos al paso inductivo, que se basa en probar la veracidad de todos los 
casos que le siguen al primero, tal que P(k) → P(k + 1), donde P(k) es 
llamado hipótesis inductiva. 
 
 
Unidad 2: Teoría de Números 
 
Divisibilidad 
 
Divisores: 
Sean a y b números enteros y a ≠ 0 se dice que a divide a b si existe c ∈ Z / b = 
a . c 
Si a | b se dice que b es divisible por a 
Si a | b se dice que b es múltiplo de a 
Si a | b se dice que a es un factor de b 
Teoremas Divisores: 
Si a | b y a | c => a | (b + c) 
Si a | b y b | c => a | c 
Si a | b => a | m . b ∀m ∈ Z 
Si a | b y a | c => a | (m . b + n . c) ∀m, n ∈ Z 
Números Primos: 
Un p ∈ Z con p > 1 se dice primo si los únicos dos factores positivos de p son 1 
y p 
Si p ∈ Z con p > 1 no es primo se le dice compuesto 
Observaciones números primos: 
1 no es primo ni compuesto 
Si n es un número compuesto existen dos enteros positivos a y b tal que: 
n = a . b 1 < a , b < n 
Existen infinitos números primos 
Teoremas números primos: 
Todo entero n > 1 puede escribirse únicamente como producto de números 
primos mediante el uso de la factorización prima (TEOREMA FUNDAMENTAL 
DE LA ARTIMÉTICA) 
Si n es entero y compuesto. Existe p un factor primo de n entonces p ≤ √n 
 
Máximo Común Divisor y Mínimo Común Múltiplo 
 
Máximo común divisor: 
Sean a y b números enteros a , b ≠ 0 se dice que d ≠ 0 es un divisor común de 
a y b si d | a y d | b (d divide tanto a a como a b) 
Si d es mayor que los divisores comunes de a y b, entonces se lo denomina 
máximo común divisor 
• Al mcd (a , b) se lo conoce como fcm (a , b) o Factor Común Mayor 
• Si mcd (a , b) = 1 se dice que a y b son primos relativos o coprimos 
• Si a1, a2, …, an son enteros tales que mcd (ai , aj) = 1 son primos 
relativos de a pares Ej.: mcd (9,13)=1 ; mcd (13,25) = 1 
Teorema MCD: 
I. Algoritmo de Euclides para determinar mcd (a,b) 
 
 (Dividir el más grande por el más chico hasta que los restos sean nulos) 
Propiedades MCD: 
I. Si c | a . b siendo a y c coprimos => c | b 
II. Si mcd (a , b) = 1 y mcd (a , c) = 1 => mcd (a , b . c) = 1 
III. Si a , b ∈ Z no simultáneamente cero y K ∈ N = {1,2,3, …} 
=> mcd (ka , kb) => k . mcd (a , b) 
IV. Si mcd (a , b) = d => mcd (a/d , b/d) = 1 
V. Si mcd (a , b) = 1 => ∀c ∈ Z mcd (a . c , b) = mcd (c , b) 
VI. Si a1, …, an son coprimos con b => mcd (a1, …, an, b) = 1 
Mínimo común múltiplo: 
Si a y b son dos enteros positivos, entonces el menor entero positivo divisor 
de ambos números recibe el nombre de mínimo común múltiplo y se denota 
como mcm (a , b) 
Teorema mcm: 
I. Si a , b ∈ N => mcd (a , b) . mcm (a , b) = a . b 
 
Cambio de Base 
 
Cambio de base general: 
En la actualidad tenemos todos los números en base 10 principalmente. Por 
Ej.: 
54321 = 1+20+300+4000+50000 = 1*100+2*101+3*102+4*103+5*104 
Pero para la computación deben ser binarios, en base 2. Por Ej.: 
1010011 = 1*20+1*21+1*24+1*26 = 1+2+16+64 = 83 
Teoremas: 
Sea b ∈ Z siendo b > 1 entonces para todo entero positivo existe k 
Algoritmo para pasar de base 10 a cualquier otra 
Teniendo un número en base 10, se debe dividir consecutivamente por el 
número de la base requerida y tomar los números del resto de atrás para 
adelante, por ejemplo: 
 
Suma de números en distintabase 
Debemos tener cuidado ya que al sumar dos números en base 2, al hacer la 
suma 1 + 1 el resultado será 10, debido a que en base 2, el número “2” no 
existe. 
 
 
Ecuaciones Diofánticas 
 
Ecuaciones diofánticas: 
Son ecuaciones de forma a . x + b . y = c, donde a, b, c son coeficientes enteros 
y x, y son incógnitas donde solo nos interesan las soluciones enteras 
Teoremas ecuaciones diofánticas: 
I. Sean a y b dos números enteros no nulos y sea d = mcd (a , b) 
entonces la ecuación a . x + b . y = c tiene solución entera sí y solo sí 
d | c. Además, si x0 , y0 es una solución particular de la ecuación, 
entonces todas las soluciones están dadas por: 
x = x0 + b/d . n n ∈ Z 
y = y0 – a/d . n n ∈ Z 
II. Si conocemos una solución particular, conocemos todas las 
soluciones 
 
 
 
Congruencia Lineal 
 
Congruencia lineal: 
Una congruencia de la forma a . x ≡ b (m) donde a , b ∈ Z m ∈ N y x es 
incógnita Se llama congruencia lineal 
• Cualquier x que satisfaga a . x ≡ b (m) se denomina solución de 
congruencia 
• Cualquier x que sea solución a . x ≡ 1 (m) se denomina inverso módulo 
m 
Ej.: m = 5 3 . x ≡ 1 (5) x puede ser 2 3 . 2 = 6 ≡ 1 (5) 2 inverso 
módulo m de 3 
 
Teoremas congruencia lineal: 
I. Si el mcd (a , m) = 1 entonces la congruencia a . x ≡ 1 ( m) tiene 
solución única 
II. a . x ≡ b (m) tiene solución si mcd (a , m) | b. En este caso, si x0 es 
solución particular, todas las soluciones son: x = x0 + k . m/d k ∈ 
Z d = mcd (a , m) 
III. Para calcular la solución particular x0: 
a . x = b (m) y d = mcd (a , m) => existe r , s ∈ Z tal que: 
d = r. a + s. m => 1 = r. a/d + s. m/d => b = br/d . a + bs/d . m ≡ 
br/d . a (m) 
x0 = br/d 
 
 
 
 
Unidad 3: Recurrencia 
 
Sucesión: 
 
Sucesión de números reales: 
Es una función f: IN0 → IR, f(n) = an y se escribe: {an} n ϵ IN0 
Ejemplo: Sea la sucesión an = n/(n+1) para n ϵ IN 
a1 = 1 / (1+1) a2 = 2 / (2+1) a3 = 3 / (3+1) 
Sucesión recurrente: 
Es una sucesión para la cual existe una ecuación que exprese el termino 
general an de la sucesión en función de uno o más de sus términos anteriores: 
a1, …, an para todos los n ≤ N0 donde N0 pertenece a los naturales. Esta 
ecuación es llamada ecuación de recurrencia o ecuación en diferencias. 
 Ejemplo: Sea la relación de recurrencia an+2 = an+1 + an para n ≥ 0 
 Para n = 0, a2 = a1 + a0 
 Para n = 1, a3 = a2 + a1 
 Para n = 2, a4 = a3 + a2 
 
 
Solución de la relación recurrente: 
Si los términos de la sucesión {an} n ϵ IN0 satisfacen la relación de recurrencia, 
entonces decimos que tenemos la solución de la relación de recurrencia. 
 Ejemplo: 
1. Tenemos una progresión geométrica: 4, 12, 36, 108, … 
2. Representamos su sucesión: a0 = 4, a1 = 12, a2 = 36… 
3. Representamos la relación de forma general para obtener los 
infinitos términos de la sucesión: an / (an-1) = 3, n ≥ 1 
O bien, despejando puede ser: an = 3an-1, n ≥ 1 
4. Hacemos que la relación de recurrencia sea solución única, ya que 
 la sucesión numérica 5, 15, 45, 135 … también satisface la relación. 
Para que sea solución única debemos establecer una condición inicial. 
 En este caso, nuestra condición inicial sería: a0 = 4 
a0 = 4 
a1 = 3 . a0 = 3 . 4 
a2 = 3 . a1 = 32 . 4 
a3 = 3 . a2 = 33 . 4 
5. A partir de la condición inicial y la relación general de recurrencia 
 obtenemos la solución general: an = 3n . 4, n ≥ 0 
 
 
Relación de recurrencia lineal constante de grado 
 
Definición: 
an = c1 . an-1 + c2 . an-2 + … + ck . an-k + g(n) Dónde: 
an representa un término y an-1 su término anterior 
k representa el grado del término 
c1,2,k representan un coeficiente, siendo números reales y ck ≠ 0 
g(n) representa la homogeneidad de la relación de recurrencia 
Linealidad: 
Se dice que es una relación de recurrencia lineal porque cada término an está 
elevado a la potencia 1 y NO hay producto entre los términos de la sucesión 
de la forma: an . am 
Grado: 
Se dice que es una relación de grado k ya que cada término se expresa según 
los k términos anteriores: an-1, an-2, … , an-k 
El grado es igual a la diferencia entre el mayor y menor subíndice de los 
miembros de la sucesión que aparecen en la relación de recurrencia: 
 n – (n – k) = k 
Homogeneidad: 
Se dice que una relación es homogénea si g(n) = 0, en caso contrario se dice 
que es no homogénea 
Coeficientes constantes: 
Se dice que una relación posee coeficientes constantes si estos no están 
afectados por alguna variable de la recurrencia 
Ejemplos: 
1. Sea la relación an = 2an-1 . an-2 es de recurrencia no lineal, de grado 2, con 
coeficientes constantes y homogénea 
2. Sea la relación an = 2an-1 + 3an-2 + 4n es de recurrencia lineal, de grado 2, 
con coeficiente constante y no homogénea 
3. Sea la relación an = -n2 an-3 es recurrencia lineal, de grado 3, con 
coeficiente no constante y no homogénea 
 
Solución de las relaciones de recurrencia homogéneas 
 
Relación de recurrencia lineal, homogénea de grado 1: 
1. Obtenemos la relación de recurrencia teniendo en cuenta el término 
homogéneo: an = c1 . an + 0, n ≥ 0 → an – c1 . an = 0, n ≥ 0 
2. Proponemos una solución reemplazando an por un valor real cualquiera λ, 
es decir: an = λ . rn, r ≠ 0 λ ∈ IR 
3. Sustituimos esta igualdad con la ecuación del paso 1 tal que: 
λrn – c1 λrn-1 = 0 ➔ Operamos ➔ λrn-1 (r – c1) = 0 
4. Al ser r distinto de 0, obtenemos la siguiente ecuación cartesiana que nos 
permite hallar su valor: r – c1 = 0 ➔ Cuya raíz característica es ➔ r = c1 
5. Luego podemos decir que la solución general de la relación de recurrencia 
es: an = λc1n 
Relación de recurrencia lineal, homogénea de grado 2: 
1. Obtenemos la relación de recurrencia teniendo en cuenta el término 
homogéneo: an – c1 . an-1 + c1 . an-2 = 0, n ≥ 2 
2. Proponemos una solución reemplazando an por un valor real cualquiera λ, 
es decir: an = λ . rn, r ≠ 0 λ ∈ IR 
3. Sustituimos esta igualdad con la ecuación del paso 1 tal que: 
λrn – c1 λrn-1 – c2 λrn-2 = 0 ➔ Operamos ➔ λrn-2 (r2 – c1 r – c2) = 0 
4. Al ser r distinto de 0, obtenemos la siguiente ecuación cartesiana que nos 
permite hallar su valor: r2 – c1 r – c2 = 0 ➔ raíz característica ➔ r1 y r2 
5. Debido a que tenemos dos raíces, tenemos 3 soluciones posibles: 
• Si r1 y r2 son raíces reales distintas la solución general se da en forma: 
 an = λ1 r1n + λ2 r2n 
• Si r1 y r2 son raíces iguales (r1 = r2) la solución general se da en forma: 
 an = λ1 r1n + λ2 r2n 
• Si r1 y r2 son raíces complejas conjugadas (r1 = a + ib y r2 = a – ib) la 
solución general se da en forma: 
an = ρn (λ1 cos (nθ) + λ2 sen (nθ)) donde: 
ρ = √(a2 + b2) 
tgθ = b/a 
 
Relación de recurrencia lineal, no homogénea y de 
coeficientes constantes: 
1. Se nos da la secuencia an = c1 an-1 + c2 an-2 + … + ck an-k + g(n), g(n) ≠ 0 
2. La solución a esta relación es an = an(h) + an(p) en donde an(h) es la solución 
de recurrencia homogénea asociada: an = c1 an-1 + c2 an-2 + … + ck an-k 
mientras que an(p) es la solución particular 
3. La solución particular an(p) depende de la forma que tome el término 
homogéneo, según la siguiente tabla: 
 
 
 
 
 
 
Unidad 4: Teoría de Grupos 
 
Clasificación de Grupos 
 
Semigrupo: 
Sea S un conjunto NO vacío y * una operación binaria sobre S. Si * es 
asociativo, entonces (S, *) es semigrupo. 
Monoide: 
Sea M un conjunto NO vacío y * una operación binaria sobre M. Si M es 
semigrupo que contiene elemento identidad, entonces (M, *) es monoide. (Es 
decir que debe cumplir propiedad asociativa e identidad) 
Grupo: 
Sea G un conjunto NO vacío y * una operación binaria sobre G. Si (G, *) es un 
monoide cuyos elementos tienen inverso, entonces (G, *) es grupo. 
Orden de grupo: 
El orden delgrupo G se denota como O(G), es decir, la cantidad de elementos 
del conjunto G. 
El orden del elemento a, denotado por O(a), es el menor entero positivo m tal 
que am = e (e es el elemento identidad) si tal elemento no existe, decimos que 
el orden es infinito. 
Propiedades de grupo: 
Sea (G, *) un grupo. Entonces cumple las siguientes propiedades: 
1. (G, *) posee un único elemento identidad 
2. (G, *) posee un único elemento inverso de cada elemento 
3. (G, *) cumple con las leyes de cancelación: a*b = a*c ➔ b = c 
4. (G, *) posee ecuaciones con solución única 
5. (G, *) el único elemento idempotente es el elemento identidad 
 
 
Grupo cíclico: 
Un grupo (G, *) es cíclico si existe un elemento a que elevado a n se pueda 
expresar como x. Si esto ocurre podemos decir que “a” genera G. 
x = an 
Teorema: Si (G, *) es cíclico, entonces: 
1. G es abeliano (Conmutativa) 
2. Si a es generador de G, entonces el inverso de a también lo es 
3. Si G de orden n es finito y a su generador, entonces an = e 
4. Si G de orden n es finito y a su generador, entonces: 
am es generador de G  el MCD de m y n es 1 
Subgrupos: 
Sea (G, *) un grupo y H un subconjunto de G (H ⊂ G) se cumple que: 
1. e ∈ H, donde e es elemento identidad de G 
2. Para todo a, b ∈ H ➔ a * b ∈ H 
3. Para todo a ∈ H ➔ a-1 ∈ 
Los subgrupos (e, *) y (G, *) del grupo (G, *) son llamados subgrupos triviales 
y los demás grupos (si hay) son llamados subgrupos propios 
Teorema: Sea (G, *) un grupo y H un subconjunto no vacío de G (H ⊂ G) 
(H, *) es un subgrupo de (G, *)  a * b-1 ∈ H para todo a, b ∈ H 
Homomorfismo: 
Sean (G, *) y (G’, △) grupos. Una función f : G → G’ es homomorfismo si: 
f (a * b) = f (a) △ f(b) 
1. Si f es inyectiva entonces es monomorfismo de grupos 
2. Si f es sobreyectiva entonces es epimorfismo de grupos 
3. Si f es biyectiva entonces es isomorfismo de grupos 
4. Si G ⊂ G’ entonces f es endomorfismo de grupos 
5. Si G = G’ entonces f es automorfismo de grupos 
Sean (G, *) y (G’, △) grupos. Una función f : G → G’ es homomorfismo si: 
1. f(e) = e’ donde e y e’ son elementos identidad de G y G’ 
2. Para todo elemento a ∈ G, f (a-1) = [f (a)]-1 
3. Si H es subgrupo de G, f (H) = {f (h) : h ∈ H} es subgrupo de G’ 
 
 
Unidad 5: Álgebra de Boole 
 
Características de un Álgebra de Boole 
 
Axiomas necesarios: 
Dado un conjunto B en el que se han definido dos leyes de composición 
interna ⊕ y ⊗. La estructura (B, ⊕, ⊗) es un álgebra de Boole si y solo si 
cumple con los siguientes axiomas necesarios: 
 
 
 
Teoremas fundamentales: 
Si el conjunto cumple con los axiomas necesarios, podemos deducir que el 
álgebra de Boole cumple también con los siguientes teoremas fundamentales: 
 
 
 
Formas normales disyuntivas y conjuntivas booleanas 
 
Minitérminos: 
Un minitérmino de n variables booleanas es un producto booleano de las n 
literales en las cuales cada literal aparece exactamente una vez. 
a b Minitérminos 
1 1 a b 
1 0 a b' 
0 1 a' b 
0 0 a' b' 
Maxitérminos: 
Un maxitérmino de n variables booleanas es una suma booleana de las n 
literales en las cuales cada literal aparece exactamente una vez. 
a b Maxitérminos 
1 1 a' + b' 
1 0 a' + b 
0 1 a + b' 
0 0 a + b 
Forma Normal Disyuntiva (FND): 
Es una función booleana que se expresa como una suma de los minitérminos. 
También se nombra suma de expansión de productos. Si una función 
booleana de n variables se expresa como la suma de todos los 2n 
minitérminos se dice que la función está en FND completa. (Si una función 
está expresada en FND se dice que está en forma canónica) 
Los minitérminos se utilizan para cuando el resultado de la función es igual a 
1, por lo que la FND se construye sumando todos aquellos casos en los que la 
función vale 1. 
Forma Normal Conjuntiva (FNC): 
Es una función booleana que se expresa como un producto de los 
maxitérminos. También se nombra suma de expansión de sumas. Si una 
función booleana de n variables se expresa como el producto de todos los 2n 
maxitérminos se dice que la función está en FNC completa. (Si una función 
está expresada en FNC se dice que está en forma canónica) 
Los maxitérminos se utilizan para cuando el resultado de la función es igual a 
0, por lo que la FNC se construye multiplicando todos aquellos casos en los 
que la función vale. 
 
Unidad 6: Grafos 
 
Grafos 
 
Uso de los grafos: 
Los grafos son gráficas utilizadas para modelar problemas definidos en 
términos de relaciones o conexiones entre objetos. Estas estructuras discretas 
están formadas y se clasifican según sus vértices y aristas. 
Definición formal de grafo: 
Un grafo “G” se denota por un par ordenado de vértices (V) y aristas (E): 
G = (V , E) 
V = {v1, v2, … , vn} conjunto finito y NO vacío de vértices o nodos 
E = {(v1, v2), … , en} conjunto de aristas de pares que pueden ser o no ser 
ordenados 
Conceptos básicos: 
• Si e1 = (v1, v2) es arista, entonces e1 une o conecta a v1 con v2. 
• Los vértices que forman una arista son los extremos de la arista. 
• La arista e1 que conecta los nodos v1 y v2 será incidente en cada nodo. 
• Dos vértices son adyacentes si existe una arista que los une o conecta. 
• Dos aristas son paralelas si conectan al mismo par de vértices. 
• Un vértice que NO sea adyacente a otro es un vértice aislado. 
• Una arista que une un vértice consigo mismo se lo llama lazo. 
• El orden de G es la cantidad de vértices. 
• El tamaño de G es la cantidad de aristas. 
• Cuando cada arista se asocia con un par ordenado de vértices es un 
grafo dirigido. 
 
Grafos no dirigidos 
Características: 
• El grado de un vértice “v”, denotado como grad(v), dg(v), d(v), es el 
número de aristas incidentes en “v”. 
• El grado de un vértice aislado es 0. 
• Si grad(v) = 1 se denomina vértice colgante. 
 
Teorema de Hadshaking: 
Si G = (V , E) es no dirigido con m aristas, entonces: 
ΣvϵV grad(v) = 2m 
Teorema pág. 368 Veerarajan: 
El número de vértices de grado impar en un grafo no dirigido siempre es par. 
 
Grafos dirigidos o digrafos 
 
Concepto: 
Grafo en el que cada arista e1 se asocia con un par ordenado de vértices v1, v2. 
Cada arista (v1, v2) se representa con una flecha o arco con dirección desde un 
punto inicial (v1) a uno terminal (v2). 
Grado interior: 
Es el número de aristas con “v” como su vértice terminal, es decir, es la 
cantidad de aristas que convergen en “v”. Este se denomina grado interior o 
grado interno del vértice “v” y se denota como grad –(v). 
Grado exterior: 
Es el número de aristas con “v” como su vértice inicial, es decir, es la cantidad 
de aristas que emanan de “v”. Este se denomina grado exterior o grado 
externo del vértice “v” y se denota como grad +(v). 
Fuente: 
Vértice con grado interior igual a 0. 
Sumidero: 
Vértice con grado exterior igual a 0. 
Aristas distintas: 
Si las aristas son dirigidas y de dirección opuesta se consideran distintas. 
Teorema de digrafos: 
Si G = (V , E) es grafo dirigido con m aristas, entonces: 
ΣvϵV grad –(v) = ΣvϵV grad +(v) = m 
 
Clases de grafos 
 
Grafo simple: 
Hay una única arista entre los pares de vértices, es decir, no presenta lazos ni 
aristas paralelas 
Multigrafo: 
Grafo que contiene aristas paralelas. 
Pseudografo: 
Contiene lazos y aristas paralelas. 
Grafo ponderado: 
Se asigna un valor numérico a cada arista. 
Grafo trivial: 
Solo posee un único vértice. 
Grafo nulo: 
Solo contiene nodos aislados. 
 
Representación matricial de grafos no dirigidos 
 
Matriz de incidencia: 
Sea G un grafo simple con n vértices y m aristas, la matriz se define por: 
Columnas = mE 
Filas = nV 
• Si mjk = 1, si ek incide en vj 
• Si mjk = 0, otro caso. 
Propiedades básicas de la matriz de incidencia: 
• Cada columna tiene exactamente 2 entradas unitarias. 
• Dado un lazo, la columna tendrá una única entrada 1. 
• Una fila con todas entradas iguales a 0 es un vértice aislado. 
• Una fila con unasola entrada igual a 1 es un vértice colgante. 
• La cantidad de entradas iguales a 1 en una fila es el grado del vértice. 
 
Matriz de adyacencia: 
Sea G un grafo simple con n vértices, la matriz se define por: 
Columnas = nV 
Filas = nV 
ajk = 1, si hay un ejk en V 
ajk = 0, si no hay un e que conecte 
Propiedades básicas de la matriz de adyacencia: 
• En grafos sin lazos, la diagonal de la matriz será 0. 
• En grafos no dirigidos la matriz será simétrica. 
• La entrada de cada fila o columna que sea 1 es igual al grado del 
vértice. 
 
Representación matricial de digrafos 
 
Matriz de incidencia: 
Sea G = (V , E) un digrafo con n vértices y m aristas, la matriz se define por: 
Columnas = mE 
Filas = nV 
mjk = 1, si vj es el extremo inicial de ek 
mjk = –1, si vj es el extremo final de ek 
mjk = 0, otro caso 
Matriz de adyacencia: 
Sea G = (V , E) un digrafo con n vértices y m aristas, la matriz se define por: 
Columnas = nV 
Filas = nV 
ajk = 1, si hay un e entre los v 
ajk = 0, otro caso 
 
 
Comparación de grafos 
 
Subgrafo: 
• Un grafo H=(V’, E’) se denomina subgrafo de G=(V, E) si V’ ⊆ V y E’ ⊆ E 
• Si V’ ⊂ V y E’ ⊂ E, entonces H se llama subgrafo propio de G 
• Cuando V’=V, H se conoce como subgrafo expandido de G (No necesita 
todas las aristas) 
• Los subgrafos se obtienen eliminando ciertos vértices y aristas de G 
- La remoción de una arista NO se relaciona con la remoción de sus 
vértices adyacentes 
- La remoción de un vértice se relaciona con la remoción de cualquier 
arista que incida en él 
• Si se elimina un subconjunto U de V y todas las aristas incidentes de U, 
entonces el subgrafo (H=(V–U, E’) se llama subgrafo de vértices 
eliminados de G 
• Si se elimina un subconjunto F de E, entonces el subgrafo (H=V’, E–F)) 
se llama subgrafo de aristas eliminadas de G 
• Dado T un árbol, el subgrafo en cierto vértice W y todos sus 
descendientes con W como raíz, es llamado subárbol de T con raíz W 
Grafos isomorfos: 
• Dos grafos son isomórficos entre sí cuando existe una correspondencia 
uno a uno entre los conjuntos de vértices que preservan la adyacencia 
de estos últimos 
• Un grafo G1=(V1, E1) es isomorfo a G2=(V2, E2) si existe una función 
biyectiva φ : V1 → V2 tal que: 
 
U V ∈ E1  φ (U) φ(V) ∈ E2 
• Cuando tenemos isomorfismo se representa con G1≈G2 
• Se debe tener correspondencia uno a uno entre V1 y V2 | E1 y E2 
• Si en G1 e1={U1, V1} entonces su arista correspondiente G2 e2={U2, V2} y 
U2 y V2 se corresponden con U1 y V1 respectivamente 
• Invariante: Condiciones necesarias para isomorfismo entre 2 grafos: 
- Mismo número de vértices (Orden) 
- Mismo número de aristas (Tamaño) 
- Vértices correspondientes con igual grado 
• Invariante adicional: Si G1≈G2, ambos grafos contendrán ciclos de igual 
longitud mayores a 2 
• Si cualquier condición anterior NO se cumple, G1 y G2 NO son 
isomórficos entre sí 
 
Trayectoria, ciclos y conectividad 
 
Trayectoria: 
• Una trayectoria es una secuencia alternada finita de vértices y aristas 
- La trayectoria empieza y termina en un vértice 
- Cada arista es incidente en los vértices que la preceden o siguen 
• Trayectoria simple: todas las aristas son distintas 
• Longitud de la trayectoria: número de aristas de la trayectoria 
Si n es la cantidad de vértices de la trayectoria, n–1 es el número de aristas 
Ciclo: 
• Un ciclo es una trayectoria cuyos vértices inicial y final coinciden 
- Únicamente se da si la trayectoria ≠ 0 
• Ciclo simple: está sobre una trayectoria simple, NO se repiten aristas 
• Acíclico: grafo sin ciclos 
Conectividad: 
• Un grafo es conexo cuando existe una trayectoria entre cada par de 
vértices 
- No posee vértices aislados 
• Un grafo no conexo se lo denomina grafo desconectado, disconexo o 
inconexo 
• Cada subgrafo independiente se denomina componente conectado del 
grafo 
 
 
 
Grafos especiales 
 
Grafo completo: 
Es un grafo simple con una arista entre cada par de vértices distintos 
Grafo regular: 
Es un grafo simple en el que sus vértices tienen el mismo grado 
Grafo bipartito: 
Es un grafo cuyo conjunto V puede ser partido en 2 subconjuntos ajenos X e Y, 
tal que cualquier arista tiene un extremo X e Y 
• Un grafo es bipartito si y solo si no contiene ciclos de longitud impar 
• Si cada vértice de X se conecta con cada vértice de Y mediante una 
arista, entonces G se denomina grafo completamente bipartito 
• Si X contiene mV e Y contiene nV, el grafo complemento bipartito se 
denota X m, n 
Grafo euleriano: 
• Trayectoria euleriana: trayectoria que incluye cada arista una única vez 
• Ciclo euleriano: ciclo que incluye cada arista una única vez 
• Grafo euleriano: grafo que contiene un ciclo euleriano 
• Un grafo conexo contiene un ciclo euleriano si y solo si cada uno de sus 
vértices es de grado par 
• Un grafo conexo contiene una trayectoria euleriana si y solo si tiene 
exactamente 2 vértices de grado impar 
- Los vértices de grado impar son los puntos extremos 
Grafo hamiltoniano 
• Trayectoria hamiltoniana: trayectoria que incluye cada vértice una 
única vez 
• Ciclo hamiltoniano: ciclo que incluye cada vértice una única vez 
- En este caso se excepciona el vértice inicial y final 
• Grafo hamiltoniano: grafo que contiene un ciclo hamiltoniano 
• La trayectoria que se obtiene al eliminar cualquier arista de un circuito 
hamiltoniano es una trayectoria hamiltoniana 
• Un circuito hamiltoniano contiene una trayectoria hamiltoniana 
• Un grafo que contiene una trayectoria hamiltoniana NO 
necesariamente tiene un circuito hamiltoniano 
• Un grafo completo siempre tendrá ciclo hamiltoniano cuando n ≥ 3 
 
Grafo aplanable: 
Cuando G puede dibujarse en el plano de tal forma que las aristas no se 
crucen entre sí, se dice que es un grafo aplanable. Tal dibujo es llamado encaje 
de G en plano 
 
Grafos de árbol 
 
Árbol: 
• Grafo conexo acíclico 
• Es un grafo simple 
• Un grafo no dirigido es árbol si y solo si hay una trayectoria simple 
única entre cada par de vértices 
• Un árbol con n vértices, tiene n–1 aristas 
• Cualquier grafo conexo acíclico con n vértices y n–1 aristas es árbol 
Árbol con raíz: 
• Un árbol con un vértice en particular que se designa como raíz 
• Altura, nivel o profundidad: es la longitud de la trayectoria desde la raíz 
a V 
- La raíz siempre está en el nivel 0 (es decir que no se cuenta) 
• Descendientes de V: todo vértice alcanzable desde V 
- V es ancestro de sus descendientes 
• Hijos de V: son los descendientes a través de una arista simple 
(descendiente directo) 
• Vértice terminal o colgante: vértice sin descendientes 
• Todo vértice no terminal es un vértice interno 
Árbol binario 
• Un árbol con raíz en el que cada vértice tiene como máximo 2 
descendientes excepto los terminales 
• Árbol binario completo: todos los vértices poseen exactamente 2 
descendientes excepto los terminales 
- La raíz es de grado 2 
• El número de vértices del árbol binario completo es impar y el número 
de vértices terminales es (n+1)/2 o 2n–1 
• La altura mínima de un árbol binario de n vértices es igual a: 
[log2(n+1)–1] 
- Donde [X] denota el entero mayor o igual a X 
 
Árbol n-ario: 
• Se sustituya la n (cuyo valor en los binarios es 2) por cualquier otro 
número 
Recorridos: 
• El recorrido de un árbol es un proceso que permite desplazarse de 
manera sistemática y visitar cada vértice una única vez. Estos 
recorridos pueden hacerse en preorden, inorden o posorden 
Preorden: 
1. Visitar la raíz 
2. Recorrer en preorden por la rama izquierda 
3. Recorrer en preorden por la rama derecha 
Inorden: 
1. Recorrer en inorden por la rama izquierda 
2. Visitar la raíz 
3. Recorrer en inorden por la rama derecha 
Posorden: 
1. Recorrer en posorden por la rama izquierda 
2. Recorrer en posorden por la rama derecha 
3. Visitar la raíz 
 
 
Unidad 7 (Extra): Teoría de Conjuntos 
 
Conjuntos 
 
Conceptosbásicos: 
Un conjunto es una colección de objetos bien definidos. Los objetos que 
formen los conjuntos se los denomina elementos. 
Los conjuntos se simbolizan con mayúsculas (A, B, C…) mientras que los 
elementos se simbolizan con minúsculas (a, b, c…). 
Cuando un elemento x pertenece a un conjunto A se dice que x ∈ A. Si el 
elemento y no perteneciera al conjunto A se dice que y ∉ A. 
Ejemplo de conjuntos: 
• Conjunto L formado por las letras de mi nombre: L = {a, d, e, l, n, o, r} 
• Conjunto D formado por el número 2906: D = {2, 9, 0, 6} 
• Conjunto de raíces del polinomio p(x) = (x+3)(x+2): S = {–3, –2} || x ∈ 
R : p(x)=0 
• Conjunto M de los múltiplos de 5: M = {…, –15, –10, -5, 0, 5, 10, 15, …} 
Los conjuntos en azul están representados por extensión, es decir, listando a 
todos los elementos del conjunto. 
Los conjuntos en verde están representados por comprensión, es decir, una 
propiedad que engloba todos los elementos del conjunto. 
El conjunto M en color rojo, si bien no es ni extensión ni comprensión pero su 
representación es de gran utilidad para entender el conjunto. 
El conjunto unitario o Singleton es un conjunto formado por un elemento, 
como por ejemplo: L = {1} o bien puede ser S = {x ∈ R : (x – 3) = 0} 
Un conjunto puede ser finito o infinito, dependiendo si la cantidad de 
elementos es limitada o no. Si X es un conjunto finito entonces lo llamaremos 
cardinal y será denotado como |X| o #X. 
Por ejemplo: 
• L = {a, d, e, l, n, o, r} es finito y |L| = 7 
• Ø es finito y |Ø| = 0 
• S = {x ∈ R : (x – 3) = 0} es finito y |S| = 1 
• M = {…, –15, –10, -5, 0, 5, 10, 15, …} NO es finito 
 
Subconjuntos e Igualdad: 
Escribimos A ⊂ B para indicar que A es subconjunto de B, es decir, para todo x 
se cumple que x ∈ A implica que x ∈ B. 
Dos conjuntos X e Y son iguales si y solo si X ⊂ Y e Y ⊂ X. 
*dato* También puede darse el caso de que X ⊂ Y pero que X ≠ Y 
Propiedades: 
• Ø ⊂ A para todo conjunto A. 
• A ⊂ A para todo A. 
• Si A ⊂ B y B ⊂ C entonces A ⊂ C 
Conjunto de partes: 
Dado un conjunto X cualquiera se puede considerar un nuevo conjunto donde 
sus elementos son los subconjuntos de X, este se denomina conjunto de 
partes de X o conjunto potencia de X y es denotado por P(X) o 2X. 
P(X) = {A : A ⊂ X} 
Ejemplos: 
• Si X = Ø, entonces… P(Ø) = { Ø } donde |P(Ø)| = 20 = 1 
• Si X = {1, 2, 3} entonces… P(X) = {Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, X}
 donde |P({1, 2, 3})| = 2|{1, 2, 3}| = 23 = 16 
Teorema: 
Si un conjunto X tiene n elementos, entonces el conjunto de partes P(X) tiene 
2n elementos 
|X| = n → |P(X)| = 2n 
 
 
Operaciones con Conjuntos 
 
Unión e intersección: 
La unión de A y B es el conjunto de elementos que pertenecen a A o a B (o a 
ambos) y se denota por medio de A ∪ B. 
A ∪ B := {x : x ∈ A ∨ x ∈ B} 
La intersección de A y B es el conjunto de elementos que pertenecen tanto a A 
como a B (es decir, los elementos que comparten) y se denota por medio de A 
∩ B. 
A ∩ B := {x : x ∈ A ∧ x ∈ B} 
Complemento, Diferencia y Diferencia Simétrica: 
El complemento de A dentro del universo U, denota por medio de A’ o Ac es el 
conjunto de elementos que pertenece a U pero no a A. 
A’ := {x : x ∈ U ∧ x ∉ A} 
La diferencia entre el conjunto A y B es el conjunto de elementos que 
pertenece a A pero no a B y se denota como A – B. 
A – B := {x : x ∈ A ∧ x ∉ B} 
La diferencia simétrica entre el conjunto A y B es el conjunto de elementos 
que pertenecen a A pero no a B y se denota como A △ B o A ⊕ B. 
A ⊕ B := (A ∪ B) – (A ∩ B) 
Propiedades base: 
1. Leyes de identidad: 
o A ∪ Ø = A 
o A ∩ U = A 
 
2. Leyes de dominación 
o A ∪ U = U 
o A ∩ Ø = Ø 
 
3. Leyes de idempotencia 
o A ∪ A = A 
o A ∩ A = A 
 
4. Leyes de inversos o Leyes de complementos 
o A ∪ A’ = U 
o A ∩ A’ = Ø 
 
5. Ley de doble complemento o Ley de involución 
o A’’ = A 
 
Propiedades: 
Sean A, B, C subconjuntos de un conjunto universal U. Entonces: 
1. Leyes conmutativas 
o A ∪ B = B ∪ A 
o A ∩ B = B ∩ A 
 
2. Leyes asociativas 
o A ∪ (B ∪ C) = (A ∪ B) ∪ C 
o A ∩ (B ∩ C) = (B ∩ A) ∩ C 
 
3. Leyes distributivas 
o A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 
o A ∪ (B ∩ C) = (B ∪ A) ∩ (A ∪ C) 
 
4. Leyes de absorción 
o A ∪ (A ∩ B) = A 
o A ∩ (A ∪ B) = A 
 
5. Leyes de De Morgan 
o (A ∪ B)’ = A’ ∩ B’ 
o (A ∩ B)’ = A’ ∪ B’ 
 
Pares Ordenados y Producto Cartesiano 
 
Par ordenado: 
Sean a y b elementos, los objetos de la forma (a, b) se denomina pares 
ordenados. Dados dos pares ordenados (a, b) y (c, d) decimos que son iguales 
si a = c y b = d 
Observación: 
En los conjuntos NO importa el orden de los elementos: {a, b} = {b, a} 
En los pares ordenados SI importa el orden de los elementos: (a, b) ≠ (b, a) 
Producto Cartesiano: 
El producto cartesiano de A por B se denota como A × B. 
A × B := {(x, y) : x ∈ A ∧ y ∈ B} 
 
 
 
Operaciones 
 
Operaciones unarias: 
Si A es un conjunto no vacío y f : A → A es una función, entonces f es 
operación unaria en A. 
Observación: 
Se denota mediante símbolos como ‘, ¬, °, c, etc., que utiliza dos elementos 
para operar. 
Ejemplos: 
• El valor absoluto en el conjunto de numero reales: operación unaria 
• El complemento de un conjunto dado cierto universo: operación unaria 
• La negación de una proposición: operación unaria 
Operaciones binarias: 
Si A es un conjunto no vacío y f : A × A → A es una función, entonces f es 
operación binaria en A. 
 
 
Observación: 
Se denota mediante símbolos como +, –, *, /, etc., que utiliza dos elementos 
para operar. 
Ejemplos: 
La suma de conjuntos de números enteros positivos: operación binaria 
La multiplicación entre números racionales: operación binaria 
El producto cruz o vectorial en R3: operación binaria 
La resta entre números naturales: NO ES operación binaria ya que 1 – 2 = –1 
El producto escalar en R3: NO ES operación binaria ya que el resultado es un 
número en otro conjunto. 
Observación: 
Las operaciones binarias son operaciones cerradas, debido a que caen en el 
mismo conjunto en el que se está trabajando. 
Propiedades: 
Sea A un conjunto y * una operación binaria sobre A, entonces: 
* es asociativa si para todo para a, b, c en A. 
(a * b) * c = a * (b * c) 
Ejemplos: 
La suma entre números reales: Asociativa 
La multiplicación entre matrices 2x2: Asociativa 
* es conmutativa si para todo a, b en A 
a * b = b * a 
Ejemplos: 
La multiplicación en el conjunto de los reales: conmutativa 
La suma de matrices 2x2: conmutativa 
La multiplicación de matrices 2x2: NO ES conmutativa 
Se dice que e ∈ A es un elemento neutro de A si para todo a en A 
e * a = a = a * e 
 
 
Ejemplos: 
La multiplicación en el conjunto de los naturales: Posee elemento neutro (1) 
La suma números naturales: Posee elemento neutro (0) 
La multiplicación de matrices 2x2: Posee elemento neutro (matriz identidad 
2x2) 
La resta de números reales: NO POSEE elemento neutro 
 
Suponiendo que existe e ∈ A elemento neutro, como se definió antes para a ∈ 
A. Se dice que b es su elemento inverso si: 
a * b = e = b * a Se dice que a es invertible en b y se lo denota como a-1 
Ejemplos: 
El 2 ∈ Q con respecto a la multiplicación: invertible (1/2) 
El –3 ∈ Z con respecto a la suma: invertible (3) 
La matriz [{1, 2}, {0, 3}] respecto a la multiplicación: Invertible (1/3 [{3, -2}, 
{0, 1}] 
Sean A un conjunto, ⊕ y ⊗ operaciones binarias sobre A entonces se dice que 
⊕ es distributiva respecto de ⊗ si para todo a, b, c en A 
(a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c) 
Ejemplos: 
La multiplicación es distributiva con respecto de la suma en el conjunto de 
números reales 
 
Relaciones 
 
Relación: 
Sean A y B conjuntos. Un subconjunto R de A x B se denomina relación binaria 
entre A y B. Es decir, R es binaria sí. 
R ⊂ A x B 
Si (a, b) ∈ R decimos que a está relacionado con b por medio de R y se escribe 
a R b o a ~ b. 
Si A = B decimos que R es relación binaria sobre A.Dominio e Imagen: 
Dom (R) := {a ∈ A : existe b ∈ B / (a, b) ∈ R} 
Im (R) := {b ∈ B : existe a ∈ B / (a, b) ∈ R} Im (R) ⊂ B 
Tipos de relaciones, operaciones y clasificaciones: 
• Relación Vacía: Ø ⊂ A x B No tiene ningún par ordenado 
• Relación Identidad: idAxA = {(a, a) : a ∈ A} Ej.: idAxA = {(1, 1), (2, 2), 
(3, 3)} 
• Relación Universal: A x B ⊂ A x B los pares ordenados están todos 
incluidos A x B 
Operación inversa: Sea R ⊂ A x B una relación de A en B. R-1 es una relación de 
B en A. 
R-1 := {(b, a) ∈ B x A : (a, b) ∈ R} (SIEMPRE EXISTE RELACIÓN 
INVERSA) 
Operación compuesta: Sea R ⊂ A x B una relación de A en B y S ⊂ B x C una 
relación de B en C. La relación compuesta S ° R ⊂ A x C es una relación de A en 
C. 
S ° R := {(a, c) ∈ A x C : existe un b ∈ B / (a, b) ∈ R y (b, c) ∈ S} 
(En A x A) 
• Reflexiva: Si para todo x ∈ A se cumple que (x, x) ∈ R 
• Simétrica: Si para todo x ∈ A se cumple que (x, y) ∈ R → (y, x) ∈ R 
• Antisimétrica: Si para todo x, y ∈ A se cumple que (x, y) ∈ R y (y, x) ∈ R 
→ x = y 
• Transitiva: Si para todo x, y, z ∈ A se cumple que (x, y) ∈ R y (y, z) ∈ R 
→ (x, y) = R 
• Equivalencia: Si R es reflexiva, simétrica y transitiva. 
• Orden parcial: Si R es reflexiva, antisimétrica y transitiva. 
 
 
	Unidad 1: Lógica�
	Proposición�
	Definición:�
	Excepciones:�
	Proposición compuesta:�
	Implicaciones asociadas:�
	Tautología, contradicción y contingencia:�
	Relaciones lógicas:�
	Equivalencias lógicas:�
	Proposiciones generales y cuantificadores lógicos:�
	Demostraciones�
	Demostración directa:�
	Demostración indirecta:�
	Demostración por reducción al absurdo:�
	Demostración por contraejemplo:�
	Demostración por inducción:�
	Unidad 2: Teoría de Números�
	Divisibilidad�
	Divisores:�
	Teoremas Divisores:�
	Números Primos:�
	Observaciones números primos:�
	Teoremas números primos:�
	Máximo Común Divisor y Mínimo Común Múltiplo�
	Máximo común divisor:�
	Teorema MCD:�
	Propiedades MCD:�
	Mínimo común múltiplo:�
	Teorema mcm:�
	Cambio de Base�
	Cambio de base general:�
	Teoremas:�
	Ecuaciones Diofánticas�
	Ecuaciones diofánticas:�
	Teoremas ecuaciones diofánticas:�
	Congruencia Lineal�
	Congruencia lineal:�
	Teoremas congruencia lineal:�
	Unidad 3: Recurrencia�
	Sucesión:�
	Sucesión de números reales:�
	Sucesión recurrente:�
	Solución de la relación recurrente:�
	Relación de recurrencia lineal constante de grado�
	Definición:�
	Linealidad:�
	Grado:�
	Homogeneidad:�
	Coeficientes constantes:�
	Ejemplos:�
	Solución de las relaciones de recurrencia homogéneas�
	Relación de recurrencia lineal, homogénea de grado 1:�
	Relación de recurrencia lineal, homogénea de grado 2:�
	Relación de recurrencia lineal, no homogénea y de coeficientes constantes:�
	Unidad 4: Teoría de Grupos�
	Clasificación de Grupos�
	Semigrupo:�
	Monoide:�
	Grupo:�
	Orden de grupo:�
	Propiedades de grupo:�
	Grupo cíclico:�
	Subgrupos:�
	Homomorfismo:�
	Unidad 5: Álgebra de Boole�
	Características de un Álgebra de Boole�
	Axiomas necesarios:�
	Teoremas fundamentales:�
	Formas normales disyuntivas y conjuntivas booleanas�
	Minitérminos:�
	Maxitérminos:�
	Forma Normal Disyuntiva (FND):�
	Forma Normal Conjuntiva (FNC):�
	Unidad 6: Grafos�
	Grafos�
	Uso de los grafos:�
	Definición formal de grafo:�
	Conceptos básicos:�
	Grafos no dirigidos�
	Características:�
	Teorema de Hadshaking:�
	Teorema pág. 368 Veerarajan:�
	Grafos dirigidos o digrafos�
	Concepto:�
	Grado interior:�
	Grado exterior:�
	Fuente:�
	Sumidero:�
	Aristas distintas:�
	Teorema de digrafos:�
	Clases de grafos�
	Grafo simple:�
	Multigrafo:�
	Pseudografo:�
	Grafo ponderado:�
	Grafo trivial:�
	Grafo nulo:�
	Representación matricial de grafos no dirigidos�
	Matriz de incidencia:�
	Propiedades básicas de la matriz de incidencia:�
	Matriz de adyacencia:�
	Propiedades básicas de la matriz de adyacencia:�
	Representación matricial de digrafos�
	Matriz de incidencia:�
	Matriz de adyacencia:�
	Comparación de grafos�
	Subgrafo:�
	Grafos isomorfos:�
	Trayectoria, ciclos y conectividad�
	Trayectoria:�
	Ciclo:�
	Conectividad:�
	Grafos especiales�
	Grafo completo:�
	Grafo regular:�
	Grafo bipartito:�
	Grafo euleriano:�
	Grafo hamiltoniano�
	Grafo aplanable:�
	Grafos de árbol�
	Árbol:�
	Árbol con raíz:�
	Árbol binario�
	Árbol n-ario:�
	Recorridos:�
	Preorden:�
	Inorden:�
	Posorden:�
	Unidad 7 (Extra): Teoría de Conjuntos�
	Conjuntos�
	Conceptos básicos:�
	Ejemplo de conjuntos:�
	Subconjuntos e Igualdad:�
	Propiedades:�
	Conjunto de partes:�
	Ejemplos:�
	Teorema:�
	Operaciones con Conjuntos�
	Unión e intersección:�
	Complemento, Diferencia y Diferencia Simétrica:�
	Propiedades base:�
	Propiedades:�
	Pares Ordenados y Producto Cartesiano�
	Par ordenado:�
	Producto Cartesiano:�
	Operaciones�
	Operaciones unarias:�
	Observación:�
	Operaciones binarias:�
	Observación:�
	Observación:�
	Relaciones�
	Relación:�
	Dominio e Imagen:�
	Tipos de relaciones, operaciones y clasificaciones:�