Pierwszym krokiem jest przekształcenie formuły do postaci koniunkcyjnej (CNF). W tej postaci: formuła jest koniunkcją (i) klauzul każda klauzula jest alternatywą (lub) literałów każdy literał jest zmienną lub jej negacją. Przykładowo, poniższa formuła jest w postaci CNF ( oznacza negację):
Taka formuła jest spełnialna jeśli możemy przyporządkować zmiennym wartości prawda/fałsz tak żeby w każdej klauzuli przynajmniej jeden literał był prawdziwy. Przykładowo dla powyższej formuły możemy przyporządkować x2 fałsz i x4 prawdę. Problem stwierdzenia czy dana formuła CNF jest spełnialna jest również NP-zupełny i nazywa się CNF-SAT.
Opiszemy teraz algorytm wielomianowy przekształcający problem CNF-SAT w problem zbioru niezależnego. Na początku tworzymy wierzchołek dla każdego literału w formule, łącznie z jego powtórzeniami. Następnie łączymy krawędziami: Każdy literał z każdą jego negacją Każde dwa literały które należą do tej samej klauzuli
Twierdzimy, że powstały graf zawiera niezależny zbiór rozmiaru k wtedy i tylko wtedy gdy formuła od której zaczęliśmy była spełnialna.