Rules of inference

If you already know some statements and you want to deduce another statement, then rules of inference tell you if this is logically valid.

The fundamental rules of inference are classified according to the logical operators that appear in them.

Introduction rules tell you what you need to know if you want to deduce a certain expression.
Elimination rules tell you what you can deduce if you already know a certain expression.

All valid arguments can be formed using these fundamental rules of inference in various combinations.

Some rules of inference ask you to temporarily assume something. You should think of these assumptions as taking place in a separate hypothetical world. Anything true in the real world is true in the hypothetical world, but not the other way around. So conclusions from the hypothetical world may not be brought back into the real world, except as specified by the rule of inference. (In a complicated proof, there might be hypothetical worlds within hypothetical worlds within ..., and all of these need to be kept separate.)

Rules for propositions

T introduction	F elimination
No matter what,	If we know F,
we can deduce T.	then we can deduce anything.

∧ (AND) introduction	∨ (OR) elimination
If we know P and we know Q,	If we know P ∨ Q and assuming P gives us R and assuming Q gives us R,
then we can deduce P ∧ Q.	then we can deduce R.

∨ (OR) introduction (left)	∧ (AND) elimination (left)
If we know P,	If we know P ∧ Q,
then we can deduce P ∨ Q.	then we can deduce P.

∨ (OR) introduction (right)	∧ (AND) elimination (right)
If we know Q,	If we know P ∧ Q,
then we can deduce P ∨ Q.	then we can deduce Q.

→ introduction	→ elimination
If assuming P gives us Q,	If we know P and we know P → Q,
then we can deduce P → Q.	then we can deduce Q.

¬ introduction	¬ elimination
No matter what,	If we know P and we know ¬P,
we can deduce P ∨ ¬P.	then we can deduce F.

Also use these definitions:

P ↔ Q := (P → Q) ∧ (Q → P);
P ⊕ Q := (P ∨ Q) ∧ ¬(P ∧ Q);
P ↑ Q := ¬(P ∧ Q);
P ↓ Q := ¬(P ∨ Q).

These tell you how to introduce or eliminate the other logical operators.

Rules for predicates

∀ introduction	∀ elimination
If assuming a variable x gives us P(x),	If we know ∀x P(x) and we have y,
then we can deduce ∀x P(x).	then we can deduce P(y).

∃ introduction	∃ elimination
If we have y and we know P(y),	If we know ∃x P(x),
then we can deduce ∃x P(x).	then we can construct a constant x and deduce P(x).

To avoid confusion, always use a separate variable for every quantified statement.

Go back to the MATH 112 homepage.

This web page was written in 2003 by Toby Bartels. Toby reserves no legal rights to it.

The permanent URI of this web page is http://tobybartels.name/MATH112/2003/inference/.