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
What is a Demultiplexer ? Ans. Demultiplexer has similar circuit as decoder but here E is obtained as the particular input line, the output lines are similar as decode

Q. Register-to-register operands in RISC? Register-to-register operands: In RISC machines operation which access memories are LOAD and STORE. All other operands are kept in reg

In a logical system, a judgement is a statement that is either true or false. So far, you are most familiar with the type of judgement "A is true", which is often simply abbreviate

Q. Show the Major benefits of microprocessor? Microprocessor is a complete CPU on a single chip. The major benefits of microprocessor are:  Powerful butCompact; can

Presumably for heightened tension - first-order logic: As an aside, it's worth pointing out that - presumably for heightened tension - in most Sherlock Holmes books, the m

How many lines of address bus must be used to access 2048 bytes of memory when available RAM chips 128 × 8.  How many lines of these will be common to each chip? Ans. AS chips

How do you ensure that our records are scanned accurately? Not only do we have a highly trained and capable staff, we also have quality controls in place to make sure your reco

A header in CGI script can specify? A header into CGI script can give format of document and New location of perticular the document.

Binary codes exist for any fundamental representation. Binary codes can be created for any set of discrete elements for example colors, spectrum, musical notes, chessboard position

Hazard in pipeline - computer architecture: A hazard in pipeline .-removing a hazard frequently need that some instructions in the pipeline to be permitted to proceed as othe