«Дискретная математика»
Задание 1.
Представить множество V ={(x, y): P (x)/\ T (y) } (высказывательные функции P (x), T (y) заданы для каждого варианта) через указанные ниже множества, используя операции над множествами и декартово произведение множеств.
Обозначения:
· N - множество натуральных чисел,
· Z - множество целых чисел,
· Q - множество рациональных чисел,
· R - множество вещественных чисел.
Заданы следующие множества:
· 
· 
· 
· 
· 
· 
· 
· 
Вариант 1. P (x): «x – целые числа, кратные 6»;
T (y): «y – рациональные числа такие, что y2 < 2».
Вариант 2. P (x): «x – четные числа такие, что x2 <2»;
T (y): «y – целые числа, кратные 6 такие, что y3<0».
Вариант 3. P (x): «x – четные числа такие, что x > 2»;
T (y): «y – целые числа, кратные 6 такие, что y2 >4».
Вариант 4. P (x): «x – нечетные числа такие, что 2 x > π»;
T (y): «y – целые числа, кратные 2 такие, что y <√5».
Вариант 5. P (x): «целые числа, которые не делятся нацело на 3 и такие, что x2 <5»;
T (y): «y – целые числа, которые не делятся нацело на 2 и на 3 и такие, что y >√5».
Вариант 6. P (x): «x – целые числа такие, что √5 < x <√2»;
T (y): «y – целые числа, кратные 3 такие, что y > -√5».
Вариант 7. P (x): «x – целые числа, которые не делятся нацело на 2 и на 3»;
T (y): «y – рациональные числа такие, что y2 <4».
Вариант 8. P (x): «x – целые отрицательные числа, кратные 2 такие, что x2 >2»;
T (y): «y – целые отрицательные числа, не кратные 6 такие, что y2 >5».
Вариант 9. P (x): «x – целые отрицательные числа, кратные 3 такие, что x2 >2»;
T (y): «y – целые отрицательные числа, кратные 2 и не кратные 3 такие, что y2 <5».
Вариант 10. P (x): «x – натуральные числа кратные 3 такие, что 2 x > π»;
T (y): «y – целые отрицательные числа, кратные 2 такие, что y2 >4».
Вариант 11. P (x): «x – целые числа, не кратные 3 такие, что x2 <5»;
T (y): «y – целые неотрицательные числа, кратные 6 такие, что y2 >4».
Решение варианта 11.
Задание 2.
Докажите следующие тождества, проиллюстрируйте справедливость тождеств диаграммами Эйлера
Вариант 1. (A Ç B) È (C Ç D) = (A È C) Ç (B È C) Ç (A È D) Ç (B È D)
Вариант 2. A \ (B È C) = (A \ B) Ç (A \ C)
Вариант 3. A \ (B Ç C) = (A \ B) È (A \ C)
Вариант 4. A Ç (B \ C) = (A Ç B) \ (A Ç C) = (A Ç B) \ C
Вариант 5. (A \ B) \ C)= (A \ C) \ (B \ C)
Вариант 6. (A Ç B) È [ A Ç (– B)] = (A È B) Ç [ A È (– B)] = A
Вариант 7. A \ (B \ C) = (A \ B) È (A Ç C)
Вариант 8. A \ (B È C) = (A \ B) \ C
Вариант 9. A È B = A ¸ B ¸ (A Ç B)
Вариант 10. A È B = (A ¸ B) È(A Ç B)
Вариант 11. (A ¸ B) Ç C = (A Ç C) ¸ (B Ç C)
Решение варианта 11.
[по закону дистрибутивности]
Задание 3.
Укажите свойства (типы) перечисленных ниже отношений (симметричное, антисимметричное, асимметричное, рефлексивное, антирефлексивное, транзитивное, эквивалентности, толерантности, порядка, строгого порядка или предпорядка, полного порядка или частичного).
Вариант 1. Какие свойства имеет отношение «жить в одном городе» на множестве людей?
Вариант 2. Какие свойства имеет отношение «быть знакомым» на множестве людей?
Вариант 3. Какие свойства имеет отношение «быть моложе» на множестве людей?
Вариант 4. Какие свойства имеет отношение «быть делителем» на множестве натуральных чисел?
Вариант 5. Какие свойства имеет отношение «иметь общий делитель, отличный от единицы» на множестве натуральных чисел?
Вариант 6. Какие свойства имеет отношение «быть потомком» на множестве людей?
Вариант 7. Какие свойства имеет отношение «быть братом» на множестве людей?
Вариант 8. Какие свойства имеет отношение «иметь общий остаток от деления на 5» на множестве натуральных чисел?
Вариант 9. Какие свойства имеет отношение конгруэнтности на множестве треугольников?
Вариант 10. Какие свойства имеет отношение подобия на множестве треугольников?
Вариант 11. Какие свойства имеет отношение «пересекаться с» (иметь непустое пересечение), заданное на системе множеств?
Решение варианта 11.
Пусть M – произвольная система непустых множеств. Обозначим через R отношение «пересекаться с», т.е. 
. Тогда выполняются следующие свойства:
· рефлексивность: 
;
· симметричность: 
т.е. 
;
Свойство транзитивности может выполняться или не выполняться в зависимости от выбора системы множеств.
Пример 1. M={[0,5], [4,7], [6,10]}. Тогда [0,5]R[4,7] и [4,7]R[6,10], но неверно [0,5]R[6,10] – отношение не транзитивно.
Пример 2. M – множество отрезков на прямой, содержащих фиксированную точку. Отношение транзитивно.
Определение
Отношение называется отношением толерантности, если оно: а) рефлексивно; б) симметрично.
Отношение в примере 1 является отношением толерантности, а отношение в примере 2 является отношением эквивалентности.
Задание 4.
Приведите примеры (все для всех):
Вариант 1. Рефлексивного отношения.
Вариант 2. Антирефлексивного отношения.
Вариант 3. Симметричного отношения.
Вариант 4. Антисимметричного отношения.
Вариант 5. Транзитивного отношения.
Вариант 6. Отношения эквивалентности.
Вариант 7. Толерантного отношения.
Вариант 8. Отношения порядка.
Вариант 9. Отношения частичного порядка.
Вариант 10. Отношения линейного порядка.
Задание 5.
Для заданной матрицы смежности выполнить следующие задания:
· нарисовать граф;
· найти булевы произведения матрицы на себя степеней от 1 до 6;
· найти матрицу достижимости.
Вариант 1.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 2.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 3.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 4.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 5.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 6.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 7.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 8.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 9.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 10.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Вариант 11.
| A | B | C | D | E | F | |
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E | ||||||
| F |
Решение варианта 11.
Обозначим через M матрицу смежности.
| Произведение матрицы смежности орграфа | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M= | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M2 = | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M3 = | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M4 = | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M5 = | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| A | B | C | D | E | F | ||
| A | |||||||
| B | |||||||
| M6 = | C | ||||||
| D | |||||||
| E | |||||||
| F | |||||||
| M6 – матрица достижимости |
Задание 6.
1. Составить три множества Ф, И, О из букв, соответственно, своей фамилии, своего имени и своего отчества.
2. Представить полученные множества на кругах Эйлера.
3. Представить буквы множеств Ф, И, О в двоичной системе, используя следующую кодировку
| А | Л | Ц | |||
| Б | М | Ч | |||
| В | Н | Ш | |||
| Г | О | Щ | |||
| Д | П | Ъ | |||
| Е | Р | Ы | |||
| Ж | С | Ь | |||
| З | Т | Э | |||
| И | У | Ю | |||
| К | Ф | Я | |||
| Х |
.
4. Используя 2, 3 и 4 разряды определить 3 булевые функции F1(x1, x2, x3, x4, x5), F2(x1, x2, x3, x4, x5), F3(x1, x2, x3, x4, x5), определенные на 5-разрядных двоичных числах (на буквах, не вошедших в Ф, И, О положить значение функции равной 0).
5. Представить каждую функцию в совершенной дизъюнктивной нормальной форме (СДНФ).
Решение
МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ
Множества
Ф = { М, О, Р, З, В };
И = { О, Л, Е, Г };
О = { Е, В, Г, Н, Ь, И, Ч };
Круги Эйлера
