Matemáticas Discretas

Introducción
Las Matemáticas Discretas son una rama fundamental de las matemáticas que se ocupa de elementos que
pueden ser contados, separados o discretos, en contraste con las matemáticas continuas que tratan con valores
que varían suavemente. Esta disciplina es la columna vertebral de la informática, la ingeniería de software, la
inteligencia artificial y muchas otras áreas tecnológicas. Proporciona las herramientas lógicas y algorítmicas
necesarias para comprender cómo funcionan las computadoras, cómo se estructuran los datos y cómo se
resuelven problemas complejos de manera eficiente.

En este documento, exploraremos los pilares de las Matemáticas Discretas, comenzando con la lógica
proposicional y la teoría de conjuntos, que son la base del razonamiento computacional y la organización de la
información. Luego, nos adentraremos en las funciones y relaciones, que son esenciales para modelar
interacciones y transformaciones en sistemas. La teoría de números y las técnicas de conteo nos equiparán con
métodos para resolver problemas de enumeración y comprender las propiedades de los enteros, cruciales en
criptografía y análisis de algoritmos. Posteriormente, abordaremos las relaciones de recurrencia y el análisis de
algoritmos, que nos permitirán evaluar la eficiencia de los programas y entender cómo se comportan a medida
que los datos de entrada crecen. Finalmente, exploraremos la teoría de grafos y árboles, herramientas poderosas
para modelar redes y conexiones, y cerraremos con los lenguajes formales y autómatas, la base teórica de los
compiladores y la computación.

Para aprovechar al máximo este material, es recomendable tener conocimientos básicos de álgebra
(manipulación de ecuaciones, resolución de ecuaciones cuadráticas) y una comprensión elemental de la lógica
de programación (variables, condicionales, bucles). Sin embargo, el enfoque paso a paso y los ejemplos
detallados están diseñados para guiar al lector a través de cada concepto, construyendo una comprensión sólida
desde cero.

Unidad 1: Conjunto, lógica, demostraciones y circuitos combinatorios

Esta unidad establece las bases del razonamiento matemático y la lógica, que son esenciales para la
programación y la informática.

1.1. Proposiciones, conectivos lógicos, tablas de verdad, propiedades y circuitos combinatorios

 Proposiciones: Son oraciones declarativas que pueden ser verdaderas (V) o falsas (F), pero no ambas al
mismo tiempo.
o Ejemplo: "El sol es una estrella." (V) o "2 + 2 = 5." (F).
 Conectivos Lógicos: Son símbolos que unen proposiciones para formar proposiciones compuestas.
o neg (Negación): "no p".
o land (Conjunción): "p y q".
o lor (Disyunción): "p o q".
o to (Condicional): "Si p, entonces q".
o leftrightarrow (Bicondicional): "p si y solo si q".
 Tablas de Verdad: Muestran el valor de verdad de una proposición compuesta para todas las
combinaciones posibles de los valores de verdad de las proposiciones simples.
 Circuitos Combinatorios: Son representaciones visuales de expresiones lógicas utilizando compuertas
(AND, OR, NOT).
Ejemplo Resuelto: Tabla de verdad para (plandnegq)top¡Error! Nombre de archivo no especificado.

Paso 1: Identificar las proposiciones simples (p, q) y los conectivos. Paso 2: Crear las columnas para p, q y las
operaciones intermedias (negq, plandnegq). Paso 3: Rellenar la tabla.

negq¡Error! Nombre de archivo plandnegq¡Error! Nombre de (plandnegq)top¡Error! Nombre de

pq
no especificado. archivo no especificado. archivo no especificado.
VVF F V
VF V V V
F VF F V
F FV F V

 Observación: La última columna siempre es verdadera, por lo que la expresión es una tautología.

Ejercicios Propuestos:

1. Construye la tabla de verdad para la expresión: (plorq)to(plandq).

2. Dibuja el circuito lógico para la expresión: (plandq)lornegr.

1.2. Proposiciones condicionales y equivalencia lógica

 Proposiciones Condicionales: La expresión ptoq tiene tres formas relacionadas:

o Inversa: negptonegq¡Error! Nombre de archivo no especificado.
o Recíproca: qtop¡Error! Nombre de archivo no especificado.
o Contrapositiva: negqtonegp¡Error! Nombre de archivo no especificado.
o Importante: La proposición original es lógicamente equivalente a su contrapositiva.
 Equivalencia Lógica: Dos proposiciones compuestas son lógicamente equivalentes si tienen la misma
tabla de verdad. Se denota con el símbolo equiv.
o Leyes de De Morgan: neg(plandq)equivnegplornegq y neg(plorq)equivnegplandnegq.

Ejemplo Resuelto: Mostrar que neg(ptoq) es lógicamente equivalente a plandnegq.

ptoq¡Error! Nombre de neg(ptoq)¡Error! Nombre negq¡Error! Nombre de plandnegq¡Error! Nombre

pq
archivo no especificado. de archivo no especificado. archivo no especificado. de archivo no especificado.
VVV F F F
VFF V V V
F VV F F F
F FV F V F

 Solución: Las columnas de neg(ptoq) y plandnegq son idénticas, por lo que son lógicamente
equivalentes.

Ejercicios Propuestos:

1. Demuestra si la recíproca de una proposición condicional es lógicamente equivalente a su inversa.

2. Simplifica la expresión neg(plornegq)lor(negplandq) usando las leyes de equivalencia lógica.

1.3. Demostraciones por métodos directo, indirecto, resolución e inducción matemática

  Demostración Directa: Se parte de las premisas (hipótesis) y se utilizan reglas de inferencia y
propiedades lógicas para llegar directamente a la conclusión.
o Paso 1: Asumir que la hipótesis es verdadera.
o Paso 2: Usar definiciones, axiomas y teoremas previamente demostrados para construir una
cadena lógica que lleve a la conclusión.
 Demostración Indirecta (por Contradicción): Se asume que la conclusión es falsa y se demuestra que
esta suposición lleva a una contradicción con las premisas o con una verdad conocida.
o Paso 1: Asumir que la hipótesis es verdadera y que la conclusión es falsa.
o Paso 2: Derivar una contradicción.
o Paso 3: Concluir que la suposición inicial (la conclusión es falsa) debe ser incorrecta, por lo
tanto, la conclusión original es verdadera.
 Resolución: Un método de inferencia para la lógica proposicional (y de primer orden) que se utiliza
para determinar la satisfacibilidad de un conjunto de cláusulas. Se basa en el principio de resolución.
o Paso 1: Convertir las proposiciones a forma normal conjuntiva (FNC).
o Paso 2: Aplicar la regla de resolución repetidamente hasta derivar una cláusula vacía
(contradicción) o hasta que no se puedan aplicar más reglas.
 Inducción Matemática: Un método para probar que una propiedad es verdadera para todos los números
naturales.
o Paso 1 (Caso Base): Demostrar que la propiedad es verdadera para el primer número natural
(generalmente n=0 o n=1).
o Paso 2 (Paso Inductivo): Asumir que la propiedad es verdadera para un entero arbitrario k
(hipótesis de inducción) y demostrar que es verdadera para k+1.

Ejemplo Resuelto: Demostrar por inducción que la suma de los primeros n enteros impares es n2. La
propiedad es P(n):1+3+5+dots+(2n−1)=n2.

 Paso 1 (Caso Base n=1): P(1):1=12, lo cual es verdadero.

 Paso 2 (Paso Inductivo):
o Hipótesis de Inducción: Asumir que P(k) es verdadero para algún entero positivo k. Es decir,
1+3+5+dots+(2k−1)=k2.
o Demostrar P(k+1): Queremos demostrar que 1+3+5+dots+(2k−1)+(2(k+1)−1)=(k+1)2.
o Partimos del lado izquierdo de P(k+1): [1+3+5+dots+(2k−1)]+(2(k+1)−1)¡Error! Nombre de
archivo no especificado.
o Por la hipótesis de inducción, la parte entre corchetes es k2: k2+(2k+2−1) k2+2k+1¡Error!
Nombre de archivo no especificado.
o Esto es un trinomio cuadrado perfecto: (k+1)2¡Error! Nombre de archivo no especificado.
o Hemos demostrado que P(k+1) es verdadero.
 Conclusión: Por el principio de inducción matemática, la propiedad es verdadera para todos los enteros
positivos n.

Ejercicios Propuestos:

1. Demuestra por inducción matemática que la suma de los primeros n enteros pares positivos es n(n+1).
Es decir, 2+4+6+dots+2n=n(n+1).
2. Demuestra por contradicción que si n2 es par, entonces n es par.

1.4. Conjunto, subconjunto, producto cartesiano, conjunto potencia, cardinalidad y

operaciones

 Conjunto: Una colección bien definida de objetos distintos.

o Ejemplo: A=1,2,3.
  Subconjunto: Un conjunto A es un subconjunto de B (AsubseteqB) si todo elemento de A también es
un elemento de B.
 Producto Cartesiano: El conjunto de todos los pares ordenados (a,b) donde a es un elemento del primer
conjunto y b es un elemento del segundo conjunto. AtimesB=(a,b)midainAlandbinB.
 Conjunto Potencia: El conjunto de todos los subconjuntos de un conjunto dado, incluyendo el conjunto

