DEKOMPOZYCJA FUNKCJI
BOOLOWSKICH METOD
NAKRYĆ I PODZIAA
ÓW
1. Wprowadzenie
2. Poj cia podstawowe
 Nakrycia, Systemy zbiorów, Podziały
2. Dekompozycja szeregowa
 Dekompozycja rozł czna (disjoint)
 Dekompozycja nierozł czna (non-disjoint)
 Dekompozycja metod nakryć
4. Podstawowe procedury dekompozycji
5. Implementacja i eksperymenty: DEMAIN
1
Przykład wprowadzaj cy
x1x2x3x4x5 y1 y2y3
1 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 1 0
3 0 0 0 1 0 1 0 0
4 0 1 1 0 0 0 1 1
5 0 1 1 0 1 0 0 1
6 0 1 1 1 0 0 1 0
7 0 1 0 0 0 0 0 1
8 1 1 0 0 0 0 0 1
9 1 1 0 1 0 0 0 0
10 1 1 1 0 0 1 0 0
11 1 1 1 1 1 0 1 1
12 1 1 1 1 0 0 1 0
13 1 0 0 0 1 0 0 1
14 1 0 0 1 1 0 0 0
15 1 0 0 1 0 1 0 0
P1 = (1,2,3,4,5,6,7; 8,9,10,11,12,13,14,15)
P2 = (1,2,3,13,14,15; 4,5,6,7,8,9,10,11,12)
P3 = (1,2,3,7,8,9,13,14,15; 4,5,6,10,11,12)
P4 = (1,4,5,7,8,10,13; 2,3,6,9,11,12,14,15)
P5 = (1,3,4,6,7,8,9,10,12,15; 2,5,11,13,14)
PF = (1,9,14; 5,7,8,13;2,6,12;4,11;3,10,15)
2
Dekompozycja szeregowa
Warunek istnienia dekompozycji o schemacie blokowym jak
na rysunku, gdzie U, V s rozÅ‚ cznymi podzbiorami X oraz W Ä
V, formułuje nast puj ce twierdzenie.
U
G
H
Y
Twierdzenie. Funkcja F: Bn %7Å„{0,1}m ma dekompozycj
F = H(U,G (V,W))
wtedy i tylko wtedy, gdy istnieje dwublokowy podział
PG Ë PVźW taki, e:
PU · PG Ę PF.
Zastosowanie rachunku podziałów jest wyj tkowo wygodne!!!
Odpowiednie twierdzenie o dekompozycji układów
wielowyj ciowych traktuje zespół funkcji jako pojedynczy
obiekt, podlegaj cy zasadom dekompozycji identycznie jak
pojedyncza funkcja boolowska.
3
Przykład c.d.
P(x1) = {(1)(2,6)(3)(4)(5,7); (8,13)(9,14)(10,15)(11)(12)}
czyli P(x1) jest 4-przydatny wzgl dem PF.
P(x3), P(x4) s 3-przydatne, P(x2), P(x5) s 4-przydatne.
a) b)
xi
y1
x3 y1
xj
y2
x4 F y2 F
xk
y3 y3
g(x1,...x5)
g(x1,...x5)
P (x3)·P (x4) = {(1)(7,8,13); (9,14)(2)(3,15); (4)(5)(10); (11)(6,12) },
czyli {P(x3), P(x4)} jest 4-przydatny.
4-przydatnymi parami s tylko {P1,P3}, {P1,P4}, {P2,P3},
{P2,P4}, {P3,P4}, {P3,P5} oraz {P4,P5}. W zwi zku z tym
4-przydatnymi trójkami mog być tylko:
a) {P1,P3,P4}; b) {P2,P3,P4}; c) {P3,P4,P5}.
Wył cznie trójki a) oraz c) s 4-przydatne.
P (x1) P (x3) P(x4) = {(1)(7); (8,13); (2)(3); (9,14)(15); (4)(5); (10); (6); (11)(12) },
P (x3) P (x4) P(x5) = {(1)(7,8); (13); (9)(3,15); (14)(2); (4)(10); (5); (6,12); (11)}.
4
Przykład c.d.
Zbiór podziałów P(x1),P(x3),P(x4)} jest 4-przydatny. St d
U = {x1,x3,x4} oraz V {x2,x5}. Podział PU = P1P3P4
(Pi = P(xi)), a wi c:
PUîPF = {(1)(7); (8,13); (2)(3); (9,14)(15); (4)(5); (10); (6); (11)(12) },
PV = {1,3,15; 2,13,14; 4,6,7,8,9,10,12; 5,11},
gdzie bloki PV s oznaczone kolejno H1, H2, ..., H4.
Blokom H1,...,H4 podziału PV odpowiadaj wektory
D(H1) = 00, D(H2) = 01, D(H3) = 10, D(H4) = 11.
PG = (1,3,5,11,15; 2,4,6,7,8,9,10,12,13,14).
x x x x x
G
H
y y y
5
Nakrycia (1)
Nakryciem na zbiorze S nazywamy rodzin
b = {B1,...,Bk} niepustych i ró nych podzbiorów S,
nazywanych blokami, których suma (union) jest S.
Na przykład:
S = {1,2,3}
b = {{1,2}, {2,3}}
b = {{1}, {1,2}, {2,3}}
b = {1,2 ; 23}
,
Iloczyn b  b dwóch nakryć:
b  b = ne{Bi a
Bj î Bi ~
b and Bj ~
b }
6
Nakrycia (2)
Przykład:
{1,2,3; 3,4,5} {1,3,4; 1,5; 2,3,4}={1,3; 1; 2,3; 3,4; 5}
{1,2,3; 3,4,5} {1,2,3; 3,4,5}={1,2,3; 3; 3,4,5}
Iloczyn nakryć nie jest idempotentny.
Je li b i b s nakryciami S, to b Ę b wtt, gdy dla
ka dego Bi z b istnieje Bj w b taki, e Bi Bj.
Przykłady:
{; 2; 3}Ę{,2; 2,3}
1 1
{12; 2,3}Ę{12; 2,3; 13}
, , ,
7
Systemy zbiorów i podziały (1)
Systemem zbiorów na S nazywamy nakrycie
s = {B1,...,Bk}, w którym bloki s maksymalne w tym
sensie, e Bi Bj implikuje i = j.
Przykład:
Dla S = {1,2,3}, s = {{1,2}, {2,3}} jest systemem
zbiorów na S.
Systemy zbiorów nie s zamkni te ze wzgl du na
operacj iloczynu:
{1,2; 2,3} {1,2; 2,3} nie jest systemem zbiorów.
Niech b = {Bi} b dzie nakryciem na S,
max b = {B S î B = Bi dla pewnego i, oraz
B Bj implikuje Bj = B}.
max odwzorowuje nakrycia na systemy zbiorów.
Iloczyn s s dwóch systemów:

