per3 pembuktian

Let’s proceed to…Let’s proceed to…

Mathematical ReasoningMathematical Reasoning

Mathematical ReasoningMathematical Reasoning

We need We need mathematical reasoningmathematical reasoning to to• determine whether a mathematical argument is determine whether a mathematical argument is correct or incorrect and correct or incorrect and• construct mathematical arguments.construct mathematical arguments.

Mathematical reasoning is not only important for Mathematical reasoning is not only important for conducting conducting proofsproofs and and program verificationprogram verification, but , but also for also for artificial intelligenceartificial intelligence systems (drawing systems (drawing inferences).inferences).

TerminologyTerminologyAn An axiomaxiom is a basic assumption about mathematical is a basic assumption about mathematical structured that needs no proof.structured that needs no proof.

We can use a We can use a proofproof to demonstrate that a particular to demonstrate that a particular statement is true. A proof consists of a sequence of statement is true. A proof consists of a sequence of statements that form an argument.statements that form an argument.

The steps that connect the statements in such a The steps that connect the statements in such a sequence are the sequence are the rules of inferencerules of inference..Cases of incorrect reasoning are called Cases of incorrect reasoning are called fallaciesfallacies..

A A theoremtheorem is a statement that can be shown to be is a statement that can be shown to be true. true.

TerminologyTerminology

A A lemmalemma is a simple theorem used as an is a simple theorem used as an intermediate result in the proof of another theorem.intermediate result in the proof of another theorem.

A A corollarycorollary is a proposition that follows directly from is a proposition that follows directly from a theorem that has been proved.a theorem that has been proved.

A A conjectureconjecture is a statement whose truth value is is a statement whose truth value is unknown. Once it is proven, it becomes a theorem.unknown. Once it is proven, it becomes a theorem.

Rules of InferenceRules of Inference

Rules of inferenceRules of inference provide the justification of the provide the justification of the steps used in a proof.steps used in a proof.

One important rule is called One important rule is called modus ponensmodus ponens or the or the law of detachmentlaw of detachment. It is based on the tautology . It is based on the tautology (p(p(p(pq)) q)) q. We write it in the following way: q. We write it in the following way:

ppp p q q________ qq

The two The two hypotheseshypotheses p and p p and p q are q are written in a column, and the written in a column, and the conclusionconclusionbelow a bar, where below a bar, where means “therefore”. means “therefore”.


The general form of a rule of inference is:The general form of a rule of inference is:

pp11

pp22 .. .. .. ppnn________ qq

The rule states that if pThe rule states that if p11 andand p p22 andand … … andand ppnn are all true, then q is true as well. are all true, then q is true as well.

These rules of inference can be used in These rules of inference can be used in any mathematical argument and do not any mathematical argument and do not require any proof.require any proof.


pp__________ ppqq AdditionAddition

ppqq__________ pp SimplificationSimplification

pp qq__________ ppqq

ConjunctionConjunction

qq ppq q __________ pp

Modus tollensModus tollens

ppqq qqr r __________ ppr r

Hypothetical Hypothetical syllogismsyllogism

ppqq pp__________ q q

Disjunctive Disjunctive syllogismsyllogism

ArgumentsArguments

Just like a rule of inference, an Just like a rule of inference, an argument argument consists of consists of one or more hypotheses and a conclusion. one or more hypotheses and a conclusion.

We say that an argument isWe say that an argument is valid valid, if whenever all its , if whenever all its hypotheses are true, its conclusion is also true.hypotheses are true, its conclusion is also true.

However, if any hypothesis is false, even a valid However, if any hypothesis is false, even a valid argument can lead to an incorrect conclusion. argument can lead to an incorrect conclusion.

ArgumentsArgumentsExample:Example:““If 101 is divisible by 3, then 101If 101 is divisible by 3, then 10122 is divisible by 9. is divisible by 9. 101 is divisible by 3. Consequently, 101101 is divisible by 3. Consequently, 10122 is divisible is divisible by 9.”by 9.”

