Polinomio de Zhegalkin

Los polinomios de Zhegalkin (también Žegalkin , Gégalkine o Shegalkin ^[1] ) ( en ruso : полиномы Жегалкина ), también conocidos como forma normal algebraica , son una representación de funciones en el álgebra de Boole . Introducidos por el matemático ruso Ivan Ivanovich Zhegalkin en 1927, ^[2] son ​​el anillo polinómico sobre los números enteros módulo 2. Las degeneraciones resultantes de la aritmética modular dan como resultado que los polinomios de Zhegalkin sean más simples que los polinomios ordinarios, y no requieran ni coeficientes ni exponentes. Los coeficientes son redundantes porque 1 es el único coeficiente distinto de cero. Los exponentes son redundantes porque en aritmética módulo 2, x ² = x . Por lo tanto, un polinomio como 3 x ² y ⁵ z es congruente con xyz y, por lo tanto, puede reescribirse como tal .

Equivalente booleano

Antes de 1927, el álgebra de Boole se había considerado un cálculo de valores lógicos con operaciones lógicas de conjunción , disyunción , negación , etc. Zhegalkin demostró que todas las operaciones booleanas podían escribirse como polinomios numéricos ordinarios, representando los valores falsos y verdaderos como 0 y 1, los enteros módulo 2. La conjunción lógica se escribe como xy y el or-exclusivo lógico como adición aritmética módulo 2 (escrito aquí como x ⊕ y para evitar confusiones con el uso común de + como sinónimo de or-inclusivo ∨). El complemento lógico ¬ x es entonces x ⊕1. Dado que ∧ y ¬ forman una base para el álgebra de Boole, todas las demás operaciones lógicas son composiciones de estas operaciones básicas, y por lo tanto los polinomios del álgebra ordinaria pueden representar todas las operaciones booleanas, lo que permite realizar el razonamiento booleano utilizando álgebra elemental .

Por ejemplo, la operación de umbral o mediana booleana 2 de 3 se escribe como el polinomio de Zhegalkin xy ⊕ yz ⊕ zx .

Propiedades formales

Formalmente, un monomio de Zhegalkin es el producto de un conjunto finito de variables distintas (por lo tanto, libre de cuadrados ), incluido el conjunto vacío cuyo producto se denota 1. Hay 2 ⁿ posibles monomios de Zhegalkin en n variables, ya que cada monomio está completamente especificado por la presencia o ausencia de cada variable. Un polinomio de Zhegalkin es la suma (o-exclusivo) de un conjunto de monomios de Zhegalkin, con el conjunto vacío denotado por 0. La presencia o ausencia de un monomio dado en un polinomio corresponde a que el coeficiente de ese monomio sea 1 o 0 respectivamente. Los monomios de Zhegalkin, al ser linealmente independientes , abarcan un espacio vectorial de 2 ⁿ -dimensional sobre el cuerpo de Galois GF (2) (NB: no GF (2 ⁿ ), cuya multiplicación es bastante diferente). Los 2 ^{2 n} vectores de este espacio, es decir, las combinaciones lineales de esos monomios como vectores unitarios, constituyen los polinomios de Zhegalkin. La concordancia exacta con el número de operaciones booleanas sobre n variables, que agotan las operaciones n -arias sobre {0,1}, proporciona un argumento de conteo directo para la completitud de los polinomios de Zhegalkin como base booleana.

Este espacio vectorial no es equivalente al álgebra booleana libre sobre n generadores porque carece de complementación (negación lógica bit a bit) como operación (de manera equivalente, porque carece del elemento superior como constante). Esto no quiere decir que el espacio no esté cerrado bajo complementación o que carezca de top (el vector de todos los unos ) como elemento, sino que las transformaciones lineales de este y otros espacios construidos de manera similar no necesitan preservar el complemento y el top. Aquellas que sí los preservan corresponden a los homomorfismos booleanos, por ejemplo, hay cuatro transformaciones lineales del espacio vectorial de polinomios de Zhegalkin sobre una variable a uno sobre ninguna, de las cuales solo dos son homomorfismos booleanos.

Método de cálculo

Existen varios métodos conocidos que se utilizan generalmente para el cálculo del polinomio de Zhegalkin:

