Soluţii corecte: Arthur Weber, Ady Nicolae, Ionel-Vasile Pit-Rada, Claudiu Dragan, Camelia Musetescu, Stefan Gatachiu

Arthur Weber:

Pentru cele patru procesoare avem 16 cazuri posibile în care se pot afla procesele care se execută. Am notat H0 ipoteza că avem un număr nenul de procese care se execută pe cel puţin unul dintre procesoare, iar cu H1-H3 am notat ipotezele din enunţ. Pentru fiecare dintre ipoteze am marcat cu x valorile/stările care nu verifică ipoteza. (de ex. pentru H1 se elimină stările care au 1 pe poziţia lui P1 şi 0 pe poziţia lui P2). La C am marcat cu asterisc stările rămase valide.(2, 3, 10, 11, 14, 15).

   0 1 2 3 4 5 6 7 8 9 a b c d e f
P1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
P2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
P3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
P4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
H0 x
H1   x       x       x       x
H2         x x x x
H3                 x x     x x
 C     * *             * *     * *

Pe baza stărilor rămase valide, analizăm implicaţiile din cerinţe. Rezultă că doar propoziţia 1 este adevărată. 2 şi 6 sunt false pentru cazul 3, 3 şi 4 sunt false în cazul 15, 5 e falsă în cazul 11.

Ionel-Vasile Pit-Rada:

Conform regulilor de calcul formal avem:
(a1) P1->P2
(a2) P3->P4
(a3) not(P2)->not(P4) <=> P2 or not(P4) <=> P4->P2
Afirmatia (a3) Toate procesele care nu utilizeaza P2 nu utilizeaza nici P4 este echivalenta cu
afirmatia (a4) Toate procesele care utilizeaza P4 folosesc P2

(q1) 1. Toate procesele care utilizeaza P3 utilizeaza P2.
Conform (a2), toate procesele care utilizeaza P3 folosesc P4 si apoi conform (a4) folosesc P2.
Deci afirmatia 1 este intotdeauna adevarata.

(q2) 2. Toate procesele care utilizeaza P1 utilizeaza P4.
Ipotezele nu exclud ca teoretic sa putem avea si procese care sa utilizeze P1 si P2 si sa nu utilizeze P4. In aceasta situatie afirmatia 2 este falsa.
Dar, daca se respecta doar ipotezele date (a1) si (a2) si (a3), atunci afirmatia 2 este adevarata.

(q3) 3. Toate procesele care utilizeaza P2 nu utilizeaza P3.
Conform (a2) avem ca toate procesele care utilizeaza P3 utilizeaza P4, de unde conform cu (a4) rezulta ca utilizeaza si P2.
Daca afirmatia 3 ar fi adevarata atunci ar rezulta in continuare ca procesele care utilizeaza P3 nu utilizeaza P3, ceea ce este absurd!
Deci afirmatia 3 este intotdeauna falsa.

(q4) 4. Toate procesele care utilizeaza P3 nu utilizeaza P1.
Conform cu (a2) si (a4) toate procesele care utilizeaza P3 vor utiliza si P4 si deci si P2, deci nu vor utiliza neaparat P1.
Daca ar exista un proces care sa utilizeze P3 si sa utilizeze P1, aceasta situatie nu ar contrazice nici una dintre cele 3 ipoteze. Deci in aceasta situatie afirmatia 4 ar fi falsa.
Dar, daca se respecta doar ipotezele date (a1) si (a2) si (a3), atunci afirmatia 4 este adevarata.

(q5) 5. Toate procesele care utilizeaza P1 utilizeaza P3.
Teoretic pot exista procese care sa utilizeze P1 si sa nu utilizeze P3. Aceasta situatie nu contravine celor 3 ipoteze date. In acest caz afirmatia 5 este falsa.
In acelasi timp , teoretic se poate intampla ca toate procesele sa utilizeze P1 si P3. Aceasta situatie nu contravine celor 3 ipoteze.In acest caz afirmatia 5 este adevarata

(q6) 6. Toate procesele care nu utilizeaza P4 nu utilizeaza P1.
Daca toate procesele care utilizeaza P1 folosesc si P4, atunci afirmatia 6 este adevarata.
Daca toate procesele care utilizeaza P1 nu utilizeaza P4, atunci afirmatia 6 este falsa.

Din analiza facuta mai sus observam ca:
- afirmatia 1 este adevarata.
- afirmatia 3 este falsa
- afirmatiile 2,4,5 si 6 sunt de fapt predicate logice , pentru ca depind de regulile/posibilitatile initiale de asocierea ale procesoarelor pentru procese, nu doar de ipotezele date ; din formularea ipotezelor nu rezultai ca vor fi respectate doar ipotezele date

In alta ordine de idei, pentru a arata dependenta afirmatiilor 2,4,5 si 6 putem considera:
P1=multimea proceselor care folosesc cel putin procesorul P1
P2=multimea proceselor care folosesc cel putin procesorul P2
P3=multimea proceselor care folosesc cel putin procesorul P3
P4=multimea proceselor care folosesc cel putin procesorul P4
Din cele trei ipoteze date rezulta ca:
- P1 este inclusa in P2
- P3 este inclusa in P4
- P4 este inclusa in P2

Cazul 1: - avem procesele 1,2,3,4,5,6
P1={1,2}
P2={1,2,3,4,5,6}
P3={3,4}
P4={3,4,5,6}
In acest context avem:
afirmatia 1 - adevarata
afirmatia 2 - falsa
afirmatia 3 - falsa
afirmatia 4 - adevarata
afirmatia 5 - falsa
afirmatia 6 - adevarata

Cazul 2: - avem procesele 1,2,3,4,5,6
P1={3,4}
P2={1,2,3,4,5,6}
P3={3,4}
P4={3,4,5,6}
In acest context avem:
afirmatia 1 - adevarata
afirmatia 2 - adevarata
afirmatia 3 - falsa
afirmatia 4 - falsa
afirmatia 5 - adevarata
afirmatia 6 - adevarata

Cazul 3: - avem procesele 1,2,3,4,5,6
P1={1,3}
P2={1,2,3,4,5,6}
P3={3,4}
P4={3,4,5,6}
In acest context avem:
afirmatia 1 - adevarata
afirmatia 2 - falsa
afirmatia 3 - falsa
afirmatia 4 - falsa
afirmatia 5 - falsa
afirmatia 6 - falsa

Raspuns final: singura afirmatie adevarata este afirmatia 1

Stefan Gatachiu a oferit o solutie naturala si frumoasa bazata pe multimi.