Although the argument is Although the argument is validvalid, its conclusion is , its conclusion is incorrectincorrect, because one of the hypotheses is false , because one of the hypotheses is false (“101 is divisible by 3.”).(“101 is divisible by 3.”).

If in the above argument we replace 101 with 102, If in the above argument we replace 101 with 102, we could correctly conclude that 102we could correctly conclude that 10222 is divisible by is divisible by 9.9.

ArgumentsArgumentsWhich rule of inference was used in the last Which rule of inference was used in the last argument?argument?

p: “101 is divisible by 3.”p: “101 is divisible by 3.”q: “101q: “10122 is divisible by 9.” is divisible by 9.”

pp ppq q __________ qq

Modus Modus ponensponens

Unfortunately, one of the hypotheses (p) is false.Unfortunately, one of the hypotheses (p) is false.Therefore, the conclusion q is incorrect.Therefore, the conclusion q is incorrect.

ArgumentsArguments

Another example:Another example:

““If it rains today, then we will not have a barbeque If it rains today, then we will not have a barbeque today. If we do not have a barbeque today, then we today. If we do not have a barbeque today, then we will have a barbeque tomorrow.will have a barbeque tomorrow.Therefore, if it rains today, then we will have a Therefore, if it rains today, then we will have a barbeque tomorrow.”barbeque tomorrow.”

This is a This is a validvalid argument: If its hypotheses are true, argument: If its hypotheses are true, then its conclusion is also true.then its conclusion is also true.

ArgumentsArguments

Let us formalize the previous argument:Let us formalize the previous argument:

p: “It is raining today.”p: “It is raining today.”q: “We will not have a barbecue today.”q: “We will not have a barbecue today.”r: “We will have a barbecue tomorrow.”r: “We will have a barbecue tomorrow.”

So the argument is of the following form:So the argument is of the following form:

ppqq qqr r __________ ppr r

Hypothetical Hypothetical syllogismsyllogism

ArgumentsArguments

Another example:Another example:

Gary is either intelligent or a good actor.Gary is either intelligent or a good actor.If Gary is intelligent, then he can count If Gary is intelligent, then he can count from 1 to 10.from 1 to 10.Gary can only count from 1 to 2.Gary can only count from 1 to 2.Therefore, Gary is a good actor.Therefore, Gary is a good actor.

i: “Gary is intelligent.”i: “Gary is intelligent.”a: “Gary is a good actor.”a: “Gary is a good actor.”c: “Gary can count from 1 to 10.”c: “Gary can count from 1 to 10.”

ArgumentsArgumentsi: “Gary is intelligent.”i: “Gary is intelligent.”a: “Gary is a good actor.”a: “Gary is a good actor.”c: “Gary can count from 1 to 10.”c: “Gary can count from 1 to 10.”

Step 1:Step 1: cc HypothesisHypothesisStep 2:Step 2: i i c c HypothesisHypothesisStep 3:Step 3: i i Modus Tollens Steps 1 & 2Modus Tollens Steps 1 & 2Step 4:Step 4: a a i i HypothesisHypothesisStep 5:Step 5: a a Disjunctive SyllogismDisjunctive Syllogism

Steps 3 & 4Steps 3 & 4

Conclusion: Conclusion: aa (“Gary is a good actor.”) (“Gary is a good actor.”)

ArgumentsArgumentsYet another example:Yet another example:

If you listen to me, you will pass CS 320.If you listen to me, you will pass CS 320.You passed CS 320.You passed CS 320.Therefore, you have listened to me.Therefore, you have listened to me.

Is this argument valid?Is this argument valid?

NoNo, it assumes ((p, it assumes ((pq)q) q) q) p. p.This statement is not a tautology. It is This statement is not a tautology. It is falsefalse if p is if p is false and q is true.false and q is true.

Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements x P(x)x P(x)____________________ P(c) if cP(c) if cUU

