Transcript P =>Q

Logic: Connectives
AND
OR
NOT
P
Q (P ^ Q)
P
Q (P v Q)
T
T
T
T
T
T
T
F
F
T
F
T
F
T
F
F
T
T
F
F
F
F
F
F
P
~P
T
F
F
T
IF AND ONLY IF
IMPLIES
Q
( P Q )
T
T
T
F
T
F
F
T
T
F
T
F
F
T
F
F
T
P
Q (P =>Q)
T
T
T
T
F
F
F
P
Converse and contrapositive
• For the proposition P => Q, the proposition Q => P is called its
converse, and the proposition ~Q => ~P is called its
contrapositive.
• For example for the proposition "If it rains, then I get wet",
Converse: If I get wet, then it rains.
Contrapositive: If I don't get wet, then it does not rain.
• The converse of a proposition is not necessarily logically equivalent
to it, that is they may or may not take the same truth value at the
same time.
• On the other hand, the contrapositive of a proposition is always
logically equivalent to the proposition. That is, they take the same
truth value regardless of the values of their constituent variables.
• Therefore, "If it rains, then I get wet." and "If I don't get wet, then
it does not rain." are logically equivalent. If one is true then the
other is also true, and vice versa.
Methods of Proof
• Direct Proof, Indirect Proof, and proof by contradiction
• Direct Proof: The implication p => q can be proved by showing
that if p is true, then q must also be true.
• Example: Give a direct proof of the theorem “If n is an odd integer,
then n 2 is an odd integer”.
• Solution: Assume that the hypothesis of this implication is true.
Suppose that n is odd.
Then n = 2k +1 where n is an integer.
It follows that n 2 = (2k + 1) 2
=4k2+4k+1
= 2 (2 k 2 + 2k) + 1
Therefore, n is an odd integer ( It is one more than twice an integer)
Methods of Proof
• Indirect Proof: We know that an implication p => q is equivalent to
its contrapositive ~q => ~p. Thus to prove p => q indirectly, we
assume q is false (~q) and show that p is then false (~p)
• Example: Give an indirect proof of the theorem “If 3n + 2 is an odd
integer, then n is an odd integer”.
• Solution: Assume that the conclusion of this implication is false.
Suppose that n is even.
Then n = 2k where n is an integer.
It follows that 3 n + 2 = 3 (2 k) + 2
= 6k + 2
= 2 (3k + 1)
Therefore, 3n + 2 is an even integer ( It is an integral multiple of 2)
Thus, we show that if n is even, then 3n + 2 is even, which is the
contrapositive of the given statement. Hence the given statement has
been proved.
Mistakes in Proof
What is wrong with the following proof “1 = 2’? a≠0,
b ≠ 0.
Step
Reason
1. a = b
Given
2. a 2 = ab
Multiply both sides by a
3. a2 – b2 = ab – b2
Subtract b2 from both sides
4. (a – b)(a + b)= b(a – b) Factorize both sides
5. a + b = b
Divide both sides by (a – b)
6. b + b = b
From 1. (Given)
7. 2b = b
Addition
8. 2 = 1
Divide both sides by b
Mistakes in Proof
What is wrong with the proof
“1 = 2’?
Solution:
Every step is valid except for one, step 5, where
we divided both sides by (a – b).
We cannot divide by (a – b)
since a – b = 0 ( a = b Given)
Division by zero is not a valid operation.
Methods of Proof
Proof by contradiction: This method is based on the
tautology (p => q) ^ (~q)) => (~p).
• Thus the rule of inference
p => q
~q
Therefore, ~p
• Informally, if a statement p implies a false statement q,
then p must be false.
• We use this technique where q is an absurdity or
contradiction.
Methods of Proof
• Prove there is no rational number p / q whose square is 2.
• Solution:
Assume (p / q) 2 = 2 where p and q are integers having no
common factors.
Then, p 2 = 2 q2
Therefore, p 2 is even.
This implies p is even, since the square of an odd number is odd.
Thus, p = 2n where n is an integer.
2 q 2 = p2 = (2 n) 2 = 4n 2 or, q 2 = 2n 2
Thus q 2 is even, and so q is even.
p and q are even, therefore they have a common factor 2. This is
a contradiction to the assumption.
Thus the assumption must be false.
Mathematical Induction
• Another proof technique.
• In this technique, we need to prove two steps:
• Basis step: First we need to prove that the basis element,
that is 0, has the property in question.
• Inductive step: Then we need to prove that if an
arbitrary natural number, denoted by n, has the property
in question, then the next element, that is n + 1, has that
property.
• When these two are proven, then it follows that all the
natural numbers have that property.
Mathematical Induction
• When these two are proven, then it follows that all the
natural numbers have that property- Explanation.
• Since 0 has the property by the basis step, the element
next to it, which is 1, has the same property by the
inductive step. Then since 1 has the property, the
element next to it, which is 2, has the same property
again by the inductive step.
• Proceeding likewise, any natural number can be
shown to have the property.
• This process is somewhat analogous to the knocking
over a row of dominos with knocking over the first
domino corresponding to the basis step.
Mathematical Induction
• Example: Prove that for any natural number n,
0 + 1 + ... + n = n( n + 1 )/2 .
Proof:
Basis Step: If n = 0, then LHS = 0, and RHS = 0 * (0 + 1) = 0 .
Hence LHS = RHS.
Induction: Assume that for an arbitrary natural number n,
0 + 1 + ... + n = n( n + 1 )/2 . -------- Induction Hypothesis
To prove this for n+1, first try to express LHS for n+1 in terms of
LHS for n, and use the induction hypothesis.
LHS for n + 1
= 0 + 1 + ... + n + (n + 1) = (0 + 1 + ... + n) + (n + 1) .
Using the induction hypothesis, the last expression can be rewritten
as n( n + 1 )/2 + (n + 1) .
Factoring (n + 1) out, we get (n + 1)(n + 2) / 2 ,
which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.
Mathematical Induction
• Problem: For any natural number n , 2 + 4 + ... + 2n = n( n + 1 ).
Proof:
Basis Step: If n = 0, then LHS = 0, and RHS = 0 * (0 + 1) = 0 .
Hence LHS = RHS.
Induction: Assume that for an arbitrary natural number n,
0 + 2 + ... + 2n = n( n + 1 ) . ---- Induction Hypothesis
To prove this for n+1, first try to express LHS for n+1 in terms of
LHS for n, and use the induction hypothesis.
LHS for n + 1 = 0 + 2 + ... + 2n + 2(n + 1)
= (0 + 2 + ... + 2n) + 2(n + 1) .
Using the induction hypothesis, the last expression can be rewritten
as n( n + 1 ) + 2(n + 1) .
= (n + 1)(n + 2) , which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.
Mathematical Induction
Problem: If r is a real number not equal to 1, then for every n ≥0,
r 0 + r 1 + …+r n = (1 – r n + 1)/(1 – r)
Proof:
Basis Step: If n = 0, then LHS = r0 = 1, and RHS = (1 - r) / (1 - r) = 1, since
r ≠ 1. Hence LHS = RHS.
Induction: Assume that
r 0 + r 1 + …+r n = (1 – r n + 1)/(1 – r) ------ Induction Hypothesis
To prove this for n+1, first try to express LHS for n+1 in terms of LHS for
n, and use the induction hypothesis.
LHS for n + 1 =
= r 0 + r 1 + …+r n + r n+1 = (r 0 + r 1 + …+r n ) + r n+1
Using the induction hypothesis, the last expression can be rewritten as:
(1 – r n + 1)/(1 – r) + r n + 1
Taking the common denominator, it is equal to
((1 – r n + 1) + (r n + 1 - r n + 2 )) / (1 – r) = (1 - r n + 2 )/(1 – r)
which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.