1.6 Minimalizacja za pomocą tablic Karnaugh’a

Przykładowe sklejenia (pary):

x

1

x

2

\x

3

x

4

00 01 11 10

00

x

01

x

1

x

11

x

10

Na przykład można sklejać:

x

1

x

2

\x

3

x

4

00 01 11 10

00
01

1

1

11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00

–

01

1

11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00

x

01

1

x

x

11

x

10

Na przykład można sklejać:

x

1

x

2

\x

3

x

4

00 01 11 10

00
01

1

1

1

11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01

1

1

11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00

1

x

x

01

x

11
10

x

Na przykład można sklejać:

x

1

x

2

\x

3

x

4

00 01 11 10

00

1

1

01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00

1

1

01
11
10

Przykładowe sklejenia (czwórki):

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

Przykładowe sklejenia (ósemki):

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

x

1

x

2

\x

3

x

4

00 01 11 10

00
01
11
10

Przykładowe sklejenia (pary):

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00

x

01

x

1

x

x

11

x

10

Na przykład można sklejać:

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01

1

1

x

11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01

1

1

11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00

x

01

1

x

x

11

x

10

Na przykład można sklejać:

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00

1

01

1

11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01

1

1

11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00

1

x

x

x

01

x

11
10

x

Przykładowe sklejenia (czwórki):

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01
11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01
11
10

x

3

x

4

x

5

x

1

x

2

000 001 011 010 110 111 101 100

00
01
11
10

Przykład:
Zminimalizować funkcję y =

Σ (1, 3, 8, (0, 2, 6, 9, 11, 15))

x

1

x

2

x

3

x

4

y

1

0

0

0

0

0

–

1

0

0

0

1

1

2

0

0

1

0

–

3

0

0

1

1

1

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

–

7

0

1

1

1

0

8

1

0

0

0

1

9

1

0

0

1

–

10 1

0

1

0

0

11 1

0

1

1

–

12 1

1

0

0

0

13 1

1

0

1

0

14 1

1

1

0

0

15 1

1

1

1

–

x

1

x

2

\x

3

x

4

00 01 11 10

00

–

1

1

–

01

0

0

0

–

11

0

0

–

0

10

1

–

–

0

y = x

1

x

2

+ x

2

x

3

Przykład:
Zminimalizować funkcję y =

Σ (1, 4, 8, 10, 15 (0, 2, 5, 6, 9))

x

1

x

2

x

3

x

4

y

0

0

0

0

0

–

1

0

0

0

1

1

2

0

0

1

0

–

3

0

0

1

1

0

4

0

1

0

0

1

5

0

1

0

1

–

6

0

1

1

0

–

7

0

1

1

1

0

8

1

0

0

0

1

9

1

0

0

1

–

10 1

0

1

0

1

11 1

0

1

1

0

12 1

1

0

0

0

13 1

1

0

1

0

14 1

1

1

0

0

15 1

1

1

1

1

x

3

x

4

x

1

x

2

00 01 11 10

00

–

1

0

–

01

1

–

0

–

11

0

0

1

0

10

1

–

0

1

y = x

1

x

3

+ x

2

x

4

+ x

1

x

2

x

3

x

4

Zminimalizować funkcję y =

∏(3, 5, 7, 8, 9,12, 13 18, 20, 22, 24, 28,(1, 2, 10, 14, 15, 16, 17,

21, 30, 31))

x

1

x

2

x

3

x

4

x

5

y

0

0

0

0

0

0

1

1

0

0

0

0

1

-

2

0

0

0

1

0

-

3

0

0

0

1

1

0

4

0

0

1

0

0

1

5

0

0

1

0

1

0

6

0

0

1

1

0

1

7

0

0

1

1

1

0

8

0

1

0

0

0

0

9

0

1

0

0

1

0

10 0

1

0

1

0

-

11 0

1

0

1

1

1

12 0

1

1

0

0

0

13 0

1

1

0

1

0

14 0

1

1

1

0

-

15 0

1

1

1

1

-

16 1

0

0

0

0

-

17 1

0

0

0

1

-

18 1

0

0

1

0

0

19 1

0

0

1

1

1

20 1

0

1

0

0

0

21 1

0

1

0

1

-

22 1

0

1

1

0

0

23 1

0

1

1

1

1

24 1

1

0

0

0

0

25 1

1

0

0

1

1

26 1

1

0

1

0

1

27 1

1

0

1

1

1

28 1

1

1

0

0

0

29 1

1

1

0

1

1

30 1

1

1

1

0

-

31 1

1

1

1

1

-

x

1

x

2

\x

3

x

4

x

5

000 001 011 010 110 111 101 100

00

1

-

0

-

1

0

0

1

01

0

0

1

-

-

-

0

0

11

0

1

1

1

-

-

1

0

10

-

-

1

0

0

1

-

0

y = x

2

x

3

+ x

1

x

5

+ x

1

x

2

x

5

Przykład: opis dekodera wskaźnika siedmiosegmentowego powszechnie stosowanego do
wyświetlania cyfr w urządzeniach pomiarowych i monitorujących. Dekoder taki to układ
kombinacyjny o wejściach x

3

, x

2

, x

1

, x

0

oraz wyjściach a, b, c,..., g , odpowiadającym

segmentom wskaźnika. Na wejścia d podawane są liczby binarne 0000, 0001,..., 1000, 1001
(dziesiętnie: 0,1,...,8,9). Wyjścia a, b, c, ..., g sterują diodami świecącymi. Dioda zostaje
podświetlona, gdy odpowiednie wyjście jest w stanie 1. W rezultacie działanie dekodera jest
opisane tablicą prawdy.

Dekoder (a) wskaźnika siedmiosegmentowego (b)

a

b

c

d

e

f

g

d
d
d
d

3

2

1

0

Dekoder

a
b
c
d

e
f
g

a)

b)

Tablica prawdy

x

3

x

2

x

1

x

0

a b c d e f

g

0

0 0

0

0

1 1 1 1 1 1 0

1

0 0

0

1

0 1 1 0 0 0 0

2

0 0

1

0

1 1 0 1 1 0 1

3

0 0

1

1

1 1 1 1 0 0 1

4

0 1

0

0

0 1 1 0 0 1 1

5

0 1

0

1

1 0 1 1 0 1 1

6

0 1

1

0

1 0 1 1 1 1 1

7

0 1

1

1

1 1 1 0 0 0 0

8

1 0

0

0

1 1 1 1 1 1 1

9

1 0

0

1

1 1 1 1 0 1 1

10 1 0

1

0

– – – – – – –

11 1 0

1

1

– – – – – – –

12 1 1

0

0

– – – – – – –

13 1 1

0

1

– – – – – – –

14 1 1

1

0

– – – – – – –

15 1 1

1

1

– – – – – – –

Minimalna postać funkcji e:

x

3

x

4

x

1

x

2

00 01 11 10

00

1

0

0

1

01

0

0

0

1

11

–

–

–

–

10

1

0

–

–

y = x

3

x

4

+ x

2

x

4