Polinomio de Zhegalkin

Zhegalkin (también Žegalkin , Gégalkine o Shegalkin ^[1] ) polinomios 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 polinomial 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 coeficientes ni exponentes. Los coeficientes son redundantes porque 1 es el único coeficiente distinto de cero. Los exponentes son redundantes porque en aritmética mod 2, x² = x . Por lo tanto, un polinomio como 3 x ² y ⁵ z es congruente y, por lo tanto, puede reescribirse como xyz .

Equivalente booleano

Antes de 1927, el álgebra de Boole se consideraba 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 podrían escribirse como polinomios numéricos ordinarios, representando los valores falso y verdadero como 0 y 1, los enteros mod 2. La conjunción lógica se escribe como xy , y la lógica exclusiva o como suma aritmética mod 2, (escrito aquí como x ⊕ y para evitar confusión con el uso común de + como sinónimo de inclusivo-o ∨). El complemento lógico ¬ x es entonces x⊕1. Dado que ∧ y ¬ forman una base para el álgebra booleana, todas las demás operaciones lógicas son composiciones de estas operaciones básicas, por lo que los polinomios del álgebra ordinaria pueden representar todas las operaciones booleanas, lo que permite realizar el razonamiento booleano utilizando álgebra elemental .

Por ejemplo, el umbral booleano 2 de 3 o la operación mediana 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 el presencia o ausencia de cada variable. Un polinomio de Zhegalkin es la suma (exclusiva-o) 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 Zhegalkin, siendo linealmente independientes , abarcan un 2 ⁿ -dimensional espacio vectorial sobre elCampo 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 en n variables, que agota las n operaciones ararias en {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 en 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 carezca de top (el vector de todos unos ) como elemento, sino más bien que las transformaciones lineales de este y los espacios construidos de manera similar no necesitan preservar el complemento y la parte superior. Aquellos que los conservan corresponden a los homomorfismos booleanos, por ejemplo, hay cuatro transformaciones lineales desde el espacio vectorial de los polinomios de Zhegalkin sobre una variable a la de ninguna, de las cuales solo dos son homomorfismos booleanos.

Método de cálculo

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

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

El método de los coeficientes indeterminados.

Utilizando el método de coeficientes indeterminados, se genera un sistema lineal que consta de todas las tuplas de la función y sus valores. Resolver el sistema lineal da los coeficientes del polinomio de Zhegalkin.

Ejemplo

Dada la función booleana , expresela como un polinomio de Zhegalkin. Esta función se puede expresar como un vector de 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

${\displaystyle {\vec {c}}={\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\c_{3}\\c_{4}\\c_{5}\\c_{6}\\c_{7}\end{pmatrix}}}$

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 {\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}A&B&C&\;\;\;\;\;\;\;\;&1&C&B&BC&A&AC&AB&ABC\\\hline 0&0&0&&1&0&0&0&0&0&0&0\\0&0&1&&1&1&0&0&0&0&0&0\\0&1&0&&1&0&1&0&0&0&0&0\\0&1&1&&1&1&1&1&0&0&0&0\\1&0&0&&1&0&0&0&1&0&0&0\\1&0&1&&1&1&0&0&1&1&0&0\\1&1&0&&1&0&1&0&1&0&1&0\\1&1&1&&1&1&1&1&1&1&1&1\end{array}}}$.

La información de la tabla de verdad anterior se puede codificar en la siguiente matriz lógica:

${\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}}}$

donde el 'S' aquí significa "Sierpiński", como en el triángulo de Sierpinski , y el subíndice 3 da los exponentes de su tamaño: .${\displaystyle 2^{3}\times 2^{3}}$

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

Entonces el sistema lineal es

${\displaystyle S_{3}{\vec {c}}={\vec {f}}}$

que se puede resolver para :${\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}}}$,

y el polinomio de Zhegalkin correspondiente a es .${\displaystyle {\vec {c}}}$${\displaystyle 1\oplus C\oplus AB}$

Usando 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 usando la suma mod 2 de la variable y 1. Los signos de disyunción se cambian a la suma mod 2, los corchetes se abren y la expresión booleana resultante se simplifica. Esta simplificación da como resultado el polinomio de Zhegalkin.

Usando tablas

Calcular el polinomio de Zhegalkin para una función de ejemplo P mediante el método de tabla

Sean las salidas de una tabla de verdad para la función P de n variables, de manera que el índice de los corresponde a la indexación binaria de los minitérminos . ^{[nb 2]} Defina una función ζ recursivamente mediante:${\displaystyle c_{0},...,c_{2^{n}-1}}$${\displaystyle c_{i}}$

