Conjunctive normal form -artificial intelligence , Computer Engineering

Assignment Help:

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.


Related Discussions:- Conjunctive normal form -artificial intelligence

Explain the working of a three bit binary ripple counter, With the help of ...

With the help of clocked JK flip flops and waveforms, explain the working of a three bit binary ripple counter. Write truth table for clock transitions. Ans. Three-Bit Binary Rip

Determine the output waveforms for and and or gates, The voltage waveforms ...

The voltage waveforms shown in given fig. are applied at the inputs of 2-input AND and OR gates. Determine the output waveforms. Ans. The Output waveforms for AND and O

Quick sort exhibit its worst-case behaviour, In which input data does the a...

In which input data does the algorithm quick sort exhibit its worst-case Behaviour? The Quick Sort method exhibits its worst-case behavior when the input data is " Already Comp

Generates sequence code, The basic project will have each group generate a ...

The basic project will have each group generate a sequence of 1's and 0's using  the Motorola 688HC11 board to turn ON and then turn OFF the TV set installed in ATRC 306. Each tele

Can we use flow logic control key words in abap/4, Can we use flow logic co...

Can we use flow logic control key words in ABAP/4 and vice-versa The flow control  of a dynpro having os a few statements that syntactically ressemble ABAP/4  statements .Thou

Programming, Write a procedure for each of the following: (i) To find the m...

Write a procedure for each of the following: (i) To find the maximum MAX of the values in the list. (ii) To find the average MEAN of the values in the list. (iii) To find the produ

What is server in sap terminology, What is Server in SAP terminology? ...

What is Server in SAP terminology? A component can having of one process or a group and is then known as the server for the respective service.

Show the code conversion with example, Q. Show the Code Conversion with exa...

Q. Show the Code Conversion with example? The conversion of data from one form to another is required. Consequently we will discuss an illustration for converting a hexadecimal

Cisc approach - cisc architecture, CISC Approach - CISC architecture: ...

CISC Approach - CISC architecture: The main goal of CISC architecture is to finish a task in as few lines of assembly as possible as. This is gain by building processor hardwa

How transmission bridges help in satisfying the connectivity, How do tra...

How do transmission bridges help in satisfying the connectivity? A usual transmission bridge is demonstrated in figure. The series capacitance and the shunt inductances of

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd