Page 99 - Discrete Mathematics and Its Applications

78 1 / The Foundations: Logic and Proofs

combines universal instantiation and modus tollens and can be expressed in the following way:

∀x(P (x) → Q(x))
¬Q(a), where a is a particular element in the domain

∴ ¬P(a)

The verification of universal modus tollens is left as Exercise 25. Exercises 26–29 develop
additional combinations of rules of inference in propositional logic and quantified statements.

Exercises

1. Find the argument form for the following argument and e) If I work all night on this homework, then I can an-
determine whether it is valid. Can we conclude that the swer all the exercises. If I answer all the exercises, I
conclusion is true if the premises are true? will understand the material. Therefore, if I work all
night on this homework, then I will understand the
If Socrates is human, then Socrates is mortal. material.
Socrates is human. 5. Use rules of inference to show that the hypotheses “Randy
works hard,” “If Randy works hard, then he is a dull boy,”
∴ Socrates is mortal.
and “If Randy is a dull boy, then he will not get the job”
imply the conclusion “Randy will not get the job.”
2. Find the argument form for the following argument and
determine whether it is valid. Can we conclude that the 6. Use rules of inference to show that the hypotheses “If it
conclusion is true if the premises are true? does not rain or if it is not foggy, then the sailing race will
be held and the lifesaving demonstration will go on,” “If
If George does not have eight legs, then he is not a the sailing race is held, then the trophy will be awarded,”
spider. and “The trophy was not awarded” imply the conclusion
George is a spider. “It rained.”
7. What rules of inference are used in this famous argu-
∴ George has eight legs.
ment? “All men are mortal. Socrates is a man. Therefore,
Socrates is mortal.”
3. What rule of inference is used in each of these argu-
ments? 8. What rules of inference are used in this argument? “No
man is an island. Manhattan is an island. Therefore, Man-
a) Alice is a mathematics major. Therefore, Alice is ei-
theramathematicsmajororacomputersciencemajor. hattan is not a man.”
b) Jerry is a mathematics major and a computer science 9. For each of these collections of premises, what relevant
major. Therefore, Jerry is a mathematics major. conclusion or conclusions can be drawn? Explain the
c) If it is rainy, then the pool will be closed. It is rainy. rules of inference used to obtain each conclusion from
Therefore, the pool is closed. the premises.
d) If it snows today, the university will close. The uni- a) “If I take the day off, it either rains or snows.” “I took
versity is not closed today. Therefore, it did not snow Tuesday off or I took Thursday off.” “It was sunny on
today. Tuesday.” “It did not snow on Thursday.”
e) If I go swimming, then I will stay in the sun too long. b) “If I eat spicy foods, then I have strange dreams.” “I
If I stay in the sun too long, then I will sunburn. There- have strange dreams if there is thunder while I sleep.”
fore, if I go swimming, then I will sunburn. “I did not have strange dreams.”
4. What rule of inference is used in each of these arguments? c) “I am either clever or lucky.” “I am not lucky.” “If I
a) KangaroosliveinAustraliaandaremarsupials.There- am lucky, then I will win the lottery.”
fore, kangaroos are marsupials. d) “Every computer science major has a personal com-
b) It is either hotter than 100 degrees today or the pollu- puter.” “Ralph does not have a personal computer.”
tion is dangerous. It is less than 100 degrees outside “Ann has a personal computer.”
today. Therefore, the pollution is dangerous. e) “What is good for corporations is good for the United
c) Linda is an excellent swimmer. If Linda is an excellent States.” “What is good for the United States is good
swimmer, then she can work as a lifeguard. Therefore, for you.” “What is good for corporations is for you to
Linda can work as a lifeguard. buy lots of stuff.”
d) Steve will work at a computer company this summer. f) “All rodents gnaw their food.” “Mice are rodents.”
Therefore, this summer Steve will work at a computer “Rabbits do not gnaw their food.” “Bats are not ro-
company or he will be a beach bum. dents.”