• Utilizando el método de coeficientes indeterminados
• Construyendo la forma normal disyuntiva canónica
• Mediante el uso de tablas
• Método Pascal
• Método de suma
• Usando un mapa de Karnaugh

El método de coeficientes indeterminados

Utilizando el método de coeficientes indeterminados se genera un sistema lineal formado por todas las tuplas de la función y sus valores. Al resolver el sistema lineal se obtienen los coeficientes del polinomio de Zhegalkin.

Ejemplo

Dada la función booleana , exprésela como un polinomio de Zhegalkin. Esta función se puede expresar como un vector columna ${\displaystyle f(A,B,C)={\bar {A}}{\bar {B}}{\bar {C}}+{\bar {A}}B{\bar {C}}+A{\bar {B}}{\bar {C}}+ABC}$ $${\displaystyle {\vec {f}}={\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}.}$$

Este vector debe ser el resultado de multiplicar por la izquierda un vector de coeficientes indeterminados por una matriz lógica de 8x8 que representa los posibles valores que pueden tomar todas las posibles conjunciones de A, B, C. Estos posibles valores se dan en la siguiente tabla de verdad: $${\displaystyle {\vec {c}}={\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\c_{3}\\c_{4}\\c_{5}\\c_{6}\\c_{7}\end{pmatrix}}}$$

La información de la tabla de verdad anterior se puede codificar en la siguiente matriz lógica: donde la 'S' aquí representa "Sierpiński", como en triángulo de Sierpiński , y el subíndice 3 da los exponentes de su tamaño: . $${\displaystyle S_{3}={\begin{pmatrix}1&0&0&0&0&0&0&0\\1&1&0&0&0&0&0&0\\1&0&1&0&0&0&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&1&0&0&1&1&0&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}}$$ ${\displaystyle 2^{3}\times 2^{3}}$

Se puede demostrar mediante inducción matemática y multiplicación de matrices de bloques que cualquier "matriz de Sierpiński" es su propia inversa. ^{[nb 1]} ${\displaystyle S_{n}}$

Entonces el sistema lineal es que puede resolverse para : ^{[ aclaración necesaria ]} y el polinomio de Zhegalkin correspondiente a es . $${\displaystyle S_{3}{\vec {c}}={\vec {f}}}$$ ${\displaystyle {\vec {c}}}$ $${\displaystyle {\vec {c}}=S_{3}^{-1}{\vec {f}}=S_{3}{\vec {f}}={\begin{pmatrix}1&0&0&0&0&0&0&0\\1&1&0&0&0&0&0&0\\1&0&1&0&0&0&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&1&0&0&1&1&0&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}={\begin{pmatrix}1\\1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\oplus 1\\1\oplus 1\oplus 1\oplus 1\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\\0\\0\\1\\0\end{pmatrix}},}$$ ${\displaystyle {\vec {c}}}$ ${\displaystyle 1\oplus C\oplus AB}$

Utilizando la forma normal disyuntiva canónica

Con este método, primero se calcula la forma normal disyuntiva canónica (una forma normal disyuntiva completamente expandida ). Luego, las negaciones en esta expresión se reemplazan por una expresión equivalente que utiliza la suma módulo 2 de la variable y 1. Los signos de disyunción se cambian a suma módulo 2, se abren los corchetes y se simplifica la expresión booleana resultante. Esta simplificación da como resultado el polinomio de Zhegalkin.

Uso de tablas

Cálculo del polinomio de Zhegalkin para una función de ejemplo P mediante el método de la tabla

Sean las salidas de una tabla de verdad para la función P de n variables, tales que el índice de las corresponde a la indexación binaria de los mintérminos . ^{[nb 2]} Defina una función ζ recursivamente mediante: Nótese que donde es el coeficiente binomial reducido módulo 2. ${\displaystyle c_{0},\dots ,c_{2^{n}-1}}$ ${\displaystyle c_{i}}$ $${\displaystyle \zeta (c_{i}):=c_{i}}$$ $${\displaystyle \zeta (c_{0},\dots ,c_{k}):=\zeta (c_{0},\dots ,c_{k-1})\oplus \zeta (c_{1},\dots ,c_{k}).}$$ $${\displaystyle \zeta (c_{0},\dots ,c_{m})=\bigoplus _{k=0}^{m}{m \choose k}_{2}c_{k}}$$ ${\textstyle {m \choose k}_{2}}$

