1

I

T
P

W

ZPT

Tablice

decyzyjne

2

I

T
P

W

ZPT

Synteza logiczna

Inżynieria informacji

Dekompozycja
funkcjonalna

Odwzorowanie technologiczne

FPGA

Hierarchiczne

podejmowanie decyzji



Minimalizacja F.B.



Redukcja argumentów



Generacja reguł
decyzyjnych



Redukcja atrybutów

3

I

T
P

W

ZPT

Tablice i reguły decyzyjne

(a,1)  (b,0)  (d,1)

(e,1)

a b d e

1 1 0 1 1
2 1 0 0 1
3 0 0 0 0
4 1 1 1 0
5 1 1 2 2
6 2 2 2 2

 Atrybuty

 Ich
wartości

 Operatory

redukcja atrybutów
redukcja (generacja) reguł
decyzyjnych

4

I

T
P

W

ZPT

Przykład tablicy decyzyjnej

Atrybuty: wiek

płeć

Stan

cywilny

zawód

Klasa

decyzyjna

x

1

20 Female Married Farm

1

x

2

17 Female Single

Farm

2

x

3

25 Male

Single

Business

3

x

4

16 Female Single

Farm

2

x

5

38 Male

Single

Business

3

x

6

25 Female Single

Pleasure

4

x

7

48 Female Single

Pleasure

4

x

8

20 Female Single

Farm

2

x

9

21 Male

Married Business

5

x

10

22 Male

Married Business

5

x

11

23 Male

Married Business

5

x

12

24 Male

Married Business

5

5

I

T
P

W

ZPT

Reguły decyzyjne generowane

z tablicy decyzyjnej

(Age, 20)  (Marital_Status, Married)



(Class, 1),

(Age 16)



(Class, 2),

(Age, 17)



(Class, 2),

(Age, 20)  (Marital_Status, Single)



(Class, 2),

(Age, 25)  (Gender, Male)

(Class, 3),

(Age, 38)



(Class, 3),

(Age, 25)  (Gender, Female)



(Class, 4)

(Age, 48)



(Class, 4),

(Age, 21)



(Class, 5),

(Age, 22)



(Class, 5),

(Age, 23)



(Class, 5),

(Age, 24)



(Class, 5).

6

I

T
P

W

ZPT

Generacja reguł

Metoda analogiczna do ekspansji:

Tworzy się macierz porównań M,

Wyznacza minimalne pokrycie M,

Atrybutami reguły minimalnej są atrybuty
należące do minimalnego pokrycia M.

7

I

T
P

W

ZPT

Przykład generacji reguł

U a b c d e

1 1 0 0 1 1
2 1 0 0 0 1
3 0 0 0 0 0
4 1 1 0 1 0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2

Tablica decyzyjna

a b c d e

1 0 – – 1
0 – – – 0

– 1 – 1 0
– – – 2 2

Tablica reguł minimalnych

8

I

T
P

W

ZPT

Przykład: uogólniamy U

1

U a b c d e

1

1 0 0 1

1

2 1 0 0 0 1
3

0 0 0 0

0

4

1 1 0 1

0

5

1 1 0 2

2

6

2 2 0 2

2

7

2 2 2 2

2

Macierz M powstaje przez porównanie obiektów: (u

1

, u

3

),

(u

1

, u

4

),

..., (u

1

, u

7

). Wynikiem porównania są wiersze M.

Dla takich samych wartości atrybutów odpowiedni m=0,
dla różnych m=1.

1

1

1

1

1

0

1

1

1

0

1

0

0

0

1

0

1

0

0

1

d

c

b

a

M

9

I

T
P

W

ZPT

Przykład: uogólniamy U

1

Minimalne pokrycia są:

{a,b} oraz {b,d},

1

1

1

1

1

0

1

1

1

0

1

0

0

0

1

0

1

0

0

1

d

c

b

a

M

a, b, c, d

a, b, d

b, d

b

a, d

Wyznaczone na ich podstawie minimalne reguły:

(a,1) & (b,0)  (e,1)

(b,0) & (d,1)  (e,1)

U a b c d e
1

1 0 0 1

1

2 1 0 0 0 1

U a b c d e
1

1 0 - -

1

2 1 0 0 0 1

10

I

T
P

W

ZPT

Przykład generacji reguł cd.

U a b c d e
1

1 0 - -

1

2 1 0 0 0 1

Po uogólnieniu obiektu u

1



u

2

.

 

u

2

można usunąć

U

a

b

c

d

e

1

1

0

-

-

1

2

1

0

0

0

1

3

0

0

0

0

0

4

1

1

0

1

0

5

1

1

0

2

2

6

2

2

0

2

2

7

2

2

2

2

2

11

I

T
P

W

ZPT

Przykład generacji reguł c.d.

1

1

1

1

1

0

1

1

1

0

1

1

0

0

0

