Zadania z rozwiązaniami
Zadanie 1
Dla funkcji F opisanej tablicą zmienne niezbędne
x1 x2 x3 x4 x5 x6 x7 F
są x5 oaz x7. Należy wyznaczyć wszystkie (!!!) 1 1 0 0 0 1 0 1 0
2 0 1 1 1 0 0 0 0
minimalne zbiory argumentów, od których zależy ta
3 1 1 1 0 0 1 1 0
funkcja oraz jej minimalne wyrażenie boolowskie z
4 1 1 0 1 1 0 0 1
najmniejszą liczbą argumentów.
5 1 0 1 0 0 1 1 0
6 1 1 1 0 1 0 0 0
7 1 0 0 0 0 0 1 1
Rozwiązanie
8 1 1 0 1 0 1 0 0
9 1 1 0 1 1 0 1 0
P5 = (1,4,6,9;2,3,5,7,8,10,11,1,2)
10 1 0 0 0 0 1 0 1
11 0 1 1 1 0 0 1 0
P7 = (1,3,5,7,9,11,12;2,4,6,8,10)
12 0 1 1 0 0 0 1 0
PF = (1,2,3,5,6,8,9,11,12;4,7,10)
P5 �" P7 | PF = (1,9) ;(4)(6) ;(7)(3,5,11,12) ;(2,8)(10)
Tablica porównań
2,10 x1x2x3x4x6
8,10 x2x4
(x4 + x2)(x4 + x3)(x3 + x6)( x3 + x1 + x2) = (x4 + x2x3)( x3 + x1x6 + x2x6) =
4,6 x3x4
= x3x4 + x1x4x6 + x2x4x6 + x2x3 + x1x2x3x6 + x2x3x6
3,7 x2x3x6
5,7 x3x6
7,11 x1x2x3x4
7,12 x1x2x3
Stąd wszystkie rozwiązania minimalno-argumentowe:
x3, x4, x5, x7
x2, x3, x5, x7
x1, x4, x5, x6, x7
x2, x4, x5, x6, x7
x5 x7
x3 x4 x5 x7 F
00 01 11 10
1 0 0 1 1 0
x3 x4
2 1 1 0 0 0
00
1 1 0 
3 1 0 0 1 0
01
0  0 1
4 0 1 1 0 1
5 1 0 0 1 0 11
0 0  
6 1 0 1 0 0
10
 0  0
