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 á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 podí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, (escrita 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, sin 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 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 ⁿ dimensiones sobre el campo 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 agotan las n operaciones arias 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 que carezca de top (el vector de todos unos ) como elemento, sino más bien que las transformaciones lineales de este y otros espacios construidos de manera similar no necesitan preservar el complemento y top. Aquellos que los conservan corresponden a los homomorfismos booleanos, por ejemplo, hay cuatro transformaciones lineales del espacio vectorial de los polinomios de Zhegalkin sobre una variable al de ninguna, de las cuales sólo dos son homomorfismos booleanos.

Método de cálculo

Existen varios métodos conocidos que se utilizan generalmente para calcular el 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 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ésala 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}}}$$

matriz lógica

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

el triángulo de Sierpiński ${\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. ^{[nota 1]} ${\displaystyle S_{n}}$

Entonces el sistema lineal es

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

^{[ se necesita aclaración ]} ${\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}$

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, se abren los corchetes y se simplifica la expresión booleana resultante. 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 la tabla

Sean las salidas de una tabla de verdad para la función P de n variables, de modo que el índice de las 's corresponda a la indexación binaria de los mintérminos . ^{[nb 2]} Defina una función ζ recursivamente mediante: ${\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}}$$

coeficiente binomialmódulo ${\textstyle {m \choose k}_{2}}$

Entonces

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

i- ^ésimoi ^-ésimoi ^-ésimo

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},\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 denominada 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 verticalmente adyacentes 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 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 las 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 toda la tabla triangular esté llena, la columna más a la izquierda se puede copiar a la columna P de la tabla de verdad.

Además, este método de cálculo corresponde al método de operación del autómata celular elemental llamado Regla 102. Por ejemplo, inicie dicho autómata celular con ocho celdas configuradas con los resultados de la tabla de verdad (o los coeficientes de la tabla de verdad canónica). forma normal disyuntiva) 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 "OR 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álculos y conveniente para construir manualmente el polinomio de Zhegalkin es el método de Pascal.

Construimos una tabla que consta de 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 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 determinada línea, 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 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 la 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 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 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 está incluido en la suma del coeficiente dado del polinomio (ver figura). A esta tabla la llamamos , 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, 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ías

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

Tenga en cuenta de paso que el patrón general de una tabla es el de una matriz lógica del triángulo de Sierpiński . 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 borradas. ${\displaystyle T_{N}}$

Usando un mapa de Karnaugh

Conversión de un mapa de Karnaugh a 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 según el 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 se encuentran. 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 sea 1 (o que pertenezcan 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 un uno en ella, entonces el término AB se suma 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 se puede considerar completo cuando, después de la siguiente inversión, todas las celdas del mapa de Karnaugh se vuelven cero, o una condición de no importa.

Transformación de Moebius

La fórmula de inversión de Möbius relaciona los coeficientes de una expresión booleana de suma de minté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: ^[5]

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

xdistancia de Hammingx ${\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: . 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, 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 están ordenados naturalmente por divisibilidad, mientras que los mintérminos booleanos no se ordenan a sí mismos de manera tan natural; cada uno representa una octava exclusiva 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 booleana de minitérminos 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 se puede resumir 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, yendo 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 sofisticada aritmetización del álgebra booleana basada en la teoría ideal de Richard Dedekind y la aritmética modular general (en contraposición a la aritmética mod 2). ^[6] El carácter aritmético mucho más simple de los polinomios de Zhegalkin fue observado por primera vez en Occidente (de forma independiente, 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 dualidad de Stone de que la analogía supuestamente vaga entre las álgebras de Boole y los anillos podría de hecho 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)
• Expansión de Reed-Muller
• dominio booleano
• Función con 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 aquí se toma para denotar la matriz 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 de 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}.}$$
   QED
2. Un mintérmino es la contraparte booleana de un monomio de Zhegalkin . Para un contexto de n variables, también existen monomios de Zhegalkin y mintérminos booleanos. Un término mínimo para un contexto de n variables consiste en un producto AND de n literales, siendo cada literal 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 minité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, y 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 mintérminos distribuyendo repetidamente AND con respecto a OR, NOT con respecto a AND o O (a través de las identidades de De Morgan), anulando negaciones dobles (cf. forma normal de negación ); y luego, cuando se haya obtenido una suma de productos, multiplicar productos con literales faltantes con instancias de la ley del medio excluido que contengan los literales faltantes; luego, por último, distribuya AND con respecto a OR nuevamente.     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 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 de 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, cristiano (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). 34 (1). Moscú, Rusia: 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"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 16 de julio de 2020 . Consultado el 27 de marzo de 2021 .
6. Campana, Eric Temple (1927). "Aritmética de la Lógica". Transacciones de la Sociedad Matemática Estadounidense . 29 (3): 597–611. doi : 10.2307/1989098 . JSTOR  1989098.
7. Piedra, Marshall (1936). "La teoría de las representaciones de álgebras de Boole". Transacciones de la Sociedad Matemática Estadounidense . 40 (1): 37-111. doi :10.2307/1989664. ISSN  0002-9947. JSTOR  1989664.

Otras lecturas

• 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, Oregon, EE.UU. págs. 21-22. CiteSeerX  10.1.1.64.1129 .(188 páginas)