CS计算机代考程序代写 algorithm CSC242 Lecture 2.2 Propositional Logic

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 ( satisfies Cij ) {
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) {
= queue.removeFirst()
if (revise(csp, i, j)) {
if Di is empty {
return false
}
foreach k in neighbors(i) {
add to queue
}
}
}
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

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

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

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Boolean CSP
• All variables must be Booleans

• Domains all { true, false }

WW Boolean CSP

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

WW Boolean CSP

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Position pos =

WW Boolean CSP

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

enum Orientation = { N,S,E,W };

Orientation orientation;

WW Boolean CSP

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Hunt The Wumpus

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

• Breeze

• Stench

• Glimmer

• Bump

• Scream

WW Boolean CSP

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

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)

George Boole

(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

START

Stench

Breeze

Gold

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
…

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

START

Stench

Breeze

Gold

PIT

Breeze

Stench

Knowledge-Based Agents

PIT

1 2 3 4

START

Stench

Breeze

Gold

PIT

Breeze

Stench

L1,1, ¬L1,2, … ¬L3,4, ¬L4,4
FacingE, ¬FacingN, ¬FacingS, ¬FacingW
OK1,1

Perception

PIT

1 2 3 4

START

Stench

Breeze

Gold

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

n propositions m sentences, O(k) connectives

O(k)

Model Checking

n propositions m sentences, O(k) connectives

O(mk)

Model Checking

n propositions m sentences, O(k) connectives

Model Checking

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

Related Posts