Poprzedni
Następny  

4. Metody minimalizacji funkcji boolowskich

4.3. Minimalizacja metodą sekwencyjnego pokrywania

Strategia sekwencyjnego pokrywania zakłada uogólnienie pojedynczej kostki zbioru F, usunięcie kostek pokrytych przez kostkę uogólnioną, a następnie powtórzenie procesu dla pozostałych elementów zbioru F. Pozwala to na wyznaczenie zbioru kostek pokrywających wszystkie kostki zbioru F. Celem etapu uogólniania kostki jest zmniejszenie liczby jej zmiennych tak, aby uzyskana kostka pokrywała jak największą liczbę kostek zbioru F,  nie pokrywając przy tym żadnej kostki zbioru R:

 

  1. Oblicza się ekspansję kostki k1 (ozn. E(k1)) – tylko jedną.
  2. Wykreśla się z macierzy F  wszystkie wektory pokrywane przez E(k1).
  3. Powstaje nowa  macierz F’, w której bierzemy pierwszą kostkę i postępujemy tak samo,
  4. Proces kończy się, gdy pokryjemy (wykreślimy) wszystkie kostki F,

Wynik (zminimalizowaną funkcję) tworzą kolejno obliczone ekspansje.

Funkcję boolowską opisaną zbiorami F i R zminimalizować metodą sekwencyjnego pokrywania.

 

F:

 

R:

00000

11000

11010

01110

11100

01011

 

11101

00010

00110

10001

01100

 

 

Rozwiązanie

 

k

 

 

 

F:

1

2

3

4

5

6

00000

11000

11010

01110

11100

01011

R:

11101

00010

00110

10001

01100

 

 

Liczymy ekspansję k1.

Ponieważ k1 = (00000), to macierz blokująca B1 jest identyczna z macierzą R.

Uzupelnij opis obrazka

Wypisujemy w każdym wierszu numery kolumn z jedynkami. Następnie wybieramy taki zbiór, który zapewni minimalne pokrycie kolumnowe. Do pokrycia wybieramy L = {3,4,5}; (x3 x4 x5).

k_1^+\ \ dla k 1=00000       będzie --000:  {\bar{x}}_3{\bar{x}}_4{\bar{x}}_5             k_1^+\geq k_2. Pokryta została także kostka k2

 

k3

11010

 

 

 

1 2 3 4 5

 

 

 

 

R:

11101

00010

00110

10001

01100

 

B3:

 

00111

11000

11100

01011

10110

 

3,4,5

1,2

1,2,3

2,4,5

1,3,4

 

Minimalne pokrycie zapewnia  L={1,5} (x1 x5)

k_3^+=1---00x_1{\bar{x}}_5     k_3^+\geq k_5

 

Kostka k 3+ pokrywa także k 5, do dalszych obliczeń zostają kostki k 4, k 6

 

k 4

01110

 

 

 

1 2 3 4 5

 

 

 

 

R:

11101

00010

00110

10001

01100

 

B4:

 

10011

01100

01000

11111

00010

 

1,4,5

2,3

2

1,2,3,4,5

4

 

Minimalne pokrycie zapewnia  L={2,4}; (x2 x4)

k_4^+\geq k_6=\mathrm{-}1-11x_2x_4     k_4^+\geq k

Zbierając wszystkie kostki pokrycia otrzymujemy funkcję minimalną:

 

f={\bar{x}}_3{\bar{x}}_4{\bar{x}}_5+x_1{\bar{x}}_5+x_2x_4

Funkcja z przykładu 2.15 zminimalizowana programem InstantRS jest reprezentowana następującymi wyrażeniami:

1] !x1!x2!x4 + x1!x5 + x2x4

2] !x1!x3!x4 + x1!x5 + x2x4

3] !x2!x4!x5 + x1!x5 + x2x4

4] !x3!x4!x5 + x1!x5 + x2x4

 

Taki sam wynik uzyskamy z programu Hummingbird: f = !x2!x4!x5+x1!x5+x2x4. Nie oznacza to jednak, że strategia sekwencyjnego pokrywania jest tak samo skuteczna jak  metoda systematyczna z algorytmem MinRow.  Świadczy o tym wynik minimalizacji funkcji Kaz, obliczonej programem Blink. Blink reprezentuje dane wyjściowe w postaci tzw. Reguł decyzyjnych omawianych w rozdziale 5. Reguły te – dla funkcji Kaz – są następujące:

 

(x3=0) & (x4=1) & (x18=1) => (y=1)

(x2=1) & (x3=1) & (x5=1) => (y=1)

(x1=0) & (x3=1) & (x5=1) => (y=1)

(x1=0) & (x6=1) & (x9=1) => (y=1)

(x3=0) & (x6=1) & (x15=0) => (y=1)

(x1=0) & (x3=1) & (x13=0) => (y=1)

(x2=0) & (x5=1) & (x8=1) => (y=1)

 

Oczywiście możemy te reguły zapisać  sumy iloczynów zmiennych boolowskich:

!x3x4x18 + x2x3x5 + !x1x3x5 + !x1x6x9 + !x3x6!x15 + !x1x3!x13 + !x2x5x8

 

Natomiast Kaz zminimalizowany programem Hummingbird jest wyrażeniem:

f =  x4!x13x21 + x7!x15x16 + !x4!x17!x21

nieco prostszym od wyrażenia uzyskanego programem Espresso:

y1 = !x2x14!x19x21 + !x8!x11!x12 + x5x8!x20

 

 

 

 
  Poprzedni
Następny