Numere naturale Booleene

Numere naturale Booleene

Se considera ecuatia (1) a_i x_i = b_i

Sa se proiecteze un algoritm care pentru a= (a₁ , a₂ , , a_n) a >0 si b numere reale precizate si pozitive sa se genereze toate solutiile booleene xI[0,1]ⁿ , x =

xI [0,1] ale ecuatiei

Caz particular

Se considera ec. (1) 3x₁ + 5 x₂ + 6 x₃ + 9 x₄ + 10 x₅ + 12 x₆ = b

Se cere:

a)Sa se genereze multimea BÌN stiind ca ( ) bIB , ecuatia (1) admite cel putin o solutie booleana xI

b)Sa se genereze submultimea CÌN stiind ca ( ) bIC, ec(1) admite cel mai mare numar de solutii booleene.

Pentru fiecare bIC sa se precizeze solutiile booleene ale ecuatiei obtinute.

Observatii :

1. In ecuatia (1) putem presupune ca a₁ , a₂ , , a_n si b sunt numere nenule

Dacanu sunt indeplinite aceste conditii se determina cel mai mic numar natural reprezentand numarul maxim de zecimale pe care le pot avea coeficientii sau termenul liber al ecuatiei

In acest caz, facand schimbarile de coeficienti a_i=10^pa_i si b¹=10^pb se inmulteste ecuatia cu 10^p si se fac schimbarile de coeficienti se va obtine ecuatia echivalenta:

a^'_i x_i = b^' _i in care a^'_iN^*, b^'N^*

2. Presupunand ca in ecuatia (1) aN^*, bN^* putem presupune ca sunt verificate inegalitatile

0 a₁ a₂ , a₃.. a_n

Daca una din aceste inegalitati nu este verificata facand o renumerotare convenabila a componentelor (x₁ , x₂ , , x_n) ale necunoscutei x, se va obtine necunoscuta

x'=(x'₁ , x'₂ , , x'_n) astfel incat ecuatia (1") a^'_i x'_i = b este echivalenta cu ecuatia (1) si are coeficientii in ordine crescatoare.

Coeficientii ecuatiei (1") sunt numere naturale si verifica simultan inegalitatile

0 a'₁ a'₂ , a'₃.. a'_n

3. In ecuatia (1) in care coeficientii a_i si b sunt numere naturale nenule si sunt verificate inegalitatile (2) putem presupune ca, coeficientii ecuatiei sunt primii in ansamblul lor , adica cmmdc (a₁ , a₂ , , a_n) = 1

Daca aceasta conditie nu este indeplinita si daca d=cmmdc(a₁ , a₂ , , a_n) , atunci se pot intalni urmatoarele cazuri:

Cazul 1:

d b ecuatia (1) nu admite solutii in N si algoritmul se incheie.

Cazul 2:

d b facand schimbarile de coeficient : a'_i = , b' = din ecuatia (1) se obtine ecuatia echivalenta :

a^'_i x_i = b^' _i in care a^'_iN^*, b^'N^*

0 a₁ a₂ , a₃ a_n

cmmdc (a₁ , a₂ , , a_n) = 1

Descrierea algoritmului

Presupunem ca in ecuatia (1) sunt verificate conditiile (2) si (3) anterioare

a)      pentru a genera BN cu proprietatea ca , ecuatia ( 1) admite cel putin o solutie booleana se aplica algoritmul de generare asemanator cu cel de la k-binare cu deosebirea ca se introduc ranguri de marime (in loc de valori ) .

In acest caz B₁ va fi formata din coeficientii ecuatiei in ordinea in care apar in ecuatie.

B₁=

Elementul a_i apartine rangului i

Elementul a_j apartine rangului j

Presupunem ca rangul i < rangul j daca elementele a_i au fost generate inaintea elementelor a_j.

B₁ verifica urmatoarea proprietate:

, ecuatia (1) obtinuta admite cel putin o solutie booleana avand o singura componenta egala cu 1, restul componentelor fiind zero.

Exemple:

b=a₂ (1) a₁x₁+ a₂x₂+ .+ a_kx_k+. +a_nx_n= a₂ admite solutia booleana (0,1,0,..,0)

Pentru k2, elementele submultimii B_k vor fi generate astfel:

- fiecare x B_k-1 anterioar generate x de rang i se aduna cu toate elementele y B₁, y rang j, rangul i < rangul j .

Daca se continua pentru orice x B_k-1 algoritmul descris mai sus, submultimea B_k obtinuta are proprietatea ca _k , ecuatia corespondenta admite cel putin o solutie care are k2 componente egale cu 1, restul componentelor fiind zero.

Submultimea B_n= are un singur element.

Submultimea B= B₁ B₂ B_3. B_n este submultimea ceruta in enunt.

b) Cu ajutorul elementelor din B₁, B₂,.. ,B_n, anterior generate vor fi generate submultimile B₁, B₂,.. ,B_k, k ] astfel:

In submultimea B_m, , 1 m k vor fi introduse acele elemente care apar de

m ori in submultimile B₁, B₂,.. ,B_n.

Procedand analog pentru 1,k submultimile B_m au urmatoara proprietate:

_m, ecuatia (1) corespunzatoare are m- solutii booleene. Deci C= B_k, este submultimea pentru care , ecuatia (1) obtinuta are k solutii booleene.

Caz particular

(1) 3x₁ + 5 x₂ + 6 x₃ + 9 x₄ + 10 x₅ + 12 x₆ = b

a)

B1: 3 5 6 9 10 12

B2: 8 9 12 13 15

11 14 15 17

15 16 18

19 21

22

B3: 14 17 18 20

18 19 21

20 21 23

22 24

24 26

25 27

25

27

28

31

B4: 23 24 26

27 29

28 30

30 32

30

31

33

34

36

37

B5: 33 35

36

39

40

42

B6: 45

B=B₁ B₂ B₃ B₄ B₅ B₆=

b)

n=6 k=[]=[3] B_1, B_2, B_3, numarul maxim de solutii booleene este 3

( [0,1]⁶)

3 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

1 2 1 2 3 1 2 3 2 2 3 2 2 3 2 2 3 2 1 3 2

32 33 34 35 36 37 39 40 42 45

2 1 1 2 1 1 1 1 1

Pentru:

b ecuatia are o singura solutie booleana

b ecuatia nu are solutii booleene

b ecuatia are 2solutii booleene

b ecuatia are 3 solutii booleene

B1 =

Ecuatia admite o singura solutie booleana:

X1 X2 X3 X4 X5 X6 | b

B1| 0 0 1 0 0 0 |6

B2| 1 0 0 0 1 1 | 25

B2 =

B3 =

| 0 1 1 1 1 0 |

B3 | 1 0 0 0 0 1 | 15 3 solutii booleene

| 0 1 0 0 1 0 |

| 0 0 1 1 0 0 |