Transcript Propositional Logic

AI=Knowledge Representation
& Reasoning
Syntax
Semantics
Inference Procedure
Algorithm
Sound?
Complete?
Complexity
1
Some KR Languages
Propositional Logic
Predicate Calculus
Frame Systems
Rules with Certainty Factors
Bayesian Belief Networks
Influence Diagrams
Semantic Networks
Concept Description Languages
Nonmonotonic Logic
2
Propositional Logic
Syntax
Atomic sentences: P, Q, …
Connectives:  , , , 
Semantics
 Truth Tables
Inference
Modus Ponens
Resolution
Soundness and
completeness
Complexity issues.
3
Semantics
Syntax: a description of the legal
arrangements of symbols (Def “sentences”)
Semantics: what the arrangement of
symbols means in the world
Sentences
Facts
Sentences
Semantics
World
Semantics
Representation
Inference
Facts
4
Propsitional Logic: Syntax
Atoms
Literals
Sentences
Any literal is a sentence
If S1 and S2 are sentences, then
Then (S1  S2) is a sentence
Then (S1  S2) is a sentence
Then (S1
Then
 S2) is a sentence
S1 is a sentence
5
Propositional Logic: SEMANTICS
An interpretation is an assignment to each
variable either True or False.
Assignments to compound sentences are
defined by the standard truth tables:
P
Q
T F
T T F
F F F
PQ
P
Q
T F
T T T
F T F
Q
P
T T F
F F T
PQ
P
A propositional knowledge base says which
sentences must be true in the world.
6
Example Knowledge Base
(Smoke
 fire) <=> Alarm
Alarm
7
More Definitions
valid = tautology = always true
satisfiable = sometimes true
unsatisfiable = never true
1)
smoke  fire
2)
smoke  smoke
3)
smoke  fire 
4)
(smoke  fire)  (smoke  fire)
fire
8
Making Inferences
A knowledge base gives us partial information
about the world: it constrains the world to a set
of possible truth assignments.
By inference, we decide what else holds in all
of the truth assignments allowed by the
knowledge base.
Inference question: does KB = S ?
9
Proof Procedures
To decide whether KB = S, we can try to look
for a proof of S from KB.
A proof procedure is some algorithm that we
apply to a KB to produce its logical
consequences.
A proof uses:
the knowledge base,
axiom schemas
inference rules.
10
Soundness and Completeness
KB |- S: S is provable from KB.
A proof procedure is sound if:
If KB |- S, then KB |= S.
That is, the procedure produces only correct
consequences.
A proof procedure is complete if:
If KB |= S, then KB |- S.
That is, the procedure produces all the
consequences.
Ideally, the procedure should be sound and
complete. (Ideals are nice in theory).
11
Modus Ponens
From A and A  B, infer B.
Modus ponens with a few axiom schemas is
sound and complete:

A  (B  A)
A  (B  C)  ((A B)  (A  C))
( A   B)  (B  A)
More in the book.
12
Normal Forms
CNF = Conjunctive Normal Form
Conjunction of disjuncts (each disjunct =
“clause”)
(P  Q)  R
(P  Q)  R
(P  Q)  R
(P  Q)  R
P  Q  R
(P  R)  (Q  R)
13
Resolution
A  B  C,
C  D  E
A  B  D  E
Refutation Complete
Given an unsatisfiable KB in CNF,
Resolution will eventually deduce the empty clause
Proof by Contradiction
To show  = Q
Show   {Q} is unsatisfiable!
14
Resolution Example prove P
(A B C) (B) (B D)
(C A D)
(D P Q) (Q)
15
Computational Complexity
Determining satisfiability is NP-complete.
Even when all clauses have at most 3 literals.
Hence, also validity and entailment testing are
NP-complete
If all clauses have at most 2 literals, it is
polynomial.
But if the KB is in DNF, satisfiability is
polynomial.
What does this tell us about transforming a CNF
into a DNF knowledge base?
16
Horn Clauses
If every sentence in KB is of the form:
A  B  C  ...  F  Z
equivalently A  B  C  ...  F  Z
• Then Modus Ponens is
– Polynomial time, and
– Complete!
17