CM3112 Artificial Intelligence
Propositional logic Syntax and semantics
Steven Schockaert
SchockaertS1@cardiff.ac.uk
School of Computer Science & Informatics Cardiff University
Stench
PIT
Stench
Gold
PIT
Stench
START
PIT
4
3
2
1
Motivating example: Hunt the Wumpus
‣The goal is to collect the gold and bring it back to the start position
‣The player does not know the position of Wumpus, the pits, or the gold
‣If the player moves to a cell with Wumpus or a pit, they die
‣In the cells adjacent to a pit, the player can sense a breeze
‣In the cells adjacent to Wumpus, the player can smell a stench
‣Actions available to the player are: turn 90 degrees (left/right), move forward, shoot in the current direction (this action is only available once)
1234
B
B
B
B
B
B
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r
r
r
r
r
r
z
z
z
z
z
z
figures/wumpus-world.eps (Tue Nov 3 16:24:13 2009). A typical wumpus
Motivating example: Hunt the Wumpus
Original version from 1980 was written in BASIC
Several variants are now available online (e.g. http://osric.com/wumpus/)
Motivating example: Hunt the Wumpus
OK
OK
A
OK
Motivating example: Hunt the Wumpus
B OK
A
A
OK
OK
There is a breeze in cell (2,1)
Motivating example: Hunt the Wumpus
A
P?
B OK
P?
OK
A
OK
There is a breeze in cell (2,1)
‣ there must be a pit in (3,1) or in (2,2)
Motivating example: Hunt the Wumpus
P?
B OK
A
A
OK
A
P?
S
There is a smell in cell (1,2) but no breeze
OK
Motivating example: Hunt the Wumpus
P? P
B OK
A
A
P? OK
A
OK
W
S
There is a smell in cell (1,2) but no breeze
‣ Wumpus is in an adjacent cell, but it cannot be (2,2) since there was no smell in (2,1) ‣There is no pit in (2,2) so there must be one in (3,1)
OK
Motivating example: Hunt the Wumpus
P? P
OK
B OK
P?
OK
A
A
OK
A
OK
S
A
OK
W
Motivating example: Hunt the Wumpus
P? P
OK
B OK
P?
OK
A
A
A
A
OK
S
A
OK
W
BGS OK
There is a breeze, a smell and gold in cell (2,3)
Hunting the Wumpus as a search problem?
A state corresponds to the set of beliefs held by the player at any given point in the game, i.e. the collection of relevant knowledge that has been obtained; this is called the epistemic state of an agent
The initial state corresponds to the situation where the epistemic state only contains generic background knowledge (e.g. the rules of the game), but no specific observations
A goal state corresponds to a situation where the position of the gold can be derived from the acquired knowledge
To assess which actions are legal, we need to check for which of the adjacent grid cells we can derive that they contain neither Wumpus nor a pit
Inference: informal examples
P? P
B OK
A
A
P? OK
A
OK
W
4 3
2
S OK 1
1234
There was a breeze in cell (2,1)
➡ Either there is a pit in (3,1) or in (2,2)
There was no breeze in (1,2)
➡ There is no pit in (1,1), (2,2) and (1,3)
There is a pit in (3,1) and not in (2,2)
Inference: informal examples
P?
B OK P?
A
AA
2
1
12
P?
OKB OK
Smell in (1,1)
➡ nowhere to move
Shoot straight ahead
➡ either Wumpus was not in (2,1) and nothing has happened
➡ or Wumpus was in (2,1) and is now dead
It is safe to move to (2,1)
P?
S
A
Propositional logic
Use a generic language to express knowledge and a generic inference mechanism
To define a language, we need a syntax and a semantics Syntax defines which expressions are allowed in a language
‣ the language of propositional logic is built from atomic propositions and logical connectives
‣ expressions which are in the language, i.e. which adhere to the syntax, are called formulas
Semantics defines the meaning of a formula
‣ a formula in propositional logic corresponds to a set of possible worlds
Propositional logic: syntax
The basic constituents of propositional logic are called atomic
propositions, or atoms
‣ They are basic assertions that can either be true or false
‣ They are the basic building blocks about which we want to reason ‣ We don’t care about what these assertions are
Let At be the set of all atoms we wish to consider
At = {breeze(1,1), breeze(1,2),…, stench(1,1),…, wumpus(1,1),…}
At = {w,s,e,ir,it,f,t}
w: “Wales will win the 6 nations championship”
s: “Scotland will win the 6 nations championship” …
t: “I will be in tears”
Propositional logic: syntax
Every atom is a formula
If α and β are formulas, then the following expressions are formulas as
well:‣ (α)∧(β) ‣ (α)∨(β)
‣ (α)➝(β) ‣ ¬(α)
(conjunction)
(disjunction)
(implication) (negation)
Note: the condition part of an implication is also called the antecedent; the conclusion part is also called the consequent
(((e)∨(f))∧(¬(w))) ➝ (t) (breeze(1,1)) ➝ ((pit(1,2))∨(pit(2,1)))
Propositional logic: syntax
In practice, we usually omit all brackets which can be omitted without causing ambiguity
We don’t write brackets around atoms or around the entire formula ((α)∨(β))∨(γ) and (α)∨((β)∨(γ)) have the same meaning, so we can write
(α)∨(β)∨(γ) without any cause for confusion
((α)∧(β))∧(γ) and (α)∧((β)∧(γ)) have the same meaning, so we can write
(α)∧(β)∧(γ) without any cause for confusion
We define ¬ to take priority over ∨ and ∧ , and ∨ and ∧ to take priority over ➝, so we write e.g. α∧¬β ➝ γ∨δ instead of (α∧(¬β)) ➝ (γ∨δ)
Propositional logic: syntax
propositional logic
¬
∧ and ∨
➝
arithmetic
– (unary operator) *
+ and – (binary operator)
-5*6 + 4 – 7*2 = (((-5) * 6) + 4) – (7*2) = ((-5) * 6) + (4 – (7*2)) (¬α∧β) ∨ γ ∨ ¬(δ∧φ) = (((¬α)∧β) ∨ γ) ∨ ¬(δ∧φ) = ((¬α)∧β) ∨ (γ ∨ ¬(δ∧φ))
Propositional logic: semantics
An interpretation, or possible world, is a mapping from At to {true,false}
We write ω ⊧ α if the formula α is satisfied (i.e. made true) by the interpretation ω:
‣ For an atom a, ω ⊧ a iff ‣ ω ⊧ β∧γ iff ‣ ω ⊧ β∨γ iff ‣ ω ⊧ β➝γ iff ‣ ω ⊧ ¬β iff
ω(a)=true
ω ⊧ β and ω ⊧ γ ω ⊧ β or ω ⊧ γ
ω ⊧ ¬β∨γ not (ω ⊧ β)
If a formula α is satisfied by ω, then ω is called a model of α
A formula which is satisfied by every interpretation ω is called a tautology, a formula which is satisfied by no interpretation is called a contradiction, a formula which is satisfied by at least one interpretation is called satisfiable
Truth tables
Is the formula ((a∧¬b) ➝ c) ➝ (a∧¬b) a tautology?
a
b
c a∧¬b
((a∧¬b) ➝ c)
((a∧¬b) ➝ c) ➝ (a∧¬b)
false false false false true true true true
false false true true false false true true
false true false true false true false true
Enumerate all interpretations
Truth tables
Is the formula ((a∧¬b) ➝ c) ➝ (a∧¬b) a tautology?
a
b
c a∧¬b
((a∧¬b) ➝ c)
((a∧¬b) ➝ c) ➝ (a∧¬b)
false false false false true true true true
false false true true false false true true
false true false true false true false true
false false false false true true false false
true true true true false true true true
false false false false true true false false
check which interpretations are models of the formula
Truth tables
Is the formula (a∧¬b) ➝ (c ➝ (a∧¬b)) a tautology?
a
b
c a∧¬b
(c ➝ (a∧¬b))
(a∧¬b) ➝ (c ➝ (a∧¬b))
false false false false true true true true
false false true true false false true true
false true false true false true false true
false false false false true true false false
true false true false true true true false
true true true true true true true true
check which interpretations are models of the formula