3.1: Polinomios booleanos

Podemos proceder más algebraicamente asignando valor\(0\) para representar falso y valor\(1\) para representar verdadero.

Ejemplo\(\PageIndex{1}\): Boolean Multiplication

Comparando las dos tablas siguientes, vemos que la multiplicación booleana es equivalente a la conjunción lógica.

\(x\)	\(y\)	\(x y\)
\(1\)	\(1\)	\(1\)
\(1\)	\(0\)	\(0\)
\(0\)	\(1\)	\(0\)
\(0\)	\(0\)	\(0\)

\(p\)	\(q\)	\(p \land q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(F\)

Ejemplo\(\PageIndex{2}\): Boolean addition.

Comparando las dos tablas siguientes, vemos que la adición booleana es equivalente a exclusiva o.

Aritmética booleana

Observe que en la primera fila para la suma booleana, usamos la\(2\) aritmética mod para definir\(1+1 = 0\text{.}\)

\(x\)	\(y\)	\(x + y\)
\(1\)	\(1\)	\(0\)
\(1\)	\(0\)	\(1\)
\(0\)	\(1\)	\(1\)
\(0\)	\(0\)	\(0\)

\(p\)	\(q\)	\(\neg (p \leftrightarrow q)\)
\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)

Ejemplo\(\PageIndex{3}\): Boolean Disjunction

En la aritmética booleana podemos realizar disyunción combinando tanto la suma como la multiplicación.

\(x\)	\(y\)	\(x + y + x y\)
\(1\)	\(1\)	\(1\)
\(1\)	\(0\)	\(1\)
\(0\)	\(1\)	\(1\)
\(0\)	\(0\)	\(0\)

\(p\)	\(q\)	\(p \lor q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)

Ejemplo\(\PageIndex{4}\): Boolean Negation

En álgebra booleana, la negación es solo cuestión de cambiar un valor al siguiente.

\(x\)	\(x + 1\)
\(1\)	\(0\)
\(0\)	\(1\)

\(p\)	\(\neg p\)
\(T\)	\(F\)
\(F\)	\(T\)

Para la notación, tomamos prestados símbolos\(\land \) y\(\lor\) de la lógica, pero agregamos nueva notación de negación.

\(x'\)Negación booleana

Con esta configuración de notación, tenemos

\ begin {alinear*} x\ land y & = x y\ text {,} & x\ lor y & = x + y + x y\ text {,} & x' & = x + 1\ text {.} \ end {alinear*}

Definición: Polinomio booleano

una expresión que involucra variables\(x_1, x_2, \ldots, x_m\) que representan valores booleanos y operaciones escritas\(\land , \lor, '\text{,}\) a menudo en notación de funciones

Nota\(\PageIndex{1}\)

Cada polinomio booleano puede interpretarse como una declaración lógica.

Ejemplo\(\PageIndex{5}\)

Hay dos polinomios booleanos constantes especiales, el polinomio cero y el polinomio unitario:

\ begin {align*} 0 (x_1, x_2,\ ldots, x_m) & = 0\ text {,} & 1 (x_1, x_2,\ ldots, x_m) & = 1\ texto {.} \ end {alinear*}

Ejemplo\(\PageIndex{6}\)

Los polinomios booleanos\(p(x,y) = x' \lor y\) y\(q(x,y) = (x \land y')'\) tienen la misma tabla de verdad.

\(x\)	\(y\)	\(x'\)	\(p(x,y)\)	\(y'\)	\(x \land y'\)	\(q(x,y)\)
\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)
\(1\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(0\)
\(0\)	\(1\)	\(1\)	\(1\)	\(0\)	\(0\)	\(1\)
\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(0\)	\(1\)

Usando nuestro conocimiento de equivalencia lógica, vemos que las tablas de verdad son las mismas porque como declaraciones lógicas,\(p\) y\(q\) son equivalentes por DeMorgan.

Definición: Polinomios equivalentes

Polinomios booleanos que representan sentencias lógicas equivalentes

Hecho\(\PageIndex{1}\): Recognizing Equivalent Boolean Polynomials

Los polinomios\(p,q\) son equivalentes si y sólo si tienen la misma tabla de verdad.