Программа экзамена по математической логике



Скачать 55.93 Kb.
Дата27.04.2018
Размер55.93 Kb.
ТипПрограмма

Программа экзамена по математической логике

Алгебра высказываний



  1. Операции над высказываниями и их свойства. Ассоциативность, дистрибутивность и идемпотентность операций алгебры высказываний.

  2. Формулы алгебры высказываний. Подформулы. Тождественные и равносильные формулы.

  3. Ранг формулы. Утверждение о замене подформул. Утверждение о
    замене подформулы равносильной формулой.

  4. Основные равносильности алгебры высказываний.

  5. Приведенные формулы. Теорема о существовании равносильной
    приведенной формулы.

  6. Дизъюнктивные и конъюнктивные нормальные формы. Теорема о существовании ДНФ и КНФ, равносильных исходной формуле алгебры высказываний.

  7. Совершенные дизъюнктивные и конъюнктивные нормальные формы. Теорема о существовании и единственности С ДНФ и СКНФ.

  8. Теорема и тождественной истинности (ложности) формулы алгебры высказываний.

Алгебра предикатов



  1. Предикаты и операции над ними. Алгебраические системы, модели и
    алгебры.

  2. Формулы алгебры предикатов. Приведенные и предваренные формулы алгебры предикатов. Теорема о существовании эквивалентной приведенной формулы.

  3. Понятие двойственности формул алгебр высказываний и предикатов. Теоремы о двойственных формулах (формулировка для обоих случаев, доказательство для формул алгебры высказываний).

  4. Принцип двойственности (в общем случае) и его доказательство для алгебры высказываний.

Булевы функции и их свойства



  1. Булевы функции и операции над ними. Фиктивные и существенные переменные. Понятие подфункции булевой функции. Разложение функций по подфункциям.

  2. Представление булевых функций формулами. Утверждение о представлении булевых функций формулами алгебры высказываний.

  3. Многочлены Жегалкина. Теорема о существовании и единственности многочлена Жегалкина булевой функции.

  4. Замыкание класса булевых функций. Замкнутые классы. Примеры.

  5. Монотонные, самодвойственные и аффинные функции. Критерий немонотонности.

  6. Полные классы функций. Примеры полных классов. Минимальные полные системы (базисы).

  7. Критерий Поста полноты системы булевых функций.

  8. Предполные классы булевых функций и их число. Критерий неполноты системы булевых функций.

  9. Импликанты булевых функций. Простые импликанты и сокращенные ДНФ. Минимальные ДНФ. Лемма о поглощении элементарных дизъюнкций.

  10. Соседние элементарные дизъюнкции. Склеивание и расклеивание э.д. Насыщенные ДНФ. Лемма о склеивании в насыщенных ДНФ.

  11. Построение сокращенной ДНФ из СДНФ.

  12. Утверждение о том, что минимальная ДНФ - тупиковая.

  13. Операция обобщенного склеивания. Алгоритм Блейка.

  14. Теорема о корректности алгоритма Блейка и ее следствие.

  15. Критерий «быть импликантой».

  16. Критерий «быть простой импликантой».

  17. Алгоритм Нельсона получения сокращенной ДНФ из произвольной КНФ. Теорема о корректности алгоритма Нельсона.

  18. Тупиковые ДНФ. Ортогональные функции. Утверждение о ортогональных функциях и его следствие.

  19. Критерий поглощения и его применение для получения тупиковых ДНФ. Алгоритм Квайна получения минимальных ДНФ.

Основные криптографические параметры булевых функций



  1. Коэффициенты Фурье и Уолша-Адамара булевых функций, соотношение между ними.

  2. Формула обращения для преобразования Уолша-Адамара.

  3. Соотношения ортогональности и равенство Парсеваля для коэффициентов Уолша-Адамара.

  4. Понятие нелинейности булевой функции, значение нелинейности.

k-значные функции



  1. k-значные функции: основные определения, примеры.

  2. Полные системы k-значных функций. Полнота системы Поста.

  3. Критерии полноты: Слупецкого, Яблонского, Саломаа.(без. док.)

  4. .Лемма А.А. Нечаева

  5. .Критерий полноты k-значных функций.

  6. . Классификация k-значных функций относительно групп преобразований. Теорема о мощности класса функций, эквивалентных относительно заданной группы.

  7. Основные группы преобразований множества к и соотношение между ними.

  8. Теорема о числе функций, инвариантных относительно заданной группы преобразований и ее применение для групп сдвигов, Джевонса и полной аффинной.

  9. Утверждение об орбитах полной линейной группы.

  10. Теорема о тривиальности группы инерции почти всех к-значных функций.

Исчисление предикатов



  1. Общее понятие о логическом исчислении. Выводимость и доказуемость формул.

  2. Основные аксиомы исчисления предикатов и правила вывода.

  3. Теоремы о выводимости формул алгебры предикатов.

  4. Теорема об ограниченной дедукции.

  5. Вспомогательные правила вывода: правила умножения формул, силлогизма, умножения посылок

  6. Правила: разделения посылок, перестановки посылок, сложения посылок, введения посылок, контрапозиции и де Моргана.

  7. Правила -отрицания и -отрицания.

  8. Правило противоречия.

  9. Теорема дедукции для замкнутой формулы.

  10. Интерпретация исчисления. Теорема об истинности формулы, выводимой из набора формул, истинных в некоторой интерпретации. Теорема Геделя о полноте (без. док.)

Теория алгоритмов



  1. Основные характерные свойства алгоритмов.

  2. Нормальные алгоритмы Маркова: определения, примеры.

  3. Принцип нормализации алгоритмов. Теорема о нормализации суперпозиции нормальных алгоритмов.

  4. Геделевская нумерация алгоритмов.

  5. Машины Тьюринга: определения, примеры.

  6. Алгоритмически неразрешимые проблемы. Теорема о несуществовании НА, применимого к несамоприменимым алгоритмам.

  7. Сложность НА, высиляющих булевы функции.

  8. С ложность вычислений на машине Тьюринга, теорема о вычислимости арифметических функций.

  9. Вычисления на недетерминированных машинах Тьюринга. Классы Р и NP. Примеры NP-полных задач.

Каталог: Tasks
Tasks -> Философия человека
Tasks -> Московская олимпиада школьников по обществознанию
Tasks -> Лакатос Имре. История науки и ее рациональные реконструкции
Tasks -> Контрольная работа для студентов заочного и очно-заочного обучений Выбор варианта: Тема Модели и система управления персоналом в органах государственной и муниципальной власти
Tasks -> Темы эссе по философии
Tasks -> Вопросы философии, 2009, №10
Tasks -> Методические рекомендации по написанию курсовых работ
Tasks -> К. Ясперс. Духовная ситуация времени (1932)


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©znate.ru 2017
обратиться к администрации

    Главная страница