Modéliser un problème en SAT consiste à traduire chaque contrainte en clauses. Deux contraintes reviennent partout, et leur coût n'est pas le même.
Les deux contraintes
Au moins un parmi les variables x1 à xn : au moins l'une doit être vraie.
Au plus un : on interdit chaque paire, en disant pour chaque couple que les deux ne peuvent pas être vraies ensemble.
Objectif
Pour quatre variables, donner le nombre de clauses et de littéraux demandés.
« Exactement un » combine les deux contraintes.