Eight-stage process - conjunctive normal forms, Computer Engineering

Assignment Help:

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.


Related Discussions:- Eight-stage process - conjunctive normal forms

Difference between a window and a frame?, The Frame class extends Window to...

The Frame class extends Window to describe a main application window that can have a menu bar. A window can be modal.

Explain fixed point representation, Q. Explain Fixed Point Representation? ...

Q. Explain Fixed Point Representation? The fixed-point numbers in binary has a sign bit. A positive number has a sign bit 0 whereas negative number has a sign bit 1. In fixed-p

Explain binary number system, Explain Binary number system. Ans. Bi...

Explain Binary number system. Ans. Binary Number System The number of system along with base or Radix two is termed as the Binary Number System. To show the number, 0 a

Concept of multithreading, Concept of Multithreading: These troubles incre...

Concept of Multithreading: These troubles increase in the design of large-scale multiprocessors such as MPP as discussed above. Thus, a solution for optimizing this latency should

Speed up factor, Remember, the value of α is between 0 and 1. Now, let us p...

Remember, the value of α is between 0 and 1. Now, let us put some values of α and compute the speed up factor for increasing values of number of processors.  We get that the S(N) k

Bounded rationality in decision making, Q.What do you mean by the term 'bou...

Q.What do you mean by the term 'bounded rationality in decision making'? Maximizing the outcomes of a decision is an ideal stage. Habitually it is an impossible thing. The caus

What is reentrant tasks and functions, What is reentrant tasks and function...

What is reentrant tasks and functions Tasks and functions without optional keyword automatic are static , with all declared items being statically allocated. These items will b

Convert logic circuit in a binary code, The logic circuit given below, conv...

The logic circuit given below, converts a binary code y 1 y 2 y 3 into Ans. Gray code is X1 = Y1,   X2 = Y1 XOR Y2  ,   X3 = Y1 XOR Y2 XOR Y3 For

What is the purpose of guard bits, What is the purpose of guard bits used i...

What is the purpose of guard bits used in floating point operations? The guard bits are the extra bits which are used to retain the in-between steps to enhance the accuracy in

Explain about microcomputers, Q. Explain about Microcomputers? Microco...

Q. Explain about Microcomputers? Microcomputers: A microcomputer's CPU is a microprocessor. They are characteristically used as single usercomputer though present day microco

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