المحاضرة السادسة هياكل متقطعة

Proofs
• The truth value of some statements about the world are obvious
and easy to assess
• The truth of other statements may not be obvious, …
…. But it may still follow (be derived) from known facts about
the world
Proof: shows that the truth value of such a statement follows from
(or can be inferred) from the truth value of other statements
Important questions:
– When is the argument correct?
– How to construct a correct argument, what method to use?
Proof by contradiction
• We want to prove p ? q
• The only way to reject (or disprove) p ? q is to show that (p ?
¬q ) can be true
• However, if we manage to prove that either q or ¬ p is True
then we contradict (p ? ¬q )
– and subsequently p ? q must be true
• Proof by contradiction. Show that the assumption (p ? ¬q )
leads either to q or ¬ p which generates a contradiction.
Proof by contradiction
• We want to prove p ? q
• The only way to reject (or disprove) p ? q is to show that (p ?
¬q ) can be true
• However, if we manage to prove that either q or ¬ p is True
then we contradict (p ? ¬q )
– and subsequently p ? q must be true
• Proof by contradiction. Show that the assumption (p ? ¬q )
leads either to q or ¬ p which generates a contradiction.
Proof by contradiction
• We want to prove p ? q
• The only way to reject (or disprove) p ? q is to show that (p ?
¬q ) can be true
• However, if we manage to prove that either q or ¬ p is True
then we contradict (p ? ¬q )
– and subsequently p ? q must be true
• Proof by contradiction. Show that the assumption (p ? ¬q )
leads either to q or ¬ p which generates a contradiction.
Proof by contradiction
• We want to prove p ? q
• The only way to reject (or disprove) p ? q is to show that (p ?
¬q ) can be true
• However, if we manage to prove that either q or ¬ p is True
then we contradict (p ? ¬q )
– and subsequently p ? q must be true
• Proof by contradiction. Show that the assumption (p ? ¬q )
leads either to q or ¬ p which generates a contradiction.
Vacuous proof
We want to show p ? q
• Suppose p (the hypothesis) is always false
• Then p ? q is always true.
Reason:
• F ? q is always T, whether q is True or False
Example:
• Let P(n) denotes “if n > 1 then n2> n” is TRUE.
• Show that P(0).
Proof:
• For n=0 the premise is False. Thus P(0) is always true.
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Trivial proofs
We want to show p ? q
• Suppose the conclusion q is always true
• Then the implication p ? q is trivially true.
• Reason:
• p? T is always T, whether p is True or False
Example:
• Let P(n) is “if a >=b then an >= bn ”
• Show that P(0)
Proof:
a0 >=b0 is 1=1 trivially true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
• We want to show p1 ? p2 ?… ? pn ? q
• Note that this is equivalent to
– (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
• Why?
• p1 ? p2 ?… ? pn ? q <=> (useful)
• ¬ (p1 ? p2 ?… ? pn) ? q <=> (De Morgan)
• (¬p1 ? ¬p2 ?… ? ¬pn) ? q <=> (distributive)
• (¬p1 ? q) ? (¬p2 ? q) ? …? (¬pn ? q) <=> (useful)
• (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
We want to show p1 ? p2 ?… ? pn ? q
• Equivalent to (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
Prove individual cases as before. All of them must be true.
Example: Show that |x||y|=|xy|.
Proof:
• 4 cases:
• x >=0, y>=0
• x>= 0, y <0
• x<0, y>=0 |
• x<0, , y <0 |
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
We want to show p1 ? p2 ?… ? pn ? q
• Equivalent to (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
Prove individual cases as before. All of them must be true.
Example: Show that |x||y|=|xy|.
Proof:
• 4 cases:
• x >=0, y>=0 xy >0 and |xy|=xy=|x||y|
• x>= 0, y <0 xy < 0 and |xy|=-xy =x (-y)=|x||y|
• x<0, y>=0 xy < 0 and |xy|=-xy =(-x) y=|x||y|
• x<0, , y <0 xy >0 and |xy|= (-x)(-y) =|x||y|
• All cases proved.
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof of equivalences
We want to prove p ? q
• Statements: p if and only if q.
• Note that p ? q is equivalent to [ (p ? q ) ? (q ? p) ]
• Both implications must hold.
Vacuous proof
We want to show p ? q
• Suppose p (the hypothesis) is always false
• Then p ? q is always true.
Reason:
• F ? q is always T, whether q is True or False
Example:
• Let P(n) denotes “if n > 1 then n2> n” is TRUE.
• Show that P(0).
Proof:
• For n=0 the premise is False. Thus P(0) is always true.
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Trivial proofs
We want to show p ? q
• Suppose the conclusion q is always true
• Then the implication p ? q is trivially true.
• Reason:
• p? T is always T, whether p is True or False
Example:
• Let P(n) is “if a >=b then an >= bn ”
• Show that P(0)
Proof:
a0 >=b0 is 1=1 trivially true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
• We want to show p1 ? p2 ?… ? pn ? q
• Note that this is equivalent to
– (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
• Why?
• p1 ? p2 ?… ? pn ? q <=> (useful)
• ¬ (p1 ? p2 ?… ? pn) ? q <=> (De Morgan)
• (¬p1 ? ¬p2 ?… ? ¬pn) ? q <=> (distributive)
• (¬p1 ? q) ? (¬p2 ? q) ? …? (¬pn ? q) <=> (useful)
• (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
We want to show p1 ? p2 ?… ? pn ? q
• Equivalent to (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
Prove individual cases as before. All of them must be true.
Example: Show that |x||y|=|xy|.
Proof:
• 4 cases:
• x >=0, y>=0
• x>= 0, y <0
• x<0, y>=0 |
• x<0, , y <0 |
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof by cases
We want to show p1 ? p2 ?… ? pn ? q
• Equivalent to (p1 ? q) ? (p2 ? q) ?… ? (pn ? q)
Prove individual cases as before. All of them must be true.
Example: Show that |x||y|=|xy|.
Proof:
• 4 cases:
• x >=0, y>=0 xy >0 and |xy|=xy=|x||y|
• x>= 0, y <0 xy < 0 and |xy|=-xy =x (-y)=|x||y|
• x<0, y>=0 xy < 0 and |xy|=-xy =(-x) y=|x||y|
• x<0, , y <0 xy >0 and |xy|= (-x)(-y) =|x||y|
• All cases proved.
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Proof of equivalences
We want to prove p ? q
• Statements: p if and only if q.
• Note that p ? q is equivalent to [ (p ? q ) ? (q ? p) ]
• Both implications must hold.