1-63 1.

5 Rules of Inference 63

1.5 Rules of Inference

Introduction
Later in this chapter, we will study proofs. Proofs in mathematics are
valid arguments that establish the truth of mathematical statements. By an argument-
we understand a sequence of sentences that end with a conclusion and, therefore,
a conclusion, or the final sentence of the argument, must follow the truth value of the sentences
premises of the argument. In other words, an argument is valid if and only if it is
It is impossible for all the premises to be true and the conclusion to be false. To deduce new
sentenças de sentenças que já temos, usamos regras de inferência, as quais são moldes para cons-
establishing valid arguments. Rules of inference are our basic tools for establishing
the determination of the truth-value of the sentences.
Before we study mathematical proofs, let's look at arguments that involve
comes only compound propositions. Let’s define what it means for an argument to be valid when
It involves compound propositions. So, let's introduce a set of inference rules.
of propositional logic. These rules of inference are the most important ingredient in the production-
the formation of valid arguments. After illustrating how inference rules are used to
to produce valid arguments, we will describe some common forms of incorrect reasoning,
fallacies, which lead us to invalid arguments.
After studying the rules of inference in propositional logic, we will introduce rules
of inference for quantified sentences. We will describe how these rules of inference
can be used to produce valid arguments. These rules of inference for sentences
that involve universal and existential quantifiers play an important role in demonstrations
tractions in computer science and mathematics, although they are always used without being
explicitly mentioned.
Finally, we will show how inference rules for propositional sentences and quan-
Certifications can be combined. These combinations are often used in arguments.
complicated mints.

Valid Arguments in Propositional Logic

Consider the following argument involving propositions (which, by definition, is a sequence
of propositions):

If you have an updated password, then you can access the network.
You have an updated password.
Therefore,

You can enter the network.

We would like to determine when this argument is valid. That is, we would like to stop-
From this, the conclusion 'You can enter the network' must be true when the premises 'If
you have an updated password, so you can access the network" and "You have an updated password
"zada" would also be true for both.
Before discussing the validity of this particular argument, let's look at its form.
para representar “Você tem uma senha atualizada” eqpara representar “Você pode entrar na
"network". So, the argument has the form
If p then q

p
∴q
in what∴ it is the symbol to indicate "therefore".
641 / The Fundamentals: Logic and Demonstrations 1-64

We know that sepeqsão are propositional variables, the sentence ((p→q)∧ p) → is a tau-
tology (see Exercise 10(c) in Section 1.2). In particular, when both p → q are true-
We know that it must also be. We say that this is a form of argument.
because whenever all your premises (all the sentences of the argument, except for the last one,
the conclusion) are true, the conclusion must also be. Now suppose that both 'If you
["There is an updated password, so you can log into the network","You have an updated password"]
they are true sentences. When we replace it with 'You have an updated password' and it with
"You can enter the network," necessarily follows that the conclusion "You can enter the network" is
true. This argument is valid because it is in valid form. Note that whenever you replace-
If propositions p → q are true, then q must be true.
What happens when we replace this form of argument with propositions such that
pep→aren't both true? For example, suppose that represents 'You have access'
The expression "You can change your grades" is true, but if p → q is false.
the argument we obtain by substituting these values in a small way from the previous argument is:

If you have access to the network, then you can change your grades.
You have access to the network.
∴ You can change your grades.

The argument obtained is a valid argument, but, as one of the premises, called the first-
the premise is false, we cannot decide if the conclusion is true. (But it seems that this
the conclusion is false.)
In our discussion, to analyze an argument, we substitute the propositions with variables.
propositional. This transforms an argument into a form of argument. We say that the vali-
The validity of an argument follows from the form of the argument. We summarize the terminology used.
I gave to discuss the validity of arguments with our definition of these important notions.

DEFINITION 1 An argument in propositional logic is a sequence of propositions. All, except for the
The last of the propositions is called a premise, and the last is called a conclusion. A
An argument is valid if the truth of the premises implies that the conclusion is true.
A form of argument in propositional logic is the sequence of compound propositions.
that involve propositional variables. One form of argument is valid regardless of
let the propositions be substituted in the propositional variables in their sentences; the conclude-
it is true if all the premises are true.

From the definition of a valid argument form, we see that an argument form with premises
sasp1,p2,p3, ... ,pn and conclusion is valid, when (p1∧ p2∧ ... ∧ pn) → is a tautology.
The key to showing that an argument in propositional logic is valid is to show that
your form of argument is valid. Consequently, we would like to have techniques to mos-
bring what forms of arguments are valid. Now let's develop methods to achieve
this objective.

