Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 3.1 Boolean polynomials
We can proceed more algebraically by assigning value
\(0 \) to represent false and value
\(1 \) to represent true.
Example 3.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 \)
Example 3.1.2 . Boolean addition.
Boolean arithmetic is
mod \(2 \) arithmetic , in which
\(2 \) is considered equivalent to
\(0 \text{.}\) Using this, by 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 \)
Example 3.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 \)
Example 3.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} \)
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
There are two special constant Boolean polynomials.
zero polynomial
the constant Boolean polynomial
\(\boolzero(x_1,x_2,\dotsc,x_m) = 0 \)
unit polynomial
the constant Boolean polynomial
\(\boolone(x_1,x_2,\dotsc,x_m) = 1 \)
Example 3.1.6 .
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 that represent equivalent logical statements
Fact 3.1.7 . Recognizing equivalent Boolean polynomials.
Polynomials
\(p,q \) are equivalent if and only if they have the same truth table.
