I

T
P

W

ZPT

1

Tablice

decyzyjne

I

T
P

W

ZPT

2

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

I

T
P

W

ZPT

3

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

I

T
P

W

ZPT

4

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

I

T
P

W

ZPT

5

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).

I

T
P

W

ZPT

6

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.

I

T
P

W

ZPT

7

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

I

T
P

W

ZPT

8

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

I

T
P

W

ZPT

9

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

I

T
P

W

ZPT

10

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

I

T
P

W

ZPT

11

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

I

T
P

W

ZPT

12

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

I

T
P

W

ZPT

13

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:

I

T
P

W

ZPT

14

Zastosowania

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

Pierwotna tablica decyzyjna

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

– 1 – 1 0
– – – 2 2

Tablica reguł minimalnych

Takie metody stosuje się w przypadkach, gdy dysponuje się zbiorem
obiektów, których przynależność do odpowiedniej klasy jest znana,
a celem jest identyfikacja nieznanych reguł klasyfikacji.

a=1,b=1, c=1, d=
1

Jaka decyzja?

Decyzja
e=0

I

T
P

W

ZPT

15

Sytuacja ta występuje np. przy wnioskach kredytowych składanych w bankach.
Ponieważ część z nich jest akceptowana, a część odrzucana, można dane
zebrane w dłuższym okresie czasu zapisać w tablicy decyzyjnej,
uogólnić i dalej stosować w uproszczonej formie do podejmowania decyzji.

Klientów charakteryzuje się za pomocą następujących cech
jakościowych i ilościowych:

- Sytuacja zawodowa: B (bezrobotny), P (pracujący)
- przeznaczenie kredytu: komputer (K), sprzęt audio (A), biżuteria (B)…
- wiek w latach
- stan konta

Zastosowania

Przykładowo:

I

T
P

W

ZPT

Przykładowa tablica danych...

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10 Klasa

P

K

K

S

nie

18

200

20

15

1

tak

P

K

K

S

nie

20

100

20

20

2

tak

B

K

K

R

tak

25

50

40

12

0

nie

•

•

•

P

S

M

R

nie

21

150

0

30

20

3

tak

P

S

M

S

nie

25

150

0

100

20

2

tak

P

S

M

R

nie

38

100

0

100

20

15

tak

16

Przeznaczenie:
Komp., sam.

wiek

Stan konta

Staż pracy w danym
zakładzie pracy

Sytuacja
zawodowa

I

T
P

W

ZPT

17

Zastosowania

[wiek > 25] & [stan konta > 70] & [staż pracy >
2]

 tak

[płeć = kobieta] & [wiek < 25]

 nie

…….

Po uogólnieniu reguł decyzyjnych…

LERS

I

T
P

W

ZPT

18

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







I

T
P

W

ZPT

19

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

}

I

T
P

W

ZPT

20

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

1
0

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

ponieważ wiersze 6 i 10
różnią się na pozycji a

1

a

1

a

6

a wiersze 2 i 8
różnią się na
pozycji a

6

I

T
P

W

ZPT

21

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

1
0

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

10)

;

3,6,7

;

,9

(1,2,4,5,8

P

1



3,4,5,7,8)

;

0

(1,2,6,9,1

P

6



9,10)

;

5,8

;

3,4,6

;

(1,2,7

P

D



(10)

;

(3)(7)

;

(6)

;

(4)(5,8)

;

(1,2)(9)

P

|

P

P

D

6

1





I

T
P

W

ZPT

22

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

1
0

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

2

, a

4

, a

5

(10)

;

(3)(7)

;

(6)

;

(4)(5,8)

;

(1,2)(9)

P

|

P

P

D

6

1





1,9
2,9
4,5
4,8
3,7

(a

4

+ a

2

) (a

4

+ a

3

) (a

4

+ a

5

) = a

4

+

a

2

a

3

a

5

a

2

, a

3

, a

4

,

a

5

a

3

, a

4

a

2

, a

4

a

4

, a

5

{a

1

, a

4

, a

6

}

{a

1

, a

2

, a

3

, a

5

, a

6

}

I

T
P

W

ZPT

23

Dekompozycja tablic decyzyjnych

B

A

G

H

Decyzja

końcowa

Atrybuty

Tablica

decyzyjna

Decyzja

pośrednia

Atrybuty

I

T
P

W

ZPT

24

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

I

T
P

W

ZPT

25

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

1
0

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

I

T
P

W

ZPT

26

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:

I

T
P

W

ZPT

27

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

I

T
P

W

ZPT

28

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

I

T
P

W

ZPT

29

I

T
P

W

ZPT

30

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

I

T
P

W

ZPT

31

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