Санкт-Петербургский Государственный Университет Телекоммуникаций им проф. М.А.Бонч-Бруевича

Министерство Российской Федерации
по связи и информатизации
Санкт-Петербургский государственный университет телекоммуникаций им. проф. Бонч-Бруевича
Факультет вечернего и заочного обучения
Е.Л.Рабкин, Ю.Б. Фарфоровская
Дискретная математика
Булевы функции и элементы теории графов
Методические указания и контрольные задания
Санкт-Петербург
2003

Стоимость выполнения контрольной работы по дискретной математике уточняйте при заказе.

Контрольное задание
Как правило, требуется решить задачи 1-10(пункт а), 11-20(пункт б), 21-30(без полинома Жигалкина), 31-40(пункт а), 41-50, 51-60(без нахождения сечений), 61-70

В заданиях 1–10 требуется привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка
В заданиях 11–20 требуется: в задаче а) написать по данной ДНФ полином Жегалкина, от ДНФ перейти к КНФ, а затем перейти к СКНФ; в задаче б) перейти от данной КНФ к ДНФ, а затем перейти к СДНФ.
В заданиях 21–30 требуется: составить таблицу истинности данной функции; написать для неё СДНФ и СКНФ (если возможно); найти по таблице истинности полином Жегалкина для данной функции; составить карту Карно для данной функции и найти сокращенную ДНФ.
В заданиях 31–40 с помощью карт Карно по данной таблице истинности для функции 4 переменных найти её сокращённую ДНФ.
В заданиях 41–50 составить таблицу Поста и найти базисы из следующих функций.
В задачах 51–60 требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути Pij из вершины i в вершину j, затем найти все сечения Sij между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет.
В заданиях 61–70 требуется найти в данной сети (т.е. в графе с заданными пропускными способностями ребер) максимальный поток из вершины с номером 1 в вершину с наибольшим номером (в заданиях либо вершину 5, либо 6). В заданиях заданы 2 графа (граф, который находится слева, – это сеть с заданными пропускными способностями ребер, и граф справа с заданным потоком, который необходимо либо улучшить, либо доказать, что он не улучшаем и, значит, является максимальным).

Вариант 0

Выполнены задачи 10а, 20б, 30, 40а, 50, 60, 70

Дата выполнения: 16/01/2013

Вариант 1

Выполнены задачи 1а, 11б, 21, 31а, 41, 51, 61

Дата выполнения: 23/04/2012

Вариант 2

Выполнены задачи 2а, 12б, 22, 32а, 42, 52, 62

Дата выполнения: 18/01/2013

Вариант 3

Выполнены задачи 3а, 13б, 23, 33а, 43, 53, 63

Дата выполнения: 18/01/2013

Вариант 4

Выполнены задачи 4а, 14б, 24, 34а, 44, 54, 64

Дата выполнения: 22/01/2013

Вариант 5

Выполнены задачи 5а, 15б, 25, 35а, 45, 55, 65

Дата выполнения: 18/01/2012

Вариант 6

Выполнены задачи 6а, 16б, 26, 36а, 46, 56, 66

Дата выполнения: 25/11/2012

Вариант 8

Выполнены задачи 8а, 18б, 28, 38а, 48, 58, 68

Дата выполнения: 23/01/2013

Вариант 9

Выполнены задачи 9а, 19б, 29, 39а, 49, 59, 69

Дата выполнения: 10/06/2010