Resumen de Fundamentos de Matemáticas Discretas

## Introducción La álgebra booleana y las estructuras algebraicas son herramientas formales que permiten modelar y razonar sobre objetos discretos y operaciones lógicas. En este material repasaremos conceptos clave, definiciones formales, procedimientos prácticos para obtener formas normales a partir de tablas de verdad y conexiones con estructuras algebraicas (sistemas axiomáticos, anillos y cuerpos) para comprender el marco formal detrás de operaciones y propiedades. > Definición: La álgebra booleana binaria es una estructura $(B,0,1,+,\cdot,\overline{\cdot})$ donde $B=\{0,1\}$, $0$ y $1$ son constantes, $+$ representa la disyunción, $\cdot$ la conjunción y $\overline{\cdot}$ la negación. ## 1. Conceptos básicos y notación ### Variables, expresiones y funciones booleanas - Una **variable booleana** toma valores en $B=\{0,1\}$, por ejemplo $x,y,z$. - Una **expresión booleana** es una fórmula construida con variables, constantes $0,1$ y operadores $+$, $\cdot$, $\overline{\cdot}$. - Una **función booleana** es una función $f\colon B^n\to B$ y puede representarse por una expresión o por su tabla de verdad. > Definición: Una función booleana $f(x_1,x_2,\dots,x_n)$ toma cada combinación de $x_i\in B$ y asigna un valor en $B$. Se escribe $f(x_1,x_2,\dots,x_n)=E(x_1,x_2,\dots,x_n)$ cuando $E$ es la expresión que la representa. Did you know que para $n$ variables una tabla de verdad tiene exactamente $2^n$ filas, una por cada combinación posible de valores? ### Tabla de verdad y equivalencia - La tabla de verdad relaciona cada tupla $(x_1,\dots,x_n)$ con $f(x_1,\dots,x_n)$. - Dos funciones booleanas son **equivalentes** si sus tablas de verdad son iguales. ## 2. Formas normales: FND y FNC Las formas normales son expresiones canónicas que permiten representar cualquier función booleana. ### Forma Normal Disyuntiva (FND) Procedimiento para obtener la FND de $f(x_1,\dots,x_n)$: 1. Identificar las filas de la tabla de verdad donde $f=1$. 2. Para cada fila con $f=1$, construir el **minterm** como producto (conjunción) de las $n$ variables, tomando la variable directa si vale $1$ y su complemento si vale $0$. 3. Sumar (disyunción) todos los minterms obtenidos. El resultado es la FND (suma de productos). Ejemplo paso a paso (dos variables): - Tabla: filas con $f=1$ en $(0,0)$, $(0,1)$, $(1,1)$. - Minterms: para $(0,0)$ $\Rightarrow \overline{x}\,\overline{y}$; para $(0,1)$ $\Rightarrow \overline{x}\,y$; para $(1,1)$ $\Rightarrow x\,y$. - FND: $$f(x,y)=\overline{x}\,\overline{y}+\overline{x}\,y+x\,y$$ ### Forma Normal Conjuntiva (FNC) Análogamente, la FNC se construye a partir de las filas donde $f=0$: 1. Identificar filas con $f=0$. 2. Para cada fila construir el **maxterm** como suma (disyunción) de las variables, donde si la variable es $1$ se toma complementada y si es $0$ se toma directa; cada maxterm es una cláusula que evalúa $0$ solo en esa fila. 3. Multiplicar (conjunción) todos los maxterms. El resultado es la FNC (producto de sumas). Ejemplo: si $f( x,y )$ es $1$ en todas menos la fila $(1,0)$, la FNC incluirá el maxterm correspondiente a $(1,0)$ que es $(\overline{x}+y)$ y otros según corresponda. ## 3. Tablas y equivalencias rápidas | Concepto | Representación | Observación práctica | |---|---:|---| | Variable booleana | $x\in\{0,1\}$ | Base de las funciones | | Minterm | $x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$ (con complementos) | Producto que es 1 en exactamente una fila | | Maxterm | $\bigl(x_1^{b_1}+x_2^{b_2}+\dots\bigr)$ | Suma que es 0 en exactamente una fila | | FND | Suma de minterms | Útil para implementar con puertas AND/OR | | FNC | Producto de maxterms | Útil para implementar con puertas OR/AND | Nota: En la tabla se usa la notación $x^1\equiv x$, $x^0\equiv\overline{x}$ como mnemotecnia para construir minterms/maxterms. ## 4. De expresiones a tablas y viceversa - Para obtener la tabla dado $E(x_1,\dots,x_n)$, evaluar la expresión para cada una de las $2^n$ combinaciones. - Para obtener una expr