Дискретная математика

Размещено на http://www.allbest.ru/

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

Филиал федерального государственного автономного образовательного учреждения высшего профессионального образования

«Российский государственный профессионально-педагогический

университет» в г. Советском

Кафедра профессионально-педагогического образования

Контрольная работа

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

Выполнил:

студентка гр. Св-211 ГМУ

Малышева Т.А.

Проверил:

Советский 2014

ЗАДАНИЕ №1

1. Пусть, , , . Найти

а) ; б) , в) .

Решение

а) = {1,2,a,b,c}; = {2, c};

б) = {1, a, b}; = {1, 2, a, b};

в) = {1,2,a,c};={1,2,a,c} .

ЗАДАНИЕ №2

Является ли рефлексивным, антисимметричным и транзитивным отношение перпендикулярности на множестве прямых в пространстве?

Решение

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

ЗАДАНИЕ №3

Пусть и . Какие из нижеперечисленных отношений между множествами А и В являются функциями, определенными на А со значениями в В?

a)

b)

Решение

Функцией называется множество упорядоченных пар , которое удовлетворяет условию: для любого элемента существует единственный элемент .

Исходя из этого определения, отношение а) является функцией, а б) не является функцией, т.к. элементу 0 ставится в соответствие два элемента из В, а именно 1 и 7.

ЗАДАНИЕ №4

бинарный предикат перпендикулярность пространство

Какими свойствами обладают следующие бинарные отношения, заданные на множестве натуральных чисел:

a)

b)

Решение

а) Не рефлексивно: любое натуральное число не может быть меньше самого себя.

Антирефлексивно: рефлексивность не выполняется для любого натурального числа.

Не симметрично: если , то не верно, что .

Не антисимметрично: если и , то не верно, что .

Транзитивно: если и , то .

б) Не рефлексивно: не верно, что для любого элемента а выполняется равенство .

Не антирефлексивно: не для всех натуральных чисел рефлексивность не выполняется (Например, 5+5=10 при а=5).

Симметрично: симметричность следует из коммутативности сложения натуральных чисел.

Не антисимметрично: если a+b=10 и b+a=10, то не верно, что a=b.

Не транзитивно: например, 4+6=10 и 6+4=10, но 4+4=8.

ЗАДАНИЕ №5

Найти значение выражения при , , .

Решение

ЗАДАНИЕ №6

Доказать логическое тождество .

Решение

Данное равенство не является тождеством: по свойству дистрибутивности получаем . Правая часть по закону поглощения равна A, то есть .

Однако, если взять вместо первого A отрицание A, то есть , то получим тождество: . Опять же по свойству дистрибутивности получаем: . Выражение равно нулю. Тогда .

ЗАДАНИЕ №7

Записать в виде логического выражения следующие рассуждения:

а) «Праздник состоится только в том случае, если на него придут Лена и Катя»

б) «Если число 56 делится на 7 и на 2, то оно делится на 14»».

Решение

а) А = {праздник состоится}, В = {Лена придет на праздник},

С = {Катя придет на праздник}. Тогда .

б) А = {число 56 делится на 7}, В = {число 56 делится на 2},

С = {число 56 делится на 14}. Тогда .

ЗАДАНИЕ №8

Доказать, что выражение * является тавтологией.

Решение

Тавтологией называется тождественно истинное выражение.

ЗАДАНИЕ №9

Областью определения предиката "" является:

1) ; 2) ; 3) ; 4) .

Решение

Областью определения предиката называется множество значений переменной х. В данном примере областью определения предиката является множество . При отрицательных значениях переменной или при x > 6 подкоренное выражение отрицательно, поэтому 1) и 2) не подходят. А т.к. x может принимать значения 0 и 2, то 4) также не подходит.

ЗАДАНИЕ №10

Указать, какие из следующих предложений являются формулами логики предикатов:

1) ; 2) ;

3) ; 4) .

Решение

1) не является формулой логики предикатов, т.к. квантор определен для всего выражения . То есть второй квантор (перед A(x,y)) лишний;

2) не является формулой, т.к. в конце пропущена закрывающая круглая скобка;

3) формула;

4) не формула: пропущена предметная переменная после квантора всеобщности.

ЗАДАНИЕ №11

Дан граф, изображенный на рис. 1. Записать матрицу смежности графа.

Рис. 1

Решение

Пронумеровали вершины графа.

Если ребро соединяет вершины i и j, то элемент матрицы aij равен 1. Если нет ребра, то 0.

Матрица смежности выглядит следующим образом

ЗАДАНИЕ №12

Указать все цепи, связывающие вершины и в графе, изображенном на рис. 2.

Рис. 2

Пронумеруем вершины. Здесь вершины А и В переобозначили. Будем искать цепи с началом в вершине 1 и с концом в вершине 3.

