Transcript Chapter 1: The Foundations: Logic and Proofs - SCU-CSIM

Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
1
1.1: Propositional Logic
Propositions: A proposition is a
declarative sentence (that is, a
sentence that declares a fact) that
is either true or false, but not
both.
2
Example 1:
All the following declarative sentences
are propositions:
1. Washington D.C., is the capital of
the USA.
2. Toronto is the capital of Canada
3. 1+1=2.
4. 2+2=3.
3
Example 2:
Consider the following sentences. Are
they propositions?
1. What time is it?
2. Read this carefully.
3. x+1=2.
4. x+y=z
4
• We use letters to denote propositional
variables (or statement variables).
• T: the value of a proposition is true.
• F: the value of a proposition is false.
• The area of logic that deals with
propositions is called the propositional
calculus or propositional logic.
5
Let p and q are propositions:
Definition 1: Negation (Not)
• Symbol: ¬
• Statement: “it is not the case that p”.
• Example:
P: I am going to town
¬P:
It is not the case that I am going to town;
I am not going to town;
I ain’t goin’.
6
7
Definition 2: Conjunction (And)
• Symbol:
• The conjunction pq is true when both p and q are
true and is false otherwise.
• Example:
P - ‘I am going to town’
Q - ‘It is going to rain’
PQ: ‘I am going to town and it is going to rain.’
8
t01_1_002.jpg
9
Definition 3: Disjunction (Or)
• Symbol:
• The disjunction pq is false when both p and q are
false and is true otherwise.
• Example:
P - ‘I am going to town’
Q - ‘It is going to rain’
P  Q: ‘I am going to town or it is going to rain.’
10
11
Definition 4: Exclusive OR
• Symbol:
• The exclusive or of p and q, denote pq, is true
when exactly one of p and q is true and is false
otherwise.
• Example:

