Дополнительная литература для преподавателя

1. Аляев, Ю.А. Дискретная математика и математическая логика / Ю.А. Аляев, С.Ф. Тюрин. М.: Финансы и статистика, 2006. 368 с.

2. Асеев, Г.Г. Дискретная математика / Г.Г. Асеев, О.М. Абрамов, Д.Э. Ситников. Ростов: Феникс, 2003. 144 с.

3. Виленкин, Н.Я. Комбинаторика / Н.Я. Виленкин. М.: Наука, 1969. 328 с.

4. Виленкин, Н.Я. Комбинаторика / Н.Я. Виленкин, А.Н. Виленкин, П.А. Виленкин. М.: ФИМА – МНЦО, 2006. 400 с.

5. Владимиров, Д.А. Теория булевых алгебр / Д.А. Владимиров. Спб.: Изд-во Санкт-Петербургского университета, 2000. 616 с.

6. Гаврилов, Г.П. Задачи и упражнения по дискретной математике / Г.П.Гаврилов, А.А.Сапоженко. М.: ФИЗМАТЛИТ, 2004. 416 с.

7. Гиндикин, С.Г. Алгебра логики в задачах / С.Г. Гиндикин. М.: Наука, 1972. 288 с.

8. Гладкий, А.В. Математическая логика / А.В. Гладкий. М.: Рос. гос. гуманит. ун-т, 1998. 479 с.

9. Горбатов, В.А. Дискретная математика / В.А. Горбатов, А.В. Горбатов, М.В. Горбатова. М.: АСТ, 2003, 448 с.

10. Гудстейн, Р.Л. Математическая логика / Р.Л. Гудстейн. М.: ИЛ, 1961. 162 с.

11. Емеличев, В.А. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990. 384 с.

12. Ершов, Ю.Л. Математическая логика / Ю.Л. Ершов, Е.А. Палютин. М.: Наука, 1979. 320 с.

13. Игошин, В.И. Математическая логика и теория алгоритмов / В.И. Игошин. М.: Академия, 2004, 448 с.

14. Карри, Х. Основания математической логики / Х. Карри. М.: Мир, 1969. 568 с.

15. Клини, С.К. Введение в метаматематику / С.К.Клини. М.: ИЛ, 1957. 529 с.

16. Клини, С.К. Математическая логика / С.К.Клини. М.: УРСС, 2005. 482 с.

17. Коваленко, С.И. Решение задач по математической логике с использованием элементарной алгебры / С.И. Коваленко. М.: ФИЗМАТЛИТ, 2004. 80 с.

18. Колмогоров, А.Н. Математическая логика / А.Н. Колмогоров, А.Г. Драгалин. М.: УРСС, 2006. 240 с.

19. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. М.: Мир, 1978. 432 с.

20. Кук, В. Компьютерная математика / В. Кук, Г. Бейз. М.: Наука, 1990. 384 с.

21. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. М.: Мир, 1970. 416 с.

22. Матросов, В.Л. Лекции по дискретной математике / В.Л. Матросов, В.Н. Стеценко. М.: МПГУ, 1997. 220 с.

23. Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. М.: Наука, 1971. 320 с.

24. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях / Г.И. Москинова. М.: Логос, 2004. 240 с.

25. Нефёдов, В.Н. Курс дискретной математики / В.Н. Нефёдов, В.А. Осипова. М.: МАИ, 1992. 264 с.

26. Новиков, П.С. Элементы математической логики / П.С. Новиков. М.: Наука, 1973. 400 с.

27. Оре, О. Теория графов / О. Оре. М.: Наука, 1980. 336 с.

28. Риордан, Дж. Введение в комбинаторный анализ / Дж. Риордан. М.: Изд-во иностранной литературы, 1963. 287 с.

29. Риордан, Дж. Комбинаторные тождества / Дж. Риордан. М.: Наука, 1982. 255 с.

30. Рыбников, К.А. Введение в комбинаторный анализ / К.А. Рыбников. М.: Изд-во МГУ, 1985. 312 с.

31. Сачков, В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.: МЦМНО, 2004. 424 с.

32. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 1984. 455 с.

33. Соболева, Т.С. Дискретная математика / Т.С. Соболева, А.В. Чечкин. М.: Академия, 2006. 255 с.

34. Судоплатов, С.В. Дискретная математика / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2007. 256 с.

35. Судоплатов, С.В. Элементы дискретной математики / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2002. 288 с.

36. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. 208 с.

37. Фудзисава, Т. Математика для радиоинженеров. Теория дискретных структур / Т. Фудзисава, Т. Касами. М.: Радио и связь, 1984. 240 с.

38. Харари, Ф. Теория графов / Ф. Харари. М.:УРСС, 2006. 296 с.

39. Холл, М. Комбинаторика / М. Холл. М.: Мир, 1970. 424 с.

40. Чёрч, А. Введение в математическую логику. Том 1 / А. Чёрч. М.: ИЛ, 1960. 488 с.

41. Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. М.: Высшая школа, 2003. 384 с.

42. Яблонский, С.В. Функции алгебры логики и классы Поста / С.В. Яблонский, Г.П. Гаврилов, В.Б. Кудрявцев. М.: Наука, 1966. 120 с.

