Perché la riduzione da 3SAT a è lavoro?

Question

Stavo leggendo della riduzione da 3Sat (Input: formula) a Set indipendente (Input (Graph, K)) Per dimostrare che quest'ultimo è in completamento NP. La riduzione che ho visto seguire i prossimi passaggi:

1. Per ogni clausola all'ingresso, creare un nodo per ogni variabile che contiene nel caso in cui non esista ancora. Quindi, crea un $ k_3 $ con questi nodi.
2. Crea un vantaggio tra un nodo e la sua negazione.

Un esempio che ho trovato:

Mentre dimostra che questa riduzione è corretta, dicono:

$ Destra $) Se la formula è soddisfacente, c'è almeno un vero letterale in ogni clausola. Siate un insieme di una di queste vere letterali da ciascuna clausola. | S | = k e non ci sono due nodi in s collegati da un bordo.

Non capisco perché funzioni. Voglio dire, $ k $ è risolto a questo punto (dall'input) quindi se $ k = 3 $ posso prendere $ s = {x_1, x_3, x_4 } $. Se $ k = 2 $ posso prendere $ s = {x_2, x_4 } $ ma se $ k = 1 $ non posso.

Potresti spiegarmi perché funziona o se non capisco nulla correttamente? Grazie.