Cardinalidad: El número de elementos en un conjunto. Se denota por ∣A∣.

vacío y el conjunto mismo. Se denota por P(A) o 2A.

 Operaciones con Conjuntos:
o Unión (AcupB): Elementos que están en A o en B (o en ambos).
o Intersección (AcapB): Elementos que están en A y en B.
o Diferencia (A−B): Elementos que están en A pero no en B.
o Complemento (barA o Ac): Elementos que no están en A (respecto a un universo dado).

Ejemplo Resuelto: Conjunto Potencia Encuentra el conjunto potencia de A=a,b.

Paso 1: Listar todos los subconjuntos posibles.

 El conjunto vacío: emptyset¡Error! Nombre de archivo no especificado.

 Los subconjuntos con un elemento: a, b¡Error! Nombre de archivo no especificado.
 Los subconjuntos con dos elementos: a,b¡Error! Nombre de archivo no especificado.

Paso 2: Formar el conjunto con todos estos subconjuntos. P(A)=emptyset,a,b,a,b.

 Cardinalidad: ∣A∣=2, ∣P(A)∣=2∣A∣=22=4.

Ejercicios Propuestos:

1. Sean A=1,2 y B=a,b. Encuentra el producto cartesiano AtimesB.

2. Sean U=1,2,3,4,5, A=1,3,5 y B=2,3,4. Encuentra AcupB, AcapB, A−B y barA.

Unidad 2: Funciones, sucesiones y relaciones

Esta unidad introduce conceptos fundamentales que se usan para modelar estructuras de datos y algoritmos.

2.1. Funciones inyectiva, sobreyectiva, composición de funciones e inversa

 Función: Una regla que asigna a cada elemento de un conjunto (dominio) exactamente un elemento de
otro conjunto (codominio).
 Inyectiva (uno a uno): Una función f:AtoB es inyectiva si cada elemento del codominio tiene como
máximo una preimagen en el dominio. Es decir, si f(x_1)=f(x_2), entonces x_1=x_2.
 Sobreyectiva (sobre): Una función f:AtoB es sobreyectiva si cada elemento del codominio es la imagen
de al menos un elemento del dominio. Es decir, para todo yinB, existe un xinA tal que f(x)=y.
 Biyectiva: Una función que es tanto inyectiva como sobreyectiva. Solo las funciones biyectivas tienen
una función inversa.
 Composición de Funciones: La aplicación de una función al resultado de otra función. Si f:AtoB y
g:BtoC, entonces (gcircf)(x)=g(f(x)).
 Función Inversa (f−1): Si f es biyectiva, su inversa f−1 "deshace" la operación de f. Si y=f(x), entonces
x=f−1(y).

Ejemplo Resuelto: Composición de funciones Sea f:mathbbNtomathbbN con f(x)=x+1 y

g:mathbbNtomathbbN con g(x)=2x. Calcular (gcircf)(x).
Paso 1: Entender la definición de composición: (gcircf)(x)=g(f(x)). Paso 2: Sustituir f(x) en g(x).
g(f(x))=g(x+1) Paso 3: Aplicar la regla de g al resultado de f(x). g(x+1)=2(x+1)=2x+2. Solución: (gcircf)
(x)=2x+2.

Ejercicios Propuestos:

1. Determina si la función f:mathbbZtomathbbZ definida por f(x)=x2 es inyectiva y/o sobreyectiva.

Justifica tu respuesta.
2. Encuentra la función inversa de f(x)=3x−5.

2.2. Relaciones, representación, matriz y dígrafo de una relación

 Relación: Un subconjunto del producto cartesiano de dos conjuntos. Representa una conexión entre los
elementos de los conjuntos. Si A y B son conjuntos, una relación R de A a B es un subconjunto de
AtimesB.
 Representación: Una relación se puede representar como:
o Un conjunto de pares ordenados.
o Una matriz de adyacencia.
o Un dígrafo (grafo dirigido).
 Matriz de una relación (M_R): Para una relación R en un conjunto A=a_1,a_2,dots,a_n, la matriz M_R
es una matriz binaria ntimesn donde M_R[i][j]=1 si (a_i,a_j)inR, y 0 en caso contrario.
 Dígrafo: Un grafo donde las aristas tienen una dirección. Cada par ordenado (a,b) en la relación se
representa como una arista dirigida desde el vértice a al vértice b.

Ejemplo Resuelto: Sea A=1,2,3 y la relación R=(1,1),(1,3),(2,1),(3,2). Representar R con una matriz y un
dígrafo.

Paso 1: Matriz de la relación Creamos una matriz 3times3 (porque hay 3 elementos en A). Las filas y
columnas corresponden a los elementos de A (1, 2, 3). Ponemos un 1 si el par está en R, y un 0 si no.

123
1101
2100
3010

M\_R = \\begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\end{pmatrix}¡Error! Nombre de archivo no
especificado.

Paso 2: Dígrafo de la relación Dibujamos los vértices que representan los elementos del conjunto A. Por cada
par (x,y)inR, dibujamos una flecha (arista dirigida) desde x hasta y.

Ejercicios Propuestos:

1. Sea A=a,b,c y R=(a,b),(b,a),(c,c). Dibuja el dígrafo de la relación.

2. Dada la matriz de una relación M = \\begin{pmatrix} 0 & 1 \\ 1 & 0 \\end{pmatrix} en el conjunto
A=x,y, escribe la relación como un conjunto de pares ordenados.

2.3. Propiedades, relaciones de equivalencia y de orden parcial

 Propiedades de las Relaciones:

o Reflexiva: Para todo ainA, (a,a)inR. (Cada elemento se relaciona consigo mismo).
 o Simétrica: Si (a,b)inR, entonces (b,a)inR. (Si a se relaciona con b, entonces b se relaciona con
a).
o Antisimétrica: Si (a,b)inR y (b,a)inR, entonces a=b. (Si a se relaciona con b y b con a, deben ser
el mismo elemento).
o Transitiva: Si (a,b)inR y (b,c)inR, entonces (a,c)inR. (Si a se relaciona con b y b con c, entonces
a se relaciona con c).
 Relación de Equivalencia: Una relación que es reflexiva, simétrica y transitiva. Una relación de
equivalencia particiona un conjunto en clases de equivalencia (subconjuntos disjuntos).
o Ejemplo: La relación "es igual a" en el conjunto de los números enteros.
 Relación de Orden Parcial: Una relación que es reflexiva, antisimétrica y transitiva. No todos los
elementos tienen que ser comparables.
o Ejemplo: La relación "divide a" en el conjunto de los enteros positivos.

Ejemplo Resuelto: Mostrar que la relación "divide a" es una relación de orden parcial en mathbbZ+
(enteros positivos).

Sea R la relación "divide a". Es decir, (a,b)inR si a∣b.

 Reflexiva: ¿a∣a para todo ainmathbbZ+? Sí, porque a=1cdota.

 Antisimétrica: Si a∣b y b∣a, ¿entonces a=b? Si a∣b, entonces b=ka para algún entero k. Si b∣a, entonces
a=lb para algún entero l. Sustituyendo b en la segunda ecuación: a=l(ka)=(lk)a. Como aneq0, lk=1. Dado
que k,l son enteros positivos (porque a,b son positivos), la única posibilidad es k=1 y l=1. Por lo tanto,
b=1cdotaimpliesb=a. La relación es antisimétrica.
 Transitiva: Si a∣b y b∣c, ¿entonces a∣c? Si a∣b, entonces b=ka para algún entero k. Si b∣c, entonces c=lb
para algún entero l. Sustituyendo b en la segunda ecuación: c=l(ka)=(lk)a. Como lk es un entero, a∣c. La
relación es transitiva.

Conclusión: La relación "divide a" es reflexiva, antisimétrica y transitiva, por lo tanto, es una relación de orden
parcial.

Ejercicios Propuestos:

1. Muestra que la relación "tiene la misma fecha de cumpleaños que" en el conjunto de todas las personas
es una relación de equivalencia.
2. Considera la relación R=(a,b)midaleb en el conjunto de los números reales. Determina si es reflexiva,
simétrica, antisimétrica y transitiva.

2.4. Sucesiones y cadenas, representación y tipos de sucesiones, notación Sigma y producto

 Sucesión: Una lista ordenada de elementos. Se denota como a_1,a_2,a_3,dots o a_n_n=1infty.

o Sucesión Aritmética: Cada término se obtiene sumando una constante (diferencia común) al
término anterior.
o Sucesión Geométrica: Cada término se obtiene multiplicando una constante (razón común) al
término anterior.
 Cadena: Una secuencia finita de símbolos de un alfabeto.
 Notación Sigma (sum): Se utiliza para representar la suma de una serie de términos.
sum_i=mna_i=a_m+a_m+1+dots+a_n.
 Notación Producto (prod): Se utiliza para representar el producto de una serie de términos.
prod_i=mna_i=a_mcdota_m+1cdotdotscdota_n.

Ejemplo Resuelto: Suma de los primeros 5 términos de la sucesión a_n=2n+1.