Rules of Inference for Propositional Logic

We can always use a truth table to show that a form of argument is valid.
We do this by showing that whenever the premises are true, the conclusion must be.
true as well. However, this can be a somewhat tedious way. For example, when
a form of argument involves 10 different propositional variables, using a truth table
To show that this argument is valid requires 2.10= 1,024 different lines. Fortunately, no
1-65 1.5 Rules of Inference 65

we always need to refer to truth tables. Instead, we can establish the validity of
some relatively simple forms of argument, referred to as rules of inference. These
Inference rules can be used as building blocks to construct valid forms of argument.
the most complicated. Let's now introduce the most important of the inference rules in the ló-
propositional logic.
A tautology (p∧ (p→q) → q is based on the inference rule called modus ponens,
or property of detachment. (Modus ponens, in Latin, means a mode that affirms.) This
Tautology leads us to the following valid form of argument, which has already been seen in our discussion.
about arguments (in which, as before, the∴ it is the symbol to indicate "therefore":

p
p implies q

∴q

Using this notation, the hypotheses are written in columns, followed by a horizontal line,
followed by a line that starts with the symbol 'therefore' and ends with the conclusion. In
Specifically, modus ponens tells us that if a conditional sentence and the hypothesis of that sentence are true.
If the conditionals are true, then the conclusion must also be true. Example 1 illustrates
the use of modus ponens.

EXAMPLE 1Suppose the conditional sentence "If it snows today, then I will go skiing" and its hypothesis "It is
"It's snowing today" is true. So, by modus ponens, it follows that the conclusion of the conditional.
"I will ski" is true. ◄

As mentioned earlier, a valid argument can lead us to an incorrect conclusion.

It means that one or more of your premises are false. We illustrate this again in Example 2.

EXAMPLE 2Determine if the argument given here is valid and if its conclusion must be true solely by
validity of the argument.

2 3 2We 3
Se2> so 3
2 ( 2)(2)> know that 2> . 2 Consequently,
2 3 2
( 2) = 2> (2) = . 94 ”
3 2
Solution: Let p be the proposition 2>" 32 the equation proposal2> ( 2 ) . The premises of the argument-
if p then q, this is the conclusion. This argument is valid, as it is built according to
modus ponens, a valid form of argument. However, one of its premises, 2> , 32 é
false. Consequently, we cannot deduce that the conclusion is true. In this case,
we note that the conclusion is false, because< . 9 ◄
4

Table 1 lists the most important rules of inference for propositional logic. The
exercises 9, 10, 15, and 30 in Section 1.2 ask for verifications that these inference rules are
valid forms of argument. Now we will give examples of arguments that use these rules of
inference. In each argument, we will first use propositional variables to express the
propositions in the argument. Then, we will show that the resulting form of the argument is a re-
table 1.

EXAMPLE 3Say which rule of inference is the basis of the following argument: 'It is getting colder now. Therefore,
Is it getting cold or is it raining now?
661 / The Foundations: Logic and Demonstrations 1-66

TABLE 1 Rules of Inference.

Rule of Inference Tautology Name
p [p∧ (p→q)] →q Modus ponens
p implies q

∴q
Mode of denying the consequent
ÿ q [ÿ q ∧ (p→q)] →ÿ p
if p then q

∴ÿ p
If p, then q Hypothetical syllogism
(p implies q)∧ (q→r) → (p→r)
q→r
∴ p implies r

p∨q [(p∨ q)∧ ÿ p implies q Disjunctive syllogism

ÿ p
∴q
p p→ (p∨ q) Addition
∴ p∨ q

p∧ q (p∧ q) → p Simplification
∴p
p (p)∧ (q)] → (p∧ q) Conjunction
q
∴p∧q

p∨ q [(p∨ q)∧ (ÿ p∨ r)] → (q∨ r) Resolution

ÿ p∨ r
∴q∨r

Solution: Let proposition 'It is getting cold now' and the proposition 'It is raining now'.
So this argument is of the form

p
∴ p∨ q

This is an argument that uses the rule of addition. ◄

EXAMPLE 4Say which rule of inference is the basis of the following argument: 'It is getting colder and raining now.'
Therefore, it is getting cold now.

Solution: Take the proposition "It is getting cold now" and the proposition "It is raining now".
So, this argument is in the form of

p∧q
∴p

This is an argument that uses the rule of simplification. ◄

1-67 1.5 Rules of Inference 67

EXAMPLE 5Say which rule of inference is the basis of the following argument:

If it rains, then there will be no barbecue today. If there is no barbecue today, there will be one tomorrow.
So, if it rains today, then there will be a barbecue tomorrow.

Solution: If the proposition "It is raining today," the proposition "There will not be a barbecue today" and
The proposition 'There will be a barbecue tomorrow.' So this argument is in the form of

If p then q

q→r
∴ if p then r

Therefore, this argument is a hypothetical syllogism. ◄

Usando Regras de Inferência para Construir Argumentos

When there are many premises, many rules of inference are often necessary.
to show that an argument is valid. This is illustrated in examples 6 and 7, where the steps of
arguments are arranged in separate lines, with the reason for each step explicitly outlined
each side. These examples also show how arguments in Portuguese can be ana-
derived through inference rules.

EXAMPLE 6Show that the hypotheses "It is not sunny this afternoon and it is colder than yesterday," "Let's
"swimming if it's sunny", "If we don't go swimming, then let's go for a boat ride" and
If we take a boat trip, then we will be home by nightfall.
We will be home by nightfall.

Examples Solution: If the proposition 'It is sunny this afternoon' is true, then the proposition 'It is colder than...'
Extras the proposition 'Let's swim', the proposition 'Let's go for a boat ride' and the pro-
position 'We will be home by nightfall.' So, the hypotheses becomeÿ p∧ q,r→p,ÿ r→s
the conclusion is simply.
We built an argument to show that our hypotheses lead us to the conclusion as
there follows.

Step Reason
1. ÿ p∧ q Hypothesis
2.ÿ p Simplification using (1)
3. r → p Hypothesis
4.ÿ r Modus tollens using (2) and (3)
5.ÿ r→s Hypothesis
6.s Modus ponens using (4) and (5)
7.s→t Hypothesis
8.t Modus ponens using (6) and (7)

Note that we could have used a truth table to show that, whenever the hypotheses...
if these premises are true, then the conclusion will also be true. However, as we are working with
five propositional variables (p,q,r,set), this table would have 32 rows. ◄

EXAMPLE 7Show that the hypotheses "If you send me an email, then I will finish the program"
If you don't send me an email, then I will go to sleep early and if I sleep early, then
681 / The Fundamentals: Logic and Proofs 1-68

I will wake up feeling good leads us to the conclusion If I do not finish the program, then I
I will wake up feeling good.

Solution: If you send me an email, I will finish the proposal.

grama," the proposition "I will sleep early" and the proposition "I will wake up feeling good".
So the hypotheses are p→q,ÿ p→rer→s. The desired conclusion isÿ q→s. We have to give
a valid argument with the hypotheses p→q,ÿ to reach a conclusionÿ q→s.
This form of argument shows that the hypotheses lead us to the desired conclusion.

Step Reason
1.p implies q Hypothesis
2.ÿ q→ÿ p Contrapositive of (1)
3.ÿ p→r Hypothesis
4.ÿ q→r Hypothetical syllogism using (2) and (3)
5.r→s Hypothesis
6.ÿ q→s Hypothetical syllogism using (4) and (5) ◄

Resolution
Computer programs have been developed to automate the task of reasoning and for-
necessary theorems. Many of these programs make use of the inference rule known as
solution. This rule of inference is based on the tautology
Links
((p∨ q)∧ (ÿ p∨ r)) → (q∨ r).

(The verification that this sentence is a tautology was requested in Exercise 30 in Section 1.2.) A
final disjunction of the rule, q∨
r, is called a solvent. Whenq= RNA tautology, we obtain
(p∨ q)∧ (ÿ p ∨ q) → q. In addition, when= F, we obtain(p∨ q)∧ (ÿ p) →q(becauseq∨ F≡ q),
what is the tautology on which the rule of disjunctive syllogism is based.

EXAMPLE 8Use the resolution to show that the hypotheses 'Jasmine is skiing or it is not snowing' and
It's snowing or José is playing soccer implies that Jasmim is skiing or José is
playing soccer.

Solution: If the proposition "It is snowing" is true, the proposition "Jasmine is skiing" is also true.
Examples Proposition 'José is playing soccer'. We can represent the hypotheses byÿ p∨ qep∨ r
Extras respectively. Using resolution, the proposition q∨ Jasmim is skiing or José is
"playing football" can be concluded. ◄

Resolution plays an important role in programming languages based on

rules of logic, such as Prolog (where the resolution rules for quantified sentences are applied
It can also be used to build systems that provide automated theorems.
mind. To construct demonstrations in propositional logic using resolution as the only
inference rule, the hypotheses and the conclusion must be expressed as clauses, in which one
A clause is a disjunction of variables or the negations of these variables. We can replace one
a propositional logic sentence that is not a clause by one or more equivalent sentences
these are clauses. For example, suppose we have a sentence of the form∨ (q∧ r).
Comop∨ (q∧ r)≡ (p∨ q)∧ (p∨ r), we can replace the sentence p∨ (q∧ r) for two sentences
1-69 1.5 Rules of Inference 69

p∨ qep∨ r, each of them being a clause. We can replace a sentence of the form
ÿ (p∨ q) for two sentencesÿ peÿ because De Morgan's law tells us thatÿ (p∨ q)≡ ÿ p
∧ ÿ We can also replace a conditional sentence p→q with the equivalent disjunction.
youÿ p∨ q.

EXAMPLE 9Show that the hypotheses (p∧ q)∨ as simple conclusion∨ s.

Solution: We can rewrite the hypothesis (p∧ q)∨ like two clauses, p∨ request∨ r. We can
also replace with the equivalent clauseÿ r∨ s. Using the two clauses∨ reÿ r∨ s,
we can use a resolution to conclude∨ r. ◄

Fallacies
Many common fallacies appear in incorrect arguments. These fallacies resemble
rules of inference, but they are based on contingencies rather than tautologies. This will be discussed
here to show the distinction between correct reasoning and incorrect reasoning.
The proposition [(p→q)∧ q] →p is not a tautology, as it is false when p is false and q is.
true. However, there are many incorrect arguments that treat this as a tautology.
Links logic. In other words, they treat the argument with premises p → q and conclusion p as
a valid form of argument, and it is not. This type of incorrect reasoning is called defalation
the affirmation of the conclusion.

EXAMPLE 10Is the following argument valid?

If you do all the exercises in this book, then you will have learned discrete mathematics.
learned discrete mathematics.

Portanto, você fez todos os exercícios deste livro.

Solution: Let p be the proposition "You did all the exercises in this book." Let q be the proposition
"You learned discrete mathematics." So this argument is in the form: sep→qeq, then p.
This is an example of an incorrect argument that uses the fallacy of affirming the consequent. Because
Is it possible for you to learn discrete mathematics differently without having to do all the exercises?
exercises from this book. (You can learn discrete mathematics by reading, watching lectures, doing
many, but not all exercises and so on. ◄

The proposition [(p→q)∧ ÿ p] →ÿ it is not a tautology, because it is false when it is false and it is
true. Many arguments use this incorrectly as if it were a rule of inference.
This type of incorrect reasoning is called deflation of the denial of hypotheses.

EXAMPLE 11Let's take the propositions from Example 10. If the conditional sentence p → q is true, and
ÿ true foot, it is correct to conclude thatÿ what is true? In other words, is it correct to ...
to sum up that you do not learn discrete mathematics if you do not do all the exercises of
book, assuming that if you solve all the problems in the book, then you will have learned
discrete mathematics?

Solution: It is possible for you to learn discrete mathematics even if you do not do all the
Exercises from the book. This incorrect argument is in the form p → q e.ÿ pimplicaÿ what is a
example of the fallacy of denying the hypotheses. ◄
701 / The Fundamentals: Logic and Demonstrations 1-70

Rules of Inference for Quantified Sentences

We discussed inference rules for propositions. Now we will describe some imposed rules.
inference rules for sentences involving quantifiers. These inference rules are
extensively used in mathematical arguments, often without explicit mention.
Universal instantiation is the rule of inference used to conclude that P(c) is true in
it is a particular element of the domain, when the premise is given∀xP(x). The instantiation
universal is used when we conclude from the sentence 'All women are discreet' that 'Maria
"is discreet", in which Maria is an element of the realm of women.
Universal generalization is the rule of inference that states that∀xP(x) is true, given as
premise that P(c) is true for all elements of the domain. The universal generalization
is used when we show that∀xP(x) is true taking an arbitrary element from the domain.
neither and showing that P(c) is true. The element we selected must be an element of
arbitrary domain, not a specific one. That is, when we conclude from∀xP(x) the existence of
In a elemental domain, we have control over the over cannot make any other conclusion.
they are about things that do not belong to the domain. Universal generalization is used implicitly.
in many demonstrations and is rarely mentioned explicitly. However, the mistake of doing
conclusions without guarantee about an arbitrary element when universal generalization is used
it is also common in incorrect reasoning.
Existential instantiation is the rule that allows us to conclude that there exists an element in the.
the domain for which P(c) is true if we know that∃xP(x) is true. We cannot select-
to assign an arbitrary value here, but it must be one for which P(c) is true. Usually-
We have no knowledge about quelconque, only that it exists. Since it exists, we can...
give a name (c) and continue our argument.
Existential generalization is the rule of inference used to conclude that∃xP(x) is true-
there is when a particular element with P(c) true is known. In other words, if we know a
elementary domain for which P(c) is true, then we know that∃xP(x) is true.
We summarize these inference rules in Table 2. Let's illustrate how one of these rules works.
inference for quantified sentences is used in Example 12.

EXAMPLE 12Show that the premises "All students in the discrete mathematics class are taking a course
of computer science" and "Maria is a student of that class" implies the conclusion "Maria
is attending a computer science course.

TABLE 2 Rules of Inference for Quantified Sentences.

Rule of Inference Name

∀xP(x)
Universal instantiation
∴ P(c)

P(c) for an arbitrary

Universal generalization
∴ ∀xP(x)

∃xP(x)
Existential instantiation
∴ P(c) for some element c

P(c) for some element c

Existential generalization
∴ ∃xP(x)
1-71 1.5 Rules of Inference 71

Solution: Let D(x) be the statement "x is in the discrete math class" and let C(x) be the statement "x
is attending a computer science course.” So, the premises are∀F o r a l l x , i f D ( x ) t h e n C ( x )
eD(Maria). And the conclusion is C(Maria).
Examples The following steps can be used to reach a conclusion from the premises.
Extras
step Reason
1.∀F o r a l l x , i f D ( x ) t hPremise
en C(x)
2.D(Maria)→C(Maria) Universal Instantiation of (1)
3.D(Maria) Premise
4.C(Maria) Modus ponens starting from (2) and (3) ◄
EXAMPLE 13Show that the premises 'A student from this class has not read the book' and 'Everyone in this class'
passing the first exam implies the conclusion 'Someone passed the first exam without having'
I read the book.
Solution: Let C(x) be the sentence 'x is in this class', B(x) be the sentence 'x has not read the book' and
P(x) is the statement 'x passed the first exam'. The premises are∃x(C(x)∧ÿ B ( x ) ) a n d ∀x ( C ( x ) →
P ( x ) ) . T h e c o n c l u s i o n i s ∃x ( P ( x ) ∧ÿ B(x)). These steps can be used to establish the
conclusão a partir das premissas.
Step Reason
1. ∃x ( C ( x ) ∧ÿ B ( x ) ) Premise
2.C(a)∧ ÿ B ( a ) Existential instantiation from (1)
3.C(a) Simplification from (2)
4. ∀For all x, if C of x then PPremise of x.
5.C(a) →P(a) Universal instantiation from (4)
6.P(a) Modus ponens derives (3) and (5)
7.ÿ B ( a ) Simplification from (2)
8.P(a)∧ÿ B ( a ) Conjunction from (6) and (7)
9.∃x ( P ( x ) ∧ÿ B ( x ) ) Existential generalization from (8) ◄

Combining Rules of Inference for Propositions

Quantified Sentences
We developed inference rules for propositions and for quantified sentences. Note that
In our arguments in examples 12 and 13, we used both universal instantiation, a rule of
inference for quantified sentences, quantomodus ponens, a rule of inference for the
propositional logic. We will often need to use this combination of inference rules.
Hi. As universal instantiation and modus ponens are often used together, this combo-
The rule of rules is commonly referred to as universal modus ponens. This rule tells us that
if∀x(P(x) → Q(x)) is true, and if P(a) is true for some particular element.
the domain of the universal quantifier, then Q(a) must be true. To see this, note that, by
Universal instantiation, P(a) → Q(a) is true. Then, by modus ponens, Q(a) must also be true.
to be true. We can describe the universal modus ponens as follows:

∀For all x, if P(x) then Q(x)

P(a), where a is a particular element of the domain
∴ Q(a)

Universal modus ponens is commonly used in mathematical arguments. This is illustrated

in Example 14.

EXAMPLE 14Assume that "For every positive integer n, if n is greater than 4, then"2less than 2nIt's true-
Use universal modus ponens to show that 1002<2100.
721 / The Fundamentals: Logic and Demonstrations 1-72

Solution: Let P(n) be the statement "n > 4" and Q(n) be the statement "n2<2n. The sentence "For all integers-
or positive, if greater than 4, then2less than 2ncan be represented by∀n(P(n) →
Q ( n ) ) , w h e r e t h e d o m a i n c o n s i s t s o f a l l p o s i t i v e i n t e g e r s . We a r e a s s u m i n g t h a t ∀n ( P ( n )
→Q(n)) is true. Note that P(100) is true, since 100>4. Then it follows by modus po-
nensuniversal queQ(n) is true, explicitly 1002<2100. ◄

Another combination frequently used of inference rule for logic with an inference rule
The reference for quantified sentences is the universal modus tollens. Universal modus tollens combines
The universal instantiation and modus tollens can be expressed as:

∀for all x, if P of x then Q of x

ÿ Q(a), where a is a particular element in the domain.
∴ ÿ P(a)

We leave the verification of the universal modus tollens to the reader (see Exercise 25).
Exercise 26 develops additional combinations of inference rules in propositional logic.
the quantified sentences.

Exercises
1. Find the form of argument for the given argument and It's either hotter than 100 degrees today or the pollution is
determine if it is valid. We can infer that the conclusion is dangerous. It's less than 100 degrees outside today. That's why,
true if the premises are true? pollution is dangerous.
If Socrates is human, then Socrates is mortal. c) Linda is an excellent swimmer. If Linda is a
Socrates is human. excellent swimmer, so she can work as
lifeguard. That's why Linda can work as a lifeguard.
∴ Socrates is mortal.
lives.
2. Find the form of argument for the given argument and
Steve will work in a computer industry
determine if it is valid. We can infer that the conclusion is
this summer. Therefore, this summer he will work on a
true if the premises are true?
computer industry or he will be unemployed
If George does not have eight legs, then he is not an on the beach.
insect.
e) If I work all night on this homework task, then
George is an insect. I can solve all the exercises. If I solve all
∴ George has eight legs. the exercises, I will understand the material. Therefore, if I
3. What is the rule of inference used in each of the arguments? work at night on this task, then I will understand the
below? material.
a) Alice has a degree in mathematics. Therefore, Alice is 5. Use the rules of inference to show that the hypotheses
graduated either in mathematics or in computer science Randy works hard
tation. he is a stupid boy” and “If Randy is a stupid boy,
b) Jerry is a graduate in mathematics and in science of
then he will not get the job" implies the conclusion
Randy will not get the job.
computing. That’s why Jerry is a graduate in math-
mathematics. 6. Use the rules of inference to show that the hypotheses
If it doesn't rain or there is no fog, then the competition of
If the day is rainy, then the pool will be closed.
it will happen and the rescue presentation will continue,
The day is rainy. That's why the pool is closed.
If the sailing competition is held, then the trophy will be
d) If it snows today, the university will be closed. "conquered" and "The trophy was not conquered" imply the
The city is not closed today. That's why it didn't snow today. Conclusion: "It rained."
If I go swimming, then I will stay in the sun for a long7. time.
What rules of inference are used in the famous argument?
If I stay in the sun for too long, then I get burned. below mentioned?
king. That's why, if I go swimming, I will get burned.
All men are mortal. Socrates is a man. For
4. What is the inference rule used in each of the Yes, arguments?
Socrates is mortal.
mentos to follow?
8. What are the inference rules used in the argument?
a) Kangaroos live in Australia and are marsupials. Therefore, below? "No man is an island. Manhattan is a
kangaroos are marsupials. island. That's why Manhattan is not a man.
1-73 1.5 Rules of Inference 73

