Transcript Document

CS.462
Artificial Intelligence
SOMCHAI THANGSATHITYANGKUL
Lecture 04 : Logic
Logic
• When we have too many states, we want a
convenient way of dealing with sets of states.
• The sentence “It’s raining” stands for all the
states of the world in which it is raining.
• Logic provides a way of manipulating big
collections of sets by manipulating short
descriptions instead.
• Instead of thinking about all the ways a world
could be, we’re going to work in the a language
of expressions that describe those sets.
2
What is logic
• A formal language
– Syntax – what expressions are legal
– Semantics – what legal expressions mean
– Proof system – a way of manipulating syntactic
expressions to get other syntactic expressions
(which will tell us something new)
• Why proofs? Two kinds of inferences an agent
might want to make:
– Multiple percepts => conclusions about the world
– Current state & operator => properties of next state
3
Propositional Logic Syntax
• Syntax: what you’re allowed to write
– for (thing t = fizz; t == fuzz; t++){ … }
– Colorless green ideas sleep furiously.
• Sentences (wffs: well formed formulas)
– true and false are sentences
– Propositional variables are sentences: P,Q,R,Z
– If f and y are sentences, then so are
• (f ), ~ f, f ∨ y, f ∧ y, f → y, f ↔ y
– Nothing else is a sentence
• ((~P ∨((True ∧R) ↔Q)) →S) well formed
• (~(P ∨Q) ∧→S) not well formed
4
Precedence
~
highest
∧
∨
→
↔ lowest
A∨B∧C
A ∨ (B ∧ C)
A∧B→C∨D
(A ∧ B) →(C ∨ D)
A→B∨C↔D
(A → (B ∨ C)) ↔ D
• If the order is clear, you can leave off
parenthesis.
5
Try this
Which of these are legal sentences?
Give fully parenthesized expressions for the legal
sentences.
6
Semantics
• An interpretation is a complete True /
False assignment to propositional symbols
• The semantics (meaning) of a sentence is
the set of interpretations in which the
sentence evaluates to True.
• Example: the semantics of the sentence P
∨ Q is the set of three interpretations
– P=True, Q=True
– P=True, Q=False
– P=False, Q=True
7
Evaluating a sentence under an
interpretation
• Truth Tables
f
Q ~P
f
t
f
t
t
f
t
t
f
f
t
f
f
f
t
f
t
f
t
t
f
t
t
t
t
t
P
P∧Q P∨Q P→Q Q→P P↔Q
f
f
t
t
t
8
Logical equivalences
9
Terminology
• A sentence is valid iff its truth value is t in
all interpretations.
• Valid sentences: true, : false, P ∨ ~ P
• A sentence is satisfiable iff its truth value
is t in at least one interpretation
– Satisfiable sentences: P, true, ~ P
• A sentence is unsatisfiable iff its truth
value is f in all interpretations
– Unsatisfiable sentences: P ∧ ~ P, false, ~ true
10
Examples
Sentence
smoke → smoke
smoke Ç :smoke
Interpretation that make
sentence’s truth value = f
Valid?
valid
smoke fire
satisfiable,
not valid
smoke = t, fire = f
(s ! f) ! (: s ! : f)
satisfiable,
not valid
s = f, f = t
(s ! f) ! (: f ! : s)
valid
b Ç d Ç (b ! d)
bÇdÇ:bÇd
valid
11
s ! f = t, : s ! : f = f
Satisfiability Problems
• Many problems can be expressed as a
list of constraints. Answer is
assignment to variables that satisfy all
the constraints.
• Examples:
– Scheduling people to work in shifts at a hospital
•
•
•
•
Some people don’t work at night
No one can work more than x hours a week
Some pairs of people can’t be on the same shift
Is there assignment of people to shifts that satisfy all
12
constraints?
Conjunctive Normal Form
• Satisfiability problems are written as conjunctive
normal form (CNF) formulas:
(A  B C) (B  D) (A) (B C)
–(A  B C) is a clause, which is a disjunction of literals
– A, B, and : C are literals, each of which is a variable or the
negation of a variable.
– Each clause is a requirement which must be satisfied and it
has different ways of being satisfied.
– Every sentence in propositional logic can be written in CNF
13
Converting to CNF
14
CNF Conversion Example
15
Try this
• Convert to CNF
16
Algorithms for Satisfiability
• Given a sentence in CNF, how can we
prove it is satisfiable?
• Consider a search tree where at each level
we consider the possible assignments to
one variable, say P. On one branch, we
assume P is f and on the other that it is t.
• Given an assignment for a variable, we
can simplify the sentence and then repeat
the process for another variable.
17
Assign and Simplify Example
18
Search Example
19
Search Example
20
Search Example
21
Search Example
22
Search Example
23
Try this
• Given a sentence (T  X) (S T) (S  X)
find the satisfiability search tree
24