${\displaystyle \zeta (c_{i}):=c_{i}}$

${\displaystyle \zeta (c_{0},...,c_{k}):=\zeta (c_{0},...,c_{k-1})\oplus \zeta (c_{1},...,c_{k})}$.

Tenga en cuenta que

${\displaystyle \zeta (c_{0},...,c_{m})=\bigoplus _{k=0}^{m}{m \choose k}_{2}c_{k}}$

donde es el coeficiente binomial reducido módulo 2.${\displaystyle {m \choose k}_{2}}$

Luego

${\displaystyle g_{i}=\zeta (c_{0},...,c_{i})}$

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 minitérmino, excepto que los literales negativos se eliminan (o se reemplazan por 1).

La transformación ζ es su propia inversa, por lo que se puede usar el mismo tipo de tabla para calcular los coeficientes dados los coeficientes . Sólo dejalo${\displaystyle c_{0},...,c_{2^{n}-1}}$${\displaystyle g_{0},...,g_{2^{n}-1}}$

${\displaystyle c_{i}=\zeta (g_{0},...,g_{i})}$.

En términos de la tabla de la figura, copie las salidas 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 llena 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 completar 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, calcule sucesivamente filas de arriba a abajo aplicando XOR a cada par de celdas adyacentes horizontalmente para llenar la celda inmediatamente hasta la parte inferior de la celda más a la izquierda de cada par. Cuando se llena toda la tabla triangular, la columna más a la izquierda se puede copiar a la columna P de la tabla de verdad.

Como acotación al margen, tenga en cuenta que 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

Usando el método Pascal para calcular el polinomio de Zhegalkin para la función booleana . La línea en ruso en la parte inferior dice: - operación bit a bit "O exclusivo"${\displaystyle {\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}}$
${\displaystyle \oplus }$

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

Construimos una tabla que consta de columnas y filas, donde N es el número de variables en 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 línea, el bloque ocupa una celda, en la segunda línea, dos, en la tercera, cuatro, en la cuarta, ocho, y así sucesivamente. Cada bloque de una línea determinada, que llamaremos "bloque inferior", siempre corresponde exactamente a dos bloques de la línea 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 en cada línea. Una vez completada la construcción, la línea inferior contiene una serie 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 diferente número de variables.

Según la tabla de verdad, es fácil calcular los coeficientes individuales del polinomio de Zhegalkin. Para ello, suma 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 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)}$

Dado que 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 ...\oplus f_{N-2}\oplus f_{N-1}}$

Representemos gráficamente los coeficientes del polinomio de Zhegalkin como sumas módulo 2 de valores de funciones en ciertos puntos. Para hacer esto, 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 se incluye en la suma del 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 le permite obtener una tabla para una función de N variables, teniendo 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 de celosía

Considere las columnas de una tabla como correspondientes a elementos de una celosía booleana de tamaño . Para cada columna, exprese el número M como un número binario , luego 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 de 0 a , entonces el contenido tabular de la fila número R es el ideal generado por el elemento de la celosía.${\displaystyle T_{N}}$${\displaystyle 2^{N}-1}$${\displaystyle f_{R}}$

Por cierto, tenga en cuenta que el patrón general de una tabla es el de un triángulo de Sierpiński de matriz lógica . Además, el patrón corresponde a un autómata celular elemental llamado Regla 60 , comenzando con la celda más a la izquierda configurada en 1 y todas las demás celdas despejadas.${\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 ) representadas como un mapa de Karnaugh , que el lector puede considerar como un ejemplo de cómo convertir tales 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 con un miembro del polinomio de Zhegalkin dependiendo de las posiciones del código en el que hay algunos. 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, agregue el término correspondiente al polinomio de Zhegalkin, luego invierta 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 vaya a la siguiente celda. Por ejemplo, si, al examinar la celda 110, aparece uno en ella, entonces el término AB se agrega al polinomio de Zhegalkin y todas las celdas del mapa de Karnaugh se invierten, para lo cual A = 1 y B = 1. Si la unidad está en celda 000, luego se agrega 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 vuelven cero o una condición de indiferencia.

Transformación de Moebius

La fórmula de inversión de Möbius relaciona los coeficientes de una expresión booleana de suma de minitérminos y un polinomio de Zhegalkin. Esta es la versión de orden parcial de la fórmula de Möbius, no la teoría de números. La fórmula de inversión de Möbius para órdenes parciales es:

${\displaystyle g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x)}$, ^[5]

