1
I
T
P
W
ZPT
I
T
P
W
ZPT
Minimalizacja funkcji boolowskich
Zagadnienie intensywnych prac badawczych od
początku lat pięćdziesiątych 20 wieku.
Ogromny wzrost zainteresowania
minimalizacją f.b. powstał ponownie w
latach 80.
Przyczyna: możliwość realizacji układów
logicznych w strukturach scalonych o złożoności
milionów bramek logicznych.
2
I
T
P
W
ZPT
I
T
P
W
ZPT
Metody minimalizacji funkcji
boolowskich
Graficzne
Analityczne
Komputerowe
Pierwsze skuteczne narzędzie do minimalizacji
wieloargumentowych i wielowyjściowych funkcji boolowskich
(Uniwersytet Kalifornijski
w Berkeley) :
Metoda i system Espresso (1984)
Absolutnie nieprzydatne
do obliczeń
komputerowych
Tablice Karnaugha
Metoda
Quine’a
–
McCluskey’a
Ze względu na ograniczony zakres wykładu omówimy
wyłącznie:
Metodę tablic Karnaugha
Metodę Ekspansji (przykładową procedurę Espresso)
Omówienie
całego
Espresso
jest
nierealne!
3
I
T
P
W
ZPT
I
T
P
W
ZPT
Metoda tablic Karnaugha
Tablica K. jest prostokątem złożonym z 2
n
kratek, z
których każda reprezentuje jeden pełny iloczyn
(minterm) zmiennych binarnych.
x
3
x
1
x
2
0
1
00
01
11
10
W tablicy K. różniącym się tylko o
negację pełnym iloczynom
przyporządkowane są leżące obok
siebie pola tablicy (sąsiednie kratki).
Korzysta się z faktu, że dla
dowolnego A:
A
Ax
x
A
-
1
1
1
0
0
0
0
3
2
1
x
x
x
3
2
1
x
x
x
W kratki wpisuje się wartości
funkcji.
2
1
x
x
Dla uzyskania efektu
sąsiedztwa
współrzędne pól
opisuje się kodem
Gray’a
4
I
T
P
W
ZPT
I
T
P
W
ZPT
Kod Gray’a
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
5
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykładzik
x
1
x
2
x
3
f
0 0
0
0
0
1 0
0
1
1
2 0
1
0
0
3 0
1
1
1
4 1
0
0
0
5 1
0
1
1
6 1
1
0
1
7 1
1
1
1
1) Wpisanie funkcji do
tablicy
x
3
x
1
x
2
0
1
00
01
11
10
f = x
1
x
2
x
3
+
2) Zakreślanie
pętelek
0
1
0
1
1
1
0
1
Z pętelkami kojarzymy iloczyn zmiennych
(prostych lub zanegowanych)
6
I
T
P
W
ZPT
I
T
P
W
ZPT
Wpisywanie funkcji ułatwia…
x
4
x
5
x
1
x
2
x
3
0
0 01 11 10
000
0
1
3
2
001
4
5
7
6
011
1
2 13 15 14
010
8
9
11 10
110
2
4 25 27 26
111
2
8
29 31 30
101
2
0
21 23 22
100
1
6
17 19 18
x
3
x
4
x
1
x
2
0
0
01 11 10
00
0
1
3
2
01
4
5
7
6
11
1
2
13 15 14
10
8
9
11 10
x
3
x
1
x
2
0
1
00
0
1
01
2
3
11
6
7
10
4
5
x
2
x
3
x
1
0
0 01 11 10
0
0
1
3
2
1
4
5
7
6
…opis kratek tablic Karnaugha wg NKB
1
n
0
j
j
j
NKB
D
2
a
A
L
A
7
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykładzik
x
1
x
2
x
3
f
0
0
0
0
0
1
0
0
1
1
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
Wpisanie funkcji do tablicy
Zakreślanie pętelek i kojarzenie z nimi
odpowiednich iloczynów jest trudniejsze
x
3
x
1
x
2
0
1
00
0
1
01
2
3
11
6
7
10
4
5
x
3
x
1
x
2
0
1
00
01
11
10
0
1
0
1
1
1
0
1
8
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykład
x
3
x
1
x
2
0
1
00
0
0
01
1
0
11
1
1
10
1
0
1
1
0
0
x
1
0
1
0
0
1
1
0
x
1
1
1
1
1
0
0
0
x
3
x
2
1
x
1
1
0
0
x
1
0
1
0
0
1
1
0
x
2
1
1
1
1
0
0
0
x
3
x
2
2
x
2
x
x
3
1
1
0
0
x
1
0
1
0
0
1
1
0
1
1
1
1
0
0
0
x
3
x
2
3
x
x
1
x
3
x
2
0
1
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
0
3
1
x
x
2
1
x
x
3
2
x
x
f
9
I
T
P
W
ZPT
I
T
P
W
ZPT
Algorytm minimalizacji
1) Zapisujemy funkcję do tablicy K.
2) Zakreślamy pętelki.
a) Pętelki zakreślamy wokół grup sąsiadujących
kratek zawierających 1-ki albo 1-ki i „–” (kreski).
b) Liczba kratek objętych pętelka musi wynosić: 1, 2,
4, …,2
k
.
c) Staramy się objąć pętelką jak największą liczbę
kratek.
3) Pętelki zakreślamy tak długo, aż każda 1-ka będzie
objęta co najmniej jedną pętelką, pamiętając o tym aby
pokryć wszystkie
1-ki możliwie minimalną liczbą pętelek.
4) Z każdą pętelką kojarzymy iloczyn zmiennych prostych
lub zanegowanych. Suma tych iloczynów, to minimalne
wyrażenie boolowskie danej funkcji.
10
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykłady pętelek
x
4
x
5
x
1
x
2
x
3
0
0 01 11 10
000
001
011
010
110
111
101
100
x
3
x
4
x
1
x
2
0
0 01 11 10
00
01
11
10
x
3
x
1
x
2
0
1
00
01
11
10
x
2
x
3
x
1
0
0 01 11 10
0
1
11
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykład - minimalizacja dla KPS
f = 0, 5, 6, 7, 10, (2, 3, 11, 12)
x
3
x
4
x
1
x
2
0
0
01 11 10
00
1
0
–
–
01
0
1
1
1
11
–
0
0
0
10
0
0
–
1
3
1
x
x
3
2
x
x
x
x
x
4
2
1
4
2
1
x
x
x
f
x
3
x
4
x
1
x
2
0
0
01 11 10
00
0
1
3
2
01
4
5
7
6
11
1
2
13 15 14
10
8
9
11 10
12
I
T
P
W
ZPT
I
T
P
W
ZPT
0
e
gdy
,
x
1
e
gdy
x,
x
e
Wszystkie czynności są takie same
Różnice wynikają ze sposobu interpretacji
zmiennej w…
1
e
gdy
,
x
0
e
gdy
x,
x
e
Kanonicznej
Postaci
Sumy:
Kanonicznej Postaci
Iloczynu:
…czyli… (tu jest komentarz tylko dla tych co
chodzą na wykłady)
Przykład - minimalizacja dla KPI
13
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykład
f = 0, 5, 6, 7, 10, (2, 3, 11, 12)
x
3
x
4
x
1
x
2
0
0 01 11 10
00
1
0
–
–
01
0
1
1
1
11
–
0
0
0
10
0
0
–
1
)
3
1
x
x
(
f
)
(
2
1
x
x
)
x
x
4
2
(
)
4
3
2
x
x
x
(
14
I
T
P
W
ZPT
I
T
P
W
ZPT
Implikant funkcji boolowskiej
Implikant
danej funkcji f jest to iloczyn
literałów (zmiennych prostych i
zanegowanych) o następującej własności:
dla wszystkich kombinacji wartości
zmiennych, dla których implikant jest
równy jedności, również funkcja f jest
równa jedności.
Implikan
t
Prosty implikant
jest to implikant,
który
zmniejszony o dowolny literał przestaje
być implikantem.
Prosty implikant
15
I
T
P
W
ZPT
I
T
P
W
ZPT
Implikant funkcji boolowskiej
x
3
x
4
x
1
x
2
0
0 01 11 10
00
1
0
–
–
01
0
1
1
1
11
–
0
0
0
10
0
0
–
1
To nie jest
Implikant!
Implikant
4
3
1
x
x
x
Prosty
implikant
3
1
x
x
W interpretacji tablic Karnaugha implikant odpowiada
prawidłowo zakreślonej grupie jedynek (i kresek).
Natomiast implikant prosty odpowiada grupie jedynek
(i kresek), której nie można powiększyć.
16
I
T
P
W
ZPT
I
T
P
W
ZPT
Realizacje bramkowe
3
2
3
1
2
1
x
x
x
x
x
x
y
Realizacja AND-OR (wg sumy
iloczynów)
Realizacja OR-AND (wg iloczynu
sum)
)
)(
)(
3
2
3
1
2
1
x
x
x
x
x
(x
y
17
I
T
P
W
ZPT
I
T
P
W
ZPT
Realizacja AND-OR
x
3
x
1
x
2
0
1
00
0
0
01
1
0
11
1
1
10
1
0
3
2
3
1
2
1
x
x
x
x
x
x
y
x
x
1
2
x
x
1
3
x
x
2
3
y
3
2
3
1
2
1
x
x
x
x
x
x
y
3
2
3
1
2
1
x
x
x
x
x
x
y
Sum-of-products (SOP)
18
I
T
P
W
ZPT
I
T
P
W
ZPT
Realizacja OR-AND
x
3
x
1
x
2
0
1
00
0
0
01
1
0
11
1
1
10
1
0
)
)(
)
3
2
3
1
2
1
x
x
x
(x
x
(x
y
x
x
1
2
x
x
1
3
x
x
2
3
y
Product-of-sums (POS)
19
I
T
P
W
ZPT
I
T
P
W
ZPT
Inne operatory (bramki) logiczne
b
a
y
NAND
(NOT-AND)
b
a
y
EX-OR
NAND
NOR
NOR (NOT-OR)
EXOR (Exclusive
OR)
b
a
b
a
b
a
y
20
I
T
P
W
ZPT
I
T
P
W
ZPT
Inne realizacje bramkowe
Realizacja
NAND
Realizacja NOR
3
2
3
1
2
1
x
x
x
x
x
x
y
21
I
T
P
W
ZPT
I
T
P
W
ZPT
Realizacja NAND
x
3
x
1
x
2
0
1
00
0
0
01
1
0
11
1
1
10
1
0
3
2
3
1
2
1
x
x
x
x
x
x
y
3
2
3
1
2
1
x
x
x
x
x
x
y
y
x
x 12
x
x 13
x
x 2
3
x
x
12x
x
1
3x
x
23
y
x
x
1
3
x
x
2
3
x
x
1
2
y
22
I
T
P
W
ZPT
I
T
P
W
ZPT
Realizacja NOR
x
3
x
1
x
2
0
1
00
0
0
01
1
0
11
1
1
10
1
0
)
)(
)(
3
2
3
1
2
1
x
x
x
x
x
(x
y
3
2
3
1
2
1
x
x
x
x
x
x
y
x
x
1
2
3
x
x
1
x
x
2
3
y
23
I
T
P
W
ZPT
I
T
P
W
ZPT
Minimalizacja funkcji
wielowyjściowych
Należy zaprojektować zespół trzech
funkcji czterech argumentów:
f
1
= (3,7,11,14,15)
f
2
= (3,7,12,13,14,15)
f
3
= (3,7,11,12,13,15)
Przykład sygnalizujący problem:
24
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykład sygnalizujący problem…
cd
ab
00 01 11 10
cd
ab
00 01 11 10
cd
ab
00 01 11 10
f
1
= abc + cd
0 0 1 0
0 0 1 0
0 0 1 1
0 0 1 0
0 0 1 0
0 0 1 0
1 1 1 1
0 0 0 0
0 0 1 0
0 0 1 0
1 1 1 0
0 0 1 0
00
01
11
10
00
01
11
10
00
01
11
10
cd
a
ab
f
2
cd
c
ab
f
3
Jeśli każdą funkcję zminimalizujemy
oddzielnie:
25
I
T
P
W
ZPT
I
T
P
W
ZPT
f
1
f
2
f
3
… to uzyskamy…
Do realizacji tych
trzech funkcji
potrzebujemy
9
bramek.
Czy
można
zredukować ich
liczbę?
Patrz następna
plansza .
a
b
c
c
d
a
b
c
d
a
b
c
d
a
c
26
I
T
P
W
ZPT
I
T
P
W
ZPT
Bramka AND dla f
1
może być
usunięta przez
wykorzystanie
bramki AND z f
3
.
f
1
f
2
f
3
a
b
c
c
d
a
b
c
d
a
b
c
d
a
c
…usuwamy niektóre bramki
Teraz
potrzebujemy 8
bramek.
…….cdn.
27
I
T
P
W
ZPT
I
T
P
W
ZPT
Bramkę AND z f
2
można usunąć
przez
wykorzystanie
faktu
f
1
f
2
f
3
a
b
c
c
d
a
b
c
d
a
b
c
d
a
c
c
ab
abc
ab
…co dalej
Teraz
potrzebujemy
zaledwie 7
bramek.
28
I
T
P
W
ZPT
I
T
P
W
ZPT
Komentarz
Przykład sugeruje, że w realizacji
zespołu funkcji stosowanie
minimalnej sumy implikantów
prostych nie zawsze prowadzi do
rozwiązania z minimalnym
kosztem.
29
I
T
P
W
ZPT
I
T
P
W
ZPT
Przykład 3.5 z książki SUL
1
1
10
1
1
11
1
1
1
01
1
1
00
1
0
1
1
0
1
00
cd
ab
1
1
10
1
1
1
11
1
1
01
00
1
0
1
1
0
1
00
cd
ab
1
1
1
1
10
1
1
11
1
1
01
1
1
00
1
0
1
1
0
1
00
cd
ab
c
b
bd
b
a
y
1
bd
a
c
y
2
c
b
a
d
c
a
bc
y
3
y
1
=
(2,3,5,7,8,9,10,11,13,15)
y
2
=
(2,3,5,6,7,10,11,14,15)
y
3
=
(6,7,8,9,13,14,15)
7 bramek AND
cd
ab
00
01
11
10
00
0
1
3
2
01
4
5
7
6
11
12
13
15
14
10
8
9
11
10
30
I
T
P
W
ZPT
I
T
P
W
ZPT
cd
ab
00
0
1
1
1
1
0
00
1
1
01
1
1
11
1
1
10
1
1
1
1
cd
ab
00
0
1
1
1
1
0
00
1
1
01
1
1
1
11
1
1
10
1
1
cd
ab
00
0
1
1
1
1
0
00
01
1
1
11
1
1
1
10
1
1
1
2
3
4
1
2
5
3
5
4
c
b
y
1
bd
a
abd
c
b
a
bc
c
b
y
2
bd
a
abd
3
y
bc
c
b
a
5 bramek AND
… a poprzednio
było 7 bramek
AND!!!
Przykład 3.5 z książki SUL