Дисциплина: «Математика»
Контрольная работа по дискретной математике № 227358
Цена 250 р.
1. С помощью алгоритма Дейкстры найти путь минимального веса между вершинами s и t в нагруженном графе.
Решение:
Присваиваем вершине s метку 0, остальным вершинам метку …….
Первый шаг. Минимальную метку имеет вершина …….
2. Найти максимальный поток в заданной транспортной сети, используя алгоритм Форда-Фалкерсона. Проверить ответ по теореме Форда-Фалкерсона (найти минимальный разрез графа сети).
Решение:
Зададим на сети нулевой поток (на всех дугах …….
3. По матрице инцидентности построить остовное дерево графа. Составить список ветвей и хорд графа. Построить граф.
Решение:
Список непосещенных вершин: …….
4. а) Написать таблицу состояний данного автомата.
б) Считая автомат неициальным, построить эквивалентный автомат Мура. Проверить работу данного автомата и построенного автоматов над одним и тем же словом.
Решение:
Изобразим таблицу данного автомата …….
Выдержка из подобной работы:
….
Практическое задание по дискретной математике
…..
6. Составить матрицы отношений заданных на системе
множеств М = {a b
и Q.
7. Задать различными способами отношение R на
множестве M × M. Определить свойства данного отношения.
R – «быть больше». M = {3 7 8 12 15 16}
8. Пусть R1 и R2 – отношения на b): b = a + 1; a b Î b): b = a2 + 1; a b
Î R2°R2=R2.
9. Определить
пошагово значение истинностной функции при следующих заданных значениях
переменных.
1 Ú 2 => x1 )) & 1 => x2)
x1
0
0
1
1
x2
0
1
1
0
?
?
?
1 Ú
2 => x1 )) & 1 => x2)
10. Имеет ли место равносильность?
11. Привести к ДНФ и СДНФ:
12. Привести к КНФ и СКНФ:
13. Построить КНФ по заданной ДНФ:
14. Построить СДНФ и СКНФ для функции 1 x2 x3)
со следующей таблицей истинности:
x1
x2
x3
1 x2 x3)
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
{
w[] || [];
w[h {
asy:
});
});
[0];
})h .d
0
0
1
1
1
1
15 . Пусть P1 и P2 обозначают
высказывания:
P1 –эти прямые
перпендикулярны
P2 –эти прямые имеют
точку пересечения.
Записать как читаются следующие символические
выражения:
а) Ø P1
б) P1 Ú P2
в) P1 & P2
г) P1 Þ P2
д) P1 Û P2
е) P1 Å P2
Определить истинность выражения если это возможно.
16. Следующие сложные высказывания расчленить на
простые и записать с помощью математической символики:
а) на улице идет дождь значит надо взять зонт
б) на каникулы Лена поедет либо в Испанию либо в
Италию
в) кот Вася любит есть рыбу и играть в мячик.
17. Связать свободную переменную квантором так что бы
получить истинное высказывание :
а)
б)
в)
г)
18. Пусть P y) – двухместный предикат «окружность x вписана в треугольник y».
Записать высказывания определить значения их истинности построить отрицания
данных высказываний:
.
19. Записать высказывания в предикатной форме
используя кванторы. Построить отрицания а затем перевести обратно в
литературное высказывание так что бы отрицание не начиналось со слов «не» или
«неверно что»:
В каждом городе хотя бы одна улица застроена только
такими домами в которых есть однокомнатные квартиры.
РЕШЕНИЕ
1. а) Трапеция — четырехугольник у
которого о»