Universal Universal instantiationinstantiation

P(c) for an arbitrary cP(c) for an arbitrary cUU______________________________________ x P(x)x P(x)

Universal Universal generalizationgeneralization

x P(x)x P(x)____________________________________________ P(c) for some element cP(c) for some element cUU

Existential Existential instantiationinstantiation

P(c) for some element cP(c) for some element cUU________________________________________ x P(x) x P(x)

Existential Existential generalizationgeneralization

Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements

Example:Example:

Every UMB student is a genius. Every UMB student is a genius. George is a UMB student.George is a UMB student.Therefore, George is a genius.Therefore, George is a genius.

U(x): “x is a UMB student.”U(x): “x is a UMB student.”G(x): “x is a genius.”G(x): “x is a genius.”

Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements

The following steps are used in the argument:The following steps are used in the argument:

Step 1:Step 1: x (U(x) x (U(x) G(x)) G(x)) HypothesisHypothesisStep 2:Step 2: U(George) U(George) G(George) G(George) Univ. instantiation Univ. instantiation

using Step 1using Step 1

x P(x)x P(x)____________________ P(c) if cP(c) if cUU

Universal Universal instantiationinstantiation

Step 3:Step 3: U(George) U(George) HypothesisHypothesisStep 4:Step 4: G(George) G(George) Modus ponensModus ponens

using Steps 2 & 3using Steps 2 & 3

Proving TheoremsProving Theorems

Direct proof:Direct proof:An implication pAn implication pq can be proved by showing that if q can be proved by showing that if p is true, then q is also true.p is true, then q is also true.

Example:Example: Give a direct proof of the theorem Give a direct proof of the theorem “If n is odd, then n“If n is odd, then n22 is odd.” is odd.”

Idea:Idea: Assume that the hypothesis of this implication Assume that the hypothesis of this implication is true (n is odd). Then use rules of inference and is true (n is odd). Then use rules of inference and known theorems to show that q must also be true (nknown theorems to show that q must also be true (n22 is odd).is odd).


n is odd.n is odd.

Then n = 2k + 1, where k is an integer.Then n = 2k + 1, where k is an integer.

Consequently, nConsequently, n22 = (2k + 1) = (2k + 1)22.. = 4k= 4k22 + 4k + 1 + 4k + 1 = 2(2k= 2(2k22 + 2k) + 1 + 2k) + 1

Since nSince n22 can be written in this form, it is odd. can be written in this form, it is odd.


Indirect proof:Indirect proof:

An implication pAn implication pq is equivalent to its q is equivalent to its contra-contra-positivepositive q q p. Therefore, we can prove pp. Therefore, we can prove pq by q by showing that whenever q is false, then p is also false.showing that whenever q is false, then p is also false.

Example:Example: Give an indirect proof of the theorem Give an indirect proof of the theorem “If 3n + 2 is odd, then n is odd.”“If 3n + 2 is odd, then n is odd.”

Idea:Idea: Assume that the conclusion of this implication Assume that the conclusion of this implication is false (n is even). Then use rules of inference and is false (n is even). Then use rules of inference and known theorems to show that p must also be false known theorems to show that p must also be false (3n + 2 is even).(3n + 2 is even).

Proving TheoremsProving Theoremsn is even.n is even.

Then n = 2k, where k is an integer.Then n = 2k, where k is an integer.

It follows that 3n + 2 = 3(2k) + 2 It follows that 3n + 2 = 3(2k) + 2 = 6k + 2= 6k + 2= 2(3k + 1)= 2(3k + 1)

Therefore, 3n + 2 is even.Therefore, 3n + 2 is even.

We have shown that the contrapositive of the We have shown that the contrapositive of the implication is true, so the implication itself is also true implication is true, so the implication itself is also true (If 2n + 3 is odd, then n is odd).(If 2n + 3 is odd, then n is odd).

per3 pembuktian

Education