факультет ВМК Кафедра информатики и автоматизации научных исследований

• Главная
• Коллектив
• Структура
• Научная деятельность
• Учебные курсы
• Обеспечение
• Участие кафедры в хоздоговорной тематике
• Защиты диссертаций

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

1. Область применения

Данная дисциплина относится к дисциплинам федерального компонента цикла математических и естественно-научных дисциплин, преподается в 1 семестре 1 курса обучения.

2. Цель и задачи дисциплины

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

3. Требования к уровню освоения содержания дисциплины

В результате освоения студенты должны:

Знать основные понятия теории множеств, бинарных отношений, комбинаторного анализа и алгебры высказываний.

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

Иметь представление (навыки) о счетных и континуальных множествах, об (n,k) — выборках, о классах эквивалентности, о биективных соответствиях, о замкнутых классах функций алгебры логики.

4. Объём дисциплины и виды учебной работы

Виды учебной работы	1 семестр
Общая трудоемкость дисциплины	70
Аудиторные занятия	54
Лекции	36
Практические занятия (ПЗ)	18
Самостоятельная работа	16
Вид итогового контроля	экзамен

5. Содержание дисциплины

5.1. Разделы дисциплины и виды занятий

№ п/п	Раздел дисциплины	Лекции	ПЗ (или С)
1	Множества	12	6
2	Бинарные отношения	6	4
3	Элементы комбинаторики	2
4	Алгебра логики	16	8

5.2. Содержание разделов дисциплины

МНОЖЕСТВА

Множества. Конечные и бесконечные множества. Способы задания множеств. Подмножества. Множество всех подмножеств данного множества. О числе к-элементных подмножеств n-элементного множества. Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона). Универсальное множество. Понятие алгебры. Алгебра множеств. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами. Законы алгебры множеств. Двойственность в алгебре множеств. Уравнения и системы уравнений в алгебре множеств. Основные леммы, используемые при решении уравнений в алгебре множеств. Мощность множества. Понятие счетного множества и континуума. Канторовская диагональная процедура. Примеры счетных множеств. Доказательство счетности множества алгебраических чисел. Свойства счетных множеств. Необходимые и достаточные условия бесконечности множества. Примеры континуальных множеств. Теорема Кантора-Бернштейна. Доказательство существования иррациональных и трансцендентных чисел. Кардинальные операции над множествами. Прямое произведение множеств. Проекция множеств.

БИНАРНЫЕ ОТНОШЕНИЯ

Бинарные отношения. Свойства бинарных отношений. Представления бинарных отношений в виде матриц, орграфов, верхнего и нижнего сечений. Операции над бинарными отношениями. Выражение свойств бинарных отношений через задающие их множества. Отношения порядка. Упорядоченные множества. Отношение эквивалентности. Классы эквивалентности. Системы различных представителей. Лексикографическое отношение порядка. Мажоранта и миноранта множеств. Максимум и минимум множеств. Точные грани множеств. Понятие графика. Функциональные, инъективные графики. Инверсия графика. Соответствия. Функциональные, инъективные, сюръективные и биективные соответствия. Общее понятие функции. Биективная функция.

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Элементы комбинаторного анализа. (n,k)-выборки. Выборки упорядоченные, неупорядоченные, с повторениями, без повторений.

АЛГЕБРА ЛОГИКИ

Высказывания. Операции над высказываниями. Алгебра логики. Формулы и функции алгебры логики. О числе функций алгебры логики от n переменных. Равносильные формулы. Законы алгебры логики. ДНФ и КНФ. Разложение функций алгебры логики по к переменным. СДНФ и СКНФ. Логические следствия. Проблема разрешимости в алгебре логики. Тавтологии и противоречия. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев. Суперпозиция функций алгебры логики. Полные системы функций. Понятие базиса. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Замкнутые классы функций. Линейные функции. Монотонные функции. Теорема о монотонных функциях. Двойственность в алгебре высказываний. Самодвойственные функции. Функции сохраняющие константы 0, 1. Теорема Поста о функциональной полноте.

Практические занятия.

1. Понятие множества. Конечные и бесконечные множества. Способы задания множеств. Подмножества. Равенство множеств. Множество всех подмножеств конечного множества. Пустое и универсальное множество.
2. Алгебраические и кардинальные операции над множествами.
3. Законы алгебры множеств. Уравнения и системы уравнений.
4. Бинарные отношения.
5. Высказывания. Операции над высказываниями.
6. Формулы алгебры логики.
7. Истинностные таблицы для сложных высказываний.
8. ДНФ и КНФ. Приведение к ДНФ и КНФ.
9. СДНФ и СКНФ. Приведение к СДНФ и СКНФ.
10. Проверка полноты систем функций алгебры логики.

6. Лабораторный практикум

Не предусмотрен.

7. Учебно-методическое обеспечение дисциплины

7.1 Рекомендуемая литература

а) Основная литература

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

б) Дополнительная литература

