Menu
I have a boolean formula: (x_{1} or x_{2}) and (x_{3} or x_{4}) and ..... and (x_{2r-1} or x_{2r}), where x_{i} belongs to the set: {p_{1}, p_{2}, ... p_{99} , ~p_{1}, ~p_{2}, ... ~p_{99} } and I have to determine if for some values of x_{i} given formula can be true.
I know that it is in general computationally difficult. But is there any quite fast way I can do this particular problem? So far I've tried backtracking - that is in recursion I substitude every possible value (0 or 1 so not many) for every possible variable and every variable, which hasn't got value yet, is trivially true. Before I go deeper into recursion I chceck the formula (even when not every variable has got a value) and if it is false, I don't go deeper. But it is too slow. Any ideas? I would be very grateful for help.
284
Satisfiable : If the Boolean variables can be assigned values such that the formula turns out to be TRUE, then we say that the formula is satisfiable. Unsatisfiable : If it is not possible to assign such values, then we say that the formula is unsatisfiable.
The problem of determining whether a formula in propositional logic is satisfiable is decidable, and is known as the Boolean satisfiability problem, or SAT. In general, the problem of determining whether a sentence of first-order logic is satisfiable is not decidable.
Because 3-SAT is a restriction of SAT, it is not obvious that 3-SAT is difficult to solve. Maybe the restriction makes it easier. But, in reality, 3-SAT is just as difficult as SAT; the restriction to 3 literals per clause makes no difference.
If you only have two variables per OR clause, then you have 2-SAT, which has a linear-time solution.
67
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
