1
$\begingroup$

What are the rules pertaining to 3SAT as to the actual boolean equation?

The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR operators i.e. (x1 & x2 | x3) or do they have to remain consistent i.e. (x1 & x2 & x3) or (x1 | x2 | x3)?

That being said when connecting clauses together do the boolean operators have to be consistent?

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) & (x1 & x2 & x3)

or                                                                             

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) | (x1 & x2 & x3)

or can they be mixed up like

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) & (x1 & x2 & x3)

or                                                                             

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) | (x1 & x2 & x3)

Can a 3SAT problem just be a huge jumble of different logic operators or do they have to remain consistent throughout the equation? Ever example I have seen has consistent operators and I cant seem to find the answer to the question anywhere.

$\endgroup$
3

1 Answer 1

1
$\begingroup$

3SAT is a problem of deciding satisfiability of boolean formula in 3CNF form: this means that

  1. Each clause has either exactly 3 different literals in each clause or at most 3 literals in each clause, according to different definitions.

  2. Only $\lor$ operators can be used inside clauses (not counting varible negations).

  3. Only $\land$ operators can be used outside clauses.

[General] SAT problem does not have a limit on number of literals in a clause and Circuit SAT allows any boolean formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.