Here is a
very simple algorithm to compute an approximal solution. How does it work? For each variable we compute the number of clauses in which the variables appears positive, and we compute the number of clauses in which the variable appears negative. Now if the number of clauses in which the variables appears positive is at least equal to the number of clauses in which the variable appears negative, then we set the value of the variable to true, otherwise we set the value of the variable to false. Once we have set the value of one variable, maybe we can simplify the formula because some clauses are satisfied and some clauses disappeared. Once we have simplified the formula, we start with a next Boolean variable. | ![]() |