Inicio · Parte 04
Lógica, conjuntos, conteo, inducción, recurrencias, grafos y aritmética modular: la matemática que hace demostrable un programa.
La matemática discreta es la que trata objetos separados y contables —proposiciones, conjuntos, grafos, enteros— frente a la continua, que trata magnitudes que fluyen. Es la matemática nativa de la computación, porque un ordenador es un objeto discreto: estados finitos, memoria numerable, pasos separados.
Las clases 081 a 083 son lógica. Su valor no es filosófico sino operativo: una implicación es equivalente a su contrarrecíproca pero no a su recíproca, y confundirlas es el error de razonamiento más caro que existe —en matemáticas y fuera de ellas—. El orden de los cuantificadores cambia el significado: «para todo x existe un y» y «existe un y para todo x» son afirmaciones distintas, y esa distinción reaparece en las definiciones de convergencia (parte 07) y en las cotas de aprendizaje (parte 17).
Las clases 084 a 090 construyen el conteo. El principio del producto, las permutaciones, las combinaciones y el principio del palomar son la base sobre la que la parte 09 define la probabilidad: un espacio muestral equiprobable convierte cada probabilidad en un cociente de conteos. El palomar (clase 090) merece atención especial porque demuestra que las colisiones de hash existen sin construir ninguna.
Las clases 091 y 092 son inducción y recurrencias: cómo demostrar algo sobre infinitos casos con dos pasos, y cómo analizar un algoritmo que se llama a sí mismo. La inducción es literalmente un bucle for con garantía, y la recurrencia es lo que hace que Fibonacci ingenuo tarde exponencialmente y memoizado tarde linealmente.
Las clases 093 a 096 son teoría de grafos. Un grafo es la estructura más versátil de la computación: modela dependencias, redes, rutas, jerarquías y —esto importa— los grafos de cómputo sobre los que se ejecuta la autodiferenciación. El orden topológico de la clase 096 es exactamente el orden en que un framework de deep learning recorre las operaciones al propagar gradientes.
El cierre (097 a 099) es álgebra booleana y aritmética modular, la base del hardware digital y de la criptografía. El capstone monta un planificador de dependencias que detecta ciclos y calcula qué tareas pueden ejecutarse en paralelo, que es el problema real de cualquier sistema de construcción.
| # | Clase | Demostración ejecutable |
|---|---|---|
081 |
Lógica proposicional | propositional_logic |
082 |
Tablas de verdad y equivalencias | truth_tables |
083 |
Lógica de predicados y cuantificadores | predicate_logic |
084 |
Conjuntos y operaciones | sets |
085 |
Relaciones y propiedades | relations |
086 |
Funciones discretas | discrete_functions |
087 |
Principios de conteo | counting_principles |
088 |
Permutaciones | permutations_demo |
089 |
Combinaciones | combinations_demo |
090 |
Principio del palomar | pigeonhole |
091 |
Inducción matemática | induction |
092 |
Recurrencias | recurrences |
093 |
Grafos: vértices y aristas | graphs |
094 |
Caminos, ciclos y conectividad | paths_connectivity |
095 |
Árboles y árboles de expansión | trees |
096 |
DAG y orden topológico | topological_order |
097 |
Álgebra booleana | boolean_algebra |
098 |
Aritmética modular | modular_arithmetic |
099 |
Números primos y máximo común divisor | primes_gcd |
100 |
Capstone: modelar dependencias con grafos | capstone_dependency_graph |
compmath run --part 04| Término | Definición | Clase |
|---|---|---|
| Implicación | p → q, falsa solo cuando p es verdadera y q falsa. Equivale a su contrarrecíproca, no a su recíproca. | 081 |
| Contrarrecíproca | ¬q → ¬p. Lógicamente equivalente a p → q, y a menudo más fácil de demostrar. | 081 |
| Tautología | Fórmula verdadera bajo toda asignación de valores de verdad. | 082 |
| Leyes de De Morgan | ¬(p∧q) ≡ ¬p∨¬q y ¬(p∨q) ≡ ¬p∧¬q. Rigen la negación de condiciones compuestas. | 082 |
| Cuantificador universal | ∀x P(x): P se cumple para todo elemento del universo. Su negación es ∃x ¬P(x). | 083 |
| Inclusión-exclusión | |A∪B| = |A| + |B| − |A∩B|. Corrige el doble conteo de la intersección. | 084 |
| Relación de equivalencia | Relación reflexiva, simétrica y transitiva. Particiona el conjunto en clases disjuntas. | 085 |
| Función inyectiva | Entradas distintas dan salidas distintas. Condición necesaria para que exista inversa. | 086 |
| Regla del producto | Si una decisión tiene m opciones y otra n, hay m·n combinaciones. | 087 |
| Permutación | Selección ordenada. P(n,k) = n!/(n−k)! | 088 |
| Combinación | Selección sin orden. C(n,k) = n!/(k!(n−k)!). Simétrica: C(n,k) = C(n,n−k). | 089 |
| Principio del palomar | Si n objetos se reparten en m cajas con n > m, alguna caja tiene al menos dos. Demuestra colisiones sin construirlas. | 090 |
| Inducción matemática | Método de demostración con caso base y paso inductivo. Cubre infinitos casos con dos argumentos. | 091 |
| Recurrencia | Definición de un término en función de los anteriores. Su coste depende de si se memoiza. | 092 |
| Grado de un vértice | Número de aristas incidentes. La suma de los grados es el doble del número de aristas. | 093 |
| BFS | Recorrido en anchura. Encuentra el camino con menos aristas en un grafo no ponderado. Coste O(V+E). | 094 |
| Árbol | Grafo conexo sin ciclos. Con n vértices tiene exactamente n−1 aristas. | 095 |
| DAG | Grafo dirigido acíclico. Admite orden topológico; su ausencia delata un ciclo. | 096 |
| Orden topológico | Ordenación de los vértices de un DAG tal que toda arista va de un vértice anterior a uno posterior. | 096 |
| Aritmética modular | Aritmética de los restos respecto a un módulo. Base de hashing, criptografía y checksums. | 098 |
| Criba de Eratóstenes | Algoritmo que encuentra todos los primos hasta n tachando múltiplos. Coste O(n log log n). | 099 |