Сборник решений: задачи по дискретной математике

Дискретная математика
Домашняя работа 1
Задача 1. Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов. Сколько студентов успешно решили только одну контрольную работу?
Задача 2. В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом – 15 учеников, метро и троллейбусом – 13 учеников, троллейбусом и автобусом – 9 учеников. Сколько учеников пользуются только одним видом транспорта?
Задача 3. В деревне N треть мужчин холостые, а у половины женщин есть муж. Какая доля в деревне одиноких людей, если все придерживаются традиционных ценностей?

---

Домашняя работа 2
Задача 1.a Доказать: (a∨b∨c)∧(a∨¬b∨c)∧¬(a∨c) = пустое множество
Задача 1б Доказать a∇(a∇b)=b
Задача 2
Найти множество P(M), где M = {0, 1, 2, 3, 4}, и построить граф и матрицу бинарного отношения P.

1. Найти P³(M).
2. Найти классы эквивалентности по P на множестве Z.

---

Домашняя работа 3
Задача 1. Дано множество B всех подмножеств множества {"р", "у", "к", "а"}. Пара элементов множества B находится в бинарном отношении R, если первый элемент является подмножеством второго элемента. Построить граф бинарного отношения R (в любом виде).
Задача 2. Найти НОД (54321, 67890) с помощью алгоритма Евклида.
Задача 3. Решить 11х - 9y = 5 в целых числах.
Задача 4
4.а. Представить число π в виде цепной дроби до 4-го числа.
4.б. Получить π в виде неправильной дроби, используя 4.а.
4.в*(не обязательно) Получить π в виде неправильной дроби, с точностью не менее 10⁻⁸.

---

Домашняя работа 4
Задача 1. Используя сравнение по модулю, доказать, что xⁿ - yⁿ делится на (x - y) при любых целых n.
Задача 2. Если миска пуста, то либо кот расстроен, либо человек даст коту корм. Если кот расстроен, он портит обои. Миска пуста. Выводится ли из этого, что либо обои будут испорчены, либо человек покормит кота?
Задача 3. Привести к ДНФ и КНФ: ¬(x∧y→x)∨(x∧(y∨z))
Задача 4. Доказать или опровергнуть равносильность логических выражений:
а) "((x→¬y)→¬z)≡(x∧¬y)" и "¬((x∨¬z)∧(¬x∨y∨z))"
б) "¬(Ɐx)[Ɐy T(x,y)→Ǝz(T(x,y)∧Q(z))]" и "ƎxⱯy[T(x,y)∧¬Q(y)]"Показать/скрыть дополнительное описание