9. For each group of premises below, what conclusion or Java programs can secure a job quite re-
Are relevant conclusions to be drawn? Explain them. rewarded. Therefore, someone in this room may be able to
inference rules used to obtain each conclusion a well-paid job.
the premises. b) "Someone in this room likes to see whales. Every person
If I take a day off, it rains or snows. I took those who enjoy watching whales care about pollution
day off on Tuesday or Thursday." "It was sunny on the no sea. That’s why there is a person in the room who cares.
["Tuesday.","It didn't snow on Thursday."] with marine pollution.
b) "If I eat spicy food, then I have Each of the 93 students in this class has their own
strange dreams." "I have strange dreams when own computer. Everyone who has their own
"a thunder struck while I sleep." "I did not have computers can use a processing program
strange dreams. word ment. That's why, Zeke, a student of
"I am either smart or lucky." "I am not lucky." room, you can use a processing program.
If I were lucky, then I would win the lottery. Everyone in New Jersey lives 50 miles from the ocean.
Every graduate in computer science has their Someone who lives in New Jersey has never seen the ocean.
"Ralph does not have his own computer." no. That's why someone who lives 50 miles from the ocean
computer." "Ana has her own computer." never saw him.
e) "What is good for corporations is good for the 14. For each argument below, indicate which rules of
State"
for the United States.” “What is good for the United States is inference was used at each step.
good for you." "What is good for corporations is Linda, a student from this classroom, has a convertible.
you buy a lot of things. red. Everyone who has a red convertible
f) "All rodents gnaw their own food." "Rats I have at least one speeding ticket.
they are rodents." "Rabbits do not gnaw their food." "Mor- So, someone in this room has a fine for
blind people are not rodents. speeding.
10. For each group of premises below, what conclusion or b) "Each of the five roommates, Melissa, Aaron,
Can relevant conclusions be drawn? Explain. Ralph, Veneesha, and Keeshawn attended a course in
rules of inference used to obtain each conclusion discrete mathematics. Every student who attended a
the premises. discretemathematicscoursecanattendacourseof
If I play hockey, then I get sore the next day algorithm. That's why all five roommates po-
next." "I use the hydro massage if I am to attend an algorithm course next year.
sore. I didn't use the hot tub. All the films produced by John Sayles are
b) "If I work, the day is sunny, total or even- wonderful. John Sayles produced a film about
especially." "I worked last Monday or mineral coal miners. That's why there is a film
I worked last Friday. The day was not... wonderful about coal miners.
"Sunny on Tuesday." "It was partly cloudy." d) "Is there anyone in this room who has been to France? Everyone who goes
released on Friday. In France, they visit the Louvre. That's why someone in this room
c) "All insects have six legs." "Dragonflies are visited the Louvre.
insects." "Spiders do not have six legs." "Spiders [Link] if each of the arguments below is correct or
eat dragonflies. incorrect and explain why.
Every student has an Internet account. All the students in this room understand logic.
There is no Internet account." "Maggie has a Xavier is a student in this classroom. Therefore, Xavier
Internet bill. understand logic.
All foods that are healthy do not have a Every graduate in computer science does
good taste." "Tofu is a healthy food." "You discrete mathematics. Natasha is doing math.
eat only what tastes good." "You don't eat discrete. That's why Natasha is an undergraduate in science
tofu. Cheeseburgers are not healthy foods. in computing.
I'm asleep or having hallucinations. I'm not c) "All parrots like fruits. My little bird
I am sleeping.” “If I am having hallucinations, I The pet is not a parrot. That's why my
I see elephants running on the road. The pet bird does not like fruits.
11. Show that the argument with the premises1, p2, . . . , pn Everyone who eats granola every day is healthy.
and the conclusion is valid if the argument with the Linda is not healthy. That's why Linda doesn't eat granola.
premises1, p2, . . . , pn that the conclusion is valid. every day.
[Link] that the argument with the premises (p∧ t) → (r∨ s),16. Determine whether each of the arguments below is correct or not.
q→ (u∧ t),u→p, eÿ If the conclusion is valid, incorrect and explain why.
using Exercise 11 and then using the rules of Everyone who is enrolled at the university lives
inference from Table 1. in a dormitory. Mia has never lived in a dormitory.
13. For each of the following arguments, identify which rules of That’s why Mia is not enrolled in university.
inference was used at each step. A convertible car is nice to drive. The car of
a) "Doug, a student in this class, knows how to write" Isaac is not a convertible. That's why Isaac's car
programs in Java. All who know how to write is not good at driving.
741 / The Fundamentals: Logic and Demonstrations 1-74

