вопросы для подготовки к зачету

Дискретная математика, ФН, 6-й семестрВопросы для подготовки к зачету1. Булевы алгебры. Доказать, что Bn с булевыми покомпонентными операциями есть булеваалгебра. Булев куб как кольцо. Полиномы Жегалкина.2. Табличный способ задания булевых функций. Наиболее распространенные булевы функцииодной, двух и трех переменных.3. Понятие формулы над заданным множеством. Соответствие между булевыми функциями иформулами. Эквивалентные функции и эквивалентные формулы.4. Замыкание множества булевых функций. Замкнутые и полные множества функций. Полнота стандартного базиса и базиса Жегалкина. Базисы из одной функции.5.

Теорема о замене подформулы эквивалентной и теорема о замене переменной в эквивалентных формулах.6. Понятие дизъюнктивной нормальной формы (ДНФ) и конъюнктивной нормальной формы(КНФ). Теорема о представлении формулы в ДНФ и КНФ.7. Классы Поста. Доказательство их замкнутости.8. Доказательство критерия Поста. Проверка множеств функций на полноту.9. Минимальные и кратчайшие ДНФ.

Их построение. Метод Квайна.10. Алгебра высказываний. Пропозициональные формулы и истинностные функции. Теоремао соответствии между пропозициональными формулами и истинностными функциями. Эквивалентные пропозициональные формулы.11. Типы формул: тавтологии, опровержимые формулы, противоречия. Теорема о правилеmodus ponens.12. Теорема об эквивалентной замене в пропозициональной формуле и ее следствия.13. Способы получения эквивалентных формул. Теорема о ДНФ.14.

Понятие исчисления. Исчисление высказываний. Язык исчисления и метаязык.15. Схемы аксиом исчисления высказываний. Понятие вывода в исчислении высказываний.Секвенции.16. Теорема о дедукции в исчислении высказываний.17. Техника естественного вывода. Структурные правила естественного вывода.18. Логические правила естественного вывода.19.

Класс выводимых формул в исчислении высказываний. Доказать, что любая выводимаяформула в исчислении высказываний есть тавтология.20. Теорема о выводимости формулы, построенной на переменных x1 , x2 , . . . , xn .21. Теорема о выводимости в исчислении высказываний любой тавтологии.22. Понятие полноты, непротиворечивости и разрешимости исчисления. Полнота, непротиворечивость и разрешимость исчисления высказываний.23. Понятие логико-математического языка.

Функциональная сложность терма. Логическаясложность формулы. Свободные и связанные вхождения переменных в формулу. Формулызамкнутые и незамкнутые.24. Переименование переменных и коллизия переменных при переименовании. Конгруэнтныеформулы. Свойство чистоты переменных.25. Понятие подстановки в логико-математическом языке.

Лемма о чистоте переменных.26. Понятие интерпретации логико-математического языка. Оценка формулы. Примеры.27. Понятие логического закона в логико-математическом языке. Законы модели. Примеры.Логически эквивалентные формулы.28. Замены в формулах. Правило замены эквивалентным.29. Предваренная (пренексная) нормальная форма. Теорема о существовании предваренной нормальной формы.30. Исчисление предикатов. Особенности вывода в исчислении предикатов.

Лемма об истинности в исчислении предикатов.31. Техника естественного вывода в исчислении предикатов.32. Основные понятия теории графов. Графы и орграфы. Степени вершин. Подграфы, остовные подграфы, порожденные подграфы. Гомоморфизм графов. Изоморфные графы.33. Понятие связности графов и орграфов. Компоненты связности.34. Способы представления графов. Матрицы инцидентности, смежности, достижимости. Графкак отношение на множестве.35.

Неориентированное дерево. Теорема об эквивалентности условий, определяющих дерево.36. Остов графа. Теорема о существовании остова у связного графа. Максимальный остовныйлес. Способы построения остова (максимального остовного леса).37. Остов наименьшего веса и алгоритмы его построения.38. Задача о путях в размеченном графе и алгоритм Дейкстры.39.

Решение задачи о путях с использованием теории полуколец.40. Понятие фундаментального цикла. Количество фундаментальных циклов. Цикломатическое число графа. Алгоритм поиска фундаментальных циклов.41. Разрезы. Понятие фундаментального разреза. Поиск фундаментальных разрезов. Связь ссистемой фундаментальных циклов.42. Эйлеровы цепи и циклы. Критерий существования.Типы задач в зачетных билетах1.2.3.4.5.6.7.8.9.10.Задачи на представление булевых функций (вектор, формула, полином Жегалкина).Задачи на минимизацию ДНФ.Задачи на полноту систем функций.Задачи на вывод в исчислении высказываний.Задачи на проверку истинности или выполнимости формул в исчислении предикатов.Задачи на построение предваренной нормальной формы.Задачи на изоморфизм графов.Задачи на проверку больших графов на связность и существование циклов.Задачи на поиск кратчайших путей и построение матрицы достижимости.Задачи на построение системы фундаментальных циклов и системы фундаментальных разрезов.11.

Некоторые задачи на графы теоретического плана..