Дискретная математика. Контрольная работа По дисциплине Дискретная математика

Название	Контрольная работа По дисциплине Дискретная математика
Анкор	Дискретная математика
Дата	03.01.2021
Размер	127.5 Kb.
Формат файла
Имя файла	Дискретная математика.doc
Тип	Контрольная работа #165658

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

Контрольная работа
По дисциплине «Дискретная математика»

Выполнил:

Ст. гр ЗПИпбуд -217

Новиков А.Д.

Принял:
Шутов Антон Владимирович

Владимир 2020
10 ВАРИАНТ
1. Раздел «Множества»
Задание 1.

Дано:

В группе 20 учеников. После медицинского осмотра на дополнительное обследование 14 учеников были направлены к терапевту, 6 – к окулисту, 5 – к ортопеду. К терапевту и окулисту были направлены 3 ученика, к терапевту и ортопеду –3, к окулисту и ортопеду – 2. Сколько учеников были направлены к терапевту, окулисту и ортопеду?
Решение:
m(E) = 20 – всего учеников

m(A) = 14 – к терапевту

m(B) = 6 – к окулисту

m(C) = 5 – к ортопеду

m(A B) = 3 – к терапевту и окулисту

m(A  C) = 3 – к терапевту и ортопеду

m(B  C) = 2 – к окулисту и ортопеду
Обозначим разбиение универсального множества Е множествами А, В, С:

К1 – к терапевту – 14;

К2 – к терапевту и окулисту – 3;

К3 – к окулисту – 6;

К4 – к терапевту и ортопеду – 3;

К5 – ко всем сразу - ?;

К6 – к окулисту и ортопеду – 2;

К7 – к ортопеду – 5;

К8 – никуда (по условию задачи таких нет).

Используя свойство мощности множеств и рисунок можно выполнить вычисления:

m(K5) = m(A È B È C) – m(A) – m(B) – m(C) + m(A  B) + m(A  C) + m(B  C);

m(K5) = 20-14-6-5+3+3+2 = 3.

Ответ: 3.
Задание 2. Упростить:

(

) \ (A È B).

Ответ:

Задание 3.

Дано: Нарисовать диаграмму Эйлера-Венна для множества (A  B) È (C \ (A È B)):

Решение:

Задание 4.

Дано: найти все подмножества множества A= {a, b, c, d}.

Решение:

Ø А;
{a}, {b}, {c}, {d};
{a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d};
{a,b,c}, {a,b,d}, {a,c,d}, {b,c,d};
.

Задание 5.

Дано: Эквивалентны ли множества A = {(x, y): y = lnx, 0 < x < ¥} и B = {(x, y): y = sinx, –¥
Решение: Данные множества неэквивалентны, т.к. невозможно установить однозначное соответствие между элементами множеств. У натурального логарифма допустимые значения x лежат в пределе [1;+∞], а у синуса [–∞;+∞], при этом значение функции lnx линейно возрастает, а sinx циклически меняется.

2. Раздел «Отношения. Функции»
Задание 1.

Дано: Задано бинарное отношение ρ = {<1, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.

Найти: D(ρ), R(ρ), ρ

ρ, ρ^-1. Проверить, будет ли отношение ρ рефлексивным, симметричным, антисимметричным, транзитивным?

Решение:

D_ = {x существует y, что x y} = {1,2,3};

R_ = {y существует x, что x y} = {1,2,3};



 = {x, z существует такое y, что x, y   и  y, z } = {<1,1>, <3,2>, <3,1>, <2,3>, <1,3>};

 ^–¹ = {x, y  y, x  } = {<1,1>, <3,2>, <3,1>, <1,3>, <2,3>};

Данное отношение не является рефлексивным, поскольку не выполняется условие « x, x   »;

Данное отношение является симметричным, поскольку выполняется условие « = ^–1»;

Данное отношение является транзитивным, поскольку выполняется условие «

  »;

Данное отношение не является антисимметричным, поскольку не выполняется условие «  ^–1 состоит только из пар вида  x, x ».
Задание 2.

Дано: Будет ли отношением эквивалентности на множестве действительных чисел отношение x ρ y, задаваемое равенством x = 2y?

Решение: Нет. Потому что отношение эквивалентности на множестве – это бинарное отношение, для которого выполнены следующие условия: рефлексивность, симметричность, транзитивность. Условия рефлективности для этого множества не выполняются.
Задание 3.

Дано: функция f(x) = lnx+

, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Решение:

D(f) = (0; +∞);

R(f) = (-∞; +∞);

Данная функция является суръективной, т.к. для любого «x»  (0; +∞) существует «y»  (-∞; +∞).

Данная функция является инъективной, потому что не существует одинаковых «y» при разных «x».

Поскольку данная функция является и суръективной, и инъективной, поэтому она также является биективной.
3. Раздел «Графы»
Задание 1.

Дано: Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).

Решение:

Данный граф неориентированный; не содержит петель и кратных рёбер; имеет смежные рёбра; неполный; непланарный; недвудольный.

На основании матрицы смежности:

Матрица инцидентности:

Матрица связности:

Задание 2.

Дано: Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из x₁ в x₇ в ориентированном графе, заданном матрицей весов.

Решение:

Кратчайший путь: 1 → 5 → 3 → 7.

Задание 3.

Дано: Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.

Решение:

4. Раздел «Булевы функции»
Дано: Для данной формулы булевой функции

а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
(x& y)  ((xVz) y)
ДНФ:

1) x&y)V((xVz)Vy);

2) (x&y)V((x&z)Vy);

3) (x&y)V((xVy)&(zVy));

4) (x&y)V(x&z)V(x&y)V(y&z)V(y&y) = (x&y)V(x&z)V(x&y)V(y&z)V(y).
КНФ:

(x&y)&((xVz)&y);
(x&y)&((xVz)&y);
(x&y)&((x&y)V(z&y))
(x&y)&(xVz)&(xVy)&(yVz)&(yVy) = (x&y)&(xVz)&(xVy)&(yVz)&(y)

СДНФ:

(x&y&z)(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&z)V(x&y&y)V(x&y&y) = (x&y&z)V(x&y&z)V(x&y&z)V(x&y&z).
СКНФ:

(x&y&z)&(x&y&z)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz)&(xVyVz) = (x&y&z)&(x&y&z)&(xVyVz)&(xVyVz)&(xVyVz).
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);