6 Methods of Proofs-1

UNIVERSITY OF SANTO TOMAS
INSTITUTE OF INFORMATION AND COMPUTING SCIENCES
METHODS OF PROOFS
LECTURE BY:
MS. CHERRY ROSE ESTABILLO
CS201 - CRRESTABILLO
PROOFS (in Mathematics) are valid

arguments that establish the
truth of mathematical statement.
ARGUMENT is a sequence of
statements that end with a
conclusion.
VALID conclusion must follow from the

truth of the preceding statements (or
PREMISES).
An argument p ,p,, q is called

logically valid if (p p p ) q
is a tautology.
Consider the argument:
If John gets 100% in Quiz 3, then John

is goodlooking. John gets 100% in all
Quiz 3. Therefore, John is
goodlooking.
What if we say?
If John gets 100% in Quiz 3, then John

is goodlooking. Jed is goodlooking.
Therefore, John gets 100% in Quiz 3.
RULES OF INFERENCE is a template for

constructing arguments and used as
a basic tool for establishing the truth
values.
RULES OF INFERENCE
RULE OF INFERENCE TAUTOLOGY NAME
p Modus Ponens
pq [p(pq)] q (Rule of Detachment)
q
q Modus Tollens
pq [q(pq)] p (Method of Denying)
p
pq Hypothetical
qr [(pq)(qr)] (pr) Syllogism
pr
pq Disjunctive
p [(pq) p] q Syllogism
q
p Addition
pq p(pq)
pq Simplification
p (pq)p
pr [(pr)(qr)][(pq) r]
Rule for Proof
qr by Cases
(pq) r
p Conjunction
q [(p) (q)] pq
pq
pq Resolution
pr [(pq)(pr)](qr)
qr
pq Absorption
p(pq) (pq) [p(pq)]
(pq)(rs) {[(pq)(rs)] Constructive

pr (pr)} (qs) Dilemma
(qs)
State which rule of inference is used in the argument.
(1) She is bored and he is excited. Therefore, she

is bored.
(2) The sky is blue. Therefore, the sky is blue or it
is black.
(3) I love mangoes. I love pineapple. Therefore, I
love mangoes and pineapple.
(4) The ant is very hungry. If the ant is very
hungry, it will eat an elephant. Therefore, the
ant will eat an elephant.
(4) If a strong earthquake hits Metro Manila, SM

Megamall will collapse. SM Megamall is still
standing. Therefore, a strong earthquake has not hit
Metro Manila.
(5) The pig is hiding whether in Agnes office or in
Elvies room. The pig is not in Agnes room.
Therefore, it is in Elvies room.
(6) If he gives her roses, he will win her heart. If he
carries her book, he will win her heart. Therefore,
he will win her heart if he either gives her roses or
carries her book.
FORMAL PROOFS OF VALIDITY

Let {Pi} i+ be an argument with
premises and Q be the conclusion,
then a formal proof of validity of
argument consists of lists of
propositions which terminates Q,
i.e.
P1P2PnQ.
Every proposition Pi must satisfy the at least one

of the ff:
(1) Pi is a PREMISE of an argument;
(2) Pi can be derived from at least one of the
propositions already in the list using one of
the rules of inference;
(3) Pi is equivalent to a proposition already
included in the list since one of the
replacement rules guarantees the logical
equivalence of the appropriate underlying
propositional functions.
Prove the ff. arguments using the rule

of inference.
(1) Two is an integer. If 2 is an integer then
4 is an element of real no. Two is an
even no. or 4 is a composite no. If 4 is a
composite no. then 4 is not an element
of real no. Therefore, 2 is an even no. or
2 is a prime no.
(2) If I get my Christmas bonus and my

friends are free, I will take a road trip
with my friends. If my friends don't find
a job after Christmas, then they will be
free. I got my Christmas bonus . My
friends did not find a job after
Christmas. Therefore, I will take a road
trip with my friends.
Write formal proofs of the validity of each of

the following arguments
1.) I shall either play COC or I shall go to a mall
and watch a movie. Therefore I shall either
play COC or go to a mall.
2.) If the summer is hot then we wont go on
vacation in May. Well either go on vacation
in May or well buy a boat (perhaps both).
Therefore, if the summer is hot, well buy a
boat.

the following arguments
3.) People are happy if and only if they are
compassionate. Nobody is both happy and
compassionate. Hence people are both
unhappy and uncompassionate.
4.) If roses are red and violets are blue then
candy is sweet and I love you. Violets are
blue and roses are red. Therefore, I love you.

the following arguments.
5.) Either the project wasnt a success or he
didnt do the feasibility study or both. If he
is sensible then he did the feasibility study.
The project was a success. If he wasnt
sensible and he didnt do the feasibility
study, then he failed. Therefore he failed.
Write a formal proof using rules of

inference:
If it does not rain or 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. The trophy was not awarded.
Therefore, it rained.
State the rules of inference used in each of

these arguments.
1.) Kangaroos live in Australia and are
marsupials. Therefore, kangaroos are
marsupials.
2.) 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.

these arguments.
3.) 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.
4.) 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.

these arguments.
5.) If I work all night on this homework, then I
can answer all exercises. If I answer all
exercises, I will understand the material.
Therefore, if I work all night on this
homework, then I will understand the
material.
6.) No man is an island. Manila is an island.
Therefore, Manila is not a man.
For each of these sets of premises, what

relevant conclusions can be drawn.
1.) If I play hockey, then I am sore the next
day. I use the whirlpool if I am sore. I did
not use the whirlpool.

6 Methods of Proofs-1

Uploaded by

Copyright:

Available Formats

6 Methods of Proofs-1

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

6 Methods of Proofs-1

Uploaded by

Copyright:

Available Formats

UNIVERSITY OF SANTO TOMAS

INSTITUTE OF INFORMATION AND COMPUTING SCIENCES

PROOFS (in Mathematics) are valid

VALID conclusion must follow from the

An argument p ,p,, q is called

Consider the argument:

If John gets 100% in Quiz 3, then John

If John gets 100% in Quiz 3, then John

RULES OF INFERENCE is a template for

(pq)(rs) {[(pq)(rs)] Constructive

State which rule of inference is used in the argument.

(1) She is bored and he is excited. Therefore, she

(4) If a strong earthquake hits Metro Manila, SM

FORMAL PROOFS OF VALIDITY

Every proposition Pi must satisfy the at least one

Prove the ff. arguments using the rule

(2) If I get my Christmas bonus and my

Write formal proofs of the validity of each of

Write formal proofs of the validity of each of

Write formal proofs of the validity of each of

Write a formal proof using rules of

State the rules of inference used in each of

State the rules of inference used in each of

State the rules of inference used in each of

For each of these sets of premises, what

You might also like