Transcript Discrete Structures & Algorithms Propositional Logic

Discrete Structures & Algorithms
Propositional Logic
EECE 320 : UBC : Spring 2009
1
Summary so far
•
Pancake sorting
•
•
•
•
•
A problem with many applications
Bracketing (bounding a function)
Proving bounds for pancake sorting
You can make money solving such problems (Bill Gates!)
Illustrated many concepts that we will learn in this course
•
•
•
•
Proofs
Sets
Counting
Performance of algorithms
2
Propositional logic
• Logic of compound statements built from
simpler statements using Boolean
connectives.
• Building block for mathematics and
computing.
• Direct applications
•
•
•
Design of digital circuits
Expressing conditions in programs
Database queries
3
A sandwich is better than God
• Nothing is better than God.
• A sandwich is better than nothing.
• Thus, a sandwich is better than God.
4
What is propositional logic?
•
•
•
The simplest form of mathematical logic.
Develops a symbolic language to treat
compound and complex propositions and their
logical relationship in an abstract manner.
And, before we get ahead of ourselves... what
is a proposition?
•
A declarative statement that is either true or
false (but not both!).
5
Examples of propositions
• September 6 2007 is a Thursday.
• September 6 2007 is a Friday.
• 3+2 equals 7.
• There is no gravity.
The following are not propositions.
• Do your homework.
• What is the time?
• 3+4.
6
Propositions and their negations
Suppose p is a proposition, then the
negation of p is written as ¬p.
The negation of proposition p implies that
“It is not the case that p.”
Examples
p: It is raining. ¬p: It is not raining.
p: 3+2=5. ¬p: 3+2≠5.
Notice that ¬p is a proposition too.
7
Conjunctions and disjunctions
• Elaborate ways of saying “and” and “or”
• Consider two propositions, p and q
•
•
Conjunction (“and”): p Λ q
•
•
It is a bright and windy day.
The day has to be both bright and windy.
Disjunction (“or”): p V q
•
•
To ride the bus you must have a ticket or hold a pass.
One of the two conditions (“have a ticket” or “hold a
pass”) suffices. (Though both could be true.)
8
“Exclusive or”
•
•
•
In day-to-day speech, sometimes we use “or”
as an “exclusive or”.
“I will take a taxi or a bus from the airport.”
•
•
Only one of “taxi” or “bus” is implied.
To be precise, one would need to say “I will take
either a taxi or a bus from the airport.”
“Exclusive or” XOR is denoted by the symbol.
9
Truth tables
•Truth tables can be used to evaluate
statements. A simple proposition can either be
“true” or “false”.
Negation
p
¬p
T
F
F
T
Conjunction (“and”)
Disjunction (“or”)
p
q
pΛq
p
q
pVq
F
F
T
T
F
T
F
T
F
F
F
T
F
F
T
T
F
T
F
T
F
T
T
T
Notice that the conjunction and disjunction of two
propositions are also propositions (and, along with
negation, are called compound propositions).
10
Logical equivalence
Two statements are logically equivalent if
and only if they have identical truth tables.
The simplest example is ¬(¬p) ≡ p.
11
Implication
• Another important logical construct is
implication
• This is akin to saying “If ... then ...”
• When proposition p holds then q holds.
•
•
Notation: p → q.
Example: If I am on campus, I study.
•
•
p: I am on campus.
q: I study.
12
Truth table for implication
• p → q: If p, then q.
• If p is true, q must be true for the implication
to hold.
• p is the assumption/premise/antecedent.
• q is the conclusion/consequent.
Implication
p
q
p→q
T
T
F
F
F
T
F
T
F
T
T
T
13
An equivalent for implication
Is there an expression that is equivalent to p → q
but uses only the operators ¬, Λ, V?
Implication
Consider the
proposition ¬p V q
p
q
p→q
F
F
T
T
F
T
F
T
T
T
F
T
p
q
¬p
¬p V q
F
F
T
T
F
T
T
T
T
F
F
F
T
T
F
T
14
Proving other equivalences
• Easy to use truth tables and show logical
equivalence.
• Example: distributivity
•
•
•
p Λ (q V r) ≡ (p V q) Λ (p V r)
Do this as an exercise.
You would have seen these forms in earlier
courses on digital logic design.
15
Logical equivalences
• The basic laws
•
•
•
•
•
•
•
•
•
Identity
Domination
Propositions that are logically equivalent.
You will need to know them, although we
will not elaborate on them in lecture.
In the text (Rosen): Chapter 1, Section 2.
Idempotence
Negation and double negation
Commutation
Association
Distribution
Absorption
De Morgan’s laws
16
Variations on a proposition
• Given a proposition p → q, there are other
propositions that can be stated.
•
three (contrapositive,
converse,
Example: If a function isOf
notthe
continuous,
it is not differentiable.
inverse), which is not like the other two?
•
Example: If a function is differentiable, then it is continuous.
• Contrapositive: ¬q → ¬p
• Converse: q → p
•
Example: If a function is not differentiable, then it is not continuous.
• Inverse: ¬p → ¬q
•
Hint: One is a logical equivalent of the
original proposition.
The “contrapositive” is equivalent to the
original proposition.
Example: If a function is continuous, then it is differentiable.
17
Tautology & Contradiction
• A proposition that is always true is called a
tautology.
•
Example: p V ¬p
• A proposition that is always false is called a
contradiction.
•
Example: p Λ ¬p
18
Bi-conditionals (“if and only if”)
• If p and q are two propositions, then p ↔ q is a
bi-conditional proposition.
•
•
•
p if and only if q. (p iff q)
p is necessary and sufficient for q.
If p then q, and conversely.
• Example: The Thunderbirds win if and only if
it is raining.
• p ↔ q is the same as (p → q) Λ (q → p).
•
Are there other other equivalent statements?
19
What is an argument?
•
•
A sequence of statements the ends with a
conclusion.
(Not the common language usage of a debate or dispute.)
Structure of an argument
Statement 1 (p1)
Statement 2 (p2)
...
Statement n (pn)
Statement n+1 (conclusion)
20
premises
or
antecedents
Example
• Premises
•
•
“If you have a current password, you can log
onto the computer network.”
“You have a current password.”
• Conclusion
•
“Therefore, you can log onto the computer
network.”
21
Representing an argument
An argument is sometimes written as follows:
premises
conclusion
22
Valid arguments
• An argument is valid if and only if it is
impossible for all the premises to be true and
the conclusion to be false.
• How do we show that an argument is valid?
•
•
We can use a truth table, or
We can show that (p1 Λ p2 Λ ... Λ pn → pn+1) is a
tautology using some rules of inference.
23
Why use rules of inference?
• Constructing a truth table is time consuming!
• If we have n propositions, what is the size of
the truth table? 2n, which means that the table
doubles in size with every proposition.
Implication
p
q
F
F
T
T
F
T
F
T
p→q
T
T
F
T
Two propositions are
involved in an implication,
therefore the truth table
has 22 = 4 rows.
24
Rules of inference
modus ponens
“method of affirming”
25
Rules of inference
modus tollens
“method of denying”
26
Rules of inference
generalization
specialization
27
Rules of Inference
More rules of inference listed in the text.
Try proving them as an exercise.
Chapter 1, Section 5 (Rosen).
•
pq
qr
pr
Rule of hypothetical
syllogism
pq
p
q
Rule of disjunctive
syllogism
•
28
Inference Rules for Quantifiers
•
P(o)
•
More rules of inference listed in the text.
Try proving them as an exercise.
Chapter 1, Section 5 (Rosen).
x P(x)
(substitute any specific object o)
P(g)
x P(x)
•
P(c)
•
(for g a general element.)
x P(x)
(substitute a new constant c)
P(o)
object o)
x P(x)
(substitute any extant
29
Formal Proofs
• A formal proof of a conclusion C, given
premises p1, p2,…,pn consists of a sequence
of steps, each of which applies some
inference rule to premises or previouslyproven statements to yield a new true
statement (the conclusion).
• A proof demonstrates that if the premises are
true, then the conclusion is true.
30
Formal Proof Example
• Suppose we have the following premises:
“It is not sunny and it is cold.”
“We will swim only if it is sunny.”
“If we do not swim, then we will canoe.”
“If we canoe, then we will be home early.”
• Given these premises, prove the theorem
“We will be home early” using inference rules.
31
Proof Example cont.
• Let us adopt the following abbreviations:
•
sunny = “It is sunny”; cold = “It is cold”;
swim = “We will swim”; canoe = “We will
canoe”; early = “We will be home early”.
• Then, the premises can be written as:
(1) sunny  cold (2) swim  sunny
(3) swim  canoe (4) canoe  early
32
Proof Example cont.
• Step
Proved by
1. sunny  cold
Premise #1.
2. sunny
Simplification of 1.
3. swimsunny
Premise #2.
4. swim
Modus tollens on 2,3.
5. swimcanoe Premise #3.
6. canoe
Modus ponens on 4,5.
7. canoeearly
Premise #4.
8. early
Modus ponens on 6,7.
33
Proofs and theorems
A theorem is a statement that can be shown
to be true. A proof is the means of doing so.
Axioms,
postulates,
hypotheses
and previously
proven
theorems
Rules of
inference
Proof
34
Common Fallacies
• A fallacy is an inference rule or other
proof method that is not logically valid.
•
A fallacy may yield a false conclusion!
• Fallacy of affirming the conclusion:
•
“pq is true, and q is true, so p must be true.” (No,
because FT is true.)
• Example:
•
•
If you do every problem in the book, then you will
learn mathematics. You learned mathematics.
Therefore you did every problem in the book
(incorrect!).
35
Common Fallacies
• Fallacy of denying the hypothesis:
•
“pq is true, and p is false, so q must be
false.” (No, again because FT is true.)
• Example
•
•
If you do every problem in the book, then
you will learn mathematics. You did not
do every problem in the book.
Therefore you did not learn mathematics
(incorrect!).
36
•
Common fallacies:
The fallacy of (explicitly or implicitly)
Circular
Reasoning
assuming the very statement you are
trying to prove in the course of its proof.
Example:
• Prove that an integer n is even, if n
2
is
even.
• Attempted proof: “Assume n
is even.
Then n2=2k for some integer k. Dividing
both sides by n gives n = (2k)/n = 2(k/n).
So there is an integer
(namely
/n) do
Begsj the
question:kHow
show that j=k/n=n/2
is an integer,
such that n=2j. you
Therefore
n is even.”
2
37
without
first assuming that n is even?
A Correct Proof
• Prove that an integer n is even, if n
2
38
is even.
Proof Methods for Implications
• For proving implications pq, we have:
• Direct proof: Assume p is true, and prove q.
• Indirect proof: Assume q, and prove p.
• Vacuous proof: Prove p by itself.
• Trivial proof: Prove q by itself.
• Proof by cases:
Show p(a  b), and (aq) and (bq).
39
Direct Proof Example
• Definition: An integer n is called odd iff
n=2k+1 for some integer k; n is even iff
n=2k for some k.
• Theorem: (For all numbers n) If n is an
odd integer, then n2 is an odd integer.
• Proof: If n is odd, then n = 2k+1 for
some integer k. Thus, n2 = (2k+1)2 = 4k2
+ 4k + 1 = 2(2k2 + 2k) + 1. Therefore n2 is
of the form 2j + 1 (with j the integer 2k2
40
+ 2k), thus n2 is odd.
□
Indirect Proof Example
• Theorem: (For all integers n)
If 3n+2 is odd, then n is odd.
• Proof: Suppose that the conclusion is false,
i.e., that n is even. Then n=2k for some
integer k. Then 3n+2 = 3(2k)+2 = 6k+2 =
2(3k+1). Thus 3n+2 is even, because it equals
2j for integer j = 3k+1. So 3n+2 is not odd. We
have shown that ¬(n is odd)→¬(3n+2 is odd),
thus its contra-positive (3n+2 is odd) → (n is
odd) is also true. □
41
Vacuous Proof Example
• Theorem: (For all n) If n is both odd and even,
then n2 = n + n.
• Proof: The statement “n is both odd and even”
is necessarily false, since no number can be
both odd and even. So, the theorem is
vacuously true. □
42
Trivial Proof Example
• Theorem: (For integers n) If n is the sum of
two prime numbers, then either n is odd or n
is even.
• Proof: Any integer n is either odd or even. So
the conclusion of the implication is true
regardless of the truth of the antecedent.
Thus the implication is true trivially. □
43
Proof by Contradiction
• A method for proving p.
• Assume p, and prove both q and q for
some proposition q. (Can be anything!)
• Why does it work?
• Thus p (q  q)
• (q  q) is a trivial contradiction, equal to F
• Thus pF, which is only true if p=F
• Thus p is true.
44
Proof by Contradiction Example
• Theorem:
• Proof:
2
•
•
•
•
•
sqrt(2) is irrational.
Assume 21/2 were rational. This means there
are integers i,j with no common divisors such
that 21/2 = i /j.
Squaring both sides, 2 = i2/j2, so 2j2 = i2. So i2 is
even; thus i is even.
Let i =2k. So 2j2 = (2k)2 = 4k2. Dividing both
sides by 2, j2 = 2k2.
Thus j2 is even, so j is even.
But then i and j have a common divisor, namely
45
2, so we have a contradiction.
□
Review: Proof Methods So Far
• Direct, indirect, vacuous, and trivial proofs of
statements of the form pq.
• Proof by contradiction of any statements.
• Next: Constructive and nonconstructive
existence proofs.
46
Proving Existence
• A proof of a statement of the form x P(x) is
called an existence proof.
• If the proof demonstrates how to actually find
or construct a specific element a such that
P(a) is true, then it is a constructive proof.
• Otherwise, it is nonconstructive.
47
Constructive Existence Proof
• Theorem: There exists a positive integer n that
is the sum of two perfect cubes in two
different ways:
•
equal to j3 + k3 and l3 + m3 where j, k, l, m are
positive integers, and {j,k} ≠ {l,m}
• Proof: Consider n = 1729, j = 9, k = 10,
l = 1, m = 12. Now just check that the
equalities hold.
48
Nonconstructive Existence Proof
• Theorem:
“There are infinitely many prime
numbers.”
• Any finite set of numbers must contain
a maximal element, so we can prove the
theorem if we can just show that there
is no largest prime number.
• I.e., show that for any prime number,
there is a larger number that is also
prime.
• More generally: For any number,  a
larger prime.
49
The proof, using proof by
cases...
• Given n>0, prove there is a prime p>n.
• Consider x = n!+1. Since x>1, we know
(x is prime)(x is composite).
• Case 1: x is prime. Obviously x>n, so let p=x
and we’re done.
• Case 2: x has a prime factor p. But if pn,
then p mod x = 1. So p>n, and we’re done.
50
Pancake numbers
• How did we prove the bounds on P ?
• n  P  2n – 3
• What are the propositions involved?
n
n
51
Wrap up
•Propositional logic
• Or propositional calculus
• Truth tables
• Logical equivalence
• Basic laws
•Rules of inference
• Arguments
• Premises and conclusions
•Proofs
52