1.10: A Few Ideas from Formal Logic
- Page ID
- 151660
\( \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}\)Formal logic deals with relationships among propositions, where a proposition is any statement of (alleged) fact. Any proposition can be expressed as an ordinary English sentence, although it may be more convenient to use mathematical symbols or some other notation. The following are all propositions:
- Albert Einstein is deceased.
- Tulsa is in Oklahoma.
- Two plus two equals four.
- \(2+2=4\)
- \(\int{x^2dx=x+1}\)
A proposition need not be true. The last of these examples is a false proposition. We represent an arbitrary proposition by any convenient symbol, usually a letter of the alphabet. Thus, we could stipulate that “\(p\)” represents any of the propositions above. Once we have associated a symbol with a particular proposition, the symbol itself is taken to represent an assertion that the proposition is true. It is an axiom of ordinary logic that any proposition must be either true or false. If we associate the symbol “\(p\)” with a particular proposition, we write “\(\sim p\)” to represent the statement: “The proposition represented by the symbol ‘\(p\)’ is false.” \(\sim p\) is called the negation of p. We can use the negation of \(p\), \(\sim p\), to state the axiom that a proposition must be either true or false. To do so, we write: Either \(p\) or \(\sim p\) is true. We can write this as the proposition “\(p\) or \(\sim p\)”. The negation of the negation of \(p\) is an assertion that \(p\) is true; that is, \(\sim \ \sim \ p\ =\ p\).
Logic is concerned with relationships among propositions. One important relationship is that of implication. If a proposition, \(q\), follows logically from another proposition, \(p\), we say that \(q\) is implied by \(p\). Equivalently, we say that proposition \(p\) implies proposition \(q\). The double-shafted arrow, \(\mathrm{\Rightarrow }\), is used to symbolize this relationship. We write “\(p\Rightarrow q\)” to mean, “That proposition \(p\) is true implies that proposition \(q\) is true.” We usually read this more tersely, saying, “\(p\) implies \(q\).” Of course, “\(p\Rightarrow q\)” is itself a proposition; it asserts the truth of a particular logical relationship between propositions \(p\) and \(q\).
For example, let \(p\) be the proposition, “Figure A is a square.” Let \(q\) be the proposition, “Figure A is a rectangle.” Then, writing out the proposition, \(p\Rightarrow q\), we have: Figure A is a square implies figure A is a rectangle. This is, of course, a valid implication; for this example, the proposition \(p\Rightarrow q\) is true. For reasons that will become clear shortly, \(p\Rightarrow q\) is called the conditional of \(p\) and \(q\). Proposition \(p\) is often called a sufficient condition, while proposition \(q\) is called a necessary condition. That is, the truth of \(p\) is sufficient to establish the truth of \(q\).
\[\text{sufficient condition}\, \mathrm{\Rightarrow} \, \text{necessary condition} \nonumber \]
Now, if proposition \(p\Rightarrow q\) is true, and proposition \(q\) is also true, can we infer that proposition \(p\) is true? We most certainly cannot! In the example we just considered, the fact that figure A is a rectangle does not prove that figure A is a square. We call \(q\Rightarrow p\) the converse of \(p\Rightarrow q\). The conditional of \(p\) and \(q\) can be true while the converse is false. Of course, it can happen that both \(p\Rightarrow q\) and \(q\Rightarrow p\) are true. We often write “\(p\Leftrightarrow q\)” to express this relationship of mutual implication. We say that, “\(p\) implies \(q\) and conversely.”
What if \(p\Rightarrow q\), and \(q\) is false? That is, \(\sim q\) is true. In this case, \(p\) must be false! If \(\sim q\) is true, it must also be that \(\sim p\) is true. Using our notation, we can express this fact as
\[(p\Rightarrow q\, \text{and} \sim q) \Rightarrow \sim p \nonumber \]
Equivalently, we can write
\[(p\Rightarrow q) \mathrm{\Leftrightarrow } (\sim q\Rightarrow \sim p) \nonumber \]
That is, \(p\Rightarrow q\) and \(\sim q\Rightarrow \sim p\) are equivalent propositions; if one is true, the other must be true. \(\sim q\Rightarrow \sim p\) is called the contrapositive of \(p\Rightarrow q\). The equivalence of the conditional and its contrapositive is a theorem that can be proved rigorously in an axiomatic formulation of logic. In our later reasoning about thermodynamic principles, we use the equivalence of the conditional and the contrapositive of \(p\) and \(q\).
The equivalence of the conditional, \(p\Rightarrow q\), and the contrapositive, \(\sim q\Rightarrow \sim p\), is the reason that \(q\) is called a necessary condition. If \(p\Rightarrow q\), it is necessary that \(q\) be true for \(p\) to be true. (If figure A is to be a square, it must be a rectangle.)
It is also intimately related to proof by contradiction. Suppose that we know \(p\) to be true. If, by assuming that \(q\) is false (\(\sim q\) is true), we can validly demonstrate that \(p\) must also be false \((\sim q\mathrm{\Rightarrow }\sim p\), so that \(\sim p\) is true), we have the contradiction that \(p\) is both true and false (\(p\) and \(\sim p\)). Since \(p\) cannot be both true and false, it must be false that q is false (\(\sim \sim q=q\)). Otherwise stated, the equivalence of the conditional and the contrapositive leads not only to (\(p\) and \(\sim p\)) but also to (\(q\) and \(\sim q\)).
\[\sim q \mathrm{\Rightarrow } \sim p \nonumber \]
implies
\[p \mathrm{\Rightarrow } q. \nonumber \]
In summary, since we know p to be true, our assumption that \(q\) is false, together with the valid implication \(\sim q\mathrm{\Rightarrow }\sim p\), leads to the conclusion that \(q\) is true, which contradicts our original assumption, so that the assumption is false, and \(q\) is true.