Problema 2SAT usando il grafico delle implicazioni

Question

Stavo facendo una domanda di pratica. Come puoi vedere di seguito c'è un grafico di implicazioni. Per verificare se il problema è soddisfacente, ho verificato se ci fossero "cattivi loop". Per fare ciò, per ogni letterale/variabile nella formula booleana, vedo se esiste un percorso da x --->-x e da -x ----> x se esistono entrambi, esiste un "ciclo cattivo" e Pertanto il problema non è soddisfacente. L'ho fatto e ho visto che non c'erano tali loop e quindi sono giunto alla conclusione che il problema del 2sat era soddisfacente. Vedi sotto:

Mi sono reso conto che l'opzione D (il problema 2SAT è soddisfacente se A, B, C e D sono impostati su False. Sto lottando per giungere a questa conclusione guardando il grafico. La mia comprensione è che prendi tutti i percorsi nel grafico e vedi se arrivi a una contraddizione? Qualcuno può farmi capire come capire l'opzione D essere corretta.

Grazie in anticipo!

Il metodo che ho escogitato è di scrivere gli archi/bordi per ogni implicazione e lavorare all'indietro per derivare la formula booleana 2sat e vedere se funziona. Qualcuno sa un modo più veloce? :)