Matemática discreta: conjuntos, lógica y combinatoria

Antes de contar posibilidades hay que decidir cuándo dos posibilidades son la misma. Elegir tres personas de un grupo no equivale a asignarles tres cargos diferentes. Cambiar el orden de los nombres conserva el grupo elegido, pero puede cambiar quién ocupa cada cargo. Una cuenta correcta aplicada a la representación equivocada responde otra pregunta.

La matemática discreta estudia elementos distinguibles, relaciones, secuencias y estructuras que se construyen mediante pasos separados. No se restringe a conjuntos finitos: los enteros y las secuencias infinitas también pertenecen a su campo. Su problema característico es explicar cómo reglas locales determinan posibilidades completas y cómo puede justificarse una afirmación sobre todas ellas sin examinarlas una por una.

125.1. Conjuntos, relaciones y funciones#

Ejemplo construido. Un archivo reúne seis documentos, identificados por las letras $a,b,c,d,e,f$. Cuatro están restaurados, $R=\{a,b,d,f\}$, y tres están digitalizados, $D=\{b,c,d\}$. Se necesita distinguir documentos disponibles en alguna de las dos condiciones, documentos que cumplen ambas y documentos que aún no cumplen ninguna. Las letras son identificadores, no cantidades que deban sumarse.

Un conjunto reúne elementos y permite decidir si cada uno pertenece a él. Se escribe $b\in R$ para indicar pertenencia y $c\notin R$ para su negación. En un conjunto, el orden de escritura no cambia el resultado y repetir un elemento no añade otro: $\{a,b,b\}=\{b,a\}$. Una lista, en cambio, puede conservar posiciones y repeticiones. El conjunto vacío, $\varnothing$, no tiene elementos; $\{\varnothing \}$ tiene uno, que es precisamente el conjunto vacío. (Levin, conjuntos).

La unión $R\cup D$ contiene los documentos que pertenecen a al menos uno de los conjuntos: $\{a,b,c,d,f\}$. La intersección $R\cap D$ contiene los que están en ambos: $\{b,d\}$. La diferencia $R\setminus D$ contiene los restaurados que no están digitalizados: $\{a,f\}$. Para hablar del complemento hay que fijar un universo de referencia. Si $U=\{a,b,c,d,e,f\}$ es todo el archivo del ejemplo, $U\setminus (R\cup D)=\{e\}$. Un complemento no significa «todo lo demás en cualquier lugar».

El número de elementos de un conjunto finito $A$ se escribe $|A|$ y se llama cardinalidad. La barra tiene aquí un significado distinto del valor absoluto de un número. Si todos los elementos de $A$ pertenecen también a $B$, se escribe $A\subseteq B$: $A$ es un subconjunto de $B$. Pertenencia e inclusión no son intercambiables; $a$ puede ser un documento y $\{a\}$ el conjunto formado por él.

Los conjuntos permiten representar relaciones entre clases distintas de objetos. Si $A$ reúne documentos y $B$ equipos de trabajo, el producto cartesiano $A\times B$ reúne todos los pares ordenados $(a,b)$ con $a\in A$ y $b\in B$. El orden de un par importa: el primer componente responde a «qué documento» y el segundo a «qué equipo». Una relación entre $A$ y $B$ es un subconjunto de ese producto; puede señalar qué equipos están autorizados a intervenir en qué documentos.

Una función de $A$ a $B$ es una relación especial que asigna a cada elemento de $A$ exactamente una imagen en $B$. Que un documento tenga varios equipos autorizados no define, por sí solo, una función de documentos a equipos. Designar un responsable único para cada documento sí podría hacerlo. Una función no necesita ser una fórmula ni tener entradas numéricas. (Levin, estructuras discretas).

Otra relación puede reunir objetos considerados equivalentes según un criterio. Para comportarse como equivalencia debe ser reflexiva, simétrica y transitiva: cada elemento se relaciona consigo mismo; relacionar $a$ con $b$ implica relacionar $b$ con $a$; y relacionar $a$ con $b$ y $b$ con $c$ implica relacionar $a$ con $c$. Las clases resultantes forman una partición: cubren el conjunto sin superponerse. (Levin, relaciones y clases de equivalencia).

La semejanza informal puede incumplir esas condiciones. Si dos longitudes se consideran «parecidas» cuando difieren menos de un centímetro, 10 y 10,7 centímetros son parecidas, y 10,7 y 11,4 también; 10 y 11,4 no lo son. La regla no es transitiva. Convertirla en categorías mutuamente excluyentes requiere otra decisión de clasificación, no sólo un cambio de nombre.

