Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 6 из 8)

2.2. Пусть

. Пусть также ( ) тогда и только тогда, когда и . Доказать, что — отношение эквивалентности и построить разбиение на классы эквивалентности.

2.3. Для разбиения

множества построить эквивалентность .

2.4. Пусть

. Рассмотрим на множестве всех подмножеств множества отношение быть подмножеством. Доказать, что это отношение частичного порядка. Построить диаграмму этого отношения.

2.5. Пусть

. Рассмотрим на этом множестве отношение делить нацело. Доказать, что это отношение частичного порядка. Построить диаграмму этого отношения.

3. Логика высказываний.

3.1. Является ли высказыванием предложение «треугольник называется равносторонним, если все его стороны равны»?

3.2. Сформулируйте отрицания следующих высказываний и укажите значения истинности высказываний и их отрицаний: «Картофель относится к семейству розоцветных»; «картофель не относится к семейству пасленовых».

3.3. Являются ли следующие высказывания отрицаниями друг друга (объяснить почему): «человеку известны все виды животных, обитающих на Земле», «на Земле существует вид животных, не известный человеку».

3.4. Следующее сложное предложение требуется расчленить на простые и записать с использованием логических связок: «Обидно, если в пору цветения садов не сочиняют стихи и не наполняют чарки вином» (Цзацзауань. Ли Шан-Инь).

3.5. Записать таблицу истинности для формулы:

.

4. Теория графов.

4.1. В шахматном турнире по круговой системе участвуют семь студентов. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима – по три, Семен и Илья – по две, Женя – одну. С кем сыграл Леша?

4.2. Насыщенным углеводородом называется соединение углерода C, имеющего валентность 4 и водорода H, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода.

4.3. Мэрия решила построить торговый центр в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками. Сколько будет построено торговых центров?

4.4. На пир при дворе короля Артура собралось четное число рыцарей, которые либо дружат, либо враждуют. Оказалось, что у каждого из рыцарей друзей больше, чем врагов. Доказать, что волшебник Мерлин может так рассадить рыцарей за круглым столом, что справа и слева от каждого из них будет сидеть друг.

4.5. Образовавшийся коммерческий университет арендует здание для проведения занятий. В четверг проводится 7 лекций: право, английский язык, французский язык, экономика, менеджмент, маркетинг, этикет. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно, например, их читает один и тот же лектор, или есть студенты, которые должны посещать разные лекции, или для их проведения нужна одна и та же аудитория и т.д. (В таблице крестиком отмечены лекции, которые не могут читаться одновременно). Определите минимальное время, за которое могут быть прочитаны лекции в четверг.

	право	англ.яз.	фран.яз.	экономика	Менеджмент	маркетинг	Этикет
Право
Англ. яз.
Фран. яз.
Экономика
Менеджмент
Маркетинг
Этикет

5. Введение в алгоритмы.

5.1. На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству их решили проводить вдоль дорог. Каким образом провести телефонные линии, чтобы их общая длина была минимальной? Ниже приведена матрица расстояний между бытовками: элемент а_ij таблицы равен 0, если i-я и j-я бытовка не соединены дорогой напрямую, в противном случае а_ij равно расстоянию между соответствующими бытовками.

	1	2	3	4	5	6	7
1	0	200	0	100	0	0	0
2	200	0	150	0	170	180	0
3	0	150	0	0	0	100	0
4	100	0	0	0	240	0	380
5	0	170	0	240	0	0	210
6	0	180	100	0	0	0	260
7	0	0	0	380	210	260	0

5.2. Из города А в город Б ведут несколько дорог (карту см. на рис. ниже). Найдите число маршрутов автомобильного путешествия из А в Б, учитывая, что при движении автомобиль должен все время приближаться к Б.