(1,2,3), (1,2,4,3), (1,2,4,5,3), (1,2,4,5,2,3), (1,2,4,5,2,6,5,3), (1,2,4,5,2,6,1,5,3), (1,2,4,5,6,2,3), (1,2,4,5,6,1,5.3), (1,2,4,5,6,1,5,2,3), (1,2,4,5,1,6,5,3), (1,2,4,5,1,6,5,2,3), (1,2,4,5,1,6,2,3), (1,2,5,3), (1,2,5,4,3), (1,2,5,4,2,3), (1,2,5,4,2,6,5,3), (1,2,5,4,2,6,1,5,3), (1,2,5,1,6,2,3), (1,2,5,1,6,5,3), (1,2,5,6,2,3), (1,2,5,6,1,5,3), (1,2,6,1,5,3), (1,2,6,1,5,2,3), (1,2,6,1,5,4,3), (1,2,6,1,5,2,4,3), (1,2,6,1,5,2,4,5,3), (1,2,6,1,5,4,2,5,3), (1,2,6,5,3), (1,2,6,5,2,3), (1,2,6,5,2,4,3), (1,2,6,5,2,4,5,3), (1,2,6,5,4,3), (1,2,6,5,4,2,3), (1,2,6,5,4,2,5,3), (1,5,3), (1,5,2,3), (1,5,2,4,3), (1,5,2,4,5,3), (1,5,2,6,5,3), (1,5,2,6,5,4,3), (1,5,2,6,5,4,2,3), (1,5,2,6,1,2,3), (1,5,2,6,1,2,4,3), (1,5,2,6,1,2,4,5,3), (1,5,2,1,6,2,3), (1,5,2,1,6,5,3), (1,5,2,1,6,5,4,3), (1,5,2,1,6,2,4,3), (1,5,2,1,6,2,4,5,3), (1,5,2,1,6,5,4,2,3), (1,5,4,3), (1,5,4,2,3), (1,5,4,2,5,3), (1,5,4,2,5,6,2,3), (1,5,4,2,5,6,1,2,3), (1,5,4,2,1,6,2,3), (1,5,4,2,1,6,5,3), (1,5,4,2,1,6,2,5,3), (1,5,4,2,1,6,5,2,3), (1,5,6,1,2,3), (1,5,6,1,2,5,3), (1,5,6,1,2,5,4,3), (1,5,6,1,2,5,4,2,3), (1,5,6,1,2,4,3), (1,5,6,1,2,4,5,2,3), (1,5,6,1,2,4,5,3), (1,5,6,2,3), (1,5,6,2,5,3), (1,5,6,2,5,4,3), (1,5,6,2,5,4,2,3), (1,5,6,2,4,3), (1,5,6,2,4,5,3), (1,5,6,2,4,5,2,3), (1,6,2,3), (1,6,2,4,3), (1,6,2,4,5,3), (1,6,2,4,5,2,3), (1,6,2,4,5,2,1,5,3), (1,6,2,4,5,1,2,3), (1,6,2,4,5,1,2,5,3), (1,6,2,5,3), (1,6,2,5,4,3), (1,6,2,5,4,2,3), (1,6,2,5,1,2,3), (1,6,2,5,1,2,4,3), (1,6,2,5,1,2,4,5,3), (1,6,5,3), (1,6,5,4,3), (1,6,5,4,2,3), (1,6,5,4,2,5,3), (1,6,5,4,2,5,1,2,3), (1,6,5,4,2,1,5,3), (1,6,5,4,2,1,5,2,3), (1,6,5,2,3), (1,6,5,2,4,3), (1,6,5,2,4,5,3), (1,6,5,2,1,5,3), (1,6,5,2,1,5,4,3), (1,6,5,2,1,5,4,2,3), (1,6,5,1,2,3), (1,6,5,1,2,4,3), (1,6,5,1,2,4,5,3), (1,6,5,1,2,4,5,2,3), (1,6,5,1,2,5,3), (1,6,5,1,2,5,4,3), (1,6,5,1,2,5,4,2,3).

ЗАДАНИЕ №13

На рис. 3 дан сетевой график. Требуется:

1) ввести обозначения вершин и ребер;

2) построить дерево путей сетевого графика туристического путешествия и найти по нему кратчайший маршрут движения.

Рис.3

Решение

Красным цветом выделены вершины графика.

Получившееся дерево. Красным выделен кратчайший путь (1,4,3,8,13), равный 19.

ЗАДАНИЕ №14

Волейбольная сетка имеет вид прямоугольника размером 50х600 клеток. Какое наибольшее число веревок можно перерезать так, чтобы сетка не распалась на куски?

Решение

Раскладываем сеть на плоскости, 1 ряд 600 ячеек. У первой ячейки не разрезаем левую веревочку, остальные вертикальные разрезаешь до конца, всего 600 разрезов, получается, что мы отрезали верхнюю веревку целиком по длине, которая держится на сети с помощью первой вертикальной веревочки.

Со вторым рядом поступаем так: не разрезаем последнюю вертикальную, а все остальные так же разрезаем.

Чередуя эти 2 способа, получим веревку вместо сетки, но выпавших кусков не будет. всего таких разрезов будет 50·600 = 30 000.

Таким образом, наибольшее число верёвок = 30 000

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.Электронные ресурсы

1. http://vk.com/math_help_student

2. http://www.matburo.ru/sub_subject.php?p=dm

3. http://www.examhelp.ru/

4. http://habrahabr.ru/company/surfingbird/blog/171279/

5. http://bankzadach.ru/diskretnaya-matematika.html

Размещено на Allbest.ru