Файл: Контрольная работа Вариант 3 Фамилия Чудинов Имя Кирилл Отчество.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.11.2023
Просмотров: 96
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕУЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»(СПбГУТ)ИНСТИТУТ НЕПРЕРЫВНОГО ОБРАЗОВАНИЯДисциплина: Дискретная математикаКонтрольная работа Вариант 3Фамилия:___Чудинов____Имя:___Кирилл____Отчество:_Витальевич__Группа №:____РБ-11з______Проверил:______________Санкт-Петербург2023Задание 1Используя правила Моргана получить ДНФ функции и упростить полученную ДНФf.РешениеЗадание 2Даны две функции f1 (x, y), f2 (x, y, z). Требуется:а) для функции f1 (x, y) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. Упростить, если возможно, СДНФ. б) для функции f2 (x, y, z) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную РКС. в) составить таблицу Поста для системы функций f1 (x, y), f2 (x, y, z), проверить полноту системы и выбрать базисы, если она полная.Решениеа) Составим таблицу истинности:
Составим по наборам для которых Упростим СДНФСоставим по наборам для которых Составим полином Жегалкина:б) Составим таблицу истинности:
Составим по наборам для которых Составим по наборам для которых Составим полином Жегалкина:Заполним карту Карно:Составим РКС:Таблица Поста имеет вид:
Так как:, не линейная, содержит , не линейная, содержит
Система функций полная, т.к. в таблице Поста нет столбца из одних «+». Проверяем на полноту каждую функцию: - не составляет полной системы, т.к. нет функции не входящей в классы L, M и S. - образует полную систему и является базисом. Других базисов нет.Задание 3Задан граф:Составить для данного графа структурную матрицу. Найти:а) все простые пути из вершины в вершину ;б) совокупность всех сечений между вершинами и .РешениеСтруктурная матрица имеет вид:Из структурной матрицы S, а затем вычеркнем из неё 1-ю строчку и 4-й столбец, тем самым получив минор M14. Согласно теореме разложения определитель равен дизъюнкции (сумме) произведений элементов любой строки (или столбца), умноженных на свои алгебраические дополнения (в данном случае миноры).Использованные при упрощении свойства: При записи ответа рёбра идут в порядке прохождения вершин от и .Для нахождения сечений между вершинами и . заменим дизъюнкцию на конъюнкцию, а конъюнкцию на дизъюнкцию и раскроем скобки.
Задание 4Задана сеть и начальный поток f. Требуется построить максимальный поток, считая вершину с номером 1 источником и вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна максимальному потоку.РешениеПоток fиз в имеет величину Путь из в : Пометки вершин: Добавка к потоку: Строим новый поток : Путь из s в t, на котором возможно увеличение потока не построить, поскольку невозможно дойти до стока. Значит поток , построенный на основе заданного в условии, максимален: .Помеченная вершина: = {1}.Непомеченные вершины: = {3,2,4}.Построим начальный поток иначе:Поток fиз в имеет величину Путь из
 |  |  |  | Коэффициенты полинома Жегалкина | |
| 1 | 1 | 0 | 1 |  |  |
| 1 | 0 | 1 | 0 |  |  |
| 0 | 1 | 1 | 1 |  |  0 |
| 0 | 0 | 0 | 1 |  |  |
Составим по наборам для которых Упростим СДНФСоставим по наборам для которых Составим полином Жегалкина:б) Составим таблицу истинности:
 |  |  |  |  |  |  | Коэффициенты полинома Жегалкина | |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 |  |  0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 |  |  |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |  |  0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 |  |  |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |  |  |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 |  |  |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 |  |  1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |  |  |
Составим по наборам для которых Составим по наборам для которых Составим полином Жегалкина:Заполним карту Карно:Составим РКС:Таблица Поста имеет вид:
| Функция |  |  | S | M | L |
 | - | + | - | - | - |
 | - | - | - | - | - |
Система функций полная, т.к. в таблице Поста нет столбца из одних «+». Проверяем на полноту каждую функцию: - не составляет полной системы, т.к. нет функции не входящей в классы L, M и S. - образует полную систему и является базисом. Других базисов нет.Задание 3Задан граф:Составить для данного графа структурную матрицу. Найти:а) все простые пути из вершины в вершину ;б) совокупность всех сечений между вершинами и .РешениеСтруктурная матрица имеет вид:Из структурной матрицы S, а затем вычеркнем из неё 1-ю строчку и 4-й столбец, тем самым получив минор M14. Согласно теореме разложения определитель равен дизъюнкции (сумме) произведений элементов любой строки (или столбца), умноженных на свои алгебраические дополнения (в данном случае миноры).Использованные при упрощении свойства: При записи ответа рёбра идут в порядке прохождения вершин от и .Для нахождения сечений между вершинами и . заменим дизъюнкцию на конъюнкцию, а конъюнкцию на дизъюнкцию и раскроем скобки.
Задание 4Задана сеть и начальный поток f. Требуется построить максимальный поток, считая вершину с номером 1 источником и вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна максимальному потоку.РешениеПоток fиз в имеет величину Путь из в : Пометки вершин: Добавка к потоку: Строим новый поток : Путь из s в t, на котором возможно увеличение потока не построить, поскольку невозможно дойти до стока. Значит поток , построенный на основе заданного в условии, максимален: .Помеченная вершина: = {1}.Непомеченные вершины: = {3,2,4}.Построим начальный поток иначе:Поток fиз в имеет величину Путь из