125.2. Proposiciones, cuantificadores e inferencia#

Una regla de selección necesita expresar condiciones con suficiente precisión para aplicarlas del mismo modo a todos los casos. «Restaurado o digitalizado» puede entenderse como pertenecer a al menos una condición, mientras que «restaurado y digitalizado» exige ambas. Formalizar la regla permite separar su significado de la manera en que se redacta.

Una proposición es un enunciado que, en un contexto fijado, tiene valor de verdad. En la lógica clásica usada aquí esos valores son verdadero y falso. «El documento $b$ está digitalizado» es una proposición respecto del archivo descrito; una orden de digitalizarlo no lo es. Que el valor exista no implica que quien investiga lo conozca. Datos incompletos y verdad lógica son cuestiones distintas.

Sean $P$ y $Q$ dos proposiciones. La conjunción $P\wedge Q$ es verdadera cuando ambas lo son. La disyunción $P\vee Q$ es verdadera cuando al menos una lo es, incluidas ambas; es una «o» inclusiva. La negación $\mathrm{\neg }P$ invierte el valor de verdad de $P$. Para exigir una condición y excluir la otra se necesita una disyunción exclusiva, que puede escribirse $(P\vee Q)\wedge \mathrm{\neg }(P\wedge Q)$.

La implicación $P\Rightarrow Q$ afirma que no ocurre el caso de $P$ verdadera y $Q$ falsa. $P$ es condición suficiente para $Q$ y $Q$ condición necesaria para $P$. Una implicación material no afirma un mecanismo causal ni una sucesión temporal. Tampoco afirma que $P$ se cumpla. (Levin, implicaciones).

La tabla examina las combinaciones de valores, no la frecuencia con que aparecen en una población. Si se exige que todo documento digitalizado tenga un identificador único, hallar un documento digitalizado sin él refuta la regla. Un documento no digitalizado no la refuta, tenga o no identificador. El caso donde $P$ es falsa no viola la condición expresada; por eso la implicación figura como verdadera en esas filas.

De $P\Rightarrow Q$ y $P$ se infiere $Q$: es una regla válida de deducción. De $P\Rightarrow Q$ y $Q$ no se infiere $P$, porque $Q$ podría cumplirse por otras vías. Tener identificador no demuestra estar digitalizado. De la misma implicación y $\mathrm{\neg }Q$ sí se infiere $\mathrm{\neg }P$. Esta última deducción expresa la contraposición: $P\Rightarrow Q$ equivale a $\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$. (Levin, reglas de lógica).

Cuando el enunciado depende de una entrada se habla de un predicado. «$x$ está digitalizado» se convierte en proposición al especificar $x$ o al cuantificar sobre un dominio. $\mathrm{\forall }x\in A$, «para todo $x$ de $A$», exige la propiedad a cada elemento; $\mathrm{\exists }x\in A$, «existe un $x$ de $A$», exige al menos uno y no necesariamente uno solo. El dominio importa: una regla sobre los seis documentos no afirma nada acerca de otro archivo. (Levin, predicados y cuantificadores).

Negar «todos cumplen» da «existe alguno que no cumple». Negar «existe alguno que cumple» da «ninguno cumple». La primera negación no equivale a decir que todos incumplen. La lógica distingue así un contraejemplo suficiente para refutar una afirmación universal de un conjunto de ejemplos que la apoya sin demostrarla.

También el orden de los cuantificadores cambia la exigencia. «Para cada documento existe un equipo autorizado» permite que distintos documentos requieran equipos distintos. «Existe un equipo autorizado para todos los documentos» exige un único equipo común. La primera condición no garantiza la segunda: pueden repartirse todas las autorizaciones sin que nadie las reúna.

Sobre un dominio vacío, «todos sus elementos cumplen» es verdadero en esta lógica: no existe un elemento que lo refute. «Alguno cumple» es falso, porque no hay testigo. Esa convención evita excepciones artificiales al expresar inclusión de conjuntos y permite reconocer cuándo una regla universal no demuestra siquiera que existan los objetos a los que se refiere.

125.3. Principios de conteo y recurrencias#

Contar requiere representar los resultados de manera que cada uno aparezca exactamente una vez. El principio de la suma reúne alternativas excluyentes: si una posibilidad pertenece a una de dos clases disjuntas, el total es la suma de sus tamaños. Si las clases se superponen, esa suma duplica los elementos compartidos.

