Vectors and Vector Operations



1.5 Rules of Inference and Valid Arguments

In this section we look at rules of inference (also called logical implications or valid arguments) which form the basis of logical arguments. In this section we work with propositions and in the next section we extend to predicates.

Example 1. Consider the following which someone might say.

(1)

This is an example of a valid argument. In order to analyze it better, let

p = "John works in the accounting department"

q = "John makes more than 50K"

Then (1) becomes

(2)

Even though we used the language "Suppose" and "From this we can conclude" we shall view (2) simply as a "big" if-then-else. Thus we represent (2) symbolically as

(3) [(p ( q)p] ( q

Without the terminology "Suppose" and "From this we can conclude" we would put (3) into words as "if p implies q is true and p true then q is true.

The interesting thing is that (3) is always true. We can see that from a truth table.

(4)

A valid argument is an "if-then" statement that is always true. So [(p ( q)p] ( q is an example of a valid argument.

Note that [(p ( q)p] ( q has the form

(5) U ( V

where U and V are the logical expressions U = (p ( q)p and V = q.

If U and V are logical expressions then we say

U logically implies V if U ( V evaluates to true for every possible combination of logical values for the logical variables appearing in them.

We write U ( V if this holds and say U ( V is a rule of inference or logical implication or valid argument.

The rule of inference p(p ( q) ( q is called modus ponens which is sometimes translated as the way that affirms by affirming. It is one of the most famous rules of inference. Modus ponens is also often written as

p

p ( q

(q

Note that in the truth table (4) above showing p(p ( q) ( q is always true, it was not really necessary to make the last column of the truth table. It would have been sufficient to note that whenever there is a 1 in a row in the column for p(p ( q) there is also a 1 in that row for the column of q. This implies that the column for p(p ( q) ( q has all 1's. This is a general rule.

U ( V if whenever there is a 1 in a row for the truth table of U there is a 1 in the truth table of V

One can also show U ( V by showing U ( V = 1 using Boolean algebra.

Example 2. Show p(p ( q) ( q = 1 using Boolean algebra.

Solution. We use p ( q = p' + q. Then (p(p ( q)) ( q = (p(p' + q))' + q = (pp' + pq)' + q = (0 + pq)' + q = (pq)' + q = p' + q' + q = p' +1 = 1.

To summarize, here are three possible ways to show U ( V.

1. Show the truth table of U ( V has a 1 in every row.

2. Show each row of the truth table of U with a 1 also has a 1 in the truth table of V.

3. Show U ( V = 1 using Boolean algebra

Some books state that something is a rule of inference in terms of the notion of a tautology.

An expression U is a tautology if it is true for all values of the logical variables in the expression, i.e. U = 1.

Example 3. Show that p + p' is a tautology.

Solution. It is true if p is true or if p is false. Hence it is a tautology.

In fact it was noted in formula (11) of section 1.3 that p + p' = 1. For example the statement "Either it is raining or it is not raining." is always true.

Note that

U ( V if and only if U ( V is a tautology

So, another way of stating that modus ponens is a rule of inference is to say that "(p(p ( q)) ( q is a tautology".

Another famous rule of inference is modus tollens which is (p ( q)q' ( p'. In words, if p implies q and q is false then p is false.

Example 4. The following two statements have the form of modus tollens and hence are always true.

If Fido is a bird implies Fido can fly and if Fido can not fly then Fido is not a bird.

If John works in the accounting department implies John makes more than $50K and if John doesn't make more than $50K then John doesn't work in the accounting department.

Example 5. Show modus tollens is a rule of inference.

Solution. The truth table at the right does this since every row that has a 1 for (p ( q)q' also has a 1 for p'.

An alternative way to see that modus tollens is use the following famous equivalence

(6) p ( q = q' ( p'

This is called transposition. The expression q' ( p' is called the contrapositive of p ( q, so (6) says an expression and its contrapositive have the same truth value. If we use transposition then (p ( q)q' = q'(q' ( p'). By modus ponens one has q'(q' ( p') ( p'. So (p ( q)q' ( p'.

Here is a list of basic rules of inference and equivalences that are used to verify that other expressions are also rules of inference.

Rules of Inference

(7) p(p ( q) ( q modus ponens (MP)

(8) (p ( q)q' ( p' modus tollens (MT)

(9) (p ( q)(q ( r) ( p ( r hypothetical syllogism (HS)

(10) (p + q)p' ( q disjunctive syllogism (DS)

(11) p ( p + q addition or disjunction introduction (AD)

(12) pq ( p simplification (S)

(13) (p ( q)(r ( s)(p + r) ( q + s constructive dilemma (CP)

(14) (p ( q)(r ( s)(q' + s') ( p' + r' destructive dilemma (DD)

(15) p ( q ( p ( pq absorption (AB)

Equivalences

(16) p ( q = (p ( q)(q ( p) = pq + p'q'

(17a) p (( q = p' + q = q' ( p' Transposition (T)

(17b) pq1q2…qn (( r = p' + q1' + q2' + … + qn' + r = r'q1q2…qn ( p' Transposition (T)

(18) (pq) ( r = p ( (q ( r) exportation (E)

That (7) – (15) are rules of inference and (16) – (18) are equivalences can be verified either by means of truth tables or Boolean algebra. If one does this by Boolean algebra, then it is useful to recall that (p ( q) = p' + q and (p ( q)' = pq'.

The term syllogism has pretty much the same meaning at the term rule of inference.

In words, a hypothetical syllogism can be stated as "if p implies q and q implies r then p implies r.

Example 11. The statement "If Tweetie is a bird implies Tweetie can fly and if Tweetie can fly implies Tweetie has feathers then Tweetie is a bird implies Tweetie has have feathers" is a true statement.

Example 12. Show a hypothetical syllogism is a rule of inference.

In the truth table at the right every row that has a 1 for (p ( q)(q ( r) also has a 1 for p ( r.

In addition to truth tables and Boolean algebra there is another method to show expressions are valid arguments (i.e. rules of inference). This method is based upon the following two properties of rules of inference.

(19) If U ( V and V ( W then U ( W transitivity

(20) If U ( V and U ( W then U ( VW conjunction

To see why transitivity is true note that U ( V implies whenever there is a 1 in a row of the truth table for U there is a 1 in the corresponding row of the truth table for V. Similarly, V ( W implies whenever there is a 1 in a row of the truth table for V there is a 1 in the corresponding row of the truth table for W. So if U ( V and V ( W are both true then if there is a 1 in a row of the truth table for U then there is a 1 in the corresponding row of the truth table of V and hence there is a 1 in the corresponding row of the truth table of W, so U ( W is true.

To see why conjunction is true suppose U ( V and U ( W . So whenever there is a 1 in a row of the truth table for U there is a 1 in the corresponding rows of the truth tables for V and W and hence the corresponding row of VW. Thus U ( VW.

Some books tend to use the term valid argument for a rules of inference U ( V where U is the and of several other logical expressions, i.e (U1U2…Un) ( V where U1, U2, …, Un and V are logical expressions. U1, U2, …, Un are called the hypotheses or premises and V is called the conclusion. Often we write the valid argument U1U2…Un ( V as

U1

U2

…

(V

To show U1U2…Un ( V it is sufficient to do the following.

(21)

Next note that to show U1U2…Um ( Um+1 it is sufficient to do the following.

(22)

The reason for this is that we can use simplification to conclude that U1U2…Um ( Uj1Uj2…Ujk and then use transitivity to conclude U1U2…Um ( Un+1.

Often when people use (22) to verify that U1U2…Un ( V is a valid argument they display the logic something like the following.

Step Reason

1. U1 Premise

2. U2 Premise

. . .

(23) n Un Premise

n +1 Un+1 Rule r1 using j1,1, j1,2, …, j1,k1

n +2 Un+2 Rule r2 using j2,1, j2,2, …, j2,k2

. . .

n +m Un+m = V Rule rm using jm,1, jm,2, …, jm,km

where r1, r2, …, rm are rules of inference. Here is an example.

Example 13. Show that the following is a valid argument.

If John is not optimistic and John is busy

and John will play the lottery only if he is optimistic

and If John does not play the lottery then he will visit the casino

and If John visits the casino then he will be broke

then John is broke

Let

p = John is optimistic

q = John is busy

r = John will play the lottery

s = John will visit the casino

t = John is broke

Then the above is

If p'q

and r ( p

and r' ( s

and s ( t

then t

or p'q(r ( p)(r' ( s)(s ( t) ( t. The following shows this is a valid argument.

Step Reason

1. p' Premise

2. r ( p Premise

3. r' Modus tollens using 1 and 2

4. r' ( s Premise

5. s Modus ponens using 3 and 4

6. s ( t Premise

7. t Modus ponens using 5 and 6

When using the above method of establishing valid arguments, the following rule of inference is useful.

(24) pq ( pq Conjunction

It is typically applied in the following type of situation. Suppose you have an argument of the following form.

Step Reason

1. U1 Premise

2. U2 Premise

. . .

n Un Premise

n +1 Un+1 Rule r1 using j1,1, j1,2, …, j1,k1

n +2 Un+2 Rule r2 using j2,1, j2,2, …, j2,k2

. . .

n +m Un+m Rule rm using jm,1, jm,2, …, jm,km

At this point you can add a line of the form

n +m+1 UjUk Conjunction using j and k

Example 14. Show that the following is a valid argument

If Tweetie is a bird

and Tweetie is a bird implies Tweetie flies

and Tweetie is a bird implies Tweetie has feathers

then Tweetie flies and has feathers

If we let

p = Tweetie is a bird

q = Tweetie flies

r = Tweetie has feathers

then what we want to show has the form [p(p ( q)(p ( r)] ( qr. We show this is a valid argument as follows.

Step Reason

1. p Premise

2. p ( q Premise

3. q Modus ponens using 1 and 2

4. p ( r Premise

5. r Modus ponens using 1 and 4

6. qr Conjunction using 3 and 5

The list of basic rules of inference and equivalences discussed above is probably not long enough to always easily show that something is a valid argument using the method (19). In some cases we might want to supplement the basic rules with a truth table.

Example 15. Show that the following is a valid argument.

If Fido is a dog implies Fido is a mammal

then Fido is a brown dog implies Fido is a brown mammal

If we let

p = Fido is a dog

q = Fido is a mammal

r = Fido is brown

then what we want to show has the form (p ( q) ( (pr ( qr). It looks like this might be hard to show using (7) – (18). In this case we can use a truth table. As you can see from the truth table at the below, everywhere there is a 1 in the column for p ( q there is a 1 in the column for pr ( qr. So (p ( q) ( (pr ( qr).

It turns out that with a little bit of manipulation it is possible to deduce (p ( q) ( (pr ( qr) by an argument of the form (23). This is done as follows. To show (p ( q) ( (pr ( qr) we need to show [(p ( q) ( (pr ( qr)] = 1. However, by (18) one has (p ( q) ( (pr ( qr) equivalent to [(p ( q)pr] ( qr. So we need to show [[(p ( q)pr] ( qr] = 1 which is the same as [(p ( q)pr] ( qr. This can be shown to be a valid argument as follows.

Step Reason

1. p ( q Premise

2. p Premise

3. q Modus ponens using 1 and 2

4. r Premise

5. qr Conjunction using 3 and 4

Example 16 (Problem #6, §1.6, Rosen, 7th edition). Show that the following is a valid argument.

If it does not rain or it is not foggy then the sailing race will be held and the lifesaving demonstration will go on

and if the sailing race is held then the trophy will be awarded

and the trophy was not awarded

then it rained

Let

p = it rains

q = it is foggy

r = the sailing race is held

s = the lifesaving demonstration goes on

t = the trophy is awarded

Then the above is ((p' + q')( rs)(r ( t)t' ( p The following shows this is a valid argument.

Step Reason

1. r ( t Premise

2. t' Premise

3. r' MT using 1 and 2

4. r' + s' Addition using 3

5. (rs)' DeMorgan using 4

6. (p' + q')( rs Premise

7. (p' + q')' MT using 5 and 6

8. pq DeMorgan using 7

9. p Simplification using 8

Example 17. Show that simplification, pq ( p and pq ( q, are rules of inference.

Solution. In pq ( p one has U = pq and V = p. At the right is a truth table. Note that every row of the truth table of (pq) ( p has a 1, so pq ( p by method 1. Alternatively, whenever the truth table of pq has a 1 (only the last row) the truth table of p also has a 1, so pq ( p by method 2. If we use method 3, then we need to show (pq) ( p = 1. Recall that p ( q = p' + q, so (pq) ( p = (pq)' + q. Using de Morgan and other basic equivalences of Boolean algebra, one has (pq)' + q = p' + q' + q = p' + 1 = 1. We could use either of these three methods to show pq ( q. However, it is probably conceptually simpler to use the following principle.

Suppose U ( V and suppose U' and V' are obtained from U and V by replacing parts of U and V by equivalent expressions. Then U' ( V'.

To apply this principle to show pq ( q, first note that if we interchange the roles of p and q then we conclude qp ( q. Since qp = pq, we conclude by the principle that pq ( q.

Example 18. Show that the proposition “If John likes to watch the Tigers and John likes to eat hot dogs then John likes to watch the Tigers” is true no matter whether John likes to watch the Tigers or eat hot dogs.

Solution. If we let p = “John likes to watch the Tigers” and q = “John likes to eat hot dogs” then the statement “If John likes to watch the Tigers and John likes to eat hot dogs then John likes to watch the Tigers” has the form (pq) ( p, i.e it is a simplification. As we saw in Example 1, it is true no matter whether each of the statements p and q are true or false.

Remark. We often just say "if U then V" for U ( V. This is confusing since we also say "if U then V" for U ( V.

Example 19. Show that addition, p ( p + q, is a rule of inference.

Solution. In this example, U = p and V = p + q. To show p ( p + q note that in the truth table at the right whenever there is a 1 in the p column, there is a 1 in the p + q column. So p ( p + q is a rule of inference. Alternatively, we could use Boolean algebra: p ( (p + q) = p' + p + q = 1 + q = 1.

Example 20. Show that the proposition “If John likes to watch the Tigers then John likes to eat hot dogs or John likes to eat hot dogs” is true no matter whether John likes to watch the Tigers or eat hot dogs.

Solution. If we let p = “John likes to watch the Tigers” and q = “John likes to eat hot dogs” then the statement “If John likes to watch the Tigers then John likes to eat hot dogs or John likes to eat hot dogs” has the form p ( (p + q), i.e it is an addition. As we saw in Example 3, it is true no matter whether each of the statements p and q is true or false.

Example 21. Show disjunctive syllogism (p + q)p' ( q is a rule of inference.

Solution. (p + q)p' = pp' + qp' = 0 + qp' = qp'. Then qp' ( q by simplification.

Example 22. Show p ( q = p ( pq is an equivalence.

Solution. p ( pq = p' + pq = (p' + p)(p' + q) = (1)(p ( q) = p ( q.

In order to show constructive dilemma is a rule of inference, it will be helpful to use another general method of proving valid arguments called Proof by Contradiction. It says

UV1V2…Vn ( W if and only if W'V1V2…Vn ( U'

The reason is that UV1V2…Vn ( W if and only if UV1V2…Vn ( W = 1 and W'V1V2…Vn ( U' if and only if W'V1V2…Vn ( U' = 1. However by (10b) the two logical expressions UV1V2…Vn ( W and W'V1V2…Vn ( U' are equivalent.

Example 23. Show constructive dilemma (p ( q)(r ( s)(p + r) ( q + s is a rule of inference.

Solution. We prove this by contradiction. We must show (q + s)'(p ( q)(r ( s) ( (p + r)'. Using DeMorgan this is equivalent to q's'(p ( q)(r ( s) ( p'r'. By MT, q'(p ( q) ( p' and s'(r ( s) ( r'. Combining this with simplification, (14) and transitivity proves CD is a rule of inference.

Destructive dilemma can be proved from constructive dilemma in the same way modus tollens is proved from modus ponens.

Example 16 (Page 73, Rosen, 7th edition). Show that the following is a valid argument.

If it is not sunny this afternoon and it is colder than yesterday

and we will go swimming only if it is sunny

and if we do not go swimming then we will take a canoe trip

and if we take a canoe trip then we will be home by sunset

then we will be home by sunset

Let

p = it is sunny

q = it is colder than yesterday

r = we go swimming

s = we take a canoe trip

t = we will be home by sunset

Then the above is p'q(r ( p)(r' ( s)(s ( t) ( t The following shows this is a valid argument.

Step Reason

1. p' Premise

2. r ( p Premise

3. r' MT using 1 and 2

4. r' ( s Premise

5. s MP using 3 and 4

6. s ( t Premise

7. t MP using 5 and 6

-----------------------

|p |q |p(q |p(p(q) |p(p(q) ( q |

|0 |0 |1 |0 |1 |

|0 |1 |1 |0 |1 |

|1 |0 |0 |0 |1 |

|1 |1 |1 |1 |1 |

|p |q |p(q |q' |(p(q)q' |p' |

|0 |0 |1 |1 |1 |1 |

|0 |1 |1 |0 |0 |1 |

|1 |0 |0 |1 |0 |0 |

|1 |1 |1 |0 |0 |0 |

|p |q |r |p ( q |q ( r |(p(q)(q(r) |p ( r |

|0 |0 |0 |1 |1 |1 |1 |

|0 |0 |1 |1 |1 |1 |1 |

|0 |1 |0 |1 |0 |0 |1 |

|0 |1 |1 |1 |1 |1 |1 |

|1 |0 |0 |0 |1 |0 |0 |

|1 |0 |1 |0 |1 |0 |1 |

|1 |1 |0 |1 |0 |0 |0 |

|1 |1 |1 |1 |1 |1 |1 |

|p |q |r |p ( q |pr |qr |pr ( qr |

|0 |0 |0 |1 |0 |0 |1 |

|0 |0 |1 |1 |0 |0 |1 |

|0 |1 |0 |1 |0 |0 |1 |

|0 |1 |1 |1 |0 |1 |1 |

|1 |0 |0 |0 |0 |0 |1 |

|1 |0 |1 |0 |1 |0 |0 |

|1 |1 |0 |1 |0 |0 |1 |

|1 |1 |1 |1 |1 |1 |1 |

|p |q |pq |(pq)(p |

|0 |0 |0 |1 |

|0 |1 |0 |1 |

|1 |0 |0 |1 |

|1 |1 |1 |1 |

|p |q |p + q |

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |1 |

|1 |1 |1 |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download