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

 

 

Министерство образования Российской Федерации Международный институт «ИНФО-Рутения»

 

РГГРУ

 

 

 

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

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

Тема контрольной работы

 

Вариант № 2

 

 

№17269____________Минина Н.В.___________________

ф.и.о. студента

 

 

 

   

    

___________________________

Дата исполнения работы

 

_____2______________с 1 по 8_____

Семестр                         Цикл обучения

 

 

 

____________________________________

Дата регистрации работы в Региональном представительстве ИНФО

 

 

___________________________________

Подпись ответственного за регистрацию

 

 

 

 

 

 

 

____________________г. Старая Русса__________________________

Наименование Регионального представительства ИНФО

 

 

 

Контрольное задание №1 

Задача №1. Дано одношаговое  рекуррентное соотношение с начальным условием . Найти 7-й член последовательности .

Решение. Чтобы найти 7-й член последовательности по рекуррентному соотношению, нужно найти все предыдущие. Нулевой член последовательности задан. Чтобы найти первый элемент, поставим в правую часть рекуррентного соотношения. Такая подстановка соответствует присваиванию и можно найти и т.д. Следовательно: 
. Поставив , получим . .

.

.

.

.

.

Ответ: . 
 
Задача №2. Вычислить .

Решение. .

Задача №3. Решить уравнение .

Решение. . После сокращения получаем . Найдем корни полученного уравнения: .

Ответ: .

Задача №4. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

Решение. Поскольку порядок в выборке из трех дежурных является не существенным,  такая выборка будет неупорядоченной. Поэтому, количество способов, которыми можно выбрать трех дежурных из группы в 20 человек определится сочетанием из 20 человек по 3 дежурным. В результате получим .

Ответ: 1140 способов.

Задача №5. Даны 2 множества: . Найти их:

1. Объединение . 
   Ответ: ;
2. Пересечение . 
   Ответ: ;
3. Разность . 
   Ответ : ;
4. Симметричную разность . 
   Ответ: .

 

Контрольное задание №2 

 

Задача №1. Построить полный поток в транспортной сети G, приведенной на рисунке (цифрами даны пропускные способности дуг).

 

 

 

 

 

 

 

 

 

 

Решение. Начинаем с нулевого потока, пологая .

 

 

 

 

 

 

 

 

При нулевом потоке отсутствуют насыщенные дуги. Выделим в G простую цепь и увеличим потоки по дугам на 3 до насыщения дуги ( ). В результате получим поток , содержащий одну насыщенную дугу.. Пометим ее крестиком и удалим из орграфа, который снова обозначим .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги ( ). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

 

 

 

 

 

 

 

 

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги ( ). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

 

 

 

 

 

 

 

 

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги ( ). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

 

 

 

 

 

 

 

 

 

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги ( ). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

 

 

 

 

 

 

 

 

В оставшемся не существует пути их , который не содержал бы насыщенных дуг, т.е. поток является полным и его величина равна 13.

 

Задача №2. По данному логическому выражению построить таблицу истинности без предварительного упрощения функции.

.

Построим таблицу истинности по частям, предварительно построив таблицу истинности для каждой конъюнкции, а затем в последнем столбце запишем логическую сумму (дизъюнкцию) соответствующих значений трех конъюнкций .

 

А	В	С					F
0	0	0	1	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	1	1	0	0	0	0	0
1	0	0	1	0	0	0	0
1	0	1	1	0	1	0	1
1	1	0	0	0	0	0	0
1	1	1	0	1	0	1	1

 

Логические переменные А, В и С принимают всего значений, причем в таком порядке, что если перевести приведенные триады из двоичной системы в десятичную то получим числа от 0 до 7. В столбцах 5, 6 и 7 приведены элементарные конъюнкции, значения которых определяются перемножение соответствующих  логических переменных. Значения дизъюнкций, приведенное в 8 столбце таблицы, определяется суммой соответствующих конъюнкций.

Задача №3. Функция задана десятичными эквивалентами единичных значений. Представить эту функцию в виде СДНФ или в виде СКНФ.

.

Поскольку в списке 14 чисел, т.е. 14 эквивалентов единичных значений, следовательно нулевых значений два (16-14=2). Поэтому по таблице истинности целесообразней строить СКНФ.

Построим таблицу истинности. В первом столбце укажем десятичные эквиваленты соответствующих наборов.

 

	N					F
	0	0	0	0	0	0
	1	0	0	0	1	0
	2	0	0	1	0	0
	3	0	0	1	1	0
	4	0	1	0	0	0
	5	0	1	0	1	0
	6	0	1	1	0	0
	7	0	1	1	1	0
	8	1	0	0	0	0
	9	1	0	0	1	1
	10	1	0	1	0	1
	11	1	0	1	1	0
*	12	1	1	0	0	0
*	13	1	1	0	1	0
	14	1	1	1	0	1
	15	1	1	1	1	1

 

В таблице звездочками отмечены строчки, в которых расположены наборы значений переменных, на которых функция равна нулю. Справа напротив этих строк показаны полные элементарные функции, которые на соответствующих наборах равны нулю. СКНФ находится как конъюнкция этих дизъюнкций и будет иметь вид: .

Задача №4. Упростить логические выражения с помощью карты Карно.

.

Известно, что конъюнкции соответствует пересечение областей карты Карно, соответствующих сомножителям, а дизъюнкции соответствует объединение областей, соответствующих слагаемым. Конъюнкции второго ранга на карте Карно соответствует 4 клеточки. Затененная область на рис.1,2,3 соответствует конъюнкциям  соответственно. На рис.4 показано пересечение областей, соответствующих множителям . В соответствующих клетках пересечения областей стоят единицы и штриховкой показана область клеток для переменной .

	В						В
А						А
					С						С
		D						D

        Рис.1. Область                                                Рис.2. Область

 

	В						В
А						А
					С		1			1	С
										1
		D						D

 

        Рис.3. Область                                Рис.4. Заполнение карты Карно для

                                                                         

Клетки имеющие затенение и штриховку одновременно соответствуют исходной функции. Объединив эти три единицы в две пары, получим представление исходной функции в виде дизъюнкции двух конъюнкций третьего ранга .