1. Новиков П. С. Элементы математической логики. М. Наука. 1973.
2. Колмогоров А. Н., Фомин С. В. Введение в теорию функций и функциональный анализ. М. Наука. 1976.
3. Шрейдер Ю. А. Равенство, сходство, порядок. М. Наука. 1971.
4. Горбатов В. А. Основы дискретной математики. М. Высшая школа. 1986.
5. Шиханович Ю. А. Введение в современную математику. М. Наука. 1965.
6. Фор Р., Кофман А., Дени-Папен М. Современная математика. М. Мир. 1966.
7. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М. Наука 1977.
8. Виленкин Н. Я. Комбинаторика. М. Наука. 1969
9. Прилуцкий М. Х. Дискретная математика. Метод. пособие для студентов факультета ВМК,
   специальности 351400 «Прикладная информатика». Н. Новгород. Нижег. гос.ун-т. 2006.

8. Вопросы для контроля

Вопросы к экзамену.

1. Множества. Конечные и бесконечные множества. Способы задания множеств.
2. Подмножества. Множество всех подмножеств данного множества.
3. О числе к-элементных подмножеств n-элементного множества.
4. Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона).
5. Универсальное множество. Понятие алгебры. Алгебра множеств.
6. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами.
7. Законы алгебры множеств. Двойственность в алгебре множеств.
8. Уравнения и системы уравнений в алгебре множеств. Основные леммы, используемые при решении уравнений в алгебре множеств.
9. Мощность множества. Понятие счетного множества и континуума.
10. Канторовская диагональная процедура. Примеры счетных множеств.
11. Доказательство счетности множества алгебраических чисел.
12. Свойства счетных множеств. Необходимые и достаточные условия бесконечности множества.
13. Примеры континуальных множеств. Теорема Кантора-Бернштейна.
14. Доказательство существования иррациональных и трансцендентных чисел.
15. Кардинальные операции над множествами. Прямое произведение множеств. Проекция множеств.
16. Бинарные отношения. Свойства бинарных отношений.
17. Представления бинарных отношений в виде матриц, орграфов, верхнего и нижнего сечений.
18. Операции над бинарными отношениями. Выражение свойств бинарных отношений через задающие их множества.
19. Отношения порядка. Упорядоченные множества.
20. Отношение эквивалентности. Классы эквивалентности. 21. Лексикографическое отношение порядка.
21. Мажоранта и миноранта множеств. Максимум и минимум множеств. Точные грани множеств.
22. Понятие графика. Функциональные, инъективные графики. Инверсия графика.
23. Соответствия. Функциональные, инъективные, сюръективные и биективные соответствия.
24. Общее понятие функции. Биективная функция.
25. Высказывания. Операции над высказываниями. Формулы и функции алгебры логики.
26. О числе функций алгебры логики от n переменных.
27. Равносильные формулы. Законы алгебры логики.
28. ДНФ и КНФ.
29. Разложение функций алгебры логики по к переменным.
30. СДНФ и СКНФ.
31. Логические следствия. Проблема разрешимости в алгебре логики.
32. Тавтологии и противоречия.
33. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев.
34. Суперпозиция функций алгебры логики.
35. Полные системы функций. Понятие базиса.
36. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина.
37. Замкнутые классы функций.
38. Линейные функции.
39. Монотонные функции. Теорема о монотонных функциях.
40. Двойственность в алгебре высказываний. Самодвойственные функции.
41. Функции сохраняющие константы 0, 1.
42. Лемма о получении константы.
43. Лемма о получении отрицания.
44. Лемма о получении конъюнкции.
45. Теорема Поста о функциональной полноте.

Экзаменационные билеты

Билет № 1

1. Найти мощность множеста всех к элементных подмножеств n злементного множества.
2. Доказать, что множество всех многочленов с рациональными коэффициентами счетно.
3. Логическое следствие. Основные схемы доказательств.

Билет № 2

1. Алгебраические и кардинальные операции над множествами.
2. Способы задания бинарных отношений.
3. Класс самодвойственных функций.

Билет № 3

1. Доказать, что объединение любого конечного или счетного числа счетных множеств есть счетное множество.
2. Свойства бинарных отношений.
3. Класс монотонных функций. Замкнутость класса монотонных функций.

Билет № 4

1. Доказать, что всякое бесконечное множество эквивалентно некоторому своему истинному подмножеству.
2. Отношение эквивалентности. Классы эквивалентности. Отношение порядка.
3. Алгебра Жегалкина. Построение полинома Жегалкина. Теорема Жегалкина.

Билет № 5

1. Доказать, что множество действительных чисел, заключенных между 0 и 1 несчетно.
2. Точные грани множеств.
3. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина.

Билет № 6

1. Теорема Кантора-Бернштейна.
2. Законы алгебры логики.
3. Логическое следствие. Основные схемы доказательств.

Билет № 7

1. Доказать, что │P(M)│>│M│.
2. ДНФ и КНФ.
3. Доказать полноту системы функций F={,xvy,xy}.

Билет № 8

1. Кардинальные операции над множествами.
2. Преблема разрешимости в алгебре высказываний.
3. Решение уравнений в алгебре множеств.

Билет № 9

1. Проекция множеств.
2. Операции над отношениями.
3. СДНФ. Алгоритмы построения.

