Problema satisfiabilităţii formulelor logice de ordinul doi

Problema 2-satisfiabilității

h1. Problema satisfiabilităţii formulelor logice de ordinul doi

h1. Problema 2-satisfiabilităţii
 
== include(page="template/implica-te/scrie-articole" user_id="marius") ==

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(toc){width: 37em}*{text-align:center} *Conţinut:*

(toc){width: 30em}*{text-align:center} *Conţinut:*

* {'Introducere':2-sat#introducere}
* {'Forme normale ale formulelor logice':2-sat#forme-normale}
* {'SAT, 3-SAT, 2-SAT':2-sat#overview-sat}
* {'Soluţii pentru 2-SAT':2-sat#solutii-2-sat}

** {'Soluţie $O(M * 2^N^)$':2-sat#solutie1}
** {'Soluţie $O(N * M)$':2-sat#solutie2}
** {'Soluţie $O(N^2^)$':2-sat#solutie3}
** {'Soluţie $O(M + N)$':2-sat#solutie4}

** {'Soluţie $O(M * 2^N^)$':2-sat#solutie-1}
** {'Soluţie $O(N * M)$':2-sat#solutie-2}
** {'Soluţie $O(N^2^ * M)$':2-sat#solutie-3}
** {'Soluţie $O(M + N)$':2-sat#solutie-4}

* {'Aplicaţii':2-sat#aplicatii}

** {'Party (preOni 2003/2004)':2-sat#party}

** {'Party (preONI 2003/2004)':2-sat#party}

** {'Cigraf':2-sat#cigraf}

** {'Peace Commission (Polish Olympiad in Informatics, 2001)':2-sat#peace-commission}
** {'Excursion (Baltic Olympiad in Informatics, 2001)':2-sat#excursion}

** {'Orpath (Olimpiadă Rusia)':2-sat#orpath}
** {'Aladdin (Bursele Agora 2005/2006, Runda 1)':2-sat#aladdin}

* {'Probleme propuse':2-sat#probleme}
* {'Bibliografie':2-sat#bibliografie}

h2(#introducere). Introducere

Problema satisfiabiltăiţii, notată prescurtat cu $SAT$, cere determinarea existenţei pentru o formulă booleană <tex> \phi </tex> a unei artibuiri satisfiabile. O formulă booleană <tex> \phi </tex> este compusă din $variabile$ logice <tex> (x_{1}, x_{2}, ...) </tex>, $operatori$ logici ( <tex> \wedge </tex> şi,  <tex> \vee </tex> sau, <tex> \sim </tex> non, <tex> \rightarrow </tex> implicaţie şi <tex> \leftrightarrow </tex> echivalenţă), şi $paranteze$. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor dă ca rezultat valoarea de adevăr $adevărat$. De acum încolo vom folosi pentru simplitate valorile <tex> 1 </tex> şi <tex> 0 </tex> în loc de $adevărat$ şi $fals$.

Problema satisfiabilităţii, notată prescurtat cu $SAT$, cere determinarea existenţei pentru o formulă booleană <tex> \phi </tex> a unei atribuiri satisfiabile. O formulă booleană <tex> \phi </tex> este compusă din $variabile$ logice <tex> (x_{1}, x_{2}, ...) </tex>, $operatori$ logici ( <tex> \wedge </tex> şi,  <tex> \vee </tex> sau, <tex> \sim </tex> non, <tex> \rightarrow </tex> implicaţie, <tex> \leftrightarrow </tex> echivalenţă), şi $paranteze$. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor dă ca rezultat valoarea de adevăr $adevărat$. De acum încolo vom folosi pentru simplitate valorile <tex> 1 </tex> şi <tex> 0 </tex> în loc de $adevărat$ şi $fals$.

Un exemplu de formulă ar fi <tex> \phi = ((x_{1} \rightarrow x_{2}) \vee \sim((\sim x_{1} \leftrightarrow x_{3}) \vee x_{4})) \wedge \sim x_{2} </tex>. Aceasta are atribuirea satisfiabilă <tex> \langle x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1 \rangle </tex> pentru că <tex> \phi = ((0 \rightarrow 0) \vee \sim((\sim 0 \leftrightarrow 1) \vee 1)) \wedge \sim 0 = (1 \vee \sim (1 \vee 1)) \wedge 1 = (1 \vee 0) \wedge 1 = 1</tex>.

Orice formulă booleană poate fi transformată în două forme:

* $Forma normal conjunctivă$ în care expresia este exprimată ca o conjuncţie de propoziţii, iar fiecare propoziţie este formată din o disjuncţie de $literali$. Un $literal$ este o variabilă care poate fi sau nu negată. Un exemplu de expresie în forma normal conjunctivă ar fi: <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) \wedge (x_{3} \vee x_{2} \vee x_{4}) \wedge (\sim x_{1} \vee \sim x_{3} \vee \sim x_{4}) </tex> care are pe <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) </tex> ca primă propoziţie cu literalii <tex> x_{1} </tex>, <tex> \sim x_{1} </tex>, <tex> \sim x_{2} </tex>.

* $Forma normal conjunctivă$ în care expresia este exprimată ca o conjuncţie de propoziţii, iar fiecare propoziţie este formată dintr-o disjuncţie de $literali$. Un $literal$ este o variabilă care poate fi sau nu negată. Un exemplu de expresie în forma normal conjunctivă ar fi: <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) \wedge (x_{3} \vee x_{2} \vee x_{4}) \wedge (\sim x_{1} \vee \sim x_{3} \vee \sim x_{4}) </tex> care are pe <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) </tex> ca primă propoziţie cu literalii <tex> x_{1} </tex>, <tex> \sim x_{1} </tex>, <tex> \sim x_{2} </tex>.

* $Forma normal disjunctivă$ este formată ca o disjuncţie de propoziţii, fiecare dintre aceste propoziţii fiind o conjuncţie de literali. Un exemplu de o asemenea formulă ar fi următoarea: <tex> (x_{1} \wedge x_{2} \wedge x_{3}) \vee (x_{1} \wedge \sim x_{2} \wedge x_{3}) \vee (x_{1} \wedge \sim x_{2} \wedge \sim x_{3}) \vee (\sim x_{1} \wedge x_{2} \wedge \sim x_{2}) </tex>.
h2(#overview-sat). SAT, 3-SAT, 2-SAT

Problema $SAT$ este $NP-completă$. Defapt, este prima problemă $NP-completă$ găsită. Stephen Cook a demonstrat $NP-completitudinea$ ei în 1971. Pe vremea aceea nu se ştia nici măcar că problemele $NP-complete$ există. Această problemă rămâne $NP-completă$ chiar dacă restricţionăm expresiile la unele care în forma normal conjunctivă au doar trei literali. Problema satisfiabilităţii pentru asemenea expresii se numeşte $3SAT$, şi multe probleme pot fi demonstrate a fi $NP-complete$ prin reducerea la această problemă. Din fericire, problema $2SAT$, adică cea pentru care în fiecare propoziţie există doar $2$ literali se poate rezolva eficient. Restul articolului va prezenta trei metode de rezolvare a problemei $2SAT$ şi câteva aplicaţii ale acesteia la concursuri de programare.

Problema $SAT$ este $NP-completă$. De fapt, este prima problemă $NP-completă$ găsită. Stephen Cook a demonstrat $NP-completitudinea$ ei în 1971. Pe vremea aceea nu se ştia nici măcar că problemele $NP-complete$ există. Această problemă rămâne $NP-completă$ chiar dacă restricţionăm expresiile la unele care în forma normal conjunctivă au doar trei literali. Problema satisfiabilităţii pentru asemenea expresii se numeşte $3-SAT$, şi multe probleme pot fi demonstrate a fi $NP-complete$ prin reducerea lui $3-SAT$ la problemele respective în timp polinomial. Din fericire, problema $2-SAT$, adică cea pentru care în fiecare propoziţie există doar $2$ literali, se poate rezolva eficient. Restul articolului va prezenta trei metode de rezolvare a problemei $2-SAT$ şi câteva aplicaţii ale acesteia din concursuri de programare.

h2(#solutii-2-sat). Soluţii pentru 2-SAT

Un exemplu de problemă $2SAT$ ar fi satisfiabilitatea formulei <tex> (x_{1} \vee \sim x_{2}) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee x_{2}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. Această formulă este satisfăcută de valorile <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 \rangle </tex>. Pentru a satisface întreaga expresie trebuie ca în fiecare propoziţie cel puţin unul din cei doi literali să aibă valoarea de adevăr <tex> 1 </tex>.

Un exemplu de problemă $2-SAT$ ar fi satisfiabilitatea formulei <tex> (x_{1} \vee \sim x_{2}) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee x_{2}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. Această formulă este satisfăcută de valorile <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 \rangle </tex>. Pentru a satisface întreaga expresie trebuie ca în fiecare propoziţie cel puţin unul din cei doi literali să aibă valoarea de adevăr <tex> 1 </tex>.

h3(#solutie1). Soluţie $O(M * 2^N^)$

h3(#solutie-1). Soluţie $O(M * 2^N^)$

O primă metodă de rezolvare ar fi să încercăm toate cele $2^4^$ posibilităţi de atribuire posibilă, dar această metodă are ordinul de complexitate $O(M * 2^N^)$ şi este eficientă doar pentru instanţe mici ale problemei.

O primă metodă de rezolvare ar fi să încercăm toate cele $2^N^$ posibilităţi de atribuire posibilă, dar această metodă are ordinul de complexitate $O(M * 2^N^)$ şi este eficientă doar pentru instanţe mici ale problemei.

h3(#solutie2). Soluţie $O(N * M)$

h3(#solutie-2). Soluţie $O(N * M)$

Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema este mai grea decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile $p$ şi $q$, apoi una dintre ele, de exemplu $p$. Dacă literalul în care apare $p$ este negat atunci îi atribuim valoarea $1$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr atunci valoarea lui $q$ este fixată. Fixând şi valoarea lui $q$, probabil şi alte propoziţii ce conţin literalul $q$ vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări. După ce toate schimbările forţate au fost făcute propoziţiile rezultate vor fi de următoarele tipuri: <tex> a \vee b </tex>, <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex>. Propoziţii de tip <tex> 0 \vee b </tex> nu pot apărea pentru că toate schimbările forţate au fost deja propagate. Dacă apare o propoziţie <tex> 0 \vee 0 </tex> atunci alegerea făcută pentru valoarea lui $p$ este greşită. Vom încerca şi alegerea opusă. Dacă ambele duc la o propoziţie de tip <tex> 0 \vee 0 </tex> atunci expresia nu poate fi satisfăcută. Propoziţiile de forma <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex> pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminate câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate $O(N * M)$, pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată.

Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema sunt mai grele decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile $p$ şi $q$, apoi una dintre ele, de exemplu $p$. Îi atribuim literalului în care apare $p$ valoarea $0$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr, atunci valoarea lui $q$ trebuie fixată. Fixând şi valoarea lui $q$, probabil şi alte propoziţii ce conţin literalul $q$ vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări. După ce toate schimbările forţate au fost făcute, propoziţiile rezultate vor fi de următoarele tipuri: <tex> a \vee b </tex>, <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex>. Propoziţii de tip <tex> 0 \vee b </tex> nu pot apărea pentru că toate schimbările forţate au fost deja propagate. Dacă apare o propoziţie <tex> 0 \vee 0 </tex> atunci alegerea făcută pentru valoarea lui $p$ este greşită. Vom încerca şi alegerea opusă pentru $p$. Dacă ambele duc la o propoziţie de tip <tex> 0 \vee 0 </tex> atunci expresia nu poate fi satisfăcută. Propoziţiile de forma <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex> pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminat câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate $O(N * M)$, pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată.

Să vedem cum funcţionează algoritmul pentru expresia: <tex> (x_{1} \vee \sim x_{2}) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee x_{2}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. Considerăm propoziţia <tex> (x_{1} \vee \sim x_{2}) </tex> şi <tex> \langle x_{2} = 1 \rangle </tex>. Astfel, vom obţine mai departe <tex> (x_{1} \vee 0) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee 1) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. În propoziţia <tex> (x_{1} \vee 0) </tex> <tex> x_{1} </tex> trebuie să fie egal cu <tex> 1 </tex>. Acum, expresia devine: <tex> (0 \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee 0) </tex>. Din propoziţia <tex> (0 \vee \sim x_{3}) </tex> obţinem <tex> \langle x_{3} = 0 \rangle </tex>, iar din <tex> (x_{4} \vee 0) </tex> obţinem <tex> \langle x_{4} = 1 \rangle </tex>. Deci, atribuirea satisfiabilă este <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 \rangle </tex>.

Să vedem cum funcţionează algoritmul pentru expresia: <tex> (x_{1} \vee \sim x_{2}) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee x_{2}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. Considerăm propoziţia <tex> (x_{1} \vee \sim x_{2}) </tex> şi <tex> \langle x_{2} = 1 \rangle </tex>. Astfel, vom obţine mai departe <tex> (x_{1} \vee 0) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee 1) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. În propoziţia <tex> (x_{1} \vee 0) </tex>, <tex> x_{1} </tex> trebuie să fie egal cu <tex> 1 </tex>. Acum, expresia devine: <tex> (0\ \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee 0) </tex>. Din propoziţia <tex> (0\ \vee \sim x_{3}) </tex> obţinem <tex> \langle x_{3} = 0 \rangle </tex>, iar din <tex> (x_{4} \vee 0) </tex> obţinem <tex> \langle x_{4} = 1 \rangle </tex>. Deci, atribuirea satisfiabilă este <tex> \langle x_{1} = 1, x_{2} = 1, x_{3} = 0, x_{4} = 1 \rangle </tex>.

h3(#solutie3). Soluţie $O(N^2^)$

h3(#solutie-3). Soluţie $O(N^2^ * M)$

O altă soluţie elegantă se bazează pe o metodă randomizată:
== code(cpp) |
atribuim valori booleene arbitrare variabilelor;

cât timp expresia nu este satisfăcută execută

cât timp expresia nu este satisfăcută, execută

    găsim o propoziţie cu valoarea de adevăr 0;
    schimbăm valoarea de adevăr a oricăreia dintre cele două variabile prezente în propoziţie;

sfcâttimp

sfârşit cât timp

==
Linia $4$ va face ca acea propoziţie să aibă noua valoare de adevăr <tex> 1 </tex>.

De ce ar merge acest algoritm? Să presupunem că există o soluţie a problemei, o notăm cu <tex> S </tex>, iar cu <tex> X </tex> notăm şirul valorilor curente ale variabilelor. Ne uităm la fiecare pas al algoritmului la numărul de variabile care au valori diferite în soluţie faţă de cele din <tex> X </tex> (acest număr de diferenţe între elementele de acelaşi index pentru două şiruri se mai numeşte şi $distanţă Hamming$ între şiruri). Fie această valoare la pasul current $K$. Noi am vrea să avem $K = 0$. Cum va evolua $K$ pe parcursul algoritmului? La un moment dat noi schimbăm valoarea unei variabile luate aleator dintr-o propoziţie nesatisfăcută. Pentru că în <tex> S </tex> propoziţia este satisfăcută, înseamnă că cel puţin una dintre cele două variabile ale propoziţiei are valori diferite în <tex> X </tex> faţă de <tex> S </tex>. Astfel, operaţia făcută de noi are probabilitate de cel puţin $0.5$ să ne aducă mai aproape de soluţie. Vom nota cu <tex> T(i) </tex> numărul probabil de paşi în care un şir <tex> X </tex> aflat la $distanţa Hamming$ egală cu $i$ faţă de <tex> S </tex>, va fi transformat în <tex> S </tex>. Evident:

De ce ar merge acest algoritm? Să presupunem că există o soluţie a problemei, o notăm cu <tex> S </tex>, iar cu <tex> X </tex> notăm şirul valorilor curente ale variabilelor. Ne uităm la fiecare pas al algoritmului la numărul de variabile care au valori diferite în soluţie faţă de cele din <tex> X </tex> (acest număr de diferenţe între elementele de acelaşi index pentru două şiruri se mai numeşte şi 'distanţă Hamming':http://en.wikipedia.org/wiki/Hamming_distance între şiruri). Fie această valoare la pasul current $K$. Noi am vrea să avem $K = 0$. Cum va evolua $K$ pe parcursul algoritmului? La un moment dat noi schimbăm valoarea unei variabile luate aleator dintr-o propoziţie nesatisfăcută. Pentru că în <tex> S </tex> propoziţia este satisfăcută, înseamnă că cel puţin una dintre cele două variabile ale propoziţiei are valori diferite în <tex> X </tex> faţă de <tex> S </tex>. Astfel, operaţia făcută de noi are probabilitate de cel puţin $0.5$ să ne aducă mai aproape de soluţie. Vom nota cu <tex> T(i) </tex> numărul probabil de paşi în care un şir <tex> X </tex> aflat la distanţa Hamming egală cu $i$ faţă de <tex> S </tex>, va fi transformat în <tex> S </tex>. Evident:

<tex> T(0) = 0 </tex>.

<tex> T(0) = 0 </tex>

<tex> T(i) \le (T(i + 1) + T(i - 1)) / 2 + 1 </tex>

<tex> T(i) \le \dfrac {T(i + 1) + T(i - 1)}{2} + 1 </tex> pentru $0 < i < N$ ({$N$} e numărul de variabile booleene ale expresiei)

Se pune semnul de inegalitate pentru că ambele variabile pot avea valori diferite faţă de cele din soluţie, deci schimbarea valorii oricăreia ar putea să ne aducă mai aproape de soluţie.

Pentru că dacă toate variabilele diferă de soluţie, orice schimbare ne aduce mai aproape de soluţie:

Dacă toate variabilele diferă de soluţie, orice schimbare ne aduce mai aproape de aceasta:

<tex> T(N) = T(N - 1) + 1 </tex>
Ne interesează numai limitele superioare, deci folosim doar egalităţi în loc de inegalităţi:

<tex> X(0) = 0, X(i) = (X(i + 1) + X(i - 1))/2 + 1, X(N) = X(N - 1) + 1 </tex>

<tex> X(0) = 0 </tex>, <tex> X(i) = \dfrac {X(i + 1) + X(i - 1)}{2} + 1 </tex>, <tex> X(N) = X(N - 1) + 1 </tex>

Dacă adunăm toate ecuaţiile obţinem:

<tex> X(0) + X(1) + ... + X(N) </tex> <tex> = (X(0) + X(1) + 2X(1) + ... + 2X(N - 2) + X(N - 1) + X(N))/2 + N + X(N - 1) </tex>

<tex> X(0) + X(1) + ... + X(N) = </tex> <tex> \dfrac {X(0) + X(1) + 2X(2) + ... + 2X(N - 2) + X(N - 1) + X(N)}{2} + X(N) + N - 1 </tex>

De aici avem că <tex> (X(1) + X(N) - X(N - 1)) / 2 = N </tex>, din <tex> X(N) = X(N - 1) + 1 </tex> avem <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4n - 4 ... X(i) = 2iN - i^2^ </tex> de unde, când <tex> i = N </tex> avem că <tex> X(N) = N^2^ </tex>.

De aici avem că <tex> \dfrac {X(1) + X(N - 1) - X(N)}{2} = N - 1 </tex>, iar din <tex> X(N) = X(N - 1) + 1 </tex> rezultă că <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4N - 4 </tex> <tex> ... </tex> <tex> X(i) = 2iN - i^2 </tex>, de unde, când <tex> i = N </tex>, avem că <tex> X(N) = N^2 </tex>.

Astfel, numărul mediu de paşi ai algoritmului este $N^2^$ iar dacă aplicăm algoritmul în mod aleator de mai multe ori avem o probabilitate foarte mare să ajungem la rezultat.

Astfel, numărul mediu de paşi ai algoritmului este pătratic în numărul $N$ de variabile. Lăsând algoritmul să ruleze de 2-3 ori mai mulţi paşi decât numărul mediu, avem o probabilitate foarte mare să ajungem la rezultat.

h3(#solutie4). Soluţie $O(M + N)$

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

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:

O a treia soluţie se bazează pe relaţia de implicaţie. Aceasta 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> |

Relaţia de implicaţie are semnificaţia dacă <tex> A </tex> este adevărat atunci şi <tex> B </tex> este adevărat. Scriem tabelul expresiei <tex> \sim A \vee B </tex> şi observăm că acesta este egal cu cel al relaţiei de implicaţie.

Relaţia de implicaţie are următoarea semnificaţie: dacă <tex> A </tex> este adevărat atunci şi <tex> B </tex> este adevărat. Scriem tabela expresiei <tex> \sim A \vee B </tex> şi observăm că aceasta este egală cu cea a relaţiei de implicaţie.

table{width: 90px; text-align: center}. | <tex> A </tex> | <tex> B </tex> | <tex> \sim A \vee 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 ş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:

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:

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 o sortare topologică.

Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru şi 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>, precum şi un drum invers, 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 aceeaşi componentă tare conexă cu <tex> \sim 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 tare 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 tare conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi aciclic. 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 tare conexe':problema/ctc se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta 'secţiunea $23.5$':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm din {'[1]':2-sat#bibliografie}. Iar eliminarea nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind o 'sortare topologică':problema/sortaret.

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:

Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tare 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ă nicio muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar după eliminarea lui <tex> \{A\} </tex> şi <tex> \{\sim A\} </tex>î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> 1 </tex> şi lui <tex> D </tex> valoarea <tex> 0 </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>

<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(#aplicatii). Aplicaţii

Restul articolului va prezenta aplicaţii ale problemei $2-SAT$ la concursurile de programare.

Restul articolului va prezenta aplicaţii ale problemei $2-SAT$ din concursurile de programare.

h2(#party). 'Party':problema/party (preOni 2003/2004)

h2(#party). 'Party':problema/party (preONI 2003/2004)

bq. George vrea să îşi organizeze majoratul, şi vrea ca petrecerea să fie de neuitat, mâncarea, băutura, locaţia şi sonorizarea sunt deja asigurate, mai rămâne problema chemării prietenilor. El şi cu prietenul lui cel mai bun Lucian au preferinte diferite şi pentru a nu se certa au pus la punct o listă de cerinţe care vor trebui să fie îndeplinite astfel încât cheful să se desfăşoare în cele mai bune condiţii! Pentru uşurinţă,  prietenii lui George vor fi indentificaţi prin numere întregi de la $1$ la $N (1 ≤ N ≤ 100)$ şi cerinţele în număr de $M  (1 ≤ M ≤ 1.000)$ vor fi de tipurile $0$, $1$, $2$ sau $3$. O cerinţă de genul $x y 0$ are semnificaţia că $x$ sau $y$ trebuie să participe la petrecere; $x y 1$ are semnificaţia că dacă $x$ participă nu există nici o restricţie pentru $y$, dar dacă $x$ nu participă atunci nici $y$ nu participa; $x y 2$ are semnificaţia simetrică cu cerinţa $1$; iar cerinţa $x y 3$ are semnificaţia că cel puţin unul dintre $x$ si $y$ nu participă la petrecere. Scrieţi un program care să-i ajute pe cei doi să determine care persoane vor fi invitate la petrecere. Se garantează că va fi posibilă întotdeauna organizarea unei petreceri!

bq. George vrea să îşi organizeze majoratul şi îşi doreşte ca petrecerea să fie de neuitat. Mâncarea, băutura, locaţia şi sonorizarea sunt deja asigurate, mai rămâne problema chemării prietenilor. El şi cu prietenul lui cel mai bun, Lucian, au preferinţe diferite şi pentru a nu se certa au pus la punct o listă de cerinţe care vor trebui să fie îndeplinite astfel încât cheful să se desfăşoare în cele mai bune condiţii! Pentru uşurinţă, prietenii lui George vor fi identificaţi prin numere întregi de la $1$ la $N$ ({$1 ≤ N ≤ 100$}) şi cerinţele în număr de $M$ ({$1 ≤ M ≤ 1.000$}) vor fi de tipurile 0, 1, 2 sau 3. O cerinţă de genul <tex> x \ y </tex> 0 are semnificaţia că <tex> x </tex> sau <tex> y </tex> trebuie să participe la petrecere; <tex> x \ y </tex> 1 are semnificaţia că dacă <tex> x </tex> participă nu există nicio restricţie pentru <tex> y </tex>, dar dacă <tex> x </tex> nu participă atunci nici <tex> y </tex> nu participa; <tex> x \ y </tex> 2 are semnificaţia simetrică cu cerinţa 1; iar cerinţa <tex> x \ y </tex> 3 are semnificaţia că cel puţin unul dintre <tex> x </tex> şi <tex> y </tex> nu participă la petrecere. Scrieţi un program care să-i ajute pe cei doi să determine care persoane vor fi invitate la petrecere. Se garantează că va fi posibilă întotdeauna organizarea unei petreceri!

h3. Soluţie

Această problemă este inspirită din o problemă de la $CEOI 2002$ şi este evident că ne cere să determinăm o atribuire satisfiabilă pentru o formulă logică formată ca conjuncţie între cerinţele care se transformă astfel:

Această problemă este inspirată dintr-o problemă de la $CEOI 2002$ şi este evident că ne cere să determinăm o atribuire satisfiabilă pentru o formulă logică formată ca conjuncţie între cerinţele care se transformă astfel:

* cerinţa de tip $0$ corespunde propoziţiei <tex> x \vee y </tex>;
* cerinţa de tip $1$ corespunde propoziţiei <tex> x \vee \sim y </tex>;
* cerinţa de tip $2$ corespunde propoziţiei <tex> \sim x \vee y </tex>;
* cerinţa de tip $3$ corespunde propoziţiei <tex> \sim x \vee \sim y </tex>.

* _cerinţa de tip 0_ corespunde propoziţiei <tex> x \vee y </tex>;
* _cerinţa de tip 1_ corespunde propoziţiei <tex> x \vee \sim y </tex>;
* _cerinţa de tip 2_ corespunde propoziţiei <tex> \sim x \vee y </tex>;
* _cerinţa de tip 3_ corespunde propoziţiei <tex> \sim x \vee \sim y </tex>.

Una din primele două rezolvări ar fi putut soluţiona această problemă, dar problema de la $CEOI$ avea limite mai mari şi pentru rezolvarea ei ar fi trebuit un algoritm de complexitate $O(N + M)$.

_Autor: Mugurel Ionuţ Andreica_

bq. Se dă un graf neorientat cu $N (1 <= N <= 1000)$ noduri şi $M (0 <= M <= N*(N-1)/2)$ muchii. Se doreşte împărţirea nodurilor acestui graf în $2$ mulţimi, <tex> C </tex> şi <tex> I </tex>, având următoarele proprietăţi: fiecare nod face parte din exact una din cele $2$ mulţimi, există muchie între oricare $2$ noduri din mulţimea <tex> C </tex>, nu există nicio muchie între $2$ noduri din mulţimea <tex> I </tex>. Este posibil ca una dintre cele $2$ mulţimi să fie vidă. Soluţia nu este neaparat unică. Numele celor două mulţimi provin de la $clică$ şi $mulţime independentă$. De exemplu, pentru graful de $6$ noduri ce are muchiile <tex> \{\{1, 4\}, \{4, 6\}, \{6, 1\}, \{2, 4\}, \{2, 6\}, \{3, 4\}, \{1, 3\}\} </tex> o împărţire posibilă ar fi <tex> C = \{1, 4, 6\} </tex>, <tex> I = \{2, 3, 5\} </tex>.
 
h3. Soluţie
 
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.
Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.
 
h2(#peace-commission). Peace Commission (Polish Olympiad in Informatics, 2001)
 
bq. Comisia Publică a Păcii trebuie să fie compusă în parlamentul Republicii Democrate a ţării Byteland după regulile impuse de Legea Foarte Importantă. Din păcate unul dintre obstacole este acela că unii deputaţi nu se înţeleg cu ceilalţi. Comisia trebuie realizată astfel ca următoarele condiţii să fie îndeplinite: fiecare partid trebuie să aibă exact un reprezentant în comisie; dacă doi deputaţi nu se înţeleg, ei nu pot fi ambii membrii ai comisiei. Fiecare partid are exact doi deputaţi în parlament. Toţi număraţi de la $1$ până la $2n (1 <= n <= 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 <= m <= 20 000)$ perechi de deputaţi <tex> (a, b) </tex> care nu se înţeleg. Se cere realizarea unei comisii dacă acest lucru este posibil. Un exemplu ar fi pentru trei partide şi perechile <tex> (1, 3) </tex> şi <tex> (2, 4) </tex> care nu se înţeleg comisia alcătuită din membrii <tex> \{1, 4, 5\} </tex>.
 
h3. Soluţie
 
Fiecărui partid îi vom asocia o variabilă; variabila va lua valoarea <tex> 1 </tex> dacă membrul $2i - 1$ al partidului va aparţine comisiei şi valoarea <tex> 0 </tex> dacă membrul $2i$ va aparţine comisiei. Pentru ca din partidul $x$ să existe exact un membru în expresie introducem  <tex> A_{x} \wedge \sim A_{x} </tex>.
Putem exprima că doi membrii ai parlamentului $(2i, 2j)$ nu se înţeleg prin expresia logică <tex> \sim A_{i} \vee \sim A_{j} </tex>. Astfel nu pot ambele variabile <tex> A_{i} </tex> şi <tex> A_{j} </tex> să aibă în acelaşi timp valoarea <tex> 1 </tex> adică $2i$ şi $2j$ nu pot face parte în acelaşi timp din comisie. Dacă cei doi membrii sunt $(2i - 1, 2j - 1)$ atunci îi putem codifica prin expresia <tex> A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> şi <tex> A_{j} </tex> nu pot avea în acelaşi timp valoarea <tex> 0 </tex>, iar dacă membrii sunt $(2i , 2j - 1)$ se poate scrie ca <tex> \sim A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> nu poate avea valoarea <tex> 1 </tex> când <tex> A_{j} </tex> are valoarea <tex> 0 </tex>.
Exemplu din problemă poate fi scris ca expresia logică în modul următor: <tex> A_{1} \wedge \sim A_{1} \wedge A_{2} \wedge \sim A_{2} \wedge A_{3} \wedge \sim A_{3} \wedge (A_{1} \vee A_{2}) \wedge (\sim A_{1} \vee \sim A_{2}) </tex>.
Din nou vom putea folosi cel de al treilea algoritm explicat pentru a obţine o rezolvare de complexitate $O(N + M)$.
 
h2(#excursion). Excursion (Baltic Olympiad in Informatics, 2001)
 
bq. Un grup de turişti are ocazia să viziteze mai multe oraşe. Fiecare turist spune două dorinţe ale sale despre ce oraş ar vrea sau nu ar vrea să viziteze. O dorinţă a turistului  va spune despre exact un oraş dacă vrea sau nu vrea să îl viziteze. Este posibil ca ambele dorinţe ale unui turist să exprime acelaşi lucru sau să exprime lucruri opuse (de exemplu „Vreau să vizitez oraşul A!” şi „Nu vreau să vizitez oraşul A!”). Va trebui să determinaţi după citirea cerinţelor celor $n$ turişti despre $m$ oraşe dacă există o mulţime a oraşelor pentru care cel puţin o dorinţă a fiecărui turist este îndeplinită $(1 <= n <= 20 000, 1 <= m <= 8 000)$. De exemplu, să presupunem că avem $3$ turişti, $4$ oraşe şi primul turist are dorinţele de a vizita oraşul întâi şi de a nu vizita oraşul doi, al doilea turist are dorinţele de a vizita oraşul doi şi de a vizita oraşul patru, iar al treilea turist are dorinţele de a vizita oraşul trei şi de a vizita oraşul unu. O soluţie pentru acest exemplu ar fi vizitarea tuturor oraşelor.

bq. Se dă un graf neorientat cu $N$ ({$1 &le; N &le; 1000$}) noduri şi $M$ ({$0 &le; M &le; N*(N-1)/2$}) muchii. Se doreşte împărţirea nodurilor acestui graf în $2$ mulţimi, <tex> C </tex> şi <tex> I </tex>, având următoarele proprietăţi: fiecare nod face parte din exact una din cele $2$ mulţimi, există muchie între oricare $2$ noduri din mulţimea <tex> C </tex>, nu există nicio muchie între $2$ noduri din mulţimea <tex> I </tex>. Este posibil ca una dintre cele $2$ mulţimi să fie vidă. Soluţia nu este neapărat unică. Numele celor două mulţimi provin de la $clică$ şi $mulţime independentă$. De exemplu, pentru graful de $6$ noduri ce are muchiile <tex> \{\{1, 4\}, \{4, 6\}, \{6, 1\}, \{2, 4\}, \{2, 6\}, \{3, 4\}, \{1, 3\}\} </tex> o împărţire posibilă ar fi <tex> C = \{1, 4, 6\} </tex>, <tex> I = \{2, 3, 5\} </tex>.

h3. Soluţie

Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.

Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>. Transformăm această problemă într-o instanţă de $2-SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dându-i lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa la mulţimea <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.

h2(#orpath). Orpath (Olimpiadă Rusia)

bq. Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 <= N, K <= 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.

bq. Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 ≤ N, K ≤ 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.

h3. Soluţie

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T … t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$ iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lot $[t1 + k*T1 .. t2 + k*T1]$ se intersectează cu intervalele $[tt1 + p*T2 … tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea adevărat doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T ... t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$, iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele $[t1 + k*T1 ... t2 + k*T1]$ ale primului să se intersecteze cu intervalele $[tt1 + p*T2 ... tt2 + p*T2]$ ale celui de-al doilea. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea $adevărat$ doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

h2(#aladdin). 'Aladdin':problema/aladdin (Bursele Agora 2005/2006, Runda 1)

bq. Aladdin, aşa cum ştiaţi, este un mare magnat în afacerea de comercializare a covoarelor magice. Acesta doreşte să o cucerească pe prinţesa Iasmina, iar aceasta, pentru a-i testa inteligenţa îl roagă să îi facă un covor dreptunghiular împărţit în pătrăţele, asemănator unei table de şah cu $N$ linii şi $M$ coloane $(1 <= N, M <= 1000)$. Fiecare pătrăţel de pe covor trebuie colorat cu alb sau cu negru. Pentru fiecare pătrat care conţine $4$ pătrăţele Iasmina pune condiţia să aibă un număr fixat de pătrăţele colorate cu negru. Ajutaţi-l pe Aladdin să realizeze un covor care satisface condiţiile impuse de prinţesa Iasmina!

bq. Aladdin, aşa cum ştiaţi, este un mare magnat în afacerea de comercializare a covoarelor magice. Acesta doreşte să o cucerească pe prinţesa Iasmina, iar aceasta, pentru a-i testa inteligenţa îl roagă să îi facă un covor dreptunghiular împărţit în pătrăţele, asemănator unei table de şah cu $N$ linii şi $M$ coloane $(1 ≤ N, M ≤ 1000)$. Fiecare pătrăţel de pe covor trebuie colorat cu alb sau cu negru. Pentru fiecare pătrat care conţine $4$ pătrăţele Iasmina pune condiţia să aibă un număr fixat de pătrăţele colorate cu negru. Ajutaţi-l pe Aladdin să realizeze un covor care satisface condiţiile impuse de prinţesa Iasmina!

h3. Soluţie

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

Fie <tex> A </tex> o matrice soluţie a problemei noastre. Vom numerota rândurile matricii de la $0$ la $N - 1$ şi coloanele de la $0$ la $M - 1$. Matricea de intrare <tex> S </tex> reprezintă de fapt sumele din fiecare pătrat de câte $2 x 2$ elemente. Facem observaţia că dacă ştim într-un pătrat de $2 x 2$ valorile pentru trei dintre celule, atunci valoarea din a patra celulă este unic determinată pentru că ştim suma elementelor din pătrat. Vedem astfel, că dacă ştim valorile elementelor din prima linie a matricii <tex> A </tex> şi din prima coloană, restul valorilor sunt unic determinate.
Pentru a rezolva problema vom presupune <tex> A[0][0] </tex> cunoscut (de fapt, mai întâi vom rezolva problema presupunând că <tex> A[0][0] = 1 </tex>, iar dacă nu obţinem nicio soluţie vom încerca cu <tex> A[0][0] = 0 </tex>). Vom nota celulele <tex> A[0][1] </tex>, <tex> A[0][2]</tex>, … <tex> A[0][M - 1] </tex> cu <tex> x_{1} </tex>, <tex> x_{2} </tex>, … <tex> x_{M-1} </tex> iar celulele <tex> A[1][0] </tex>, <tex> A[2][0] </tex>, … <tex> A[N - 1][0] </tex> cu <tex> y_{1} </tex>, <tex> y_{2} </tex>, … <tex> y_{N-1} </tex>.

Fie <tex> A </tex> o matrice soluţie a problemei noastre. Vom numerota rândurile matricii de la $0$ la $N - 1$ şi coloanele de la $0$ la $M - 1$. Matricea de intrare <tex> S </tex> reprezintă de fapt sumele din fiecare pătrat de câte $2 x 2$ elemente. Facem observaţia că dacă ştim într-un pătrat de $2 x 2$ valorile pentru trei dintre celule, atunci valoarea din a patra celulă este unic determinată pentru că ştim suma elementelor din pătrat. Vedem astfel, că dacă ştim valorile elementelor din prima linie a matricii <tex> A </tex> şi din prima coloană, restul valorilor sunt unic determinate. Pentru a rezolva problema vom presupune <tex> A[0][0] </tex> cunoscut (de fapt, mai întâi vom rezolva problema presupunând că <tex> A[0][0] = 1 </tex>, iar dacă nu obţinem nicio soluţie vom încerca cu <tex> A[0][0] = 0 </tex>). Vom nota celulele <tex> A[0][1] </tex>, <tex> A[0][2]</tex>, <tex>...</tex>, <tex> A[0][M - 1] </tex> cu <tex> x_{1} </tex>, <tex> x_{2} </tex>, <tex>...</tex>, <tex> x_{M-1} </tex>, iar celulele <tex> A[1][0] </tex>, <tex> A[2][0] </tex>, <tex>...</tex>, <tex> A[N - 1][0] </tex> cu <tex> y_{1} </tex>, <tex> y_{2} </tex>, <tex>...</tex>, <tex> y_{N-1} </tex>.

table{width: 90px; text-align: center}.
| <tex> A[0][0] </tex> | <tex> x_{1} </tex> | <tex> x_{2} </tex> | <tex> ... </tex> | <tex> x_{M-1} </tex> |

| ... | ... | ... | ... | ... |
| <tex> y_{N-1} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |

Acum, pentru fiecare celulă putem demonstra prin inducţie că <tex> A[i][j] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>. Unde <tex> b[i][j] </tex> sunt nişte constante ce sunt calculate în funcţie de matricea primită la intrare.
Este uşor de observat că dacă:
<tex> A[i-1][j] = (-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j] </tex>,
<tex> A[i-1][j-1] = (-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1] </tex>,
<tex> A[i][j-1] = (-1)^i x_{j-1} + (-1)^{(j-1)} y_{i} + b[i][j-1] </tex>,

Acum, pentru fiecare celulă putem demonstra prin inducţie că <tex> A[i][j] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>. Unde <tex> b[i][j] </tex> sunt nişte constante ce sunt calculate în funcţie de matricea primită la intrare. Este uşor de observat că dacă:
 
<tex> A[i-1][j] = (-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j] </tex>,
<tex> A[i-1][j-1] = (-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1] </tex>,
<tex> A[i][j-1] = (-1)^i x_{j-1} + (-1)^{(j-1)} y_{i} + b[i][j-1] </tex>,
 

atunci:

<tex> A[i][j] = S[i-1][j-1] - A[i-1][j] - A[i][j-1] - A[i-1][j-1] = </tex>
<tex> = S[i-1][j-1] - ((-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j]) - </tex> <tex> ((-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1]) - ((-1)^i x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i][j-1]) = </tex>
<tex> = (-1)^i x_{j} - (-1)^j y_{i-1} + (-1)^i x_{j-1} + (-1)^j y_{i-1} - </tex> <tex> (-1)^i x_{j-1} + (-1)^j y_{i} + S[i-1][j-1] - b[i-1][j] - b[i][j-1] - b[i-1][j-1] = </tex>
<tex> = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>.

 
<tex> A[i][j] = </tex> <tex> S[i-1][j-1] - </tex> <tex> A[i-1][j] - </tex> <tex> A[i][j-1] - </tex> <tex> A[i-1][j-1] = </tex> <tex> S[i-1][j-1] - </tex> <tex> ((-1)^{(i-1)} x_{j} + </tex> <tex> (-1)^j y_{i-1} + </tex> <tex> b[i-1][j]) - </tex> <tex> ((-1)^{(i-1)} x_{j-1} + </tex> <tex> (-1)^{(j-1)} y_{i-1} + </tex> <tex> b[i-1][j-1]) - </tex> <tex> ((-1)^i x_{j-1} + </tex> <tex> (-1)^{(j-1)} y_{i-1} + </tex> <tex> b[i][j-1]) = </tex> <tex> (-1)^i x_{j} - </tex> <tex> (-1)^j y_{i-1} + </tex> <tex> (-1)^i x_{j-1} + </tex> <tex> (-1)^j y_{i-1} - </tex> <tex> (-1)^i x_{j-1} + </tex> <tex> (-1)^j y_{i} + </tex> <tex> S[i-1][j-1] - </tex> <tex> b[i-1][j] - </tex> <tex> b[i][j-1] - </tex> <tex> b[i-1][j-1] = </tex> <tex> (-1)^i x_{j} + </tex> <tex> (-1)^j y_{i} + </tex> <tex> b[i][j] </tex>.
 

De aici concluzionăm că <tex> b[i][j] = S[i-1][j-1] - b[i-1][j] - b[i][j-1] - b[i-1][j-1] \ (*)</tex>.
Avem un sistem format din inecuaţiile:
<tex> 0 \le x_{j} \le 1 </tex>
<tex> 0 \le y_{i} \le 1 </tex>

<tex> -b[i][j] \le (-1)^i xj + (-1)^j yi \le 1 - b[i][j] </tex>

<tex> -b[i][j] \le (-1)^i x_{j} + (-1)^j y_{i} \le 1 - b[i][j] </tex>
 
Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> -2 \le b[i][j] \le 3 </tex>, altfel nu avem soluţie. Dacă partea constantă minimă într-o relaţie este $2$ atunci ambele variabile au valori fixe, iar dacă este $1$ sau $0$ atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.
 
O relaţie precum <tex> 0 \le x + y \le 1 </tex> poate fi tansformată logic în <tex> \sim x \vee \sim y </tex>, astfel <tex> x </tex> şi <tex> y </tex> nu vor fi în acelaşi timp <tex> 1 </tex>, una de genul <tex> 1 \le x + y \le 2 </tex> va fi transformată în <tex> x \vee y </tex>, astfel cel puţin <tex> x </tex> sau <tex> y </tex> va fi egal cu <tex> 1 </tex>, alta de tipul <tex> 0 \le x - y \le 1 </tex> poate fi scrisă ca <tex> x \vee \sim y </tex>, una de tipul <tex> 2 \le x + y \le 3 </tex> în <tex> x \wedge y </tex>, iar una de tipul <tex> 0 \le -x -y \le 1 </tex> în <tex> \sim x \wedge \sim y </tex>, una de tipul <tex> 1 \le x - y  \le 2 </tex> în <tex> x \wedge \sim y </tex>. Astfel am redus problema la rezolvarea unei instanţe de $2-SAT$. Avem $N+M-1$ necunoscute şi @(N-1)*(M-1)@ propoziţii. Folosind {'a treia metodă de rezolvare':2-sat#solutie-3} vom obţine un algoritm de complexitate $O((M + N)^2^)$ care soluţionează problema noastră.
 
Să vedem cum merge acestă rezolvare pe exemplul din problemă:
 
Alegem <tex> A[0][0] = 1 </tex>. Necunoscutele vor fi <tex> x_{1} </tex>, <tex> x_{2} </tex>, <tex> x_{3} </tex> şi <tex> y_{1} </tex>, <tex> y_{2} </tex>, <tex> y_{3} </tex>.
 
table{width: 90px; text-align: center}.
| <tex> 1 </tex> | <tex> x_{1} </tex> | <tex> x_{2} </tex> | <tex> x_{3} </tex> |
| <tex> y_{1} </tex> | <tex> A[1][1] </tex> | <tex> A[1][2] </tex> | <tex> A[1][3] </tex> |
| <tex> y_{2} </tex> | <tex> A[2][1] </tex> | <tex> A[2][2] </tex> | <tex> A[2][3] </tex> |
| <tex> y_{3} </tex> | <tex> A[3][1] </tex> | <tex> A[3][2] </tex> | <tex> A[3][3] </tex> |
 
Folosind recurenţa <tex> (*) </tex> obţinem că matricea <tex> b </tex> este:
 
table{width: 90px; text-align: center}.
| <tex> 1 </tex> | <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |
| <tex> 0 </tex> | <tex> 2 </tex> | <tex> 0 </tex> | <tex> 3 </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 1 </tex> | <tex> -1 </tex> |
| <tex> 0 </tex> | <tex> 1 </tex> | <tex> 0 </tex> | <tex> 1 </tex> |
 
De aici obţinem sistemul de inegalităţi:
 
<tex> 0 \le x_{1} \le 1,  0 \le x_{2} \le 1, 0 \le x_{3} \le 1, </tex>
<tex> 0 \le y_{1} \le 1, -2 \le -x_{1} - y_{1} \le -1, 0 \le -x_{2} + y_{1} \le 1, -3 \le -x_{3} - y_{1} \le -2, </tex>
<tex> 0 \le y_{2} \le 1,  0 \le  x_{1} - y_{2} \le  1,-1 \le  x_{2} + y_{2} \le 0,  1 \le  x_{3} - y_{2} \le  2, </tex>
<tex> 0 \le y_{3} \le 1, -1 \le -x_{1} - y_{3} \le  0, 0 \le -x_{2} + y_{3} \le 1, -1 \le -x_{3} - y_{3} \le  0 </tex>
 
Transformăm relaţiile astfel ca să nu apară nicio constantă negativă:
 
<tex> 0 \le x_{1} \le 1, 0 \le x_{2} \le 1, 0 \le x_{3} \le  1, </tex>
<tex> 0 \le y_{1} \le 1, 1 \le x_{1} + y_{1} \le 2, 0 \le -x_{2} + y_{1} \le 1, 2 \le x_{3} + y_{1} \le 3, </tex>
<tex> 0 \le y_{2} \le 1, 0 \le x_{1} - y_{2} \le 1, 0 \le -x_{2} - y_{2} \le 1, 1 \le x_{3} - y_{2} \le 2, </tex>
<tex> 0 \le y_{3} \le 1, 0 \le x_{1} + y_{3} \le 1, 0 \le -x_{2} + y_{3} \le 1, 0 \le x_{3} + y_{3} \le 1 </tex>
 
Acest sistem poate fi transformat într-o expresie booleană:
 
<tex> (x_{1} \vee y_{1}) \wedge (\sim x_{2} \vee y_{1}) \wedge (x_{3} \wedge y_{1}) \wedge </tex>
<tex> (x_{1} \vee \sim y_{2}) \wedge (\sim x_{2} \wedge \sim y_{2}) \wedge (x_{3} \wedge \sim y_{2}) \wedge </tex>
<tex> (\sim x_{1} \vee \sim y_{3}) \wedge (\sim x_{2} \vee y_{3}) \wedge (\sim x_{3} \vee \sim y_{3}) </tex>.
 
Acestă expresie e satisfăcută de valorile: <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 1, y_{1} = 1, y_{2} = 0, y_{3} = 0 \rangle </tex>, iar de aici putem determina o soluţie a problemei noastre iniţiale ca fiind:
 
table{width: 90px; text-align: center}.
| <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> | <tex> 1 </tex> |
| <tex> 1 </tex> | <tex> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> |
| <tex> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |
 
h2(#probleme). Probleme propuse
 
Pentru a vă familiariza cu subiectul prezentat în acest articol, vă propunem să încercaţi să rezolvaţi următoarele probleme:

Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> | b[i][j] | \le 2 </tex> altfel nu avem soluţie. Dacă <tex> | b[i][j] | = 2 </tex> atunci ambele variabile au valori fixe, iar dacă <tex> | b[i][j] | = 1 </tex> sau <tex> | b[i][j] | = 0 </tex> atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.

# 'Excursion':http://www.oi.edu.pl/download/boi-2001.pdf - Baltic Olympiad in Informatics, 2001
# 'Peaceful Commission':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 2001

O relaţie precum <tex> 0 \le x + y \le 1 </tex> poate fi tansformată logic în <tex> \sim x \vee \sim y </tex>, astfel <tex> x </tex> şi <tex> y </tex> nu vor fi în acelaşi timp <tex> 1 </tex>, una de genul <tex> 1 \le x + y \le 2 </tex> va fi transformată în <tex> (x \vee y) </tex>, astfel cel puţin <tex> x </tex> sau <tex> y </tex> va fi egal cu <tex> 1 </tex>, alta de tipul <tex> 0 \le x - y \le 1 </tex> poate fi scrisă ca <tex> x \vee \sim y </tex>, una de tipul <tex> 2 \le x + y \le 3 </tex> în <tex> x \wedge y </tex>, iar una de tipul <tex> 0 \le -x -y \le 1 </tex> în <tex> \sim x \wedge \sim y </tex>, una de tipul <tex> 1 \le x - y  \le 2 </tex> în <tex> x \wedge \sim y </tex>.

h2(#bibliografie). Bibliografie:

# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere în Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm
# '_Satisfiability_':http://en.wikipedia.org/wiki/Satisfiability, Wikipedia
# '_BOI 2001 Competition Material_':http://www.oi.edu.pl/download/boi-2001.pdf
# '_CEOI 2002 Competition Material_':http://ics.upjs.sk/ceoi/Documents.html

3704