Part 8 Inference and Resolution for Problem Solving

Presentation Transcript

Section 8 Inference and Resolution for Problem Solving

Chapter 8 Contents (1) Normal Forms Converting to CNF Clauses The Resolution Rule Resolution Refutation Proof by Refutation Example: Graph Coloring

Chapter 8 Contents (2) Normal Forms in Predicate Calculus Skolemization Unification The Unification calculation The Resolution Algorithm Horn Clauses in PROLOG

Normal Forms A wff is in Conjunctive Normal Form (CNF) on the off chance that it is a conjunction of disjunctions: A 1 Λ A 2 Λ A 3 Λ … Λ A n where every statement, An i, is of the shape: B 1 v B 2 v B 3 v … v B n The B's are literals. E.g.: A Λ (B v C) Λ (¬A v ¬B v ¬C v D) Similarly, a wff is in Disjunctive Normal Form (DNF) in the event that it is a disjunction of conjunctions. E.g.: A v (B Λ C) v (¬A Λ ¬B Λ ¬C Λ D)

Converting to CNF Any wff can be changed over to CNF by utilizing the accompanying equivalences: (1) A ↔ B  (A → B) Λ (B → A) (2) A → B  ¬ A v B (3) ¬ (A Λ B)  ¬ A v ¬ B (4) ¬ (A v B)  ¬ A Λ ¬ B (5) ¬¬ A  A (6) A v (B Λ C)  (A v B) Λ (A v C) Importantly, this can be changed over into a calculation – this will be helpful when we come to robotizing determination.

Clauses Having changed over a wff to CNF, it is common to compose it as an arrangement of statements. E.g.: (A → B) → C In CNF is: (A V C) Λ (¬B V C) In provision shape, we compose: {(A, C), ( ¬B, C ) }

The Resolution Rule The determination govern is composed as takes after: A v B ¬ B v C A v C This reveals to us that on the off chance that we have two conditions that have a strict and its invalidation, we can consolidate them by evacuating that exacting. E.g.: on the off chance that we have {(A, C), ( ¬A, D)} We would apply determination to get {C, D}

Resolution Refutation Let us resolve: {(¬A, B), (¬A, ¬B, C), A, ¬C} We start by settling the principal provision with the second statement, in this manner taking out B and ¬B: {(¬A, C), A, ¬ C} {C, ¬C} Now we can resolve both residual literals, which gives falsum: ^ If we reach falsum, we have demonstrated that our underlying arrangement of conditions were conflicting. This is composed: {( ¬ A, B), ( ¬ A, ¬ B, C), A, ¬ C} ╞ ^

Proof by Refutation If we need to demonstrate that a sensible contention is substantial, we nullify its decision, change over it to condition shape, and afterward attempt to determine falsum utilizing determination. In the event that we infer falsum, then our statements were conflicting, which means the first contention was legitimate, since we nullified its decision.

Proof by Refutation - Example Our contention is: (A Λ ¬ B) → C A Λ ¬ B  C Negate the conclusion and change over to provisos: {( ¬ A, B, C), A, ¬ B, ¬ C} Now resolve: {(B, C), ¬ B, ¬ C} {C, ¬ C} ^ We have come to falsum, so our unique contention was substantial.

Refutation Proofs in Tree Form It is regularly sensible to speak to a nullification evidence in tree frame: For this situation, the proof has bombed, as we are left with E rather than falsum.

Example: Graph Coloring Resolution negation can be utilized to figure out whether an answer exists for a specific combinatorial issue. For instance, for diagram shading, we speak to the task of hues to the hubs and the requirements viewing edges as suggestions, and endeavor to demonstrate that the entire arrangement of provisos is predictable. This does not reveal to us how to shading the diagram, basically that it is conceivable.

Example: Graph Coloring (2) Available hues are r (red), g (green) and b (blue). A r implies that hub A has been shaded red. Every hub must have precisely one shading: A r v A g v A b ¬A r v ¬A g (  A r → ¬A g ) ¬A g v ¬A b ¬A b v ¬A r If (A,B) is an edge, then: ¬A r v ¬B r ¬A b v ¬B b ¬A g v ¬B g Now we build the entire arrangement of statements for our chart, and attempt to check whether they are predictable, utilizing determination.

Normal Forms in Predicate Calculus A FOPC expression can be placed in prenex ordinary frame by changing over it to CNF, with the quantifiers moved to the front. For instance, the wff: (  x)(A(x) → B(x)) → (  y)(A(y) Λ B(y)) Converts to prenex ordinary shape as: (  x)(  y)(((A(x) v A(y)) Λ (¬B(x) v A(y)) Λ (A(x) v B(y)) Λ (¬B(x) v B(y))))

Skolemization Before determination can be connected,  mus t be evacuated, utilizing skolemization. Factors that are existentially measured are supplanted by a steady:  (x) P(x) is changed over to: P(c) c m ust not as of now exist in the expression.

Skolem capacities If the existentially measured variable is inside the extent of an all around evaluated variable, it must be supplanted by a skolem work, which is an element of the all around measured variable. Sounds muddled, however is really straightforward: (  x)(  y)(P(x,y)) Is Skolemized to give: (  x)(P(x,f(x)) After skolemization,  is dropped, and the expression changed over to provisos in the standard way.

Unification (1) To determine provisos we frequently need to make substitutions. For instance: {(P(w,x)), (¬P(y,z))} To determine, we have to substitute y for w, and z for x, giving: {(P(y,z)), (¬P(y,z))} Now these take steps to give falsum.

Unification (2) A substitution that empowers us to determine an arrangement of statements is known as a unifier. We compose the unifier we utilized above as: {y/w, z/x} A unifier (u) is a most broad unifier (mgu) if some other unifier can be shaped by the organization of u with some other unifier. A calculation can be produced which gets a most broad unifier for any arrangement of provisos.

The Resolution Algorithm 1 First, discredit the conclusion and add it to the rundown of suppositions. 2 Now change over the suspicions into Prenex Normal Form 3 Next, skolemize the subsequent expression 4 Now change over the expression into an arrangement of provisos 5 Now settle the conditions utilizing reasonable unifiers. This calculation implies we can compose programs that consequently demonstrate hypotheses utilizing determination.

Horn Clauses in PROLOG (1) PROLOG utilizes determination. A Horn statement has at most one positive strict: A v ¬B v ¬C v ¬D v ¬E … This can likewise be composed as a ramifications: B Λ C Λ D Λ E → An In PROLOG, this is composed: A :- B, C, D, E

Horn Clauses in PROLOG (2) Horn provisions can express standards: A :- B, C, D Or certainties: A :- Or objectives: :- B, C, D, E If an arrangement of provisos is substantial, PROLOG will demonstrate it utilizing determination and profundity first pursuit.