| <tex> 1 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |
| <tex> 1 </tex> | <tex> 1 </tex> | <tex> 1 </tex> |

Fiecare clauză <tex> A \vee B </tex> poate fi scrisă ca două implicaţii <tex> \sim A \rightarrow B </tex> şi <tex> \sim B \rightarrow A </tex>. Realizăm un graf al implicaţiilor şi astfel nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> ... şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> ... iar muchiile acestui graf vor fi implicaţiile echivalente cu propoziţiile din expresie. Deci dacă expresia are $M$ propoziţii graful va avea $2M$ muchii.

Fiecare clauză <tex> A \vee B </tex> poate fi scrisă ca două implicaţii <tex> \sim A \rightarrow B </tex> şi <tex> \sim B \rightarrow A </tex>. Realizăm un graf al implicaţiilor şi astfel nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> ... şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> ... iar muchiile acestui graf vor fi implicaţiile echivalente cu propoziţiile din expresie. Deci, dacă expresia are $M$ propoziţii graful va avea $2M$ muchii. Astfel, expresiei <tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) </tex> îi corespunde graful:
 
p=. !2-sat?Graf.png!
 
Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru, atunci dacă literalul <tex> A </tex> este adevărat atunci şi literalul <tex> B </tex> trebuie să fie adevărat pentru ca propoziţia reprezentată de muchie să fie satisfăcută. Putem demonstra prin inducţie că dacă există un drum în graf de la literalul <tex> A </tex> la literalul <tex> B </tex>, atunci dacă <tex> A </tex> este adevărat şi <tex> B </tex> trebuie să fie adevărat. Dacă există un drum de la un literal <tex> X </tex> la <tex> \sim X </tex> atunci nu va exista soluţie pentru că nu putem seta în acelaşi timp o variabilă şi valoarea ei negată la valoarea adevărat. De aici rezultă că dacă în graful asociat expresiei există o variabilă <tex> X </tex> în aceiaşi componentă tare conexă cu <tex> X </tex> atunci instanţa problemei satisfiabilităţii nu poate fi satisfăcută. Dacă nu există o asemenea variabilă, vom vedea în continuare cum putem rezolva problema. Întâi, facem observaţia că dacă în graf există muchia <tex> A \longrightarrow B </tex> atunci există şi muchia <tex> \sim B \longrightarrow \sim A </tex>. Astfel, dacă există un drum de la <tex> A </tex> la <tex> B </tex> în graf, aplicând proprietatea menţionată pentru fiecare muchie a drumului, vom găsi un drum de la <tex> \sim B </tex> la <tex> \sim A </tex>. Evident, afirmaţia este valabilă şi reciproc: dacă există drum de la <tex> B </tex> la <tex> A </tex> atunci vom avea un drum de la nodul <tex> \sim A </tex> la <tex> \sim B </tex>. Astfel, dacă avem că <tex> A </tex> şi <tex> B </tex> sunt în aceeaşi componentă tare conexă atunci şi nodurile <tex> \sim A </tex> şi <tex> \sim B </tex> sunt în aceeaşi componentă tare conexă. Deci dacă nu există doi literali <tex> X </tex> şi <tex> \sim X </tex> în aceeaşi componentă tare conexă, putem să împărţim graful în componente tari conexe şi să împerechem componentele câte două astfel ca în fiecare pereche să apară o componentă <tex> U </tex> cu nişte literali şi altă componentă <tex> \sim U </tex> cu aceiaşi literali negaţi. Pentru a găsi o soluţie vom determina mai întâi componentele tari conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi acciclic. Alegem un nod <tex> u </tex> în care nu intră nicio muchie (un asemenea nod trebuie să existe pentru a nu exista cicluri), din considerente de simetrie, din nodul lui pereche <tex> \sim u </tex> nu va ieşi nicio muchie. Literalilor componentei <tex> U </tex> putem să le dăm valoarea de adevăr <tex> 0 </tex>, iar literalilor din componenta pereche <tex> \sim U </tex>  putem să le dăm valoarea de adevăr <tex> 1 </tex>. Această alegere nu impune restricţii asupra celorlalţi literali şi elimină câteva variabile din problemă. Repetarea recursivă a acestui pas pe graful rămas va duce la rezolvarea problemei. Determinarea componentelor tari conexe se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta secţiunea $23.5$ a [1]. Iar eliminarea  nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind de exemplu o sortare topologică.
 
Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tari conexe sunt următoarele: <tex> \{A\} </tex>, <tex> \{\sim A\} </tex>, <tex> \{B, C, \sim D\} </tex>, <tex> \{\sim B, \sim C, D\} </tex>. În nodul asociat componentei <tex> \{A\} </tex> nu intră nici o muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar în nodul asociat componentei <tex> \{\sim B, \sim C, D\} </tex> nu intră nicio muchie, deci putem să îi atribuim lui <tex> B </tex> valoarea <tex> 1 </tex>, lui <tex> C </tex> valoarea <tex> 0 </tex> şi lui <tex> D </tex> valoarea <tex> 1 </tex>. Această atribuire este satisfiabilă după cum vedem în continuare:
 
<tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) </tex> <tex> = (\sim 0 \vee \sim 1) \wedge (1 \vee \sim 1) \wedge (1 \vee 1) \wedge (\sim 1 \vee \sim 0) \wedge (1 \vee 0) </tex> <tex> = 1 \wedge 1 \wedge 1 \wedge 1 \wedge 1 = 1 </tex>
 
h2. Aplicaţii
 

Astfel, expresiei <tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) </tex> îi corespunde graful:
p=. !2-sat?Graf.jpg!