Rules of inference allow us to deduce new statements from statements we already have.

An **argument** is a sequence of n+1 propositions.
The first n propositions (p1…pn) are called **premises**,
the last one (q) is called the **conclusion**.
An argument is **valid** if ((p1…pn) → q) is a tautology.

Example 1. Let p1 be "I am wearing a T-shirt", and p2 be "I am wearing shorts", given (p ∧ q) then I can conclude: "I am wearing shorts". This is an example of "Simplification": p∧q→q.

p | q | p ∧ q | (p ∧ q) → q |

0 | 0 | ||

0 | 1 | ||

1 | 0 | ||

1 | 1 |

Inference rules are templates for valid arguments, just like the Simplification example above. The notation for these arguments is as follows:

p2

…

__pn__

∴q

Notice the underscore between the premises and the conclusion, and that ∴ means "therefore". In the case of simplification we can write:

__q__

∴q

Example 2. Here is something intuitive: given p1 "if it is raining, then the grass is wet" and p2 "it is raining", we can conclude q "the grass is wet". This is an example of the use of the inference rule called MODUS PONENS:

__p→q__

∴q

This inference rule is totally intuitive; we use it all the time without even thinking about it. It is just that we have given it a Latin name (it means: the mode that affirms) and use some new notation.

Rules of inference are "truth preserving" which means that as long as the premises are true, what is concluded using these rules is guaranteed to be true. But what happens when the premises are not true? Then the argument is *not* valid.

Example 3. An old Scotish nursery rhyme includes the statement "If wishes were horses then beggars would ride." Given a premise that "wishes were horses" is true, then using modus ponens, we can conclude that "beggars would ride." Since we know that it is false that wishes were horses, we can conclude nothing at all from the implication -- it could be true or it could be false. There is no way to tell -- the argument is not valid.

Aside:For those who are curious, the full nursery ryhme is:

If wishes were horses then beggars would ride,

If turnips were swords I'd have one by my side.

If 'ifs' and 'ands' were pots and pans

There would be no need for tinkers hands!

For the next questions, determine whether the arguments are valid.

Example 4.
We know that π > 3 (it is 3.14...), and if x > 3 then x^{2} > 9,
so we conclude that π^{2} > 9.

This example uses modus ponens, but requires a bit more representational power than propositional logic. It requires predicates. Here x can be considered as a variable in the predicate greaterthan (>) and π can be a constant, as is '3' and '9'. So the statements can be written as follows:

__ ∀ x greaterthan(x,3)→square(x,9)__

∴square(π,9)

A derivative of the modus ponens is the MODUS TOLLENS, which uses the above equivalence and says: if(p→q) and ¬q we can conclude ¬p. (Note: this is close, but not quite the statement that was not valid.) In diagram form:

__p→q__

∴ ¬p

Again, we can prove Modus Tollens using a truth table.

Here is another inference rule, **resolution**:

__¬p∨r__

∴ q∨r

- premise 1: if p = false then q must be true.
- premise 2: if p = true then not p is false so r must be true

This is a very powerful inference rule used in theorem proving. In fact,we can implement automated theorem provers based on resolution. It can be programmed because it has the property of simplifying large collections of premises like a process of elimination. In the description above, we can ignore p's truth value and instead focus on q and r -- clearly, at least one of them must be true.

A special case of resolution is disjunctive syllogism:

__¬p__

∴ q

Resolution theorem proving works when all statements are converted to *clause* form, where a clause is a disjunction of variables or their negations. So p→q gets converted to the equivalent clause ¬p ∨ q. Additionally, negations get distributed as in ¬(p∧q) becomes ¬p ∨ ¬q.

Study the identity rules from Rosen 1.2 (tables 6 and 7) again. They are important here. Also study Rosen 1.5 Table 1: rules of inference. You will learn a number of inference rules in addition to the set we have described here.

We can use the rules of inference to build arguments, i.e., as another proof technique in addition to truth tables. Using just resolution, one can create new resolvents step by step until you discover the truth value of a particular proposition (or prove that it is true or false).

Consider that you are given the following as true:

- p ∨ q
- ¬ p ∨ r
- ¬ q ∨ r

Step | Statement | Reason |
---|---|---|

1. | (p ∨ q) | Given |

2. | (¬ p ∨ r) | Given |

3. | (q ∨ r) | Resolution on 1 and 2 |

4. | (¬ q ∨ r) | Given |

5. | r | Resolution on 3 and 4 |

- p ∨ q
- p → r
- q → r

Step | Statement | Reason |
---|---|---|

1. | (p ∨ q) | Given |

2. | (p → r) | Given |

3. | (¬ p ∨ r) | Logical equivalence 1 in Table 7 in Rosen Chapter 1.2 applied to 2 |

4. | (q ∨ r) | Resolution on 1 and 3 |

5. | (q → r) | Given |

6. | (¬ q ∨ r) | Logical equivalence 1 in Table 7 in Rosen Chapter 1.2 applied to 5 |

7. | r | Resolution on 4 and 6 |

Here is an example of a proof using inference rules to show that ((p∧q)∨r) and (r→s) imply p∨s

Step | Statement | Reason |
---|---|---|

1. | (p∧q)∨r | Given |

2. | (p∨r)∧(q∨r) | Distributive law with step 1 |

3. | (p∨r) | Simplification of 2 |

4. | (r→s) | Given |

5. | (¬r∨s) | Logical equivalence of 4 |

6. | p ∨ s | Resolution of 3 and 5 |

- (p ∧ t) → (r ∨ s)
- q → (u ∧ t)
- u → p
- ¬ s