2.2: Hypothesis an Theorems in Two-column Proofs
- Page ID
- 23886
\( \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 two-column proof must start by listing all of the hypotheses of the deduction, and each hypothesis is justified by writing the word hypothesis in the second column. (This is the only rule that is allowed above the dark horizontal line, and it is not allowed below the dark horizontal line.) We saw this rule in the above examples of two-column proofs. As a synonym for “hypothesis,” one sometimes says “given” or “assumption.”
Any deduction that is already known to be valid can be used as a justification if its hypotheses have been verified earlier in the proof. (And the lines where the hypotheses appear are written in parentheses after the name of the theorem.) For example, the theorems “\(\Rightarrow\)-elim” and “\(\lor\)-elim were used in our first examples of two-column proofs. These and several other very useful theorems were given in Exercise \(1.9.4\). You will be expected to be familiar with all of them.
| # | Assertion | Justification | English Version of Assertion |
|---|---|---|---|
| 1 | P \(\lor\) Q | hypothesis | Either the Pope is here, or the Queen is here. |
| 2 | Q \(\Rightarrow\) R | hypothesis | If the Queen is here, then the Registrar is also here. |
| 3 | \(\lnot\) P | hypothesis | The Pope is not here. |
| 4 | Q | \(\lor\)-elim (lines 1 and 3) | The Queen is here. |
| 5 | R | \(\Rightarrow\)-elim (lines 2 and 4) | The Registrar is here. |
Here is a proof of the deduction \(\lnot L \Rightarrow (J \lor L)\), \(\lnot L\), \(J\).
| # | Assertion | Justification |
|---|---|---|
| 1 | \(\lnot\)L\(\Rightarrow\)(J\(\lor\)L) | hypothesis |
| 2 | \(\lnot\)L | hypothesis |
| 3 | J\(\lor\)L | \(\Rightarrow\)-elim (lines 1 and 2) |
| 4 | J | \(\lor\)-elim (lines 3 and 2) |
Provide a justification (rule and line numbers) for each line of this proof.
| # | Assertion | Justification |
|---|---|---|
| 1 | W\(\Rightarrow\lnot\)B | |
| 2 | A & W | |
| 3 | \(\lnot\)B\(\Rightarrow\)(J & K) | |
| 4 | W | |
| 5 | \(\lnot\)B | |
| 6 | J & K | |
| 7 | K |
Provide a justification (rule and line numbers) for each line of this proof.
| # | Assertion | Justification |
|---|---|---|
| 1 | A\(\Rightarrow\)B | |
| 2 | \(\lnot\)A\(\Rightarrow\)B | |
| 3 | A \(\lor\lnot\)A | |
| 4 | B |
Write a two-column proof of each of the following deductions:
- \(P\lor Q\), \(Q\lor R\), \(\lnot Q\), \(P \& R\).
- \((E\lor F) \lor G\), \(\lnot F \& \lnot G\), \(E\).
Write a two-column proof of each of the following deductions. (Write the assertions in English.)
1. Hypothesis:
The Pope and the Queen are here.
Conclusion: The Queen is here.
2. Hypothesis:
The Pope is here.
The Registrar and the Queen are here.
Conclusion: The Queen and the Pope are here.
3. Hypothesis:
If the Pope is here, then the Queen is here.
If the Queen is here, then the Registrar is here.
The Pope is here.
Conclusion: The Registrar is here.
4. Grace is sick.
Frank is sick.
\(\therefore\) Either Grace and Frank are both sick, or Ellen is sick.
Many proofs use the Rules of Negation or the fact that any statement is logically equivalent to its contrapositive. Here is an example.
| # | Assertion | Justification | English Version of Assertion |
|---|---|---|---|
| 1 | \(\lnot\)P \(\Rightarrow\) (Q & R) | hypothesis | If the Pope is not here, then the Queen and the Registrar are here. |
| 2 | \(\lnot\)Q\(\lor\lnot\)R | hypothesis | Either the Queen is not here, or the Registrar is not here. |
| 3 | \(\lnot\)(Q & R)\(\Rightarrow\lnot\lnot\)P | contrapositive of line 1 | If it is not the case that both the Queen and the Registrar are here, then it is not the case that the Pope is not here. |
| 4 | (\(\lnot\)Q\(\lor\lnot\)R)\(\Rightarrow\)P | Rules of Negation applied to line 3 | If it is the case either that the Queen is not here, or that the Registrar is not here, then the Pope is here. |
| 5 | P | \(\Rightarrow\)-elim (lines 4 and 2) | The Pope is here. |
Provide a justification (rule and line numbers) for each line of these proofs.
1)
| # | Assertion | Justification |
|---|---|---|
| 1 | H\(\Rightarrow\)F | |
| 2 | H\(\Rightarrow\)G | |
| 3 | (F & G )\(\Rightarrow\)I | |
| 4 | \(\lnot\)I | |
| 5 | \(\lnot\)I\(\Rightarrow\lnot\) (F & G) | |
| 6 | \(\lnot\) (F & G) | |
| 7 | \(\lnot\)F \(\lor\lnot\)G | |
| 8 | \(\lnot\)F \(\Rightarrow\lnot\) H | |
| 9 | \(\lnot\)G \(\Rightarrow\lnot\) H | |
| 10 | \(\lnot\)H |
2)
| # | Assertion | Justification |
|---|---|---|
| 1 | (W\(\lor\)X)\(\Rightarrow\)(Y&Z) | |
| 2 | \(\lnot\)Y | |
| 3 | \(\lnot\)Y \(\lor\lnot\)Z | |
| 4 | \(\lnot\)(Y & Z)\(\Rightarrow\lnot\)(W\(\lor\)X) | |
| 5 | (\(\lnot\)Y\(\lor\lnot\)Z)\(\Rightarrow\)(\(\lnot\)W&\(\lnot\)X) | |
| 6 | \(\lnot\)W \(\&\lnot\)X | |
| 7 | \(\lnot\)X |
Give a two-column proof of each of these deductions.
- \(A \Rightarrow B\), \(\lnot B\), \(\therefore \lnot A\)
- \((L \lor M) \Rightarrow (N \& O)\), \(M\), \(\therefore O\)
- Hypothesis:
Either the Pope is not here, or the Queen is here.
The Pope is here.
Conclusion: Either the Queen is here, or else the Registrar and the Pope are both here.
4. Hypothesis:
If Sammy is not tired, then she does not need a nap.
Sammy needs a nap.
Conclusion: Sammy is tired.
You should also remember that \(\&\) and \(\lor\) are commutative, so, for example, \[F \Rightarrow((E \& D \& C \& B) \vee(A \& B)) \equiv F \Rightarrow((A \& B) \vee(B \& C \& D \& E)) .\]