P - ‘I am going to town’
Q - ‘It is going to rain’
P  Q: ‘Either I am going to town or it is going
to rain.’
12
13
Definition 5: Implication
•
•
•
•
•
If…. Then….
Symbol:
The conditional statement pq is false when p is true
and q is false, and true
P is called the hypothesis and q is called the conclusion.
Example:
P - ‘I am going to town’
Q - ‘It is going to rain’
P Q: ‘If I am going to town then it is going to rain.’
14
15
Equivalent Forms
If P, then Q
P implies Q
If P, Q
P only if Q
P is a sufficient condition for Q
Q if P
Q whenever P
Q is a necessary condition for P
16
Note: The implication is false only when P is true and
Q is false!
• ‘If the moon is made of green cheese then I have
more money than Bill Gates’ (?)
• ‘If the moon is made of green cheese then I’m on
welfare’ (?)
• ‘If 1+1=3 then your grandma wears combat boots’
(?)
• ‘If I’m wealthy then the moon is not made of green
cheese.’ (?)
• ‘If I’m not wealthy then the moon is not made of
green cheese.’ (?)
17
More terminology
•QP is the CONVERSE of P  Q
•¬ Q  ¬ P is the CONTRAPOSITIVE of P  Q
•¬ P ¬ Q is the inverse of P  Q
•Example:
Find the converse of the following statement:
R: ‘Raining tomorrow is a sufficient condition
for my not going to town.’
18
Procedure
Step 1: Assign propositional variables to component
propositions
P: It will rain tomorrow
Q: I will not go to town
Step 2: Symbolize the assertion
R: P  Q
Step 3: Symbolize the converse
QP
Step 4: Convert the symbols back into words
‘If I don’t go to town then it will rain tomorrow’
• Homework: Find inverse and contrapositive of statements
above.
19
Definition 6: Biconditional
•
•
•
•
•
‘if and only if’, ‘iff’
Symbol:
The biconditional statement pq is true when p and q
have the same truth value, and is false otherwise.
Biconditional statements are also called bi-implications.
Example:
P - ‘I am going to town’
Q - ‘It is going to rain’
P Q: ‘I am going to town if and only if it is going
to rain.’
20
21
Translating English
•Breaking assertions into component propositions look for the logical operators!
•Example:
‘If I go to Harry’s or go to the country I will not go
shopping.’
P: I go to Harry’s
Q: I go to the country
R: I will go shopping
If......P......or.....Q.....then....not.....R
(P Q)  ¬ R
22
Constructing a truth table
1.
2.
3.
4.
one column for each propositional variable
one for the compound proposition
count in binary
n propositional variables = 2n rows
• Construct the truth table for
(P  ¬ Q)  (PQ)
• HW: Construct the truth table for (P Q)  ¬ R
23
24
t01_1_008.jpg
25
• What is the real meaning of ¬ PQ ?
a) (¬ P) Q
b) ¬ (PQ)
• What is the real meaning of PQR ?
a) (PQ)R
b) P(QR)
• What is the real meaning of P  QR ?
a) (P  Q)R
b) P  (QR)
26
27
Logic and Bit Operations
• Example 20
Find the bitwise OR, bitwise AND, and
bitwise XOR of the bit strings
01 1011 0110 and
11 0001 1101.
28
Logic Puzzles
• Example 18:
There are two kind of inhabitants, knights,
who always tell the truth, and their
opposites, knaves, who always lie. You
encounter two people A and B. What
are A and B if A says “B is a knight” and
B says “The two of us are opposite type”?
29
Terms
•
•
•
•
•
•
Proposition
Negation
Conjection
Disjunction
Exclusive OR
Implication
• Inverse
• Converse
• Contrapositive
30
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
31
1.2: Propositional Equivalences
Definition:
Tautology: A compound proposition that
is always true.
Contradiction: A compound proposition
that is always false.
Contingency: A compound proposition
that is neither a tautology nor a
contradiction.
32
33
Logical Equivalences
•
Compound propositions that have
the same truth values in all possible
cases are called logically equivalent.
• Definition:
The compound propositions p and q are
called logically equivalent if pq is a
tautology. Denote pq.
34
Logical Equivalences
•
•
One way to determine whether
two compound propositions are
equivalent is to use a truth table.
Symbol: PQ
35
Logical Equivalences
•
Prove the De Morgan’s Laws.
36
Logical Equivalences
• HW: Prove the other one (De Morgan’s
Laws).
37
Logical Equivalences
• Example:
Show that pq and ¬pq are logically
equivalent.
• HW: example 4 of page 23
38
Logical Equivalences
t01_2_006.jpg
39
Logical Equivalences
40
Logical Equivalences
41
Logical Equivalences
Example 5: Use De Morgan’s laws to express the
negations of “Miguel has a cellphone and he
has a laptop computer”.
Example 5: Use De Morgan’s laws to express the
negations of “Heather will go to the concert or
Steve will go to the concert”.
42
Logical Equivalences
• Example 6: Show that ¬(pq) and p ¬q are
logically equivalent.
• Example 7: Show that ¬(p(¬p  q)) and ¬p 
¬q are logically equivalent by developing a
series of logical equivalences.
• Example 8: Show that (p  q) ( pq) is a
tautology.
43
Terms
•
•
•
•
•
•
•
•
Tautology
Contradiction
Contingency
Logical Equivalence
De Morgan’s Laws
Commutative Law
Associative Law
Distributive Law
44
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
Predicates
Predicate: A generalization of
propositions ; A propositions which
contain variables
• Predicates become propositions once
every variable is bound- by
– assigning it a value from the Universe of
Discourse U or
– quantifying it
P. 1
Predicates
Examples:
Let U = Z, the integers = {. . . -2, -1, 0 , 1, 2, . . .}
– P(x): x > 0 is the predicate. It has no truth value until
the variable x is bound.
• Examples of propositions where x is assigned a
value:
(a) P(-3) (?, true or false);
(b) P(0)(?);
(c) (c) P(3)(?).
• The collection of integers for which P(x) is true are
the positive integers.
• P(y) ν ¬ P(0) is not a proposition. The variable y
has not been bound. However, P(3) ν ¬ P(0) is a
proposition which is true.
P. 1
Predicates
Example: Let R be the three-variable predicate
R(x, y, z): x + y = z
• Find the truth value of
R(2, -1, 5),
R(3, 4, 7),
R(x, 3, z)
P. 1
Quantifiers: Universal
• P(x) is true for every x in the universe of
discourse.
• Notation: universal quantifier ∀xP(x)
• ‘For all x, P(x)’, ‘For every x, P(x)’
• The variable x is bound by the universal
quantifier producing a proposition.
• An element for which P(x) is false is
called a counterexample of ∀xP(x).
• Example: U={1,2,3}
∀ xP(x)  P(1) Λ P(2) Λ P(3)
P. 1
Quantifiers: Universal
• Example 8:
Let P(x) be the statement “x+1>x.” What is the
truth value of the quantification ∀ xP(x) where
the domain consists of all real number.
• HW: P36, example 13
P. 1
Quantifiers: Existential
• P(x) is true for some x in the universe of
discourse.
• Notation: existential quantifier ∃xP(x)
– ‘There is an x such that P(x),’
– ‘For some x, P(x)’,
– ‘For at least one x, P(x)’,
– ‘I can find an x such that P(x).’
• Example: U={1,2,3}
–∃xP(x)  P(1) ν P(2) ν P(3)
P. 1
Quantifiers: Existential
• Example 14:
Let P(x) denote the statement “x>3.” What is the
truth value of the quantification ∃ xP(x),
where the domain consists of all real numbers.
• HW:
Page 37, Example 16.
P. 1
Quantifiers
P. 1
Quantifiers: Unique Existential
• P(x) is true for one and only one x in the
universe of discourse.
• Notation: unique existential ∃!xP(x)
– ‘There is a unique x such that P(x),’
– ‘There is one and only one x such that P(x),’
– ‘One can find only one x such that P(x).’
P. 1
Quantifiers
• Example: U={1,2,3}
• Truth Table:
P(1)
P(2) P(3)
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
∃!xP(x)
0
1
1
0
1
0
0
0
P. 1
Quantifiers
• Note: A predicate is not a proposition until all
variables have been bound either by
quantification or assignment of a value!
P. 1
Precedence of Quantifiers
The quantifiers  and  have higher precedence than
all logical operators from propositional calculus.
Example:
 xP(x)Q(x) means
