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 p ∧ (r ∨ q)? Haz clic en ella.
p ∧ (r ∨ q)
1(p ∧ r) ∨ (p ∧ q)
2(p ∧ r) ∨ q
3p ∨ (r ∧ q)
4(p ∨ r) ∧ (p ∨ q)
2.Lógica proposicional y demostracionesDifícil
El argumento con premisas r ∨ p; r y conclusión ¬p no es válido. Haz clic en la fila de la tabla de verdad que es un contraejemplo.
r ∨ pr∴ ¬p
1p = 1, r = 1
2p = 1, r = 0
3p = 0, r = 1
4p = 0, r = 0
3.Conjuntos, relaciones y funcionesMedia
R = {(1, 2), (3, 1), (3, 3)} es una relación en {1, 2, 3}. ¿Cuál es el menor número k de pares ordenados que hay que añadir a R para hacerla simétrica?
R = {(1, 2), (3, 1), (3, 3)}
k =
4.Conjuntos, relaciones y funcionesDifícil
Las funciones f y g en {1, 2, 3, 4, 5} vienen dadas por sus tablas. Halla (g ∘ f)(4).
Un árbol tiene 2 vértices de grado 3, 2 vértices de grado 4, 3 vértices de grado 5, 2 vértices de grado 2, y todos sus demás vértices son hojas (grado 1). ¿Cuántas hojas, L, tiene?
2 × deg 32 × deg 43 × deg 52 × deg 2
L =
6.Teoría de grafosDifícil
¿Cuántos recorridos cerrados de longitud 2 empiezan y terminan en A? Un recorrido puede repetir vértices y aristas. Llama al número N.
M = matriz de adyacenciaL = 2
N =
7.Teoría de números y aritmética modularMedia
Halla el inverso de 27 módulo 70: el número x con 0 < x < 70 y 27·x ≡ 1 (mod 70).
a = 27n = 70
27−1 mod 70 =
8.Teoría de números y aritmética modularDifícil
¿Cuántas soluciones, N, tiene 34x ≡ 24 (mod 48) en {0, 1, …, 47}?
34x ≡ 24 (mod 48)
N =
3Disoluciones
1.Lógica proposicional y demostraciones
Respuesta: (p ∧ r) ∨ (p ∧ q)
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
∧ se distribuye sobre ∨: a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c).
p ∧ (r ∨ q) ≡ (p ∧ r) ∨ (p ∧ q)
Comprueba con la tabla de verdad
p = 1, q = 1, r = 1: 1 | 1 1 1 1
p = 1, q = 1, r = 0: 1 | 1 1 1 1
p = 1, q = 0, r = 1: 1 | 1 1 1 1
p = 1, q = 0, r = 0: 0 | 0 0 1 1
p = 0, q = 1, r = 1: 0 | 0 1 1 1
p = 0, q = 1, r = 0: 0 | 0 1 0 0
p = 0, q = 0, r = 1: 0 | 0 0 0 0
p = 0, q = 0, r = 0: 0 | 0 0 0 0
Respuesta
(p ∧ r) ∨ (p ∧ q)
Las columnas después de la barra son las opciones, en el orden mostrado.
2.Lógica proposicional y demostraciones
Respuesta: p = 1, r = 1
Cuantificadores y argumentos: ¬∀x P(x) ≡ ∃x ¬P(x) y ¬∃x P(x) ≡ ∀x ¬P(x). Desplaza la negación hacia dentro, intercambia cada cuantificador que atraviesa y niega la fórmula interior con las leyes proposicionales, como ¬(a → b) ≡ a ∧ ¬b. Un argumento es válido cuando la conclusión vale 1 en todas las filas en las que todas las premisas valen 1. Una sola fila con premisas verdaderas y conclusión falsa es un contraejemplo y demuestra que el argumento no es válido.
Premisas y conclusión fila por fila
p = 1, r = 1: 1 1 | 0
p = 1, r = 0: 1 0 | 0
p = 0, r = 1: 1 1 | 1
p = 0, r = 0: 0 0 | 1
Contraejemplo
p = 1, r = 1
Respuesta
p = 1, r = 1
Un argumento con esta forma parece una regla válida, pero una sola fila basta para demostrar que no lo es.
3.Conjuntos, relaciones y funciones
Respuesta: k = 2
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.
Pares que añadir
{(2, 1), (1, 3)}
Contar
k = 2
Respuesta
k = 2
4.Conjuntos, relaciones y funciones
Respuesta: (g ∘ f)(4) = 2
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.
Función interior
f(4) = 1
Función exterior
g(1) = 2
(g ∘ f)(4) = 2
Respuesta
(g ∘ f)(4) = 2
5.Teoría de grafos
Respuesta: L = 17
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.
Lema del apretón de manos para un árbol
L + 33 = 2(L + 9) − 2
L = 17
Respuesta
L = 17
Atajo: L = 2 + Σ (d − 2) sobre los vértices de grado d ≥ 3.
6.Teoría de grafos
Respuesta: N = 2
Grados: el grado de un vértice es el número de aristas que inciden en él. Cada arista tiene dos extremos, así que los grados suman el doble del número de aristas: Σ gr(v) = 2|E| (el lema del apretón de manos). Por tanto, el número de vértices de grado impar es par. Kn tiene n(n − 1)/2 aristas, un grafo k-regular de n vértices tiene nk/2, y un árbol de n vértices tiene n − 1 aristas.
Matriz de adyacencia
A: 0 1 1 0 0 0
B: 1 0 0 1 0 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 0 1 1 0 1
F: 0 0 0 1 1 0
Vecinos comunes
(M²)AA = 0·0 + 1·1 + 1·1 + 0·0 + 0·0 + 0·0 = 2
Respuesta
N = 2
7.Teoría de números y aritmética modular
Respuesta: 27−1 mod 70 = 13
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·27 (mod 70).
r = 70, t = 0
r = 27, q = 2, t = 1
r = 16, q = 1, t = −2
r = 11, q = 1, t = 3
r = 5, q = 2, t = −5
r = 1, q = 5, t = 13
Inversa
1 ≡ 13·27 (mod 70)
x = 13
comprobación: 27·13 = 351 = 5·70 + 1
Respuesta
27−1 mod 70 = 13
8.Teoría de números y aritmética modular
Respuesta: N = 2
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).