Paso 1: Escribir los primeros 5 términos:

 a_1=2(1)+1=3¡Error! Nombre de archivo no especificado.

 a_2=2(2)+1=5¡Error! Nombre de archivo no especificado.
 a_3=2(3)+1=7¡Error! Nombre de archivo no especificado.
 a_4=2(4)+1=9¡Error! Nombre de archivo no especificado.
 a_5=2(5)+1=11¡Error! Nombre de archivo no especificado.

Paso 2: Sumar los términos: sum_i=15(2i+1)=3+5+7+9+11=35.

Ejercicios Propuestos:

1. Calcula el producto de los primeros 4 números pares positivos usando la notación producto.
2. Encuentra el quinto término de una sucesión aritmética donde el primer término es 5 y la diferencia
común es 3.

Unidad 3: Introducción a la teoría de números y técnicas de conteo

Esta unidad cubre temas fundamentales para la criptografía, la seguridad informática y el análisis de algoritmos.

3.1. Divisibilidad, algoritmo de la división, números primos y teorema fundamental de la

aritmética

 Divisibilidad: Un entero a (divisor) divide a un entero b (dividendo) (a∣b) si existe un entero k tal que
b=ak. Si a∣b, entonces b es un múltiplo de a.
 Algoritmo de la División: Para enteros a (dividendo) y d (divisor) con d0, existen enteros únicos q
(cociente) y r (residuo) tales que a=dq+r, donde 0leqr\<d.
 Números Primos: Un número entero mayor que 1 cuyos únicos divisores positivos son 1 y sí mismo.
 Teorema Fundamental de la Aritmética: Todo número entero mayor que 1 puede ser escrito de forma
única (salvo el orden de los factores) como un producto de números primos. Esta es la factorización
prima.

Ejemplo Resuelto: Usar el algoritmo de la división para a=17,d=5.

Paso 1: Identificar a y d. a=17, d=5. Paso 2: Encontrar el cociente q tal que dcdotq sea el mayor múltiplo de d
menor o igual que a. 5cdot3=15 (es el mayor múltiplo de 5 menor o igual que 17). Así que q=3. Paso 3:
Calcular el residuo r=a−dq. r=17−(5cdot3)=17−15=2. Solución: 17=5cdot3+2. Aquí, el cociente q=3 y el
residuo r=2.

Ejercicios Propuestos:

1. Encuentra los factores primos de 140.

2. Verifica si 179 es un número primo.

3.2. Máximo común divisor (mcd) y mínimo común múltiplo (mcm), sistemas de numeración

 Máximo Común Divisor (MCD): El entero positivo más grande que divide a dos o más enteros sin
dejar residuo.
o Algoritmo de Euclides: Un método eficiente para calcular el MCD de dos números.
  Mínimo Común Múltiplo (MCM): El entero positivo más pequeño que es múltiplo de dos o más
enteros.
o Relación con MCD: Para dos enteros positivos a,b, acdotb=textMCD(a,b)cdottextMCM(a,b).
 Sistemas de Numeración: Diferentes bases para representar números (ej. binario (base 2), octal (base
8), decimal (base 10), hexadecimal (base 16)).

Ejemplo Resuelto: Calcular MCD(24, 36) usando el Algoritmo de Euclides.

Paso 1: Dividir el número mayor por el menor y obtener el residuo. 36=1cdot24+12 Paso 2: Reemplazar el
número mayor por el menor, y el menor por el residuo. Repetir. 24=2cdot12+0 Paso 3: Cuando el residuo es 0,
el último divisor no nulo es el MCD. Solución: El MCD(24, 36) es 12.

Ejercicios Propuestos:

1. Calcula el MCM(15, 25).

2. Convierte el número decimal 13 a su representación binaria (base 2).

3.3. Principio de la multiplicación y de la suma

 Principio de la Multiplicación: Si una tarea se puede dividir en una secuencia de k subtareas, y la

primera subtarea tiene n_1 resultados, la segunda n_2, etc., hasta la k-ésima con n_k, entonces hay
n_1cdotn_2cdotdotscdotn_k resultados posibles para la tarea total. Se usa cuando los eventos son
secuenciales o simultáneos.
 Principio de la Suma: Si una tarea puede realizarse de n_1 maneras o de n_2 maneras (disjuntas, es
decir, no hay solapamiento), entonces hay n_1+n_2 maneras de realizar la tarea. Se usa cuando los
eventos son mutuamente excluyentes.

Ejemplo Resuelto: Un restaurante ofrece 3 entradas, 5 platos principales y 2 postres. ¿Cuántos menús de
3 platillos se pueden armar?

Paso 1: Identificar el número de opciones para cada elección.

 Entradas: 3 opciones
 Platos principales: 5 opciones
 Postres: 2 opciones

Paso 2: Aplicar el principio de la multiplicación, ya que las elecciones son secuenciales e independientes.
Número total de menús = (Opciones de entrada) times (Opciones de plato principal) times (Opciones de postre)
Solución: 3times5times2=30 menús posibles.

Ejercicios Propuestos:

1. En una ciudad, una placa de automóvil consiste en 3 letras seguidas de 3 dígitos. Si las letras y los
dígitos pueden repetirse, ¿cuántas placas diferentes son posibles? (Considera 26 letras y 10 dígitos).
2. Si una persona puede viajar de la ciudad A a la B por 3 aerolíneas, y de la B a la C por 2 aerolíneas.
Además, de la A a la C hay 4 rutas directas. ¿Cuántas maneras diferentes hay de viajar de A a C?

3.4. Principio de las casillas, permutaciones y combinaciones

 Principio de las Casillas (Principio del Palomar): Si se distribuyen N objetos en K casillas, entonces
al menos una casilla debe contener al menos lceilN/Krceil objetos.
 o Ejemplo: Si tienes 13 calcetines de 3 colores diferentes, al menos 5 calcetines deben ser del
mismo color.
 Permutaciones: Arreglos ordenados de objetos. El orden importa.
o Permutaciones de n objetos tomados de r en r: P(n,r)=fracn(n−r).
o Permutaciones con repetición: Para n objetos con n_1 indistinguibles de tipo 1, n_2 de tipo 2,
etc.: fracnn_1n_2dotsn_k.
 Combinaciones: Selecciones de objetos donde el orden no importa.
o Combinaciones de n objetos tomados de r en r: C(n,r)=binomnr=fracnr(n−r).

Ejemplo Resuelto: Permutaciones y Combinaciones

Problema 1: ¿Cuántas permutaciones diferentes se pueden formar con las letras de la palabra "MATH"?
Solución: La palabra "MATH" tiene 4 letras distintas. El número de permutaciones es
4=4times3times2times1=24.

Problema 2: De un grupo de 5 estudiantes, ¿cuántas formas hay de seleccionar un comité de 2

estudiantes? Solución: El orden no importa en un comité, así que es una combinación.
C(5,2)=frac52(5−2)=frac523=frac5times4times3times2times1(2times1)(3times2times1)=frac12012=10.

Ejercicios Propuestos:

1. En un cajón hay 10 calcetines rojos y 10 calcetines azules. Si sacas calcetines al azar en la oscuridad,
¿cuántos debes sacar para asegurarte de tener un par del mismo color? (Usa el principio de las casillas).
2. De un grupo de 10 personas, ¿cuántas formas hay de seleccionar un equipo de 3 personas para un
proyecto?

3.5. Combinaciones generalizadas y teorema del binomio

 Combinaciones Generalizadas (con repetición): El número de formas de elegir r objetos de n tipos

distintos, donde la repetición está permitida y el orden no importa.
o Fórmula: binomn+r−1r.
o Ejemplo: Elegir 3 donas de 5 tipos diferentes.
 Teorema del Binomio: Una fórmula para expandir potencias de un binomio (x+y)n.
o (x+y)n=sum_k=0nbinomnkxn−kyk.
o Los coeficientes binomnk son los coeficientes binomiales, que se encuentran en el Triángulo de
Pascal.

Ejemplo Resuelto: Expansión de (x+y)3 usando el Teorema del Binomio.

Paso 1: Identificar n=3. Paso 2: Aplicar la fórmula del binomio.

(x+y)3=binom30x3y0+binom31x2y1+binom32x1y2+binom33x0y3 Paso 3: Calcular los coeficientes
binomiales: binom30=1 binom31=3 binom32=3 binom33=1 Solución:
(x+y)3=1x3+3x2y+3xy2+1y3=x3+3x2y+3xy2+y3.

Ejercicios Propuestos:

1. Tienes un suministro ilimitado de 4 tipos de dulces. ¿De cuántas maneras puedes elegir 10 dulces?
(Combinaciones con repetición).
2. Encuentra el coeficiente de x2y3 en la expansión de (x+y)5.

Unidad 4: Relaciones de recurrencia y algoritmo

Esta unidad se centra en dos conceptos fundamentales en la informática y las matemáticas discretas: el análisis
de algoritmos y la resolución de relaciones de recurrencia. Ambos están estrechamente relacionados, ya que las
relaciones de recurrencia son una herramienta clave para analizar el tiempo de ejecución de algoritmos
recursivos.

4.1. Pseudocódigo, algoritmos numéricos simples, promedio, mínimo y máximo

¿Qué es el pseudocódigo? El pseudocódigo es una forma de describir un algoritmo utilizando un lenguaje

