Eight-stage process - conjunctive normal forms, Computer Engineering

Eight-stage process - Conjunctive normal forms:

Hence we notice the following eight-stage process converts any sentence with CNF as: 

1.  Eliminate all arrow connectives by rewriting into 

      P ↔ Q    =>   (P  →Q) ^  (Q → P)

      P → Q   =>   ¬P ? Q

2.  Just move ¬ inwards requiring De Morgan's laws in inc. quantifier versions and double

3.  Here rename variables apart: as the same variable name may be reused several times for different variables, contained by one sentence or between several. However to avoid confusion later rename each distinct variable into a unique name. 

4. Now move quantifiers outwards: as the sentence is now in a form whether all the quantifiers can be moved safely to the outside else affecting the semantics, which are provided they are kept in the same order. 

5. Skolemise existential variables  by replacing them into  Skolem constants and functions. But this is similar to the existential elimination rule from the last lecture: as we just substitute a term for each existential variable such are represents the 'something' for that it holds. Suppose if there are no preceeding universal quantifiers the 'something' is a fresh constant. Moreover, if there are then we use a function that takes all these preceeding universal variables as arguments then we're done we just drop all the universal quantifiers. Thus this types  leaves a quantifier-free sentence.

Posted Date: 1/11/2013 6:17:44 AM | Location : United States

Related Discussions:- Eight-stage process - conjunctive normal forms, Assignment Help, Ask Question on Eight-stage process - conjunctive normal forms, Get Answer, Expert's Help, Eight-stage process - conjunctive normal forms Discussions

Write discussion on Eight-stage process - conjunctive normal forms
Your posts are moderated
Related Questions
How is recursion handled internally? Internally, every recursive call to a function requires storing the intermediate values of the parameters and local variables in a run time

Explain about the Arithmetic Shift An arithmetic shift micro operation shifts the signed binary number to left or right. The effect of the arithmetic shift left operation is

1.  The network shown in figure 2 uses neurons with:             (a) Unipolar Binary;             (b) Bipolar Binary. Calculate a table of responses to all four possi

The memory allocation scheme subject to “external” fragmentation is? Segmentation is the memory allocation scheme subject to “external” fragmentation.

Draw the logic circuit using minimizaed equation by K-map for the simplified function using NOR gates only. F (A, B, C, D) = Π M (1, 2, 3, 8, 9, 10, 11,14) ⋅ d (7, 15) Ans

Q. Explain Sample Instruction Format of MIPS instruction? All MIPS instructions are of same size and are 32 bits long. MIPS designers chose to keep all instructions of same len

What is Monkey testing? The monkey testing is the process of testing here and there for judging the application trying to observe the accessing dissimilar functionalities is i

A ppropriate Problems for Decision Tree Learning - Artificial intelligence It is a expert job in AI to select accurately the right learning representation for a particular lea

What does the term convergence mean regarding E-commerce? Convergence regarding e-commerce: The capability to leverage and integrate the different data sources and proces

Refining the Ratio Analysis Basically, refinement leads to purity. Thus to get a cleaner, more understandable and consistent design need to iterate analysis process.  R