Transcript Logical and Rule-Based Models I

Logical and Rule-Based
Reasoning
Part I
Logical Models and Reasoning
Big Question:
Do people think logically?
Exercise
You are given 4 cards each with a letter on one side, and
a number on the other. You can see one side of each
card only:
1
2
3
4
E
7
K
2
Rule: “if a card has a vowel on one side, then it
has an odd number on the other”
In order to check whether the rule is true of these cards,
what is the minimal number of cards cards do you need
to turn over and which ones?
Exercise
Now assume each card has a beverage on one
side, and the drinker's age on the other :
1
2
Beer
Coke
3
4
23
19
years
years
Rule: “if someone drinks beer, then she is 21
years or older”
In order to check whether the rule is true of these cards,
what is the minimal number of cards cards do you need
to turn over and which ones?
Logical Reasoning
The goal is find a way to


state knowledge explicitly
draw conclusions from the stated knowledge
Logic





A "logic" is a mathematical notation (a language) for
stating knowledge
The main alternative to logic is "natural language" i.e.
English, Swahili, etc.
As in natural language the fundamental unit is a
“sentence” (or a statement)
Syntax and Semantics
Logical inference
Propositional Logic: Syntax
Sentences


represented by propositional symbols (e.g., P,
Q, R, S, etc.)
logical constants: True, False
Connectives: ~, , , , 

 is also shown as  and  as 
Examples:
P  (Q  ~ R)
P  (Q  ~ Q )  (~ R  P )
( P  Q )  (Q  P )
( P  Q )  (~ P  Q )
Interpretations and Validity
A logical sentence S is satisfiable if it is
true at least in one situation

(under at least one “interpretation”)
S is valid if it is true under all
interpretations (S is a tautology)
S is unsatisfiable if it is false for all
interpretations (S is inconsistent)
A sentence T follows (is entailed by) S, if
any time S is true, T is also true
Propositional Logic: Semantics
In propositional logic, the semantics of connectives are
specified by truth tables:
P
Q
~P
P Q
P Q
F
F
T
T
F
T
F
T
T
T
F
F
F
F
F
T
F
T
T
T
P Q P Q
T
T
F
T
T
F
F
T
Each assignment of truth values to individual
propositions (e.g., P, Q, R) in the sentence represents
one interpretation  a row in the truth table
Truth tables can also be used to determine the validity of
sentences
Notes on Implication
If p and q are both true, then p  q is true.


If 1+1 = 2 then the sun rises in the east.
Here p: "1+1 = 2" and q: "the sun rises in the east."
If p is true and q is false, then p  q is false.




When it rains, I carry an umbrella.
p: "It is raining," and q: "I am carrying an umbrella."
we can rephrase as: "If it is raining then I am carrying an
umbrella."
On days when it rains (p is true) and I forget to bring my umbrella
(q is false), the statement p  q is false
If p is false, then p  q is true, no matter whether q is
true or not. For instance:

If the moon is made of green cheese, then I am the King of
England.
Notes on Implication
Using truth tables we
notice that the only
way the implication p
 q can be false is
for p to be true and q
to be false.

In other words, p  q
is logically equivalent
to (~p) \/ q.
p  q  (~p) \/ q
"Switcheroo" law
Propositional Inference
Let S be (A \/ C) /\ (B \/ ~C) and let R be
A \/ B. Does R follow from S?

check all possible interpretations (involving A,
B, and C); R must be true whenever S is true
A
F
F
F
F
T
T
T
T
B
F
F
T
T
F
F
T
T
C
F
T
F
T
F
T
F
T
A C
F
T
F
T
T
T
T
T
B ~C
T
F
T
T
T
F
T
T
R
F
F
F
T
T
F
T
T
S = A B
F
F
T
T
T
T
T
T
Checking Validity and Equivalences
Suppose we want to determine if a sentence:
(PQ)(~PQ)
is valid:


