
Theory of Computation Theoretical Computer Science  Automata Theory, Computability Theory, and Computational Complexity Theory 
 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 1edit of another formula fi’ which is turn a kedit of fi. So fi1 is a 2 –edit of a formula fi if it is a 1 –edit of a 1edit of a 1edit of fi, a 3edit is a 1edit 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 kedit 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 krobust if every kedit of fi is satisfiable. Show that for each fixed k, the problem of determining whether or not fi is k – robust is NPComplete. ************************************************** ************************************************** ************************************* Please help me how to solve this problem...............................Please...... ......................................... ************************************************** ************************************************** ********************************* 
My Computer Forum is free to register and we welcome everyone! 

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 