Matemáticas discretas
Las matemáticas discretas son las matemáticas de las cosas separadas y contables: verdadero o falso, dentro de un conjunto o fuera, este camino o aquel. Son las matemáticas con las que funcionan los ordenadores, y empiezan por una lógica que puedes encender y apagar.
Última actualización
Las matemáticas discretas son las matemáticas de las cosas separadas y contables. Una afirmación es verdadera o falsa, un elemento está en un conjunto o no, una red tiene un enlace entre dos puntos o no lo tiene. No hay nada en medio, que es lo que significa "discreto", y es exactamente como ve el mundo un ordenador.
Un primer curso cubre seis temas: lógica, conjuntos, conteo, grafos, teoría de números y demostración. La lógica va primero, porque todos los demás temas se escriben con ella. Elige una conectiva abajo y cambia p y q.
Tabla de verdad de p ∧ q
| p | q | p ∧ q |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Cambia p y q, o haz clic en una fila. La fila resaltada es la que eligen.
Lee p como "x está en A" y q como "x está en B". Las regiones sombreadas son donde la afirmación es verdadera; el punto es la fila actual.
p ∧ q
Se lee p y q
Con estos valores, p ∧ q es verdadera.
Verdadera solo cuando p y q son verdaderas.
Como conjuntos AND es la intersección: x está en A ∩ B exactamente cuando x está en A y x está en B.
Lógica: proposiciones y conectivas
Una proposición es una frase que es verdadera o falsa, como "7 es primo" o "está lloviendo". La lógica construye proposiciones más grandes a partir de otras más pequeñas con unas pocas conectivas, y una tabla de verdad enumera el resultado para cada combinación de entradas.
| símbolo | nombre | se lee | verdadera cuando |
|---|---|---|---|
| ∧ | AND, conjunción | "p y q" | las dos son verdaderas |
| ∨ | OR, disyunción | "p o q" | al menos una es verdadera |
| ¬ | NOT, negación | "no p" | p es falsa |
| ⊕ | XOR, disyunción exclusiva | "p o q, pero no ambas" | exactamente una es verdadera |
| → | IMPLICA, condicional | "si p, entonces q" | en todos los casos salvo p verdadera y q falsa |
| ↔ | SSI, bicondicional | "p si y solo si q" | p y q tienen el mismo valor |
Dos de ellas sorprenden. El OR lógico es inclusivo: "p o q" es verdadera cuando las dos son verdaderas, al contrario que el "¿té o café?" de todos los días. La versión exclusiva tiene su propio nombre, XOR.
La otra es IMPLICA. p → q es falsa en una sola fila, cuando p es verdadera y q es falsa. Piénsalo como una promesa: "si llueve, llevaré paraguas". La promesa solo se rompe si llueve y no hay paraguas. En un día seco la promesa no se ha roto, lleves lo que lleves, así que la afirmación cuenta como verdadera.
Proposiciones equivalentes
Dos proposiciones son equivalentes cuando sus tablas de verdad coinciden en todas las filas. En el widget, elige OR y niega p: la columna de ¬p ∨ q es idéntica a la columna de p → q, así que las dos dicen lo mismo.
Las equivalencias más útiles son las leyes de De Morgan, que dicen cómo pasa NOT a través de AND y OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Con palabras: "no las dos" es lo mismo que "una u otra es falsa", y "ninguna" es lo mismo que "las dos son falsas". Los programadores las usan a diario para reescribir una condición como "no (ha iniciado sesión y está verificado)".
Lógica y conjuntos son una misma idea
Lee p como "x está en A" y q como "x está en B". Entonces AND es la intersección, OR es la unión y NOT es el complemento, y cada tabla de verdad es un diagrama de Venn sombreado, que es por lo que el widget dibuja uno junto a la tabla. Las leyes de De Morgan se convierten en reglas sobre conjuntos:
(A ∩ B)′ = A′ ∪ B′
La página de notación de conjuntos sombrea cada una de estas en un diagrama en el que puedes hacer clic.
Conteo
Contar en matemáticas discretas significa contar sin enumerar. Dos reglas hacen casi todo el trabajo.
La regla del producto. Si una elección se puede hacer de m maneras y una segunda de n maneras, el par se puede hacer de m × n maneras. Un PIN de 4 cifras tiene 10 opciones para cada cifra, así que hay 10^4 = 10000 PIN posibles.
Combinaciones. El número de formas de elegir k cosas de entre n, cuando el orden no importa, se escribe C(n, k). Elegir 3 ingredientes de entre 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
El numerador cuenta las elecciones ordenadas, y dividir entre 3 × 2 × 1 quita los 6 órdenes en que se podrían haber elegido los mismos tres ingredientes.
La respuesta es 6 × 5 dividido entre 2, que es 15. Si te ha salido 30, has contado cada pareja dos veces, una en cada orden.
Grafos
Un grafo es un conjunto de puntos, llamados vértices, unidos por líneas, llamadas aristas. Modela cualquier cosa hecha de conexiones: carreteras entre pueblos, amigos en una red social, enlaces entre páginas web.
Un primer resultado: si 5 personas se dan la mano todas con todas una vez, hay C(5, 2) = 10 apretones de manos. Cada persona da la mano a 4, lo que da 5 × 4 = 20 extremos, y cada apretón tiene dos extremos, así que 20 / 2 = 10. Ese argumento es el lema del apretón de manos: los grados de todos los vértices suman el doble del número de aristas.
Teoría de números y demostración
La aritmética modular es la aritmética de un reloj. 17 mod 5 es 2, el resto de dividir 17 entre 5. Nueve horas después de las 8 son las 5, porque 17 mod 12 es 5. La misma idea, con números muy grandes, es como funciona el cifrado RSA que protege las webs seguras.
La demostración por inducción prueba que una afirmación se cumple para todo número entero n en dos pasos: se comprueba para n = 1, y luego se demuestra que si se cumple para un n también se cumple para n + 1. Es como se demuestra, por ejemplo, que
1 + 2 + ... + n = n(n + 1) / 2
para todo n, no solo para los valores que has probado.
Para qué sirven las matemáticas discretas
- Programación: cada sentencia if es lógica, y las leyes de De Morgan reescriben condiciones.
- Bases de datos: una consulta que une o filtra tablas es una operación con conjuntos.
- Algoritmos: el conteo te dice cuántos pasos da un programa a medida que crece la entrada.
- Redes y mapas: las rutas más cortas y las redes sociales son problemas de grafos.
- Seguridad: el cifrado se apoya en la teoría de números y la aritmética modular.
- Hardware: un procesador está hecho de puertas lógicas, que son tablas de verdad en silicio.
¿Son difíciles las matemáticas discretas?
Son difíciles de otra manera que el álgebra y el cálculo. Hay pocas fórmulas que memorizar y la aritmética es pequeña, pero muchas preguntas te piden demostrar algo en lugar de calcularlo, y escribir un argumento convincente es una destreza nueva para la mayoría de los estudiantes.
Lo que más ayuda es resolver casos pequeños a mano antes de buscar el patrón: dibuja el diagrama de Venn, escribe la tabla de verdad, enumera todos los casos. La notación parece pesada al principio, pero casi toda consiste en los símbolos de esta página y de la página de notación de conjuntos.
Preguntas frecuentes
- ¿Qué son las matemáticas discretas?
- La rama de las matemáticas que estudia objetos separados y contables en lugar de magnitudes que varían de forma continua. Sus temas principales son la lógica, los conjuntos, el conteo, los grafos, la teoría de números y la demostración. El cálculo pregunta cómo cambian las cosas de forma continua; las matemáticas discretas preguntan cuántos, cuáles y si una afirmación es verdadera.
- ¿Son difíciles las matemáticas discretas?
- Son difíciles de otra manera que el cálculo. Hay menos fórmulas que aplicar y más argumentos que construir, y para muchos estudiantes es su primer curso centrado en escribir demostraciones. El álgebra suele ser ligera. A quienes les cuesta, casi siempre es porque se están adaptando a las demostraciones, y eso mejora rápido practicando con ejemplos pequeños.
- ¿Para qué sirven las matemáticas discretas?
- Para casi todo en informática. La lógica es cómo funcionan los circuitos y las sentencias if, los conjuntos están detrás de las consultas a bases de datos, el conteo te dice cuánto tarda un algoritmo, los grafos modelan redes y mapas, y la teoría de números es la base del cifrado que protege los pagos en línea.
- ¿Qué temas se estudian en matemáticas discretas?
- Un primer curso típico cubre lógica proposicional y tablas de verdad, conjuntos y diagramas de Venn, funciones y relaciones, técnicas de demostración incluida la inducción, conteo con permutaciones y combinaciones, probabilidad básica, grafos y árboles, y aritmética modular. Algunos cursos añaden relaciones de recurrencia y álgebra de Boole.
- ¿Necesito matemáticas discretas para estudiar informática?
- Sí. Casi todas las carreras de informática la exigen, normalmente en primero o segundo curso, porque los algoritmos, las estructuras de datos y la teoría de la computación la dan por sabida. Para programar sin más puedes empezar sin ella, pero la lógica, los conjuntos y el conteo aparecen en el código de cada día antes de lo que la mayoría espera.
- ¿Qué diferencia hay entre matemáticas discretas y continuas?
- Las matemáticas discretas tratan valores que se pueden enumerar uno a uno, como los números enteros, verdadero y falso o los nodos de una red. Las matemáticas continuas, como el cálculo, tratan magnitudes que pueden tomar cualquier valor de un intervalo, como el tiempo, la distancia o la temperatura.
- ¿Qué es una tabla de verdad?
- Una tabla que enumera todas las combinaciones de verdadero y falso para las entradas de una afirmación lógica, y el valor de la afirmación en cada una. Con dos entradas p y q hay cuatro filas. Una tabla de verdad es la forma de demostrar que dos afirmaciones son equivalentes: si sus columnas coinciden en todas las filas, siempre coinciden.
