Transcript document
CS 2710, ISSP 2610
Chapter 7
Propositional Logic
Reasoning
1
Knowledge Based Agents
• Central component: knowledge base, or KB.
• A set of sentences in a knowledge
representation language
• Generic Functions
– TELL (add a fact to the knowledge base)
– ASK (get next action based on info in KB)
• Both often involve inference, which is?
• Deriving new sentences from old
2
Note
• We’re all familiar with logic from
mathematics
• In AI, we need to think about things we
usually can take for granted
• To use the notion of prime number, you don’t
have to think about what prime means … or
number, for that matter
• In AI, we create knowledge representation
schemes, which define the objects,
predicates, and functions which exist
3
The Wumpus World
• Game is played in a MxN grid
• One player, one wumpus, one or more pits
• Goal: find gold while avoiding wumpus and
pits
• Percepts:
–
–
–
–
–
Glitter (gold is in this square)
Stench (wumpus is within 1 square N,E,S,W)
Breeze (pit is within 1 square N, E, S, W)
Bump (agent walks into a wall)
Scream (when Wumpus dies; hear it anywhere)
4
Wumpus Example
[start]
stench
[Wumpus] stench
Glitter
[gold]
stench,
breeze
breeze
[Pit]
breeze
0
0
5
Wumpus
• Main difficulty: player doesn’t know
the configuration
• Reason about configuration
• Knowledge evolves as new percepts
arrive and actions are taken.
6
Examples of reasoning
• If the player is in square (1, 0) and the
percept is breeze, then there must be a pit
in (0,0) or a pit in (2,0) or a pit in (1,1).
• If the player is now in (0,0) [and still alive],
there is not a pit in (0,0).
• If there is no breeze percept in (0,0),
there is no pit in (0,1)
• If there is also no breeze in (0,1) then
there is no pit in (1,1).
• Therefore, there must be a pit in (2,0)
7
Fundamental Concepts of logical
representation and reasoning
• Information is represented in sentences, which
must have correct syntax
( 1 + 2 ) * 7 = 21 vs. 2 ) + 7 = * ( 1 21
• The semantics of a sentence defines its truth with
respect to each possible world – an interpretation
assigning T or F to all propositions
• W is a model of S means that sentence S is true
under interpretation W
• What do the following mean?
– X |= Y
– X entails Y
– Y logically follows from X
8
Which are true?
Which are not true but useful?
• {Man, Man Mortal} |= Mortal
• {Raining,Dog Mammal} |= Mammal
• {Raining,Raining Wet} |= Wet
• {Smoke, Fire Smoke} |= Fire
• {Tall ^ Silly} |= Tall
• {Tall v Silly} |= Silly
• {Tall, Silly} |= Tall ^ Silly
(On board – E.g. with Wumpus world)
9
Entailment
• A |= B
• Under all interpretations in which A is
true, B is true as well
• All models of A are models of B
• Whenever A is true, B is true as well
• A entails B
• B logically follows from A
10
Inference
KB |-i A
Inference algorithm i can derive A
from KB
i derives A from KB
i can derive A from KB
A can be inferred from KB by i
11
Inference Algorithm Examples
•
•
•
•
•
{A,B} |- (^intro) A ^ B
{A, AB} |- (MP) B
{A, B A} |- (abduction) B
A |- (some religions) GodExists
SunnyDay |- (some students) NoClass
(Italics used for constants here)
12
Inference Algorithms
• A. Definition of soundness of inference
algorithm i?
• B. Definition of completeness of inference
algorithm i?
• Notes:
implication, piece of syntax
|= entailment, used to describe semantics
Inference algorithm, inference procedure, rule of
inference, inference rule: procedure that
derives sentences from sentences
13
Monotonicity
• A logic is monotonic if…
14
Propositional Logic Syntax
• Sentence -> AtomicSent | complexSent
AtomicSent -> true|false| P, Q, R …
ComplexSent ->
sentence
|
( sentence sentence ) |
( sentence sentence ) |
( sentence sentence ) |
( sentence sentence ) |
( sentence )
[no predicate or function symbols]
15
Propositional Logic
Sentences
• If there is a pit at [1,1], there is a
breeze at [1,0]
P11 B10
• There is a breeze at [2,2], if and only
if there is a pit in the neighborhood
B22 ( P21 P23 P12 P32 )
• There is no breeze at [2,2]
B22
16
Semantics of Prop Logic
• In model-theoretic semantics, an
interpretation assigns elements of
the world to sentences, and defines
the truth values of sentences
• Propositional logic: easy! Assign T or
F to each proposition symbol; then
assign truth values to complex
sentences in the obvious way
17
Logical Equivalences
• Sentences A and B are logically
equivalent if:
• they are true under exactly the same
interpretations
• A |= B and B |= A
18
Validity
• A sentence (or set of sentences) is
valid if
• it is true under all interpretations
• P v ~P
19
Satisfiability
• A sentence (or set of sentences) is
satisfiable if
• there exists some interpretation that
makes it true
• An interpretation satisfies a set of
sentences if it makes them true
20
Entailment
• A |= B
• In all worlds in which A is true, B is true as
well
• All models of A are models of B
• Whenever A is true, B is true as well
• A entails B
• B logically follows from A
• All interpretations that satisfy A also
satisfy B
21
Propositional Logic
Inference
• Question: Does KB entail S?
• Method 1: Truth Table Entailment
– Construct a truth table whose columns are all
propositions used in the sentences in KB.
– If S is true everywhere all sentences in KB are
true, then KB entails S (otherwise not)
• Method 2: Proof
– Proof by deduction
– Proof by contradiction
– Etc.
22
A
B
C
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
F
T
F
T
F
T
F
T
A
B
F
F
F
F
F
F
T
T
A
C
F
F
F
F
F
T
F
T
BC
F
F
F
T
F
F
F
T
A^C, C
does not
entail
BC
A,B,
Entails
AB
23
Rules for Deductive Proofs
• Modus Ponens
– Given: S1 S2 and S1, derive S2
• And-elimination
– Given: S1 S2, derive S1
– Given: S1 S2, derive S2
• DeMorgan’s Law
– Given ( A B) derive A B
– Given ( A B) derive A B
• See p. 249 (for review if needed)
24
Example Proof by Deduction
• Knowledge
S1: B22 ( P21 P23 P12 P32 )
S2: B22
• Inferences
rule
observation
S3: (B22 (P21 P23 P12 P32 ))
((P21 P23 P12 P32 ) B22) S1,bi elim
S4: ((P21 P23 P12 P32 ) B22) S3, and elim
S5: (B22 ( P21 P23 P12 P32 )) contrapos
S6: (P21 P23 P12 P32 )
S2,S5, MP
S7: P21 P23 P12 P32
S6, DeMorg
25
Proofs
• A derivation
• A sequence of applications of (usually
sound) rules of inference
• Reasoning by Search
• Successor function: all possible
applications of inference rules
• Monotonicity means search can be
local, and more efficient
26
Resolution
• Resolution allows a complete inference
mechanism (search-based) using only one
rule of inference
• Resolution rule:
– Given: P1 P2 P3 … Pn, and P1 Q1 … Qm
– Conclude: P2 P3 … Pn Q1 … Qm
Complementary literals P1 and P1 “cancel out”
27
Resolution
• winter v summer
• ~winter v cold
• Either winter or ~winter is true, so we
know that summer or cold is true
• Resolution rule:
– Given: P1 P2 P3 … Pn, and P1 Q1 … Qm
– Conclude: P2 P3 … Pn Q1 … Qm
Complementary literals P1 and P1 “cancel out”
28
Resolution in Wumpus World
• There is a pit at 2,1 or 2,3 or 1,2 or
3,2
– P21 P23 P12 P32
• There is no pit at 2,1
– P21
• Therefore (by resolution) the pit
must be at 2,3 or 1,2 or 3,2
– P23 P12 P32
29
Resolution
• Any complete search algorithm,
applying only the resolution rule, can
derive any conclusion entailed by any
KB in propositional logic.
30
Proof using Resolution
• To prove P, apply res until either:
– No new clauses can be added, (KB does not
entail P)
– The empty clause is derived (KB does entail P)
• Proof by contradiction: prove KB P is
contradictory (empty clause) to prove P
• Sentences need to be in CNF
• To carry out the proof, need a search
mechanism that will enumerate all possible
resolutions.
31
B22 ( P21 P23 P12 P32
)
1.
Eliminate , replacing with two implications
(B22 ( P21 P23 P12 P32 )) ((P21 P23 P12 P32 )
B22)
2. Replace implication (A B) by A B
(B22 ( P21 P23 P12 P32 )) ((P21 P23 P12 P32 )
B22)
3. Move “inwards” (unnecessary parens removed)
(B22 P21 P23 P12 P32 ) ( (P21 P23 P12 P32
) B22)
4. Distributive Law
(B22 P21 P23 P12 P32 ) (P21 B22) (P23 B22)
(P12 B22) (P32 B22)
32
Previous Slide: Sentence is in
CNF
• Next step (with simpler example):
• (P1 v P2 v ~P3) ^ P4 ^ ~P5 ^ (P2 v P3)
• Create a separate clause
corresponding to each conjunct
–
–
–
–
P1 v P2 v ~P3
P4
~P5
P2 v P3
33
Finally…
– Add the negation of the goal to the set
of clauses, and perform resolution. If
you reach the empty clause, you have
proved the goal
34
Simple Resolution EG
• When the agent is in 1,1, there is no
breeze, so there can be no pits in
neighboring squares
• (B11 (P12 v P21)); ~B11
• Prove: ~P12.
35
Horn Clauses
• A Horn Clause is a CNF clause with at most
one positive literal
• Horn Clauses form the basis of forward
and backward chaining
• The Prolog language is based on Horn
Clauses
• Deciding entailment with Horn Clauses is
linear in the size of the knowledge base
36
Reasoning with Horn Clauses
• Forward Chaining
– For each new piece of data, generate all new
facts, until the desired fact is generated
– Data-directed reasoning
• Backward Chaining
– To prove the goal, find a clause that contains
the goal as its head, and prove the body
recursively
– (Backtrack when you chose the wrong clause)
– Goal-directed reasoning
37