Сборник задач по дискретной математике (стр. 4 )

12б) ; 12в) . 13а) существенная переменная x; 13б) все переменные существенны; 13в) существенных переменных нет.

14а) ; 14б) . 16а) ;

16б) ; 16в) ; 16г) . 18а) ; 18б) .

20. Схеме соответствует функция . 21а) не полна; 21б) не полна;

21в) полна; 21г) не полна; 21д) полна; 21е) полна. 22а) ;

22б) ; 22в) ; 22г) .

ГЛАВА IV

1а) истинное; 1б) ложное; 1в) переменное, 1г) переменное, 1д) переменное.

3а) ложное; 3б) ложное; 3в) истинное; 3г) ложное; 3д) истинное; 3е) ложное.

5а) ; 5б) ; 5в) ; 5г) ;

5д) ; 5е) . 6а) ; 6б) ; 6в) ; 6г) .

ГЛАВА V

1а) 000101; 1б) 001111; 1в) машина не применима к слову;

2а) 00111; 2б) 0010; 2в)- г) машина не применима к слову.

ГЛАВА VI

1а) ; ; ;

1б) ; ;

1в); ; ;

1г) в мостов и точек сочленения нет; в мостами являются ребра (А, С) и (С, Е), точка сочленения – С; 1е) ; ; 3а) {1,2}, {3,4,5}, {6}; 3б) граф сильносвязный; 3в) {1,2,3,4}, {5}, {6}; 3г) {2}, {1,3,5,6}, {4};

3д) {1,2,3,4,5,6}, {7}, {8}; 3е) {1}, {2,6}, {3}, {4}, {5}, {7}; {8};

4а) 7,5,4,4,5,6,1, 1,2,6,8,8,4,3,3; 4б) 1,1,2,3,3,4,4,5,6,8,8,1,7,8,1,6,2,6,3,5,2,3, 4,1; 5а) да; 5б) да; 5в) нет; 6а) мин. остов имеет вес 8; 6б) мин. остов имеет вес 7; 7а) ; 7б) ;

8а) ; 8б) ;

9) изоморфными являются: {а), б)}, {д), е)}, {ж), з)}.

ГЛАВА VII

S\X	0	1	2
B1	B3/1	B1/0	B1/1
B2	B2/1	B4/0	B1/1
B3	B3/0	B3/0	B1/1
B4	B3/1	B3/0	B4/1

1а) 1б) 2а)

S\X	0	1
*S1	S1/0	S2/0
S2	S1/1	S2/1

S\X	0	1
*S1	S1/0	S2/0
S2	S3/0	S4/0
S3	S1/1	S2/1
S4	S3/1	S4/1

B1={S1,S5},

B2={S4},

B3={S2, S6},

B4={S3,S7}

2б) 3а)

S\X	0	1	2
B1	B2/1	B3/0	B1/0
B2	B2/1	B1/0	B1/0
B3	B3/0	B3/0	B3/1

s(t)	x(t)	y (t)	s(t+1)
0	0	0	0
0	1	0	1
1	0	1	0
1	1	1	1

B1={S1, S3}, .

B2={S4}, B3={S2, S5, S6, S7}

3б)

0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	0	0
1	0	1	1	0	1
1	1	0	1	1	0
1	1	1	1	1	1

5а) 5б)

З З

З

6а)

S\X	0	1
B1	B2/0	B3/1
B2	B1/1	B1/0
B3	B1/0	B1/1

0	0	0	0	0	1
0	0	1	1	1	0
0	1	0	1	0	0
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	1	0	0
1	1	0	-(0)	-(0)	-(0)
1	1	1	-(0)	-(0)	-(0)