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
¿Qué fórmula es lógicamente equivalente a c → b? Haz clic en ella.
c → b
1¬c ∧ b
2b → c
3¬c ∨ b
4¬c → ¬b
2.Lógica proposicional y demostracionesDifícil
¿Cuántas de las 16 filas de la tabla de verdad hacen verdadera ((q ∨ r) ∨ p) ↔ (s → r)? Llama a ese número N.
((q ∨ r) ∨ p) ↔ (s → r)
N =
3.Conjuntos, relaciones y funcionesMedia
La relación R en {1, 2, 3} se dibuja como un grafo dirigido (un lazo significa (x, x) ∈ R). Se cumple exactamente una de las cuatro propiedades. Haz clic en ella.
En X = {1, 2, …, 10} la relación R se cumple cuando x ≡ y (mod 5). ¿Cuántos pares ordenados contiene R? Llama al número |R|.
X = {1, …, 10}x R y ⟺ 5 | (x − y)
|R| =
5.Teoría de grafosMedia
¿Cuántos circuitos de Hamilton distintos, H, tiene el grafo completo K5? Los circuitos que solo difieren en el vértice inicial o en el sentido cuentan como el mismo.
K5
H =
6.Teoría de grafosDifícil
El algoritmo de Dijkstra se ejecuta desde A. Haz clic en el vértice que se fija (se hace permanente) en la ronda 4; la propia A es la ronda 1.
inicio: Aronda 4
1A
2B
3C
4D
5E
6F
7.Teoría de números y aritmética modularMedia
Halla el inverso de 9 módulo 11: el número x con 0 < x < 11 y 9·x ≡ 1 (mod 11).
a = 9n = 11
9−1 mod 11 =
8.Teoría de números y aritmética modularDifícil
Cifra el mensaje m = 192 con la clave pública RSA (n, e) = (1073, 17). Halla el texto cifrado c.
n = 1073e = 17m = 192
c =
3Disoluciones
1.Lógica proposicional y demostraciones
Respuesta: ¬c ∨ b
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).
La ley
a → b vale 0 solo cuando a = 1 y b = 0, así que es lo mismo que ¬a ∨ b.
c → b ≡ ¬c ∨ b
Comprueba con la tabla de verdad
b = 1, c = 1: 1 | 0 1 1 1
b = 1, c = 0: 1 | 1 0 1 0
b = 0, c = 1: 0 | 0 1 0 1
b = 0, c = 0: 1 | 0 1 1 1
Respuesta
¬c ∨ b
Las columnas después de la barra son las opciones, en el orden mostrado.
2.Lógica proposicional y demostraciones
Respuesta: N = 12
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
q ∨ r; (q ∨ r) ∨ p; s → r; ((q ∨ r) ∨ p) ↔ (s → r)
Divide según p
p = 1: 6
p = 0: 6
N = 6 + 6 = 12
Respuesta
N = 12
3.Conjuntos, relaciones y funciones
Respuesta: reflexiva
Relaciones: una relación R en un conjunto X es un conjunto de pares ordenados (x, y). R es reflexiva cuando (x, x) ∈ R para todo x de X; simétrica cuando (x, y) ∈ R siempre va acompañado de (y, x) ∈ R; antisimétrica cuando (x, y) y (y, x) están ambos en R solo si x = y; y transitiva cuando (x, y) y (y, z) en R obligan a que (x, z) ∈ R. Una relación de equivalencia es reflexiva, simétrica y transitiva, y divide X en clases disjuntas.
reflexiva
se cumple
simétrica
falla: (1, 3) ∈ R, (3, 1) ∉ R
antisimétrica
falla: (1, 2), (2, 1) ∈ R
transitiva
falla: (2, 1), (1, 3) ∈ R, (2, 3) ∉ R
Respuesta
reflexiva
4.Conjuntos, relaciones y funciones
Respuesta: |R| = 20
Relaciones: una relación R en un conjunto X es un conjunto de pares ordenados (x, y). R es reflexiva cuando (x, x) ∈ R para todo x de X; simétrica cuando (x, y) ∈ R siempre va acompañado de (y, x) ∈ R; antisimétrica cuando (x, y) y (y, x) están ambos en R solo si x = y; y transitiva cuando (x, y) y (y, z) en R obligan a que (x, z) ∈ R. Una relación de equivalencia es reflexiva, simétrica y transitiva, y divide X en clases disjuntas.
Clases
resto 0: 2
resto 1: 2
resto 2: 2
resto 3: 2
resto 4: 2
Pares
|R| = 2² + 2² + 2² + 2² + 2² = 20
Respuesta
|R| = 20
5.Teoría de grafos
Respuesta: H = 12
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.
Contar
H = (5 − 1)!/2 = 24/2 = 12
Respuesta
H = 12
6.Teoría de grafos
Respuesta: E
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.
Dijkstra ronda a ronda
1. A (0): B: 12, C: 1
2. C (1): E: 16
3. B (12)
4. E (16): D: 20, F: 28
5. D (20): F: 21
6. F (21)
ronda 4
E
Respuesta
E
7.Teoría de números y aritmética modular
Respuesta: 9−1 mod 11 = 5
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·9 (mod 11).
r = 11, t = 0
r = 9, q = 1, t = 1
r = 2, q = 4, t = −1
r = 1, q = 2, t = 5
Inversa
1 ≡ 5·9 (mod 11)
x = 5
comprobación: 9·5 = 45 = 4·11 + 1
Respuesta
9−1 mod 11 = 5
8.Teoría de números y aritmética modular
Respuesta: c = 867
Potencias modulares y RSA: calcula aᵏ mod n por cuadrado repetido: escribe k en binario, eleva al cuadrado, reduce después de cada paso y multiplica las potencias cuyo bit es 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) para un primo p que no divide a a, así que el exponente se puede reducir módulo p − 1. RSA: elige los primos p y q, n = p·q y φ(n) = (p − 1)(q − 1); el exponente público e es coprimo con φ(n), y el exponente privado es d = e⁻¹ mod φ(n). Cifra con c = mᵉ mod n y descifra con m = cᵈ mod n.