Материал: Дискретная математика. методические указания к выполнению лабораторных работ для студентов направления подготовки «Информатика и вычислительная техника». Собенина О.В., Пак А.А
13. |
|
|
|
|
|
|
|
17. |
|
|
|
|
|
|
|
|
R |
а |
b |
с |
d |
е |
f |
|
R |
а |
b |
с |
d |
е |
f |
|
а |
1 |
0 |
0 |
0 |
0 |
1 |
|
а |
1 |
0 |
0 |
0 |
1 |
0 |
|
b |
0 |
1 |
0 |
0 |
0 |
0 |
|
b |
0 |
1 |
1 |
0 |
0 |
0 |
|
с |
0 |
0 |
1 |
1 |
1 |
0 |
|
с |
0 |
1 |
1 |
0 |
0 |
0 |
|
d |
0 |
0 |
1 |
1 |
1 |
0 |
|
d |
0 |
0 |
0 |
1 |
0 |
1 |
|
е |
0 |
0 |
1 |
1 |
1 |
0 |
|
е |
1 |
0 |
0 |
0 |
1 |
0 |
|
f |
1 |
0 |
0 |
0 |
0 |
1 |
|
f |
0 |
0 |
0 |
1 |
0 |
1 |
14. |
|
|
|
|
|
|
|
18. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
R |
а |
b |
с |
d |
е |
f |
|
R |
а |
b |
с |
d |
е |
f |
|
а |
1 |
0 |
1 |
0 |
0 |
1 |
|
а |
1 |
0 |
0 |
0 |
1 |
0 |
|
b |
0 |
1 |
0 |
0 |
0 |
0 |
|
b |
0 |
1 |
0 |
0 |
0 |
0 |
|
с |
1 |
0 |
1 |
0 |
0 |
1 |
|
с |
0 |
0 |
1 |
0 |
0 |
1 |
|
d |
0 |
0 |
0 |
1 |
1 |
0 |
|
d |
0 |
0 |
0 |
1 |
0 |
0 |
|
е |
0 |
0 |
0 |
1 |
1 |
0 |
|
е |
1 |
0 |
0 |
0 |
1 |
0 |
|
f |
1 |
0 |
1 |
0 |
0 |
1 |
|
f |
0 |
0 |
1 |
0 |
0 |
1 |
15. |
|
|
|
|
|
|
|
19. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
R |
а |
b |
с |
d |
е |
f |
|
R |
а |
b |
с |
d |
е |
f |
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
|
а |
1 |
0 |
1 |
1 |
0 |
0 |
|
b |
0 |
1 |
0 |
0 |
1 |
1 |
|
b |
0 |
1 |
0 |
0 |
0 |
0 |
|
с |
1 |
0 |
1 |
0 |
0 |
0 |
|
с |
1 |
0 |
1 |
1 |
0 |
0 |
|
d |
0 |
0 |
0 |
1 |
0 |
0 |
|
d |
1 |
0 |
1 |
1 |
0 |
0 |
|
е |
0 |
1 |
0 |
0 |
1 |
1 |
|
е |
0 |
0 |
0 |
0 |
1 |
1 |
|
f |
0 |
1 |
0 |
0 |
1 |
1 |
|
f |
0 |
0 |
0 |
0 |
1 |
1 |
16. |
|
|
|
|
|
|
|
20. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
R |
а |
b |
с |
d |
е |
f |
|
R |
а |
b |
с |
d |
е |
f |
|
а |
1 |
0 |
0 |
1 |
0 |
0 |
|
а |
1 |
1 |
0 |
0 |
0 |
0 |
|
b |
0 |
1 |
0 |
0 |
1 |
1 |
|
b |
1 |
1 |
0 |
0 |
0 |
0 |
|
с |
0 |
0 |
1 |
0 |
0 |
0 |
|
с |
0 |
0 |
1 |
0 |
0 |
1 |
|
d |
1 |
0 |
0 |
1 |
0 |
0 |
|
d |
0 |
0 |
0 |
1 |
1 |
0 |
|
е |
0 |
1 |
0 |
0 |
1 |
1 |
|
е |
0 |
0 |
0 |
1 |
1 |
0 |
|
f |
0 |
1 |
0 |
0 |
1 |
1 |
|
f |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11
Задание 3
Докажите утверждение
Варианты
№ |
|
|
|
|
|
|
|
|
|
|
|
|
|
Задание |
|
|
|||
варианта |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
Докажите, что если отношения |
|
R1 и R2 рефлексивны, то рефлексивно от- |
||||||||||||||||
|
ношение |
R1 R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
Докажите, что если отношения R1 и R2 симметричны, то симметрично |
||||||||||||||||||
|
отношение |
R1 R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
3 |
Докажите, что если R эквивалентность, то R |
1 |
есть также эквивалент- |
||||||||||||||||
|
|||||||||||||||||||
|
ность. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
Докажите, что если отношения |
|
R1 и R2 рефлексивны, то рефлексивно от- |
||||||||||||||||
|
ношение |
R1 R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
5 |
Докажите, что |
R |
R |
|
|
– эквивалентность тогда и только тогда, когда |
|||||||||||||
|
1 |
|
2 |
|
|
||||||||||||||
|
R1 R2 R1 R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
6 |
Докажите, что |
(R R ) 1 |
R 1 R 1. |
|
|
||||||||||||||
|
|
|
|
|
1 |
|
2 |
|
|
|
2 |
|
|
1 |
|
|
|
||
7 |
Докажите, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
(R |
R ) R (R R ) (R |
R ) . |
|
|
|
|
||||||||||||
|
1 |
2 |
3 |
|
1 |
3 |
|
|
2 |
|
|
|
3 |
|
|
|
|
||
8 |
Докажите, что если отношения |
|
R1 и R2 рефлексивны, то рефлексивно от- |
||||||||||||||||
|
ношение |
R1 |
R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
9 |
Докажите, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
(R1 R2) R3 (R1 R3) (R2 R3) . |
|
|
|
|
||||||||||||||
10 |
Докажите, что если R эквивалентность, то R |
1 |
есть также эквивалент- |
||||||||||||||||
|
|||||||||||||||||||
|
ность. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
Докажите, что если отношения R1 и R2 симметричны, то симметрично |
||||||||||||||||||
|
отношение, |
R1 |
R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
12 |
Докажите, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
(R R ) R (R R ) (R |
|
R ) . |
|
|
|
|||||||||||||
|
1 |
2 |
3 |
|
1 |
3 |
|
2 |
|
|
3 |
|
|
|
|
||||
13 |
Докажите, что если отношения |
|
R1 и R2 рефлексивны, то рефлексивно от- |
||||||||||||||||
|
ношение R 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
Докажите, что |
(R |
R |
) |
1 |
R |
1 |
R |
1 |
|
|
||||||||
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
1 |
|
2 |
|
|
|
1 |
|
|
2 |
|
|
|
||
15 |
Докажите, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
(R R ) R (R R ) (R |
|
R ). |
|
|
||||||||||||||
|
1 |
2 |
3 |
|
1 |
|
|
3 |
|
|
2 |
3 |
|
|
|
||||
16 |
Докажите, что если отношения R1 и R2 симметричны, то симметрично |
||||||||||||||||||
|
отношение |
|
1 |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
R1 R1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
17 |
Докажите, что |
(R1 R2 ) |
1 |
1 |
|
1 |
. |
|
|
||||||||||
|
|
|
R1 |
|
|
R2 |
|
|
|
||||||||||
18 |
Докажите, что если R эквивалентность, то R |
1 |
есть также эквивалент- |
||||||||||||||||
|
|||||||||||||||||||
|
ность. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
Докажите, что если отношения R1 и R2 симметричны, то симметрично |
||||||||||||||||||
|
отношение R 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
Докажите, что |
R1 R2 |
|
|
– эквивалентность тогда и только тогда, когда |
||||||||||||||
|
R1 R2 R1 R2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
12
|
|
|
|
|
|
Задание 4. |
|
|
|
|
|
|
А={a,b,c}, В={1,2,3,4}, R |
A B, |
R B B . Изобразите |
R |
, R |
графиче- |
|||||
|
|
|
|
|
1 |
|
2 |
1 |
2 |
|
|
ски. Найдите (R R) |
1 |
. Проверьте с помощью матрицы, является ли отношение |
|||||||||
|
|||||||||||
R2 |
рефлексивным, симметричным, антисимметричным, транзитивным? |
||||||||||
|
|
|
|
|
|
Варианты |
|
|
|
|
|
|
№ |
|
|
|
|
Задание |
|
|
|
|
|
варианта |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
R {(a,1), (a,2), (b,3), (c,2), (c,3), (c,4)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (2,1), (2,2), (2,3), (2,4), (3,3), (4,4)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
2 |
R {(a,1), (a,2), (а,3), (а,4), (b,3), (c,2)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (1,4), (2,2), (2,3), (3,3), (3,2), (4,1), (4,4)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
3 |
R {(a,1), (a,2), (a,4), (c,3), (c,2), (c,4)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(3,1), (2,1), (3,2), (4,1), (4,3)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
4 |
R {(a,1), (a,2), (b,2), (b,4), (c,3), (c,2)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
5 |
R {(a,1), (a,2), (a,4), (b,1), (b,4), (c,3)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (2,4), (2,1), (3,3), (4,2), (4,1)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
6 |
R {(a,1), (a,2), (b,3), (c,2), (c,3), (c,4)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (2,1), (2,2), (2,3), (2,4), (3,3), (4,4)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
7 |
R1 |
{(a,1), (b,1), (b,3), (b,4), (c,3), (c,2)}, |
|
|
|
|
||||
|
|
|
|
|
|
||||||
|
|
R2 {(1,3), (1,4), (2,2), (3,3), (4,3), (4,4)}. |
|
|
|
|
|||||
|
8 |
R {(a,1), (a,2), (a,4), (b,3), (c,1), (c,4)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,3), (1,2), (2,3), (3,2), (3,4), (4,1)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
9 |
R {(a,3), (a,2), (b,2), (b,3), (c,1), (c,4)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (1,2), (2,2), (3,3), (4,1), (4,4)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
10 |
R {(a,2), (a,4), (b,3), (c,1), (c,2)}, |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,1), (1,3), (2,4), (3,1), (3,4), (4,3), (4,2)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
11 |
R1 |
{(a,1), (a,2), (a,4), (b,2), (b,4), (c,3)}, |
|
|
|
|
||||
|
|
|
|
|
|
||||||
|
|
R2 {(1,1), (2,2), (2,4), (3,3), (4,4), (4,2)}. |
|
|
|
|
|||||
|
12 |
R |
{(a,2), (a,3), (a,4), (c,1), (c,3), (c,4)}, |
|
|
|
|
||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
R |
{(1,4), (2,3), (2,1), (3,4), (4,2)}. |
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
13 |
R1 |
{(a,1), (a,2), (b,3), (b,4), (c,3), (c,4)}, |
|
|
|
|
||||
|
|
|
|
|
|
||||||
|
|
R2 {(1,1), (1,4), (2,1), (2,2), (2,4), (3,3)}. |
|
|
|
|
|||||
13
14 |
R {(a,3), (b,4), (b,3), (b,1), (b,2), (c,2)}, |
|
|
1 |
|
|
R |
{(1,1), (1,3), (2,4), (3,1), (3,3), (4,2)}. |
|
2 |
|
15 |
R |
{(a,3), (b,4), (b,3), (c,1), (c,2), (c,4)}, |
|
1 |
|
|
R |
{(1,2), (1,3), (1,4), (2,3), (4,3), (4,2)}. |
|
2 |
|
16 |
R {(a,2), (a,3), (a,4), (c,1), (c,2), (c,3)}, |
|
|
1 |
|
|
R |
{(1,1), (1,4), (2,3), (3,3), (4,1), (4,3), (4,4)}. |
|
2 |
|
17 |
R {(a,2), (a,4), (b,1), (b,2), (b,4), (c,2), (c,4)}, |
|
|
1 |
|
|
R |
{(1,1), (2,2), (2,4), (3,3), (4,4), (3,2), (1,3), (4,1)}. |
|
2 |
|
18 |
R {(b,1), (a,3), (a,4), (c,2), (c,4), (b,4)}, |
|
|
1 |
|
|
R |
{(1,1), (2,3), (2,2), (2,4), (3,3), (3,4), (4,2), (4,4)}. |
|
2 |
|
19 |
R1 |
{(a,1), (b,2), (b,3), (c,2), (c,3), (c,4)}, |
|
||
|
R2 {(1,3), (2,1), (2,2), (2,3), (2,4), (3,3), (4,4)}. |
|
20 |
R1 |
{(a,2), (a,3), (a,4), (b,3), (c,1), (c,4)}, |
|
||
|
R2 {(1,1), (2,3), (2,2), (3,4), (1,4), (2,4), (4,2)}. |
|
Содержание отчета
1.Номер и тема лабораторной работы.
2.Цель выполнения работы.
3.Условия задач приводятся полностью.
4.Решения излагаются подробно, объясняются все действия по ходу ре-
шения.
5.Анализ полученных результатов и вывод по работе.
ЛАБОРАТОРНАЯ РАБОТА № 4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМИЧЕСКИХ
ПРОЦЕДУР ТЕОРИИ ОТНОШЕНИЙ
Цель работы: изучение основных понятий и определений теории отношений, свойств отношений, операций над ними и специальных типов бинарных отношений. Получение практических навыков программной реализации алгоритмических процедур теории отношений.
Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.
ПРАКТИЧЕСКАЯ ЧАСТЬ Задания
Написать программу, реализующую следующую процедуру:
1.Получить инверсию отношения в виде перечисления упорядоченных пар и матрицы отношения.
14
2.Даны два отношения А и В, заданные перечислением пар. Получить A B
и B A .
3.Определить какими из свойств (рефлективность, симметричность, транзитивность) обладает отношение, а каким нет.
4.Даны два отношения А и В. Определить А В, А В, А\В.
5. Даны два отношения А и В. Определить |
A B , A |
6.Даны два отношения А и В. Определить ( A B) A
7.Даны три отношения А, В и С. Определить A B
8.Даны три отношения А, В и С. Определить ( A B) \
B A .
, A (A B)
C , A B C
( A C) , ( A \
.
.
C)
B
.
9.Определить, является ли данное отношение отношением эквивалентности.
10.Определить, является ли данное отношение отношением строго порядка.
11.Определить, является ли данное отношение отношением нестрого порядка.
12.Приведением к блочно-диагональному виду матрицу отношения, определить, является ли данное отношение эквивалентностью.
ЛАБОРАТОРНАЯ РАБОТА № 5
ПРЕДСТАВЛЕНИЕ ГРАФОВ В ЭВМ
Цель работы: изучение основных алгоритмов теории графов и получение практических навыков их программной реализации.
Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.
Алгоритмы 1. Алгоритм построения простого графа,
имеющего заданную последовательность степеней
Шаг 1. {d1 , ... ,dn }- последовательность степеней, упорядоченная по невозрастанию. Выберем произвольное dk. 0 и "изымем" dk из последовательности, соединяя вершину хk с первыми dk вершинами, не считая саму вершину хk.
Шаг 2. Упорядочим остаточную последовательность в порядке невозрастания.
Шаг 3. Шаги 1-2 выполнять до тех пор, пока не возникнет одна из следующих ситуаций:
а) все остаточные степени равны 0. В этом случае по
15