Skip to main content
Contents Dark Mode Prev Up Next \(\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Inn}{Inn}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Perm}{Perm}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\Orb}{Orb}
\DeclareMathOperator{\Rot}{Rot}
\DeclareMathOperator{\re}{Re}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\img}{image}
\DeclareMathOperator{\conj}{conj}
\DeclareMathOperator{\Id}{Id}
\def\expi{E}
\def\wrap{W}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Quat}{\mathbb{H}}
\newcommand{\extC}{\hat{\C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\extR}{\hat{\R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\extF}{\hat{\F}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Proj}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\B}{\mathbb{B}}
\newcommand{\M}{{\rm MOB}}
\newcommand{\E}{{\rm EUC}}
\renewcommand{\H}{{\rm HYP}}
\newcommand{\HU}{\rm HYP_{\U}}
\renewcommand{\S}{{\rm ELL}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\closedD}{\hat{\D}}
\newcommand{\U}{\mathbb{U}}
\newcommand{\spacer}{\rule[0cm]{0cm}{0cm}}
\newcommand{\MOD}{\mathbin{\text{MOD}}}
\newcommand{\twotwo}[4]{\left[ \begin{array}{cc} #1 \amp #2 \\
#3 \amp #4 \end{array} \right]}
\let\oldsection\section
\renewcommand{\section}{\clearpage\oldsection}
\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 1.1 Boolean algebra
The truth tables for compound statements that are presented in most textbooks are just input-output tables for functions, where every entry is a truth value. In these tables, the actual statements play no role; only their truth values matter. Boolean algebra provides a language for working directly with such functions in a way that bypasses the need for cumbersome input-output tables.
The set
\(\B=\{0,1\}\text{,}\) together with the operations of addition and multiplication mod 2, is called the
Boolean domain . Multiplication mod 2 is the same as ordinary multiplication of integers. Addition mod 2 is defined by
\(0+0=0\text{,}\) \(1+0=0+1=1\text{,}\) and
\(1+1=0\text{.}\)
Checkpoint 1.1.1 .
Show that the following identities hold for \(x,y,z\in \B\text{.}\)
\(x+y=y+x\) (the commutative law of addition)
\(xy=yx\) (the commutative law of multiplication)
\(x+(y+z)=(x+y)+z\) (the associative law of addition)
\(x(yz)=(xy)z\) (the associative law of multiplication)
\(x+0 = 0+x = x\) (additive identity)
\(x1 = 1x = x\) (multiplicative identity)
\(x(y+z) = xy+xz\) (the distributive law)
\(\displaystyle x^2=x\)
\(\displaystyle (x+y)^2=x+y\)
\(\displaystyle x(x+1)=0\)
Let \(\mathcal{S}\) denote the set of all statements, and let \(v\colon \mathcal{S} \to \B\) given by
\begin{equation*}
v(p) = \begin{cases}
1 \amp \text{ if } p \text{ is true}\\
0 \amp \text{ if } p \text{ is false}.
\end{cases}
\end{equation*}
In these notes we will refer to \(v\) as the truth value function.
Checkpoint 1.1.2 .
Let \(p,q\in \mathcal{S}\text{.}\)
Show that \(v(\sim p) = v(p)+1\text{.}\)
Show that \(v(p\wedge q) = v(p)v(q)\text{.}\)
Show that \(v(p\vee q) = v(p)+v(q)+v(p)v(q)\text{.}\)
The exercise above justifies the following associations for \(p,q\in \mathcal{S}\) and \(x=v(p), y=v(q)\text{.}\)
\begin{equation*}
\begin{array}{c|c}
\text{logical statement } r
\amp \text{Boolean expression } v(r)
\\ \hline
\sim p \amp x+1\\
p\wedge q \amp xy\\
p\vee q \amp x+y+xy
\end{array}
\end{equation*}
Checkpoint 1.1.3 .
Let
\(\oplus\) denote the logical connective whose corresponding Boolean function is
\(+\text{,}\) that is, we have
\(v(p\oplus q)=v(p)+v(q)\text{.}\) Use a truth table to verify that a reasonable verbalization of “
\(p \oplus q\) ” is “
\(p\) or
\(q\text{,}\) but not both”. The connective
\(\oplus\) is called
exclusive or .
Checkpoint 1.1.4 .
Find the missing Boolean functions for the logical connectives in the table below.
\begin{equation*}
\begin{array}{c|c}
\text{logical statement } r
\amp \text{Boolean expression } v(r) \\ \hline
p \Rightarrow q \amp \\
p \Leftarrow q \amp \\
p \Leftrightarrow q \amp \\
\end{array}
\end{equation*}
Checkpoint 1.1.5 .
Let \(p,q,r\) be statements, and let \(x,y,z\) be \(v(p),v(q),v(r)\text{,}\) respectively.
Find the Boolean expression that corresponds to the logical expression
\begin{equation*}
[p\wedge(q\oplus r)] \oplus \left([r\Leftarrow p] \wedge
\sim[q\Leftrightarrow r]\right).
\end{equation*}
Find the truth table for the logical expression whose corresponding Boolean expression is \(xyz+xy+y+z+1\text{.}\)
Checkpoint 1.1.6 .
Use Boolean expressions instead of truth tables for all of the exercises in Ch 1 of
[1] that suggest that you use truth tables.
