Tablice
Tablice
Tablice
Tablice
Tablice
Tablice
K n
h
K n
h
Tablice
Tablice
K n
h
K n
h
Karnaugh
Karnaugh
Karnaugh
Karnaugh
6 marca 2011
Tablice Karnaugh
2
Tablice
Tablice
Tablice
Tablice
Tablice
Tablice
K n
h
K n
h
Tablice
Tablice
K n
h
K n
h
Karnaugh
Karnaugh
Karnaugh
Karnaugh
6 marca 2011
Tablice Karnaugh
2
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Tablice Karnaugh są graficzną reprezentacją tablic prawdy.
Tablice Karnaugh są graficzną reprezentacją tablic prawdy.
Każda kratka reprezentuje jeden minterm
Każda kratka reprezentuje jeden minterm
00
11
00
00
00
FF
xx
00
xx
11
xx
22
10
10
11
11
01
01
00
00
xx
22
xx
11
xx
00
00
11
00
00
00
11
11
11
00
00
22
00
00
11
00
m
m
00
m
m
11
00
44
11
66
00
22
11
00
00
xx
00
22
00
00
11
00
44
00
00
00
11
33
00
11
11
00
m
m
22
m
m
33
m
m
11
55
11
77
00
33
11
11
11
55
11
11
00
11
66
11
00
11
11
44
00
00
00
11
m
m
44
m
m
55
m
m
66
h
h
6 marca 2011
Tablice Karnaugh
3
77
11
11
11
11
m
m
66
m
m
77
Karnaugh Map
Karnaugh Map
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Każde dwa sąsiednie pola różnią się między sobą tylko
Każde dwa sąsiednie pola różnią się między sobą tylko
jednym bitem. Dotyczy to również pól skrajnych
jednym bitem. Dotyczy to również pól skrajnych
(ostatnie pole
(ostatnie pole
j
ym
m. D y y
w
p
j y
j
ym
m. D y y
w
p
j y
(
p
(
p
różni się tylko jednym bitem od pierwszego pola w szeregu).
różni się tylko jednym bitem od pierwszego pola w szeregu).
10
10
11
11
01
01
00
00
xx
22
xx
11
00
44
11
66
00
22
11
00
00
10
10
11
11
01
01
00
00
22 11
xx
00
11
55
11
77
00
33
11
11
11
00
44
11
66
00
22
11
00
00
6 marca 2011
Tablice Karnaugh
4
55
77
33
11
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Suma dwóch sąsiednich mintermów o tej samej wartości
Suma dwóch sąsiednich mintermów o tej samej wartości
logicznej może być uproszczona do jednego iloczynu
logicznej może być uproszczona do jednego iloczynu
xx
22
xx
11
logicznego, w którym wyeliminowana zostaje jedna
logicznego, w którym wyeliminowana zostaje jedna
zmienna.
zmienna.
00
44
11
66
00
22
11
00
00
10
10
11
11
01
01
00
00
xx
22
xx
11
xx
00
11
55
11
77
00
33
11
11
11
00
44
11
66
00
22
11
00
00
Biorąc mintermy z pierwszej kolumny otrzymamy zależność:
Biorąc mintermy z pierwszej kolumny otrzymamy zależność:
xx
22
’x
’x
11
’x
’x
00
’ +
’ + xx
22
’x
’x
11
’x
’x
00
== xx
22
’x
’x
11
’(x
’(x
00
’ +
’ + xx
00
) = x
) = x
22
’x
’x
11
’’
6 marca 2011
Tablice Karnaugh
5
22 11 00
22 11 00
22 11
((
00
00
))
22 11
Upraszczając wyrażenie można wyeliminować zmienną x
Upraszczając wyrażenie można wyeliminować zmienną x
00
..
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Aby uprościć funkcję logiczną wykorzystując tablice Karnaugh,
Aby uprościć funkcję logiczną wykorzystując tablice Karnaugh,
należy pogrupować sąsiednie kratki zawierające wartości
należy pogrupować sąsiednie kratki zawierające wartości
logiczne 1
logiczne 1
10
10
11
11
01
01
00
00
xx
22
xx
11
logiczne 1.
logiczne 1.
Zadajemy sobie pytanie: Kiedy funkcja logiczna ma wartość 1?
Zadajemy sobie pytanie: Kiedy funkcja logiczna ma wartość 1?
00
11
00
11
00
10
10
11
11
01
01
00
00
xx
00
11
55
11
77
00
33
11
11
11
00
44
11
66
00
22
11
00
00
xx
22
xx
00
55
77
33
11
xx
22
’x
’x
11
’’
xx
22
xx
11
xx
22
xx
00
6 marca 2011
Tablice Karnaugh
6
22 11
22 11
F = x
F = x
11
’x
’x
22
’ + x
’ + x
11
xx
22
+ x
+ x
00
xx
22
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Można też zadać pytanie:
Można też zadać pytanie:
Kiedy funkcja logiczna ma wartość 0?
Kiedy funkcja logiczna ma wartość 0?
10
10
11
11
01
01
00
00
xx
22
xx
11
00
44
11
66
00
22
11
00
00
xx
00
11
55
11
77
00
33
11
11
11
xx
22
+
+ xx
11
’’ xx
00
+ x
+ x
11
+ x
+ x
22
’’
F =
F =
(x
(x +
+ xx’’ ) ) (x
(x + x
+ x + x
+ x ’)’)
6 marca 2011
Tablice Karnaugh
7
F =
F =
(x
(x
22
+
+ xx
11
) ) ⋅⋅ (x
(x
00
+ x
+ x
11
+ x
+ x
22
))
Zasady upraszczania tablic Karnaugh
Zasady upraszczania tablic Karnaugh
Zasady upraszczania tablic Karnaugh
Zasady upraszczania tablic Karnaugh
•• Grupujemy sąsiednie kwadraty zawierające 1 (0)
Grupujemy sąsiednie kwadraty zawierające 1 (0)..
•• Ilość zgrupowanych kwadratów musi być potęgą liczby dwa
Ilość zgrupowanych kwadratów musi być potęgą liczby dwa
np. 1, 2, 4, 8
np. 1, 2, 4, 8..
•• Staramy się grupować jak największą liczbą kwadratów
Staramy się grupować jak największą liczbą kwadratów..
•• W pierwszej kolejności grupujemy kwadraty, które mogą
W pierwszej kolejności grupujemy kwadraty, które mogą
znajdować się tylko w jednym kwadracie
znajdować się tylko w jednym kwadracie
•• Każda jedynka może być grupowana wielokrotnie
Każda jedynka może być grupowana wielokrotnie
l k
d k
l k
d k
6 marca 2011
Tablice Karnaugh
8
•• Jeżeli wszystkie jedynki zostały zgrupowane
Jeżeli wszystkie jedynki zostały zgrupowane –– uproszczenie
uproszczenie
tablicy jest zakończone
tablicy jest zakończone
Tablice
Tablice Karnaugh
Karnaugh
Tablice
Tablice Karnaugh
Karnaugh
Liczba wyeliminowanych zmiennych w zależności od
Liczba wyeliminowanych zmiennych w zależności od
rozmiaru zaznaczonej grupy
rozmiaru zaznaczonej grupy
Tablica z 3 zmiennymi
Tablica z 3 zmiennymi
j g py
j g py
Ilość kwadratów w
Ilość kwadratów w
grupie
grupie
Liczba
Liczba
wyeliminowanych
wyeliminowanych
zmiennych
zmiennych
11
00
11
00
22
11
44
22
88
33
6 marca 2011
Tablice Karnaugh
9
Grupowanie kwadratów
Grupowanie kwadratów
Grupowanie kwadratów
Grupowanie kwadratów
xx
33
xx
22
xx
33
xx
22
xx
11
xx
00
00
00
01
01
11
11
10
10
00
00
00
00
01
01
01
01
11
11
10
10
6 marca 2011
Tablice Karnaugh
10
Grupowanie kwadratów
Grupowanie kwadratów
Grupowanie kwadratów
Grupowanie kwadratów
xx
33
xx
22
xx
33
xx
22
xx
11
xx
00
00
00
01
01
11
11
10
10
00
00
00
00
01
01
01
01
11
11
10
10
6 marca 2011
Tablice Karnaugh
11
Tablica Karnaugh z funkcji kanonicznej
Tablica Karnaugh z funkcji kanonicznej
Tablica Karnaugh z funkcji kanonicznej
Tablica Karnaugh z funkcji kanonicznej
Przykład uproszczenia wyrażenia przedstawionego w postaci
Przykład uproszczenia wyrażenia przedstawionego w postaci
kanonicznej
kanonicznej
(
)
(
)
FF= Σ
= Σ
(1,3,6,9,11,12,13,14)
(1,3,6,9,11,12,13,14)
F = x
F = x
00
xx
22
’
’
++
xx
33
xx
22
xx
11
xx
00
00
00
01
01
11
11
10
10
00
00
F x
F x
00
xx
22
+ x
+ x
00
’’
xx
11
xx
22
++
00 00 11 00
00
00
01
01
+ x
+ x
11
’’
xx
22
xx
33
00 00 11 00
11 00 11
11
0
4
12
8
1
5
13
9
11
11
10
10
11 00 00 11
00 11
11 00
3
7
15
11
6 marca 2011
Tablice Karnaugh
12
10
10
00 11
11 00
2
6
14
10
Warunek
Warunek Don’t
Don’t--Care
Care
Warunek
Warunek Don’t
Don’t--Care
Care
Dla niektórych funkcji niektóre kombinacje wejściowe są
Dla niektórych funkcji niektóre kombinacje wejściowe są
nieużywane, np. funkcja kodowania decymalnego BCD, gdzie
nieużywane, np. funkcja kodowania decymalnego BCD, gdzie
kodowane jest 10 cyfr na 16 możliwych kombinacji (4 bity).
kodowane jest 10 cyfr na 16 możliwych kombinacji (4 bity).
Minterm związany z nieużywaną kombinacja wejściową
Minterm związany z nieużywaną kombinacja wejściową
Minterm związany z nieużywaną kombinacja wejściową
Minterm związany z nieużywaną kombinacja wejściową
nazywa się
nazywa się “don’t
“don’t care
care conditions”
conditions”
Z t
i
Z t
i d ’t
d ’t
t bli K
h
ż
ś ić
t bli K
h
ż
ś ić
Zastosowanie
Zastosowanie don’t
don’t--care
care w tablicy Karnaugh może uprościć
w tablicy Karnaugh może uprościć
funkcje wyjściową
funkcje wyjściową
Don’t
Don’t--care
care jest zapisywane w tablicy jako
jest zapisywane w tablicy jako “X”
“X”
D
D
j
p yw
w
y j
j
p yw
w
y j
X
X
Warunek
Warunek
don’t
don’t--care
care może być traktowany jako zero lub
może być traktowany jako zero lub
jeden zależnie od potrzeby
jeden zależnie od potrzeby
6 marca 2011
Tablice Karnaugh
13
jeden, zależnie od potrzeby.
jeden, zależnie od potrzeby.
Warunek
Warunek Don’t
Don’t--Care
Care
Warunek
Warunek Don’t
Don’t--Care
Care
Zadanie:
Zadanie: Zdefiniować funkcję, która będzie zapalała diodę
Zdefiniować funkcję, która będzie zapalała diodę
LED przy liczbach parzystych:
LED przy liczbach parzystych:
F(
F(xx
33
,,xx
22
,,xx
11
,,xx
00
) = Σ(0, 2, 4, 6, 8)
) = Σ(0, 2, 4, 6, 8)
xx
33
xx
22
33 22
xx
11
xx
00
00
00
01
01
11
11
10
10
00
00
11
11
00
11
W kodzie BCD liczby binarne 10, 11, 12, 13, 14, and
00
00
01
01
00
44
12
12
88
11
55
13
13
99
11
11
00
11
00
00
00
00
15 są nieużywane, czylidon’t-care.
Rozwiązanie
Rozwiązanie
11
11
11
55
13
13
99
33
77
15
15
11
11
00
00
00
00
00
00
00
00
nie
nie względniające
względniające don’t
don’t care
care
F(
F(xx
33
,,xx
22
,,xx
11
,,xx
00
) =
) = xx
00
’’xx
33
’ +
’ + xx
00
’’xx
11
’’xx
22
’’
6 marca 2011
Tablice Karnaugh
14
10
10
22
66
14
14
10
10
11
11
00
00
Warunek
Warunek Don’t
Don’t--Care
Care
Warunek
Warunek Don’t
Don’t--Care
Care
Zadanie:
Zadanie: Zdefiniować funkcję, która będzie zapalała diodę LED
Zdefiniować funkcję, która będzie zapalała diodę LED
przy liczbach parzystych:
przy liczbach parzystych:
F(
F(xx
33
,,xx
22
,,xx
11
,,xx
00
) = Σ(0, 2, 4, 6, 8)
) = Σ(0, 2, 4, 6, 8)
xx
33
xx
22
33 22
xx
11
xx
00
00
00
01
01
11
11
10
10
00
00
11
11
X
X
11
W kodzie BCD liczby binarne 10, 11, 12, 13,
00
00
01
01
00
44
12
12
88
11
55
13
13
99
X
X
00
00
X
X
00
14, and 15 są nieużywane, czylidon’t-care.
Rozwiązanie uwzględniające
Rozwiązanie uwzględniające
don’t
don’t care
care
11
11
11
55
13
13
99
33
77
15
15
11
11
00
00
X
X
X
X
don t
don t care
care
F(
F(xx
33
,,xx
22
,,xx
11
,,xx
00
) =
) = xx
00
’ ’
6 marca 2011
Tablice Karnaugh
15
10
10
22
66
14
14
10
10
11
11
X
X
X
X
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
Zadanie:
Zadanie:
Zbudować układ logiczny sterownika do wyświetlacza 7
Zbudować układ logiczny sterownika do wyświetlacza 7--
segmentowego
segmentowego
aa
Decoder
Decoder
xx
00
xx
11
ff
gg
bb
aa
A
A
BB
CC
D
D
BCD to 7
BCD to 7 segm
segm
xx
22
xx
33
cc
dd
ee
D
D
EE
FF
G
G
6 marca 2011
Tablice Karnaugh
16
dd
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
1. Zbuduj tablicę prawdy
1. Zbuduj tablicę prawdy
xx
33
xx
22
xx
11
xx
00
aa
bb
cc
dd
ee
ff
gg
00
00
00
00
11
11
11 11
11
11
00
Decoder
Decoder
BCD to 7 segm
BCD to 7 segm
xx
00
xx
11
xx
22
xx
33
bb
cc
ee
ff
aa
gg
00
00
00
11
00
00
11
00
00
00
11
11
00
11
00
00
00
11
11 00
00
00
00
11
11
00 11
11
00
11
11
11
11 11
00
00
11
00
11
11 00
00
11
11
11
11
11
11
11
11
00
11
11
11
11
11
11
00
dd
00
11
00
00
00
11
00
11
00
11
11
00
00
11
11
11
00
11
11 00
00
11
11
11
00
11 11
00
11
11
11
00
11 11
11
11
11
11
11
11 00
00
00
00
00
11
11
11
11
00
00
00
11
00
00
11
11
00
11
00
11
11
11 00
00
00
00
11
11
11 11
11
11
11
11
11
11 11
00
11
11
xx
xx
xx
xx
xx
xx
xx
11
00
11
11
11
11
00
00
11
11
00
11
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
6 marca 2011
Tablice Karnaugh
17
11
11
11
00
11
11
11
11
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
xx
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
2. Utworzyć tablicę Karnaugh
2. Utworzyć tablicę Karnaugh
xx
33
xx
22
xx
11
xx
00
aa
00
00
00
00
00
00
00
11
11
00
00
00
00
11
00
00
11
00
00
00
11
11
00
11
00
00
ff
bb
aa
xx
33
xx
22
xx
11
xx
00
00
00 01
01 11
11 10
10
00
00
00
11
11
00
X
X
00
11
00
00
00
11
00
11
00
11
11
00
00
11
11
11
cc
ee
ff
gg
bb
01
01
11
11
00
11
11
11
X
X
X
X
X
X
X
X
00
11
11
11
11
00
00
00
11
00
00
11
11
00
11
00
dd
11
11
10
10
11
11
11
X
X
X
X
X
X
X
X
11
00
11
00
xx
11
00
11
11
xx
11
11
00
00
xx
11
11
00
00
a = x
a = x
11
+ x
+ x
33
+ x
+ x
00
xx
22
+ x’
+ x’
00
x’
x’
22
3. Zapisać funkcję logiczną
3. Zapisać funkcję logiczną
6 marca 2011
Tablice Karnaugh
18
11
11
00
00
xx
11
11
11
00
xx
11
11
11
11
xx
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
Budowa układu logicznego
4.
4. Narysować schemat układu logicznego
Narysować schemat układu logicznego
a = (x
a = (x +x
+x ) + x
) + x xx + x’
+ x’ x’
x’
a = (x
a = (x
11
+x
+x
33
) + x
) + x
00
xx
22
+ x
+ x
00
xx
22
aa
ff
gg
bb
ee
cc
dd
6 marca 2011
Tablice Karnaugh
19
xx
3
3
xx
2
2
xx
11
xx
00