| Форма обучения | Шифр спец. | группа | Форма проведения | Количество студентов на экзамене | Количество вопросов | Количество ПЗ |
| очная | 09.02.07 | 20ИП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. Функционально замкнутые классы (функции, сохраняющие константу T0 и T1, самодвойственные функции S). Примеры.
30. Функционально замкнутые классы (монотонные функции M, линейные функции L). Примеры.
31. Функционально полные системы функций. Булев базис. Примеры других базисов.
32. Теорема Поста о полноте. Таблицы Поста.
33. Доказательство того, что штрих Шеффера и стрелка Пирса являются базисами.
34. Логические схемы. Метод «черного ящика». Логические схемы, реализующие основные логические операции: «И» (конъюнктор), «ИЛИ» (дизъюнктор), «НЕ» (инвертор).
35. Логические схемы, реализующие логические операции штрих Шеффера и стрелка Пирса: элемент Шеффера и элемент Пирса соответственно.
36. Построение логических схем для произвольных логических функций на элементах «И», «ИЛИ», «НЕ».
37. Построение логических схем для произвольных логических функций на элементах «И-НЕ», «ИЛИ-НЕ».
38. Логические операции над предикатами. Примеры.
39. Кванторы. Область действия квантора. Связанные и свободные переменные. Примеры.
40. Построение отрицаний к предикатам, содержащим кванторные операции.
41. Применение логики предикатов к логико-математической практике. Запись на языке логики предикатов различных предложений. Строение математических теорем.
42. Графы. Основные понятия: графические представления, вершина, ребро, дуга, граф, отношение инцидентности, вершины и ребра, инцидентные друг другу, смежные вершины, ориентированный и неориентированный графы, кратные ребра, петля, мультиграф, пустой и полный графы, равные графы.
43. Способы задания графов: матрица смежности, матрица инцидентности, список ребер.
44. Расстояние между двумя вершинами. Центр и радиус н-графа.
45. Маршруты, пути, цепи, циклы.
46. Связные и несвязные графы. Свойства отношения связности. Компоненты связности. Мост.
47. Эйлеров цикл, эйлеров граф, эйлерова цепь. Теоремы о существовании в н-графе эйлерова цикла и цепи. Гамильтоновы цикл и цепь.
48. Планарные графы. Теорема Эйлера. Доказательство утверждения о непланарности полных графов, полных двудольных графов.
49. Известные задачи на графах.
50. Деревья. Характерные свойства деревьев. Ориентированное дерево. Бинарные деревья. Цикломатическое число. Лес.
51. Алгоритмы на графах. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры.
52. Алгоритмы на графах. Построение минимального остова графа: алгоритм Краскала.
53. Определение машины Тьюринга. Применение машин Тьюринга к словам. Конструирование машин Тьюринга.
Практические задания
1. Задачи на тему «Основы теории множеств».
2. Задачи на построение таблиц истинности для логических формул и решение логических задач.
3. Задачи на минимизацию (упрощение) логических функций, на построение СДНФ, СКНФ.
4. Задачи на построение многочлена Жегалкина, таблиц Поста.
5. Построение логических схем для произвольных логических функций на элементах «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ».
6. Задачи на выполнение операций над предикатами, определение логических значений предикатов, формализацию различных предложений средствами логики предикатов.
7. Конструирование машин Тьюринга.