Entonces es el i ^-ésimo coeficiente de un polinomio de Zhegalkin cuyos literales en el i ^-ésimo monomio son los mismos que los literales en el i ^-ésimo mintérmino, excepto que los literales negativos se eliminan (o se reemplazan por 1). $${\displaystyle g_{i}=\zeta (c_{0},\dots ,c_{i})}$$

La transformación ζ es su propia inversa, por lo que se puede utilizar el mismo tipo de tabla para calcular los coeficientes dados los coeficientes . Simplemente sea ${\displaystyle c_{0},\dots ,c_{2^{n}-1}}$ ${\displaystyle g_{0},\dots ,g_{2^{n}-1}}$ $${\displaystyle c_{i}=\zeta (g_{0},\dots ,g_{i}).}$$

En términos de la tabla de la figura, copie los resultados de la tabla de verdad (en la columna etiquetada P ) en la columna más a la izquierda de la tabla triangular. Luego calcule sucesivamente las columnas de izquierda a derecha aplicando XOR a cada par de celdas adyacentes verticalmente para llenar la celda inmediatamente a la derecha de la celda superior de cada par. Cuando se completa toda la tabla triangular, la fila superior lee los coeficientes de una combinación lineal que, cuando se simplifica (eliminando los ceros), produce el polinomio de Zhegalkin.

Para pasar de un polinomio de Zhegalkin a una tabla de verdad, es posible llenar la fila superior de la tabla triangular con los coeficientes del polinomio de Zhegalkin (poniendo ceros para cualquier combinación de literales positivos que no estén en el polinomio). Luego, calcular sucesivamente las filas de arriba a abajo aplicando XOR a cada par de celdas adyacentes horizontalmente para llenar la celda inmediatamente inferior a la celda más a la izquierda de cada par. Cuando se llena toda la tabla triangular, la columna más a la izquierda de la misma se puede copiar a la columna P de la tabla de verdad.

Por otra parte, este método de cálculo corresponde al método de funcionamiento del autómata celular elemental llamado Regla 102. Por ejemplo, inicie un autómata celular de este tipo con ocho celdas configuradas con las salidas de la tabla de verdad (o los coeficientes de la forma normal disyuntiva canónica) de la expresión booleana: 10101001. Luego ejecute el autómata celular durante siete generaciones más mientras mantiene un registro del estado de la celda más a la izquierda. El historial de esta celda resulta ser: 11000010, que muestra los coeficientes del polinomio de Zhegalkin correspondiente. ^{[3] [4]}

El método Pascal

Utilizando el método Pascal para calcular el polinomio de Zhegalkin para la función booleana . La línea en ruso que aparece al final dice: – operación bit a bit "OR exclusivo" ${\displaystyle {\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}}$
${\displaystyle \oplus }$

El método más económico en términos de cantidad de cálculo y conveniente para construir el polinomio de Zhegalkin manualmente es el método de Pascal.

Construimos una tabla formada por columnas y filas, donde N es el número de variables de la función. En la fila superior de la tabla colocamos el vector de valores de la función, es decir, la última columna de la tabla de verdad. ${\displaystyle 2^{N}}$ ${\displaystyle N+1}$

Cada fila de la tabla resultante se divide en bloques (líneas negras en la figura). En la primera fila, el bloque ocupa una celda, en la segunda, dos, en la tercera, cuatro, en la cuarta, ocho, y así sucesivamente. Cada bloque de una determinada fila, que llamaremos "bloque inferior", siempre corresponde exactamente a dos bloques de la fila anterior. Los llamaremos "bloque superior izquierdo" y "bloque superior derecho".

La construcción comienza desde la segunda línea. El contenido de los bloques superiores izquierdos se transfiere sin cambios a las celdas correspondientes del bloque inferior (flechas verdes en la figura). Luego, la operación "suma módulo dos" se realiza bit a bit sobre los bloques superior derecho e izquierdo y el resultado se transfiere a las celdas correspondientes del lado derecho del bloque inferior (flechas rojas en la figura). Esta operación se realiza con todas las líneas de arriba a abajo y con todos los bloques de cada línea. Una vez completada la construcción, la línea inferior contiene una cadena de números, que son los coeficientes del polinomio de Zhegalkin, escritos en la misma secuencia que en el método del triángulo descrito anteriormente.

