Dibuja un diagrama de Venn y decide región por región qué pertenece a la expresión de conjuntos.
En los problemas de recuento, rellena las regiones desde el centro hacia fuera: primero todos los conjuntos, luego los pares, después los conjuntos sueltos y por último el exterior.
Usa la inclusión–exclusión como comprobación: |A ∪ B| = |A| + |B| − |A ∩ B|.
En una relación, comprueba cada propiedad en todos los pares y da un contraejemplo cuando falle.
En una función, cuenta las flechas que llegan a cada elemento de B: como mucho una significa inyectiva, al menos una, sobreyectiva.
Teoría de grafos
Lema del apretón de manos
Σ deg(v) = 2|E|
Grafos completos
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regular
|E| = n·k/2
Árbol y bosque
|E| = n − 1, |E| = n − c
Hojas de un árbol
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuito: todos los grados pares; camino: exactamente 2 grados impares
Circuitos de Hamilton en Kn
(n − 1)!/2
Actualización de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Recorridos de longitud L
(Mᴸ)ij
Método
Anota el grado de cada vértice; los grados suman el doble del número de aristas.
En las preguntas de Euler, comprueba que el grafo sea conexo y cuenta los vértices de grado impar.
En los árboles, usa n − 1 aristas y el lema del apretón de manos.
En Dijkstra, lleva una tabla de distancias provisionales y fija en cada ronda el vértice no fijado de menor distancia.
Para un árbol generador mínimo, ordena las aristas por peso y descarta toda arista que cierre un ciclo (Kruskal), o haz crecer un único árbol desde un vértice inicial (Prim).
Teoría de números y aritmética modular
División con resto
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Mínimo común múltiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruencia lineal
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Función φ de Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Método
Reduce primero cada número módulo n; los restos están entre 0 y n − 1.
Para un mcd, divide repetidamente con el algoritmo de Euclides; el último resto distinto de cero es el mcd.
Para un inverso, aplica el algoritmo extendido y quédate con el coeficiente de a; suma n si es negativo.
Resuelve a·x ≡ b multiplicando por a⁻¹; combina dos congruencias escribiendo x = r₁ + m₁k.
Para las potencias, escribe el exponente en binario y eleva al cuadrado repetidamente; en RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
2Problemas de práctica
1.Lógica proposicional y demostracionesMedia
Quieres demostrar ¬c → (b ∨ a) por contrarrecíproca. ¿Qué implicación demuestras en su lugar? Haz clic en ella.
¬c → (b ∨ a)
1¬c ∧ ¬(b ∨ a)
2(b ∨ a) → ¬c
3¬(b ∨ a) → ¬¬c
4¬¬c → ¬(b ∨ a)
2.Lógica proposicional y demostracionesDifícil
¿Cuántas de las 16 filas de la tabla de verdad hacen verdadera (¬a → (b → d)) ∧ ¬(c ∨ a)? Llama a ese número N.
(¬a → (b → d)) ∧ ¬(c ∨ a)
N =
3.Conjuntos, relaciones y funcionesMedia
En un grupo de 83 estudiantes, 33 hablan francés (F), 41 hablan alemán (G) y 42 hablan español (S). 17 hablan francés y alemán, 18 francés y español, 14 alemán y español, y 4 hablan los tres. ¿Cuántos no están en ninguno de los tres conjuntos?
|U| = 83
|(F ∪ G ∪ S)′| =
4.Conjuntos, relaciones y funcionesDifícil
El diagrama de flechas muestra una función f: A → B con A = {1, 2, 3, 4} y B = {a, b}. Haz clic en la descripción que corresponde a f.
f = {(1, a), (2, b), (3, a), (4, b)}
1inyectiva, no sobreyectiva
2sobreyectiva, no inyectiva
3biyectiva
4ninguna de las dos
5.Teoría de grafosMedia
¿Tiene el grafo conexo un circuito euleriano, un camino euleriano que no es un circuito, o ninguno de los dos? Haz clic en tu respuesta.
|V| = 6|E| = 8
1Circuito euleriano
2Camino euleriano, sin circuito
3ninguna de las dos
6.Teoría de grafosDifícil
Halla el peso total W de un árbol generador mínimo del grafo ponderado.
|V| = 7|E| = 10
W =
7.Teoría de números y aritmética modularMedia
Halla el inverso de 50 módulo 67: el número x con 0 < x < 67 y 50·x ≡ 1 (mod 67).
a = 50n = 67
50−1 mod 67 =
8.Teoría de números y aritmética modularDifícil
Resuelve 16x ≡ 12 (mod 30). Da la menor solución positiva x.
16x ≡ 12 (mod 30)
x =
3Disoluciones
1.Lógica proposicional y demostraciones
Respuesta: ¬(b ∨ a) → ¬¬c
Equivalencia lógica: dos fórmulas son equivalentes (≡) cuando tienen el mismo valor en todas las filas de la tabla de verdad. Una tautología vale 1 en todas las filas, una contradicción vale 0 en todas las filas, y una contingencia no es ninguna de las dos. Leyes útiles: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b y ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrarrecíproca); ¬(a → b) ≡ a ∧ ¬b; y las leyes distributivas, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Partes de la implicación
a = ¬c, b = b ∨ a
Contrarrecíproca
¬b → ¬a = ¬(b ∨ a) → ¬¬c
Respuesta
¬(b ∨ a) → ¬¬c
La contrarrecíproca es equivalente al enunciado original, así que demostrarla demuestra el enunciado.
2.Lógica proposicional y demostraciones
Respuesta: N = 3
Tablas de verdad: una fórmula con n variables distintas tiene 2ⁿ filas, una por cada combinación de valores de verdad (1 = verdadero, 0 = falso). Trabaja de dentro hacia fuera y dale a cada subfórmula su propia columna. ¬a invierte el valor; a ∧ b vale 1 solo cuando ambos son 1; a ∨ b vale 0 solo cuando ambos son 0; a → b vale 0 solo cuando a = 1 y b = 0; a ↔ b vale 1 cuando ambos lados son iguales.
Columnas
¬a; b → d; ¬a → (b → d); c ∨ a; ¬(c ∨ a); (¬a → (b → d)) ∧ ¬(c ∨ a)
Divide según a
a = 1: 0
a = 0: 3
N = 0 + 3 = 3
Respuesta
N = 3
3.Conjuntos, relaciones y funciones
Respuesta: |(F ∪ G ∪ S)′| = 12
Conjuntos y diagramas de Venn: A ∪ B contiene los elementos que están en A o en B (o en ambos), A ∩ B los elementos que están en ambos, A − B los elementos de A que no están en B, y el complemento A′ todo lo de U que no está en A. En un diagrama de Venn toda expresión de conjuntos es una unión de regiones, así que cuéntala región por región. Inclusión–exclusión: |A ∪ B| = |A| + |B| − |A ∩ B|, y |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Centro y pares
F ∩ G ∩ S: 4
F ∩ G solo: 17 − 4 = 13
F ∩ S solo: 18 − 4 = 14
G ∩ S solo: 14 − 4 = 10
Conjuntos sueltos
F solo: 33 − 13 − 14 − 4 = 2
G solo: 41 − 13 − 10 − 4 = 14
S solo: 42 − 14 − 10 − 4 = 14
Respuesta
|F ∪ G ∪ S| = 71
|(F ∪ G ∪ S)′| = 83 − 71 = 12
Respuesta
|(F ∪ G ∪ S)′| = 12
4.Conjuntos, relaciones y funciones
Respuesta: sobreyectiva, no inyectiva
Funciones y recuento: una función f: A → B da a cada elemento de A exactamente una imagen en B. f es inyectiva (uno a uno) cuando elementos distintos tienen imágenes distintas, sobreyectiva cuando todo elemento de B es una imagen, y biyectiva cuando se cumplen ambas. Con |A| = m y |B| = n hay nᵐ funciones, n!/(n − m)! inyectivas (m ≤ n) y, por inclusión–exclusión, Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ sobreyectivas. |𝒫(A)| = 2ᵐ y |A × B| = m·n.
¿Inyectiva?
f(1) = f(3) = a → no inyectiva
¿Sobreyectiva?
todo elemento de B recibe alguna flecha → sobreyectiva
Respuesta
sobreyectiva, no inyectiva
Respuesta
sobreyectiva, no inyectiva
5.Teoría de grafos
Respuesta: Camino euleriano, sin circuito
Euler, Hamilton y árboles: un grafo conexo tiene un circuito euleriano (cada arista una vez, volviendo al inicio) cuando todos los vértices tienen grado par, y un camino euleriano que no es un circuito cuando exactamente dos vértices tienen grado impar; entonces el camino va de un vértice impar al otro. Un circuito hamiltoniano visita cada vértice una vez; Kn tiene (n − 1)!/2 de ellos. Un árbol de n vértices tiene n − 1 aristas, y un grafo conexo con m aristas conserva un árbol generador tras quitarle m − n + 1 aristas.
El camino euleriano empieza en un vértice impar y termina en el otro.
6.Teoría de grafos
Respuesta: W = 29
Caminos mínimos y árboles generadores: el algoritmo de Dijkstra fija un vértice por ronda: el vértice no fijado con la menor distancia provisional. Su distancia es entonces definitiva, y cada vecino v recibe d(v) = min(d(v), d(u) + w(u, v)). El algoritmo de Kruskal construye un árbol generador mínimo tomando las aristas de la más ligera a la más pesada y descartando toda arista que cierre un ciclo; el algoritmo de Prim hace crecer un único árbol desde un vértice inicial añadiendo siempre la arista más ligera que sale de él. Un árbol generador de n vértices tiene n − 1 aristas.
Algoritmo de Kruskal
DF (1): tomar
AC (2): tomar
GE (3): tomar
EF (5): tomar
BC (6): tomar
DE (7): descartar, cierra un ciclo
CE (12): tomar
Peso total
W = 1 + 2 + 3 + 5 + 6 + 12 = 29
Respuesta
W = 29
7.Teoría de números y aritmética modular
Respuesta: 50−1 mod 67 = 63
Inversos y congruencias: a tiene inverso módulo n exactamente cuando mcd(a, n) = 1. El algoritmo de Euclides extendido escribe 1 = s·n + t·a, y entonces a⁻¹ ≡ t (mod n). Una congruencia a·x ≡ b (mod n) con mcd(a, n) = 1 tiene la solución x ≡ a⁻¹·b. Dos congruencias x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂) con módulos coprimos tienen una solución módulo m₁·m₂ (teorema chino del resto). La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(n) = n·∏(1 − 1/p).
Algoritmo de Euclides extendido
Cada resto r se escribe como r ≡ t·50 (mod 67).
r = 67, t = 0
r = 50, q = 1, t = 1
r = 17, q = 2, t = −1
r = 16, q = 1, t = 3
r = 1, q = 16, t = −4
Inversa
1 ≡ −4·50 (mod 67)
x = 63
comprobación: 50·63 = 3150 = 47·67 + 1
Respuesta
50−1 mod 67 = 63
8.Teoría de números y aritmética modular
Respuesta: x = 12
Inversos y congruencias: a tiene inverso módulo n exactamente cuando mcd(a, n) = 1. El algoritmo de Euclides extendido escribe 1 = s·n + t·a, y entonces a⁻¹ ≡ t (mod n). Una congruencia a·x ≡ b (mod n) con mcd(a, n) = 1 tiene la solución x ≡ a⁻¹·b. Dos congruencias x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂) con módulos coprimos tienen una solución módulo m₁·m₂ (teorema chino del resto). La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(n) = n·∏(1 − 1/p).