s s = max (s s )

Przykład:
{12,3; 3,4,5}o{13,4; 15; 2,3,4}={13; 2,3; 3,4; 5}
, , , ,
8
Systemy zbiorów i podziały (2)
Podziałem na zbiorze S nazywamy system
zbiorów p = {Bi}, którego bloki s rozł czne, czyli,
/
Bi a
Bj = 0, je li i Ä… j.
Przykład
p = {{1,2},{3}} jest podziałem na S = {1,2,3}.
9
Nakrycia dla funkcji boolowskich (1)
Tablica 1
Numer x1 x2 x3 x4 y1 y2
10 0 - 0 1 1
21 0 - 0 1 0
3- 0 0 - 1 -
4- - 1 1 0 -
5 - 1 1 0 0 0
6- 1 - 1 - 1
70 - 0 1 1 -
on-set dla y1:
on
y1 = x1 x2 x4 + x1x2 x4 + x2 x3 + x1 x3x4.
off-set dla y1:
off
y1 = x3x4 + x2x3x4
yon = x1 x2 x4 + x2x4
2
yoff = x1x2 x4 + x2x3x4
2
10
Nakrycia dla funkcji boolowskich (2)
Dla ka dej xi w tablicy funkcji F, definiujemy dwu-
blokowe nakrycie bi = {Fxi 0, Fxi 1} na F jak
nast puje:
Fxi 0 = {t ~
F î ti 0}
oraz
Fxi 1 = {t ~
F î ti 1}
Dla funkcji z Tablicy 1,
b1 = {134567; 23456}
, , , , , , , , ,
b2 = {12,34,7; 4567}
, , , , ,
b3 = {12,367; 12,456}
, , , , , ,
b4 = {12,35; ,34,67}
, , , ,
Dla podzbioru V zbioru X = {x1,...,xn} zmiennych
wej ciowych definiujemy nakrycie wg V
bV =
Ðb
i
xi ~
V
gdzie P iloczynem nakryć.
11
Nakrycia dla funkcji boolowskich (3)
Dla funkcji z Tablicy 1, oraz V = {x2,x3,x4},
uzyskujemy,
Tablica 1
Numer x1 x2 x3 x4 y1 y2
10 0 - 0 1 1
21 0 - 0 1 0
3- 0 0 - 1 -
4- - 1 1 0 -
5 - 1 1 0 0 0
6- 1 - 1 - 1
70 - 0 1 1 -
000 001 010 011 101 110 111
bV ={1,2,3; 3,7; 1,2; 4; 6,7; 5; 4,6}
Nakrycie wyj ciowe dla funkcji z Tablicy 1:
00 01 10 11
bF ={45; 46; 237; 1,367}
, , , , , ,
12
 Twierdzenia
