cs122

Tutorial 3: Inference Rules

Study Rosen 1.5, and the notes on Rules of Inference.

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.

Quick Test

pqp ∧ q(p ∧ q) → q
00
01
10
11
To show using a truth table that ((p ∧ q) → q) is a tautology, we need to fill in the remaining two columns of the truth table.

1. The third column of the truth table is:
0, 0, 0, 1
0, 1, 1, 1
0, 1, 1, 0

2. The fourth column of the truth table is:
1, 0, 0, 0
1, 1, 1, 1
0, 1, 1, 0

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

p1

p2

…

pn

∴q

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

p

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

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.

Quick Test

We can prove using a truth table that ((p∧(p→q))→q) is a tautology. Answer the following questions about the truth table needed to do that.

3. The truth table should have how many columns?
3
4
5

4. The truth table should have how many rows?
2
4
8

5. To prove that it is a tautology, the last column in the truth table should:
contain all 1s
contain all 0s

Self Check: Create the truth table to prove that ((p∧(p→q))→q) is a tautology.

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!

Quick Test

Create the truth table to try to prove that ((¬p∧(p→q))→q) is a valid argument and answer the following questions.

6. To prove that the argument is valid, one shows that the entire statement is a tautology.
True
False

7. The last column of the truth table is:
0, 0, 0, 0
1, 1, 1, 1
0, 1, 1, 1

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

8. All students in the class understand logic. Marvin is a student in this class. Therefore, Marvin understands logic.
Valid
Invalid

9. Every computer science major takes calculus. Heather is taking calculus. Therefore, Heather is a computer science major.
Valid
Invalid

Example 4. We know that π > 3 (it is 3.14...), and if x > 3 then x2 > 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:

greaterthan(π,3)

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

∴square(π,9)

Note: π gets substituted into the predicates on the second and third lines. We can do that because x is used with ∀, which means any substitution, variable or constant, should be valid.

Self Check: show by truth table that (p→q)≡( ¬q→ ¬p)

Quick Test

10. What must be true for ≡ to be true?
p and q must both be true.
The statements on the left (p→q) and right ( ¬q→ ¬p) sides must both be true.
The statements on the left (p→q) and right ( ¬q→ ¬p) sides must have the same truth values under all possible combinations of truth values for p and q.

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:

¬q

p→q

∴ ¬p

Intuitively, when we know the consequent (right side of implies) is false, then the precedent (left side) must be false for the statement to be true. Going back to the earlier example about grass being wet if it is raining. If I know that the grass is dry (¬ wet), then it cannot be raining (¬ p).

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

Quick Test

11. The truth table for proving Modus Tollens has columns:
p, q, ¬p, ¬q, p→q, ¬q ∧ (p→q), (¬q ∧ (p→q)) → ¬p
p, q, ¬q, p→q, ¬q → (p→q), (¬q → (p→q)) → ¬p
p, q, ¬q, p→q, ¬q ∧ (p→q), (¬q ∧ (p→q)) → ¬p

Here is another inference rule, resolution:

p∨q

¬p∨r

∴ q∨r

The premises of resolution say: The conclusion says: because p is either true or false, q or 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

¬p

∴ q

It is resolution with r = false. Disjunctive syllogism is effectively used to determine truth values of single propositions.

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.

Quick Test

Answer the following questions about converting to clause form:

12. ¬(p ∧ t) becomes:
¬ p ∧ ¬ t
¬ p ∨ ¬ t
p ∨ t

13. (p ∧ t) → (r ∨ s) becomes:
¬ p ∨ ¬ t ∨ r ∨ s
(p ∧ t) ∨ (r ∨ s)

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.

Quick Test

What rule of inference is used in each of the following arguments?

14. A kangaroo is a marsupial. Therefore, a kangaroo is either a marsupial or a reptile.
Addition
Simplification
Conjunction

15. If I work hard on my homework, then I can do the problems that are required. If I can do all the problems that are required, then I will do well on my test. Therefore, if I work hard on my homework, I will do well on my test.
Disjunctive Syllogism
Modus Ponens
Hypothetical Syllogism

16. If it snows today, CSU will close. CSU is not closed today. Therefore, it did not snow.
Modus Tollens
Modus Ponens
Resolution

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:

you can prove r using just resolution:
StepStatementReason
1.(p ∨ q) Given
2.(¬ p ∨ r)Given
3.(q ∨ r)Resolution on 1 and 2
4.(¬ q ∨ r)Given
5.rResolution on 3 and 4
We can also use the identity rules. Consider that you are given the following as true: we can prove r as follows:
StepStatementReason
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.rResolution on 4 and 6
Note: this is the same resolution proof as before, but with the premises in a slightly different form.

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

StepStatementReason
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

Quick Test

Suppose you are given the premises:
  1. (p ∧ t) → (r ∨ s)
  2. q → (u ∧ t)
  3. u → p
  4. ¬ s
and are asked to prove (q → r). Answer the following questions about steps in the proof.

17. Which of the following can be deduced as steps in the proof?
¬ u ∨ ¬ t ∨ ¬ q
¬ p ∨ ¬ t ∨ r ∨ s
(u → p) ∨ s

18. Choose one of the following strategies that is useful for the proof.
Resolve premise 1 (converted with equivalences) with premise 4
Apply Hypothetical Syllogism to premise 2 and 3

19. All of the premises listed are used in the proof.
True
False

Self Check: Write out the steps in the full proof for the quick test.