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