2-SAT (X1V-X2)A(X2V-x3)(X4VX3)(x5VX1)(X4V-X5) clauses X1 X2 X3 Xa X5 current T T T T T Find an unsatisfied clause:none We have a satisfying assignment!=2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: none • We have a satisfying assignment! =) x1 x2 x3 x4 x5 current T T T T T clauses