cercano al humano, pero con estructuras de programación. Su propósito es ser legible y fácil de entender, sin las
reglas de sintaxis estrictas de un lenguaje de programación específico (como C++, Python o Java). Es una
herramienta ideal para planificar la lógica de un programa antes de codificarlo.

Algoritmos numéricos simples: Estos son algoritmos que resuelven problemas básicos utilizando operaciones
matemáticas.

 Promedio:
o Paso 1: Inicializar una variable suma en 0.
o Paso 2: Inicializar una variable contador en 0.
o Paso 3: Leer una lista de números.
o Paso 4: Para cada número en la lista:
 Sumar el número a la variable suma.
 Incrementar la variable contador en 1.
o Paso 5: Calcular el promedio dividiendo suma entre contador.
o Paso 6: Mostrar el promedio.
 Mínimo y Máximo:
o Paso 1: Leer el primer número de la lista.
o Paso 2: Inicializar una variable minimo con este primer número.
o Paso 3: Inicializar una variable maximo con este primer número.
o Paso 4: Para cada uno de los números restantes en la lista:
 Si el número actual es menor que minimo, actualizar minimo con el número actual.
 Si el número actual es mayor que maximo, actualizar maximo con el número actual.
o Paso 5: Mostrar minimo y maximo.

Ejemplo Resuelto: Algoritmo para calcular el promedio de una lista de números

Problema: Escribir un algoritmo que calcule el promedio de N números dados.

Pseudocódigo:

Algoritmo CalcularPromedio
Definir N, i Como entero
Definir suma Como real
Definir promedio Como real

suma <- 0

Escribir "Ingrese la cantidad de números:"

Leer N

Para i desde 1 hasta N hacer

Definir numero_actual Como real
Escribir "Ingrese el número ", i, ":"
Leer numero_actual
suma <- suma + numero_actual
 Fin Para

Si N > 0 Entonces
promedio <- suma / N
Escribir "El promedio de los números es: ", promedio
Sino
Escribir "La lista de números está vacía. El promedio no puede ser calculado."
Fin Si

Fin Algoritmo

Ejercicios Propuestos:

1. Escribe el pseudocódigo para encontrar el número más pequeño en una lista de 10 números.
2. Escribe un algoritmo que pida al usuario una lista de números y muestre cuántos de ellos son pares y
cuántos son impares.

4.2. Análisis de algoritmos, tiempo del mejor caso, peor caso y caso promedio

El análisis de algoritmos es el proceso de determinar la cantidad de recursos (generalmente tiempo y memoria)

que un algoritmo necesita para resolver un problema. Nos ayuda a predecir el comportamiento de un algoritmo
a medida que el tamaño de la entrada crece. La métrica más común es la complejidad temporal, que se expresa
con la notación de la "O" grande (O-grande).

 Tiempo del mejor caso (Big-Omega, Omega):

o Es el escenario ideal donde el algoritmo ejecuta el menor número de operaciones posibles.
o Ejemplo: En un algoritmo de búsqueda lineal, el mejor caso es cuando el elemento que
buscamos se encuentra en la primera posición de la lista. Solo se necesita una comparación.
 Tiempo del peor caso (Big-O, O):
o Es el escenario menos favorable, donde el algoritmo realiza la mayor cantidad de operaciones. Es
la métrica más importante en el análisis de algoritmos porque nos da una garantía de que el
tiempo de ejecución nunca será peor que este límite.
o Ejemplo: En un algoritmo de búsqueda lineal, el peor caso es cuando el elemento que buscamos
está en la última posición o no se encuentra en la lista. En este caso, el algoritmo debe recorrer
toda la lista. Si la lista tiene n elementos, se necesitan n comparaciones. La complejidad es O(n).
 Tiempo del caso promedio (Big-Theta, Theta):
o Es el tiempo de ejecución esperado, promediado sobre todas las posibles entradas. Es a menudo
el más difícil de calcular, ya que requiere un análisis probabilístico.
o Ejemplo: En la búsqueda lineal, asumiendo que el elemento puede estar en cualquier posición
con la misma probabilidad, el caso promedio sería aproximadamente n/2 comparaciones. La
complejidad es Theta(n).

Ejemplo Resuelto: Análisis de un algoritmo de búsqueda lineal

Problema: Analizar el tiempo de ejecución de un algoritmo que busca un elemento x en una lista de n
elementos.

Pseudocódigo (Búsqueda Lineal):

Algoritmo BusquedaLineal(lista, n, x)
Para i desde 1 hasta n hacer
Si lista[i] == x Entonces
Retornar i // Se encontró el elemento
 Fin Si
Fin Para
Retornar -1 // No se encontró el elemento
Fin Algoritmo

Análisis:

 Mejor Caso (Omega): El elemento x se encuentra en la primera posición. El bucle Para se ejecuta una
sola vez. La complejidad es Omega(1), es decir, tiempo constante.
 Peor Caso (O): El elemento x no está en la lista o se encuentra en la última posición. El bucle Para se
ejecuta n veces. La complejidad es O(n), es decir, tiempo lineal.
 Caso Promedio (Theta): Asumiendo una distribución uniforme de probabilidades, el elemento se
encuentra en promedio a la mitad de la lista. El bucle se ejecuta aproximadamente n/2 veces. La
complejidad es Theta(n).

Ejercicios Propuestos:

1. Analiza la complejidad en el peor caso de un algoritmo que busca el mínimo y el máximo en una lista de
n números.
2. Considera un algoritmo que verifica si un elemento está en una lista ordenada. ¿Cuál sería el mejor caso
y el peor caso si el algoritmo utiliza una búsqueda binaria?

4.3. Relaciones de recurrencia, aplicaciones a problemas discretos

¿Qué son las relaciones de recurrencia? Una relación de recurrencia es una ecuación que define una
secuencia donde cada término se define en función de los términos anteriores. Son la base para analizar
algoritmos recursivos (algoritmos que se llaman a sí mismos).

Ejemplo clásico: La Torre de Hanoi El problema de la Torre de Hanoi es un ejemplo perfecto. Para mover n
discos de una torre a otra, se necesita:

1. Mover n−1 discos de la torre de origen a la torre auxiliar.

2. Mover el disco más grande a la torre de destino.
3. Mover los n−1 discos de la torre auxiliar a la torre de destino.

Si T(n) es el número de movimientos para n discos, la relación de recurrencia es: T(n)=2T(n−1)+1 con la
condición base: T(1)=1.

Aplicaciones a problemas discretos: Las relaciones de recurrencia no solo se usan para algoritmos. Se aplican
en muchos otros campos:

 Combinatoria: Contar el número de formas de hacer algo.

 Biología: Modelar el crecimiento de poblaciones.
 Finanzas: Calcular el interés compuesto.

Ejercicios Propuestos:

1. La secuencia de Fibonacci se define como f_n=f_n−1+f_n−2 con f_0=0 y f_1=1. Calcula los primeros 5
términos de la secuencia.
2. Considera un problema donde un conejo tiene dos crías cada mes. Si empieza con un solo conejo,
formula la relación de recurrencia para el número de conejos al cabo de n meses.
4.4. Resolución de relaciones de recurrencia homogénea de segundo orden

Este subtema se enfoca en la técnica matemática para encontrar una fórmula cerrada (una ecuación que no es
recursiva) para una relación de recurrencia. La forma de una relación de recurrencia homogénea de segundo
orden es: a_n=c_1a_n−1+c_2a_n−2¡Error! Nombre de archivo no especificado.

Pasos para la resolución:

Paso 1: Ecuación característica Se asume que la solución tiene la forma a_n=rn. Sustituyendo esto en la
relación de recurrencia, obtenemos la ecuación característica: r2=c_1r+c_2 o r2−c_1r−c_2=0¡Error! Nombre
de archivo no especificado.

Paso 2: Encontrar las raíces de la ecuación característica Se resuelve la ecuación cuadrática para encontrar
las raíces r_1 y r_2. Hay tres casos posibles:

 Caso 1: Raíces distintas (r_1neqr_2) La solución general es: a_n=Ar_1n+Br_2n¡Error! Nombre de

archivo no especificado.
 Caso 2: Una sola raíz (r_1=r_2) La solución general es: a_n=Ar_1n+Bnr_1n¡Error! Nombre de
archivo no especificado.
 Caso 3: Raíces complejas conjugadas (r=alphapmibeta) La solución general es más compleja y se
expresa en términos de senos y cosenos, pero el principio es el mismo.

Paso 3: Usar las condiciones iniciales para encontrar las constantes A y B Se utilizan las condiciones
iniciales del problema (ej. a_0=1,a_1=3) para crear un sistema de ecuaciones y resolverlo para encontrar los
valores de las constantes A y B. Una vez que se tienen A y B, se tiene la fórmula cerrada para la secuencia.

Ejemplo Resuelto: Resolver la relación de recurrencia a_n=5a_n−1−6a_n−2 con a_0=1,a_1=2.

Paso 1: Ecuación Característica Asumimos una solución de la forma a_n=rn. Sustituyendo, obtenemos:
r2=5r−6 r2−5r+6=0¡Error! Nombre de archivo no especificado.

Paso 2: Encontrar las raíces Factorizamos la ecuación: (r−2)(r−3)=0 Las raíces son r_1=2 y r_2=3. Son raíces
distintas.

