Дискретная математика
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Задание множеств
9.7) Пусть I = { a,b,c,d,e,f }, X = { a,b,c }, Y = {a,c,e,f }, Z = { d,e }. Определить множество, заданное формулой, перечислением элементов и с помощью характеристической функции:
Решение. Пересечение . Дополнение пересечения .
14.3) Какие из следующих утверждений справедливы: { }=1;
Решение. Справедливо. Единственным элементом данного множества является пустое множество.
Операции над множествами
7) Решить систему уравнений
где А, В, С - данные множества.
Решение. Из второй формулы следует, что . Следовательно,
.
10.3) Решить следующую систему уравнений:
При каких А, В, С эта система имеет решение?
Решение. В силу того, что для любых множеств , из второго уравнения следует, что . Таким образом, и . Учитывая, что , из первого уравнения выводим .
Заметим, что . Таким образом, решением системы является любое множество , удовлетворяющее включениям . Необходимым условием разрешимости является включение .
4.18) Доказать справедливость тождества: A = B (A\B) (B\A) = .
Нужно полное решение этой работы?
Решение
III. Отношения и функции
1.12) Пусть [a,b],[c,d] R. Найти геометрическую интерпретацию множеств:{1,2} x {a} .
Решение. Прямое произведение является парой точек на плоскости .
3.6) Задать всеми возможными способами бинарное отношение на множестве {-4,-3,-2,-1,0,1,2,3,4},определенное следующим образом: аb b-1 < a < b+2.
Решение. Перечисление
, или
.
Графиком (заштрихована полоса ), Стрелками между осями, графом
графом
378269512446016.6) Найти область определения, область значений, график отношения , обратное отношение 1, дополнение отношения, композиции , 1, 1 для отношения: .
Решение. График отношения изображен справа.
Область определения .
Область значений .
Обратное отношение .
Дополнение отношения
Квадрат отношения . В силу того, что синус монотонная функция, имеем .
Композиция с обратным отношением
то есть
Композиция обратного отношения с данным , то есть
15.4) Доказать, что для любых бинарных отношений справедливо тождество:
Решение.
Специальные бинарные отношения
5) Доказать, что если отношения 1 и 2 антисимметричны, то антисимметричны и отношения: 12 и 11, а объединение 12 антисимметричных отношений на А антисимметрично тогда и только тогда, когда 121 А.
Решение. Антисимметричность означает . Имеем: если и , то
,
.
Заметим, что ,
то есть . Если объединение 12 антисимметричных отношений на А антисимметрично, то
,
поэтому и .
Обратно, если , то и поэтому
.
10) Доказать, что отношение равномощности множеств есть эквивалентность
. Что является классами эквивалентности в этом случае?
Решение. Множества называются равномощными, если существует биекция . Рассмотрим на множестве всех множеств отношение «существует биекция ». Данное отношение симметрично, так как для любой биекции существует обратное отображение , которое также является биекцией. Данное отношение транзитивно, так как композиция биекций является биекцией, « существуют биекции и сквозное отображение является биекцией, поэтому ». Данное отношение рефлексивно, так как тождественное отображение , , является биекцией.
Классами эквивалентности являются мощности множеств. В случае конечных множеств, классы можно отождествить с неотрицательными целыми числами.
Функции алгебры логики
1.3) Построить таблицу истинности для формулы и, используя правила равносильных преобразований формул, привести ее к ДНФ и к КНФ, построить полином Жегалкина. Проверить правильность выполненных преобразований с использованием диаграмм Вейча. Найти существенные переменные функции, заданной формулой: (xy)(yz).
Решение. Построим таблицу истинности
0 0 0 1 1 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 0 1 0
1 0 1 0 0 1
1 1 0 1 0 0
1 1 1 1 1 0
ДНФ совпадает с СДНФ и состоит из одного дизъюнкта
Эта же форма является КНФ, состоящей из трех конъюнктов.
Полином Жегалкина