Re: 3CNF Formula

On Apr 16, 11:20 pm, "busy...@xxxxxxxxx" <busy...@xxxxxxxxx> wrote:
First of all, separate variables which have the same value in the both
satisfying assignment. In your example it is x2. For each of these
variables create a 1-literal clause -- with negation if the variable
is 0 in both assignments and without negation otherwise. Next,
consider each pair of the remaining variables, let it be (xi,xj). If
they are equal to each other in the both assignments, impose (~xi OR
xj) & (xi OR ~xj). Otherwise, impose (~xi OR ~xj) & (xi OR xj). So,
your example will yield:

x2 & (~x1 OR ~x3) & (x1 OR x3)

--Stashttp://www.busygin.dp.ua

On Apr 16, 11:17 pm, "meyousikmann" <meyousikm...@xxxxxxxxx> wrote:



I am working with 3CNF formulae and trying to figure out if there is some
logical way to find a formula given a pair of satisfying assignments. For
example, if I want to find a formula that can only be satisfied by the two
assignments x1=0,x2=x3=1 and x1=x2=1, x3=0, is there some method to make
this easy. Perhaps a truth table or Karnaugh map will help, but I am unsure
how to apply either to find a solution. I am trying to understand some
things about boolean algebra and digital logic and this item seems to escape
me.- Hide quoted text -

- Show quoted text -

Thanks so much for the pointers.

.

Relevant Pages

  • Re: 3CNF Formula
    ... separate variables which have the same value in the both ... satisfying assignment. ... is 0 in both assignments and without negation otherwise. ... Perhaps a truth table or Karnaugh map will help, but I am unsure ...
    (comp.theory)
  • A Class of 3SAT Solvable in Polytime
    ... If there is an assignment of variables ... in polynomial time. ... Assume we transform every clause in F ... Fhas a satisfying assignment such ...
    (comp.theory)
  • A Class of 3SAT Solvable in Polytime
    ... If there is an assignment of variables ... in polynomial time. ... Assume we transform every clause in F ... Fhas a satisfying assignment such ...
    (sci.math)
  • A Class of 3SAT Solvable in Polytime
    ... If there is an assignment of variables ... in polynomial time. ... Assume we transform every clause in F ... Fhas a satisfying assignment such ...
    (sci.logic)
  • Re: A Class of 2SAT is NP-Complete
    ... because you need 3 literals per clause to represent a logic gate: ... the original expression is satisfiable. ... This is a satisfying assignment for the 2SAT expression: ... b2 maps to x1 in the second clause. ...
    (comp.theory)