Este tema se resuelve por cálculo y razonamiento verbal, sin depender de figuras. En conjuntos, recuerda que un conjunto con n elementos tiene exactamente 2^n subconjuntos, por lo que la cardinalidad del conjunto potencia es |P(A)| = 2^|A| (un conjunto de 5 elementos tiene 2^5 = 32 subconjuntos). Las leyes de De Morgan aplican tanto a la lógica como a los conjuntos: ¬(p ∧ q) ≡ ¬p ∨ ¬q y ¬(p ∨ q) ≡ ¬p ∧ ¬q. Para dos conjuntos, el principio de inclusión-exclusión da |A ∪ B| = |A| + |B| − |A ∩ B| (si |A|=10, |B|=7 y |A ∩ B|=3, entonces |A ∪ B| = 14).
En combinatoria y conteo distingue si importa el orden y si hay repetición:
El teorema del binomio expresa (x + y)^n = Σ C(n,k) x^(n−k) y^k para k de 0 a n, y la suma de sus coeficientes para un n fijo es 2^n. Una relación de equivalencia es reflexiva, simétrica y transitiva, e induce una partición del conjunto en clases de equivalencia. En lógica, la implicación p → q solo es falsa cuando p es verdadera y q falsa, y equivale a su contrapositiva (p → q ≡ ¬q → ¬p), no a su recíproca ni a su inversa.
En teoría de grafos (analizable desde listas de adyacencia), el lema del apretón de manos afirma que Σ grado(v) = 2|E|; por eso el número de vértices de grado impar siempre es par. La fórmula de Euler para un grafo plano conexo es V − E + F = 2 (cubo: 8 − 12 + 6 = 2), y un árbol con n vértices tiene n − 1 aristas (10 vértices → 9 aristas). En inducción matemática, la suma de Gauss 1 + 2 + ... + n = n(n+1)/2 (para n=100 da 5050), patrón útil también en relaciones de recurrencia. En aritmética modular, a ≡ b (mod m) si y solo si m divide a (a − b); es decir, ambos dejan el mismo residuo al dividirse entre m.
1. Si un conjunto A tiene exactamente 6 elementos, ¿cuántos elementos distintos tiene su conjunto potencia P(A) (es decir, cuántos subconjuntos distintos tiene A)?
|P(A)| = 2^|A|; con |A|=6 resulta 2^6 = 64. Los distractores provienen de errores típicos: 32 usa el exponente n−1, 36 calcula n² en lugar de 2^n, y 63 olvida contar el propio conjunto vacío como subconjunto. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (cardinalidad del conjunto potencia, 2^n).)
2. En teoría de conjuntos, el conjunto potencia P(A) de un conjunto A se define como:
P(A) reúne todos los subconjuntos de A, por lo que su cardinalidad es 2^|A|. Confundirlo con A×A (pares ordenados) o con las permutaciones de A es un error común porque ambos conceptos también crecen con el tamaño de A. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (definición del conjunto potencia).)
3. En una campaña de marketing, una empresa registra que 120 clientes compraron el producto A y 85 clientes compraron el producto B; 35 clientes compraron ambos productos. ¿Cuántos clientes distintos compraron al menos uno de los dos productos?
Por inclusión-exclusión, |A∪B| = |A|+|B|−|A∩B| = 120+85−35 = 170. Sumar sin restar el traslape (205), restarlo dos veces (135) o sumarlo en vez de restarlo (240) son errores típicos de conteo. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conteo (principio de inclusión-exclusión).)
4. La diferencia de conjuntos A − B se define como el conjunto de elementos que:
A−B contiene únicamente los elementos de A que quedan fuera de B. La opción 'en A o en B pero no en ambos' describe en realidad la diferencia simétrica, no la diferencia simple. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (operaciones entre conjuntos: diferencia).)
5. La diferencia simétrica entre dos conjuntos A y B, denotada A ⊕ B, corresponde al conjunto formado por:
La diferencia simétrica A⊕B reúne los elementos que están en A∪B pero no en A∩B, es decir, en un conjunto o en el otro pero no en ambos. Describir solo la unión (A∪B) ignora la exclusión de los elementos compartidos, y A−B corresponde a la diferencia simple. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (diferencia simétrica).)
6. Aplicando las leyes de De Morgan a conjuntos, el complemento de la unión (A ∪ B)' es igual a:
(A ∪ B)' = A' ∩ B', de forma análoga a la ley de De Morgan de la lógica proposicional ¬(p∨q) ≡ ¬p∧¬q. La opción A'∪B' corresponde en realidad al complemento de la intersección, (A∩B)'. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones / Lógica proposicional (leyes de De Morgan).)
7. Una base de datos de 500 registros de clientes se audita: 80 registros tienen correo electrónico inválido, 54 tienen teléfono inválido, y 12 registros tienen ambos datos inválidos. ¿Cuántos registros tienen tanto el correo como el teléfono válidos?
Los registros con algún dato inválido son |A∪B| = 80+54−12 = 122, por lo que los válidos en ambos campos son 500−122 = 378. Restar 80 y 54 directamente de 500 (366) resta el traslape dos veces, sumarlo en vez de restarlo da 354, y 122 responde la pregunta inversa. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conteo (principio de inclusión-exclusión aplicado a conjuntos complementarios).)
8. Si A es un conjunto de 4 elementos y B es un conjunto de 7 elementos, ¿cuántos elementos tiene el producto cartesiano A × B?
|A×B| = |A|·|B| = 4×7 = 28. Sumar en lugar de multiplicar (11) o restar (3) son errores comunes al confundir el producto cartesiano con la unión o la diferencia de conjuntos. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (producto cartesiano).)
9. ¿Cuál de las siguientes afirmaciones sobre el conjunto vacío (∅) es FALSA?
∅ ∪ A siempre es igual a A, no a ∅, por lo que esa afirmación es falsa. Las otras tres son propiedades verdaderas y bien conocidas del conjunto vacío. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conjuntos y funciones (propiedades del conjunto vacío).)
10. Según el lema del apretón de manos (handshaking lemma), en cualquier grafo no dirigido, la suma de los grados de todos los vértices es igual a:
El lema establece que Σ grado(v) = 2|E|, es decir, el doble del número de aristas, porque cada arista aporta un grado a cada uno de sus dos vértices extremos. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Grafos (lema del apretón de manos).)
11. Un grafo no dirigido G tiene la siguiente lista de adyacencia: v1: {v2, v3}; v2: {v1, v3, v4}; v3: {v1, v2, v4, v5}; v4: {v2, v3, v5}; v5: {v3, v4}. ¿Cuántas aristas tiene G?
Los grados son 2, 3, 4, 3 y 2, cuya suma es 14; por el lema del apretón de manos, el número de aristas es 14/2 = 7. Responder 14 es olvidar dividir la suma de grados entre dos, y 5 confunde el resultado con el número de vértices. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Grafos (lema del apretón de manos aplicado a listas de adyacencia).)
12. Una red de comunicación con 8 nodos es conexa (existe una ruta entre cualesquiera dos nodos) y su lista de adyacencia muestra un total de 8 aristas. ¿Qué se puede concluir sobre esta red?
Un árbol de n=8 vértices tiene exactamente n−1=7 aristas; como esta red conexa tiene 8 aristas (una más de las permitidas para un árbol), necesariamente contiene al menos un ciclo. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Árboles (n−1 aristas).)
13. En teoría de grafos, un árbol se define como un grafo que es:
Un árbol es, por definición, un grafo conexo y acíclico. Esta propiedad implica que tiene exactamente n−1 aristas para n vértices, a diferencia de un grafo con ciclos o uno no conexo. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Árboles (definición de árbol).)
14. En todo grafo simple no dirigido con n ≥ 2 vértices, aplicando el principio del palomar a los posibles valores de grado (0 a n−1, sabiendo que un vértice de grado 0 y uno de grado n−1 no pueden coexistir), se puede garantizar que:
Como los n vértices solo pueden tomar, en la práctica, n−1 valores posibles de grado, el principio del palomar obliga a que al menos dos vértices compartan grado. La suma de los grados nunca es impar, pues por el lema del apretón de manos siempre equivale a 2|E|. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Conteo (principio del palomar) aplicado a Grafos.)
15. ¿Cuál de las siguientes secuencias de grados NO puede corresponder a la lista de adyacencia de un grafo no dirigido, de acuerdo con el lema del apretón de manos?
La suma de {1,2,2,4} es 9, un número impar, lo cual viola el lema del apretón de manos, que exige que la suma de grados sea siempre par (2|E|). Las otras tres secuencias suman 8, 6 y 12, todas pares y por tanto posibles. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Grafos (corolario del lema del apretón de manos: la suma de grados es siempre par).)
16. Un grafo no dirigido tiene la siguiente lista de adyacencia: P: {Q, R}; Q: {P, R, S}; R: {P, Q, S}; S: {Q, R}. ¿Cuál es el grado del vértice R?
R aparece conectado a P, Q y S en la lista de adyacencia, por lo que su grado es 3. Contar a R como su propio vecino llevaría erróneamente a 4. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Grafos (grado de un vértice a partir de la lista de adyacencia).)
17. En un grafo no dirigido, la relación 'existe una ruta entre estos dos vértices' es una relación de equivalencia sobre el conjunto de vértices porque cumple las propiedades de:
Al cumplir las tres propiedades, la relación de conectividad particiona los vértices en componentes conexas disjuntas, que son las clases de equivalencia de esa relación. Omitir cualquiera de las tres propiedades describiría una relación distinta a la de equivalencia. (Richard Johnsonbaugh, Matemáticas discretas (Pearson), capítulo de Relaciones (relación de equivalencia) aplicado a componentes conexas de grafos.)
18. Un grafo plano conexo con forma de cubo (el mismo ejemplo clásico usado para ilustrar la fórmula de Euler) tiene 8 vértices y 6 caras, incluyendo la cara exterior. ¿Cuántas aristas tiene, según la fórmula V − E + F = 2?
Despejando E de V−E+F=2 se obtiene E = V+F−2 = 8+6−2 = 12. Sumar V y F sin restar 2 (14) es el error más común al despejar la fórmula, mientras que 6 y 8 solo repiten los datos de caras y vértices. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Grafos planos (fórmula de Euler, ejemplo del cubo).)
19. Se dice que a es congruente con b módulo m (a ≡ b mod m) si y solo si:
La definición de congruencia establece que m | (a−b), es decir, que a y b dejan el mismo residuo al dividirse entre m. La opción que invierte la divisibilidad, '(a−b) divide a m', es un error común de dirección. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (definición de congruencia).)
20. Un sistema distribuye tareas entre 6 procesadores numerados del 0 al 5, asignando la tarea número k al procesador (k mod 6). ¿A qué procesador se asigna la tarea número 47?
47 = 6×7+5, por lo que 47 mod 6 = 5. Responder 7 confunde el residuo con el cociente, y responder 6 es imposible porque el residuo siempre debe ser menor que el módulo. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (congruencias, cálculo de residuos).)
21. Si a ≡ b (mod m) y c ≡ d (mod m), ¿cuál de las siguientes propiedades de la aritmética modular es válida?
La aritmética modular preserva la suma y el producto, de modo que a·c ≡ b·d (mod m). No preserva, en general, la división, ni permite multiplicar el módulo por c. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (propiedades de las congruencias).)
22. En una tabla hash con 13 posiciones, la función h(k) = k mod 13 asigna tanto la clave 100 como la clave 139 a la posición 9, provocando una colisión. ¿Qué relación matemática explica esta colisión?
Como 139−100=39=13×3, se cumple que 13 divide a esa diferencia, es decir, 100 ≡ 139 (mod 13). Por eso ambas claves caen en la misma posición de la tabla hash. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (congruencias aplicadas a funciones hash).)
23. ¿Cuál es el valor de x, con 0 ≤ x ≤ 6, que satisface la congruencia 3x ≡ 1 (mod 7)?
Con x=5, 3×5=15=2×7+1, por lo que 15 ≡ 1 (mod 7), cumpliendo la congruencia. Los demás valores no funcionan: por ejemplo, 3×4=12 ≡ 5 (mod 7), no 1. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (inverso multiplicativo módulo m).)
24. Si hoy es lunes, ¿qué día de la semana será dentro de 100 días, sabiendo que los días se repiten cada 7 días (aritmética módulo 7)?
100 mod 7 = 2 (pues 100 = 7×14+2), así que se avanzan 2 días desde el lunes, resultando en miércoles. Responder domingo equivale a suponer erróneamente que 100 es múltiplo exacto de 7. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (aplicaciones de la aritmética modular).)
25. Un sistema de control de inventario considera válido un código C si cumple C ≡ 0 (mod 9). Para el código C = 2457, ¿el código es válido?
La suma de los dígitos de 2457 (2+4+5+7=18) es múltiplo de 9, por lo que 2457 ≡ 0 (mod 9) y el código es válido. La paridad del número no tiene relación alguna con este criterio de validación. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números (congruencias, criterio de divisibilidad entre 9).)
26. Las clases de congruencia módulo 5 (conjuntos de enteros que dejan el mismo residuo al dividirse entre 5) forman una partición del conjunto de los números enteros. ¿Cuántas clases de equivalencia distintas existen módulo 5?
Los residuos posibles al dividir entre 5 son 0, 1, 2, 3 y 4, lo que da exactamente 5 clases de equivalencia distintas. Olvidar el residuo 0 lleva erróneamente a contar solo 4 clases. (Richard Johnsonbaugh, Matemáticas discretas (Pearson), capítulo de Relaciones (relación de equivalencia) aplicado a clases de congruencia módulo m.)
27. En matemáticas discretas, se dice que una relación binaria R definida sobre un conjunto A es una relación de equivalencia cuando cumple simultáneamente tres propiedades. ¿Cuáles son esas tres propiedades?
Una relación es de equivalencia si y solo si es reflexiva, simétrica y transitiva, lo que induce una partición del conjunto en clases de equivalencia; sustituir 'simétrica' por 'antisimétrica' describe en cambio una relación de orden. (Richard Johnsonbaugh, Matemáticas discretas (Pearson), capítulo de Relaciones (relaciones de equivalencia).)
28. Un programador diseña una función hash simple para distribuir claves enteras en 5 charolas (buckets) de una tabla hash, asignando a cada clave k la charola k mod 5. Para agrupar como equivalentes a las claves que caen en la misma charola, se apoya en la relación 'a R b si y solo si a ≡ b (mod 5)'. ¿Qué condición aritmética exacta define esta congruencia entre a y b?
Por definición, a ≡ b (mod m) equivale a que m divida a (a − b); no se requiere que a y b sean múltiplos de 5 ni que compartan cantidad de dígitos, sino que dejen el mismo residuo al dividirse entre 5. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Teoría de números / Congruencias.)
29. Dadas dos funciones f: A → B y g: B → C, la composición (g ∘ f): A → C se define para cada elemento x de A mediante la expresión...
La composición (g ∘ f) aplica primero f y después g, por lo que (g ∘ f)(x) = g(f(x)); invertir el orden como en f(g(x)) corresponde a la composición (f ∘ g), que en general es distinta. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Funciones (composición de funciones).)
30. En el diseño de una base de datos, un ingeniero define una función que asigna a cada empleado su número de cuenta bancaria; ningún número de cuenta se repite entre dos empleados distintos, pero existen números de cuenta válidos del banco que todavía no han sido asignados a ningún empleado. ¿Qué tipo de función describe mejor esta asignación?
Como ningún par de empleados comparte cuenta, la función es inyectiva; como existen cuentas válidas sin asignar, no cubre todo el codominio y por lo tanto no es sobreyectiva ni, en consecuencia, biyectiva. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Funciones (funciones inyectivas y sobreyectivas).)
31. Para que una función f: A → B tenga una función inversa f⁻¹: B → A tal que f⁻¹(f(a)) = a para todo a en A y f(f⁻¹(b)) = b para todo b en B, ¿qué condición debe cumplir f?
Solo una función biyectiva garantiza que cada elemento del codominio tenga exactamente una preimagen, condición necesaria y suficiente para definir f⁻¹ en todo B; ser solo inyectiva o solo sobreyectiva no es suficiente. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Funciones (función inversa).)
32. Se define una relación R sobre el conjunto de todas las cadenas de caracteres de un lenguaje de programación, donde una cadena s1 está relacionada con s2 si y solo si s1 y s2 tienen la misma longitud. ¿Qué propiedad de las relaciones garantiza que toda cadena esté relacionada consigo misma?
La propiedad reflexiva exige que todo elemento se relacione consigo mismo, lo cual se cumple aquí porque toda cadena tiene la misma longitud que ella misma; simetría y transitividad describen otras condiciones de la relación. (Richard Johnsonbaugh, Matemáticas discretas (Pearson), capítulo de Relaciones (propiedad reflexiva).)
33. Un programador necesita que, para cada entero x, primero se calcule x² y después se sume 1 al resultado; es decir, requiere aplicar la composición f(g(x)) donde g(x) = x² y f(x) = x + 1. Por un error en el orden de las llamadas, su código calcula g(f(x)) en lugar de f(g(x)). Con la entrada de prueba x = 3, ¿qué valor entero debió haber obtenido con la composición correcta f(g(x))?
f(g(3)) = f(9) = 10; en cambio, el orden invertido g(f(3)) = g(4) = 16 confirma que la composición de funciones no es conmutativa. Los valores 9 y 4 corresponden a aplicar una sola de las dos funciones y detenerse ahí. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Funciones (composición de funciones).)
34. Si f: A → B es una función biyectiva y f⁻¹ es su función inversa, ¿qué resulta de la composición f⁻¹ ∘ f?
Por definición de inversa, (f⁻¹ ∘ f)(a) = a para todo a en A, es decir, se obtiene la función identidad sobre el dominio A; la identidad sobre B correspondería más bien a la composición f ∘ f⁻¹. (Kenneth H. Rosen, Matemáticas discretas y sus aplicaciones (McGraw-Hill), capítulo de Funciones (función inversa).)
35. ¿Cuál de las siguientes relaciones definidas sobre el conjunto de los números enteros NO es una relación de equivalencia?
La relación 'a es menor que b' no es reflexiva (a no es menor que a) ni simétrica, por lo que no es de equivalencia; la congruencia módulo 4, la igualdad y la relación 'a − b es múltiplo de 3' sí cumplen las tres propiedades requeridas. (Richard Johnsonbaugh, Matemáticas discretas (Pearson), capítulo de Relaciones (relaciones de equivalencia).)