En el archivo construido, sumar cuatro restaurados y tres digitalizados da siete menciones, no siete documentos. Los dos compartidos aparecen dos veces. Para contarlos una vez,

La fórmula es el caso de dos conjuntos del principio de inclusión y exclusión. La resta corrige el exceso de conteo de la intersección, no elimina esos documentos del resultado. (Levin, resultados no disjuntos).

El principio del producto cuenta decisiones sucesivas. Si hay $m$ opciones iniciales y cada una permite $n$ opciones posteriores, existen $mn$ pares de elecciones. No requiere independencia probabilística: todavía no se han asignado probabilidades. Requiere que el número de continuaciones considerado sea correcto para cada elección previa. Si unas opciones permiten dos continuaciones y otras cinco, se suman los tamaños de las ramas correspondientes en vez de multiplicar por un número arbitrario. (Levin, combinación de resultados).

Para elegir tres elementos distintos de un conjunto de seis y ponerlos en orden hay seis opciones para el primero, cinco para el segundo y cuatro para el tercero: $6\cdot 5\cdot 4=120$. Si se permiten repeticiones, cada posición conserva seis opciones y el total es $6^3=216$. Si sólo importa el grupo de tres, las 120 secuencias duplican cada grupo seis veces, una por cada orden de sus tres elementos. Quedan $120/6=20$ grupos.

En general, para enteros $n\ge 0$ y $0\le k\le n$, el número de subconjuntos de $k$ elementos de un conjunto de $n$ elementos es

$n!$ es el producto de los enteros de uno a $n$, y se define $0!=1$. El numerador dividido por $(n-k)!$ cuenta elecciones ordenadas sin repetición; dividir por $k!$ elimina las permutaciones internas de cada grupo. La fórmula no sirve sin cambios si los elementos son indistinguibles o hay otras restricciones. (Levin, combinaciones y permutaciones).

Una elección vacía es una posibilidad, no la ausencia de posibilidades: $(\genfrac{}{}{0ex}{}{n}{0})=1$. Del mismo modo, hay un único subconjunto vacío. Para contar todos los subconjuntos, cada elemento tiene dos decisiones, incluirlo o excluirlo; por el producto hay $2^n$. Estas decisiones binarias vinculan conjuntos y secuencias de ceros y unos.

Si se restringen las secuencias, puede resultar más fácil relacionar tamaños sucesivos que dar una fórmula directa. Sea $t_n$ el número de secuencias binarias de longitud $n$ sin dos unos consecutivos. Hay $t_0=1$, la secuencia vacía, y $t_1=2$, las secuencias 0 y 1. Para $n\ge 2$, las que terminan en cero se obtienen añadiendo un cero a cualquier secuencia válida de longitud $n-1$; son $t_{n-1}$. Las que terminan en uno deben terminar en 01 y se obtienen añadiendo ese bloque a una secuencia válida de longitud $n-2$; son $t_{n-2}$.

Las dos clases son disjuntas y cubren todos los resultados. Por tanto,

Es una recurrencia: define cada cantidad mediante otras de índices anteriores y necesita valores iniciales. Produce $1,2,3,5,8,13,\dots$. Compartir una recurrencia con otros problemas no demuestra que sus mecanismos físicos sean iguales; expresa una estructura de conteo común. (Hammack, conteo y razonamiento recursivo).

125.4. Inducción y definiciones recursivas#

Comprobar una fórmula para los primeros cien enteros no demuestra que se cumpla para todos. La inducción matemática permite pasar de una comprobación inicial a una garantía general cuando se demuestra que la propiedad se transmite de cada caso al siguiente. Debe establecerse el primer caso y probarse, para un índice arbitrario $k$ dentro del dominio, que la verdad del caso $k$ implica la del caso $k+1$. (Levin, demostración por inducción).

El supuesto sobre $k$ no es aceptar sin prueba la conclusión universal. Se demuestra una implicación que funciona para cualquier $k$ permitido. El caso inicial la pone en marcha. Si una afirmación fallara después, habría un primer entero donde falla; el anterior sería verdadero y la transmisión demostrada impediría esa primera falla.

Por ejemplo, la suma de los primeros $n$ enteros positivos impares es $n^2$. Para $n=1$, la suma es uno. Suponiendo que la suma hasta el impar $2k-1$ es $k^2$, añadir el siguiente impar da

