Контрольная работа - Решение задач дискретной математике - файл n1.doc

Контрольная работа - Решение задач дискретной математике
скачать (1547.5 kb.)
Доступные файлы (1):
n1.doc1548kb.15.10.2012 23:13скачать

n1.doc

1. Используя диаграммы Эйлера-Венна, решить задачу:

Экзамен по математике содержал три задачи: по алгебре, по геометрии и по тригонометрии. Из 750 абитуриентов задачу по алгебре решили 400 абитуриентов, по геометрии - 480, по тригонометрии 420; задачи по алгебре или геометрии решили 630 абитуриентов; по геометрии или тригонометрии -600 абитуриентов; по алгебре или тригонометрии - 620 абитуриентов; 100 абитуриентов не решили ни одной задачи. Сколько абитуриентов решили все задачи? Сколько абитуриентов решили только одну задачу?
группа 43

ХАГ = ХА + ХГ – ХА-Г = 400 + 480 – 630 = 250

ХГТ = ХГ + ХТ – ХГ-Т = 480 + 420 – 600 = 300

ХТА = ХТ + ХА – ХТ-А = 420 + 400 – 620 = 200=

ХАГТ = 750 – Х0 – ХА + ХГ + ХТ – ХАГ – ХГТ – ХТА =

= 750 –100 – 400 – 480 – 420 + 250 + 300 + 200 = 100

ХА’ = ХА – ХАГ – ХТА + ХАГТ = 400 – 250 – 200 + 100 = 50

ХГ’ = ХГ – ХГТ – ХАГ + ХАГТ= 480 – 300 – 250 + 100 = 30

ХТ’ = ХТ – ХТА – ХАГ + ХАГТ = 420 – 200 – 250 +100 = 20

50 + 30 + 20 = 100
Ответ: Все задачи решили: 100 человек

Только одну задачу 100 человек
2. Упростить выражение:













3. Установить выполнимость формулы 










1

2

3

4

5

6

7

A

B

C















0

0

0

1

1

1

0

1

1

1

0

0

1

1

0

1

1

1

1

1

0

1

0

1

1

1

0

1

0

0

0

1

1

1

0

1

1

1

1

1

1

0

0

0

1

1

1

1

1

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

1

1

1

1

1

0

0

0

1

0

1

0


Ответ: формула выполнима

4. Установить равносильны ли формулы ? и ?

? = (А?) ? (С ? А В)










1

2

3

4

5

A

B

C



А?

А В



 ? 4

0

0

0

1

1

0

1

1

0

0

1

1

1

0

0

1

0

1

0

0

1

0

1

1

0

1

1

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

0

0

1

1

1

0

0

0

1

1

1

1

1

1

0

0

1

1

1


? = (A? B?)? (?A)










1

2

3

4

5

6

A

B

C



А В

2?



?A

3?5

0

0

0

1

0

1

1

0

1

0

0

1

1

0

1

1

0

1

0

1

0

0

0

1

0

1

1

0

1

1

0

0

1

0

1

1

1

0

0

1

0

1

1

1

1

1

0

1

1

0

1

1

1

1

1

1

0

0

1

0

0

1

1

1

1

1

0

1

0

0

1

1


Ответ: формулы ? и ? равносильны
5. По заданной функции проводимости построить наиболее простую схему


X1

X2

X3

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1
F(1,0,1)=f(0,1,1)= f(1,1,1)=1

? ?  =

= Х3 (? ? ) =

= Х3(? 
6. Упростить схему


















7. Для заданного графа построить : матрицу смежности, матрицу инцидентности, матрицу достижимости:



Матрица смежности Матрица инцидентности





1

2

3

4

5

1

0

0

0

0

0

2

1

0

0

1

0

3

1

1

0

0

1

4

0

1

0

0

1

5

1

0

0

0

0







х2\ x1

х3\ x1

х5\ x1

х3\ x2

х2\ x4

х3\ x5

х4\ x2

х4\ x5

1

-1

-1

-1

0

0

0

0

0

2

1

0

0

-1

1

0

-1

0

3

0

1

0

1

0

1

0

0

4

0

0

0

0

-1

0

1

1

5

0

0

1

0

0

-1

0

-1



Матрица достижимости





1

2

3

4

5

1

1

0

0

0

0

2

1

1

0

1

1

3

1

1

1

1

1

4

1

1

0

1

1

5

1

0

0

0

1



8. Для графа из задания 7 найти число внутренней устойчивости.
х = {x1; x2; x3; x4; x5}

Г(x1) = 0;

Г(x2) = {x1; x3; x5};

Г(x3) = {x1; x4};

Г(x4) = {x3; x5};

Г(x5) = {x1}

S1 = {x1}

x \{S1 Г(S1)} = {x1; x3; x4; x5}

S2 = {x1; x2}

{x1; x2} {x1; x3; x5} = {x1} - внутренне неустойчивое множество

S2 = {x1; x3}

{x1; x3} {x1; x4} = {x1} - внутренне неустойчивое множество

S2 = {x1; x4}

{x1; x4} { x3; x5} - внутренне устойчивое множество

S2 = {x1; x4; x5}

{x1; x4; x5} {x1; x3; x5} = {x1; x3} - внутренне неустойчивое множество

S2 = {x1; x4} – 1-е max число внутренней устойчивости.
S3 = {x2}

x \ {S3 Г(S3)} = {x4}

S3 = {x2; x4}

{x2; x4} {x1; x3; x5; x3; x5} = 

S3 = {x2; x4} – 2-е max число внутренней устойчивости.
S4 = {x3}

x \ {S4 Г(S4)} = {x2; x5}

{x1; x3} {x1; x4} = {x1} - внутренне неустойчивое множество

S5 = {x3; x2}

{x3; x2} {x1; x3; x5; x1} = {x5} - внутренне неустойчивое множество

S5 = {x3;x5}

{x3; x5} {x1; x4; x1} =  - внутренне устойчивое множество

S5 = {x3;x5} - 3-е max число внутренней устойчивости
S6 = {x4}

x \ {S6 Г(S6)} = {x1; x2}

S7 = {x4; x1}

{x4; x1} { x3; x5 } =  - внутренне устойчивое множество

S7 = {x4; x1; x2}

{x4; x1; x2} {x3; x5; x1} = {x1} - внутренне неустойчивое множество

S7 = {x4;x1} - 4-е max число внутренней устойчивости
S8 = {x5}

x \ {S8 Г(S8)} = {x2; x3; x4}

S9 = {x5; x2}

{x5; x2} { x1; x3; x5 } = {x5} - внутренне неустойчивое множество

S9 = {x5; x3}

{x5; x3} { x1; x3; x5} ={x5} - внутренне неустойчивое множество

S9 = {x5; x4}

{x5; x4} { x1; x2; x5} ={x5} - внутренне неустойчивое множество
S8 = {x5} - 5-е max число внутренней устойчивости
Umax = {2; 2; 2; 2; 1} = 2
Ответ: Umax = 2

Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации