My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Closed Thread
 
LinkBack Thread Tools Display Modes
December 4th, 2010, 08:47 PM   #1
 
Joined: Dec 2010
Posts: 2
Problem Related To Propositional Formula

Problem given to me such a way,

The parse tree of a propositional formula is defined by induction on the formula :

· The parse tree of true is a tree consisting of a single node labelled true, and similarly for false.

· The parse tree of proposition p is a tree consisting of a single node labelled p.

· The parse tree for –fi consists of a root node labelled –(negation) having only one child, which is the parse tree of Fi.

· The parse tree of fi ^ Fi’ has a root node labelled with ^, which has two subtrees, the parse tree of Fi and the parse of Fi’, and similarly for V.

For Example, the parse tree of (p ^ -p)Vq consists of 6 nodes: a root node r1 labelled V, a child r2 of the root labelled q, a child r3 of the root labelled ^; a child r4 of r3 labelled p, another child r5 of r3 labelled –(neg), and a child r6 of r5 labelled p.

A formula edit operation for formula fi is of the form replace(i,p(row)) where i is a node in the parse tree of fi whose subtree has depth at most 2, and p (row) is a “small” formula. That is, p(row) is either:

· A proposition

· The negation of a proposition

· True of false

· Of the form AVB, where A and B are both either propositions or negations of propositions

· Of the form A^B, where A and B are both either propositions or negations of propositions

The application of an edit operation o=replace(i,p(row)) to a parse tree is defined via replacing node i by the parse tree of p(row). As with word edits, the application is defined to do nothing if argument is improper. So, if i is not a node of required depth in the parse tree , the operation does nothing.

The application of an edit to a formula fi is defined by applying the edit to the parse tree of fi, and taking the formula whose parse tree is produced – the formula produced is 1 – edit of Fi.

We also consider fi itself to be a 1 – edit of fi.

A k edit of a formula fi is defined inductively: fi1 is a k+1 – edit of fi if it is a 1-edit of another formula fi’ which is turn a k-edit of fi. So fi1 is a 2 –edit of a formula fi if it is a 1 –edit of a 1-edit of a 1-edit of fi, a 3-edit is a 1-edit of a 1 –edit of a 1 – edit of fi, and so forth.



Question:- Show that for any two formulas fi and fi’, there is k so that fi is a k-edit of some formula fi’’ where fi’’ is logically equivalent to fi’. That is, we can edit any formula to make it equivalent to another formula.

Question 2:- A propositional formula fi is said to be k-robust if every k-edit of fi is satisfiable.

Show that for each fixed k, the problem of determining whether or not fi is k – robust is NP-Complete.

************************************************** ************************************************** *************************************
Please help me how to solve this problem...............................Please...... .........................................
************************************************** ************************************************** *********************************
ajitjjn is offline  
 

My Computer Forum is free to register and we welcome everyone!

Closed Thread

  My Computer Forum > Computer Science Forum > Theory of Computation

Tags
formula, problem, propositional, related



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Turbo C++ compiler related problem chetanbhasin Programming 4 April 3rd, 2011 06:25 AM





Copyright © 2018 My Computer Forum Forum. All rights reserved.