2-SAT problem

Boolean satisfiability is a NP-complete problem but, a special case of it can be solved in polynomial time. This special case is called cas 2-SAT or 2-Satisfiability.

We have explained the basic ideas to understand this problem with depth along with solution.

Boolean Satisfiability
Boolean formulas

Boolean formulas are ones where the variables can take values 0 (false) or 1 (true). Some operators in Boolean formulas:

Name
Operator




not
$ \neg a $


and
$ a \wedge b $


or
$ a \vee b $


i...