Quincy likes all action movies. 25. Justify the universal rule of modus tollens by showing
what are the premises∀For all x, if P(x) then Q(x)ÿ Q ( a ) f o r a
I like the movie Eight Men Out. That's why, Eight Men Out.
It's an action movie. particular element in the domain impliesÿ P(a).
d) "All men who fish for lobsters set up for 26. Justify the rule of universal transitivity, which states
less than a dozen traps. Hamilton is a what is∀For all x, if P(x) then Q(x)∀x(Q(x) → R(x)) are true,
lobster fisherman. That's why Hamilton sets up for so∀x(P(x) → R(x)) is true, in which the domains
less than a dozen traps. of all the quantifiers are the same.
17. What is wrong with this argument? Consider H(x) as 27. Use the rules of inference to show that if∀x ( P ( x ) →
"tear happy". Given the premise∃xH(x), we conclude that (Q(x)∧ S ( x ) ) ) e ∀x ( P ( x ) ∧ If R(x)) are true, then
H(Lola). Por isso, Lola é feliz. ∀x ( R ( x ) ∧ S(x)) is true.
18. What is wrong with this argument? Consider S(x, y) 28. Use the rules of inference to show that if∀x ( P ( x ) ∨
as "xé lower than y". Given the premise∃sS(s, Q ( x ) ) e ∀x ( ÿ P ( x ) ∧ I f Q ( x ) → R ( x ) a r e t r u e ,
Max), follows that S(Max, Max). Then, by generalization so∀x(ÿ R(x) → P(x) is also true, where the
existential, we have to∃xS(x, x), that is, someone is more The domains of all the quantifiers are the same.
below oneself. 29. Use the rules of inference to show that if∀x ( P ( x ) ∨
19. Determine if each of the arguments below is valid. If Q ( x ) ) , ∀x ( ÿ Q ( x ) ∨ S ( x ) ) , ∀x ( R ( x ) → ÿ S ( x ) ) , e ∃xÿ P ( x )
if an argument is correct, what rule of inference was used they are true, then∃xÿ R(x) is true.
used? If not, what logical errors were made? 30. Use the resolution to show that the hypotheses 'Allen is a'
a) Let x be a real number, such that x > 1, then2>1. bad boy or Hillary is a good girl" and "Allen is a
Assume that2Then good boy or David is happy" implies the conclusion "Hillary
b) If n is a real number with n > 3, then 9. 2 is she a good girl or is David happy.
2
Suppose that ≤ 9. Then ≤ 3. 31. Use resolution to show that the hypotheses 'It is not
c) If n is a real number with n > 2, then24. raining or Ivete has her little umbrella," "Ivete doesn't have one
Suppose that n ≤ 2. Then n2≤ 4. umbrella or she doesn't want to get wet" and "It's raining or
"Ivete does not get wet" implies that "Ivete does not get wet".
20. Determine if the arguments below are valid.
32. Show that the equivalence holds∧ ÿ p ≡ It can be derived
a) If x is a positive real number, then x2it is a number
using resolution along with the fact that a proposition
real positive. Therefore, be2it's positive, in which it is a
A conditional with a false hypothesis is true. [Tip:
real number, then it is a positive real number.
Consider= r= Make a resolution.
b) Sex2 0, in which a real number, then x 0. Con-
33. Use the resolution to show that a proposition
sidereal as a real number like2 0; so 0.
composed (p∨ q)∧ (ÿ p∨ q)∧ (p∨ ÿ q)∧ (ÿ p∨ÿ no
21. What inference rules were used to establish is satisfactory.
the conclusion of the argument by Lewis Carroll described in
*34. The Logic Problem, taken from the FBF Exam, The Game of
Exemplo 26 da Seção 1.3?
Logic has these two assumptions:
22. Which inference rules were used to establish
Logic is hard or not many students like it
the conclusion of the argument by Lewis Carroll described in
of logic.
Example 27 of Section 1.3?
If mathematics is easy, then logic is not difficult.
23. Identify the error(s) in this argument that supposedly
Transcribing these assumptions into propositions that en-
show that if∃xP(x)∧ ∃xQ(x) is true, then
return propositional variables and logical connectives, of-
∃x ( P ( x ) ∧ Q(x) is true.
determine whether each of the following conclusions is valid
1. ∃xP(x)∧ ∃x Q ( x ) Premise
for the assumptions:
2.∃xP(x) Simplification of (1) a) Mathematics is not easy, if many students like it
3.P(c) Existential Instantiation of (2) of logic.
4. ∃x Q(x) Simplification of (1) b) Few students like logic, if mathematics
5.Q(c) Existential Instantiation of (4) it's not easy.
6.P(c)∧ Q ( c ) Conjunction of (3) and (5) c) Mathematics is not easy or logic is difficult.
7.∃x(P(x)∧ Q(x)) Existential Generalization d) Logic is not difficult or math is not easy.
24. Identify the error(s) in this argument that supposedly If few students like logic, then math
show(s) that if∀x ( P ( x ) ∨ If Q(x) is true, then it is not easy or logic is not difficult.
∀xP(x)∨ ∀ x Q(x) is true. *35. Determine if this argument, taken from Kalish and Montague
1. ∀xP(x)∨ Q(x)) Premise [KaMo64], it is valid.
2.P(c)∨ Q(c) Universal instantiation of (1) SeoSuper-Homem is capable and eager to fight.
3.P(c) Simplification of (2) Oh bad, he would be benevolent. If Superman wouldn't
4.∀xP(x) Universal generalization of (3) if he were capable of fighting evil, he would be powerless; if
5.Q(c) Simplification of (2) if he did not have the will to combat evil, he would be
malevolent. Superman does not fight evil. If the
6.∀xQ(x) Universal generalization of (5)
Superman exists, he is either impotent or malevolent.
7.∀x(P(x)∨ ∀Conjunction of (4) and (6) That's why Superman does not exist.