donde , | x | siendo la distancia de Hamming de x desde 0. Dado que en el álgebra de Zhegalkin, la función de Möbius colapsa para ser la constante 1.${\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 orden ideal generada por ese número: . Dado que la suma es módulo 2, la fórmula se puede reformular 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

Como ejemplo, considere el caso de tres variables. La siguiente tabla muestra la relación de divisibilidad:

X	divisores de x
000	000
001	000, 001
010	000, 010
011	000, 001, 010, 011
100	000, 100
101	000, 001, 100, 101
110	000, 010, 100, 110
111	000, 001, 010, 011, 100, 101, 110, 111

Luego

${\displaystyle g(000)=f(000)}$

${\displaystyle g(001)=f(000)\oplus f(001)}$

${\displaystyle g(010)=f(000)\oplus f(010)}$

${\displaystyle g(011)=f(000)\oplus f(001)\oplus f(010)\oplus f(011)}$

${\displaystyle g(100)=f(000)\oplus f(100)}$

${\displaystyle g(101)=f(000)\oplus f(001)\oplus f(100)\oplus (101)}$

${\displaystyle g(110)=f(000)\oplus f(010)\oplus f(100)\oplus f(110)}$

${\displaystyle 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)}$

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

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

Minitérmino booleano	A B C	Monomio de Zhegalkin
${\displaystyle {\bar {A}}{\bar {B}}{\bar {C}}}$	000	1
${\displaystyle {\bar {A}}{\bar {B}}C}$	001	C
${\displaystyle {\bar {A}}B{\bar {C}}}$	010	B
${\displaystyle {\bar {A}}BC}$	011	antes de Cristo
${\displaystyle A{\bar {B}}{\bar {C}}}$	100	A
${\displaystyle A{\bar {B}}C}$	101	C.A.
${\displaystyle AB{\bar {C}}}$	110	AB
${\displaystyle ABC}$	111	A B C

Los monomios de Zhegalkin están ordenados naturalmente por divisibilidad, mientras que los minitérminos booleanos no se ordenan de forma 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: dado 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 minitérminos booleanos de tres variables y un polinomio de Zhegalkin es entonces:

${\displaystyle 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}$

${\displaystyle \qquad \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}$.

El sistema de ecuaciones anterior se puede resumir como una ecuación de matriz 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 una transformación Boole-Möbius.

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

${\displaystyle f_{000}}$	${\displaystyle f_{001}}$	${\displaystyle f_{010}}$	${\displaystyle f_{011}}$	${\displaystyle f_{100}}$	${\displaystyle f_{101}}$	${\displaystyle f_{110}}$	${\displaystyle f_{111}}$
${\displaystyle g_{000}}$	${\displaystyle g_{000}\oplus g_{001}}$	${\displaystyle g_{000}\oplus g_{010}}$	${\displaystyle g_{000}\oplus g_{010}\oplus g_{001}\oplus g_{011}}$	${\displaystyle g_{000}\oplus g_{100}}$	${\displaystyle g_{000}\oplus g_{100}\oplus g_{001}\oplus g_{101}}$	${\displaystyle g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}}$	${\displaystyle g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}\oplus g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}}$
${\displaystyle g_{001}}$	${\displaystyle g_{001}\oplus g_{010}}$	${\displaystyle g_{001}\oplus g_{011}}$	${\displaystyle g_{001}\oplus g_{011}\oplus g_{010}\oplus g_{100}}$	${\displaystyle g_{001}\oplus g_{101}}$	${\displaystyle g_{001}\oplus g_{101}\oplus g_{010}\oplus g_{110}}$	${\displaystyle g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}}$
${\displaystyle g_{010}}$	${\displaystyle g_{010}\oplus g_{011}}$	${\displaystyle g_{010}\oplus g_{100}}$	${\displaystyle g_{010}\oplus g_{100}\oplus g_{011}\oplus g_{101}}$	${\displaystyle g_{010}\oplus g_{110}}$	${\displaystyle g_{010}\oplus g_{110}\oplus g_{011}\oplus g_{111}}$
${\displaystyle g_{011}}$	${\displaystyle g_{011}\oplus g_{100}}$	${\displaystyle g_{011}\oplus g_{101}}$	${\displaystyle g_{011}\oplus g_{101}\oplus g_{100}\oplus g_{110}}$	${\displaystyle g_{011}\oplus g_{111}}$
${\displaystyle g_{100}}$	${\displaystyle g_{100}\oplus g_{101}}$	${\displaystyle g_{100}\oplus g_{110}}$	${\displaystyle g_{100}\oplus g_{110}\oplus g_{101}\oplus g_{111}}$
${\displaystyle g_{101}}$	${\displaystyle g_{101}\oplus g_{110}}$	${\displaystyle g_{101}\oplus g_{111}}$
${\displaystyle g_{110}}$	${\displaystyle g_{110}\oplus g_{111}}$
${\displaystyle g_{111}}$