Construct the truth table for the sentence using all possible
combinations of true and false assigned to P and Q
As intermediate steps, can create columns for different
components of the compound sentence
P
Q
~P
~P Q
P Q
(P Q) ( ~P Q)
F
F
T
T
F
T
F
T
T
T
F
F
T
T
F
T
T
T
F
T
T
T
T
T
This sentence is a tautology because it is true under all interpretations
Some Useful Tautologies
(equivalences)
( P  Q)  (P  Q)
( P  Q)  (P  Q)
Conversion between => and \/
(( P  Q)  R)  (P  Q  R)
( P  Q)  (P  Q)
( P  Q)  (P  Q)
P  (Q  R)  ( P  Q)  ( P  R)
P  (Q  R)  ( P  Q)  ( P  R)
DeMorgan’s Laws
Distributivity
Using Equivalences: Example
Some Online Practice Exercises
http://people.hofstra.edu/faculty/Stefan_W
aner/RealWorld/logic/logic3.html
More Tautologies and Equivalences
More Tautologies and Equivalences
Can also check it with truth tables:
More Tautologies and Equivalences
More Online Practice Exercises
http://people.hofstra.edu/faculty/Stefan_W
aner/RealWorld/logic/logic4.html
More Tautologies and Equivalences
More Tautologies and Equivalences
More Tautologies and Equivalences
Summary of Tautological
Implications and Equivalences
See tables A and B at the following page:
http://people.hofstra.edu/faculty/Stefan_W
aner/RealWorld/logic/logic4.html
Exercise: The Island of Knights &
Knaves
We are in an island all of whose
inhabitants are either knights or knaves


knights always tell the truth
knaves always lie
Problem:


you meet inhabitants A and B, and A tells you
“at least one of us is a knave”
can you determine who is a knave and who is
a knight?
Exercise: The Island of Knights
& Knaves
Problem 1

you meet inhabitants A and B. A says: “We
are both knaves.” What are A and B?
Problem 2


you meet inhabitants A, B, and C. You walk
up to A and ask: "are you a knight or a
knave?" A gives an answer but you don't
hear what she said. B says: "A said she was a
knave." C says: "don't believe B; he is lying.”
What are B and C? How about A?
Logical Inference
Given a set of assumptions (premises),
logically inferring a new statement
(conclusion) is done by a step-by-step
derivation using “rules of inference”



Rules of inference are the Tautological
Implications and Tautological Equivalences
we saw before (e.g., Modus Ponens)
The derivation starting from the premises and
leading to the conclusion is called a “proof” or
and “argument”
See the middle column of Tables A and B in
Section 4 of the Logic Web site.
Examples of Inference Rules
Applying Inference Rules
Example: Modus Ponens (MP)




Suppose we have 3 statements we know to be true:
Applying MP to statements 1 and 3, we conclude:
(r /\ ~s) as the conclusion.
Note that MP has the form:
Here A stands for (p \/ q) and B stands for (r /\ ~s).
Premise 2 in this case was not used.
Applying Inference Rules
Example: Modus Tollens (MT)
Applying Inference Rules
Some general rules to remember:
Proof Example
Prove that the following
argument is valid
Proof Example
Prove that the following
argument is valid
Do Exercise 2P on Section 6 of the Logic Web site
Proof Example
Prove that the following
argument is valid
More Examples & Exercises
In Section 6 of the Logic Web Site:




Proof Strategies: Examples 4 and 5, and
exercise 5P
Forward and Backward: Examples 6 and 7,
and exercise 7P
Different types of arguments: Examples 8-10
Logical Reasoning: Example 11
Extra Credit Contest
You are to write down and submit a statement
Rules of the contest: (Note: I can’t violate the rules)

There are two prizes:
Prize 1: you get a couple of m&m’s
Prize 2: you get 10 extra credit points on your next
assignment


If your statement is true, then I have to give you
one of the prizes
If it is false, you get nothing
The challenge: come up with a statement that
guarantees you get prize 2!
Predicate Logic
Consider:

p: All men are mortal.
q: Socrates is a man.
r: Socrates is mortal.
We know that from p and q we should be able to
prove r.

But, there is nothing in propositional logic that allows
us to do this.
Need to represent the relationship between all
men and one man in particular (Socrates).
Predicate Logic
Instead we need to use quantifiers and
predicates:
For all x, if x is a man, then x is mortal
 x [ man(x)  mortal(x) ]
Universal
quantifier
predicates
Predicate Logic
Second quantifier is the existential
quantifier (“there exists”):
“Everybody loves somebody”
“for every person x, there is a person y so that x loves y”
x [ person(x)  y [ person(y) /\ loves(x,y) ] ]
Existensial
quantifier
predicates