2SAT

Avem o expresie cu operanzi de tip boolean care are următoarea structură: subexpresii de forma "p sau q" (deci un "sau" între doi operanzi, nu mai mult) unite prin "și". Trebuie să asociem valori booleene la operanzii necunoscuți astfel încât să facem ca expresia să fie adevărată.