Trabajo relacionado

En 1927, el mismo año que el artículo de Zhegalkin, ^[2] el matemático estadounidense Eric Temple Bell publicó una sofisticada aritmetización del álgebra booleana basada en la teoría ideal de Richard Dedekind y la aritmética modular general (en oposición a la aritmética mod 2). ^[6] El carácter aritmético mucho más simple de los polinomios de Zhegalkin se notó por primera vez en Occidente (independientemente, la comunicación entre los matemáticos soviéticos y occidentales era 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 la dualidad de Stone de que la analogía supuestamente vaga entre las álgebras de Booley los anillos , de hecho, podrían formularse como una equivalencia exacta para álgebras finitas e infinitas, lo que lo llevó a reorganizar sustancialmente su artículo durante los próximos años.

Ver también

• Forma normal algebraica (ANF)
• Forma normal de suma de anillo (RSNF)
• Expansión Reed-Muller
• Dominio booleano
• Función de valor booleano

Notas

1. Como caso base,

   ${\displaystyle S_{0}:={\begin{pmatrix}1\end{pmatrix}}}$

   ${\displaystyle (S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}}$

   donde se toma aquí para denotar la matriz de identidad de tamaño . El supuesto inductivo es${\displaystyle I_{n}}$${\displaystyle 2^{n}\times 2^{n}}$

   ${\displaystyle (S_{n})^{2}=I_{n}}$.

   Entonces el paso inductivo es:

   ${\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}}$,

   donde denota el producto Kronecker ,${\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}}$,

   o, en términos del producto Kronecker:

   ${\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 minitérmino es la contraparte booleana de un monomio de Zhegalkin. Para uncontexto de n- variables, también haymonomios de Zhegalkin yminitérminos booleanos. Un término producto para un n contexto -Variable consiste en un Y-producto de n literales, cada literal o bien ser una variable en el contexto o la NO-negación de una variable tal. Además, para cada variable en el contexto debe aparecer exactamente una vez en cada término mínimo 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${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$filas, las entradas de cada fila corresponden naturalmente a un minité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 se puede convertir a la forma de suma de minitérminos distribuyendo repetidamente Y con respecto a O, NO con respecto a Y o O (a través de las identidades de De Morgan), anulando las dobles negaciones (cf. forma normal de negación ); y luego, cuando se haya obtenido una suma de productos, multiplique los productos con literales faltantes con instancias de la ley del medio excluido que contengan las literales faltantes; luego, por último, distribuya AND con respecto a OR de nuevo.
       Tenga en cuenta que existe una correspondencia formal, para un contexto dado, entre los monomios de Zhegalkin y los minitérminos booleanos. Sin embargo, la correspondencia no es una equivalencia lógica. Por ejemplo, para el contexto { A , B , C }, existe una correspondencia formal entre el monomio Zhegalkin AB y el minitérmino booleano , pero no son lógicamente equivalentes. (Para ver más de 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 minitérminos booleanos como el conjunto de monomios de Zhegalkin).${\displaystyle AB{\bar {C}}}$

Referencias

1. Steinbach, Bernd ; 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. 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). Moscú, Rusia. 34 (1): 9-28. Mi msb7433 . Archivado desde el original el 12 de octubre de 2017 . Consultado el 12 de octubre de 2017 . 
3. Suprun [Супрун], Valeriy P. [Валерий Павлович] (1987). "Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy"Табличный метод полиномиального разложения булевых функций[El método tabular de descomposición polinomial de funciones booleanas]. Kibernetika [Кибернетика] (Cybernetics) (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 16 de julio de 2020 . Consultado el 27 de marzo de 2021 .
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. Piedra, Marshall (1936). "La teoría de las representaciones para álgebras de Boole". Transacciones de la American Mathematical Society . 40 (1): 37-111. doi : 10.2307 / 1989664 . ISSN 0002-9947 . JSTOR 1989664 .  

Otras lecturas

• Gindikin [Гиндикин], Semen Grigorʹevich [Семен Г.] (1972). алгебра логики в задачах[ 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. Reseña histórica de la investigación sobre la descomposición". Un estudio de la literatura sobre la 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)