Дискретная математика

  • 31 авг. 2011 г.
  • 1403 Слова
ОБРАЗОВАТЕЛЬНАЯ АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОРГАНИЗАЦИЯ

«ВОЛЖСКИЙ УНИВЕРСИТЕТ ИМ. В.Н. ТАТИЩЕВА»
(ИНСТИТУТ)

Факультет «Информатика и телекоммуникации»
Кафедра «Прикладная математика»

Контрольная работа
по дисциплине «Дискретная математика»

Вариант № 9

(071900 «Информатика и телекоммуникационные системы»)

Выполнила:Студентка группы ИТЗ-301

Корнилова Татьяна Юрьевна

Дата сдачи__________________
Проверил:
Профессор кафедры «ПМ»:________________С.В.Каверин

Дата:_______________________

Тольятти 2008г.
Оглавление

Задача 1. 3
Задача 2. 4
Задача 3. 7
Задача 4. 9
Задача 5. 11
Задача 6. 13
Задача 7. 15
Задача 8. 16

Задача 1.

Докажите тождество, используя диаграммы Венна.
(A U B)\C = (A\C) U (B\C).
Решение.Диаграмма Венна (A U B)\C
A U B C (A U B)\C
[pic]

Диаграмма Венна (A\C) U (B\C)
A \ C B \ C (A\C ) U (B\C)
[pic]

Из вида диаграмм Венна заключаем, что тождество верно.

Задача 2.

Дано: А={а,b,с}, В={1,2,3,4}, P1(А×В, P2(В2. Найдите область определения и область значений отношений P1, Р2.Изобразите P1, Р2 графически. Найдите P2-1. Проверьте графически и с помощью матрицы [Р2], является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным? Являются ли отношения P1, P2 функциями? Постройте три функции (если это возможно) f:A→B, чтобы одна из них была сюръективной, другая инъективной, а третья биективной.
P1 = {(a,1), (a,2), (a,4), (c,3), (c,2), (c,4)}
P2 ={(2,1), (3,1), (3,2), (4,1), (4,3)}
Решение.
Область определения отношения P1 = {а,с}.
Область значений отношения P1 = B = {1,2,3,4}.
Область определения отношения Р2 = {2,3,4}.
Область значений отношения P2 = {1,2,3}.
Графическое изображение P1 :
1) 2)

Графическое изображение P2 :
1) 2)

3)

P2-1 = {(1,2),(1,3), (2,3), (1,4), (3,4)}.
По графу отношения P2 (3-й способ представления) заключаем:
1) P2 − не рефлексивно, т.к. на элементах нет петель;
2) P2 − антирефлексивно, т.к. на элементах нет ни одной петли (для каждого узла на диаграмме не существует петли);
3) P2 − не симметрично, т.к. есть (2,1), но нет (1,2);
4) P2 − антисимметрично, т.к. не существует 2-хразличных узлов, связанных парой стрелок;
5) P2 − не транзитивно.
Проверим с помощью матрицы [Р2] свойства отношения P2
0 1 1 1 0 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 0 1 0

1) P2 − не рефлексивно, т.к. на главной диагоналиматрицы [P2] стоят нули;
2) P2 − антирефлексивно, т.к. на главной диагонали матрицы [P2] нет единиц;
3) P2 − не симметрично, т.к. [P2] ≠ [P2]T;
4) P2 − антисимметрично, т.к. верно, что

0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 00 0 0 0 1 0 1 0 0 0 0 0

5) P2 − не транзитивно, т.к. не верно, что

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

Отношение P1 не является функцией,...
tracking img