ZPT
1
V
U
G
H
Y = F(X)
W
czyli U
∪ V ⊆ X
Dekompozycja metodą rachunku podziałów
X
Ponadto dopuszczamy powiększenie zbioru
argumentów bloku G
U, V są rozłącznymi podzbiorami X,
ale U
∪ V niekoniecznie = X
W jest podzbiorem właściwym U
W
⊂ U
ZPT
1
V
U
G
H
Y = F(X)
W
czyli U
∪ V ⊆ X
Dekompozycja metodą rachunku podziałów
X
Ponadto dopuszczamy powiększenie zbioru
argumentów bloku G
U, V są rozłącznymi podzbiorami X,
ale U
∪ V niekoniecznie = X
W jest podzbiorem właściwym U
W
⊂ U
ZPT
Elementy rachunku podziałów
Podziałem na zbiorze S jest system zbiorów P = {
B
i
}, którego bloki
są rozłączne, czyli
B
i
∩
B
j
=
φ
, jeśli tylko i
≠ j
Π =
)
4,6
;
3,5
;
1,2
(
Podstawowe pojęcia:
Iloczyn podziałów oraz relacja
≤.
Podzbiory nazywamy
blokami
Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S.
i
i
B
S
=
a ponadto
ZPT
Elementy rachunku podziałów…
Powiemy, że podział P
a
jest nie większy od P
b
(co oznaczamy: P
a
≤ P
b
),
jeśli każdy blok z P
a
jest zawarty w pewnym bloku z P
b
.
Π
b
=
)
3,5
;
2,6
;
1,4
(
)
3,5,6
;
1,2,4
(
)
3,5
;
6
;
4
;
1,2
(
Π
a
=
Π
.
=
Π
c
≤
Π
a
Tak
Π
c
Π
b
</
Π(0) – podział najmniejszy
Π(1) – podział największy
)
3,5
;
6
;
4
;
1,2
(
Π
.
=
)
3,5,6
;
1,2,4
(
Π
a
=
)
3,5
;
6
;
4
;
1,2
(
Π
.
=
Π
b
=
)
3,5
;
2,6
;
1,4
(
ZPT
Elementy rachunku podziałów…
Π
b
=
Iloczynem podziałów
Π
a
•
Π
b
nazywamy największy (względem
relacji
≤) podział, który jest nie większy od
Π
a
oraz
Π
b
.
)
3,5
;
2,6
;
1,4
(
)
3,5,6
;
1,2,4
(
Π
a
=
Π
a
•
Π
b
=
;
1,4
(
;
2
)
3,5
;
6
ZPT
Niech P
a
i P
b
są podziałami na S oraz P
a
≥ P
b
. Podział P
a
| P
b
jest
podziałem ilorazowym P
a
i P
b
, jeżeli jego elementy są blokami P
b
,
a bloki są blokami P
a
.
4,5
;
2,3,8
;
1,6,7
P
a
=
6,7
;
4,5
;
3
;
2,8
;
1
P
b
=
Elementy rachunku podziałów…
(4,5)
P
|
P
b
a
=
;
(1)(6,7)
;
(3)(2,8)
Podział ilorazowy
Na przykład:
ZPT
Nowy sposób opisu funkcji - podziały
x
1
x
2
x
3
x
4
x
5
x
6
x
7
f
1
1
0
0
0
1
0
1
0
2
1
0
1
1
1
1
0
0
3
1
1
0
1
1
1
0
0
4
1
1
1
0
1
1
1
0
5
0
1
0
0
1
0
1
1
6
1
0
0
0
1
1
0
1
7
1
0
1
0
0
0
0
1
8
1
0
1
0
1
1
0
1
9
1
1
1
0
1
0
1
1
P
1
=
P
2
=
P
f
=
;
5
{
;
8
,
7
,
6
,
2
,
1
{
;
4
,
3
,
2
,
1
{
}
9
,
8
,
7
,
6
,
4
,
3
,
2
,
1
}
9
,
5
,
4
,
3
P
3
=
;
6
,
5
,
3
,
1
{
}
9
,
8
,
7
,
4
,
2
P
4
=
;
9
,
8
,
7
,
6
,
5
,
4
,
1
{
}
3
,
2
P
5
=
;
7
{
}
9
,
8
,
6
,
5
,
4
,
3
,
2
,
1
P
6
=
;
9
,
7
,
5
,
1
{
}
8
,
6
,
4
,
3
,
2
P
7
=
;
8
,
7
,
6
,
3
,
2
{
}
9
,
5
,
4
,
1
}
9
,
8
,
7
,
6
,
5
Funkcja f
ZPT
7
… w ujęciu rachunku podziałów
Funkcję F: B
n
{0,1}
m
można zrealizować w strukturze:
F = H(U,G(V,W))
Twierdzenie o dekompozycji
U
G
H
Π
G
P
F
wtedy i tylko wtedy, gdy istnieje podział
Π
G
≥ P
V
∪W
taki, że:
P
U
·
Π
G
≤ P
F
ZPT
8
Twierdzenie o dekompozycji - interpretacja
Π
G
≥ P
V
∪W
taki, że: P
U
·
Π
G
≤ P
F
F
Y = F(X)
X
Y = H(U,G(V,W))
U
G
H
Π
G
X
Π
Π
Π
Π
G
P
U
P
V
∪W
(P
V
)
P
F
to podziały indukowane przez
argumenty zbiorów U, V
∪ W, (V)
Podział wyjściowy funkcji F
Trzeba obliczyć!!!
ZPT
9
Przykład (TL27) ilustrujący skuteczność
dekompozycji
.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e
Można wykazać, że funkcja ta
jest zależna od
7 argumentów
X = {x
3
, x
5
, x
6
, x
7
, x
8
, x
9
, x
10
}
Książka Programowalne układy… str. 52
Dalej wszystkie obliczenia będą wykonywane na podziałach
P
3
, P
5
, P
6
, P
7
, P
8
, P
9
, P
10
Celem przykładu jest pokazanie, że cały proces
dekompozycji (łącznie z obliczeniem tablic prawdy)
można wykonać wyłącznie na podziałach
Są to podziały na zbiorze ponumerowanych
wektorów 1,…,25
ZPT
10
Specyfikacja funkcji – podziałami
P
3
=
;
25
,
20
,
14
,
13
,
12
,
11
,
9
,
8
,
6
,
5
,
3
{
}
24
,
23
,
22
,
21
,
19
,
18
,
17
,
16
,
15
,
10
,
7
,
4
,
2
,
1
P
5
=
;
24
,
21
,
19
,
16
,
15
,
14
,
11
,
9
,
6
,
5
,
3
,
2
{
}
25
,
23
,
22
,
20
,
18
,
17
,
13
,
12
,
10
,
8
,
7
,
4
,
1
P
6
=
;
24
,
22
,
21
,
20
,
19
,
17
,
15
,
13
,
9
,
7
,
4
{
}
25
,
23
,
18
,
16
,
14
,
12
,
11
,
10
,
8
,
6
,
5
,
3
,
2
,
1
P
f
=
;
9
,...,
2
,
1
{
}
25
,...,
10
P
7
=
;
24
,
22
,
20
,
19
,
16
,
15
,
13
,
12
,
11
,
9
,
8
,
7
,
6
,
5
,
2
{
}
25
,
23
,
21
,
18
,
17
,
14
,
10
,
4
,
3
,
1
P
8
=
;
25
,
22
,
19
,
17
,
16
,
13
,
12
,
10
,
9
,
8
,
5
,
4
,
1
{
}
24
,
23
,
21
,
20
,
18
,
15
,
14
,
11
,
7
,
6
,
3
,
2
P
9
=
;
25
,
23
,
19
,
17
,
16
,
13
,
11
,
8
,
2
{
}
24
,
22
,
21
,
20
,
18
,
15
,
14
,
12
,
10
,
9
,
7
,
6
,
5
,
4
,
3
,
1
P
10
=
;
25
,
24
,
22
,
19
,
15
,
13
,
11
,
9
,
8
,
7
,
6
,
3
,
2
,
1
{
}
23
,
21
,
20
,
18
,
17
,
16
,
14
,
12
,
10
,
5
,
4
ZPT
11
Ustalenie zbiorów U i V
X = {x
3
, x
5
, x
6
, x
7
, x
8
, x
9
, x
10
}
U = {x
7
, x
8
, x
9
}
V = {x
3
, x
5
, x
6
, x
10
}
f
G
H
x
7
x
8
x
9
x
3
x
5
x
6
x
10
Przyjmujemy arbitralnie…
Nie wiemy ile jest
wyjść z bloku G
ZPT
12
Obliczenie podziałów P
U
, P
V
)
23
;
17,25
;
8,13,16,19
;
24
6,7,15,20,
;
5,9,12,22
;
3,14,18,21
;
2,11
;
1,4,10
(
P
V
=
)
21
;
20
;
16
;
15,19,24
;
13
;
12
;
10,18,23
;
9
;
8,25
;
7,22
;
5,14
;
4,17
;
3,6,11
;
2
;
1
(
P
U
=
P
U
=P
7
•P
8
•P
9
P
V
=P
3
•P
5
•P
6
•P
10
Można je wyznaczyć bezpośrednio z tablicy funkcji, ale
tym razem przy zastosowaniu rachunku podziałów:
…obliczenia są żmudne, ale proste
U = {x
7
, x
8
, x
9
} V = {x
3
, x
5
, x
6
, x
10
}
ZPT
13
)
23
;
17,25
;
8,13,16,19
;
24
6,7,15,20,
;
5,9,12,22
;
3,14,18,21
;
2,11
;
1,4,10
(
((1,4)(10)
P
U
=
P
f
=
;
1,2,...,9
{
10,...,25}
Podział ilorazowy P
u
|P
u
•
P
F
; (2)(11)
(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))
; (3)(14,18,21) ; (5,9)(12,22)
P
u
|P
u
•
P
f
=
Przy liczeniu podziału ilorazowego po prostu rozdzielamy
elementy bloków P
U
między różne bloki podziału P
f
W każdym bloku P
u
|P
u
• P
f
są co najwyżej dwa elementy (nawiasy),
zatem liczba bloków podziału Π
G
musi być co najmniej dwa.
ZPT
14
Obliczenie Π
G
)
24
23,
21,
20,
19,
18,
4,15,16,
13,1
10,
2,5,9,
;
25
22,
17,
11,12,
7,8,
6,
1,3,4,
(
Π
g
=
P
u
|P
u
· P
f
= ((1,4)(10) ; (2)(11) ; (3)(14,18,21) ; (5,9)(12,22) ;
(6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23))
P
V
=
)
21
;
20
;
16
;
15,19,24
;
13
;
12
;
10,18,23
;
9
;
8,25
;
7,22
;
5,14
;
4,17
;
3,6,11
;
2
;
1
(
4,17
1
10,18,23
3,6,11
2
5,14
12
7,22
8,25
9
15,19,24
20
13
16
21
ZPT
15
Liczba wyjść bloku G
f
G
H
x
7
x
8
x
9
x
3
x
5
x
6
x
10
Liczba wyjść z bloku G = 1
Skoro Π
G
jest dwublokowy
f
G
H
x
7
x
8
x
9
x
3
x
5
x
6
x
10
ZPT
16
Co dalej …
Zawartość bloków G i H, czyli tablice prawdy
funkcji G i H
f
G
H
x
7
x
8
x
9
x
3
x
5
x
6
x
10
ZPT
17
Funkcja G
x
3
x
5
x
6
x
10
g
P
V
=
)
21
;
20
;
16
;
15,19,24
;
13
;
12
;
10,18,23
;
9
;
8,25
;
7,22
;
5,14
;
4,17
;
3,6,11
;
2
;
1
(
1 1 1 0
0
1 0 1 0
1
0 0 1 0
0
)
24
23,
21,
20,
19,
18,
4,15,16,
13,1
10,
2,5,9,
;
25
22,
17,
11,12,
7,8,
6,
1,3,4,
(
Π
g
=
P
3
=
;
25
,
20
,
14
,
13
,
12
,
11
,
9
,
8
,
6
,
5
,
3
{
}
24
,
23
,
22
,
21
,
19
,
18
,
17
,
16
,
15
.
10
,
7
,
4
,
2
,
1
P
5
=
;
24
,
21
,
19
,
16
,
15
,
14
,
11
,
9
,
6
,
5
,
3
,
2
{
}
25
,
23
,
22
,
20
,
18
,
17
,
13
,
12
,
10
,
8
,
7
,
4
,
1
P
6
=
;
24
,
22
,
21
,
20
,
19
,
17
,
15
,
13
,
9
,
7
,
4
{
}
25
,
23
,
18
,
16
,
14
,
12
,
11
,
10
,
8
,
6
,
5
,
3
,
2
,
1
P
10
=
;
25
,
24
,
22
,
19
,
15
,
13
,
11
,
9
,
8
,
7
,
6
,
3
,
2
,
1
{
}
23
,
21
,
20
,
18
,
17
,
16
,
14
,
12
,
10
,
5
,
4
Wektory (wiersze) tablicy funkcji g
są wyznaczane przez bloki P
V
,
a wartości tej funkcji przez bloki Π
G
ZPT
18
Funkcja H
x
7
x
8
x
9
g
h
...)
14,18,21
;
3
;
11
;
2
;
10
;
1,4
(
=
P
U
• Π
G
< P
F
1 0 1 0
0
1 0 1 1
1
0 1 0 1
0
P
7
=
;
24
,
22
,
20
,
19
,
16
,
15
,
13
,
12
,
11
,
9
,
8
,
7
,
6
,
5
,
2
{
}
25
,
23
,
21
,
18
,
17
,
14
,
10
,
4
,
3
,
1
P
8
=
;
25
,
22
,
19
,
17
,
16
,
13
,
12
,
10
,
9
,
8
,
5
,
4
,
1
{
}
24
,
23
,
21
,
20
,
18
,
15
,
14
,
11
,
7
,
6
,
3
,
2
P
9
=
;
25
,
23
,
19
,
17
,
16
,
13
,
11
,
8
,
2
{
}
24
,
22
,
21
,
20
,
18
,
15
,
14
,
12
,
10
,
9
,
7
,
6
,
5
,
4
,
3
,
1
)
24
23,
21,
20,
19,
18,
4,15,16,
13,1
10,
2,5,9,
;
25
22,
17,
11,12,
7,8,
6,
1,3,4,
(
Π
g
=
Wektory (wiersze) tablicy
funkcji h są wyznaczane
przez bloki P
U
• Π
G
, a wartości
tej funkcji przez bloki P
F
ZPT
19
Co uzyskaliśmy…
f
G
H
x
7
x
8
x
9
x
3
x
5
x
6
x
10
Tylko 2 komórki typowej
struktury FPGA
QUARTUS
Uzyskaliśmy wynik dziesięciokrotnie razy lepszy od
wyniku systemu Quartus amerykańskiej firmy
Altera
23 kom.
ZPT
20
Dekompozycja zespołu funkcji
X
F
X
G
H
Y
U
V
Y = y
1
, y
2
,…, y
m
Twierdzenie w ujęciu rachunku podziałów jest ogólne,
obliczenia są niezależne od liczby wyjść funkcji F.
Dekompozycja
ZPT
21
x
1
x
2
x
3
x
4
x
5
y
1
y
2
y
3
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
)
15
,
14
,
13
,
12
,
11
,
10
,
9
,
8
;
7
,
6
,
5
,
4
,
3
,
2
,
1
(
1
=
P
;
14
,
9
,
1
(
Przykład dekompozycji zespołu funkcji (SUL Przykład 8.4)
)
12
,
11
,
10
,
9
,
8
,
7
,
6
,
5
,
4
;
15
,
14
,
13
,
3
,
2
,
1
(
2
=
P
)
12
,
11
,
10
,
6
,
5
,
4
;
15
,
14
,
13
,
9
,
8
,
7
,
3
,
2
,
1
(
3
=
P
)
15
,
14
,
12
,
11
,
9
,
6
,
3
,
2
;
13
,
10
,
8
,
7
,
5
,
4
,
1
(
4
=
P
)
14
,
13
,
11
,
5
,
2
;
15
,
12
,
10
,
9
,
8
,
7
,
6
,
4
,
3
,
1
(
5
=
P
Niezależnie od liczby
funkcji wszystkie
wyjścia opisujemy
jednym!
podziałem
;
15
,
10
,
3
)
11
,
4
;
13
,
8
,
7
,
5
;
12
,
6
,
2
v
v
v
v
v
v
=
F
P
ZPT
22
Przykład…wyznaczanie podziałów
P
U
, P
V
U = {x
3
,x
4
} V = {x
1
,x
2
,x
5
}
6,11,12
;
4,5,10
;
5
2,3,9,14,1
;
1,7,8,13
P
U
=
3,10,15
;
4,11
;
2,6,12
;
5,7,8,13
;
1,9,14
P
F
=
;
)
(1)(7,8,13
P
U
= P
3
•
P
4
P
V
=P
1
•
P
2
•
P
5
=
F
U
U
P
P
|
P
;
3,15)
(2)(9,14)(
(11)(6,12)
;
(4)(5)(10)
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
x
3
x
4
x
1
x
2
x
5
g
h
• • •
Szukamy dekompozycji
ZPT
23
Przykład…obliczanie
Π
Π
Π
Π
G
(2)
(9,14)
(3,15)
2
12
,
10
,
9
,
8
14
,
13
3
,
1
15
7
,
6
,
4
5
11
5
1,3,5,11,1
;
13,14
8,9,10,12,
;
2,4,6,7
Π
G
=
(11)(6,12)
;
(4)(5)(10)
;
3,15)
(2)(9,14)(
;
)
(1)(7,8,13
P
|
P
F
U
=
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
Jak wyznaczyć
Π
Π
Π
Π
G
???
Trochę
inny
zapis
ZPT
24
Przykład…kodowanie
Π
G
5
1,3,5,11,1
;
;
13,14
8,9,10,12,
2,4,6,7
=
Π
G
Należy zakodować bloki Π
G
01
10
00
Kodowanie jest dowolne
Aktualna teoria nie podaje rozwiązania
problemu kodowania
W przypadku zespołu funkcji liczba bloków podziału Π
G
jest większa.
Kodowanie jest potrzebne do wyznaczenia tablic prawdy funkcji G i H
ZPT
25
Tablica prawdy G
)
14
,
13
,
11
,
5
,
2
;
15
,
12
,
10
,
9
,
8
,
7
,
6
,
4
,
3
,
1
(
)
12
,
11
,
10
,
9
,
8
,
7
,
6
,
5
,
4
;
15
,
14
,
13
,
3
,
2
,
1
(
)
15
,
14
,
13
,
12
,
11
,
10
,
9
,
8
;
7
,
6
,
5
,
4
,
3
,
2
,
1
(
5
2
1
=
=
=
P
P
P
x
1
x
2
x
5
g
1
g
2
. . .
. . .
3
,
1
2
7
,
6
,
4
5
1,3,5,11,1
;
;
13,14
8,9,10,12,
2,4,6,7
=
Π
G
01
10
00
0 0 0
0 0 1
0 1 0
0 0
0 1
0 1
5
0 1 1
0 0
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
ZPT
26
Tablica prawdy H
x
3
x
4
g
1
g
2
y
1
y
2
y
3
. . .
. . .
1
7
13
,
8
15
,
3
)
15
,
14
,
12
,
11
,
9
,
6
,
3
,
2
;
13
,
10
,
8
,
7
,
5
,
4
,
1
(
)
12
,
11
,
10
,
6
,
5
,
4
;
15
,
14
,
13
,
9
,
8
,
7
,
3
,
2
,
1
(
4
3
=
=
P
P
P
U
• Π
G
=
5
1,3,5,11,1
;
;
13,14
8,9,10,12,
2,4,6,7
=
Π
G
01
10
00
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
0 0 0
1 0 0
0 0 1
0 0 1
;
7
;
13
,
8
;
15
,
3
…
;
1
(
P
U
• Π
G
< P
F
6,11,12
;
4,5,10
;
5
2,3,9,14,1
;
1,7,8,13
P
U
=
ZPT
27
Co uzyskaliśmy…
Ale dla struktur FPGA
wystarczy schemat
dekompozycji i tablice
prawdy.
Funkcje g i h można obliczyć jawnie…z tablic prawdy
można uzyskać realizacje na bramkach.
x
3
x
4
x
1
x
2
x
5
g
h
Proces minimalizacji
jest niepotrzebny!!!
ZPT
28
Obliczanie podziału Π
G
metodą
przenoszenia bloków P
V
na podstawie
podziału ilorazowego P
U
│P
U
•
Π
G
jest
trudne do zalgorytmizowania.
Szczęśliwie jednak algorytm obliczania
Π
G
można sprowadzić do algorytmu
obliczania MKZ.
Systematyczny algorytm dekompozycji
ZPT
29
Systematyczny algorytm dekompozycji
Dwa bloki B
i
i B
j
podziału P
V
są zgodne, jeśli podział
γ
ij
uzyskany z P
V
przez sklejenie B
i
oraz B
j
w jeden blok i
pozostawienie pozostałych bloków bez zmiany
W przeciwnym przypadku B
i
oraz B
j
są niezgodne.
P
V
=( B
1
,…,B
i
,…,B
j
,…,B
N
)
γ
ij
=( B
1
,…,B
i
B
j
,…,B
N
)
spełnia warunek Twierdzenia o dekompozycji: P
U
• γ
ij
≤ P
F
.
ZPT
30
Przykład (ten sam co poprzednio)
6,11,12
;
4,5,10
;
5
2,3,9,14,1
;
1,7,8,13
P
U
=
3,10,15
;
4,11
;
2,6,12
;
5,7,8,13
;
1,9,14
P
F
=
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
(11)(6,12)
;
(4)(5)(10)
;
3,15)
(2)(9,14)(
;
)
(1)(7,8,13
P
P
|
P
F
U
U
=
γ
57
=
γ
12
=
;
1,2,3
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
13,14
8,9,10,12,
;
5
;
4,6,7
;
2
;
1,3
15
;
11
U = {x
3
,x
4
} oraz V = {x
1
,x
2
,x
5
}
Numerujemy bloki P
V
ZPT
31
Przykład …
Ale do wyznaczenia zgodnych (lub sprzecznych) par (B
i
, B
j
)
niekoniecznie musimy się posługiwać skomplikowaną
nierównością P
U
•
γ
ij
≤
P
F
Można sprawdzić, że
P
U
• γ
12
P
F
,
P
U
• γ
57
≤
P
F
</
(B
1
, B
2
) jest sprzeczna
(B
5
, B
7
) jest zgodna
Wystarczy w tym celu obliczyć iloczyn zbioru B
i
∪ B
j
z blokami podziału P
U
i sprawdzić, czy każdy „niepusty
iloczyn” jest zawarty w jakimś bloku P
F
ZPT
32
Przykład …
6,11,12
;
4,5,10
;
5
2,3,9,14,1
;
1,7,8,13
P
U
=
3,10,15
;
4,11
;
2,6,12
;
5,7,8,13
;
1,9,14
P
F
=
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
(B
1
,B
2
) jest sprzeczna
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
B
1
∪
B
2
=
1,2,3
1,2,3
•
P
U
)
( 2,3
;
1
=
</
P
F
B
5
∪
B
7
=
13,14
8,9,10,12,
13,14
8,9,10,12,
•
P
U
12
;
10
;
9,14
;
8,13
=
≤ P
F
(B
5
, B
7
) jest zgodna
ZPT
33
Przykład c.d.
Pary zgodne: (B
1
,B
4
), (B
1
,B
6
), (B
1
,B
8
), (B
2
,B
3
), (B
2
,B
4
), (B
2
,B
6
), (B
3
,B
7
),
(B
3,
B
8
), (B
4
,B
6
), (B
4
,B
7
), (B
4
,B
8
), (B
5
,B
7
), (B
6
,B
7
), (B
6
,B
8
).
Doskonale wiemy jak obliczać
Maksymalne Klasy Zgodne
MKZ
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
=
Π
G
;
{B
1
,B
4
, B
6
, B
8
}
;
{B
2
, B
3
}
{B
5
, B
7
}
Klasy maksymalne:
{B
1
,B
4
, B
6
, B
8
}
{B
4
, B
6
, B
7
}
{B
2
, B
4
, B
6
}
{B
3
, B
7
}
{B
3
, B
8
}
{B
2
, B
3
}
{B
5
, B
7
}
ZPT
34
Przykład c.d.
5
1,3,5,11,1
;
13,14
8,9,10,12,
;
2,4,6,7
=
Π
G
15
;
13,14
;
11
;
8,9,10,12
;
5
;
4,6,7
;
2
;
1,3
P
V
=
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
Ten sam rezultat co poprzednio
=
Π
G
;
{B
1
,B
4
, B
6
, B
8
}
;
{B
2
, B
3
}
{B
5
, B
7
}
ZPT
35
Komentarz: algorytmy dekompozycji
Y
A
B
X
G
H
Szeregowa
X
Yg
Yh
G
H
Równoległa
Dekompozycję funkcjonalną nazywać będziemy szeregową, dla
odróżnienia od równoległej