Matemática discreta: pack de repaso

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.

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.

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.

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.

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; K_n 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.

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. K_n 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.

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).

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).