how to convert SAT to 3SAt

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
0
down vote

favorite
1












My teacher showed these steps when converting SAT to 3SAT (he was working with an example).



He said to construct a formula F1



F1 = y1 and (y1 bidirectional arrow (y2 and not x2))
 and (y2 bidirectional arrow (x1 or y3))
 and (y3 bidirectional arrow not y4)
 etc.


He got F1 by converting a SAT formula to a parse tree (e.g., the formula x1 and x2 would is converted into a tree where and is the root (labelled y1) and the left child is x1, right child is x2).



After getting F1, he said to convert each case into a CNF formula. He then said the first case (y1 bidirectional arrow (y2 and not x2)) equals the following CNF formula:



(not y1 or not y2 or not x2)
and (not y1 or y2 or not x2)
and (not y1 or y2 or x2)
and (y1 or not y2 or x2)


Can someone explain how my teacher went from the first case (y1 bidirectional arrow (y2 and not x2)) to the CNF formula above?




computational-complexity np-complete satisfiability




share|cite|improve this question
























    up vote
    0
    down vote

    favorite
    1












    My teacher showed these steps when converting SAT to 3SAT (he was working with an example).



    He said to construct a formula F1



    F1 = y1 and (y1 bidirectional arrow (y2 and not x2))
     and (y2 bidirectional arrow (x1 or y3))
     and (y3 bidirectional arrow not y4)
     etc.


    He got F1 by converting a SAT formula to a parse tree (e.g., the formula x1 and x2 would is converted into a tree where and is the root (labelled y1) and the left child is x1, right child is x2).



    After getting F1, he said to convert each case into a CNF formula. He then said the first case (y1 bidirectional arrow (y2 and not x2)) equals the following CNF formula:



    (not y1 or not y2 or not x2)
    and (not y1 or y2 or not x2)
    and (not y1 or y2 or x2)
    and (y1 or not y2 or x2)


    Can someone explain how my teacher went from the first case (y1 bidirectional arrow (y2 and not x2)) to the CNF formula above?




    computational-complexity np-complete satisfiability




    share|cite|improve this question






















      up vote
      0
      down vote

      favorite
      1









      up vote
      0
      down vote

      favorite
      1






      1





      My teacher showed these steps when converting SAT to 3SAT (he was working with an example).



      He said to construct a formula F1



      F1 = y1 and (y1 bidirectional arrow (y2 and not x2))
       and (y2 bidirectional arrow (x1 or y3))
       and (y3 bidirectional arrow not y4)
       etc.


      He got F1 by converting a SAT formula to a parse tree (e.g., the formula x1 and x2 would is converted into a tree where and is the root (labelled y1) and the left child is x1, right child is x2).



      After getting F1, he said to convert each case into a CNF formula. He then said the first case (y1 bidirectional arrow (y2 and not x2)) equals the following CNF formula:



      (not y1 or not y2 or not x2)
      and (not y1 or y2 or not x2)
      and (not y1 or y2 or x2)
      and (y1 or not y2 or x2)


      Can someone explain how my teacher went from the first case (y1 bidirectional arrow (y2 and not x2)) to the CNF formula above?




      computational-complexity np-complete satisfiability




      share|cite|improve this question












      My teacher showed these steps when converting SAT to 3SAT (he was working with an example).



      He said to construct a formula F1



      F1 = y1 and (y1 bidirectional arrow (y2 and not x2))
       and (y2 bidirectional arrow (x1 or y3))
       and (y3 bidirectional arrow not y4)
       etc.


      He got F1 by converting a SAT formula to a parse tree (e.g., the formula x1 and x2 would is converted into a tree where and is the root (labelled y1) and the left child is x1, right child is x2).



      After getting F1, he said to convert each case into a CNF formula. He then said the first case (y1 bidirectional arrow (y2 and not x2)) equals the following CNF formula:



      (not y1 or not y2 or not x2)
      and (not y1 or y2 or not x2)
      and (not y1 or y2 or x2)
      and (y1 or not y2 or x2)


      Can someone explain how my teacher went from the first case (y1 bidirectional arrow (y2 and not x2)) to the CNF formula above?





      computational-complexity np-complete satisfiability





      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Aug 8 at 20:09









      user2719875

      1517




      1517

























          active

          oldest

          votes











          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );








           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2876535%2fhow-to-convert-sat-to-3sat%23new-answer', 'question_page');

          );

          Post as a guest






















          active

          oldest

          votes













          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes










           

          draft saved


          draft discarded


























           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2876535%2fhow-to-convert-sat-to-3sat%23new-answer', 'question_page');

          );

          Post as a guest
































































          -

          這個網誌中的熱門文章

          How to combine Bézier curves to a surface?

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
          閱讀完整內容

          Mutual Information Always Non-negative

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 '12 at 15:38 Cameron Buie 83.6k 7 71 154 asked Jun 17 '12 at 15:30 Omri 359 3 13 3 Convexity of the function $tmapsto tlog t$. – Did Jun 17 '12 at 15:33 In addition, the convexity properties require the coefficients in the linear combination sum 1. Then, as p(x,y) is a probability distribution, it fullfits such condition. – Francisco Javier Delgado Ceped Aug 10 at 18:44 add a comment  |  up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 ...
          閱讀完整內容

          Why am i infinitely getting the same tweet with the Twitter Search API?

          圖片
          up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia...
          閱讀完整內容