3.1: Boolean Polynomials

We can proceed more algebraically by assigning value \(0\) to represent false and value \(1\) to represent true.

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

Comparing the two tables below, we see that Boolean multiplication is equivalent to logical conjunction.

\(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\)

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

Comparing the following two tables, we see that Boolean addition is equivalent to exclusive or.

Boolean Arithmetic

Notice that in the first row for Boolean addition, we use mod \(2\) arithmetic to define \(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\)

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

In Boolean arithmetic we may realize disjunction by combining both addition and multiplication.

\(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\)

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

In Boolean algebra, negation is just a matter of shifting one value to the next.

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

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

For notation, we borrow symbols \(\land \) and \(\lor\) from logic, but add new negation notation.

\(x'\) Boolean negation

With this notation setup, we have

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

Definition: Boolean Polynomial

an expression involving variables \(x_1, x_2, \ldots, x_m\) representing Boolean values, and operations \(\land , \lor, '\text{,}\) often written in function notation

Note \(\PageIndex{1}\)

Every Boolean polynomial can be interpreted as a logical statement.

Example \(\PageIndex{5}\)

There are two special constant Boolean polynomials, the zero polynomial and the unit polynomial:

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

Example \(\PageIndex{6}\)

The Boolean polynomials \(p(x,y) = x' \lor y\) and \(q(x,y) = (x \land y')'\) have the same truth table.

\(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\)

Using our knowledge of logical equivalence, we see that the truth tables are the same because as logical statements, \(p\) and \(q\) are equivalent by DeMorgan.

Definition: Equivalent Polynomials

Boolean polynomials which represent equivalent logical statements

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

Polynomials \(p,q\) are equivalent if and only if they have the same truth table.