Transcript Slide 1

Original author of the slides:
Vadim Bulitko
University of Alberta
http://www.cs.ualberta.ca/~bulitko/W04
Modified by T. Andrew Yang
([email protected])
1
Conditionals
• “If I go to Save-on-Foods tomorrow, I will buy
oranges there”
• S = (go to SOF)  (buy oranges)
• When is S true?
– When I went to SOF and bought oranges
– When I didn’t go there at all!
• When is S false?
– When I went there but didn’t buy oranges
2
Truth Table
• N independent atomic formulae (variables)
 2N rows
• N=20: 220 ~= 1 million
• Consider A  B:
A
F
F
T
T
B
F
T
F
T
AB
T
T
F
T
3
More terminology
• AB
• A is called:
– Assumption
– Premise
– Antecedent
• B is called
– Conclusion
4
Bi-Conditionals
• “Marion will take 272 if and only if Norma does
so”
• S = (Marion takes 272)  (Norma takes 272)
• When is S true?
– When Marion takes it and Norma takes it
– When Marion doesn’t take it and neither does Norma
• When is S false?
– When one of them takes it but not the other
5
Truth Tables
•
•
•
•
•
A
F
F
T
T
B
F
T
F
T
AB
T
F
F
T
6
if, iff, only if, and Daily Life
• Suppose:
“Buy Ferrari” = B, “Ferrari is on sale” = S
• I will buy a Ferrari if it is on sale:
• S  B (or B if S)
• I will buy a Ferrari if and only if it is
on sale:
• S  B (or B iff S)
• I will buy a Ferrari only if it is on
sale: B only if S
• ~S  ~B
• B  S (Note: not equivalent to S  B)
• Exercise: Show the truth tables for
B if S, B iff S, and B only if S.
7
if, iff, only if
B
S
T
F
B if S
(S  B)
T
T
B iff S
(B  S)
T
F
B only if S
(B  S)
T
F
T
T
F
F
T
F
F
T
F
T
T
T
8
if, iff, only if
•
•
•
•
•
A = ‘You will get an A’
F = ‘You score 95 or higher in the final exam’
P1= A if F
P2= A iff F
P3= A only if F
• Suppose F is true. In which case will an A grade will
guaranteed? P1? P2? P3?
• In P1, F is sufficient for getting an A
• In P2, F is the only way to get an A
• In P3, F is necessary (but not sufficient) to get an A
9
Sufficient & Necessary Conditions
• Suppose the Ferrari salesperson wants to figure
out when you are ready to buy one of their
cars…
B = “ready to buy”
X = some condition of you
• If they find X such that: X  B
– Then they have a sufficient condition
– Example: X = “got a UofA scholarship”
• If they find X such that: B  X
– Then they have a necessary condition
– Example: X = “it is winterized”
10
Summary
• Suppose X is a statement
• A is a sufficient condition for X iff we can
prove that:
“A implies X”
• A is necessary condition for X iff we can prove
that:
“X implies A”
• R = “it rains”, W = “the lawn will be wet”, and
RW.
R is a sufficient condition for W, and W is a necessary
condition for R.
11
Summary (cont.)
• In the Ferrari example
B if S (or SB): S is a sufficient condition for B, and
B a necessary condition for S.
B iff S (or BS): S is a sufficient and necessary
condition for B, and B a sufficient and necessary
condition for S.
B only if S (or BS): B is a sufficient condition of S,
and S a necessary (but not sufficient) condition for
B.
That is, ‘being on sale’ does not guarantee a ‘buy’.
12
Summary (cont.)
• Suppose X is a statement
• A is a criterion for X iff we can prove
that: "X holds if and only if A holds”
Q1: Is W in RW a criterion for R? Is R a
criterion for W?
Q2: Is ‘K has won a presidential campaign’ a
criterion for ‘K is the President’?
Examples of criterion?
13
• Let A be the set of effects when it rains.
• Let B be the set of causes that may cause a
wet lawn.
• What is A ∩ B?
• What is A – B?
• What is B – A?
• Does A U B mean anything?
14
Questions?
15
Contradictions & Tautologies
• Contradiction:
– A statement that is always false regardless of
the values of its variables
• Examples: A & ~A
• Tautology:
– A statement that is always true regardless of
the values of its variables
• Examples: A v ~A
16
Contingencies
• What if I have a formula that is sometimes
true and sometimes false?
• It is called a contingency
• Example:
• A&B
• If A and B are independent variables
17
Interpretation
• In propositional logic, interpretation is a
mapping from symbols in your formulae to
{true, false}
• Example:
– Formula:
– Interpretation:
AvB
A = true, B = false
18
Formula Classification
• Tautology :
– all interpretations satisfy the formula
• Contradiction :
– all interpretations falsify the formula
• Contingency :
– some interpretations satisfy and some falsify
the formula
19
Logic Equivalence
• Propositions/statements/formulae A and B
are logically equivalent when:
A holds if and only if B holds
• Notation:
AB
• Examples:
AvAA
A v ~A  true
20
Equivalence & Tautology
•
•
•
•
•
•
•
•
Suppose A and B are logically equivalent
Consider proposition (A  B)
What can we say about it?
It is a tautology!
Why?
A B
AB
F F
T
T T
T
21
More Equivalences
• Alex is not unemployed
– Alex is employed
• P  ~(~P) : Double-negation
• It is not true that she is single and she is cute
– She is not single or she is not cute
• ~(A & B)  ~A v ~B : De Morgan’s law
• It is not true that she is single or she is cute
– She is not single and she is not cute
• ~(A v B)  ~A & ~B : De Morgan’s law
22
Boolean Algebra
• Page 14 presents Theorem 1.1.1 with 21
equivalences
• However, only the first 10 are needed
• The rest can be derived from them
• Example: let’s prove that P v P  P
PvCP
P v (P & ~P)  P
(P v P) & (P v ~P)  P
(P v P) & T  P
PvPP
(4)
(5)
(3)
(5)
(4)
• Alternatively, use a Truth Table.
23
Proving Equivalences
• Suppose P and Q can take on T and F
only
• Then all equivalences can be proven by
definition using truth tables
• An example: Prove P  Q  ~P v Q
24
Uses of Equivalences
• Simplification
• Suppose someone gives you
~P v (AB) v ~(C v D  H) v P v XY
• and asks you to compute it for all possible
input values
• You can either immediately draw a truth
table with 28 = 256 rows
• Or you can simplify it first
25
Simplification
•
•
•
•
~P v (AB) v ~(C v D  H) v P v XY
~P v P v (AB) v ~(C v D  H) v XY
T v (AB) v ~(C v D  H) v XY
T
• The statement is a tautology – always
true…
26
Test Drive
• Let’s take our equivalence tool box for a
spin…
• What can we tell about
AB
• and its contrapositive:
~B  ~A
• ?
• They are equivalent !
27
Proof?
• Truth-tables
• Equivalences
AB
~A v B
B v ~A
~B  ~A
• Isn’t this fun?
28
Test Drive
• Let’s try another one!
• What can we tell about
AB
• and its inverse:
~A  ~B
•
•
•
•
?
Oh-oh…
They are not equivalent!
Counter-model: A is false and B is true…
29
Summary
• Implication
AB
• is equivalent to:
~B  ~A : its contrapositive
• But is not equivalent to:
~A  ~B : its inverse
• Or to:
B  A : its converse
30
Another Lesson Learned
• Proving equivalences
– via truth-tables
– via other equivalences
• Proving non-equivalence:
– Finding an instantiation that
makes one formula hold and
the other doesn’t
31
Bi-conditionals
• How can we express:
AB
• With &, v, ~ ?
• It is simply:
(A & B) v (~A & ~B)
• How can we express it with , & ?
• Why, but of course it is just:
(A  B) & (B  A)
32
Another Spin…
• Ok, let’s try this fun ride:
(P  Q) & P
• In English it would sound:
(If P is true then Q is true) and (P is true)
• What does it tell us?
– Naturally Q is true!
• In Logic, is this the correct result?
• Let’s prove it…
33
Proving…
•
(P  Q) & P
 (~P v Q) & P
 (~P & P) v (Q & P) (distributive law)