7 0 0 0 1 1
8 0 1 0 0 0
9 0 1 1 1 0
F = x3x4x5 + x4x5x7
10 0 0 0 0 1
11 1 1 0 1 0
12 1 0 0 1 0
1
Zadanie 2
Poniższy zespół 7 funkcji 5 zmiennych zrealizować w układzie o schemacie
blokowym, jak na rysunku. Zapewnić minimalną liczbę wyjść z pamięci ROM.
x1 x5
" " "
f1 = Ł(0,3,7,10,17,31)
f2 = Ł(0,2,10,15)
ROM
f3 = Ł(1,4,6,11)
" " "
f4 = Ł(1,14,17,20,25)
DEKODERY
f5 = Ł(5,16,18,30)
f6 = Ł(2,8,13,20) " " "
f1 f7
f7 = Ł(8,12,27,28)
W rozwiązaniu podać rysunek ilustrujący organizację dekoderów.
Rozwiązanie
Obliczanie klas zgodności (zapisy wg indeksów i dla fi)
S1 = O 1
/
S2 = O 1 / 2
/
S3 = 1,2 1,3 / 2,3
S4 = 2 1,3 / 2,3 / 2,4
S5 = 1,2,3,4 1,3,5 / 2,3,5 / 2,4,5
S6 = 1,3,5 1,3,5,6 / 2,3,5 / 2,4,5
S7 = 1,2,3,4,5 1,3,5,6 / 2,3,5,7 / 2,4,5,7 / 1,3,5,7
Uwaga: znak / separuje klasy
Rozłączne klasy zgodne: {f1, f3, f5, f6}, {f2, f4, f7}
0 1 2 3 4 0 1 2 3
f1 f3 f5 f6 O f2 f4 f7 O
/ /
2
Zadanie 3
x4 x5
x1 x2 x3 0 0 0 1 1 1 1 0
W tabelce dana jest funkcja f(x1,x2,x3,x4,x5).
0 0 0 1 2  3
Należy obliczyć dekompozycję nierozłączną dla
0 0 1 4 5 6 
A = {x4,x5}. W rozwiązaniu wystarczy podać podział
0 1 1  7 8 9
G . Kodowanie bloków PF przyjąć dowolne wg NKB. 0 1 0 10  11 12
1 1 0  13 14 
1 1 1 15   16
Rozwiązanie
1 0 1 17   18
1 0 0  19 20 
A = {x4, x5} B = {x1, x2, x3} C = ?
PF = (1,10,17 ;5,7,19 ;6,8,14 ;3,12,16 ;2,13 ;4,15 ;9,18 ;11,20)
P(A) | PF = (1,10,17) | (4,15) ;(5,7,19) | (2,13) ;(6,8,14) | (11,20) ;(3,12,16) | (9,18)
P(B) = (1,2,3 ;4,5,6 ;7,8,9 ;10,11,12 ;13,14 ; 15,16 ;17,18 ;19,20)
Tworzenie podziału G:
1,2,3 4,5,6
13/14 x4
10,11,12 15, 16
17, 18 7,8,9
13, 14 19, 20
Obliczanie zbioru C:
15/16 x4
17/18 x4 czyli: F= H(x4, x5, g(x1, x2, x3, x4))
19/20 x4
P(B,C) = (1,2 ;3 ;4,5 ;6 ;7 ;8,9 ;10 ;11,12 ;13 ;14 ; 15 ;16 ;17 ;18 ;19 ;20)
G = (1,2,3,10,11,12,13,16,17,20 ;4,5,6,7,8,9,14,15,18,19)
a1 a2 a3 a4 a5 a6 f
Zadanie 4
1
0 0 0 0 0 0 0
Dla funkcji f o wielowartościowych
2 1 2 1 2 0 2 0
3 1 2 1 0 1 2 1
wejściach podanej w tablicy należy obliczyć
4 0 1 1 0 0 1 1
wszystkie minimalne zbiory argumentów
5 0 1 1 2 0 0 2
zapewniające jednoznaczną reprezentację tej funkcji.
6 1 2 0 3 2 2 1
Przyjąć, że argumenty  niezbędne (tzw. rdzeń) są: 7 0 0 0 1 0 1 0
8 0 0 1 1 0 1 2
a1, a3. W rozwiązaniu podać również tablicę funkcji
9 0 1 0 3 2 0 3
z minimalną i najmniejszą liczbą argumentów.
10 2 2 0 3 2 2 3
3
Rozwiązanie
P1 �" P3 = (1,7,9 ;2,3 ;4,5,8 ;6 ;10)
PF = (1,2,7 ;3,4,6 ;5,8 ;9,10)
P1 �" P3 | PF = (1,7)(9) ;(2)(3) ;(4)(5,8) ;(6) ;(10)
Tablica porównań:
1,9 a2, a4, a5
7,9 a2, a4, a5, a6
2,3 a4, a5
4,5 a4, a6
4,8 a2, a4
(a4 + a2)(a4 + a5)(a4 + a6) = a4 + a2a5a6
Stąd dwa rozwiązania minimalno-argumentowe:
a) a1, a3, a4
b) a1, a2, a3, a5, a6
Ale rozwiązanie minimalne z najmniejszą licznością to: a1, a3, a4
Konstrukcja tablicy z najmniejszą liczbą argumentów:
a1 a3 a4 f
1 0 0 0 0
2 1 1 2 0
3 1 1 0 1
.
. itd
.
Zadanie 5
Zaprojektować licznik mod 8 z wejściem zezwalającym (Enable). Przerzutniki do
realizacji dobrać tak, aby uzyskać najprostszy schemat logiczny licznika. Schemat ten należy
narysować.
4
Rozwiązanie
Tablica przejść-wyjść licznika Tablica wzbudzeń przerzutników typu D
E E
0 1 y 0 1
Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0
0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 1
1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1
1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0
1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0
1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 0 1 0 1
D2 D1 D0
Tablice wzbudzeń przerzutników typu T
E
0 1 0 1 0 1
Q2 Q1 Q0
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 0 1
0 1 0 0 1 0 1 0 1
0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 1
1 0 1 0 1 0 1 0 1
1 1 0 0 0 0 1 0 1
1 1 1 0 0 0 0 0 1
T = EQ1Q0 T1 = EQ0 T0 = E
czyli
T = Q1T1 T1 = EQ0 T0 = E
Najprostszy schemat logiczny licznika (synchronicznego!)
E
T0 Q0 T1 Q1 T2
Q2
CLK
5
Zadanie 6
Dla funkcji F podanej w tablicy x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2
1 0 0 0 1 0 0 1 1 0  1
obliczyć minimalne i o najmniejszej liczności
2 0 1 1 0 0 0 0 1 0 0 1
zbiory argumentów, od których ta funkcja
3 0 1 0 0 0 1 1  1 0 0
zależy. Zmienne niezbędne tej funkcji to: x1,
4 0 0 1 0 1 1 1 0 0 0 1
x3, x7.
5 0  1 0 0 0 1 1 0 0 0
6 0 1 1 0 1 1 0 1 1 1 
7 0 0 0 1 0 0 1 0 1 1 1
8 1 1 1 0 0 0 1  0 1 0
9 0 0 1 1 0  1 0 1 1 0
Rozwiązanie
PN = P1 �" P3 �" P7 = (1,3,7 ;2,6 ;4,5,9 ;8)
PF = (1,2,4 ;1,67 ;3,5 ;6,8,9)
PN | PF = (1,7)(3) ;(2,6) ;(4)(5)(9) ;(8)
1,3 2,4,6,9
3,7 2,4,6
2,6 5,6,9
4,5 5,6,8
4,9 4,5,9
5,9 4,8,9
(5 + 6 + 8)(5 + 6 + 9)(4 + 9 + 8) = (5 + 6 + 5 �" 9)(5 + 6 + 9)(4 + 9 + 5 �" 8) =�"
= (4 �" 5 + 5 �" 9 + 5 �" 8 + 4 �" 6 + 6 �" 9 + 5 �" 6 �" 8 + 4 �" 8 �" 9 + 8 �" 9 + 5 �" 8 �" 9)(2 + 4 + 6) =
= (4 �" 5 + 5 �" 9 + 5 �" 8 + 4 �" 6 + 6 �" 9 + 8 �" 9)(2 + 4 +6)
Składniki iloczynowe z najmniejszą liczbą argumentów: 4 �" 5, 4 �" 6, 6 �" 9
czyli R1 = {x1, x3, x4, x5, x7}
R2 = { x1, x3, x4, x6, x7}
R3 = { x1, x3, x6, x7, x9}
6
Zadanie 7
Wiedząc, że dla funkcji z tablicy podziały P1,
x1 x2 x3 x4 x5 Y
P2, P5 są 3-przydatne, a P3, P4  4-przydatne,
1 0 0 0 0 0 D
zrealizować tę funkcję w strukturze z najmniejsza
2 1 0 0 0 0 A
3 0 0 0 1 0 C
liczbą wejść bezpośrednich oraz najmniejszą liczbą
4 0 0 0 1 1 D
wejść i wyjść bloku G.
5 1 0 0 1 1 B
6 1 0 0 1 0 B
7 0 0 1 0 0 D
8 1 0 1 0 1 B
9 1 0 1 0 0 A
10 0 1 1 0 0 C
11 0 1 1 0 1 E
12 1 1 1 0 1 A
Rozwiązanie
PF = (1,4,7 ;2,9,12 ;3,10 ;5,6,8,11)
P1 �" P5 | PF = (1,7)(3,10) ;(2,9)(6) ;(4)(11) ;(5,8)(12) r = 3
P1 �" P2 | PF = (1,4,7)(3) ;(5,6,8)(2,9) ;(10)(11) ;(12) r = 3
P2 �" P5 | PF = (1,7)(2,9)(3)(6) ;(4)(5,8) ;(10) ;(11)(12) r = 4
A) U = {x1, x5} B) U = {x1, x2}
A) PV = (1,2 ;3,4,5,6 ;7,8,9 ;10,11,12)
Tworzenie podziału G:
x5 => 4,5 | 3,6
1,2 3,4,5,6
7,8,9 10,11,12
Wektory 4, 5 trzeba oddzielić od 3, 6. Stąd x5, czyli V = x2 x3 x4 x5
PV ' = (1,2 ;3,6 ;4,5 ;7,9 ;8 ;10 ;11,12)
G' = (1,2,4,5,7,8,9 ;3,6,10,11,12)
B) PV = (1,2;3,6;4,5;7,9,10;8,11,12)
1,2 3,6
4,5 8,11,12
7,9,10
=> x1
7
Wektor 5 należy oddzielić od wektora 4. Stąd x51, czyli V = {x3, x4, x5, x1}
PV ' = (1 ;2 ;3 ; 4 ;5 ;7,10 ;9 ;8,12 ;11)
G' = (1,2,4,7,9,10 ;3,5,6,8,11,12)
A) x2 x3 x4 x5 B) x3 x4 x5 x1
G
G
x1 x5 x1 x2
H H
Zadanie 8
Dla funkcji F podanej w tablicy obliczyć wszystkie minimalne zbiory argumentów,
od których ta funkcja zależy. Zmienne niezbędne tej funkcji to: x1, x3, x7.
x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2
1 0 0 0 1 0 0 1 1 0 0 1
2 0 1 1 0 0 0 0 1 0 0 1
3 1 1 1 0 1 1 0 0 0 1 0
4 0 1 0 0 0 1 1 0 1 0 0
5 0 0 1 0 1 1 1 0 0 0 1
6 0 1 1 0 0 0 1 1 0 0 0
7 0 1 1 0 1 1 0 1 1 1 1
8 0 0 0 1 0 0 1 0 1 1 1
9 1 1 1 0 0 0 1 1 0 1 0
10 0 0 1 1 0 0 1 0 1 1 0
Rozwiązanie
P1 �" P3 �" P7 = (1,4,8 ;2,7 ;3 ;5,6,10 ;9)
P1 �" P3 �" P7 | PF = (1)(4)(8) ;(2)(7) ;(3) ;(5)(6)(10) ;(9)
Tablica porównań:
1|4 2,4,6,8,9
1|8 8,9
4|8 2,4,6
2|7 5,6,9
5|6 2,5,6,8
5|10 4,5,6,9
6|10 2,4,8,9
8
Wyrażenie boolowskie według indesów zmiennych xi:
(8 + 9)(2 + 4 + 6)(5 + 6 + 9)(2 + 5 + 6 8) = (9 + 89)(9 + 5 + 6)(2 + 6 + 4)(2 + 6 + 5 + 8) =
= [9 + 8(5 + 6)][2 + 6 + 4(5 + 8)] = (9 + 5 �" 8 + 6 �" 8)(2 + 6 + 4 �" 5 + 4 �" 8) =
= 2 �" 9 + 6 �" 9 + 4 �" 5 �" 9 + 4 �" 8 �" 9 + 2 �" 5 �" 8 + 5 �" 6 �" 8 + 4 �" 5 �" 8 + 4 �" 5 �" 8 + 2 �" 6 �" 8 +6 �" 8 +
4 �" 5 �" 6 �" 8 + 4 �" 6 �" 8
Stąd wszystkie minimalne rozwiazania:
x1, x2, x3, x7, x9
x1, x3, x6, x7, x9
x1, x3, x6, x7, x8
x1, x3, x4, x5, x7, x9
x1, x3, x4, x7, x8, x9
x1, x2, x3, x5, x7, x8
x1, x3, x4, x5, x7, x8
Zadanie 9
Dla funkcji F podanej w tablicy znalez
ć dekompozycję o strukturze jak na rysunku.
W rozwiązaniu podać tablice prawdy funkcji G1, G0 oraz H.
Wskazówka: najpierw obliczyć dekompozycję H(x1,x2,x3,G0(x1,x4,x5));
x1 x2 x3 x4 x5 y1 y2 y3
1 1 1 0 0 0 0 0 1
x1 x2 x3 x1 x4 x
5
2 1 1 1 1 1 0 1 1
3 1 1 0 1 0 1 0 0
4 1 0 0 1 1 0 1 0
G1 G0
5 1 0 0 0 0 0 0 0
6 0 0 1 1 1 0 0 0
7 0 0 0 1 1 1 0 0
H
8 0 0 0 1 0 0 0 1
9 0 1 0 1 0 0 0 0
y1 y2 y
3
10 1 1 1 0 1 0 0 1
Rozwiązanie
U = {x1, x2, x3} V = {x1, x4, x5}
PU = (1,3 ;2,10 ;4,5 ;6 ;7,8 ;9)
PV = (1,5 ;2,4 ;3 ;6,7 ;8,9 ;10)
PF = (1,8,10 ; 2;3,7 ;4 ;5,6,9)
9
PU | PF = (1)(3) ;(2)(10) ;(4)(5) ;(6) ;(7)(8) : (9)
Tworzenie podziału G :
0
1,5 3
10 2,4
8,9 6,7
G =1,5,8,9,10 ;2,3,4,6,7
0
G | PF = (1,8,10)(5,9) ;(2)(3,7)(4)(6)
0
Tworzenie podziału G :
1
2 3,7 4 6
2,10
1,3 4,5 6
9
7,8
G1 = 2,10 ;1,3,7,8 ;4,5 ;6,9
Konstrukcja tablic prawdy:
G0 : G1 : H:
x1 x4 x5 g0 x1 x2 x3 g1 g2 g1 g2 g0 h
1 0 0 0 1,3 1 1 0 0 1 1 0 0 0 1 1
1,5 2
2,10 1 1 1 0 0
1 1 1 0 0 1
1 1 1 1 10
2,4
4,5 1 0 0 1 0
1 1 0 0 0 1
1,8
1 1 0 1
3
"
" 0 1 1 1 0 0
3,7
"
"
"
"
"
"
"
Podział do obliczenia funkcji h:
G �" G = (1,5,8,9,10 ;2,3,4,6,7)(2,10 ;1,3,7,8 ;4,5 ;6,9) = (2 ;10 ;1,8 ;3,7 ;4 ;5 ;6 ;9)
0 1
10
Zadanie 10
Dla relacji R, w której zbiór par zgodnych jest E = {(e1,e2), (e1,e3), (e1,e4), (e1,e5),
(e1,e6), (e1,e7), (e2,e3), (e2,e5), (e2,e6), (e2,e7), (e3,e4), (e3,e5), (e3,e6), (e3,e8), (e4,e6), (e4,e7), (e4,e8),
(e5,e6), (e5,e7), (e5,e8), (e6,e7), (e6,e8), (e7,e8)} obliczyć maksymalne klasy zgodności:
a) metodą wg par zgodnych,
b) metodą wg par sprzecznych.
Rozwiązanie a)
e1
O
/
S1 =
S2 = e1 e1, e2
S3 = e1, e2 e1, e2, e3
S4 = e1, e3 e1, e3, e4/e1, e2, e3
S5 = e1, e2, e3 e1, e3, e5/e1, e2, e3, e5/e1, e3, e4
S6 = e1, e2, e3, e4, e5 e1, e2, e3, e5, e6/e1, e3, e4, e6/e1, e3, e4
S7 = e1, e2, e4, e5, e6 e1, e2, e5, e6, e7/e1, e4, e6, e7/e1, e2, e3, e5, e6/e1, e3, e4, e6
S8 = e3, e4, e5, e6, e7 e5, e6, e7, e8/e4, e6, e7, e8/e3, e5, e6, e8/e3, e4, e6, e8/e1, e2, e5, e6, e7/
e1, e4, e6, e7/e1, e2, e3, e5, e6/e1, e3, e4, e6
Rozwiązanie b)
Pary sprzeczne: (e1, e8) (e2, e4) (e2, e8) (e3, e7) (e4, e5)
(e8 + e1) (e8 + e2) (e4 + e2) (e4 + e5) (e3 + e7) =
= (e8 + e1e2) (e4 + e2e5)(e3 + e7) =
= (e4e8 + e2e5e8 + e1e2e4 + e1e2e5)(e3 + e7) =
= e3e4e8 + e2e3e5e8 + e1e2e3e4 + e1e2e3e5 +
e4e7e8 + e2e5e7e8 + e1e2e4e7 + e1e2e5e7
W obu przypadkach Maksymalne klasy zgodności są następujące:
{e1, e2, e5, e6, e7}
{e1, e4, e6, e7}
{e5, e6, e7, e8}
{ e4, e6, e7, e8}
{ e1, e2, e3, e5, e6}
{e1, e3, e4, e6}
{e3, e5, e6, e8}
{e3, e4, e6, e8}
11