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

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

Специальность: Прикладная информатика

Преподаватель: Прилуцкий М.Х.

Данная дисциплина относится к дисциплинам федерального компонента цикла математических и естественно-научных дисциплин, преподается в 1 семестре 1 курса обучения.
Содержание дисциплины направлено на ознакомление студентов с фундаментальными понятиями, основными определениями и методами дискретной математики, овладение математическим аппаратом, являющимся базовым для дальнейшего обучения. В курс включены основные понятия теории множеств, бинарных отношений, комбинаторного анализа и алгебры логики.
В результате освоения студенты должны:
Знать основные понятия теории множеств, бинарных отношений, комбинаторного анализа и алгебры высказываний.
Уметь доказывать основные теоремы теории множеств, бинарных отношений и алгебры высказываний, решать уравнения и системы уравнений в алгебре множеств, строить анкеты бинарных отношений, строить нормальные формы и определять функциональную полноту систем функций алгебры логики.
Иметь представление (навыки) о счетных и континуальных множествах, об (n,k) – выборках, о классах эквивалентности, о биективных соответствиях, о замкнутых классах функций алгебры логики.

Содержание

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

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

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Элементы комбинаторного анализа. (n,k)-выборки. Выборки упорядоченные, неупорядоченные, с повторениями, без повторений.

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

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

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

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

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

Литература

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.

Вопросы для экзамена

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

Отчетность

  • Семестр 1: Экз