El método de suma

Representación gráfica de los coeficientes del polinomio de Zhegalkin para funciones con diferentes números de variables.

De acuerdo con la tabla de verdad, es fácil calcular los coeficientes individuales del polinomio de Zhegalkin. Para ello, se suman módulo 2 los valores de la función en aquellas filas de la tabla de verdad donde las variables que no están en la conjunción (que corresponde al coeficiente que se está calculando) toman valores cero.

Supongamos, por ejemplo, que necesitamos encontrar el coeficiente de la conjunción xz para la función de tres variables . No hay ninguna variable y en esta conjunción. Encuentre los conjuntos de entrada en los que la variable y toma un valor cero. Estos son los conjuntos 0, 1, 4, 5 (000, 001, 100, 101). Entonces el coeficiente en la conjunción xz es ${\displaystyle f(x,y,z)}$

$${\displaystyle a_{5}=f_{0}\oplus f_{1}\oplus f_{4}\oplus f_{5}=f(0,0,0)\oplus f(0,0,1)\oplus f(1,0,0)\oplus f(1,0,1)}$$

Como no hay variables con el término constante, $${\displaystyle a_{0}=f_{0}.}$$

Para un término que incluye todas las variables, la suma incluye todos los valores de la función: $${\displaystyle a_{N-1}=f_{0}\oplus f_{1}\oplus f_{2}\oplus \dots \oplus f_{N-2}\oplus f_{N-1}}$$

Representemos gráficamente los coeficientes del polinomio de Zhegalkin como sumas módulo 2 de los valores de las funciones en ciertos puntos. Para ello, construimos una tabla cuadrada, donde cada columna representa el valor de la función en uno de los puntos, y la fila es el coeficiente del polinomio de Zhegalkin. El punto en la intersección de alguna columna y fila significa que el valor de la función en este punto está incluido en la suma para el coeficiente dado del polinomio (ver figura). Llamamos a esta tabla , donde N es el número de variables de la función. ${\displaystyle T_{N}}$

Existe un patrón que permite obtener una tabla para una función de N variables, que consiste en tener una tabla para una función de variables. La nueva tabla se organiza como una matriz de tablas de 2 × 2 y se borra el bloque superior derecho de la matriz. ${\displaystyle N-1}$ ${\displaystyle T_{N}+1}$ ${\displaystyle T_{N}}$

Interpretación de la teoría reticular

Considere las columnas de una tabla como correspondientes a elementos de una red booleana de tamaño . Para cada columna, exprese el número M como un número binario , entonces si y solo si , donde denota OR bit a bit. ${\displaystyle T_{N}}$ ${\displaystyle 2^{N}}$ ${\displaystyle f_{M}}$ ${\displaystyle M_{2}}$ ${\displaystyle f_{M}\leq f_{K}}$ ${\displaystyle M_{2}\vee K_{2}=K_{2}}$ ${\displaystyle \vee }$

Si las filas de la tabla están numeradas, de arriba a abajo, con los números del 0 al , entonces el contenido tabular de la fila número R es el ideal generado por el elemento de la red. ${\displaystyle T_{N}}$ ${\displaystyle 2^{N}-1}$ ${\displaystyle f_{R}}$

Cabe señalar que el patrón general de una tabla es el de una matriz lógica, un triángulo de Sierpinski . Además, el patrón corresponde a un autómata celular elemental llamado Regla 60, que comienza con la celda más a la izquierda establecida en 1 y todas las demás celdas vacías. ${\displaystyle T_{N}}$

Usando un mapa de Karnaugh

Conversión de un mapa de Karnaugh en un polinomio de Zhegalkin.

La figura muestra una función de tres variables, P ( A , B , C ) representada como un mapa de Karnaugh , que el lector puede considerar como un ejemplo de cómo convertir dichos mapas en polinomios de Zhegalkin; el procedimiento general se da en los siguientes pasos:

• Consideramos todas las celdas del mapa de Karnaugh en orden ascendente del número de unidades en sus códigos. Para la función de tres variables, la secuencia de celdas será 000–100–010–001–110–101–011–111. Cada celda del mapa de Karnaugh está asociada a un miembro del polinomio de Zhegalkin dependiendo de las posiciones del código en las que hay unos. Por ejemplo, la celda 111 corresponde al miembro ABC, la celda 101 corresponde al miembro AC, la celda 010 corresponde al miembro B y la celda 000 corresponde al miembro 1.
• Si la celda en cuestión es 0, pase a la siguiente celda.
• Si la celda en cuestión es 1, se añade el término correspondiente al polinomio de Zhegalkin, luego se invierten todas las celdas en el mapa de Karnaugh donde este término es 1 (o perteneciente al ideal generado por este término, en una red booleana de monomios) y se pasa a la celda siguiente. Por ejemplo, si al examinar la celda 110 aparece un uno en ella, entonces se añade el término AB al polinomio de Zhegalkin y se invierten todas las celdas del mapa de Karnaugh, para lo cual A = 1 y B = 1. Si la unidad está en la celda 000, entonces se añade un término 1 al polinomio de Zhegalkin y se invierte todo el mapa de Karnaugh.
• El proceso de transformación puede considerarse completo cuando, después de la siguiente inversión, todas las celdas del mapa de Karnaugh se convierten en cero o en una condición de no importancia.

Transformación de Möbius

La fórmula de inversión de Möbius relaciona los coeficientes de una expresión de suma de mintérminos booleana y un polinomio de Zhegalkin. Esta es la versión de orden parcial de la fórmula de Möbius, no la teórica de números. La fórmula de inversión de Möbius para órdenes parciales es: ^[5] donde , | x | es la distancia de Hamming de x desde 0. Dado que en el álgebra de Zhegalkin, la función de Möbius colapsa a ser la constante 1. $${\displaystyle g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x),}$$ ${\displaystyle \mu (y,x)=(-1)^{|x|-|y|}}$ ${\displaystyle -1\equiv 1}$

El conjunto de divisores de un número dado x es también el ideal de orden generado por ese número: . Como la suma es módulo 2, la fórmula puede reformularse como ${\displaystyle \langle x\rangle }$ $${\displaystyle g(x)=\bigoplus _{y:y\in \langle x\rangle }f(y)\leftrightarrow f(x)=\bigoplus _{y:y\in \langle x\rangle }g(y)}$$

Ejemplo

A modo de ejemplo, consideremos el caso de tres variables. La siguiente tabla muestra la relación de divisibilidad:

Entonces $${\displaystyle {\begin{aligned}g(000)&=f(000)\\[1ex]g(001)&=f(000)\oplus f(001)\\[1ex]g(010)&=f(000)\oplus f(010)\\[1ex]g(011)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\\[1ex]g(100)&=f(000)\oplus f(100)\\[1ex]g(101)&=f(000)\oplus f(001)\oplus f(100)\oplus (101)\\[1ex]g(110)&=f(000)\oplus f(010)\oplus f(100)\oplus f(110)\\[1ex]g(111)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\oplus f(100)\oplus f(101)\oplus f(110)\oplus f(111)\end{aligned}}}$$

El sistema de ecuaciones anterior se puede resolver para f , y el resultado se puede resumir como obtenible intercambiando g y f en todo el sistema anterior.

La siguiente tabla muestra los números binarios junto con sus monomios de Zhegalkin y mintérminos booleanos asociados:

Los monomios de Zhegalkin se ordenan naturalmente por divisibilidad, mientras que los minitérminos booleanos no se ordenan de manera tan natural; cada uno representa un octavo exclusivo del diagrama de Venn de tres variables . El orden de los monomios se transfiere a las cadenas de bits de la siguiente manera: dados y , un par de tripletes de bits, entonces . ${\displaystyle a_{1}a_{2}a_{3}}$ ${\displaystyle b_{1}b_{2}b_{3}}$ ${\displaystyle a_{1}a_{2}a_{3}\leq b_{1}b_{2}b_{3}\leftrightarrow a_{1}\leq b_{1}\wedge a_{2}\leq b_{2}\wedge a_{3}\leq b_{3}}$