Paso 3: Formular la solución general Dado que las raíces son distintas, la solución general es:
a_n=A(2)n+B(3)n¡Error! Nombre de archivo no especificado.

Paso 4: Usar las condiciones iniciales para encontrar A y B

 Para n=0: a_0=1implies1=A(2)0+B(3)0implies1=A+B¡Error! Nombre de archivo no especificado.

 Para n=1: a_1=2implies2=A(2)1+B(3)1implies2=2A+3B¡Error! Nombre de archivo no especificado.

Ahora resolvemos el sistema de ecuaciones:

1. A+B=1impliesA=1−B¡Error! Nombre de archivo no especificado.

2. 2(1−B)+3B=2 2−2B+3B=2 B=0 Sustituyendo B=0 en la primera ecuación: A=1−0=1.

Paso 5: Escribir la solución final Sustituimos A=1 y B=0 en la solución general: a_n=1(2)n+0(3)n
a_n=2n¡Error! Nombre de archivo no especificado.

Ejercicios Propuestos:
 1. Resuelve la relación de recurrencia a_n=4a_n−1−4a_n−2 con a_0=1,a_1=3. (Pista: tiene una sola raíz).
2. Resuelve la relación de recurrencia de Fibonacci: f_n=f_n−1+f_n−2 con f_0=0,f_1=1.

Unidad 5: Teoría de grafos, árboles y aplicaciones

Esta unidad explora las estructuras de datos que modelan redes y conexiones, muy utilizadas en redes sociales,
sistemas de navegación y bases de datos.

5.1. Grafos, subgrafos, isomorfismo de grafos, rutas y ciclos de Euler y Hamilton, grafos
ponderados

 Grafo: Un par ordenado G=(V,E), donde V es un conjunto de vértices (nodos) y E es un conjunto de

aristas (conexiones) que unen pares de vértices.
o Grafo No Dirigido: Las aristas no tienen dirección (ej. una amistad en Facebook).
o Grafo Dirigido (Dígrafo): Las aristas tienen dirección (ej. seguir a alguien en Twitter).
 Subgrafo: Un grafo G′ es un subgrafo de G si sus vértices y aristas son subconjuntos de los vértices y
aristas de G.
 Isomorfismo de Grafos: Dos grafos son isomorfos si son estructuralmente idénticos, es decir, existe
una correspondencia uno a uno entre sus vértices que preserva las aristas.
 Ruta: Una secuencia de vértices conectados por aristas.
 Ciclo de Euler: Un ciclo que visita cada arista de un grafo exactamente una vez. Un grafo conexo tiene
un ciclo de Euler si y solo si todos sus vértices tienen grado par.
 Ciclo de Hamilton: Un ciclo que visita cada vértice de un grafo exactamente una vez.
 Grafo Ponderado: Un grafo donde cada arista tiene un valor numérico asociado (peso), que puede
representar distancia, costo, tiempo, etc.

Ejemplo Resuelto: Determina si el siguiente grafo tiene un ciclo de Euler.

 Grafo: Vértices A, B, C, D y aristas (A,B), (A,C), (A,D), (B,C), (C,D).

 Paso 1: Calcular el grado de cada vértice (número de aristas que inciden en él).
o Grado(A) = 3 (aristas: AB, AC, AD)
o Grado(B) = 2 (aristas: BA, BC)
o Grado(C) = 3 (aristas: CA, CB, CD)
o Grado(D) = 2 (aristas: DA, DC)
 Paso 2: Aplicar la condición para un ciclo de Euler: todos los vértices deben tener grado par.
 Conclusión: Como los vértices A y C tienen grado impar, el grafo no tiene un ciclo de Euler.

Ejercicios Propuestos:

1. Dibuja un grafo con 5 vértices que contenga un ciclo de Hamilton pero no un ciclo de Euler.
2. Considera los 8 vértices de un cubo. Dibuja el grafo que los representa y determina si tiene un ciclo de
Hamilton.

5.2. Árboles y caracterización, árboles de expansión mínima y binarios, recorridos

 Árbol: Un grafo conexo sin ciclos.

o Propiedades clave: Cualquier dos vértices están conectados por un único camino, y un árbol con
n vértices tiene exactamente n−1 aristas.
 Árbol de Expansión (Spanning Tree): Un subgrafo de un grafo conexo que es un árbol y que incluye
todos los vértices del grafo original.
  Árbol de Expansión Mínimo (Minimum Spanning Tree - MST): Para un grafo ponderado, es un
árbol de expansión cuya suma de los pesos de sus aristas es la mínima posible.
o Algoritmos: Algoritmo de Prim y Algoritmo de Kruskal son dos métodos populares para
encontrar un MST.
 Árbol Binario: Un árbol donde cada nodo tiene como máximo dos hijos (izquierdo y derecho).
 Árbol Binario de Búsqueda (ABB): Un árbol binario donde, para cada nodo, todos los valores en su
subárbol izquierdo son menores que el valor del nodo, y todos los valores en su subárbol derecho son
mayores.
 Recorridos de Árboles Binarios: Formas sistemáticas de visitar todos los nodos de un árbol.
o Preorden (Raíz-Izquierda-Derecha): Visita la raíz, luego el subárbol izquierdo, luego el
subárbol derecho.
o Inorden (Izquierda-Raíz-Derecha): Visita el subárbol izquierdo, luego la raíz, luego el
subárbol derecho. (Produce una lista ordenada en un ABB).
o Postorden (Izquierda-Derecha-Raíz): Visita el subárbol izquierdo, luego el subárbol derecho,
luego la raíz.

Ejemplo Resuelto: Inserción en un Árbol Binario de Búsqueda (ABB) Inserta los siguientes números en un
ABB vacío: 50, 30, 70, 20, 40, 60, 80.

Paso 1: Inserta 50 (raíz). Paso 2: Inserta 30: 30\<50, va a la izquierda de 50. Paso 3: Inserta 70: 7050, va a la
derecha de 50. Paso 4: Inserta 20: 20\<50, va a la izquierda de 50; 20\<30, va a la izquierda de 30. Paso 5:
Inserta 40: 40\<50, va a la izquierda de 50; 4030, va a la derecha de 30. Paso 6: Inserta 60: 6050, va a la
derecha de 50; 60\<70, va a la izquierda de 70. Paso 7: Inserta 80: 8050, va a la derecha de 50; 8070, va a la
derecha de 70.

Ejercicios Propuestos:

1. Dado el siguiente árbol binario (raíz A, hijo izquierdo B, hijo derecho C; B tiene hijo izquierdo D; C
tiene hijo izquierdo E, hijo derecho F): Realiza los recorridos en preorden, inorden y postorden.
2. Usa el algoritmo de Kruskal para encontrar el árbol de expansión mínimo en el siguiente grafo
ponderado: Vértices: A, B, C, D, E. Aristas y Pesos: (A,B,4), (A,C,1), (B,C,2), (B,D,5), (C,D,8),
(C,E,10), (D,E,6).

5.3. Algoritmo de la ruta más corta, algoritmo del mínimo peso

 Algoritmo de la Ruta Más Corta: Resuelve el problema de encontrar un camino entre dos vértices en
un grafo ponderado de forma que la suma de los pesos de las aristas sea mínima.
o Algoritmo de Dijkstra: Un algoritmo famoso que resuelve este problema para grafos con pesos
no negativos. Funciona manteniendo un conjunto de vértices cuyas distancias más cortas desde el
origen ya se conocen.
 Algoritmo del Mínimo Peso (para árboles de expansión): Encuentra un subgrafo que conecta todos
los vértices con el menor peso total posible. El resultado es un árbol de expansión mínimo.
o Algoritmo de Prim: Comienza desde un vértice arbitrario y crece el árbol añadiendo la arista de
menor peso que conecta un vértice en el árbol con uno fuera del árbol.
o Algoritmo de Kruskal: Ordena todas las aristas por peso de forma ascendente y añade las
aristas al árbol si no forman un ciclo con las aristas ya añadidas.

Ejemplo Resuelto: Algoritmo de Dijkstra Encuentra el camino más corto del vértice A al E en el siguiente
grafo: A-B (4), A-C (1), B-C (2), B-D (5), C-D (8), C-E (10), D-E (6).
Paso 1: Inicialización Distancias: A=0, B=infty, C=infty, D=infty, E=infty. Visitados: {} No visitados: {A, B,
C, D, E}

Paso 2: Iteración

1. Seleccionar A (dist=0). Marcar A como visitado.

o Vecinos de A: B (dist 0+4=4), C (dist 0+1=1).
o Distancias: A=0, B=4, C=1, D=infty, E=infty.
2. Seleccionar C (dist=1). Marcar C como visitado.
o Vecinos de C: A (ya visitado), B (dist 1+2=3, mejor que 4), D (dist 1+8=9), E (dist 1+10=11).
o Distancias: A=0, B=3, C=1, D=9, E=11.
3. Seleccionar B (dist=3). Marcar B como visitado.
o Vecinos de B: A (ya visitado), C (ya visitado), D (dist 3+5=8, mejor que 9).
o Distancias: A=0, B=3, C=1, D=8, E=11.
4. Seleccionar D (dist=8). Marcar D como visitado.
o Vecinos de D: B (ya visitado), C (ya visitado), E (dist 8+6=14, peor que 11).
o Distancias: A=0, B=3, C=1, D=8, E=11. (No se actualiza E).
5. Seleccionar E (dist=11). Marcar E como visitado.