FvQ&P
Q&P
• The result is Q & P, not Q!
• Is Q & P  Q ?
• No -- counter-model: Q=T and P=F …
• So, what have we learned from this?
34
logical expression vs inference
• So, what have we learned from this?
A logical expression cannot be interpreted as an English
statement.
The expression (P  Q) & P, for example, should be
interpreted by considering possible values for both P
and Q. That is, the variables P and Q can be either
True or False, and not always True (as is in the
English interpretation).
• c.f., inference
P  Q, and
P
Therefore, Q.
35
Entailment (Implication)
• A collection of statements P1,…,Pn (premises) entails
statement Q (conclusion) if and only if:
Whenever all premises hold the conclusion holds
• Example:
– Premises:
• P1 = “If Socrates is human then Socrates is mortal”
• P2 = “Socrates is human”
– Conclusion:
• Q = “Socrates is mortal”
• P1 & P2 |= Q
• P1 & P2  Q
• P1 & P2. Therefore, Q.
• See http://en.wikipedia.org/wiki/Logical_implication for
detailed discussion.
36
Valid/Invalid Arguments
• Suppose someone makes an argument:
– P1,..,PN therefore Q
• The argument is called valid iff:
– P1,…,PN logically entail Q
• That is:
– Q must hold when all Pi hold
• Otherwise the argument is called invalid
37
Questions?
38
Modus Ponens
• The “generalized” argument
P1 = X  Y
P2 = X
entails
Q =Y
• …is much more useful!
• Why?
“method of
affirming” (Lat.)
• Because it captures the essence of both
arguments and can be used for infinitely many
more
39
Valid Arguments (Revisited)
• Suppose someone makes an argument:
– P1,..,PN therefore Q
• The argument is called valid iff:
– P1,…,PN logically entail Q
• That is:
– For any interpretation I that satisfies all Pj,
interpretation I must necessarily satisfy Q
• Usually: Pj and Q are somehow related formulae
and P1 & … & PN can be true or false depending
on the interpretation I
40
How Do We:
• Tell between a valid argument and an invalid argument:
– People are mortal. Socrates is a man. Socrates is mortal.
– Ducks fly. F-16 flies. F-16 is a duck.
• Prove that something logically follows from something
else:
– 1: Everybody likes Bob
– 2: Everybody likes someone
• Prove that something is logically equivalent to something
else:
– 1: Everybody likes cream and sugar
– 2: Everybody likes cream and everybody likes sugar
• Prove that there is a contradiction?
41
Propositional Logic
• Method #1:
– Go through all possible interpretations and
check the definition of valid argument
• Method #2:
– Use derivation rules to get from the premises
to the conclusion in a logically sound way
• “derive the conclusions from premises”
42
Method #1
• Section 1.3 in the text proves many
arguments/inference rules using truth
tables
• Suppose the argument is:
P1,…,PN therefore Q
• Create a truth table for formula
X = (P1 & … & PN  Q)
• Check if X is a tautology
43
But Why? Recall:
• Formula A entails formula B
iff (A  B) is a tautology
• In general:
– premises P1,…,PN entail Q
– iff
– formula F=(P1 & … & PN  Q)
– is a tautology
44
Example #1
•
•
•
•
PvQvR
~R
entails
PvQ
• valid/invalid?
• (example 1.3.2 in the book, p. 31)
45
Example #2
•
•
•
•
PvQvR
~R
entails
Q
• valid/invalid?
46
Example #3
•
•
•
•
PQ
P
entails
Q
• valid/invalid?
• Modus ponens (p.31)
47
Example #4
•
•
•
•
PQ
Q
entails
P
• valid/invalid?
48
Example #5
•
•
•
•
PQ
~Q
entails
~P
• valid/invalid?
• Modus tollens (p.32)
49
Example #6
• PQ
• entails
• ~Q  ~P
• valid/invalid?
• In fact, we proved last time that:
• (P  Q)  (~Q  ~P)
50
Pros & Cons
• Method #1:
– Pro: straight-forward, not much creativity 
machines can do
– Con: the number of interpretations grows
exponentially with the number of variables 
cannot do for many variables
– Con: in predicate and some other logics even
a small formula may have an infinite number
of interpretations
51
Method #2 : Derivations
• To prove that an argument is valid:
– Begin with the premises
– Use valid/sound inference rules
– Arrive at the conclusion
52
Inference Rules
• But what are these “inference rules”?
• They are simply…
– …valid arguments!
• Example:
–X&Y
–X&YZ&W
– therefore
–Z&W
by modus ponens
53
Example #1
•
•
•
•
•
•
•
•
•
(X&Y  Z&W) & K
X&Y
therefore
Z&W
How?
(X&Y  Z&W) & K
X&Y  Z&W by conjunctive simplification
X&Y
Z&W
by modus ponens
54
Derivations
• The chain of inference rules that starts
with the premises and ends with the
conclusion
• …is called a derivation:
– The conclusion is derived from the premises
• Such a derivation makes a proof of an
argument’s validity
55
Example #1
•
•
•
•
•
•
•
•
•
(X&Y  Z&W) & K
X&Y
therefore
Z&W
derivation
How?
(X&Y  Z&W) & K
X&Y  Z&W by conjunctive simplification
X&Y
Therefore Z&W
by modus ponens
56
Fallacies
• An error in derivation leading to an invalid
argument
• Possible causes:
– Vague formulations of premises/conclusion
– Missing steps
– Using non-sound inference rules, e.g.:
• Converse error
• Inverse error
57
Converse Error
•
•
•
•
If John is smart then John makes a lot of money
John makes a lot of money
Therefore:
John is smart
• Tries to use this non-sound “inference rule”:
AB,
B
Thus: A
58
Inverse Error
•
•
•
•
If John is smart then John makes a lot of money
John is not smart
Therefore:
John doesn’t make a lot of money
• Tries to use this non-sound “inference rule”:
AB,
~A
Thus: ~B
59
Truth of facts vs. Validity of Arguments
• The premises are assumed to be true ONLY in
the context of the argument (i.e., a valid
argument may include false premises)
• The following argument is valid:
–
–
–
–
If John Lennon was a rock star then he was a woman
John Lennon was a rock star
Thus:
John Lennon was a woman
• But the 1st premise doesn’t hold under the
common sense interpretation
60
Inference Rules
• Table 1.3.1 on page 40
• If practice with the rules then will be more
fluent using them
• If are more fluent using them then will be
more likely to get a better mark on exams
61
Summary
• Equivalence:
AB
A holds iff B holds
A is a criterion for B
B is a criterion for A
A entails B
B entails A
A and B are “equivalently strong”
Formula F=(AB) is a tautology
62
Summary
• Entailment (or implication)
– A entails B
– B follows from A
– AB is a valid argument
– A is a sufficient condition for B
– B is a necessary condition for A
– If A holds then B holds
– A may be “stronger than” B
– Formula F=(AB) is a tautology
63
The Big Picture
• Logic is being used to verify validity of
arguments
• An argument is valid iff its conclusion logically
follows from the premises
• Derivations are used to prove validity
• Inference rules are used as part of derivations
64
Questions?
65