2017-12-14
1062Экзаменационные вопросы
По дисциплине «Элементы математической логики»
| Форма обучения | Шифр спец. | группа | Форма проведения | Количество студентов на экзамене | Количество вопросов | Количество ПЗ |
| очная | 09.02.04 | 16ИС1 | устно | |||
| очная | 09.02.04 | 16ИС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. Функционально замкнутые классы (функции, сохраняющие константу T0 и T1, самодвойственные функции S). Примеры.
В33. Функционально замкнутые классы (монотонные функции M, линейные функции L). Примеры.
В34. Функционально полные системы функций. Булев базис. Примеры других базисов.
В35. Теорема Поста о полноте. Таблицы Поста.
В36. Доказательство того, что штрих Шеффера является базисом
В37. Доказательство того, что стрелка Пирса является базисом.
В38. Базис Жегалкина.
В39. Логические схемы. Метод «черного ящика». Логические схемы, реализующие основные логические операции: «И» (конъюнктор), «ИЛИ» (дизъюнктор), «НЕ» (инвертор).
В40. Логические схемы, реализующие логические операции штрих Шеффера и стрелка Пирса: элемент Шеффера и элемент Пирса соответственно.
В41. Построение логических схем для произвольных логических функций на элементах «И», «ИЛИ», «НЕ».
В42. Построение логических схем для произвольных логических функций на элементах «И-НЕ», «ИЛИ-НЕ».
В43. Применение булевых функций для анализа и синтеза дискретных устройств. Основные узлы ЭВМ: триггеры, дешифраторы. Их назначение и функциональные схемы.
В44. Применение булевых функций для анализа и синтеза дискретных устройств. Основные узлы ЭВМ: счетчики, регистры. Их назначение и функциональные схемы.
В45. Применение булевых функций для анализа и синтеза дискретных устройств. Основные узлы ЭВМ: сумматоры. Их назначение и функциональные схемы.
В46. Логика предикатов. Основные определения.
В47. Логические операции над предикатами. Примеры.
В48. Кванторы. Область действия квантора. Связанные и свободные переменные. Примеры.
В49. Построение отрицаний к предикатам, содержащим кванторные операции.
В50. Применение логики предикатов к логико-математической практике. Запись на языке логики предикатов различных предложений. Строение математических теорем.
В51. Определение машины Тьюринга. Применение машин Тьюринга к словам. Конструирование машин Тьюринга.
В52. Происхождение рекурсивных функций. Основные понятия теории рекурсивных функций и тезис. Примитивно рекурсивные функции.
В53. Графы. Основные понятия: графические представления, вершина, ребро, дуга, граф, отношение инцидентности, вершины и ребра, инцидентные друг другу, смежные вершины, ориентированный и неориентированный графы, кратные ребра, петля, мультиграф, пустой и полный графы, равные графы.
В54. Способы задания графов: матрица смежности, матрица инцидентности, список ребер.
В55. Расстояние между двумя вершинами. Центр и радиус н-графа.
В56. Маршруты, пути, цепи, циклы.
В57. Связные и несвязные графы. Свойства отношения связности. Компоненты связности. Мост.
В58. Эйлеров цикл, эйлеров граф, эйлерова цепь. Теоремы о существовании в н-графе эйлерова цикла и цепи. Гамильтоновы цикл и цепь.
В59. Планарные графы. Теорема Эйлера. Доказательство утверждения о непланарности полных графов, полных двудольных графов.
В60. Известные задачи на графах.
В61. Деревья. Характерные свойства деревьев. Ориентированное дерево. Бинарные деревья. Цикломатическое число. Лес.
В62. Алгоритмы на графах. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры.
В63. Алгоритмы на графах. Построение минимального остова графа: алгоритм Краскала.
Практические задания
П1. – П10. Практические задачи на тему «Основы теории множеств».
П11. – П15. Практические задачи на построение таблиц истинности для логических формул и решение логических задач.
П16. – П20. Практические задачи на минимизацию (упрощение) логических функций, на построение СДНФ, СКНФ.
П21. – П30. Практические задачи на построение многочлена Жегалкина, таблиц Поста.
П31. – П40. Построение логических схем для произвольных логических функций на элементах «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ».
П41. – П50. Практические задачи на графах.
П51. – П55. Практические задачи на выполнение операций над предикатами, определение логических значений предикатов, формализацию различных предложений средствами логики предикатов
П56. – П60. Практические задачи на проведение логико-математического анализа теорем и определение необходимых и достаточных условий.
П61. – П65. Конструирование машин Тьюринга.