La correspondencia entre una suma de mintérminos booleana de tres variables y un polinomio de Zhegalkin es entonces: $${\displaystyle {\begin{aligned}&f(000){\bar {A}}{\bar {B}}{\bar {C}}\vee f(001){\bar {A}}{\bar {B}}C\vee f(010){\bar {A}}B{\bar {C}}\vee f(011){\bar {A}}BC\vee f(100)A{\bar {B}}{\bar {C}}\vee f(101)A{\bar {B}}C\vee f(110)AB{\bar {C}}\vee f(111)ABC\\[1ex]&\qquad \equiv g(000)\oplus g(001)C\oplus g(010)B\oplus g(011)BC\oplus g(100)A\oplus g(101)AC\oplus g(110)AB\oplus g(111)ABC.\end{aligned}}}$$

El sistema de ecuaciones anterior puede resumirse como una ecuación matricial lógica :

$${\displaystyle {\begin{pmatrix}g(000)\\g(001)\\g(010)\\g(011)\\g(100)\\g(101)\\g(110)\\g(111)\end{pmatrix}}={\begin{pmatrix}1&&0&&0&&0&&0&&0&&0&&0\\1&&1&&0&&0&&0&&0&&0&&0\\1&&0&&1&&0&&0&&0&&0&&0\\1&&1&&1&&1&&0&&0&&0&&0\\1&&0&&0&&0&&1&&0&&0&&0\\1&&1&&0&&0&&1&&1&&0&&0\\1&&0&&1&&0&&1&&0&&1&&0\\1&&1&&1&&1&&1&&1&&1&&1\end{pmatrix}}{\begin{pmatrix}f(000)\\f(001)\\f(010)\\f(011)\\f(100)\\f(101)\\f(110)\\f(111)\end{pmatrix}}}$$

que NJ Wildberger llama transformación de Boole-Möbius.

A continuación se muestra la forma de “ hoja de cálculo XOR ” de la transformación, que va en la dirección de g a f :

Trabajo relacionado

En 1927, el mismo año del artículo de Zhegalkin, ^[2] el matemático estadounidense Eric Temple Bell publicó una aritmetización sofisticada del álgebra de Boole basada en la teoría ideal de Richard Dedekind y la aritmética modular general (en oposición a la aritmética módulo 2). ^[6] El carácter aritmético mucho más simple de los polinomios de Zhegalkin fue notado por primera vez en Occidente (independientemente de que la comunicación entre matemáticos soviéticos y occidentales fuera muy limitada en esa época) por el matemático estadounidense Marshall Stone en 1936 ^[7] cuando observó mientras escribía su célebre teorema de dualidad de Stone que la analogía supuestamente vaga entre las álgebras de Boole y los anillos podía de hecho formularse como una equivalencia exacta válida tanto para las álgebras finitas como para las infinitas, lo que lo llevó a reorganizar sustancialmente su artículo en los siguientes años.

Véase también

• Forma normal algebraica (ANF)
• Expansión de Reed-Muller
• Dominio booleano
• Función con valor booleano
• Álgebra de Zhegalkin

Notas

