Conversión de expresiones booleanas en polinomios

Question

¿Existe una forma sencilla de convertir una expresión booleana general compuesta por variables $x_1,\cdots,x_n)$ ys; ors; y nots a un polinomio en $p\in\mathbb{F}_2[x_1,\cdots,x_n]$ de forma que se conserve la tabla de verdad? Por ejemplo, podríamos identificar " $x_1\text{or } x_2$ " con $1-(1-x_1)(1-x_2)$ .

Answer 1

Me parece que has hecho todo el trabajo duro al idear una expresión para el $\lor$ . Porque $\neg x$ es simplemente $1-x$ y $x \land y$ es $xy$ .

Answer 2

Como usted dijo, ou puede codificarse como $D(x_{1}, x_{2}) = 1-(1-x_{1})(1-x_{2})$ y se puede demostrar fácilmente que y puede codificarse como $C(x_{1}, x_{2})=x_{1}x_{2}$ y no puede codificarse como $N(x_{1})=1-x_{1}$ . Las expresiones complejas son, como ya he dicho, composiciones de estas operaciones.

Por ejemplo $$P(x_{1}, x_{2}, x_{3}) = \neg(x_{1} \land x_{3}) \lor(x_{2}\land x_{3}).$$

Podemos codificarlo utilizando $C, D$ y $N$ como $$ 1-(1-(1-x_{1}x_{3}))(1-x_{2}x_{3})=1-x_{1}x_{3}(1-x_{2}x_{3}).$$

Answer 3

Si realizas la aritmética en el campo de dos elementos GF(2) entonces XOR es suma, AND es multiplicación, NOT sigue siendo $1-x$ y OR puede definirse como $x_1 + x_2 + x_1x_2$ .

Lo he sacado casi textualmente de Artículo de Wikipedia sobre álgebra booleana . Véase también Polinomio de Zhegalkin . Y buscando en Google "polinomio booleano" se obtienen muchas respuestas relevantes.

De hecho, varias tareas informáticas habituales se definen a partir de polinomios booleanos, CRC y registros de desplazamiento de realimentación lineal, por citar algunos ejemplos.