Paso 3: Reconstruir el camino a E

 Para llegar a E con 11, vino de C (1+10=11).

 Para llegar a C con 1, vino de A (0+1=1).
 Camino: A -> C -> E.
 Peso total: 1+10=11.

Ejercicios Propuestos:

1. Usa el algoritmo de Prim para encontrar el árbol de expansión mínimo en el mismo grafo del ejemplo
anterior (A, B, C, D, E; Aristas y Pesos: (A,B,4), (A,C,1), (B,C,2), (B,D,5), (C,D,8), (C,E,10), (D,E,6)).
2. Usa el algoritmo de Dijkstra para encontrar el camino más corto de C a B en el mismo grafo.

Unidad 6: Lenguajes, gramáticas y autómatas de estado finito

Esta unidad es la base teórica de la computación, el diseño de compiladores y la teoría de la información.

6.1. Circuitos secuenciales y máquinas de estado finito

 Circuitos Combinatorios (repaso): La salida solo depende de la entrada actual. No tienen memoria.
 Circuitos Secuenciales: La salida depende de la entrada actual Y del estado anterior. Tienen memoria,
lo que les permite recordar información pasada. Ejemplos incluyen flip-flops, contadores y registros.
 Máquina de Estado Finito (MEF) / Autómata Finito (AF): Un modelo matemático abstracto de un
sistema que puede estar en uno de un número finito de estados en un momento dado. Cambia de estado
en respuesta a entradas.
o Componentes de una MEF:
 Un conjunto finito de estados (Q).
 Un alfabeto de entrada (Sigma).
 Una función de transición (delta) que mapea un par (estado, entrada) a un nuevo estado.
 Un estado inicial (q_0inQ).
 Un conjunto de estados finales (o de aceptación) (FsubseteqQ).
Ejemplo Resuelto: Diseñar una MEF que detecte la cadena de bits "101".

Paso 1: Definir los estados.

 S_0: Estado inicial, no se ha recibido ninguna parte de "101".

 S_1: Se ha recibido un '1'.
 S_2: Se ha recibido "10".
 S_3: Se ha recibido "101" (estado final/de aceptación).

Paso 2: Definir las transiciones.

 Desde S_0:
o Si entrada es '1', ir a S_1.
o Si entrada es '0', permanecer en S_0.
 Desde S_1:
o Si entrada es '0', ir a S_2.
o Si entrada es '1', permanecer en S_1 (se recibió un nuevo '1', pero no "10").
 Desde S_2:
o Si entrada es '1', ir a S_3.
o Si entrada es '0', ir a S_0 (la secuencia "100" no es parte de "101").
 Desde S_3:
o Si la MEF debe detectar cada ocurrencia, al recibir cualquier entrada, volver a S_0 o a un estado
apropiado para buscar la siguiente "101". (Para este ejemplo simple, asumimos que una vez
detectada, la MEF se reinicia o se detiene). Si se permite superposición, la lógica sería más
compleja. Para este caso, si llega a S_3 y recibe un '1', puede volver a S_1 (ya tiene un '1'). Si
recibe un '0', vuelve a S_0.

Paso 3: Dibujar el diagrama de transición.

Ejercicios Propuestos:

1. Diseña una MEF que detecte la cadena de bits "11". Incluye los estados y las transiciones.
2. Dibuja el diagrama de transición de la MEF que diseñaste para el problema anterior.

6.2. Autómata de estado finito, diagrama de transición, cadena de aceptación

 Autómata de Estado Finito (Formalmente): Se define como una 5-tupla (Q,Sigma,delta,q_0,F),

donde:
o Q: Conjunto finito de estados.
o Sigma: Alfabeto de entrada (conjunto finito de símbolos).
o delta: Función de transición delta:QtimesSigmatoQ.
o q_0inQ: Estado inicial.
o FsubseteqQ: Conjunto de estados de aceptación (o finales).
 Diagrama de Transición: Una representación gráfica de una MEF, donde los nodos son estados y las
aristas dirigidas son transiciones etiquetadas con símbolos de entrada. Los estados iniciales se indican
con una flecha entrante, y los estados finales con un doble círculo.
 Cadena de Aceptación: Una cadena de entrada es aceptada por una MEF si, al procesar la cadena desde
el estado inicial, la MEF termina en uno de los estados de aceptación. El conjunto de todas las cadenas
aceptadas por una MEF se llama el lenguaje reconocido por la MEF.

Ejemplo Resuelto: Traza la cadena "0101" en la MEF que detecta "101" (del ejemplo anterior).
  Paso 1: Iniciar en S_0.
 Paso 2: Entrada '0'. Desde S_0 con '0' toS_0. Estado actual: S_0.
 Paso 3: Entrada '1'. Desde S_0 con '1' toS_1. Estado actual: S_1.
 Paso 4: Entrada '0'. Desde S_1 con '0' toS_2. Estado actual: S_2.
 Paso 5: Entrada '1'. Desde S_2 con '1' toS_3. Estado actual: S_3.

Conclusión: La cadena "0101" es aceptada porque la MEF termina en S_3, que es un estado de aceptación.

Ejercicios Propuestos:

1. Diseña una MEF que acepte todas las cadenas binarias que terminan en "00".
2. Traza la cadena "10010" en la MEF que diseñaste para el problema anterior y determina si es aceptada.

6.3. Lenguaje, gramáticas, notación Backus-Nauer form (BNF)

 Alfabeto (Sigma): Un conjunto finito y no vacío de símbolos.

 Cadena: Una secuencia finita de símbolos de un alfabeto.
 Lenguaje: Un conjunto de cadenas formadas a partir de un alfabeto. Los lenguajes pueden ser finitos o
infinitos.
 Gramática Formal: Un conjunto de reglas de producción que especifican cómo construir cadenas
válidas en un lenguaje. Se define como una 4-tupla (V,T,P,S), donde:
o V: Conjunto finito de variables (símbolos no terminales).
o T: Conjunto finito de terminales (símbolos del alfabeto, que forman las cadenas del lenguaje).
o P: Conjunto finito de reglas de producción (ej. Atoalpha, donde AinV y alpha es una cadena de
símbolos de VcupT).
o SinV: Símbolo inicial (o axioma).
 Notación Backus-Nauer Form (BNF): Una forma metalingüística estándar para describir la sintaxis de
los lenguajes de programación y otros lenguajes formales. Utiliza la notación ::= para "se define como"
y | para "o".
o Ejemplo: <dígito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
o <número> ::= <dígito> | <número><dígito>

Ejemplo Resuelto: Usar BNF para describir una lista de números enteros separados por comas.

 Paso 1: Definir los elementos más básicos.

o Un dígito: <dígito> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" |
"9"
o Un número: <número> ::= <dígito> | <número><dígito> (un número es un dígito, o un
número seguido de un dígito).
 Paso 2: Definir la lista de números.
o Una lista de números es un número, o un número seguido de una coma y otra lista de números.
o <lista_de_numeros> ::= <número> | <número> "," <lista_de_numeros>

Ejercicios Propuestos:

1. Usa la notación BNF para describir la sintaxis de una expresión aritmética simple que involucre
números y los operadores de suma y resta. (Ej. "5+3-2", "10").
2. Dada la gramática: <exp> ::= "a" | <exp> "b". ¿Qué cadenas son válidas en esta gramática?
Enumera las primeras 5 cadenas.

Conclusión
Las Matemáticas Discretas son mucho más que una colección de temas abstractos; son el lenguaje y la lógica
subyacente de la era digital. A lo largo de este documento, hemos explorado desde los fundamentos del
razonamiento lógico y la teoría de conjuntos, que nos permiten estructurar la información y construir
argumentos válidos, hasta las relaciones y funciones que modelan las interacciones en sistemas complejos.
Hemos profundizado en la teoría de números y las técnicas de conteo, herramientas indispensables para la
criptografía, la seguridad y la optimización. El análisis de algoritmos y las relaciones de recurrencia nos han
proporcionado la capacidad de evaluar la eficiencia de las soluciones computacionales, un aspecto crítico en el
desarrollo de software. Finalmente, la teoría de grafos y árboles nos ha permitido modelar redes y conexiones,
omnipresentes en la informática moderna, y la teoría de lenguajes formales y autómatas nos ha dado una visión
del funcionamiento interno de los compiladores y la computación misma.

Dominar estos conceptos no solo fortalece la capacidad de resolver problemas de manera estructurada y lógica,
sino que también sienta las bases para comprender y crear tecnologías innovadoras. Es el pensamiento discreto
el que nos permite descomponer problemas complejos en componentes manejables, diseñar algoritmos
eficientes y construir sistemas robustos.