1

1

0

0

1

d

c

b

a

U a b c d e

1 1 0 0 1 1
2 1 0 0 0 1
3

0 0 0 0

0

4

1 1 0 1

0

5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2

(a,0)  (e,0)

(b,1) & (d,1)  (e,0)

1

1

1

1

1

0

1

1

1

0

0

0

1

0

1

0

0

0

1

0

d

c

b

a

Dla obiektu u3

Dla obiektu u4

1101

0







0000

1

1







Niestety po uogólnieniu ani u

3

nie pokrywa u

4

, ani u

4

nie pokrywa u

3

12

I

T
P

W

ZPT

Przykład generacji reguł c.d.

1

0

0

0

1

0

0

1

1

0

1

0

1

0

1

0

d

c

b

a

U a b c d e

1 1 0 0 1 1
2 1 0 0 0 1
3 0 0 0 0 0
4 1 1 0 1 0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2

(d,2)  (e,2)

Dla obiektu u5









2

u

6

, u

7

13

I

T
P

W

ZPT

Reguły minimalne

a b c d e
1 0 – – 1
0 – – – 0

– 1 – 1 0
– – – 2 2

(a,1) & (b,0)  (e,1)

(a,0)  (e,0)

(b,1) & (d,1)  (e,0)

(d,2)  (e,2)

(a,1) & (b,0)  (e,1)

(a,0)  (b,1) & (d,1)  (e,0)

(d,2)  (e,2)

w innym zapisie:

14

I

T
P

W

ZPT

Reguły minimalne

LERS

.i 7
.o 1
.type fr
.p 9
1000101 0
1011110 0
1101110 0
1110111 0
0100101 1
1000110 1
1010000 1
1010110 1
1110101 1
.e

< a a a a a a a d >
[ x1 x2 x3 x4 x5 x6 x7 d ]
1 0 0 0 1 0 1 0
1 0 1 1 1 1 0 0
1 1 0 1 1 1 0 0
1 1 1 0 1 1 1 0
0 1 0 0 1 0 1 1
1 0 0 0 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 1

ESPRESSO

6

2

7

4

x

x

x

x

f





(x4,1) -> (d,0)
(x7,1) & (x1,1) & (x3,0) -> (d,0)
(x2,1) & (x6,1) -> (d,0)
(x4,0) & (x2,0) & (x6,1) -> (d,1)
(x6,0) & (x2,1) -> (d,1)
(x5,0) -> (d,1)

5

2

6

6

2

4

x

x

x

x

x

x

f







15

I

T
P

W

ZPT

Redukcja atrybutów

a

1

a

2

a

3

a

4

a

5

a

6

d

1

0

1

0

1

0

0

1

2

1

0

0

0

1

3

2

3

1

1

0

2

2

3

3

4

1

1

0

2

3

3

2

5

1

1

1

0

2

3

4

6

0

0

2

0

2

3

1

7

1

1

2

0

2

2

5

8

1

1

2

0

2

3

6

9

1

0

2

2

1

3

6

10

1

1

2

2

3

1

7

a

1

a

3

a

5

a

6

d

1

0

0

0

0

1

2

1

0

1

3

2

3

1

0

2

3

3

4

1

0

3

3

2

5

1

1

2

3

4

6

0

2

2

3

1

7

1

2

2

2

5

8

1

2

2

3

6

9

1

2

1

3

6

10

1

2

3

1

7

Redukty: {a

1

, a

3

, a

5

, a

6

} {a

2

, a

3

, a

5

,

a

6

}

16

I

T
P

W

ZPT

Przykład redukcji atrybutów

3

3

1

2

3

2

0

0

1

0

a

4

2

2

0

0

2

0

0

1

0

0

a

5

1

1

2

2

1

7

4

0

0

1

0

9

3

1

1

0

0

8

4

0

2

2

2

10

2

0

2

2

1

6

3

1

0

1

0

5

2

1

1

1

0

4

2

1

2

2

1

3

1

0

1

0

0

2

1

0

0

0

0

1

d

a

6

a

3

a

2

a

1

{a

1

, a

4

, a

6

}

{a

1

, a

2

, a

3

, a

5

, a

6

}

(10)

;

(3)(7)

;

(6)

;

(4)(5,8)

;

(1,2)(9)

P

|

P

P

D

6

1





1,9

a

2

, a

4

, a

5

2,9

a

2

, a

3

, a

4

, a

5

4,5

a

3

, a

4

4,8

a

2

, a

4

3,7

a

4

, a

5

(a

4

+ a

2

) (a

4

+ a

3

) (a

4

+ a

5

) = a

4

+

a

2

a

3

a

5

17

I

T
P

W

ZPT

Dekompozycja tablic decyzyjnych

B

A

G

H

Decyzja

końcowa

Atrybuty

Tablica

decyzyjna

Decyzja

pośrednia