(a) ( xP(x))Q(x)
(b)  x(P(x)Q(x))
P. 1
Binding Variables
• Example:
x(x+y=1)
Bound variable:
Free variable:
• Example:
x(P(x)Q(x)) xR(x)
The scope of :
The scope of :
The same meaning of x(P(x)Q(x)) yR(y)
P. 1
Logical Equivalences Involving Quantifiers
Example 19:
Show that x(P(x)Q(x)) and xP(x) xQ(x)
are logically equivalent.
P. 1
Logical Equivalences Involving Quantifiers
• Statement involving predicates and quantifiers
are logically equivalent if and only if they have
the same truth value no matter which
predicates are substituted into these
statements and which domain of discourse is
used for the variables in these propositional
functions.
• Symbol: S T
P. 1
Equivalences Involving the Negation Operator
• Equivalences involving the negation operator
¬∀xP(x)  ∃x ¬ P(x)
¬∃xP(x)  ∀ x ¬ P(x)
• Distributing a negation operator across a
quantifier changes a universal to an existential
and vice versa.
P. 1
Equivalences Involving the Negation Operator
• Example 20:
What are the negations of the statements:
“There is an honest politician”
• Example 20:
What are the negations of the statements:
“All Americans eat cheeseburgers”.
HW: Example 21 in P41.
P. 1
Translating from English into Logical
Expressions (single quantifier)
• Example 23:
Express the statement “Every student in this class has
studied calculus” using predicates and quantifiers.
P. 1
Using Quantifiers in System Specifications
• Example 26:
Consider these statements.
“All lions are fierce.”
“Some lions do not drink coffee.”
“Some fierce creatures do not drink coffee.”
Let P(x): x is a lion.
Q(x): x is fierce.
R(x): x drinks coffee.
Assuming that the domain consists of all creatures, express
the statements in the argument using quantifiers and
P(x), Q(x), and R(x).
P. 1
Logic Programming
• Prolog(Programming in Logic, developed in the 1970s.
• Working in AI.
• Prolog programs including a set of declarations
consisting of two types of statements:
– Facts : define predicates by specifying the elements that
satisfy these predicates.
– Rules: define new predicates using those already defined
by facts.
P. 1
Logic Programming
• Example 28:
Facts:
instructor(chan, math273)
instructor(patel, ee222)
instructor(grossman, cs301)
enrolled(kevin, math273)
enrolled(juana, ee222)
enrolled(juana, cs301)
enrolled(kiko, math273)
enrolled(kiko, cs301)
Rules:
teacher(P,S) :instructor(P,C),
enrolled(S,C)
Queries:
?enrolled(kevin, math273)
?enrolled(X,math273)
?teacher(X,juana)
Uppercase letters are variables. The “” represents by “,”
and the “” represents by “;” in Prolog.
P. 1
Quantifiers
• Multiple Quantifiers: read left to right . . .
• Example: Let U = R, the real numbers, P(x,y): xy= 0
∀x∀yP(x, y)
∀x∃yP(x, y)
∃x∀yP(x, y)
∃x∃yP(x, y)
The only one that is false is the first one.
• Suppose P(x,y) is the predicate x/y=1? Assume U=R{0}.
P. 1
Quantifiers
• Example: Let U = {1,2,3}. Find an expression
equivalent to ∀x∃yP(x, y) where the variables are
bound by substitution instead:
• Expand from inside out or outside in.
• Outside in:
∃yP(1, y) Λ ∃ yP(2, y) Λ ∃ yP(3, y)
[P(1,1) ν P(1,2) ν P(1,3)] Λ
[P(2,1) ν P(2,2) ν P(2,3)] Λ
[P(3,1) ν P(3,2) ν P(3,3)]
• HW: Inside Out:
P. 1
Quantifiers
• De Morgan’s Laws for Quantifiers
P. 1
Quantifiers: Converting from English
• Examples:
F(x): x is a fleegle
S(x): x is a snurd
T(x): x is a thingamabob
U={fleegles, snurds, thingamabobs}
• Note: the equivalent form using the existential
quantifier is also given
P. 1
Quantifiers: Converting from English
• Everything is a fleegle
∀xF( x)  ¬∃x¬F(x)
• Nothing is a snurd.
∀x¬S(x)  ¬∃xS( x)
• All fleegles are snurds.
∀x[F(x) → S(x)]
∀ x[¬ F(x) ν S(x)]
 ∀ x ¬[F(x) Λ ¬ S(x)]
 ¬∃x[F(x) Λ ¬ S( x)]
P. 1
Quantifiers: Converting from English
• Some fleegles are thingamabobs.
∃x[F(x) Λ T(x)]
 ¬ ∀ x[¬ F(x) ν ¬ T(x)]
• No snurd is a thingamabob.
∀ x[S(x) → ¬ T(x)]
 ¬ ∃ x[S(x ) Λ T(x)]
• If any fleegle is a snurd then it's also a thingamabob
∀ x[(F(x) Λ S(x)) → T(x)]
 ¬ ∃ x[F(x) Λ S(x) Λ ¬ T( x)]
P. 1
Quantifiers:Dangerous situations
• Commutativity of quantifiers
∀x∀yP(x, y)  ∀y∀xP(x, y)?
YES!
∀x∃yP(x, y)  ∃y∀xP(x, y)?
NO!
DIFFERENT MEANING!
• Example:
P(x,y): x+y=0, U: Integers
∀x∃yP(x, y) is Ture
∃y∀xP(x, y) is False
P. 1
Quantifiers:Dangerous situations
• Distributivity of quantifiers over operators
∀x[P(x)ΛQ(x)]  ∀xP( x)Λ∀xQ(x)? YES!
∀x[P(x)→Q(x)] [∀xP(x)→∀xQ(x)]? NO!
• Let P(x) sometimes true, sometimes false, and
Q(x) is always false, then
∀x[P(x)→Q(x)] is False
[∀xP(x)→∀xQ(x)] is True
P. 1
Terms
•
•
•
•
•
•
•
•
Proposition
Predicate
Universal Quantifier
Existential Quantifier
Unique Existential Quantifier
De Morgan’s Laws for Quantifiers
Binding Variables
Logic Programming
P. 1
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
Introduction: Nested Quantifiers
•
•
Nested
quantifiers:
Two
quantifiers are nested if one is
within the scope of the other.
Example: xy(x+y=0)
Introduction: Nested Quantifiers
• Example:
Domain: real number.
Addition inverse: xy(x+y=0)
Commutative law for addition: xy(x+y=y+x)
Associative
law
for
addition:
xyz
(x+(y+z)=(x+y)+z)
The Order of Quantifiers
• Example:
Let Q(x,y) denote “x+y=0.” What are the truth
values of the quantifications yxQ(x,y) and
xyQ(x,y), where the domain for all
variables consists of all real numbers?
Translating Mathematical Statements into
Statements Involving Nested Quantifiers
• Example 7:
Translate the statement “Every real umber except
zero has a multiplicative inverse.” (A
multiplicative inverse of a real number x is a
real number y such that xy=1)
• HW: Example 8, p54
Translating from Nested Quantifiers
into English
• Example 9:
Translate the statement x(C(x)y(C(y)F(x,y)))
into English, where C(x) is “x has a computer,”
F(x,y) is “x and y are friends,” and the domain
for both x and y consists of all students in
your school.
•
HW: Example 10, p55.
Negating Nested Quantifiers
• Example 14:
Express the statement xy(xy=1) negation of the
statement so that no negation precedes a
quantifier.
• HW: Example 15, p57
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
Rules of Inference
• Definition:
An argument in propositional logic is a sequence of
propositions. All but the final proposition in the
argument are called premises and the final
proposition is called the conclusion. An argument is
valid if the truth of all its premises implies that the
conclusion is true.
Rules of Inference
• Definition: A theorem is a valid logical assertion
which can be proved using
– other theorems
– axioms (statements which are given to be true) and
– rules of inference (logical rules which allow the deduction
of conclusions from premises).
• A lemma (not a “lemon”) is a 'pre-theorem' or a
result which is needed to prove a theorem.
• A corollary is a 'post-theorem' or a result which
follows directly from a theorem.
Rules of Inference
• Many of the tautologies in Chapter 1 are rules of inference.
They have the form
H1 Λ H2 Λ..... Λ Hn →C
• Where Hi are called the hypotheses and C is the conclusion.
• As a rule of inference they take the symbolic form:
H1
H2
.
.
Hn
C
where  means 'therefore' or 'it follows that.'
Rules of Inference
• Examples:The tautology P Λ(P → Q) → Q becomes
P
P→Q
Q
• This means that whenever P is true and P → Q is true
we can conclude logically that Q is true.
• This rule of inference is the most famous and has the
name
– modus ponens or
– the law of detachment.
Rules of Inference
Rules of Inference for Quantifiers
• Note:
– In Universal Generalization, x must be arbitrary.
– In Universal Instantiation, c need not be arbitrary but often is assumed to be.
– In Existential Instantiation, c must be an element of the universe which makes
P(x) true.
Rules of Inference
• Example: Every man has two legs. John Smith
is a man. Therefore, John Smith has two legs.
• Define the predicates:
M(x): x is a man
L(x): x has two legs
J: John Smith, a member of the universe
Rules of Inference
• Example:
• The argument becomes
1.x[M(x) → L(x)]
2.M( J )
 L( J)
• The proof is
1. x[M(x) → L(x)] Hypothesis 1
2.M( J ) → L(J ) step 1 and UI
3.M( J ) Hypothesis 2
4.L( J) steps 2 and 3 and modus ponens
Q. E. D.
Note: Using the rules of inference requires lots of practice.
Rule of Inference for Quantified Statement
• Example 12:
Show that the premises “Everyone in this
discrete mathematics class has taken a
course in computer science” and “Marla
is a student in this class” imply the
conclusion “Marla has taken a course in
computer science.”
• HW: Example 13, p71.
Fallacies
• Fallacies are incorrect inferences.
• Some common fallacies:
–The Fallacy of Affirming the
Consequent
–The Fallacy of Denying the Antecedent
(or the hypothesis)
–Begging the question or circular
reasoning
Fallacies:
The Fallacy of Affirming the Consequent
• Example:
If the butler did it he has blood on his hands.
The butler had blood on his hands.
Therefore, the butler did it.
• This argument has the form
P→Q
Q
P
or
[(P → Q)ΛQ] → P
• which is not a tautology and therefore not a rule of
inference!
Fallacies:
The Fallacy of Denying the Antecedent (or the hypothesis)
• Example:
if the butler is nervous, he did it.
The butler is really mellow.
Therefore, the butler didn't do it.
• This argument has the form
P→Q
¬P
¬Q
or
[(P → Q)Λ ¬ P] → ¬ Q
• which is also not a tautology and hence not a rule of
inference.
Fallacies:
Begging the question or circular reasoning
• This occurs when we use the truth of
statement being proved (or something
equivalent) in the proof itself.
• Example:
Conjecture: if x2 is even then x is even.
Proof: If x2 is even then x2 = 2k for some k. Then
x = 2l for some l. Hence, x must be even.
Fallacies
• Example:
P (x): x注射疫苗
Q(x): x死亡
某報刊登：『某人於下午過世，上午有注射疫苗』，請問其
論點及目的為何？
Example:
上題中加入一個描述：”所有注射疫苗的人都會死亡”。某
人不幸過世，請問他是否有打疫苗？
Example:要如何確認(加入rules)某人是因注射疫苗過世。
HW: Example 10, p69
Terms
•
•
•
•
•
•
•
•
Argument
Premises
Conslusion
Valid
•
•
•
•
Rule of inference
Modus ponens
Modus tollensva
fallacies
Theorem
Axioms
Lemma
Corollary
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
Formal
FormalProofs
Proofs
• To prove an argument is valid or the
conclusion follows logically from the
hypotheses:
– Assume the hypotheses are true
– Use the rules of inference and logical
equivalences to determine that the conclusion
is true.
P. 1
Formal
FormalProofs
Proofs
Example:
• Consider the following logical argument:
If horses fly or cows eat artichokes, then the mosquito is the
national bird. If the mosquito is the national bird then peanut
butter takes good on hot dogs. But peanut butter tastes terrible
on hot dogs. Therefore, cows don't eat artichokes.
1. Assign propositional variables to the component
propositions in the argument:
F
A
M
P
Horses fly
Cows eat artichokes
The mosquito is the national bird
Peanut butter tastes good on hot dogs
P. 1
Formal
FormalProofs
Proofs
2. Represent the formal argument using the
variables
1.(F ν A) → M
2.M →P
3. ¬ P
¬A
P. 1
Formal
FormalProofs
Proofs
3. Use the hypotheses 1., 2., and 3. and the above rules of
inference and any logical equivalences to construct the proof.
Assertion
1.(F ν A) → M
2.M → P
3.(F ν A) → P`
4. ¬ P
5. ¬(F ν A)
6. ¬F Λ¬A
7. ¬A Λ¬F
8. ¬A
Reasons
Hypothesis 1.
Hypothesis 2.
steps 1 and 2 and hypothetical syll.
Hypothesis 3.
steps 3 and 4 and modus tollens
step 5 and DeMorgan
step 6 and commutativity of 'and'
step 7 and simplification
Q. E. D.
P. 1
Methods of Proof
• We wish to establish the truth of the
'theorem‘
P→Q.
• P may be a conjunction of other
hypotheses.
• P → Q is a conjecture until a proof is
produced.
P. 1
Methods of Proof
•
•
•
•
•
•
Trivial Proof
Vacuous Proof
Direct Proof
Indirect Proof
Proof by Contradiction
Proof by Cases
P. 1
Methods of Proof: Trivial Proof
• Trivial proof
– If we know Q is true then P → Q is true.
• Example:
– If it's raining today then the void set is a subset
of every set.
– The assertion is trivially true independent of
the truth of P.
P. 1
Methods of Proof: Vacuous Proof
• Vacuous proof
– If we know one of the hypotheses in P is false then P →
Q is vacuously true.
• Example:
– If I am both rich and poor then hurricane Fran was a
mild breeze.
• This is of the form
(P Λ ¬ P) → Q
– and the hypotheses form a contradiction.
– Hence Q follows from the hypotheses vacuously.
歐亞書局
P. 1
Methods of Proof: Direct Proof
• Direct proof
– assumes the hypotheses are true
– uses the rules of inference, axioms and any
logical equivalences to establish the truth of
the conclusion.
• Example:
歐亞書局
– Theorem: If 6x + 9y = 101, then x or y is not an integer.
– Proof: Assume 6x + 9y = 101 is true.
Then from the rules of algebra 3(2x + 3y) = 101.
But 101/3 is not an integer so it must be the case that
one of 2x or 3y is not an integer (maybe both).
Therefore, one of x or y must not be an integer.
Q.E.D.
P. 1
Methods of Proof: Indirect Proof
• Indirect proof
– A direct proof of the contrapositive:
– assumes the conclusion of P → Q is false (¬ Q is true)
– uses the rules of inference, axioms and any logical
equivalences to establish the premise P is false.
• Note, in order to show that a conjunction of
hypotheses is false is suffices to show just one
of the hypotheses is false.
P. 1
Methods of Proof: Indirect Proof
• Example:
– A perfect number is one which is the sum of all
its divisors except itself. For example, 6 is
perfect since 1 + 2 + 3 = 6. So is 28.
– Theorem: A perfect number is not a prime.
– Proof: (Indirect). We assume the number p is a
prime and show it is not perfect.
But the only divisors of a prime are 1 and itself.
Hence the sum of the divisors less than p is 1
which is not equal to p.
Hence p cannot be perfect.
Q. E. D.
P. 1
Methods of Proof:Proof by contradiction
• Proof by contradiction
– assumes the conclusion Q is false
– derives a contradiction..
P. 1
Methods of Proof:Proof by contradiction
• Example:
– Theorem: There is no largest prime number.
(Note that there are no formal hypotheses here.)
We assume the conclusion 'there is no largest prime
number' is false. There is a largest prime number. Call it
p. Hence, the set of all primes lie between 1 and p.
Form the product of these primes:
r = 2•3•5•7•11•....•p.
But r + 1 is a prime larger than p. (Why?).
This contradicts the assumption that there is a largest
prime.
Q.E.D.
P. 1
Methods of Proof:Proof by contradiction
• The formal structure of the above proof is as follows:
– Let P be the assertion that there is no largest prime.
– Let Q be the assertion that p is the largest prime.
– Assume ¬ P is true.
– Then (for some p) Q is true so ¬ P→Q is true.
– We then construct a prime greater than p so Q → ¬ Q.
– Applying hypothetical syllogism we get ¬ P → ¬ Q.
– From two applications of modus ponens we conclude
that Q is true and ¬ Q is true so by conjunction ¬ QΛQ
or a contradiction is true.
– Hence the assumption must be false and the theorem
is true.
歐亞書局
P. 1
Methods of Proof: Proof by Cases
1. Break the premise of P→Q into an equivalent
disjunction of the form
P1 ν P2 ν... ν Pn .
2. Then use the tautology
[(P1 → Q) Λ (P2 → Q) Λ... Λ(Pn → Q)]↔[(P1 ν P2 ν... ν Pn )
→ Q]
Each of the implications Pi → Q is a case.
• You must
a) Convince the reader that the cases are inclusive, i.e.,
they exhaust all possibilities
b) Establish all implications
P. 1
Methods of Proof: Proof by Cases
• Example:
– Let  be the operation 'max' on the set of
integers:
if a  b then a  b = max {a, b} = a = b  a.
– Theorem: The operation  is associative.
– For all a, b, c
(a  b)  c = a (b  c).
歐亞書局
P. 1
Methods of Proof: Proof by Cases
• Example:Proof:
– Let a, b, c be arbitrary integers.
– Then one of the following 6 cases must hold (are
exhaustive):
1. a  b  c
2. a  c  b
3. b  a  c
4. b  c  a
5. c  a  b
6. c  b  a
Case 1: a  b = a, a  c = a, and b  c = b.
Hence (a  b)  c = a = a (b  c).
Therefore the equality holds for the first case.
The proofs of the remaining cases are similar (and are
left for the student).
Q. E. D.
–
–
–
–
歐亞書局
P. 1
Mistakes in Proofs
• Example 15:
What is wrong with the “proof” that 1=2?
“Proof:” We use these steps where a and b are
two equal positive integers.
1. a=b (Given)
2. a2=ab
3. a2-b2=ab-b2
4. (a-b)(a+b)=b(a-b)
5. a+b=b
6. 2b=b
7. 2=1
•
HW: Example 15, p83
P. 1
Terms
• Conjunction
• Disjunction
• Conjecture
P. 1
Chapter 1: The Foundations:
Logic and Proofs
1.1 Propositional Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy
Existence Proofs
• We wish to establish the truth of
xP( x).
• Constructive existence proof:
– Establish P(c) is true for some c in the universe.
– Then  xP( x) is true by Existential Generalization (EG).
• Example:
Theorem: There exists an integer solution to the
equation x2+y2=z2.
Proof: Choose x = 3, y = 4, z = 5.
P. 1
Existence Proofs
• Example:
–Theorem: There exists a bijection
from A= [0,1] to B= [0, 2].
–Proof:
–we could have chosen g(x) = x/2 and
obtained a bijection directly.
• HW: Prove that g(x) above is a
bijection function.
歐亞書局
P. 1
Nonconstructive Existence Proof
• Nonconstructive existence proof.
– Assume no c exists which makes P(c) true and
derive a contradiction.
• Example:
– Theorem: There exists an irrational number.
– Proof:
Assume there doesn’t exist an irrational number.
Then all numbers must be rational.
Then the set of all numbers must be countable.
Then the real numbers in the interval [0, 1] is a countable set.
But we have already known this set is not countable.
Hence, we have a contradiction (The set [0,1] is countable and not
countable).
Therefore, there must exist an irrational number.
Q. E. D.
– Note: we have not produced such a number!
HW: Prove that [0,1] is not countable.
P. 1
Disproof by Counterexample
• Recall that x ¬ P(x)↔¬ xP(x ).
• To establish that ¬xP(x ) is true (or xP(x)
is false) construct a c such that ¬ P(c) is true
or P(c) is false.
• In this case c is called a counterexample to
the assertion xP(x)
P. 1
Disproof by Counterexample
• Example:
Prove or disprove that “every positive integer
is the sum of the squares of two integers.
Example: 5=12+22; 34=32+52.
Counterexample:
P. 1
Nonexistence Proofs
• Nonexistence Proofs
– We wish to establish the truth of ¬  xP( x)
(which is equivalent to x ¬ P(x)).
– Use a proof by contradiction by assuming there
is a c which makes P(c) true.
P. 1
Universally Quantified Assertions
• We wish to establish the truth of xP(x)
• We assume that x is an arbitrary member of
the universe and show P(x) must be true.
Using UG it follows that xP(x) .
P. 1
Universally Quantified Assertions
• Example:
– Theorem: For the universe of integers, x is even iff
x2 is even.
Proof: The quantified assertion is  x[x is even ↔ x2
is even]
We assume x is arbitrary.
Recall that P ↔ Q is equivalent to (P→Q) Λ (Q → P).
P. 1
Universally Quantified Assertions
• Example:
– Case 1 . We show if x is even then x2 is even using a
direct proof
If x is even then x = 2k for some integer k.
Hence, x2 = 4k2 which is even since it is an integer
which is divisible by 2.
This completes the proof of case 1.
P. 1
Universally Quantified Assertions
• Example:
– Case 2 . We show that if x2 is even then x must be even .
We use an indirect proof:
Assume x is not even and show x2 is not even.
If x is not even then it must be odd.
So, x = 2k + 1 for some k.
Then x2 = (2k+1) 2 = 2(2k 2+2k)+1 which is odd and hence not
even.
This completes the proof of the second case.
Therefore we have shown x is even iff x2 is even.
Since x was arbitrary, the result follows by UG.
Q.E.D.
P. 1
Rosen to his student
• Dear students: Learning how to construct
proofs is probably one of the most difficult
things you will face in life. Few of us are
gifted enough to do it with ease. One only
learns how to do it by practicing .
P. 1