Transcript CSS342: Proofs

CSS342: Proofs
Professor: Munehiro Fukuda
CSS342: Proofs
1
Terminologies
• Axioms: are assumed true.
– Ex: Given two distinct points, there is exactly one line that contains them.
• Undefined terms: implicitly defined (and used) by the
axioms.
– Ex: Points, lines
• Definitions: used to create new concepts.
– Ex: Two lines are parallel if they never cross each other.
• Theorem: a proposition that has been proved to be true.
– If two sides of a triangle are equal, the angles opposite them are equal.
• Corollary: a theorem that follows quickly from another
theorem.
– Ex: If a triangle is equilateral, then it is equiangular.
• Lemma: a theorem not interesting but useful in proving
another theorem.
– Ex: A positive integer – 1 ≥ 0
CSS342: Proofs
2
Axioms, Definitions, and Undefined Terms
Examples
• Euclidean geometry:
– Axiom 1: Given two distinct points, there is exactly one line that contains them.
– Axiom 2: If three points are not collinear, then there is exactly one plane that
contains them.
– Definition 1: Two angles are supplementary if the sum of their measures is 180.
– Definition 2: Two lines are parallel if they never cross each other.
– Undefined terms: points, lines, planes, and angles
• Real numbers:
– Axiom 1: The commutative law stands up right for +-*/ operations.
– Axiom 2: If x and y are in a subset P, -x and –y are not in P, and x+y and xy are
in P.
– Definition 1: P is called positive real numbers.
– Definition 2: Given a nonnegative real number, x and a positive integer, n, x1/n is
y satisfying yn = x
– Undefined terms: numbers and 0
CSS342: Proofs
3
Theorem and Corollary
Examples
• Theorem:
– If two sides of a triangle are equal, then the angles opposite
them are equal.
Draw a line from the top vertex down to the
– Proof.
bottom side so that the side is divided into
two halves equally.
Then, we can have two sub triangles, both
having all equal sides.
• Corollary:
Thus, they are congruent.
Therefore, the angles opposite them are equal.
– If a triangle is equilateral, then it is equiangular.
CSS342: Proofs
4
Lemma
Example
• If n is a positive integer number, the either n – 1 is a
positive integer or n – 1 = 0.
• Proof:
– The minimal positive integer is 1. Thus, n – 1 cannot be
smaller than 0. Therefore, the lemma is true.
– This lemma is not interesting in its own right, but can be
used to prove other results.
CSS342: Proofs
5
Direct Proof
• When proving a universally quantified statement:
x1, …, xn, P(x1, …, xn)→q(x1, …, xn)
• If P(x1, …, xn) is false, this statement is always
true.
• Thus, focus on only the case when P(x1, …, xn) is
true.
• Using P(x1, …, xn) for a proof is called
A direct proof
A
CSS342: Proofs
6
Direct Proof
Example
• Universally quantified statement:
– If d = min{d1, d2} and x ≤ d, x ≤ d1 and x ≤ d2
• Proof:
Assume that d = min {d1, d2} and x ≤ d.
From the definition of min,
d ≤ d1 and d ≤ d2
From x ≤ d and d ≤ d1 , x ≤ d1
From x ≤ d and d ≤ d2 , x ≤ d2
Thus, the statement is true.
CSS342: Proofs
7
Proof by contradiction
• Assume that the hypothesis p is true but the conclusion q
is false.
• Use p, !q and r (= other axioms, definitions, theorems).
• Derive r && !r = false. In other words, p && !q→ r && !r
p
q (!q)
r
p→q
p&&!q
r&&!r
p && !q → r && !r
T
T (F)
T
T
F
F
T
T
T (F)
F
T
F
F
T
T
F (T)
T
F
T
F
F
T
F (T)
F
F
T
F
F
F
T (F)
T
T
F
F
T
F
T (F)
F
T
F
F
T
F
F (T)
T
T
F
F
T
F
F (T)
F
T
F
F
T
CSS342: Proofs
8
Proof by Contradiction
Example 1
• If xy = 0, then either x = 0 or y = 0
• Proof.
– p: xy = 0
– q: x = 0 || y = 0
– !q: !(x=0 || y=0) ≡ x ≠ 0 && y ≠ 0
– r: if ab = ac and a ≠ 0, b = c (Let’s assume it has been
proved)
– p && !q: xy = x * 0 = 0 and x ≠ 0
– From r: y must be 0
– This contradicts !q, which thus means r is wrong.
– This derives r && !r
– Thus, this statement must be true.
CSS342: Proofs
9
Proof by Contradiction
Example 2
• For all real numbers x and y, if x + y ≥ 2, then either x ≥ 1
or y ≥ 1.
• Proof.
– p: x + y ≥ 2
– q: x ≥ 1 || y ≥ 1
– !q: !(x ≥ 1 || y ≥ 1) ≡ !(x ≥ 1) && !(y ≥ 1) ≡ x < 1 && y < 1 ≡ x +
y < 2 ≡ !p
– This derived p && !p
– Thus, the statement must be true.
– Therefore, the statement must be true.
• Instead of r && !r, we derived p && !p, (i.e., r = p)
– Special case: proof by contrapositive
CSS342: Proofs
10
Deductive Reasoning
• Drawing a conclusion from a sequence of propositions.
• Hypothesis:
P1:
P2:
P3:
The bug is either in module 17 or in 81.
The bug is a numerical error.
Module 81 has no numerical error.
• Conclusion:
∴ Q: The bug is in module 17
CSS342: Proofs
11
•
•
•
•
p→q
p
∴q
P: 1 * 2 = 2
Q: I ate candy.
P is true
Thus Q is true (= I ate candy)
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
p → q && p
T
F
F
F
q
T
F
T
F
Note: p →q, p /∴ q does not mean p →q && p ≡ ∴ q
In fact, truth values do not match perfectly.
It means that if p →q && p, then q = true.
CSS342: Proofs
12
•
•
•
•
P: 1 + 2 = 2
Q: I ate my hat.
Q is true (= I ate my hat.)
Then, is 1 + 2 = 2 true?
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
p→q
q
∴p
p → q && q
T
F
T
F
p
T
T
F
F
When p → q && q = true, p can be true or false.
Thus, this deductive argument is wrong.
CSS342: Proofs
13
Rules of inference for propositions
Rule of
Inference
Name
Rule of
Inference
Name
p→q
p
∴q
Modus ponens
p
q
∴p && q
Conjunction
p→q
!q
∴!P
Modus tollens
p→q
q→r
∴p → r
Hypothetical syllogism
p
∴p || q
Addition
p || q
!p
∴q
Disjunctive syllogism
p && q
∴p
Simplification
CSS342: Proofs
14
Inference Example 1
•
•
•
•
If you pass CSS342, then you can take CSS343. (p → q)
If you can take CSS343, then you’ll learn binary trees. (q → r)
If you can take CSS343, then you’ll learn inheritance. (q → s)
You passed CSS342. (p)
• Applying the hypothetical syllogism:
p→q
q→r
∴p → r
p→q
q→s
∴p → s
• Thus, r && s
• You’ll learn both binary trees and inheritance
CSS342: Proofs
15
Rules of Inference for Quantified
Statements
Rules of Inference
Name
∀x ∈ D P(x)
∴P(d) if d ∈ D
Universal instantiation
P(d) for any d ∈ D
∴∀x P(x)
Universal generalization
∃x ∈ D P(x)
∴P(d) for some d ∈ D
Existential instantiation
P(d) for some d ∈ D
∴ ∃ x P(x)
Existential generalization
CSS342: Proofs
16
Inference Example 2
• Given two statements:
– Everyone loves either Microsoft or Apple.
– Lynn does not love Microsoft.
• P(x): x loves Microsoft.
• Q(x): x loves Apple.
• From universal generalization,
– ∀x P(x) || Q(x): Everyone loves either MicroSoft or Apple.
• !P(Lynn): Lynn does not love Microsoft.
• From disjunctive syllogism: p || q, !p / ∴q
– Q(Lynn) is true.
• Q(Lynn): Lynn loves Apple.
CSS342: Proofs
17
Final Review
Why Logic is So Important in CS?
•
•
•
•
Inference is quite often used in knowledge database.
Knowledge database is a core of expert system.
Thus, inference is a core of expert system. 
Example in CS: Prolog
likes(mary, food).
likes(mary, wine).
likes(john, wine).
likes(john, mary).
?- likes(mary, X), likes(john, X).
X=wine
CSS342: Proofs
18