ULOG10 u MKZ, Studia WIT - Informatyka, PUL - Podstawy układów logicznych

[ Pobierz całość w formacie PDF ]
Jak usprawnić obliczanie MKZ?
Znamy metodę wg par sprzecznych oraz metodę
bezpośrednią
W celu sprawniejszego obliczania MKZ
wprowadzimy skuteczniejszą metodę wg par
zgodnych
I
T
P
W
ZPT
1
Algorytm MKZ wg par zgodnych
E – relacja zgodności (e
i
,e
j
)
∈
E
R
j
= { e
i
| i < j oraz (e
i
,e
j
)
∈
E}
RKZ
k
RKZ
k+1
KZ
∈
RKZ
k
a) R
k+1
=
, RKZ
k+1
jest powiększana o klasę KZ = {k+1}
b) KZ
∩
R
k+1
=
φ
, KZ bez zmian
c) KZ
∩
R
k+1
≠φ
, KZ’ = KZ
∩
R
k+1
∪
{k+1}
I
T
P
W
ZPT
2
φ
Przykład
R
j
= { e
i
| i < j oraz (e
i
,e
j
)
∈
E}
E:
1,2
1,3
1,5
2,3
2,4
2,5
3,5
3,6
4,6
R
1
=
φ
R
2
=
1
R
3
=
1,2
R
4
=
2
R
5
=
1,2,3
R
6
=
3,4
I
T
P
W
ZPT
3
Przykład c.d.
a) R
k+1
=
φ
, RKZ
k+1
jest powiększana o klasę KZ = {k+1}
b) KZ
∩
R
k+1
=
φ
, KZ bez zmian
c) KZ
∩
R
k+1
≠φ
, KZ’ = KZ
∩
R
k+1
∪
{k+1}
R
1
=
φ
{1}
R
2
= 1
{1,2}
R
3
= 1,2
{1,2,3}
R
4
= 2
{2,4},
{1,2,3}
I
T
P
W
R
5
= 1,2,3
{2,5},
{1,2,3,5}, {2,4}
Rodzina MKZ
R
6
= 3,4
{3,6},
{4,6},
{1,2,3,5}, {2,4}
ZPT
4
Algorytm MKZ wg par sprzecznych
Zapisać pary sprzeczne w postaci koniunkcji dwuskładnikowych sum
Koniunkcję dwuskładnikowych sum przekształcić do minimalnego
wyrażenia boolowskiego typu suma iloczynów
Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez
składniki iloczynowe tego wyrażenia
I
T
P
W
ZPT
5
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •