CSC242 Lecture 2.2 Propositional Logic
CSC242:
Introduction to
Artificial Intelligence
Lecture 2.2
Please put away all electronic devices
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, …, Xn }
• D: Set of domains { D1, …, Dn }
• Each Di : set of values { v1, …, vk }
• C: Set of constraints { C1, …, Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Factored Representation
• Splits a state into factors (attributes,
features, variables) that can have
values
• Factored states can be more or less
similar (unlike atomic states)
• Can also represent uncertainty (don’t
know the value of some attribute)
Backtracking Search for
CSPs
• DFS search through the space of
assignments
• Assign one variable at a time
• Because the representation of CSPs is
standardized, no need to supply initial
state, actions, transition model, or goal
test!
• Early pruning of inconsistent states
Constraint Propagation
• Using the constraints to reduce the set of
legal values of a variable, which can in
turn reduce the legal values of another
variable, and so on
• Not a search process!
• Part of state update in state-space search
• A type of inference: making implicit
information explicit
Constraint Propagation
• Node consistency:
• Propagate unary constraints (once)
• Arc consistency
• Propagate binary constraints
• AC-3 algorithm
Arc Consistency
X Y
Y=X2
{ 0,1,2,3,4,5,6,7,8,9 } { 0,1,2,3,4,5,6,7,8,9 }
# possible assignments: 10×10 = 100
Arc Consistency
X Y
Y=X2
{ 0,1,2,3,4,5,6,7,8,9 } { 0,1,2,3,4,5,6,7,8,9 }
Make X arc-consistent with respect to Y
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,2,3,4,5,6,7,8,9 }
X arc-consistent with respect to Y
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,2,3,4,5,6,7,8,9 }
Make Y arc-consistent with respect to X
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
Y arc-consistent with respect to X
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
X and Y arc-consistent
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
# possible assignments: 4×4 = 16
X and Y arc-consistent
AC-3
boolean revise(csp, i, j) {
boolean changed = false
foreach vi in Di {
boolean ok = false
foreach vj in Dj {
if (
ok = true
}
}
if (!ok) {
delete vi from Di
changed = true
}
}
return changed
}
boolean AC3(csp) {
Set queue = all arcs in csp
while (queue is not empty) {
if (revise(csp, i, j)) {
if Di is empty {
return false
}
foreach k in neighbors(i) {
add
}
}
}
return true
}
AC-3 Analysis
• CSP with n variables, domain size O(d),
c constraints (arcs)
• Each arc can be inserted in the queue at
most d times
• Checking a single arc takes O(d 2) time
• Total time: O(cd 3)
• Independent of n
Constraint Propagation
• “After constraint propagation, we are
left with a CSP that is equivalent to
the original CSP—they both have the
same solutions—but the new CSP will in
most cases be faster to search because
its variables have smaller domains.”
State-Space
Search
Constraint
Propagation
(inference)
Interleaving Search and
Inference
• After each choice during search, we
can perform inference to reduce future
search
Interleaving Search and
InferenceCSP:
• Variables
• Domains
• Constraints Node Consistency
Arc Consistency (AC-3)
Solved?
Assign a variable
OK
No
Backtrack
No
Yes
Done!
FailInconsistent?
Inconsistent?
Yes
No
Constraint Satisfaction
• Impose a structure on the representation of
states: Variables, Domains, Constraints
• Backtracking (DFS) search for complete,
consistent assignment of values to variables
• Inference (constraint propagation) can reduce
the domains of variables
• Preprocessing and/or interleaved with search
• Useful problem-independent heuristics
Hunt The Wumpus
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
• Move fwd, turn left/
right
• Shoot arrow (once)
• Grab gold
• Climb out (from [1,1])
• Costs:
• -1 per move
• -10 to shoot
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
• Get gold and climb
out: +1000
• Fall in pit or get eaten
by wumpus: -1000
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
?
Boolean CSP
• All variables must be Booleans
• Domains all { true, false }
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
For each room:
Has pit? true, false, idk
Has wumpus? true, false, idk
Has gold? true, false, idk
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean[][] P =
new Boolean[n][n];
Boolean[][] W =
new Boolean[n][n];
Boolean[][] G =
new Boolean[n][n];
// P[i][j] == Boolean.TRUE
// if there’s a pit at [i,j]
// P[i][j] == Boolean.FALSE
// if there’s no pit at [i,j]
// P[i][j] == null
// if we don’t know
// W[i][j] ditto for wumpus
// G[i][j] ditto for gold
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
// P_ij == Boolean.TRUE
// if there’s a pit at [i,j]
// P_ij == Boolean.FALSE
// if there’s no pit at [i,j]
// P_ij == null
// if we don’t know
// W_ij ditto for wumpus
// G_ij ditto for gold
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Position pos =
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
// L_ij == Boolean.TRUE
// if agent is at location [i,j]
// else Boolean.FALSE
// Note: The agent always knows
// where it is.
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
enum Orientation = { N,S,E,W };
Orientation orientation;
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
// FacingN == Boolean.TRUE
if agent is facing north
// Ditto for the other directions
// Note: The agent always knows
// which way it is facing
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Hunt The Wumpus
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
• Breeze
• Stench
• Glimmer
• Bump
• Scream
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean S_11, S_12, S_13, …,
S_21, S_22, …;
Boolean B_11, B_12, B_13, …,
B_21, B_22, …;
…
// S_ij == Boolean.TRUE
// if a stench perceived @[i,j]
// S_ij == Boolean.FALSE
// if no stench @[i,j]
// S_ij == null
// if we don’t know
// B_ij ditto for breeze
// Ditto for other percepts
WW Boolean CSP
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
Boolean S_11, S_12, S_13, …,
S_21, S_22, …;
Boolean B_11, B_12, B_13, …,
B_21, B_22, …;
…
Constraints
Constraints
• Constraints are Boolean functions of the
variables
•
•
•
WA ≠ NT
T2 ≥ T1 + 10
AllDiff(A1,A2,A3,B1,B2,B3,C1,C2,C3)
Constraints
• Constraints are Boolean functions of the
variables
•
•
•
• Constraints on Boolean variables are
Boolean functions of Boolean values
WA ≠ NT
T2 ≥ T1 + 10
AllDiff(A1,A2,A3,B1,B2,B3,C1,C2,C3)
Aristole
(384BC – 332BC)
(1815-1864)
Propositional Logic
(Boolean Algebra)
A Programming Language for Knowledge!
Propositions
• Propositions: things that can be true or
false
Propositions
• Propositions: things that can be true or
false
• Atomic propositions:
• “It is raining”
• “Socrates was a person”
• “The wumpus is in room [2,2]”
Connectives
(Operators)
• Combine propositions into larger
propositions
• ¬, ∧, ∨, ⇒, ⇔
• ¬Raining
• Raining ∧ Cold, Raining ∨ Sunny
• Raining ∧ BelowFreezing ⇒ Slippery
Connectives
(Operators)
• Combine propositions into larger
propositions
• ¬, ∧, ∨, ⇒, ⇔
• ¬Raining
• Raining ∧ Cold, Raining ∨ Sunny
• Raining ∧ BelowFreezing ⇒ Slippery
Syntax
Connectives
(Operators)
• Combine propositions into larger
propositions
• ¬, ∧, ∨, ⇒, ⇔
• Each connective represents a Boolean
function of its (Boolean) arguments
Syntax
Semantics
Connectives
p ¬p
F T
T F
Connectives
p q ¬p p∧q p∨q p⇒q p⇔q
F F T F F T T
F T F F T T F
T F F T F F
T T T T T T
Sentences
(Expressions)
• Every sentence of propositional logic
represents (“denotes”) a Boolean
function of its (Boolean) arguments
Sentences
(Expressions)
• Every sentence of propositional logic
represents (“denotes”) a Boolean
function of its (Boolean) arguments
• The meaning of a sentence (the Boolean
function that it denotes) is the
composition of its parts (“compositional
semantics”)
L1,1: True if the agent is in room [1,1]
W1,2: True if the wumpus is in room [1,2]
W2,1: True if the wumpus is in room [2,1]
Possible Worlds
L1,1 W1,2 W2,1
F F F
F F T
F T F
F T T
T F F
T F T
T T F
T T T
A Sentence
L1,1 ∧ (W1,2∨W2,1)
L1,1 W1,2 W2,1
F F F
F F T
F T F
F T T
T F F
T F T
T T F
T T T
Meaning of a Sentence
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Meaning of a Sentence
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Truth Table
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Truth Table
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Truth Table
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Truth Table
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Truth Table
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Propositional Logic
and Boolean CSPs
• Every sentence of propositional logic
represents (“denotes”) a Boolean
function of its (Boolean) arguments
• Constraints on Boolean variables are
Boolean functions of Boolean values
Satisfiability
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Inconsistency
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Inconsistency
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Models
L1,1 W1,2 W2,1 W1,2∨W2,1
L1,1∧
(W1,2∨W2,1)
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
L1,1 ∧ (W1,2∨W2,1)
Models
L1,1 W1,2 W2,1 W1,2∨W2,1
{ L1,1,
(W1,2∨W2,1) }
F F F F F
F F T T F
F T F T F
F T T T F
T F F F F
T F T T T
T T F T T
T T T T T
{ L1,1, (W1,2∨W2,1) }
Unsatisfiable
L1,1 W1,2 L1,1 ∧W1,2 ¬W1,2
L1,1 ∧W1,2 ∧
¬W1,2
F F F T F
F T F F F
T F F T F
T T T F F
L1,1 ∧W1,2 ∧ ¬W1,2
Unsatisfiable
L1,1 W1,2 ¬W1,2 { L1,1,W1,2, ¬W1,2 }
F F T F
F T F F
T F T F
T T F F
{ L1,1, W1,2, ¬W1,2 }
Propositional Logic
and Boolean CSPs
• Every sentence of propositional logic
represents a Boolean function of its
atomic propositions
• Each assignment of true or false to the
atomic propositions is one possible world
• That world is consistent with the
sentence if the function denoted by the
sentence is true given that assignment
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
P1,1, P1,2, … : There is a pit at [1,1], [1,2], …
W1,1, W1,2, … : The wumpus is at [1,1], [1,2], …
…
B1,1, B1,2, … : You perceived a breeze at [1,1], …
S1,1, S1,2, … : You perceived a stench at [1,1], …
…
L1,1, L1,2, … : The agent is at [1,1], …
FacingN, FacingS, FacingE, FacingW
Background Knowledge
Background Knowledge
• You perceive a breeze in a room if that
room is adjacent to a room that
contains a pit
Background Knowledge
• You perceive a breeze in a room only if
that room is adjacent to a room that
contains a pit
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits are breezy.
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits have breezes.
Bi,j ⇔ Pk,l for some room [k,l] adjacent to [i,j]
?
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits have breezes.
Bi,j ⇔ Pk,l for some room [k,l] adjacent to [i,j]
?
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits have breezes.
Bi,j ⇔ Pk,l for some room [k,l] adjacent to [i,j]
?
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits have breezes.
• You perceive a breeze in [1,1] iff there
is a pit in [1,2] or [2,1]
B1,1 ⇔ P1,2 ∨ P2,1
Background Knowledge
• You perceive a breeze in a room if and
only if that room is adjacent to a room
that contains a pit
• Rooms adjacent to pits have breezes.
• You perceive a breeze in [1,1] iff there is
a pit in [1,2] or [2,1]
• You perceive a breeze in [1,2] iff there is
a pit in [1,1] or [2,2] or [3,1]
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1
…
Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1
…
S1,1 ⇔ W1,2 ∨ W2,1
S1,2 ⇔ W1,1 ∨ W2,2 ∨ W3,1
S2,2 ⇔ W1,2 ∨ W2,3 ∨ W3,2 ∨ W2,1
…
Background Knowledge
• A room is safe (“OK”) if and only if it
does not contain either a pit or the
wumpus
Background Knowledge
• A room is safe (“OK”) if and only if it
does not contain either a pit or the
wumpus
OK1,1 ⇔ ¬(P1,1 ∨ W1,1)
OK1,2 ⇔ ¬(P1,2 ∨ W1,2)
OK2,1 ⇔ ¬(P2,1 ∨ W2,1)
…
Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.
Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.
• There is a wumpus in at least one of
the rooms AND a wumpus cannot be in
two rooms.
Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.
• There is a wumpus in at least one of
the rooms AND a wumpus cannot be in
two rooms.
W1,1 ∨ W1,2 ∨ … ∨ W3,4 ∨ W4,4
¬(W1,1 ∧ W1,2), ¬(W1,1 ∧ W1,3), …, ¬(W3,4 ∧ W4,4)
Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1
…
S1,1 ⇔ W1,2 ∨ W2,1
S1,2 ⇔ W1,1 ∨ W2,2 ∨ W3,1
S2,2 ⇔ W1,2 ∨ W2,3 ∨ W3,2 ∨ W2,1
…
OK1,1 ⇔ ¬(P1,1 ∨ W1,1)
OK1,2 ⇔ ¬(P1,2 ∨ W1,2)
OK2,1 ⇔ ¬(P2,1 ∨ W2,1)
…
W1,1 ∨ W1,2 ∨ … ∨ W3,4 ∨ W4,4
¬(W1,1 ∧ W1,2), ¬(W1,1 ∧ W1,3), …, ¬(W3,4 ∧ W4,4)
Knowledge-Based Agents
Knowledge-Based Agents
• Maintain a knowledge base (KB) of
sentences believed to be true
Knowledge-Based Agents
• Maintain a knowledge base (KB) of
sentences believed to be true
• Perceives the world (and updates its
beliefs)
Knowledge-Based Agents
• Maintain a knowledge base (KB) of
sentences believed to be true
• Perceives the world (and updates its
beliefs)
• Infers what to do next
Knowledge-Based Agents
• Maintain a knowledge base (KB) of
sentences believed to be true
• Perceives the world (and updates its
beliefs)
• Infers what to do next
• Performs an action (and updates its
beliefs)
Knowledge-Based Agents
Perceive
InferAct
KB
Knowledge-Based Agents
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
Knowledge-Based Agents
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
L1,1, ¬L1,2, … ¬L3,4, ¬L4,4
FacingE, ¬FacingN, ¬FacingS, ¬FacingW
OK1,1
Perception
PIT
1 2 3 4
1
2
3
4
START
Stench
Stench
Breeze
Gold
PIT
PIT
Breeze
Stench
¬B1,1, ¬S1,1
Inference
• Given what I know…
• What should I do? See AIMA 7.7
Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe?
Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe?
• Is room [2,1] safe?
Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe?
• Is room [2,1] safe?
• Is there no pit in room [2,1]?
Inference
Given what I know… Is there no pit in room [2,1]?
KB ¬P2,1?
Inference
Given what I know… Is there no pit in room [2,1]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
¬B1,1
¬P2,1?
Inference
P1,1 P1,2 P2,1 B1,1
F F F F
F F F T
F F T F
…
T T F T
T T T F
T T T T
Possible Worlds
Inference
P1,1 P1,2 P2,1 B1,1 R1 R2 ¬B1,1 ¬P2,1
F F F F T T T
F F F T T F F
F F T F T F T
… …
T T F T F T F
T T T F F F T
T T T T F T F
Knowledge
Inconsistent Worlds
P1,1 P1,2 P2,1 B1,1 R1 R2 ¬B1,1 ¬P2,1
F F F F T T T
F F F T T F F
F F T F T F T
… …
T T F T F T F
T T T F F F T
T T T T F T F
Knowledge
Models
P1,1 P1,2 P2,1 B1,1 R1 R2 ¬B1,1 ¬P2,1
F F F F T T T
F F F T T F F
F F T F T F T
… …
T T F T F T F
T T T F F F T
T T T T F T F
Knowledge
Inference
P1,1 P1,2 P2,1 B1,1 R1 R2 ¬B1,1 ¬P2,1
F F F F T T T T
F F F T T F F
F F T F T F T
… …
T T F T F T F
T T T F F F T
T T T T F T F
Query
Entailment
• α entails β : α ⊨ β
• Every model of α is also a model of β
Entailment
• α entails β : α ⊨ β
• Every model of α is also a model of β
• Whenever α is true, so is β
• β is true in every world consistent with α
•
• β logically follows from α
Models(α) ⊆ Models(β)
Entailment
• Is very conservative
• Only accepts a conclusion that is
guaranteed to be true whenever the
premises are true
Entailment
• Is very conservative
• Only accepts a conclusion that is
guaranteed to be true whenever the
premises are true
• If β is false in every model of α,
then α ⊨ ¬β
Entailment
• Is very conservative
• Only accepts a conclusion that is
guaranteed to be true whenever the
premises are true
• If β is false in every model of α,
then α ⊨ ¬β
• Otherwise: don’t know!
Entailment
Given what I know… Is there no pit in room [2,1]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
¬B1,1
¬P2,1?
KB ⊨ ¬P2,1
Entailment
Given what I know… Is there no pit in room [1,2]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
¬B1,1
B2,1
¬P1,2?
Inference
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
Inference
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
Possible Worlds
Inference
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
Knowledge
Impossible Worlds
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
Models
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
Inference
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
KB ⊨ ¬P1,2
Inference
B1,1 B1,2 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB
F F F F F F F T T T T F F
F F F F F F T T T F T F
F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
F T F F F F F T T F T T F
F T F F F F T T T T T T T
F T F F F T F T T T T T T
F T F F F T T T T T T T T
F T F F T F F T F F T T F
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
T T T T T T T F T T F T F
KB ⊭ ¬P2,2
KB ⊭ P2,2
Entailment
Given what I know…
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
¬B1,1
B2,1
¬P1,2?
KB ⊨ ¬P1,2
KB ⊭ ¬P2,2
KB ⊭ P2,2
Entailment
• α entails β : α ⊨ β
• Every model of α is also a model of β
• Whenever α is true, so is β
• β is true in every world consistent with α
•
• β logically follows from α
Models(α) ⊆ Models(β)
Computing Entailment
• Given knowledge α and query β
• For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β
• Conclude that α ⊨ β
Model Checking
• Given knowledge α and query β
• For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β
• Conclude that α ⊨ β
Computing Entailment
boolean TT_Entails?(KB,α)
symbols ⟵ proposition symbols used in KB and α
return TT_Check_All(KB, α, symbols, {})
boolean TT_Check_All(KB, α, symbols, model)
if empty?(symbols) then
if PL_True?(KB,model) then return PL_True(α,model)
else return true // when KB is false, always return true
else
P ⟵ first(symbols)
rest ⟵ rest(symbols)
return TT_Check_All(KB, α, rest, model ∪ {P=true})
&& TT_Check_All(KB, α, rest, model ∪ {P=false})
AIMA Fig. 7.10
But…
Model Checking
• Given knowledge α and query β
• For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β
• Conclude that α ⊨ β
Model Checking
P1,1 P1,2 … OK1,1 OK2,1 R1 R2 … ¬B1,1 ¬S1,1 OK2,1
F F … F F F … … … T
… …
F F … T T T T … … T T
… …
T T … F T F … … … F
T T … T F T F … … T
T T … T T T T … … F
n propositions m sentences, O(k) connectives
Model Checking
P1,1 P1,2 … OK1,1 OK2,1 R1 R2 … ¬B1,1 ¬S1,1 OK2,1
F F … F F F … … … T
… …
F F … T T T T … … T T
… …
T T … F T F … … … F
T T … T F T F … … T
T T … T T T T … … F
n propositions m sentences, O(k) connectives
O(k)
Model Checking
P1,1 P1,2 … OK1,1 OK2,1 R1 R2 … ¬B1,1 ¬S1,1 OK2,1
F F … F F F … … … T
… …
F F … T T T T … … T T
… …
T T … F T F … … … F
T T … T F T F … … T
T T … T T T T … … F
n propositions m sentences, O(k) connectives
O(mk)
Model Checking
P1,1 P1,2 … OK1,1 OK2,1 R1 R2 … ¬B1,1 ¬S1,1 OK2,1
F F … F F F … … … T
… …
F F … T T T T … … T T
… …
T T … F T F … … … F
T T … T F T F … … T
T T … T T T T … … F
n propositions m sentences, O(k) connectives
2n
Model Checking
P1,1 P1,2 … OK1,1 OK2,1 R1 R2 … ¬B1,1 ¬S1,1 OK2,1
F F … F F F … … … T
… …
F F … T T T T … … T T
… …
T T … F T F … … … F
T T … T F T F … … T
T T … T T T T … … F
n propositions m sentences, O(k) connectives
O(2nmk) Intractable!
Entailment
• α entails β : α ⊨ β
• Every model of α is also a model of β
• Whenever α is true, so is β
• β is true in every world consistent with α
•
• β logically follows from α
Models(α) ⊆ Models(β)
co-NP-complete!
Propositional Logic
• Programming language for knowledge
• Factored representation (Boolean CSP)
• Propositions, connectives, sentences
• Possible worlds, satisfiability, models
• Entailment: α ⊨ β
• Every model of α is a model of β
• Model checking intractable!
For next time:
AIMA Ch. 7.5