ПРИЛОЖЕНИЕ № 1. Перечень вопросов для проверки практических

навыков студентов по дисциплине «Математические основы теории систем»

1. Доказательство тождеств с множествами.

2. Построение булеана данного множества.

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

4. Правила суммы и произведения.

5. Решение задач на основные формулы комбинаторики (перестановки, размещения, сочетания).

6. Бином Ньютона.

7. Свойства биномиальных коэффициентов.

8. Формула включений и исключений.

9. Нахождение производящей, экспоненциальной производящей функции для данной последовательности.

10. Нахождение последовательности, для которой данная функция является производящей, экспоненциальной производящей.

11. Действия над производящими функциями.

12. Применение производящих функций для доказательства комбинаторных тождеств.

13. Производящие функции выборок для некоторых схем выбора.

14. Экстремальные задачи теории графов (алгоритм Дейкстры, Беллмана-Мура, Прима, нахождения максимального пути и др.).

15. Алгоритм Форда-Фалкерсона.

16. Алгоритм построения потока минимальной стоимости.

17. Распознавание формул алгебры логики.

18. Метод истинностных таблиц в алгебре логики: построение таблиц истинности булевых функций, доказательство эквивалентности формул, выяснение тождественной истинности (ложности), выполнимости (опровержимости) формулы.

19. Основные эквивалентные формулы алгебры логики. Доказательство эквивалентности, упрощение формул алгебры логики, выяснение тождественной истинности (ложности), выполнимости (опровержимости) формулы методом эквивалентных преобразований.

20. Приведение булевой функции к ДНФ.

21. Приведение булевой функции к СДНФ по таблице истинности и алгебраически.

22. Приведение булевой функции к КНФ.

23. Приведение булевой функции к СКНФ по таблице истинности и алгебраически.

24. Приведение булевой функции к полиному Жегалкина методом неопределённых коэффициентов и с помощью эквивалентных преобразований.

25. Построение РКС.

26. Нахождение булевой функции, реализуемой данной РКС.

27. Построение сокращенной ДНФ методом Блейка, Нельсона, Квайна, карт Карно.

28. Методы построения тупиковых, минимальных и кратчайших ДНФ.

ПРИЛОЖЕНИЕ № 2. Перечень вопросов необходимого минимума для получения положительной оценки на экзамене по курсу «Математические основы теории систем»

1. Множество. Равенство множеств. Пустое множество, универсум.

2. Подмножество. Собственное и несобственное подмножество.

3. Булеан.

4. Основные операции над множествами.

5. Булева алгебра.

6. Декартово произведение множеств.

7. Бинарное отношение.

8. Отображение множества.

9. Образ, прообраз, обратное отображение.

10. Сюръекция, инъекция, биекция.

11. Функция, обратная функция.

12. Рефлексивность (иррефлексивность), симметричность, антисимметричность, транзитивность.

13. Эквивалентность.

14. Порядок, линейный и полный порядок.

15. Эквивалентность и мощность множеств.

16. Кардинальные числа.

17. Конечные, бесконечные, счётные, бессчётные, континуальные множества.

18. Выборки. Правила суммы и произведения.

19. Перестановки без повторений и с повторениями.

20. Размещения без повторений и с повторениями.

21. Сочетания без повторений и с повторениями.

22. Бином Ньютона.

23. Формула включений и исключений.

24. Производящие функции, экспоненциальные производящие функции.

25. Линейное рекуррентное уравнение с постоянными коэффициентами.

26. Граф (орграф), его элементы.

27. Смежность и инцидентность.

28. Степень вершины графа (орграфа).

29. Изоморфизм.

30. Связность.

31. Маршруты в графах.

32. Цепь, цикл.

33. Пути в орграфах.

34. Контур.

35. Теоремы о маршрутах и циклах.

41. Дерево (ордерево).

42. Теоремы о деревьях.

43. Определения двухполюсной направленной сети, потока.

44. Разрез.

45. Теорема Форда-Фалкерсона.

46. Булева функция (функция двузначной логики).

47. Элементарные булевы функции, логические связки.

48. Формулы алгебры логики, функции, их реализующие.

49. Основные эквивалентные формулы алгебры логики.

50. Элементарная конъюнкция и элементарная дизъюнкция.

51. Дизъюнктивная нормальная форма (ДНФ).

52. Теорема о дизъюнктивном разложении булевой функции.

53. Совершенная дизъюнктивная нормальная форма (СДНФ).

54. Конъюнктивная нормальная форма (КНФ).

55. Теорема о конъюнктивном разложении булевой функции.

56. Совершенная конъюнктивная нормальная форма (СКНФ).

57. Полином Жегалкина.

58. Функциональная замкнутость и полнота.

59. Двойственная функция.

60. Класс самодвойственных функций.

61. Класс линейных функций.

62. Классы функций, сохраняющих константы.

63. Класс монотонных функций.

64. Сокращённая дизъюнктивная форма (ДНФ).

65. Тупиковая, минимальная, кратчайшая ДНФ.

Примечание: для получения положительной оценки все теоремы из данного списка достаточно знать без доказательств.