в) найдите длину наименьшего цикла

 

Решение:

Цикл:                 

Маршрут:

Цепь:

 

 

Задания для контрольной работы.

Студент должен выполнить пять заданий того варианта, номер которого совпадает с последней цифрой шифра.

 

 

Вариант/Задания	1	2	3	4	5
1	1.1	2.1	3.1	4.1	5.1
2	1.2	2.2	3.2	4.2	5.2
3	1.3	2.3	3.3	4.3	5.3
4	1.4	2.4	3.4	4.4	5.4
5	1.5	2.5	3.5	4.5	5.5
6	1.6	2.6	3.6	4.6	5.1
7	1.7	2.7	3.7	4.7	5.2
8	1.8	2.8	3.8	4.8	5.3
9	1.9	2.9	3.9	4.9	5.4
10	1.10	2.10	3.10	4.10	5.5

Задание 1. Доказать тождество с помощью диаграммы Венна.

Задание 2. Определить свойства бинарного отношения , заданного на множестве . Построить матрицу бинарного отношения. Определить, является ли данное отношение отношением эквивалентности или порядка(строгого или нестрогого).

Задание 3 . По заданной суперпозиции

1) напишите формулу, реализующую функцию;

2) составьте таблицу истинности для этой функции;

3) найдите фиктивные переменные и исключите их, если они есть;

4) найдите двойственную функцию;

Напишите СДНФ и СКНФ

Задание 4. По заданной матрице смежности постройте неориентированный граф. Постройте матрицу инцидентности. Укажите маршрут, цепь, цикл в графе.

Определите, является ли граф эйлеровым.

Задание 5. Решите задачи

5.1)

1.    Скольким способами можно переставить буквы слова «ЛОГАРИФМ» так, чтобы второе, четвертое и шестое места всегда были заняты гласными буквами?

2.    Из 12 девушек и 10 юношей выбирают команду, состоящую из 5 человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей?

3.     Определите z из условия, что разность между пятым и третьим членами разложения равна 300.

5.2)

1. В состав сборной включены 2 вратаря, 5 защитников, 6 полузащитников и 6 нападающих. Сколькими способами тренер может выставить на поле команду, в которую входят вратарь, 3 защитника, 4 полузащитника и 3 нападающих?

2. Сколькими способами можно расставить10 книг на одной полке так, чтобы 3 определенные книги были поставлены рядом?

3. Найдите член разложения , содержащий .

5.3)

1. Сколько различных 7-значных чисел можно составить из цифр 2,2,3,3,3,4,4?

2. 30 человек голосуют по 5 предложениям. Сколькими способами могут распределиться голоса, если каждый голосует только за одно предложение ?

3. Определите x из условия, что пятый член разложения равен 5/9.

 

5.4)

1. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?

2. Сколько различных трёхзначных чисел можно составить с помощью цифр 7 и 3?

3. Найти члены разложения, являющиеся целыми числами

5.5)

 

1. На прививку в медпункт отправились 7 друзей. Сколькими разными способами они могут встать в очередь у медицинского кабинета?

2. При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей?

3. Найти член разложения , не содержащий x      

 

Вопросы к зачету

1.Множества. Способы задания множеств. Подмножества.

2.Теоретико-множественные операции над множествами.

3.Основные законы алгебры множеств.

4.Доказательство тождеств алгебры множеств с помощью законов алгебры множеств, диаграмм           Венна и кругов Эйлера.

5.Классификация множеств. Мощность множества. Булеан множества.

6.Прямое произведение. Мощность прямого произведения n множеств.

7.Бинарные отношения. Свойства бинарных отношений.

8.Функции алгебры логики. Основные законы алгебры логики.

9.Принцип двойственности. Самодвойственные функции.

10.Разложение булевых функций по переменным.

11.Полином Жегалкина. Способы нахождения полинома Жегалкина. Линейные функции.

12.Полнота системы булевых функций. Теорема о полноте второй системы булевых функций.

13.Монотонные функции.

14.Важнейшие замкнутые классы.

15.Лемма о несамодвойственной функции.

16. Лемма о немонотонной функции.

17. Лемма о нелинейной функции.

18.Критерий полноты системы булевых функций.

19.Понятия базиса и предполного класса. 20. Комбинаторные конфигурации. Бином Ньютона. Биномиальные коэффициенты.

21.Неориентированные графы. Виды графов. Маршруты, цепи и циклы графа.

22.Связность графов. Изоморфные графы.

23.Способы задания графов.

24.Теорема Эйлера и её следствия.

25.Плоские графы. Формула Эйлера.

26.Эйлеровы и гамильтоновы графы.

27.Деревья. Лес. Представление деревьев.

Литература.

 

1. Хаггарти Р. Дискретная математика для программистов – М.: Техносфера, 2005

4. Спирин П. А., Спирина М. С. Дискретная математика. – М.: Академия, 2004

2. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2004

3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988

4. Гончарова Г. А., Молчалин А. А. Элементы дискретной математики. М.: ИД «Форум» Инфра-М, 2003

5. Канцедал С.А. Дискретная математика: учебное пособие. - М.:ИД «Форум»: Интра-М,2007