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

$$P\wedge Q\models P.$$

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:

1. $Q\wedge P \models Q$
2. $(P\wedge (Q\vee R))\wedge Q \models (P\wedge (Q\vee R))$
3. $P\wedge P \models P$
4. $(P\vee \neg P)\wedge Q \models P \vee \neg P$
5. $(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

$$X\wedge Y\Rightarrow X$$

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:

1. $P\wedge Q$
2. $(P\wedge Q) \wedge R$
3. $P\wedge P$
4. $(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:

1. 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".
2. 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".
3. 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".
4. 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:

1. Infer $Q$ from $P\wedge Q$, denoted $P\wedge Q\Rightarrow Q$.
2. 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

$$X_1, X_2, \ldots, X_n\models Y$$

as valid or invalid:

1. 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.

2. 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:

1. $P, P\rightarrow Q\models Q$
2. $P, P\rightarrow P\models P$
3. $P\rightarrow Q, (P\rightarrow Q) \rightarrow R\models R$
4. $(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):

$$Y, X\rightarrow Y \Rightarrow X$$

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:

$$X_1\wedge X_2\wedge\cdots\wedge X_n$$

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$.

Observation

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.

Observation

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).

Monotonicity of Valid Inferences

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

Challenge

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

Deduction Theorem

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

Practice Questions

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

   $X\wedge \neg Y$ is a contradiction.

   $X\rightarrow Y$ is a tautology.

   There is a truth value assignment that makes both $X$ and $Y$ are true.

   ​

   For example, when $X$ is $P\wedge\neg P$ and $Y$ is $Q$, we have $P\wedge\neg P\models Q$ but there is no truth value assignment that makes both $X$ and $Y$ true.

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

   For any formula $Z$, we have that $X\wedge Z\models Y$.

   For any formula $Z$, we have that $X\models Y\wedge Z$.

   ​

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

   For any formula $Z$, we have that $X\vee Z\models Z$.

   For any formula $Z$, we have that $X\models Y\vee Z$.

   ​

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

   $P\wedge Q, P\rightarrow R\models R$, since $R$ can be inferred by two applications of Modus Ponens.

   $P\wedge Q, P\rightarrow R\models R$, since $R$ can be inferred by one application of right-$\wedge$ elimination and then one application of Modus Ponens

   $P\wedge Q, P\rightarrow R\not\models R$.

   ​

5. 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$

   $P$

   $Q$

   $R$

   ​

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

   $X, P, Q\models R$

   $P\rightarrow (Q\rightarrow R)$

   $(P\rightarrow Q)\rightarrow R$

   ​

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

   $\neg X \vee Y, X \models Y$ since this the Disjunctive Syllogism inference rule.

   $\neg X \vee Y, X \models Y$, but this is not the same as the Disjunctive Syllogism inference rule.

   $\neg X \vee Y, X \not\models Y$.

   ​