Skip to main content

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∧Q⊨P.P\wedge Q\models P.

The form of this argument is X∧Yβ‡’XX\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∧P⊨QQ\wedge P \models Q
  2. (P∧(Q∨R))∧Q⊨(P∧(Q∨R))(P\wedge (Q\vee R))\wedge Q \models (P\wedge (Q\vee R))
  3. P∧P⊨PP\wedge P \models P
  4. (P∨¬P)∧Q⊨P∨¬P(P\vee \neg P)\wedge Q \models P \vee \neg P
  5. (P∧¬P)∧P⊨P∧¬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

X∧Yβ‡’XX\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∧QP\wedge Q
  2. (P∧Q)∧R(P\wedge Q) \wedge R
  3. P∧PP\wedge P
  4. (Pβ†’Β¬Q)∧(S∨¬R)(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∧QP\wedge Q into PP. In this case, we say "PP is inferred from P∧QP\wedge Q using the right-∧\wedge elimination inference rule".
  2. The right-∧\wedge elimination transforms (P∧Q)∧R(P\wedge Q) \wedge R into P∧QP\wedge Q. In this case, we say "P∧QP\wedge Q is inferred from (P∧Q)∧R(P\wedge Q) \wedge R using the right-∧\wedge elimination inference rule".
  3. The right-∧\wedge elimination transforms P∧PP\wedge P into PP. In this case, we say "PP is inferred from (P∧P)(P\wedge P) using the right-∧\wedge elimination inference rule".
  4. The right-∧\wedge elimination transforms (Pβ†’Β¬Q)∧(S∨¬R)(P\rightarrow \neg Q) \wedge (S \vee \neg R) into (Pβ†’Β¬Q)(P\rightarrow \neg Q). In this case, we say "(Pβ†’Β¬Q)(P\rightarrow \neg Q) is inferred from (Pβ†’Β¬Q)∧(S∨¬R)(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 QQ from P∧QP\wedge Q, denoted P∧Qβ‡’QP\wedge Q\Rightarrow Q.
  2. Infer PP from (P∧Q)∧R(P\wedge Q) \wedge R, denoted (P∧Q)∧Rβ‡’P(P\wedge Q) \wedge R\Rightarrow P.

The first is an instance of a related, but different inference rule (left-∧\wedge elimination): X∧Yβ‡’YX\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∧Q)∧R(P\wedge Q) \wedge R, the correct application of right-∧\wedge elimination gives (P∧Q)(P\wedge Q) follows from (P∧Q)∧R(P\wedge Q) \wedge R. Then, using right-∧\wedge elimination a second time we have that PP follows from P∧QP\wedge Q. So, PP follows from (P∧Q)∧R(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

X1,X2,…,Xn⊨YX_1, X_2, \ldots, X_n\models Y

as valid or invalid:

  1. The above inference rule is valid, denoted X1,X2,…,Xn⊨YX_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 X1,X2,…,Xn⊭YX_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:

NameValid inference rule
Modus PonensX,Xβ†’Y⊨YX, X\rightarrow Y\models Y
Modus TollensXβ†’Y,Β¬Y⊨¬XX\rightarrow Y, \neg Y\models \neg X
Disjunctive SyllogismX∨Y,¬X⊨YX\vee Y, \neg X\models Y
Hypothetical Syllogism (Transitivity)Xβ†’Y,Yβ†’Z⊨Xβ†’ZX\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β†’Q⊨QP, P\rightarrow Q\models Q
  2. P,Pβ†’P⊨PP, P\rightarrow P\models P
  3. Pβ†’Q,(Pβ†’Q)β†’R⊨RP\rightarrow Q, (P\rightarrow Q) \rightarrow R\models R
  4. (P∧¬Q),(P∧¬Q)β†’(Β¬Qβ†’S)⊨¬Qβ†’S(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β†’Qβ‡’PQ, 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β†’Q⊭PQ, P\rightarrow Q\not\models P) is an instance of the following invalid inference rule (called Affirming the Consequent):

Y,X→Y⇒XY, X\rightarrow Y \Rightarrow X

To explain why Y,Xβ†’Y⊭XY, X\rightarrow Y \not\models X, we note that Q,Pβ†’Q⊭PQ,P\rightarrow Q\not\models P since the truth value function that makes PP false and QQ true, makes both QQ and Pβ†’QP\rightarrow Q true, but makes PP false. Other examples of invalid inference rules include:

NameInvalid inference rule
Denying the AntecedentΒ¬X,Xβ†’Y⊭¬Y\neg X, X\rightarrow Y\not\models\neg Y
Affirming the ConsequentY,Xβ†’Y⊭XY, X\rightarrow Y\not\models X
Affirming a DisjunctX∨Y,X⊭¬YX\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 X1,X2,…,XnX_1, X_2, \ldots, X_n true if, and only if, the truth value assignment makes the following formula true:

X1∧X2βˆ§β‹―βˆ§XnX_1\wedge X_2\wedge\cdots\wedge X_n

This means that:

  • If X1,X2,…,Xn⊨YX_1, X_2,\ldots, X_n\models Y, then X1∧X2βˆ§β‹―βˆ§Xn⊨YX_1\wedge X_2\wedge \cdots\wedge X_n\models Y.
  • If X1,X2,…,Xn⊭YX_1, X_2,\ldots, X_n\not\models Y, then X1∧X2βˆ§β‹―βˆ§Xn⊭YX_1\wedge X_2\wedge \cdots\wedge X_n\not\models Y.
Observation

For all formulas XX and YY, if XX and YY are tautologically equivalent, then for all formulas ZZ,

X⊨ZX\models Z if and only if Y⊨ZY\models Z.

Z⊨XZ\models X if and only if Z⊨YZ\models Y.

Since, for all formulas XX and YY, X∧YX\wedge Y is tautologically equivalent to Y∧XY\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β†’Q,P⊨QP\rightarrow Q, P\models Q is an instance of Modus Ponens.

Observation

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

Monotonicity of Valid Inferences

For all formulas XX, YY and ZZ, if X⊨YX\models Y, then X,Z⊨YX, 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 XX and YY, X⊨YX\models Y if, and only if, Xβ†’YX\rightarrow Y is a tautology.

Practice Questions#

  1. Suppose that XX and YY are formulas and that X⊨YX\models Y. Which of the following is not true?

  2. Suppose that XX and YY are formulas and that X⊨YX\models Y. Which of the following is true?

  3. Suppose that XX and YY are formulas and that X⊨YX\models Y. Which of the following is true?

  4. Consider the argument P∧Q,Pβ†’Rβ‡’RP\wedge Q, P\rightarrow R\Rightarrow R. Which of the following is true?

  5. Which of the following formulas can be substituted for XX to ensure that the following argument is valid?

    Pβ†’Q,Β¬Q,P∨R⊨XP\rightarrow Q, \neg Q, P\vee R\models X

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

    X,P,Q⊨RX, P, Q\models R

  7. Consider the inference rule: Β¬X∨Y,Xβ‡’Y\neg X \vee Y, X \Rightarrow Y. Which of the following is true?