Scribd
Upload
3 views11 pages

Resolution

The document discusses Conjunctive Normal Form (CNF) in propositional logic, defining literals, clausal sentences, and clauses. It explains the resolution rule and how it leads to a complete inference procedure by showing that every sentence can be expressed as a conjunction of clauses. Additionally, it outlines a resolution algorithm that uses proof by contradiction to derive conclusions from given clauses.

Uploaded by

kollatirevanthsivasai22
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views11 pages

Resolution

The document discusses Conjunctive Normal Form (CNF) in propositional logic, defining literals, clausal sentences, and clauses. It explains the resolution rule and how it leads to a complete inference procedure by showing that every sentence can be expressed as a conjunction of clauses. Additionally, it outlines a resolution algorithm that uses proof by contradiction to derive conclusions from given clauses.

Uploaded by

kollatirevanthsivasai22
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

RESOLUTION

Conjunctive Normal Form


Conjunctive Normal Form
• A literal is either an atomic sentence or a negation of an atomic
sentence.
• Eg: p, ¬p
• A clausal sentence is either a literal or a disjunction of literals.
• Eg: p, ¬p, ¬p ∨ q
• A clause is the set of literals in a clausal sentence
• Eg: {p}, {¬p}, {¬p, q}
Conjunctive Normal Form
• The resolution rule applies only to clauses.

• How, Resolution lead to a complete inference procedure for all of


propositional logic?

• every sentence of propositional logic is logically equivalent to a


conjunction of clauses.

• A sentence expressed as a conjunction of clauses is said to be in


conjunctive normal form or CNF (Product of Sum)
Conjunctive Normal Form -converting to CNF
• B1,1 ⇔ (P1,2 ∨ P2,1)
Resolution Principle
A Resolution algorithm
• Inference procedures based on resolution work by using the principle
of proof by contradiction.
• to show that KB |= α, we show that (KB ∧ ¬α) is unsatisfiable.
• We do this by proving a contradiction.
• Eg: When the agent is in [1,1], there is no breeze, so there can be no
pits in neighboring squares. The relevant knowledge base is
A Resolution algorithm
• α is say, ¬P1,2
• convert (KB ∧ ¬α) into CNF.
Resolution algorithm
Suppose, for example, we are given the clauses {¬p, r} and {¬q, r} and {p, q}.
Then we can derive the conclusion {r} as shown below.
Resolution algorithm
• As an example, consider the clauses {p, q}, {p, ¬q}, {¬p, q}, and {¬p, ¬q}. There is
no truth assignment that satisfies all four of these clauses.
Resolution algorithm
• We have three premises - p, (p ⇒ q), and (p ⇒ q) ⇒ (q ⇒ r).
• Our job is to prove r.

You might also like