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

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

Текст из файла

Дискретная математика, ФН, 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.

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

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов вопросов/заданий