# Valid and Invalid Inferences

An important feature of valid arguments is that *any* instance of the form of a valid argument will also be valid. For example, consider the valid argument

The form of this argument is $X\wedge Y\Rightarrow X$. Its only premise is a conjunction and the conclusion is the left conjunct of the premise. Every instance of this abstract argument is valid. For example, the following instances are all valid:

- $Q\wedge P \models Q$
- $(P\wedge (Q\vee R))\wedge Q \models (P\wedge (Q\vee R))$
- $P\wedge P \models P$
- $(P\vee \neg P)\wedge Q \models P \vee \neg P$
- $(P\wedge \neg P)\wedge P \models P\wedge \neg P$

Thus, when an argument is shown to be valid, then any argument with the same form is valid. With this in mind, here is another way to think about valid arguments in propositional logic. The form of a valid argument is a *rule*, called an **inference rule**, that specifies how to transform a sequence of statements into a statement. For instance, the abstract argument

is a rule, called **right-$\wedge$ elimination**, that transforms any conjunction into its left conjunct. To apply an inference rule to a list of formulas, you need to make sure that the list of formulas has the appropriate form. For example, **right-$\wedge$ elimination** can be applied to any of the following formulas since the main connective of each formula is a conjunction:

- $P\wedge Q$
- $(P\wedge Q) \wedge R$
- $P\wedge P$
- $(P\rightarrow \neg Q) \wedge (S \vee \neg R)$

Applying **right-$\wedge$ elimination** to the above formulas transforms each of these conjunctions into their left conjuncts:

- The
**right-$\wedge$ elimination**transforms $P\wedge Q$ into $P$. In this case, we say "$P$ is inferred from $P\wedge Q$ using the**right-$\wedge$ elimination**inference rule". - The
**right-$\wedge$ elimination**transforms $(P\wedge Q) \wedge R$ into $P\wedge Q$. In this case, we say "$P\wedge Q$ is inferred from $(P\wedge Q) \wedge R$ using the**right-$\wedge$ elimination**inference rule". - The
**right-$\wedge$ elimination**transforms $P\wedge P$ into $P$. In this case, we say "$P$ is inferred from $(P\wedge P)$ using the**right-$\wedge$ elimination**inference rule". - The
**right-$\wedge$ elimination**transforms $(P\rightarrow \neg Q) \wedge (S \vee \neg R)$ into $(P\rightarrow \neg Q)$. In this case, we say "$(P\rightarrow \neg Q)$ is inferred from $(P\rightarrow \neg Q) \wedge (S \vee \neg R)$ using the**right-$\wedge$ elimination**inference rule".

Note that the following are **not** instances of **right-$\wedge$ elimination**:

- Infer $Q$ from $P\wedge Q$, denoted $P\wedge Q\Rightarrow Q$.
- Infer $P$ from $(P\wedge Q) \wedge R$, denoted $(P\wedge Q) \wedge R\Rightarrow P$.

The first is an instance of a related, but different inference rule (**left-$\wedge$ elimination**): $X\wedge Y\Rightarrow Y$. For item 2, note that right-$\wedge$ elimination must be applied to the *main connective* of the premise. Since, the second occurrence of "$\wedge$" is the main connective in $(P\wedge Q) \wedge R$, the correct application of right-$\wedge$ elimination gives $(P\wedge Q)$ follows from $(P\wedge Q) \wedge R$. Then, using right-$\wedge$ elimination a second time we have that $P$ follows from $P\wedge Q$. So, $P$ follows from $(P\wedge Q)\wedge R$ using *two applications* of the right-$\wedge$ elimination inference rule.

We use the notation introduced in the chapter on validity to classify the inference rule

as valid or invalid:

The above inference rule is

**valid**, denoted $X_1, X_2, \ldots, X_n\models Y$, when there is no instance of the argument and truth value assignment that makes all the (instances of the) premises true and the (instance of the) conclusion false.The above inference rule is

**invalid**, denoted $X_1, X_2, \ldots, X_n\not\models Y$, when there is an instance of the argument and truth value assignment that makes all the (instances of the) premises true and the (instance of the) conclusion false.

Examples of some important valid inference rules include:

Name | Valid inference rule |
---|---|

Modus Ponens | $X, X\rightarrow Y\models Y$ |

Modus Tollens | $X\rightarrow Y, \neg Y\models \neg X$ |