Después de haber cubierto los fundamentos de las Matemáticas Discretas, el camino de aprendizaje se ramifica
hacia áreas más especializadas y aplicadas. Naturalmente, el siguiente paso lógico sería profundizar en
Algoritmos y Estructuras de Datos Avanzadas, donde se aplican directamente las técnicas de análisis de
complejidad y se exploran estructuras como heaps, árboles balanceados y grafos complejos. Otros campos que
se benefician enormemente de esta base incluyen la Teoría de la Computación (que explora los límites de lo
que las computadoras pueden hacer), el Diseño de Compiladores (donde se aplican gramáticas y autómatas), la
Criptografía (que se basa en la teoría de números), la Inteligencia Artificial (especialmente en lógica, grafos y
algoritmos de búsqueda), y la Investigación de Operaciones (optimización, problemas de ruta). Las
Matemáticas Discretas son, en esencia, el lenguaje con el que se construye el mundo computacional.

Referencias Bibliográficas
 Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3a ed.).
The MIT Press.
 Grimaldi, R. P. (1998). Matemáticas discretas y combinatoria (3a ed.). Pearson Educación.
 Rosen, K. H. (2012). Matemáticas discretas y sus aplicaciones (7a ed.). McGraw-Hill Interamericana.

Respuestas a los Ejercicios Propuestos

Unidad 1: Conjunto, lógica, demostraciones y circuitos combinatorios

1. Tabla de verdad para (plorq)to(plandq): | p | q | plorq | plandq | (plorq)to(plandq) | |---|---|---|---|---| | V |

V|V|V|V||V|F|V|F|F||F|V|V|F|F||F|F|F|F|V|
2. Circuito lógico para (plandq)lornegr:
o Una compuerta AND con entradas p y q.
o Una compuerta NOT con entrada r.
o Una compuerta OR con las salidas de la AND y la NOT.
3. Recíproca vs. Inversa: No son lógicamente equivalentes. La recíproca es qtop y la inversa es
negptonegq. Sus tablas de verdad son diferentes.
4. Simplificar neg(plornegq)lor(negplandq):
o Aplicando De Morgan a la primera parte: (negplandneg(negq))lor(negplandq)¡Error! Nombre
de archivo no especificado.
o Simplificando neg(negq): (negplandq)lor(negplandq)¡Error! Nombre de archivo no
especificado.
 o Por la ley de idempotencia: negplandq¡Error! Nombre de archivo no especificado.
5. Demostración por inducción: 2+4+6+dots+2n=n(n+1):
o Caso Base (n=1): 2=1(1+1)=2. Verdadero.
o Paso Inductivo: Asumir 2+dots+2k=k(k+1). Demostrar 2+dots+2k+2(k+1)=(k+1)(k+2).
k(k+1)+2(k+1)=(k+1)(k+2). Verdadero.
6. Demostración por contradicción: Si n2 es par, entonces n es par:
o Asumir n2 es par y n es impar.
o Si n es impar, entonces n=2k+1 para algún entero k.
o Entonces n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1.
o Esto significa que n2 es impar, lo cual contradice nuestra suposición de que n2 es par. Por lo
tanto, si n2 es par, n debe ser par.
7. Producto cartesiano AtimesB para A=1,2 y B=a,b:
o (1,a),(1,b),(2,a),(2,b)¡Error! Nombre de archivo no especificado.
8. Operaciones con conjuntos para U=1,2,3,4,5, A=1,3,5 y B=2,3,4:
o AcupB=1,2,3,4,5¡Error! Nombre de archivo no especificado.
o AcapB=3¡Error! Nombre de archivo no especificado.
o A−B=1,5¡Error! Nombre de archivo no especificado.
o barA=2,4¡Error! Nombre de archivo no especificado.

Unidad 2: Funciones, sucesiones y relaciones

1. Función f:mathbbZtomathbbZ definida por f(x)=x2:

o No es inyectiva: Porque f(−2)=4 y f(2)=4, pero −2neq2.
o No es sobreyectiva: Porque no hay ningún entero x tal que x2=−1 (o cualquier número
negativo). El rango es 0,1,4,9,dots, que no cubre todos los enteros.
2. Función inversa de f(x)=3x−5:
o y=3x−5¡Error! Nombre de archivo no especificado.
o y+5=3x¡Error! Nombre de archivo no especificado.
o x=(y+5)/3¡Error! Nombre de archivo no especificado.
o f−1(x)=(x+5)/3¡Error! Nombre de archivo no especificado.
3. Dígrafo de la relación R=(a,b),(b,a),(c,c) en A=a,b,c:
o Vértices: a, b, c.
o Aristas: a to b, b to a, c to c (bucle).
4. Relación como conjunto de pares ordenados de la matriz M = \\begin{pmatrix} 0 & 1 \\ 1 & 0 \\
end{pmatrix} en A=x,y:
o R=(x,y),(y,x)¡Error! Nombre de archivo no especificado.
5. Propiedades de la relación R=(a,b)midaleb en los números reales:
o Reflexiva: Sí, alea es verdadero.
o Simétrica: No, si aleb no implica que blea (ej. 2le3 pero 3notle2).
o Antisimétrica: Sí, si aleb y blea, entonces a=b.
o Transitiva: Sí, si aleb y blec, entonces alec.
6. Relación "tiene la misma fecha de cumpleaños que" como relación de equivalencia:
o Reflexiva: Sí, una persona tiene la misma fecha de cumpleaños que ella misma.
o Simétrica: Sí, si la persona A tiene la misma fecha de cumpleaños que la persona B, entonces la
persona B tiene la misma fecha de cumpleaños que la persona A.
o Transitiva: Sí, si la persona A tiene la misma fecha de cumpleaños que B, y B tiene la misma
fecha de cumpleaños que C, entonces A tiene la misma fecha de cumpleaños que C.
o Como es reflexiva, simétrica y transitiva, es una relación de equivalencia.
7. Producto de los primeros 4 números pares positivos:
o prod_i=14(2i)=2times4times6times8=384.
8. Quinto término de una sucesión aritmética:
 o a_1=5, d=3.
o a_n=a_1+(n−1)d¡Error! Nombre de archivo no especificado.
o a_5=5+(5−1)3=5+4times3=5+12=17.

Unidad 3: Introducción a la teoría de números y técnicas de conteo

1. Factores primos de 140:

o 140=2times70=2times2times35=22times5times7.
2. Verificar si 179 es un número primo:
o Las raíces de 179 es aproximadamente 13.37. Necesitamos probar divisores primos hasta 13: 2,
3, 5, 7, 11, 13.
o 179 no es divisible por 2 (es impar).
o 179 no es divisible por 3 (1+7+9=17, no es múltiplo de 3).
o 179 no es divisible por 5 (no termina en 0 o 5).
o 179 / 7 = 25 con residuo 4.
o 179 / 11 = 16 con residuo 3.
o 179 / 13 = 13 con residuo 10.
o Sí, 179 es un número primo.
3. MCM(15, 25):
o MCD(15, 25): 25=1cdot15+10, 15=1cdot10+5, 10=2cdot5+0. MCD es 5.
o MCM(15, 25) = (15times25)/5=375/5=75.
4. Convertir 13 (decimal) a binario:
o 13div2=6 residuo 1¡Error! Nombre de archivo no especificado.
o 6div2=3 residuo 0¡Error! Nombre de archivo no especificado.
o 3div2=1 residuo 1¡Error! Nombre de archivo no especificado.
o 1div2=0 residuo 1¡Error! Nombre de archivo no especificado.
o Leyendo los residuos de abajo hacia arriba: 1101_2.
5. Placas de automóvil:
o 26times26times26times10times10times10=263times103=17,576times1,000=17,576,000 placas
diferentes.
6. Maneras de viajar de A a C:
o (A a B a C) + (A a C directo) = (3times2)+4=6+4=10 maneras diferentes.
7. Principio de las casillas (calcetines):
o Tienes 2 colores (casillas).
o Si sacas 3 calcetines (objetos), al menos lceil3/2rceil=2 calcetines deben ser del mismo color.
o Debes sacar 3 calcetines para asegurarte de tener un par del mismo color. (Si sacas 2, podrían ser
uno rojo y uno azul).
8. Seleccionar un equipo de 3 personas de 10:
o Es una combinación porque el orden no importa.
o C(10,3)=frac103(10−3)=frac1037=frac10times9times83times2times1=10times3times4=120
formas.
9. Elegir 10 dulces de 4 tipos (con repetición):
o n=4 (tipos de dulces), r=10 (dulces a elegir).
o binomn+r−1r=binom4+10−110=binom1310=binom133=frac13times12times113times2times1=1
3times2times11=286 maneras.
10. Coeficiente de x2y3 en (x+y)5:
o Según el teorema del binomio, el término es binom5kx5−kyk.
o Para y3, k=3.
o El coeficiente es binom53=frac532=frac5times42times1=10.
Unidad 4: Relaciones de recurrencia y algoritmo

1. Pseudocódigo para encontrar el número más pequeño en una lista de 10 números:

2. Algoritmo EncontrarMinimo
3. Definir lista[10] Como entero
4. Definir minimo, i Como entero
5.
6. // Leer los 10 números
7. Para i desde 1 hasta 10 hacer
8. Escribir "Ingrese el número ", i, ":"
9. Leer lista[i]
10. Fin Para
11.
12. minimo <- lista[1] // Inicializar con el primer elemento
13.
14. Para i desde 2 hasta 10 hacer // Comparar con el resto de la lista
15. Si lista[i] < minimo Entonces
16. minimo <- lista[i]
17. Fin Si
18. Fin Para
19.
20. Escribir "El número más pequeño es: ", minimo
21. Fin Algoritmo

