Задачи для практических занятий по дискретной математике (стр. 3 )

д) , , . е) , , .

ж)

3. По таблицам переходов–выходов автоматов, вычисляющих функции из задачи 2 а) – ж), построить канонические таблицы и канонические уравнения к. а. (автомат рекомендуется предварительно минимизировать).

4. Минимизировать к. д.а., заданный таблицей переходов-выходов.

а)		0	1	б)		0	1
S1			S1
S2			S2
S3			S3
S4			S4
S5			S5
S6			S6
S7			S7
S8			S8
S9			S9
			S10

в) г)

ОТВЕТЫ.

Занятие 1-3. 1. а) ; б) ; в) ; г) ; д) ; е) ; ж) ; з) ;

и) . 2. а) ; б) ; в) ; г) ;

д) ; е) ; ж) ; з) ; и) ; к) ;

л) . 3. а) да; б) нет; в) да; г) да; д) нет; е) нет.

4.	а) б) в) г) д) е)

5. а) ; б) ; в) . 9. а) ; б) ; в) ;

г) ; д) ; е)

; ж)

; з)

. 10. а) Е1 покрытие, не разбиение, Е2 не покрытие,

Е3 покрытие, разбиение, Е4 не покрытие, Е5 не покрытие, Е6 покрытие, разбиение; б) Е1 покрытие, не

разбиение, Е2 не покрытие, Е3 покрытие, разбиение, Е4 не покрытие, Е5 не покрытие. 11. 81. 12. 22.

13. 12. 14. 11, 1, 4. 15. 94, 65. 16. 1.

Занятие 4-5. 1. а) ;

б) ; в) ; г) .

2. а)	,	, , , , ;
б)		, , , , ;
в)		, , , , .

3. а) , , , ; б) , , ,

. 4. а) рефлекс., симметр., транзит., эквив.; б) антирефлекс., антисимметр., транзит., полнота; в) рефлекс., антисимметр., транзит., полнота; г) симметр.; д) антирефлекс., антисимметр.; е) рефлекс., симметр., транзит., эквив. 5. а) антирефлекс., антисимметр., транзит.,

полнота; б) рефлекс., симметр., транзит., эквив. 7. а) является; б) не является; в) не является;

г) является. 8. а) не является; б) не является; в) является; г) является; д) не является.

9. а) не является функцией; б) функция, инъекция; в) функция, инъекция, сюръекция, биекция;

г) функция, сюръекция; д) функция.

Занятие 6.

1. а) ; б) . 2. а) истинно; б) истинно; в) ложно. 3. а) не является истинным; б) не является истинным. 4. второй. 5. все сдали. 6. в среднем есть.

Занятие 8-10. 1. а) 1, 0; б) 1, 1. 2. а) (1101); б) (1111); в) (); г) ();

д) (); е) (). 3. а) тожд. ложная; б) выполн.; в) выполн.;

г) тожд. ложная; д) тожд. истинная. 4. а) ; б) ; в) . 5. а) ; б)

; в) ; г) . 6. а) ;

б) ; в) . 7. а) ;

б) . 8. а) , ; б) , . 9. а) ,

; б) , ; в) , . 10. а) ;

б) ; в) ; г) . 11. а) не полна; б) не полна; в) полна; г) полна;

д) полна; е) полна. 12. а) ; б) ; в) ; г) .

13. а) ; б) ; в) ; г) ;

д) ; е) ; ж) ; з) ; и) ;

к) ; л) ; м) ; н) .

Занятие 11-15.

1. :	а) ; б) ;	в) 4,1,4,2,1,0; г) b, f – висячие, g - изолированная; д) псевдограф, мультиграф.
:	а) ; б) ;	в) 1,7,3,1; г) А, Д – висячие, изолированных нет; д) псевдограф, мультиграф.
:	а) ; б) ;	в) : 3,0,1,1,2, : 1,2,2,0,2, : 4,2,3,1,4.
:	а) ; б) ;	в) : 1,1,1,1,1,4, : 1,2,3,1,1,1, : 2,3,4,2,2,5.

2. а) сильно связный; kcc()=1; koc()=1; kсл. с()=1; б) слабо связный; kcc()=4; koc()=2;

kсл. с()=1; в) слабо связный; kcc()=3; koc()=2; kсл. с()=1; г) сильно связный; kcc()=1;

koc()=1; kсл. с()=1; д) односторонне связный; kcc()=2; koc()=1; kсл. с()=1; е) односторонне

связный; kcc()=2; koc()=1; kсл. с()=1. 3. а) не является связным; k=2; V3,V4; (V1,V4), (V4,V5),

(V2,V3), (V3,V6); б) не является связным; k=2; точек сочленения нет; (V3,V4); в) не является связным;

k=2; V2; (V1,V2), (V3,V2), (V5,V2); г) не является связным; k=3; точек сочленения нет; мостов нет;

д) связный; k=1; V2,V3,V4,V5; (V2,V4), (V3,V5); е) связный; k=1; V3; (V2,V3), (V3,V6). 4. а) ,

, ; б) ; в) , , ; г) , , . 5. а) эйл. цепь:

; б) эйл. цикл: ; в) эйл. цикл: ;

г) эйл. цикл: ; д) эйл. цикл: ;

е) эйл. цепь: . 6. а) , , , , , , ;

б) , , , , , , . 9. а) , ,

, , , ; б) , , ,

, , . 10. а) ; .

Занятие16-17 a) S0Б→ S0М; S0Е→ S0Е; S0Г→ S1Д; S1Е→ S2В;

S1М→ S1Е; S1О→ S1Д; S1Т→ S1Ь;

S0М→ S0М; S0О→ S0О; S0Т→ S0Т; S1Б→ S1Б; S1Г→ S1Г;