Skip to main content ☰ Contents Index You! < 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{\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 2.1 Equivalence
equivalent statements
statements \(A,B\) such that \(A \lgcbicond B\) is a tautology
\(A \lgcequiv B\) statements \(A\) and \(B\) are equivalent
Test 2.1.1 . Equivalence of logical statements.
Statements \(A\) and \(B\) are logically equivalent if \(A\) and \(B\) always have the same output truth value whenever the same input truth values are substituted for the substatement variables in each. That is, \(A \lgcequiv B\) if \(A\) and \(B\) have the same truth table
Worked Example 2.1.2 . Testing logical equivalence.
Demonstrate that the following are equivalent statements.
\(A\text{:}\) If it’s nice outside, I will ride my bike.
\(B\text{:}\) It’s not nice outside, or I will ride my bike.
Solution .
Let \(p\) represent the substatement “it’s nice outside,” and let \(q\) represent the substatement “I will ride my bike.” Then the equivalence we want to establish is
\begin{equation*}
p \lgccond q \lgcequiv \lgcnot p \lgcor q\text{.}
\end{equation*}
We can analyze the truth tables of both statements in the same table.
\(p\) \(q\) \(\lgcnot p\) \(\lgcnot p \lgcor q\) \(p \lgccond q\)
\(\lgctrue\) \(\lgctrue\) \(\lgcfalse\) \(\lgctrue\) \(\lgctrue\)
\(\lgctrue\) \(\lgcfalse\) \(\lgcfalse\) \(\lgcfalse\) \(\lgcfalse\)
\(\lgcfalse\) \(\lgctrue\) \(\lgctrue\) \(\lgctrue\) \(\lgctrue\)
\(\lgcfalse\) \(\lgcfalse\) \(\lgctrue\) \(\lgctrue\) \(\lgctrue\)
We see that the two statements always have the same truth value in all rows of the truth table, so they are equivalent.
Worked Example 2.1.4 .
Demonstrate the equivalence \(p \lgcbicond q \lgcequiv \lgcnot p \lgcbicond \lgcnot q\text{.}\)
Solution .
Again we build a truth table, and see that the “output” columns for the two statements are identical.
\(p\) \(q\) \(\lgcnot p\) \(\lgcnot q\) \(p \lgcbicond q\) \(\lgcnot p \lgcbicond \lgcnot q\)
\(\lgctrue\) \(\lgctrue\) \(\lgcfalse\) \(\lgcfalse\) \(\lgctrue\) \(\lgctrue\)
\(\lgctrue\) \(\lgcfalse\) \(\lgcfalse\) \(\lgctrue\) \(\lgcfalse\) \(\lgcfalse\)
\(\lgcfalse\) \(\lgctrue\) \(\lgctrue\) \(\lgcfalse\) \(\lgcfalse\) \(\lgcfalse\)
\(\lgcfalse\) \(\lgcfalse\) \(\lgctrue\) \(\lgctrue\) \(\lgctrue\) \(\lgctrue\)
Proposition 2.1.5 .
Logical equivalence has the following properties.
It is reflexive . That is, \(A \lgcequiv A\) is always true.
It is symmetric . That is, whenever \(A \lgcequiv B\text{,}\) then also \(B \lgcequiv A\text{.}\)
It is transitive . That is, whenever \(A \lgcequiv B\) and \(B \lgcequiv C\text{,}\) then also \(A \lgcequiv C\text{.}\)
Every pair of tautologies is an equivalent pair of logical statements.
Every pair of contradictions is an equivalent pair of logical statements.
Check your understanding. Thinking in terms of truth tables, consider why each of the statements of
Proposition 2.1.5 holds.