Disjunctive Syllogism | $X\vee Y, \neg X\models Y$ |

Hypothetical Syllogism (Transitivity) | $X\rightarrow Y, Y\rightarrow Z\models X\rightarrow Z$ |

The inference rules in the above table each transform a list of formulas. For example, the inference rule Modus Ponens can be applied to any list of formulas in which the first element is any formula and the second element is a conditional where the antecedent is the first formula in the list. The output of Modus Ponens is the consequent of the second formula in the input to the inference rule. For example, the following valid arguments are all instances of Modus Ponens:

- $P, P\rightarrow Q\models Q$
- $P, P\rightarrow P\models P$
- $P\rightarrow Q, (P\rightarrow Q) \rightarrow R\models R$
- $(P\wedge\neg Q), (P\wedge\neg Q) \rightarrow (\neg Q\rightarrow S)\models \neg Q \rightarrow S$

Note that, the following is **not** an instance of Modus Ponens: $Q, P\rightarrow Q\Rightarrow P$. Modus Ponens does not apply since the first formula in the input to the rule is the consequent of the second formula rather than the antecedent. This invalid argument (i.e., $Q, P\rightarrow Q\not\models P$) is an instance of the following invalid inference rule (called **Affirming the Consequent**):

To explain why $Y, X\rightarrow Y \not\models X$, we note that $Q,P\rightarrow Q\not\models P$ since the truth value function that makes $P$ false and $Q$ true, makes both $Q$ and $P\rightarrow Q$ true, but makes $P$ false. Other examples of invalid inference rules include:

Name | Invalid inference rule |
---|---|

Denying the Antecedent | $\neg X, X\rightarrow Y\not\models\neg Y$ |

Affirming the Consequent | $Y, X\rightarrow Y\not\models X$ |

Affirming a Disjunct | $X\vee Y, X\not\models\neg Y$ |

We conclude with some general observations about valid inference rules.

It is sometimes convenient to replace a list of premises with a single formula that is a conjunction of all the premises. Note that a truth value assignment makes each of $X_1, X_2, \ldots, X_n$ true if, and only if, the truth value assignment makes the following formula true:

This means that:

- If $X_1, X_2,\ldots, X_n\models Y$, then $X_1\wedge X_2\wedge \cdots\wedge X_n\models Y$.
- If $X_1, X_2,\ldots, X_n\not\models Y$, then $X_1\wedge X_2\wedge \cdots\wedge X_n\not\models Y$.

For all formulas $X$ and $Y$, if $X$ and $Y$ are tautologically equivalent, then for all formulas $Z$,

$X\models Z$ if and only if $Y\models Z$.

$Z\models X$ if and only if $Z\models Y$.

Since, for all formulas $X$ and $Y$, $X\wedge Y$ is tautologically equivalent to $Y\wedge X$, using Observation 1 and Observation 2, we see that the order of the premises of an inference rule does not matter. For example, this means that: $P\rightarrow Q, P\models Q$ is an instance of Modus Ponens.

For all formulas $X$ and $Y$, $X\models Y$ means that $X\wedge\neg Y$ is a contradiction, and $X\not\models Y$ means that there is a truth value assignment that makes $X\wedge\neg Y$ true (so, the set of formulas consisting of $X$ and $\neg Y$ is satisfiable).

For all formulas $X$, $Y$ and $Z$, if $X\models Y$, then $X, Z\models Y$.

Is monotonicity a good property? Can you think of an English argument where monotonicity seems to fail?

For all formulas $X$ and $Y$, $X\models Y$ if, and only if, $X\rightarrow Y$ is a tautology.

## Practice Questions

Suppose that $X$ and $Y$ are formulas and that $X\models Y$. Which of the following is not true?

Suppose that $X$ and $Y$ are formulas and that $X\models Y$. Which of the following is true?

Suppose that $X$ and $Y$ are formulas and that $X\models Y$. Which of the following is true?

Consider the argument $P\wedge Q, P\rightarrow R\Rightarrow R$. Which of the following is true?

Which of the following formulas can be substituted for $X$ to ensure that the following argument is valid?

$P\rightarrow Q, \neg Q, P\vee R\models X$

Which of the following formulas can be substituted for $X$ to ensure that the following argument is valid?

$X, P, Q\models R$

Consider the inference rule: $\neg X \vee Y, X \Rightarrow Y$. Which of the following is true?