Контрольная по Дискретной математике 22_12_20
.pdf
|
Контрольные задачи по дискретной математике |
|
|||
|
Задача №1 24 варианта |
|
|
||
|
Найдите многочлен Жегалкина и выясните принадлежность клас- |
||||
|
сам K0, K1, S, L, M для булевой функции f(a; b; c; d). |
|
|
||
1. |
f(a; b; c; d) = (0; 1; 4; 5; 8 11; 13). |
13. |
f(a; b; c; d) = (2; 4 6; 9 |
14). |
|
2. |
f(a; b; c; d) = (0; 2; 4 8; 10; 14). |
14. |
f(a; b; c; d) = (2; 5 |
10; 12 |
14). |
3. |
f(a; b; c; d) = (1; 3 9; 11; 12). |
15. |
f(a; b; c; d) = (2; 4 |
6; 8 |
14). |
4. |
f(a; b; c; d) = (2 4; 6; 8 13). |
16. |
f(a; b; c; d) = (1 7; 10 12; 14). |
||
5. |
f(a; b; c; d) = (1 6; 9; 12 14). |
17. |
f(a; b; c; d) = (1 7; 9 11; 13). |
||
6.f(a; b; c; d) = (0; 2; 4; 5; 8; 10; 12 14). 18. f(a; b; c; d) = (2; 3; 5 8; 12; 13; 15).
7.f(a; b; c; d) = (0 2; 4 7; 10; 14). 19. f(a; b; c; d) = (1; 3; 4; 6; 9 11; 14; 15).
8. |
f(a; b; c; d) = (0; 2; 5; 8 11; 13). |
20. |
f(a; b; c; d) = (0 3; 8; 9; 11; 12). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9. |
f(a; b; c; d) = (0; 1; 4; 5; 10; 12 14). |
21. |
f(a; b; c; d) = (0; 1; 3 5; 8; 10 12; 14). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10. |
f(a; b; c; d) = (0; 2; 6 8; 10; 14). |
22. |
f(a; b; c; d) = (0 2; 5 10; 14). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
11. |
f(a; b; c; d) = (1; 3; 5 9; 12 14). |
23. |
f(a; b; c; d) = (0 3; 5; 6; 10; 13; 14). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
12. |
f(a; b; c; d) = (2 7; 9 11; 13). |
24. |
f(a; b; c; d) = (0; 2 4; 6; 8 13). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Задача №2 24 варианта |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Для булевой функции g(a; b; c) найдите минимальную ДНФ и по- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
стройте контактную схему по этой ДНФ. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
1. |
g(a; b; c) = ((a ! b) c) |
b |
. |
|
|
|
|
|
|
|
13. |
g(a; b; c) = (a b |
|
) ( |
|
|
|
|
! b). |
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
a |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
2. |
g(a; b; c) = ((a b) ! |
|
|
|
) |
|
|
|
. |
|
|
|
|
|
|
|
14. |
g(a; b; c) = (a bc) (b ! |
|
|
|
|
|
). |
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
b |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
ac |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
3. |
g(a; b; c) = ((b |
|
) _ |
|
|
|
) c. |
15. |
g(a; b; c) = (a c) (bc ! a |
|
|
). |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
a |
c |
c |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
4. |
g(a; b; c) = |
(a b)c |
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16. |
g(a; b; c) = |
a ! (b c) |
b |
|
. |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||
|
a |
c |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
5. |
g(a; b; c) = |
a ! (b c) |
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
17. |
g(a; b; c) = |
a (b ! c) |
|
b |
. |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
a |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
6. |
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
18. |
g(a; b; c) = (a |
|
|
bc) (a ! b). |
|||||||||||||||||||||||||||||||||||||||||||||
|
a (b ! c) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
g(a; b; c) = |
b |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
7. |
g(a; b; c) = (a b) |
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
19. |
g(a; b; c) = a ( |
|
|
|
! b). |
||||||||||||||||||||||||||||||||||||||||||||||||||
|
b ! c |
bc a |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
8. |
g(a; b; c) = q((a c) ! (b |
a |
)). |
|
|
|
20. |
g(a; b; c) = b ( |
ac |
! (b |
a |
)). |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
9. |
|
|
|
|
|
|
|
|
). |
|
|
|
|
|
|
21. |
|
|
(b _ c) a |
|
|
|
|
|
|
|
. |
||||||||||||||||||||||||||||||||||||||||||||
|
g(a; b; c) = (a c) (b ! |
|
|
|
|
|
g(a; b; c) = ( |
|
bc) _ |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
a |
a |
c ! a |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
10. |
g(a; b; c) = q(a ! (c (b |
a |
))). |
|
22. |
g(a; b; c) = (a |
b |
(b ! c)) ! a |
c |
. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
11. |
g(a; b; c) = (ab c) ! (b |
|
). |
|
|
|
|
23. |
g(a; b; c) = (c ! b) ! (a |
|
|
ac). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
bc |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
12. |
g(a; b; c) = (a ! a |
|
|
|
|
|
). |
24. |
g(a; b; c) = (a c) ! |
|
(a ! c). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
bc) ! (ab b |
|
b |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Задача №3 24 варианта
Найдите множество всех значений y, для которых является истинным предикат.
1.y 6 8 ! 8x(y + 1 > 2x), если x 2 ( 1; 3]; y 2 [0; 1).
2.y < 5 8x(y + 3 > 3x), если x 2 ( 1; 2]; y 2 [0; 10].
3.y > 2 8x(y < 2x + 3), если x 2 [0; 1); y 2 [0; 1).
4.y > 1 ! 8x(y < 5x + 2), если x 2 [0; 7]; y 2 [0; 1).
5.y > 5 8x(y < 7x + 1), если x 2 [0; 3]; y 2 [0; 7].
6.y > 6 9x(2y < 3x + 1), если x 2 [0; 5]; y 2 [0; 9].
7.y > 7 9x(3y < 2x + 1), если x 2 [ 2; 1]; y 2 [0; 1).
8.y > 8 9x(4y < 2x + 6), если x 2 ( 1; 1]; y 2 [0; 9].
9.y < 7 9x(y > x + 5), если x 2 [0; 1); y 2 [0; 8].
10.y > 1 _ 9x(y < 3x + 1), если x 2 [ 1; 2]; y 2 [0; 1).
11.9x(y > 2x + 1 3x + y < 1), если x 2 [ 1; 1]; y 2 [0; 7].
12.y < 10 ^ 8x(y > 3x + 4), если x 2 [ 2; 0]; y 2 [0; 1).
13.8x(y > 2x + 4 x + y < 3), если x 2 [ 3; 4]; y 2 [0; 6].
14.y > 2 ^ 9x(y < x + 4), если x 2 [ 4; 1]; y 2 [0; 1).
15.8x(y < x + 3 _ 3x + y < 2), если x 2 [ 4; 1]; y 2 [0; 1).
16.y > 3 ! 9x(y < 2x + 2), если x 2 [ 2; 1]; y 2 [0; 7].
17.8x(y > x + 2 ^ x + y < 3), если x 2 [ 3; 4]; y 2 [0; 1).
18.y < 10 9x(y < 4x + 2), если x 2 [ 2; 0]; y 2 [0; 1).
19.8x(y < 3x + 3 2x + y > 2), если x 2 [ 2; 2]; y 2 [0; 5].
20.y > 2 9x(y < 3x + 2), если x 2 [ 2; 3]; y 2 [0; 7].
21.9x(y > 2x + 4 ^ y > 3 3x), если x 2 [ 1; 1]; y 2 [0; 1).
22.8x(y > 4x + 3) ! (y > 2), если x 2 [ 2; 1]; y 2 [0; 8].
23.9x(y < 4x + 4 ^ 2x + y < 4), если x 2 [ 2; 3]; y 2 [0; 1).
24.y < 10 _ 8x(y > 4x + 4), если x 2 [ 3; 1]; y 2 [0; 11].
Задача №4 24 варианта
Докажите следующее утверждение, где A, B, C – произвольные множества.
1.(A [ C) n ( A4B) = (A n B) [ ((B \ C) n A).
2.(A4 B) [ (C n A) = (A \ B) [ A [ (B n C).
3.( B n A)4(A [ C) = (B4C) n A.
4.( A n C) [ (A4B) = (A n B) [ ((B [ C) n A).
5.(A4 B) n (A \ C) = ((A \ B) n C) [ ( B n A).
6.( A [ C) n (A4B) = ((A \ B) n C) [ A [ B.
7.( A4B) \ (B n C) = A [ B [ C.
8.(A n B)4(A \ C) = A \ (B4C).
9.( C n B) [ (A4 C) = (A \ C) [ C [ (A n B).
10.(A4B) n ( A \ C) = (A n B) [ ((B \ C) n A).
11.(A \ C) n (A4B) = (A \ B) n C.
12.(A4B) \ ( B n C) = A n (B [ C).
13.( B n A)4( A \ C) = A [ (B4C).
14.A4(B n (A4C)) = (A n B) [ (B n C).
15.( A4B) n ( B [ C) = A \ B \ C.
16.(A n C) \ (A4B) = (A \ C) n B.
17.(A4 B) [ (B n C) = A [ B [ (B n (C n A)).
18.(A n B)4( A [ C) = A n (B4C).
19.C4(B n (A4C)) = (C n B) [ (B n A).
20.C n (A4B) = (C n A) \ (C n B) () A \ B \ C = ?.
21.(A \ C) n B = (A \ C) () (A \ B) n C = A \ B.
22.(A4B) [ C = A [ B [ C () (A \ B) n C = ?.
23.A n (A n B) = C n (C n B) () B n A = B n C.
24.(A \ B) [ C = (B [ C) \ A () C A.
Задача №5 24 варианта
Найдите R1 R2 1, если R1 A P , а R2 B P , где A = fa; b; cg,
B= fx; y; zg, P = fp; q; r; tg.
1.R1 = f(a; p); (a; q); (a; r); (a; t); (b; r); (c; t)g, R2 = f(x; p); (y; p); (y; q); (y; t); (z; q); (z; t)g.
2.R1 = f(a; p); (b; q); (b; r); (b; t); (c; r); (c; t)g, R2 = f(x; p); (x; q); (y; q); (y; r); (z; q); (z; r)g.
3.R1 = f(a; p); (a; q); (b; p); (b; q); (c; r); (c; t)g, R2 = f(x; q); (x; r); (y; q); (y; r); (y; t); (z; t)g.
4.R1 = f(a; p); (a; q); (a; r); (a; t); (b; r); (c; r)g, R2 = f(x; p); (x; q); (y; p); (y; r); (z; q); (z; r)g.
5.R1 = f(a; p); (a; q); (a; r); (b; p); (c; r); (c; t)g, R2 = f(x; p); (x; q); (y; q); (y; r); (z; p); (z; r)g.
6.R1 = f(a; p); (a; r); (b; r); (b; t); (c; r); (c; t)g, R2 = f(x; r); (y; q); (y; r); (y; t); (z; r); (z; t)g.
7.R1 = f(a; p); (a; q); (b; q); (c; q); (c; r); (c; t)g, R2 = f(x; p); (x; q); (y; q); (y; r); (z; q); (z; r)g.
8.R1 = f(a; p); (a; q); (b; q); (b; r); (c; q); (c; t)g, R2 = f(x; r); (y; p); (y; q); (y; r); (y; t); (z; r)g.
9.R1 = f(a; p); (b; p); (b; q); (b; r); (c; q); (c; r)g, R2 = f(x; p); (x; q); (x; r); (y; q); (y; r); (z; t)g.
10.R1 = f(a; p); (a; q); (b; q); (b; t); (c; p); (c; t)g, R2 = f(x; p); (x; q); (y; q); (y; r); (y; t); (z; p)g.
11.R1 = f(a; p); (a; q); (a; r); (b; q); (c; q); (c; r)g, R2 = f(x; p); (x; r); (y; q); (y; r); (z; q); (z; t)g.
12.R1 = f(a; p); (a; q); (b; q); (b; r); (c; r); (c; t)g, R2 = f(x; p); (x; r); (y; q); (y; r); (y; t); (z; r)g.
13.R1 = f(a; p); (a; q); (a; r); (b; q); (c; q); (c; r)g, R2 = f(x; q); (x; r); (y; q); (y; r); (z; p); (z; t)g.
14.R1 = f(a; p); (a; r); (b; q); (b; r); (c; r); (c; t)g, R2 = f(x; r); (y; q); (y; r); (y; t); (z; r); (z; t)g.
15.R1 = f(a; p); (a; q); (a; r); (b; r); (b; t); (c; t)g, R2 = f(x; p); (x; t); (y; q); (y; r); (z; q); (z; r)g.
16.R1 = f(a; p); (a; q); (b; p); (b; q); (c; q); (c; t)g, R2 = f(x; r); (y; p); (y; q); (y; r); (y; t); (z; r)g.
17.R1 = f(a; p); (a; q); (a; r); (b; t); (c; q); (c; r)g, R2 = f(x; p); (x; q); (y; q); (y; r); (z; q); (z; t)g.
18.R1 = f(a; p); (b; p); (b; q); (b; r); (b; t); (c; t)g, R2 = f(x; p); (x; q); (y; r); (z; q); (z; r); (z; t)g.
19.R1 = f(a; q); (b; p); (b; q); (b; t); (c; r); (c; t)g, R2 = f(x; p); (y; q); (z; p); (z; q); (z; r); (z; t)g.
20.R1 = f(a; p); (a; q); (a; t); (b; p); (b; t)g,
R2 = f(x; p); (y; p); (y; r); (y; t); (z; p); (z; q); (z; r)g. 21. R1 = f(a; q); (a; r); (b; q); (b; r); (b; t)g,
R2 = f(x; q); (x; r); (y; q); (y; t); (z; p); (z; r); (z; t)g. 22. R1 = f(a; p); (a; r); (a; t); (c; p); (c; t)g,
R2 = f(x; p); (x; q); (x; r); (y; t); (z; p); (z; r); (z; t)g. 23. R1 = f(a; r); (a; t); (c; p); (c; r); (c; t)g,
R2 = f(x; q); (x; r); (y; p); (y; q); (y; t); (z; r); (z; t)g. 24. R1 = f(b; p); (b; q); (b; t); (c; q); (c; t)g,
R2 = f(x; p); (x; r); (x; t); (y; q); (y; r); (y; t); (z; p)g.
Задача №6 24 варианта
Вычислите значение указанного выражения.
1. |
P5 9A(3)2 |
6C42. |
13. |
P (2; 2; 1) + A42 C(5)3 . |
||||
2. |
6P2 |
+ A53 3C(4)2 . |
14. |
P (3; 1; 2) + A(2)4 7C53. |
||||
3. |
P (3; 0; 2) |
+ A52 2C64. |
15. |
2P (2; 1; 1) + A(2)3 C(4)3 . |
||||
4. |
P (2; 2; 1) |
+ 2A43 3C(3)5 . |
16. |
P6 2A64 3C42. |
||||
5. |
P4 + A(2)4 C(5)3 . |
17. |
P6 |
A(5)4 C64. |
||||
6. |
P (3; 1; 2) |
+ A(2)3 6C52. |
18. |
P (3; 0; 3) 6A53 + C(5)3 . |
||||
7. |
2P (2; 1; 1) + A(3)4 5C(4)3 . |
19. |
2P (2; 0; 3) A(5)3 + 3C(7)2 . |
|||||
8. |
P2 A53 + 9C42. |
20. |
P3 |
+ A(2)5 C(3)6 . |
||||
9. |
2P3 |
+ A52 2C(4)2 . |
21. |
P (2; 0; 2) 3A52 + C(4)5 . |
||||
10. |
P4 |
A(3)2 |
C64. |
22. |
P4 |
A(3)3 + C64. |
||
11. |
P5 |
A(3)4 |
C(3)5 . |
23. |
P (3; 0; 1) + A63 5C72. |
|||
12. |
P (3; 0; 2) A43 + C52. |
24. |
P3 |
2A42 + C(4)4 . |
||||
Задача №7 24 варианта
Решите указанную рекуррентность.
1.a0 = 4, an+1 = 2an + 18 4n.
2.a0 = 4, b0 = 1, an+1 = 2an + 3bn, bn+1 = 2an bn.
3.a0 = 3, an+1 = 4an 14( 3)n.
4.a0 = 5, b0 = 0, an+1 = 2an 2bn, bn+1 = 2an bn.
5.a0 = 5, an+1 = an + 6 5n.
6.a0 = 3, b0 = 4, an+1 = an + 2bn, bn+1 = 5an 2bn.
7.a0 = 5, an+1 = 4an + 21 3n.
8.a0 = 6, b0 = 3, an+1 = 3an 4bn, bn+1 = an 2bn.
9.a0 = 8, an+1 = 4an 14 2n.
10.a0 = 0, b0 = 3, an+1 = an + 2bn, bn+1 = 4an bn.
11.a0 = 1, an+1 = 3an + 6 3n.
12.a0 = 1, b0 = 1, an+1 = 5an 3bn, bn+1 = 3an bn.
13.a0 = 2, an+1 = 4an + 12 4n.
14.a0 = 1, b0 = 1, an+1 = 3an + bn, bn+1 = an bn.
15.a0 = 3, an+1 = 5an + 10 5n.
16.a0 = 1, b0 = 1, an+1 = an + 4bn, bn+1 = an + 5bn.
17.a0 = 1, an+1 = 2an 14( 2)n.
18.a0 = 1, b0 = 2, an+1 = 5an 2bn, bn+1 = 2an bn.
19.a0 = 3, an+1 = 3an 12( 3)n.
20.a1 = b1 = 4, an+1 = bn, bn+1 = 4 + an.
21.a0 = 5, an+1 = 4an 6( 2)n.
22.a1 = 1, a2 = 7, an+1 = 2 + 3an 1.
23.a0 = 0, an+1 = 4an + 5( 1)n.
24.a0 = 0, a1 = 1, an+2 = 2( 1)n 2an+1 an.
Задача №8 24 варианта
Постройте указанный граф G и найдите его цикломатическое и хроматическое число.
1.G = O2 + K4.
2.G = K2 + K1;2.
3.G = O3 + K2.
4.G = K4 + K1;3.
5.G = O4 + K3.
6.G = K2 + K3;3.
7.G = O3 + K4.
8.G = K3 + K2;3.
9.G = O4 + K1;2.
10.G = K2 + K1;4.
11.G = O2 + K4;2.
12.G = K3 + K3;1.
13.G = O3 + K3;2.
14.G = K3 + K1;4.
15.G = O2 + K1;3.
16.G = K2 + K2;3.
17.G = O3 + K2;2.
18.G = K4 + K1;2.
19.G = O2 + K3;2.
20.G = K3 + K2;2.
21.G = O3 + K1;3.
22.G = K2 + O4.
23.G = O2 + K3;3.
24.G = K2 + K2;2.