La identidad demuestra el paso y, junto con la base, el resultado para todo entero $n\ge 1$. No basta mostrar que al cuadrado inicial se le añade «algo parecido» a un borde; hay que establecer el tamaño exacto de ese aporte. La fórmula y la interpretación geométrica coinciden porque el borde nuevo tiene $2k+1$ unidades.

En una definición recursiva, la relación con casos menores construye el objeto en vez de demostrar una propiedad. El factorial se define por $0!=1$ y $n!=n(n-1)!$ para $n\ge 1$. La definición termina porque el índice disminuye hasta cero. Especificar sólo la segunda igualdad dejaría sin fijar el punto de partida; especificar $n!=n(n+1)!$ no proporcionaría un procedimiento descendente hacia esa base.

Las definiciones recursivas también construyen conjuntos de expresiones. Para las secuencias sin 11, las bases pueden ser la secuencia vacía y la secuencia 1; las reglas añaden 0 o 01 a cualquier secuencia ya construida. Así, añadir 0 a la vacía produce 0. Toda secuencia válida de longitud al menos dos admite una de las descomposiciones de la sección anterior, y las reglas nunca introducen 11: generan exactamente el conjunto buscado. En una definición de un conjunto, debe precisarse que sólo se incluyen los objetos obtenidos de las bases mediante aplicaciones finitas de las reglas. (Meyer, definiciones recursivas).

La inducción fuerte permite suponer la propiedad para todos los índices menores necesarios y demostrar el siguiente. No afirma que los resultados sean más verdaderos que en la inducción ordinaria; amplía la información disponible dentro del paso. Es útil si un objeto se descompone en partes de varios tamaños. (Levin, inducción fuerte).

Por ejemplo, todo entero $n\ge 2$ puede expresarse como producto de números primos. Si $n$ es primo, ya constituye el producto. Si no lo es, tiene una factorización $n=ab$ con $2\le a,b<n$. Suponiendo demostrada la propiedad para todos los enteros menores desde dos, ambos factores tienen descomposiciones en primos y multiplicarlas proporciona la de $n$. El primer caso, dos, es primo. El razonamiento demuestra existencia de una descomposición; su unicidad es otra afirmación y necesita otro argumento.

125.5. Estructuras finitas y algoritmos#

Una estructura finita permite describir todos sus elementos, pero no siempre examinarlos en un tiempo útil. Veinte elementos admiten $2^{20}=1048576$ subconjuntos; cuarenta admiten $2^{40}$, más de un billón en la escala larga usada en español. Duplicar el número de elementos eleva al cuadrado la cantidad de subconjuntos. La finitud garantiza que una enumeración ideal tiene un final, no que sea una buena forma de resolver el problema.

Un algoritmo especifica pasos sin ambigüedad para transformar una entrada en una salida. Para un procedimiento que pretende resolver siempre una tarea, deben comprobarse dos propiedades: que termina para todas las entradas permitidas y que, cuando termina, entrega lo que exige la especificación. La rapidez es una tercera cuestión. Un método puede ser correcto y terminar, pero requerir demasiados pasos para tamaños de interés.

El algoritmo de Euclides permite hallar el máximo común divisor de dos enteros positivos sin listar todos sus divisores. Si $a=qb+r$, con $q$ el cociente entero y $0\le r<b$, reemplaza el par $(a,b)$ por $(b,r)$ y repite mientras el segundo componente sea distinto de cero. Para 210 y 84, la secuencia es $(210,84)$, $(84,42)$, $(42,0)$; la salida es 42.

La justificación tiene dos partes separables. Un entero divide a $a$ y a $b$ exactamente cuando divide a $b$ y a $r=a-qb$. En un sentido, restar el múltiplo conserva la divisibilidad; en el otro, sumar $qb$ recupera $a$. Los pares sucesivos tienen los mismos divisores comunes y, por tanto, el mismo máximo. Cuando se alcanza $(d,0)$, ese máximo es $d$.

Además, el segundo componente es un entero no negativo que disminuye estrictamente en cada paso donde era positivo. No puede disminuir indefinidamente sin llegar a cero. Esta prueba de terminación no deriva sólo de que el máximo común divisor se conserve. Una regla que dejara siempre el par igual conservaría también ese máximo, pero no avanzaría. (Lehman, Leighton y Meyer, algoritmo de Euclides e invariantes).

