$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

1.9: Some Valid Deductions

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Recall that a deduction is valid if its conclusion is true in all situations where all of its hypotheses are true. This means, for each and every possible assignment of true/false to the variables, if all of the hypotheses true, then the conclusion is also true.

Example $$\PageIndex{1}$$

Explain how you know that the following deduction is valid. $A \lor B, \quad \lnot A, \quad \therefore \ B .$

Solution

Assume we are in a situation in which both hypotheses of the deduction are true. Then, from the first hypothesis, we know that either $$A$$ is true or $$B$$ is true. However, from the second hypothesis, we know that $$A$$ is not true. Therefore, it must be $$B$$ that is true. Hence, the conclusion of the deduction is true.

Exercise $$\PageIndex{2}$$

1. Assume $$({A}\&{B})\Rightarrow{C}$$ is neither a tautology nor a contradiction. What can you say about the deduction “$$A$$, $$B$$, $$\therefore C$$”?
2. Assume $$A$$ is a contradiction. What can you say about the deduction “$$A$$, $$B$$, $$\therefore C$$”?
3. Assume $$C$$ is a tautology. What can you say about the deduction “$$A$$, $$B$$, $$\therefore C$$”?

Other Terminology $$1.9.3$$.

Any valid deduction can be called a theorem.

Exercise $$1.9.4$$. (Rules of Propositional Logic).

It is not difficult to see that each of the following is a valid deduction. For each of them, either give a short explanation of how you know that it is valid, or verify the dedcution by evaluating the conclusion for all possible values of the variables that make the hypotheses true.

 1 Repeat $$\mathit{A},\enspace \therefore \mathit{A}$$ 2 &-Introduction $$\mathit{A, B}, \enspace \therefore \mathit{A}\& \mathit{B}$$ 3 &-Elimination $$\mathit{A} \& \mathit{B}, \enspace \therefore\mathit{A} \quad \mathit{A} \& \mathit{B}, \enspace \therefore\mathit{B}$$ 4 $$\lor$$-Introduction $$\mathit{A}, \enspace \therefore \mathit{A}\lor\mathit{B} \quad \mathit{B}, \enspace \therefore \mathit{A}\lor\mathit{B}$$ 5 $$\lor$$-Elimination $$\mathit{A}\lor\mathit{B},\lnot\mathit{A}, \enspace\therefore\mathit{B} \quad \mathit{A}\lor\mathit{B},\lnot\mathit{B}, \enspace\therefore\mathit{A}$$ 6 $$\Rightarrow$$-Elimination $$\mathit{A}\Rightarrow\mathit{B}, \enspace\mathit{A}, \enspace\therefore\mathit{B}$$ 7 $$\Leftrightarrow$$-Introduction $$\mathit{A}\Rightarrow\mathit{B}, \enspace\mathit{B}\Rightarrow\mathit{A}, \enspace\therefore\mathit{A}\Leftrightarrow\mathit{B}$$ 8 $$\Leftrightarrow$$-Elimination $$\mathit{A}\Leftrightarrow\mathit{B}, \enspace\therefore\mathit{A}\Rightarrow\mathit{B} \quad\mathit{A}\Leftrightarrow\mathit{B}, \enspace\therefore\mathit{B}\Rightarrow\mathit{A}$$ 9 Proof by Cases $$\mathit{A}\lor\mathit{B}, \enspace\mathit{A}\Rightarrow\mathit{C}, \enspace\mathit{B}\Rightarrow\mathit{C}, \enspace\therefore\mathit{C}$$

All of the theorems in Exercise $$1.9.4$$. will be used on a regular basis in the following chapters (and in your later mathematics courses).

Other Terminology.

Most logicians call the $$\Rightarrow$$-elimination rule by its Latin name, which is Modus Ponens. (According to Wikipedia, this is short for modus ponendo ponens, which means “the way that affirms by affirming.”)

Remark $$1.9.5$$.

A theorem remains valid if we change the names of the variables. For example, $$P \lor Q$$, $$\lnot P$$, $$Q$$ is the same as $$\lor$$-elimination, but we have replaced $$A$$ with $$P$$ and $$B$$ with $$Q$$. (In the language of high-school algebra, we have plugged in $$P$$ for $$A$$, and plugged in $$Q$$ for $$B$$.) Indeed, it should be clear that any theorem remains valid even if we substitute more complicated expressions into the variables.

Example $$1.9.6$$

The theorem $(X \lor Y) \Rightarrow (Y \lor Z), \ X \lor Y, \ \therefore Y \lor Z$
is obtained from “$$\Rightarrow$$-elimination,” by letting $$A = (X \lor Y)$$ and $$B = (Y \lor Z)$$.

Exercise $$1.9.7$$

Each of the following is a valid theorem that is obtained from one of the basic theorems in Exercise $$1.9.4$$, by substituting some expressions into the variables. Identify the theorem it is obtained from, and the expressions that were substituted into each variable.

1. $$(A \lor B) \& (Y \Rightarrow Z), \ \therefore Y \Rightarrow Z$$
2. $$(A \lor B) \& (Y \Rightarrow Z), \ \therefore (A \lor B) \& (Y \Rightarrow Z)$$
3. $$A \lor B, \ \therefore (A \lor B) \lor (Y \Rightarrow Z)$$
4. $$(A \lor B), (Y \Rightarrow Z), \ \therefore (A \lor B) \& (Y \Rightarrow Z)$$

Exercise $$1.9.8$$.

Each of the following is the English-language version of a valid theorem that is obtained from one of the basic theorems of Table 1.9.1, by substituting some expressions into the variables. Identify the theorem it is obtained from.

1. Susie will stop at either the grocery store or the drug store. If she stops at the grocery store, she will buy milk. If she stops at the drug store, she will buy milk. Therefore, I am sure that Susie will buy milk.
2. My opponent in this election is a liar! My opponent in this election is a cheat! Therefore, I say to you that my opponent is a liar and a cheat!
3. John went to the store. Therefore, as I already told you, John went to the store.
4. If I had $50, I would be able to buy a new coat. Hey, look! I found a$50 bill on the sidewalk! So I will be able to buy a new coat.