h3(#solutie-4). Soluţie $O(M + N)$

O a treia soluţie se bazează pe relaţia de implicaţie. Aceasta are următoarea tabelă de adevăr:

O a treia soluţie se bazează pe relaţia de implicaţie. Relaţia <tex> \rightarrow </tex> are următoarea tabelă de adevăr:

table{width: 90px; text-align: center}. | <tex> A </tex> | <tex> B </tex> | <tex> A \rightarrow B </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 1 </tex>  |

| <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. Astfel, nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> <tex> ... </tex> şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> <tex> ... </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. Acestea fiind zise, 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:

Fiecare clauză <tex> A \vee B </tex> poate fi scrisă ca două implicaţii <tex> (\sim A \rightarrow B) \wedge (\sim B \rightarrow A) </tex>. Realizăm un graf al implicaţiilor. Astfel, nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> <tex> ... </tex> şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> <tex> ... </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. Acestea fiind zise, 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!