Una propiedad preservada durante la ejecución se llama invariante. La inducción explica su garantía: se cumple al comenzar y cada transición la conserva, luego se cumple tras cualquier número de pasos. Un invariante adecuado conecta el estado intermedio con la salida buscada; una cantidad descendente puede garantizar que se alcanza el final. No deben confundirse ambas funciones.

También las recurrencias pueden convertirse en algoritmos. Calcular $t_n$ mediante llamadas que recalculen una y otra vez $t_{n-1}$ y $t_{n-2}$ repite subproblemas. Guardar los resultados sucesivos permite obtener el siguiente con una suma y conservar sólo los dos últimos. La relación matemática es la misma; la organización del cálculo cambia el trabajo requerido. Como las cantidades crecen, el costo de operar con sus dígitos también importa: contar sumas no equivale siempre a contar operaciones elementales sobre bits.

Una representación finita puede omitir restricciones reales. Un conjunto de autorizaciones no demuestra que un equipo tenga tiempo suficiente; un conteo de calendarios formalmente válidos no demuestra que sus condiciones se cumplirán. El beneficio de formalizar consiste en poder revisar por separado los objetos admitidos, las reglas aplicadas y las deducciones que efectivamente se siguen. El capítulo siguiente usa otra estructura discreta, el grafo, para representar relaciones cuya disposición modifica caminos y posibilidades de circulación.

Preguntas de transferencia#

¿Siete menciones son siete elementos?#

En un conjunto de seis objetos, cuatro cumplen $P$ y tres cumplen $Q$. ¿Se puede deducir cuántos cumplen al menos una condición sin conocer la intersección?

¿Un equipo para cada tarea es un equipo para todas?#

Ejemplo construido. Hay dos tareas y dos equipos. El primero está autorizado sólo para la primera tarea y el segundo sólo para la segunda. ¿Se cumplen ambas expresiones cuantificadas?

¿Cuántas distribuciones de cargos hay?#

Ejemplo construido. Se eligen de seis personas una responsable, una revisora y una secretaria, sin acumular cargos. ¿Por qué no basta $(\genfrac{}{}{0ex}{}{6}{3})$?

¿Conservar una propiedad demuestra que un cálculo termina?#

Un procedimiento conserva el conjunto de divisores comunes de dos enteros y vuelve al mismo par en cada paso. ¿Eso prueba que encuentra su máximo común divisor?

Fuentes y lecturas del capítulo#

Oscar Levin. Discrete Mathematics: An Open Introduction, cuarta edición, secciones Sets, Discrete Structures y Relations and Graphs. Consultadas para notación, relación frente a función y condiciones que permiten formar clases de equivalencia. (Conjuntos; estructuras; relaciones).

Oscar Levin. Misma obra, Mathematical Statements, Implications y Rules of Logic. Tratamientos consultados de cuantificación, implicación material y validez de deducciones; no convierten una relación lógica en una explicación causal. (Enunciados; implicaciones; reglas).

Oscar Levin. Misma obra, Combining Outcomes, Non-Disjoint Outcomes y Combinations and Permutations. Consultadas para distinguir ramas de elección, corregir superposiciones y reconocer cuándo el orden identifica resultados diferentes. (Combinación; superposición; combinaciones y permutaciones).

Oscar Levin. Misma obra, Proof by Induction y Strong Induction. Lecturas consultadas sobre el alcance del supuesto inductivo y la necesidad de establecer los casos iniciales. (Inducción; inducción fuerte).

Richard Hammack. Book of Proof, tercera edición, versión 3.4 (2018). Manual consultado en los temas de conteo y razonamiento recursivo. Sus argumentos sirven como contraste de las distinciones entre representación, comprobación y demostración. (Documento).

Albert R. Meyer. Recursive Data, material de MIT 6.042J/18.062J fechado el 29 de febrero de 2012. Distingue bases y reglas constructoras de una definición recursiva; el documento está alojado entre los materiales del curso de 2018. (Documento).

Eric Lehman, F. Thomson Leighton y Albert R. Meyer. Mathematics for Computer Science, revisión del 18 de mayo de 2015. Se consultaron el principio de invariantes y la justificación del algoritmo de Euclides; el capítulo utiliza números propios y separa corrección de terminación. (Documento).

Bibliografía de la parte XII · Bibliografía general

Última revisión editorial

29 de septiembre de 2026

Cierre de contenidos

29 de septiembre de 2026