1.4: Tautologies and contradictions
- Page ID
- 83400
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)a logical statement that is always true for all possible truth values of its variable substatements
synonym for tautology
- \(p \rightarrow p\text{.}\)
- \(p \leftrightarrow p\text{.}\)
- Law of the Excluded Middle: \(p \lor \neg p \text{.}\)
Verification:
| \(p\) | \(\neg p\) | \(p \lor \neg p\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
The table verifies that the statement is a tautology as the last column consists only of \(T\) values.
- Law of Contradiction: \(\neg (p \land \neg p)\text{.}\)
Verification:
| \(p\) | \(\neg p\) | \(p \land \neg p\) | \(\neg (p \land \neg p)\) |
| \(T\) | \(F\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(T\) |
The table verifies that the statement is a tautology as the last column consists only of \(T\) values.
Is \(p \lor p\) a tautology? No, since it is false when \(p\) is false.
a statement that must always be false, regardless of the truth values of its variable substatements
synonym for contradiction
Negation of a tautology is always a contradiction (and negation of a contradiction is always a tautology).
Statement \((p \lor \neg p) \rightarrow (q \land \neg q)\) is a contradiction:
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p \lor \neg p\) | \(q \land \neg q\) | \((p \lor \neg p) \rightarrow (q \land \neg q)\) |
| \(T\) | \(T\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(F\) | \(F\) |
The table verifies that the statement is a contradiction as the last column consists only of \(F\) values.
Implication \(A\rightarrow B\) can only be a contradiction if \(A\) is a tautology and \(B\) is a contradiction.
Suppose \(A\) is a logical statement involving substatement variables \(p_1, p_2, \dotsc, p_m\text{.}\) If \(A\) is logically true or logically false, then so is every statement obtained from \(A\) by replacing each statement variable \(p_i\) by some logical statement \(B_i\text{,}\) for every possible collection of logical statements \(B_1, B_2, \dotsc, B_m\text{.}\)
- We know \(p \lor \neg p\) is a tautology, therefore so is
\begin{equation*} (q \rightarrow (r \land \neg s)) \lor \neg (q \rightarrow (r \land \neg s)) \end{equation*}
using substitution \(p = (q \rightarrow (r \land \neg s))\text{.}\)
- We know \((p \lor \neg p) \rightarrow (q \land \neg q)\) is a contradiction, therefore so are
\begin{gather*} (p \lor \neg p) \rightarrow (p \land \neg p) \qquad \text{(by } p = p \text{, } q = p \text{),}\\ ((r \lor s) \lor \neg (r \lor s)) \rightarrow (q \land \neg q) \qquad \text{(by } p = r \lor s \text{, } q = q \text{),}\\ (r \land (s \leftrightarrow t)) \lor \neg (r \land (s \leftrightarrow t)) \rightarrow (t \land \neg t) \qquad \text{(by } p = r \land (s \leftrightarrow t) \text{, } q = t \text{).} \end{gather*}
In mathematics, we often wish to prove that a condition \(A \rightarrow B\) is actually a tautology. (See Chapter 6.)
if the conditional \(A \rightarrow B\) is a tautology, we say that \(A\) logically implies \(B\)
notation for logical implication
- If \(A = p\) and \(B = p \lor q\text{,}\) then \(A \Rightarrow B\text{.}\)
- If \(A = p \land q\) and \(B = p\text{,}\) then \(A \Rightarrow B\text{.}\)
Remark \(\PageIndex{1}\)
As we will see in Chapter 6, verifying logical implications in mathematical contexts is one of the main tasks of mathematical proof. And to verify a logical implication \(A \Rightarrow B\text{,}\) we want to focus on the idea of conditional as expressing “If \(A\) is true then \(B\) is true,” and we really don't want to concern ourselves with what happens in the case that \(A\) is false. Here is where our “default” values in the rows of the truth table for the conditional \(A \rightarrow B\) where \(A\) is false help out — as the conditional \(A \rightarrow B\) is automatically true when \(A\) is false, regardless of the truth value of \(B\text{,}\) we really only need to consider what happens when \(A\) is true to verify \(A \Rightarrow B\text{.}\)