О.Б. Лупанов - Вопросы по курсу Введение в математическую логику
Описание файла
PDF-файл из архива "О.Б. Лупанов - Вопросы по курсу Введение в математическую логику", который расположен в категории "". Всё это находится в предмете "математическая логика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Вопросы по курсу"Введение в математическую логику"(лектор О.Б. Лупанов), 2005г.1. Формулы алгебры логики. Существенные и несущественные переменные. Формулы. Эквивалентность формул. Элементарные функции и их свойства. Разложение функция по переменной . Совершенная дизъюнктивнаянормальная форма (СДНФ).2. Полные системы функций. Примеры полных систем. Замкнутые классы.3. Полиномы Жегалкина.
Линейные функции. Лемма о линейной функции.4. Самодвойственные функции. Лема о несамодвойственной функции.5. Монотонные функции. Лемма о немонотонной функции.6. Теорема о полноте систем функций алгебры логики. Возможность выделить из каждой полной системыполную систему, состоящую не более чем из четырех функций. Предполные классы.7. Функции k-значной логики. Элементарные функции. Полнота системы{0, 1, . . . , k − 1, J0 (x), J1 (x), . . . , Jk−1 (x), max(x, y), min(x, y)}.8.
Полнота систем {max(x, y), x + 1}, {Vk (x, y)}.9. Алгоритм распознавания полноты конечных систем функций в Pk .10. Представление функций из Pk полиномами.11. Лемма о трех наборах. Лемма о квадрате. Теорема Яблонского. Теорема Слупецкого.12.
Классы сохранения множеств фукнций и их свойства. Теорема Кузнецова.13. Замкнутый класс в Pk (k ≥ 3) без базиса. Замкнутый класс в Pk (k ≥ 3), имеющий счетный базис.Мощность множества замкнутых классов в Pk .14. Графы, основные понятия. Реализация графов в трехмерном пространстве.15. Схемы из функциональных элементов. Простейшие методы синтеза.16. Контактные схемы.
Простейшие методы синтеза.17. Метод каскадов (для контактных схем и функциональных элементов).18. Верхняя оценка функции Ln для схем из функциональных элементов и контактных схем. Порядок ростафункции Ln .19. Детерминированные функции. Ограниченно-детерминированные функции (автоматные) функции. Способы их задания.20. Реализуемость автоматных функция схемами из функциональных элементов и элементов задержки (схемами с обратными связями).21. Исчисление высказываний. Аксиомы. Правило вывода.
Тождественная истинность выводимых формул.Непротиворечивость исчисления высказываний.22ю Предикаты. Логические операции над предикатами.23. Условие полноты системы предикатов на конечном множестве.24. Модель, формулы в модели. Свободные и связные переменные. Значение формул в модели.25. Истинность формул в модели, на множестве. Тождественно истинные формулы.26. Правила эквивалентных преобразований формул логики предикатов. Нормальная форма.27.
Машина Тьюринга. Вычислимые функции.28. Алгоритмическая неразрешимость проблемы самоприменимости.28. Алгоритмическая неразрешимость проблемы применимости.1.