Билет №10

1. Доказательство основных лемм, используемых при решении уравнений в алгебре множеств.
2. Лексикографическое отношение порядка.
3. Разложение функции алгебры логики по k переменным.

Билет №11

1. Доказать, что множество тогда и только тогда бесконечно, если оно эквивалентно собственному подмножеству.
2. Операции над бинарными отношениями.
3. СДНФ. Алгоритмы построения.

Билет №12

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

Билет №13

1. Лемма о получении константы из несамодвойственной функции.
2. Представления бинарных отношений.
3. Теорема Кантора-Бернштейна.

Билет №14

1. Доказать формулу бинома Ньютона.
2. График. Функциональность. Композиция графиков. Инверсия.
3. Теорема о функциональной полноте. Примеры полных систем функций.

Билет №15

1. Доказать, что объединение любого конечного или счетного числа счетных множеств есть счетное множество.
2. Соответствия. Функции. Функциональность, инъективность, всюду определенность, сюръективность, биективность.
3. Лемма о получении из немонотонной функции отрицание.

Билет №16

1. Доказать, что всякое бесконечное множество эквивалентно некоторому своему истинному подмножеству.
2. Отношение порядка. Упорядоченные множества.
3. Алгебра Жегалкина. Построение полинома Жегалкина. Теорема Жегалкина.

Билет №17

1. Доказать, что множество действительных чисел, заключенных между 0 и 1 несчетно.
2. Доказать, что множество тогда и только тогда бесконечно, если оно эквивалентно собственному подмножеству.
3. СДНФ. Алгоритмы построения.

Билет №18

1. Операции над множествами. Алгебра множеств.
2. Лексикографическое отношение порядка. Выражение свойств бинарных отношений через множества, их определяющие.
3. Алгебра Жегалкина. Теорема Жегалкина. Полином Жегалкина.

Билет №19

1. Доказать, что │P(M)│>│M│.
2. Точные грани множеств.
3. СКНФ. Алгоритмы построения.

Билет №20

1. Лемма о получении из нелинейной функции конъюнкции.
2. Точные грани множеств.
3. СКНФ. Алгоритмы построения.

Билет №21

1. Доказательство основных лемм, используемых при решении уравнений в алгебре множеств.
2. Способы задания бинарных отношений.
3. Логическое следствие. Основные схемы доказательств.

Билет №22

1. Решение систем уравнений в алгебре множеств.
2. Отношение эквивалентности. Классы эквивалентности. Отношение порядка.
3. Доказательство теоремы Поста.

Билет №23

1. Доказать, что множество тогда и только тогда бесконечно, если оно эквивалентно собственному подмножеству.
2. Операции над отношениями.
3. Преблема разрешимости в алгебре высказываний.

Билет №24

1. Доказать, что множество натуральных чисел не эквивалентно множеству действительных чисел, заключенных в интервале между 0 и 1.
2. Лексикографическое отношение порядка. Выражение свойств бинарных отношений через множества, их определяющие.
3. ДНФ и КНФ. Алгоритмы построения.

Билет №25

1. Доказать, что множество всех многочленов с рациональными коэффициентами счетно.
2. Точные грани множеств.
3. Логическое следствие. Доказать, что если B <= A, то <= A → B.

Билет №26

1. О числе k элементных подмножеств n элементного множества.
2. График. Функциональность. Композиция графиков. Инверсия.
3. Класс монотонных функций. Теорема о монотонности логических функций. Замкнутость класса монотонных функций.

Билет №27

1. Доказать, что множество действительных чисел, заключенных между 0 и 1 несчетно.
2. Отношение эквивалентности. Классы эквивалентности. Отношение порядка.
3. Алгебра Жегалкина. Полиномы Жегалкина. Теорема Жегалкина.

Билет №28

1. Логическое следствие. Доказать, что если
2. Точные грани множеств.
3. Соответствия. Функции. Функциональность, инъективность, всюду определенность, сюръективность, биективность.

Билет №29

1. Найти мощность множества всех к элементных подмножеств n элементного множества.
2. Операции над отношениями.
3. Точные грани множеств.

Билет №30

1. Операции над множествами. Алгебра множеств.
2. Доказать, что всякое бесконечное множество эквивалентно некоторому своему истиному подмножеству.
3. Разложение функции алгебры логики от n переменных по k переменным.

9. Критерии оценок

Превосходно	В совершенстве владеет всем материалом, включая разделы, предложенные для изучения в рамках самостоятельной работы.
Отлично	В совершенстве владеет всем материалом курса.
Очень хорошо	Владеет всем материалом курса, но допускает неточности в изложении.
Хорошо	Знает основные определения курса, может доказать основные теоремы.
Удовлетворительно	Знает основные определения курса, но не может доказать основные теоремы.
Неудовлетворительно	Не знает основных определений курса.
Плохо	Не знает основных определений курса, не знает содержание курса.

10. Примерная тематика курсовых работ и критерии их оценки

Курсовой работы нет.

Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности
080801 «ПРИКЛАДНАЯ ИНФОРМАТИКА».