Discrete Structures 1 Lecture15
Rules of Inference
Objectives:
Valid Arguments in Propositional Logic
Rules of Inference
___________________________________________________________________________
Valid Arguments in Propositional Logic:
An argument in propositional logic is a sequence of propositions. All but the final
proposition in the argument are called premises and the final proposition is called the
conclusion. An argument is valid if the truth of all its premises implies that the conclusion is
true. An argument form in propositional logic is a sequence of compound propositions
involving propositional variables. An argument form is valid if no matter which particular
propositions are substituted for the propositional variables in its premises, the conclusion is
true if the premises are all true.
((p →q) ∧ p) → q
premise1 premise2 conclusion
Consider the following argument involving propositions.
"If you have a current password, then you can log onto the network."
"You have a current password."
Therefore,
"You can log onto the network."
Then, the argument has the form
p→q
p
∴q
where ∴ is the symbol that denotes ''therefore.''
Using this notation, the hypotheses are written in a column, followed by a horizontal bar,
followed by a line that begins with the therefore symbol and ends with the conclusion.
We know that when p and q are propositional variables, the statement ((p →q) ∧ p) → q is a
tautology .In particular, when both p → q and p are true, we know that q must also be true.
We say this form of argument is valid because whenever all its premises are true, the
conclusion must also be true.
We can always use a truth table to show that an argument form is valid. Instead of using truth
tables, we can first establish the validity of some relatively simple argument forms, called
rules of inference. These rules of inference can be used as building blocks to construct more
complicated valid argument forms.
The most important rules of inference in propositional logic are given in Table1.
Discrete Structures 2 Lecture15
Example 1: State which rule of inference is the basis of the following argument?
"It is below freezing now. Therefore, it is either below freezing or raining now."
Solution: Let p be the proposition "It is below freezing now" and q the proposition "It is
raining
now." Then this argument is of the form
∴p∨q
p
This is an argument that uses the addition rule.
Example 2: State which rule of inference is the basis of the following argument?
"It is below freezing and raining now. Therefore, it is below freezing now."
Solution: Let p be the proposition "It is below freezing now," and let q be the proposition "It
is
Discrete Structures 3 Lecture15
p∧q
raining now." This argument is of the form
∴p
This argument uses the simplification rule.
Example 3: State which rule of inference is used in the argument?
If it rains today, then we will not have a barbecue today. If we do not have a barbecue today,
then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a
barbecue tomorrow.
Solution: Let p be the proposition "It is raining today," let q be the proposition "We will not
have a barbecue today," and let r be the proposition "We will have a barbecue tomorrow."
Then this argument is of the form
p→q
q→r
∴p→r
Hence, this argument is a hypothetical syllogism.
Exercise 1.5
1. Find the argument form for the following argument and determine whether it is valid. Can
we conclude that the conclusion is true if the premises are true?
If Socrates is human, then Socrates is mortal.
Socrates is human.
∴Socrates is mortal.
2. Find the argument form for the following argument and determine whether it is valid. Can
we conclude that the conclusion is true if the premises are true?
If George does not have eight legs, then he is not an insect.
George is an insect.
∴ George has eight legs.
3. What rule of inference is used in each of these arguments?
a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a
computer science major.
b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a
mathematics major.
c) If it is rainy, then the pool will be closed. It is rainy. Therefore, the pool is closed.
d) If it snows today, the university will close. The university is not closed today. Therefore, it
did not snow today.
e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I
will sunburn. Therefore, if I go swimming, then I will sunburn.
4. What rule of inference is used in each of these arguments?
a) Kangaroos live in Australia and are marsupials. Therefore, kangaroos are marsupials.
Discrete Structures 4 Lecture15
b) It is either hotter than 100 degrees today or the pollution is dangerous. It is less than 100
degrees outside today. Therefore, the pollution is dangerous.
c) Linda is an excellent swimmer. If Linda is an excellent swimmer, then she can work as a
lifeguard. Therefore, Linda can work as a lifeguard.
d) Steve will work at a computer company this summer. Therefore, this summer Steve will
work at a computer company or he will be a beach bum.
e) If I work all night on this homework, then I can answer all the exercises. If I answer all the
exercises, I will understand the material. Therefore, if I work all night on this homework,
then I will understand the material.
5. Use rules of inference to show that the hypotheses "Randy works hard," "If Randy works
hard, then he is a dull boy," and "If Randy is a dull boy, then he will not get the job" imply
the conclusion "Randy will not get the job."
6. Use rules of inference to show that the hypotheses "If it does not rain or if it is not foggy,
then the sailing race will be held and the lifesaving demonstration will go on," "If the sailing
race is held, then the trophy will be awarded," and "The trophy was not awarded" imply the
conclusion
"It rained."
7. What rules of inference are used in this famous argument?
"All men are mortal. Socrates is a man. Therefore, Socrates is mortal"
8. What rules of inference are used in this argument? "No man is an island. Manhattan is an
island. Therefore, Manhattan is not a man."
9. For each of these sets of premises, what relevant conclusion or conclusions can be drawn?
Explain the rules of inference used to obtain each conclusion from the premises.
a) "If I take the day off, it either rains or snows." "I took Tuesday off or I took Thursday off."
"It was sunny on Tuesday." "It did not snow on Thursday."
b) "If I eat spicy foods, then I have strange dreams." "I have strange dreams if there is
thunder while I sleep." "I did not have strange dreams."
c) "I am either clever or lucky." "I am not lucky." "If I am lucky, then I will win the lottery."
d) "Every computer science major has a personal computer." "Ralph does not have a personal
computer." "Ann has a personal computer."
e) "What is good for corporations is good for the United States." "What is good for the United
States is good for you." "What is good for corporations is for you to buy lots of stuff."
f) "All rodents gnaw their food." "Mice are rodents." "Rabbits do not gnaw their food." "Bats
are not rodents."
10. For each of these sets of premises, what relevant conclusion or conclusions can be drawn?
Explain the rules of inference used to obtain each conclusion from the premises.
a) "In play hockey, then I am sore the next day." "I use the whirlpool if I am sore." "I did not
use the whirlpool."
Discrete Structures 5 Lecture15
b) "In work, it is either sunny or partly sunny." "I worked last Monday or I worked last
Friday." "It was not sunny on Tuesday." "It was not partly sunny on Friday."
c) "All insects have six legs." "Dragonflies are insects." "Spiders do not have six legs."
"Spiders eat dragonflies."
d) "Every student has an Internet account." "Homer does not have an Internet account."
"Maggie has an Internet account."
e) "All foods that are healthy to eat do not taste good." "Tofu is healthy to eat." "You only eat
what tastes good." "You do not eat tofu." "Cheeseburgers are not healthy to eat."
f) "I am either dreaming or hallucinating." "I am not dreaming." "If I am hallucinating, I see
elephants running down the road."
_______________