Экзаменационные вопросы. по дисциплине «Дискретная математика с элементами математической логики». Теоретические вопросы

РАССМОТРЕНО	УТВЕРЖДАЮ
на заседании кафедры	Заместитель директора по учебной работе
протокол №___
от «___»________________20__г.	_____________________И. И. Козенкова
Зав. кафедрой ______ Т. В. Долдина	«___»________________20__г.
РАЗРАБОТАЛ
Преподаватель _____ Ю. В. Маянцева
«___»__________________20__г.

Экзаменационные вопросы

по дисциплине «Дискретная математика с элементами математической логики»

Форма обучения	Шифр спец.	группа	Форма проведения	Количество студентов на экзамене	Количество вопросов	Количество ПЗ
очная	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. Деревья. Характерные свойства деревьев. Ориентированное дерево. Бинарные деревья. Цикломатическое число. Лес.

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

1. Задачи на тему «Основы теории множеств».

2. Задачи на построение таблиц истинности для логических формул и решение логических задач.

3. Задачи на минимизацию (упрощение) логических функций, на построение СДНФ.