Twierdzenie 1.
Funkcja F specyfikowana zbiorem kostek F ma
dekompozycj szeregow rozł czn ze wzg l du na
(U,V), F = H(U, G(V)), wtt istnieje nakrycie bG na F
takie, e
Ü bV Ę bG,
Ü bU  bG Ę bF,
gdzie bU oraz bV s nakryciami dla zbiorów U oraz V,
a bF jest nakryciem wyj ciowym.
Twierdzenie 2.
Funkcja F specyfikowana zbiorem kostek F ma
dekompozycj szeregow rozł czn ze wzg l du na
(U,V), F = H(U, G(V)), wtt istnieje system zbiorów sG
na F taki, e
 sV Ę sG, and
 sU sG Ę sF,
gdzie sU = max bU oraz sV = max bV systemami zbiorów
dla U oraz V, a sF = max bF jest wyj ciowym systemem
zbiorów.
13
Dekompozycja nierozł czna
U
G
H
Y
Twierdzenie 3.
Je li istnieje nakrycie bG na F takie, e
Ü bV Ę bG, and
Ü bU  * bG Ę bF,
to F ma dekompozycj szeregow ze wzgl du na
nierozł czne zbiory (U,V).
14
Procedury dekompozycji
bG Ë bV : bU  bG Ę sF
Sklejanie bloków z bV. Tak wielu jak to tylko mo liwe.
Dwa bloki Bi i Bj nakrycia bV s zgodne, je li
nakrycie gij uzyskane z bV przez sklejenie Bi oraz Bj w
jeden blok spełnia drugi warunek Twierdzenia 1, tzn.,
je li bU  gij Ę bF.
W przeciwnym przypadku Bi oraz Bj niezgodne.
Podzbiór d bloków nakrycia wej ciowego bV
nazywamy zgodn klas bloków je li bloki w d s
parami zgodne.
Zgodna klasa bloków jest nazywana maksymaln ,
je li nie jest zawarta w adnej innej klasie zgodnej.
Obliczanie maksymalnych klas zgodnych jest
równowa ne do problemu znajdowania maksymalnych
klik w grafie G = (N,E), gdzie zbiór N w złów (nodes)
jest zbiorem bloków w bV, natomiast zbiór E kraw dzi
jest okre lony przez pary bloków zgodnych.
15
Przykład
Dla funkcji z Tablicy 1nale y obliczyć dekom-
pozycj nierozł czn okre lon przez
U = {x1,x4} i V = {x2,x3,x4}
Tablica 1
Numer x1 x2 x3 x4 y1 y2
10 0 - 0 1 1
21 0 - 0 1 0
3- 0 0 - 1 -
4- - 1 1 0 -
5 - 1 1 0 0 0
6- 1 - 1 - 1
70 - 0 1 1 -
bU = {135; 3,4,6,7; 2,35; 3,4,6}
, , ,
B B B B B B B
bV = {1,2,3; 3,7; 1,2; 4; 6,7; 5; 4,6;}
16
Przykład
Pary zgodne: (B1,B4), (B1,B6), (B1,B7), (B2,B4),
(B2,B6), (B2,B7), (B3,B6), (B4,B5), i (B5,B7).
Przy tworzeniu klas maksymalnych musimy
wykluczyć (B1 albo B4) i (B1 albo B6),itd. St d
uzyskujemy 2-składnikow postać normaln (2-CNF),
czyli iloczyn dwu-składnikowych sum:
(B1 + B4)(B1 + B6)(B1 + B7)(B2 + B4)(B2 + B6)
(B2 + B7)(B3 + B6)(B4 + B5)(B5 + B7),
Na tej podstawie tworzy si sum iloczynów:
DNF: Bi Bj Bk É%7Å„ i j k
1 2 3 5 + 1 2 5 6 + 1 2 3 4 7 + 4 6 7
Ka dy iloczyn uzyskanej sumy iloczynów
reprezentuje zbiór, który nale y wykluczyć.
Klasy maksymalne:
{B4, B6, B7}
{B3, B4, B7}
{B5, B6}
{B1, B2, B3, B5}
17
Przykład c.d.
bG = {1,2,3,6,7; 4,5,6}
F = H(x1, x4, G(x2, x3, x4)) (3 komórki)
Znaczenie dekompozycji nierozł cznej:
Komórka o 3 wej ciach i 1 wyj ciu.
H(x1, x2, G(x3, x4)) nie istnieje
H(x1, G(x2, x3, x4)) (4 komórki).
x1 x2 x3 x4 x1 x4 x2 x3 x4
GG
H H
18
Redukcja argumentów  przykład
Funkcja f: Po redukcji:
x1 x2 x3 x4 x5 x6 x7 f x2 x4 x6 x7 f
1 1 0 0 0 1 0 1 0 1 0 0 0 1 0
2 1 0 1 1 1 1 0 0 2 0 1 1 0 0
3 1 1 0 1 1 1 0 0 3 1 1 1 0 0
4 1 1 1 0 1 1 1 0 4 1 0 1 1 0
5 0 1 0 0 1 0 1 1 5 1 0 0 1 1
6 1 0 0 0 1 1 0 1 6 0 0 1 0 1
7 1 0 1 0 0 0 0 1 7 0 0 0 0 1
8 1 0 1 0 1 1 0 1 8 0 0 1 0 1
9 1 1 1 0 1 0 1 1 9 1 0 0 1 1
P1 = {5; 1,2,3,4,6,7,8,9}
P2 = {1,2,6,7,8; 3,4,5,9}
P3 = {1,3,5,6; 2,4,7,8,9}
P4 = {1,4,5,6,7,8,9; 2,3}
P5 = {7; 1,2,3,4,5,6,8,9}
P6 = {1,5,7,9; 2,3,4,6,8}
P7 = {2,3,6,7,8; 1,4,5,9}
Pf = {1,2,3,4; 5,6,7,8,9}
19