22. Pseudocódigo para contar números pares e impares:

23. Algoritmo ContarParesImpares
24. Definir N, i Como entero
25. Definir num_pares, num_impares Como entero
26.
27. num_pares <- 0
28. num_impares <- 0
29.
30. Escribir "Ingrese la cantidad de números a procesar:"
31. Leer N
32.
33. Para i desde 1 hasta N hacer
34. Definir numero_actual Como entero
35. Escribir "Ingrese el número ", i, ":"
36. Leer numero_actual
37. Si (numero_actual MOD 2) == 0 Entonces
38. num_pares <- num_pares + 1
39. Sino
40. num_impares <- num_impares + 1
41. Fin Si
42. Fin Para
43.
44. Escribir "Cantidad de números pares: ", num_pares
45. Escribir "Cantidad de números impares: ", num_impares
46. Fin Algoritmo

47. Análisis de complejidad en el peor caso para encontrar mínimo y máximo:

o La complejidad es O(n). El algoritmo debe recorrer toda la lista de n elementos al menos una vez
para garantizar que ha encontrado los valores correctos.
48. Mejor y peor caso para la búsqueda binaria:
o Mejor Caso: Omega(1). El elemento buscado se encuentra en la posición media de la lista en la
primera comparación.
 o Peor Caso: O(logn). El elemento no se encuentra o se encuentra en una de las "hojas" del árbol
de búsqueda. El algoritmo divide la lista a la mitad en cada paso, por lo que la cantidad de
comparaciones es logarítmica.
49. Primeros 5 términos de la secuencia de Fibonacci (f_n=f_n−1+f_n−2, f_0=0,f_1=1):
o f_0=0¡Error! Nombre de archivo no especificado.
o f_1=1¡Error! Nombre de archivo no especificado.
o f_2=f_1+f_0=1+0=1¡Error! Nombre de archivo no especificado.
o f_3=f_2+f_1=1+1=2¡Error! Nombre de archivo no especificado.
o f_4=f_3+f_2=2+1=3¡Error! Nombre de archivo no especificado.
50. Relación de recurrencia para el problema del conejo:
o Si C(n) es el número de conejos al mes n.
o C(n)=C(n−1)+2cdotC(n−1) (los conejos del mes anterior más sus dos crías cada uno).
o C(n)=3cdotC(n−1)¡Error! Nombre de archivo no especificado.
o Condición inicial: C(0)=1 (si se empieza con un conejo).
51. Resuelve a_n=4a_n−1−4a_n−2 con a_0=1,a_1=3:
o Ecuación característica: r2−4r+4=0implies(r−2)2=0. Raíz única r=2.
o Solución general: a_n=A(2)n+Bn(2)n.
o a_0=1implies1=A(2)0+B(0)(2)0implies1=A.
o a_1=3implies3=A(2)1+B(1)(2)1implies3=2A+2B.
o Sustituyendo A=1: 3=2(1)+2Bimplies3=2+2Bimplies1=2BimpliesB=1/2.
o Solución final: a_n=1cdot2n+frac12ncdot2n=2n+ncdot2n−1.
52. Resuelve la relación de recurrencia de Fibonacci: f_n=f_n−1+f_n−2 con f_0=0,f_1=1:
o Ecuación característica: r2−r−1=0.
o Raíces (usando fórmula cuadrática): r=frac−(−1)pmsqrt(−1)2−4(1)
(−1)2(1)=frac1pmsqrt1+42=frac1pmsqrt52.
o r_1=frac1+sqrt52 (conocido como phi, la razón áurea).
o r_2=frac1−sqrt52 (conocido como psi).
o Solución general: f_n=Aleft(frac1+sqrt52right)n+Bleft(frac1−sqrt52right)n.
o Para n=0: f_0=0implies0=A+BimpliesB=−A.
o Para n=1: f_1=1implies1=Aleft(frac1+sqrt52right)+Bleft(frac1−sqrt52right).
o Sustituyendo B=−A: 1=Aleft(frac1+sqrt52right)
−Aleft(frac1−sqrt52right)=Aleft(frac1+sqrt5−(1−sqrt5)2right)=Aleft(frac2sqrt52right)=Asqrt5.
o A=frac1sqrt5. Entonces B=−frac1sqrt5.
o Solución final (Fórmula de Binet):
f_n=frac1sqrt5left(left(frac1+sqrt52right)n−left(frac1−sqrt52right)nright).

Unidad 5: Teoría de grafos, árboles y aplicaciones

1. Grafo con ciclo de Hamilton pero no de Euler:

o Un ejemplo simple es un grafo con 5 vértices (A, B, C, D, E) y aristas que forman un ciclo:
(A,B), (B,C), (C,D), (D,E), (E,A). Este es un ciclo de Hamilton.
o Para que no tenga ciclo de Euler, al menos dos vértices deben tener grado impar. Si añadimos
una arista extra, por ejemplo (A,C), los grados se vuelven: Grado(A)=3, Grado(B)=2,
Grado(C)=3, Grado(D)=2, Grado(E)=2. A y C tienen grado impar, por lo tanto, no tiene ciclo de
Euler.
2. Grafo del cubo y ciclo de Hamilton:
o Sí, el grafo de los vértices de un cubo tiene un ciclo de Hamilton. Se puede recorrer todos los
vértices del cubo una sola vez y volver al punto de partida. Un ejemplo es: (000)-(100)-(110)-
(010)-(011)-(111)-(101)-(001)-(000).
3. Recorridos del árbol binario:
o Árbol: Raíz A, Izq B, Der C. B tiene Izq D. C tiene Izq E, Der F.
 o Preorden (Raíz-Izquierda-Derecha): A, B, D, C, E, F
o Inorden (Izquierda-Raíz-Derecha): D, B, A, E, C, F
o Postorden (Izquierda-Derecha-Raíz): D, B, E, F, C, A
4. Árbol de Expansión Mínimo (MST) usando Kruskal:
o Aristas ordenadas por peso: (A,C,1), (B,C,2), (A,B,4), (B,D,5), (D,E,6), (C,D,8), (C,E,10).
o
1. Añadir (A,C) - Peso 1. (A-C)
o

2. Añadir (B,C) - Peso 2. (A-C-B)

3. Añadir (A,B) - Peso 4. (Formaría ciclo A-C-B-A, NO AÑADIR).

4. Añadir (B,D) - Peso 5. (A-C-B-D)

5. Añadir (D,E) - Peso 6. (A-C-B-D-E)

6. Añadir (C,D) - Peso 8. (Formaría ciclo C-B-D-C, NO AÑADIR).

7. Añadir (C,E) - Peso 10. (Formaría ciclo C-B-D-E-C, NO AÑADIR).

oMST: {(A,C), (B,C), (B,D), (D,E)}. Peso total: 1+2+5+6=14.

5. Camino más corto de C a B usando Dijkstra:
o Camino: C -> B
o Peso total: 2

Unidad 6: Lenguajes, gramáticas y autómatas de estado finito

1. MEF para detectar la cadena de bits "11":

o Estados: S_0 (inicial), S_1 (recibido un '1'), S_2 (recibido "11", estado final).
o Transiciones:
 Desde S_0: '1' toS_1, '0' toS_0.
 Desde S_1: '1' toS_2, '0' toS_0.
 Desde S_2: '0' toS_0, '1' toS_1 (si se permite superposición, un '1' después de "11" puede
ser el inicio de otra "11").
2. Diagrama de transición para la MEF de "11": *
3. MEF para cadenas binarias que terminan en "00":
o Estados: S_0 (inicial), S_1 (recibido un '0'), S_2 (recibido "00", estado final).
o Transiciones:
 Desde S_0: '0' toS_1, '1' toS_0.
 Desde S_1: '0' toS_2, '1' toS_0.
  Desde S_2: '0' toS_2 (si llega otro '0', sigue terminando en "00"), '1' toS_0 (la secuencia
se rompe).
4. Traza de la cadena "10010" en la MEF que termina en "00":
o S_0xrightarrow1S_0¡Error! Nombre de archivo no especificado.
o S_0xrightarrow0S_1¡Error! Nombre de archivo no especificado.
o S_1xrightarrow0S_2 (estado de aceptación)
o S_2xrightarrow1S_0¡Error! Nombre de archivo no especificado.
o S_0xrightarrow0S_1¡Error! Nombre de archivo no especificado.
o Resultado: La MEF termina en S_1. Como S_1 no es un estado de aceptación, la cadena
"10010" no es aceptada. (La cadena "100" sí sería aceptada, pero "10010" no lo es porque no
termina en "00").
5. BNF para expresión aritmética simple:
o <expresion> ::= <termino> | <expresion> "+" <termino> | <expresion> "-"
<termino>
o <termino> ::= <numero>
o <numero> ::= <digito> | <numero><digito>
o <digito> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
6. Cadenas válidas de la gramática <exp> ::= "a" | <exp> "b":
o Las cadenas válidas son:

1. "a"
2. "ab"
3. "abb"
4. "abbb"
5. "abbbb"

o Esta gramática genera cadenas que comienzan con "a" y son seguidas por cero o más "b".