Conjunctive normal form -artificial intelligence , Computer Engineering

Conjunctive Normal Form -artificial intelligence :

For the resolution law to determine two sentences, they should both be in a normalized format known as conjunctive normal form, which is generally cut to CNF. This is an unlucky name because the sentences themselves are made up of orders of disjunctions. It is implicitly understood that the whole knowledge base is a huge conjunction of the sentences, which is where conjunctive normal form haveits name. So, CNF is basically a conjunction of disjunctions. The disjunctions are made up of literals which may either be a predicate or the negation of a predicate (for propositional read a proposition or the negation of a proposition):

So, CNF sentences are of the form:

(p1p2 ∨      ...  ∨ pm)  (q1 ∨ q2 ∨ ...∨qn)∧  etc.

Where each pi and qj  is a truthful. Note that we call the disjunction of such truthful a Clause. As a concrete example,

Likes (George, X) ∨ likes (tony, George)∨¬ is mad(Maggie)

Is in conjunctive normal form, but:

Likes (George, X) ∨ likes (tony, George) -> ¬ is mad (Maggie) ∧ is mad (tony) is not in CNF.

The following eight-stage method converts any sentence into CNF:

1. remove arrow connectives by rewriting with

P <-> Q  => (P ->Q) ∧(Q ->P)

P<-> Q  =>   ¬P ∨ Q

2.   Move ¬ inwards using De Morgan's laws (inc. quantifier versions) and double negation:

¬ (P ∨ Q)   =>   ¬P ∧ Q

¬ (P ∧ Q)   =>   ¬P ∨  Q

¬ ∀X. P => X. ¬P

¬∃X. P        =>        X. ¬P

¬¬P              =>   P

3. Rename variables distant: the similar variable name may be reused a lot of time for different variables, within one sentence or among several. To ignore uncertainty later rename every dissimilar variable with a exclusive name.

4. Move quantifiers outwards:  the sentence is now in a form where all the quantifiers may be moved strongly to the outside without disturbing the semantics, provided they are reserved in the similar order.

5. Solemnize existential variables by replacing them with Solemn constants and methods. This is similar to the existential removal law from the last  format we  just  replace a word  for  each  existential  variable  so as to  represents  the 'something' for which it handles. If there are no preceding unique quantifiers the 'something' is immediately a new constant. However, if there are then we use a method that may have all these preceding unique variables as arguments. When we are done we immediately drop all the general quantifiers. This leaves a quantifier-free statement . For example:

 X. ∃Y. person(X)-> has(X, Y) heart(Y) is Solemnized like

person (X) ->has(X, f(X)) ∧heart(f(X))

6. Distribut ∧ over  to get a conjunction of disjunctions. This includes rewriting with:

P ∧(Q ∨R)   =>   (P ∧Q) ∨(P ∧R)

(P∨Q)∧ R => (P∧R)   (Q ∧ R)

7. Flatten binary connectives: swap nested ∧ and ∨ with flat lists of conjuncts and disjoints:

P ∧(Q∧ R)   =>   P∧ Q ∧ R

(P∧ Q)∧ R   =>   P ∧ Q∧ R

P ∨ (Q ∨ R)   =>   P∨Q∨R 

(P ∨ Q) ∨ R   =>   P ∨ Q ∨ R

8. The sentence is now in CNF. more simplification may take place by avoiding duplicate literals and sinking any clause which contains both A and ¬A (one will be right, so the clause is always right. In the conjunction of clauses we need everything to be exact, so  we can drop it.) There is an another possible final step that takes it to Kowalski normal form, also famous as implicative normal form (INF):

9. Reintroduce implication  by collecting up all the negative literals (the negated ones)  and  making  their  conjunction  N,  then  taking  the  disjunction  P  of  the affirmative literals, and forming the logically equivalent clause N-> P.

Posted Date: 10/2/2012 9:25:25 AM | Location : United States

Related Discussions:- Conjunctive normal form -artificial intelligence , Assignment Help, Ask Question on Conjunctive normal form -artificial intelligence , Get Answer, Expert's Help, Conjunctive normal form -artificial intelligence Discussions

Write discussion on Conjunctive normal form -artificial intelligence
Your posts are moderated
Related Questions
Q. Illustrate Clock signals of clock pulse generator? Synchronization in a sequential circuit is attained by a clock pulse generator that gives continuous clock pulse.  Figure

By now you can write procedures both internal andexternal and pass parameters particularly through stack.Let's us use these concepts to see how assembly language can be interfaced

Implication connective - Modus ponens rule: We notice that this is a trivial example, so it highlights how we use truth tables: as the first line is the only one when both abo

Q. Analysts in Computer Operations? Computer Operations: All of the shared computers comprising mainframes, minicomputers and other computers are put to operation and same is c

What is a matchcode? A match code is an aid to finding records keeps in the system whenever an object key is needed in an input field but the user only knows other (non-key) in

Q. Pros and Cons of general purpose register architecture? General Purpose Register Architecture: Pros and Cons Registers can be employed to store variables as it decrea

Q. Explain XNOR gate with three input variable and draw necessary circuits. Q. Simplify FOLLOWING Using K-Map 1. m0 + m1 + m6 + m7 + m12 + m13 + m8 + m9 2. m0 + m2 + m4 +

Q. What do you mean by Processor Arrangements? It is a very common event in data parallel programming to combine many processors to execute specific tasks. To achieve this obje

What is testing? List its types. Testing ensures that the application is suitable for actual use and that it truthfully satisfies the requirements. Types are: Unit te

How adaptive transmission helps TCP to maximize throughput on each connection? To know how adaptive retransmission helps TCP maximize throughput upon all connection, see a case