We can proceed more algebraically by assigning value \(0\) to represent false and value \(1\) to represent true.
Example3.1.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 \lgcand q\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgcfalse\)
Example3.1.2.Boolean addition.
Comparing the following two tables, we see that Boolean addition is equivalent to exclusive or.
\(x\)
\(y\)
\(x + y\)
\(1\)
\(1\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(1\)
\(1\)
\(0\)
\(0\)
\(0\)
\(p\)
\(q\)
\(\lgcnot (p \lgcbicond q)\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgcfalse\)
Example3.1.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 \lgcor q\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgctrue\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgcfalse\)
Example3.1.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\)
\(\lgcnot p\)
\(\lgctrue\)
\(\lgcfalse\)
\(\lgcfalse\)
\(\lgctrue\)
For notation, we borrow symbols \(\lgcand\) and \(\lgcor\) from logic, but add new negation notation.
\(\boolnot{x}\)
Boolean negation
With this notation setup, we have
\begin{align*}
x \lgcand y \amp = x y \text{,} \amp
x \lgcor y \amp = x + y + x y \text{,} \amp
\boolnot{x} \amp = x + 1 \text{.}
\end{align*}
Boolean polynomial
an expression involving variables \(x_1, x_2, \dotsc, x_m\) representing Boolean values, and operations \(\lgcand, \lgcor, \boolnot{}\text{,}\) often written in function notation
Note3.1.5.
Every Boolean polynomial can be interpreted as a logical statement.
Example3.1.6.
There are two special constant Boolean polynomials, the zero polynomial and the unit polynomial:
The Boolean polynomials \(p(x,y) = x' \lgcor y\) and \(q(x,y) = (x \lgcand y')'\) have the same truth table.
\(x\)
\(y\)
\(x'\)
\(p(x,y)\)
\(y'\)
\(x \lgcand 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.
equivalent polynomials
Boolean polynomials which represent equivalent logical statements