Atrybuty

18

I

T
P

W

ZPT

Dekompozycja tablic decyzyjnych

F = H(A,G(B))



G

 P(B):

P(A)





G

 P

D

B

A

G

H

Decyzja

końcowa

Decyzja

pośrednia

19

I

T
P

W

ZPT

Przykład dekompozycji TD

(10)

;

(3)(7)

;

(6)

;

(4)(5,8)

;

(1,2)(9)

P

|

P

D

U



3

3

1

2

3

2

0

0

1

0

a

4

2

2

0

0

2

0

0

1

0

0

a

5

1

1

2

2

1

7

4

0

0

1

0

9

3

1

1

0

0

8

4

0

2

2

2

10

2

0

2

2

1

6

3

1

0

1

0

5

2

1

1

1

0

4

2

1

2

2

1

3

1

0

1

0

0

2

1

0

0

0

0

1

d

a

6

a

3

a

2

a

1

A =

{a

4

, a

5

,

a

6

}

B =

{a

1

, a

2

,

a

3

}

)

8

;

6,9,10

;

5,7

;

4

;

3

;

2

;

1

(

P(A) 

)

10

;

5,9

;

4

;

3,6,7

;

2,8

;

1

(

P(B)



)

9,10

;

5,8

;

3,4,6

;

1,2,7

(

P

D



)

5,9,10

;

7,8

1,2,3,4,6,

(





G

20

I

T
P

W

ZPT

Przykład c.d.

F

a

1

a

2

a

3

g

1

0

0

0

1

2

0

0

1

1

3

1

2

2

1

4

0

1

1

1

5

0

1

0

2

6

2

2

2

2

a

4

a

5

a

6

g

d

1

0

0

0

1

1

2

1

0

0

1

1

3

0

1

1

1

2

4

0

0

1

1

2

5

2

0

1

2

3

6

3

2

0

1

2

7

2

0

1

1

1

8

1

0

1

1

3

9

3

2

0

2

4

G:

H:

21

I

T
P

W

ZPT

Kompresja danych

S

F

= 130 jednostek

S

G

= 42 jednostki

S

H

= 72 jednostki

S = pq

i

Dekompozycja

S

G

+ S

H

= 87% S

F

22

I

T
P

W

ZPT

Przykład

!, D e c is io n ta b le f o r h o u s e o f r e p s . !,

< D A A A A A A A A A A A A A A A A >

!,

[ C L A S S - N A M E H A N D I C A P P E D - I N F A N T S W A T E R - P R O J E C T - C O S T - S H A R I N G

A D O P T I O N - O F - T H E - B U D G E T - R E S O L U T I O N P H Y S I C I A N - F E E - F R E E Z E E L -

S A L V A D O R - A I D R E L I G I O U S - G R O U P S - I N - S C H O O L S A N T I - S A T E L L I T E - T E S T - B A N

A I D - T O - N I C A R A G U A N - C O N T R A S M X - M I S S I L E I M M I G R A T I O N

S Y N F U E L S - C O R P O R A T I O N - C U T B A C K E D U C A T I O N - S P E N D I N G S U P E R F U N D -

R I G H T - T O - S U E C R I M E D U T Y - F R E E - E X P O R T S E X P O R T - A D M I N I S T R A T I O N - A C T -

S O U T H - A F R I C A ]

!,

!, N o w th e d a ta

!,

d e m o c r a t

n y y n y y n n n n n n y y y y

r e p u b lic a n

n y n y y y n n n n n y y y n y

r e p u b lic a n

n n y y y y n n y y n y y y n y

d e m o c r a t

n n y n n n y y y y n n n n n y

. . . . . . . . . . . .

. . . . . . . . . . . .

68%

kompresji

danych

23

I

T
P

W

ZPT

24

I

T
P

W

ZPT

Przykład: zastosowanie dekompozycji w

nauczaniu sieci neuronowych

Przykłady

rd53 rd73 rd84 root s8 sao2 sqrt8 xor5 z4

Czas [s] 17

233 1200 1200 165 4004 470 432 108

Bez

dekompozycji Liczba

błędów

0

0

5

5

0

106

0

0

0

Czas [s] 9

29

53

661 26 586

52

67 56

Z

dekompozycją Liczba

błędów

0

0

0

0

0

0

0

0

0

25

I

T
P

W

ZPT

PODSUMOWANIE

Zagadnienia syntezy logicznej znajdują

szerokie zastosowanie w wielu dziedzinach
techniki:



w technice cyfrowej



w inżynierii informacji



w kryptografii



w sieciach neuronowych

Znaczenie syntezy logicznej ciągle
wzrasta, a USSL stają się niezbędnym
narzędziem w projektowaniu układów i
systemów cyfrowych

Uniwersyteckie Systemy Syntezy Logicznej:

SIS, (Espresso, NOVA, ...), ... DEMAIN