1. Como caso base, donde se toma aquí para denotar la matriz identidad de tamaño . La suposición inductiva es Entonces el paso inductivo es: donde denota el producto de Kronecker , o, en términos del producto de Kronecker: QED $${\displaystyle S_{0}:={\begin{pmatrix}1\end{pmatrix}}}$$ $${\displaystyle (S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}}$$ ${\displaystyle I_{n}}$ ${\displaystyle 2^{n}\times 2^{n}}$ $${\displaystyle (S_{n})^{2}=I_{n}.}$$ $${\displaystyle S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n},}$$ ${\displaystyle \otimes }$ $${\displaystyle (S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1},}$$ $${\displaystyle S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}.}$$
2. Un mintérmino es la contraparte booleana de un monomio de Zhegalkin . Para un contexto de n variables, también hay monomios de Zhegalkin y mintérminos booleanos. Un mintérmino para un contexto de n variables consiste en un producto AND de n literales, cada literal es una variable en el contexto o la negación NOT de dicha variable. Además, para cada variable en el contexto debe aparecer exactamente una vez en cada mintérmino un literal correspondiente (ya sea la afirmación o la negación de esa variable). Una tabla de verdad para una función booleana de n variables tiene exactamente filas, las entradas de cada fila corresponden naturalmente a un mintérmino cuyo contexto es el conjunto de variables independientes de esa función booleana. (Cada entrada 0 corresponde a una variable negada; cada entrada 1 corresponde a una variable afirmada.)     Cualquier expresión booleana puede convertirse a la forma de suma de mintérminos distribuyendo repetidamente AND con respecto a OR, NOT con respecto a AND u OR (a través de las identidades de De Morgan), cancelando las negaciones dobles (cf. forma normal de negación ); y luego, cuando se ha obtenido una suma de productos, multiplicar los productos con literales faltantes con instancias de la ley del medio excluido que contengan los literales faltantes; luego, por último, distribuir AND con respecto a OR nuevamente.     Nótese que hay una correspondencia formal, para un contexto dado, entre los monomios de Zhegalkin y los mintérminos booleanos. Sin embargo, la correspondencia no es equivalencia lógica. Por ejemplo, para el contexto { A , B , C }, hay una correspondencia formal entre el monomio de Zhegalkin AB y el mintérmino booleano , pero no son lógicamente equivalentes. (Para obtener más información sobre este ejemplo, consulte la segunda tabla en la sección "Transformación de Möbius". El mismo conjunto de cadenas de bits se utiliza para indexar tanto el conjunto de mintérminos booleanos como el conjunto de monomios de Zhegalkin). ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$
   
   ${\displaystyle AB{\bar {C}}}$

Referencias

1. Steinbach, Bernd [en alemán] ; Posthoff, Christian (2009). "Prefacio". Escrito en Freiberg, Alemania. Funciones y ecuaciones lógicas: ejemplos y ejercicios (1.ª ed.). Dordrecht, Países Bajos: Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8. Número de serie LCCN  2008941076.
2. Жега́лкин [Zhegalkin], Ива́н Ива́нович [Ivan Ivanovich] (1927). "O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye" О технике вычислений предложений в символической логике [Sobre la técnica de cálculo de proposiciones en lógica simbólica (Sur le calcul des propositions dans la logique symbolique)]. Matematicheskii Sbornik (en ruso y francés). 34 (1). Moscú, Rusia: 9–28. Mi  msb7433. Archivado desde el original el 2017-10-12 . Consultado el 2017-10-12 .
3. Suprun [Супрун], Valeriy P. [Валерий Павлович] (1987). "Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy"Método de tabla de configuración de funciones polinómicas[El método tabular de descomposición polinómica de funciones booleanas]. Kibernetika [Кибернетика] (Cibernética) (en ruso) (1): 116–117.
4. Suprun [Супрун], Valeriy P. [Валерий Павлович] (2017). "Osnovy teorii bulevykh funktsiy"Основы теории булевых функций[Fundamentos de la teoría de funciones booleanas]. М.: Lenand [Ленанд] / URSS (en ruso): 208.
5. "Inversión de Möbius". Enciclopedia de Matemáticas . 2021-02-17 [2011-02-07]. Archivado desde el original el 2020-07-16 . Consultado el 2021-03-27 .
6. Bell, Eric Temple (1927). "Aritmética de la lógica". Transacciones de la American Mathematical Society . 29 (3): 597–611. doi : 10.2307/1989098 . JSTOR  1989098.
7. Stone, Marshall (1936). "La teoría de representaciones para álgebras de Boole". Transactions of the American Mathematical Society . 40 (1): 37–111. doi :10.2307/1989664. ISSN  0002-9947. JSTOR  1989664.

Lectura adicional

• Gindikin [Гиндикин], Semen Grigorʹevich [Семен Г.] (1972). Lógica algebraica алгебра логики в задачах [ Lógica algebraica ] (en ruso) (1 ed.). Moscú, Rusia: Наука [Nauka] . ISBN 0-387-96179-8.(288 páginas) (NB. Traducción: Springer-Verlag , 1985.[1])
• Perkowski, Marek A.; Grygiel, Stanislaw (20 de noviembre de 1995). "6. Panorama histórico de la investigación sobre descomposición". Un estudio de la literatura sobre descomposición de funciones. Versión IV. Grupo de descomposición funcional, Departamento de ingeniería eléctrica, Universidad de Portland, Portland, Oregón, EE. UU., págs. 21–22. CiteSeerX  10.1.1.64.1129 .(188 páginas)