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

Математическая логика ^ ^

1

Математическая логика

1. Природа математической логики. Формальная логика. Основные формы мышления (понятие, высказывание, умозаключение). Простые и сложные высказывания. Основные законы формальной логики.

2. Понятие и структура аксиоматических систем.

3. Понятие и структура формальных систем.

4. Основные логические операции алгебры высказываний (АВ). Пропозиционная переменная. Постоянные и переменные высказывания АВ.

5. Определение формулы АВ. Равносильность формул. Важнейшие примеры равносильных формул.

6. Двойственные операции и двойственные формулы АВ. Закон двойственности.

7. Тождественно истинные, выполнимые и невыполнимые формулы АВ.

8. Проблема разрешения в алгебре высказываний. Элементарные произведения и суммы. Теорема о тождественной истинности элементарной суммы. Теорема о тождественной ложности элементарного произведения.

9. КНФ и ДНФ. Преобразования формул алгебры высказываний к КНФ и ДНФ. Теорема о существовании КНФ и ДНФ формулы алгебры высказываний.

10. Критерии тождественной истинности и ложности формул алгебры высказываний.

11. СКНФ и СДНФ. Преобразование формул алгебры высказываний к СКНФ и СДНФ, используя равносильности алгебры высказываний.

12. СКНФ и СДНФ. Получение СКНФ и СДНФ формулы алгебры высказывания при помощи таблицы истинности.

13. Описание исчисления высказываний (ИВ). Символы ИВ. Формулы ИВ. Элементарные формулы ИВ, части формул ИВ.

14. Выводимые формулы ИВ. Аксиомы ИВ.

15. Правила вывода формул в ИВ (подстановки и заключения).

16. Некоторые составные правила ИВ (правила силлогизма, перестановки посылок, соединения посылок, разъединения посылок и т.д).

17. Понятие выводимости формулы из набора формул ИВ. Теорема дедукции.

18. Эквивалентные формулы в ИВ. Теорема эквивалентности.

19. Проблемы аксиом ИВ (разрешимость, непротиворечивость, полнота, независимость).

20. Проверки выводимости формул ИВ методом резолюций.

21. Описание логики предикатов (ЛП). Символы ЛП. Логические функции. Предикаты. Предметные области и предметы. Переменные высказывания и предикаты. Элементарные высказывания и элементарные формулы.

22. Кванторы всеобщности и существования. Свободные и связные переменные ЛП.

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

24. Нормальные формулы и нормальные формы. Теорема о существовании нормальной формулы.

25. Проблема разрешения в ЛП. Выполнимые, тождественно истинные для некоторой области Ω, тождественно истинные, невыполнимые формулы ЛП.

26. Решение проблемы разрешения для логики предикатов с одной переменной.

27. Описание исчисления предикатов (ИП). Символы ИВ. Формулы ИВ. Части формул ИВ.

28. Кванторы ИП. Область действие квантора в ИП. Коллизия переменных в ИП.

29. Аксиомы ИП.

30. Правила образования выводимых формул в ИП (Правила заключения; подстановки в переменное высказывание и переменный предикат; замены свободной предметной переменной; переименования связанных предметных переменных; связывание квантором).

31. Непротиворечивость ИП.

32. Определение выводимости формул из набора формул в ИП. Теорема дедукции.

33. Эквивалентные формулы в ИП. Приведенные и нормальные формы формул в ИП. Теорема о существовании нормальной формулы в ИП.

34. Дедуктивная эквивалентность. Связь эквивалентности и дедуктивной эквивалентности.

35. Проблемы ИП (непротиворечивости, полнота в узком смысле, полнота в широком смысле).

36. Логические основы ЭВМ. Простейшие преобразователи информации. Структурная формула. Функциональная схема.

37. Нечеткая логика. Основные понятия (нечеткое множество, лингвистические переменные). Основные свойства нечетких множеств.

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

38. Интуитивное определение алгоритма. Возможные случаи протекания алгоритмического процесса. Определение алгоритма, применимого к исходному набору данных. Характерные черты алгоритма. Область применимости алгоритма.

39. Особенности алгоритмов, которые необходимо учитывать при построении алгоритмических моделей. Основные классы универсальных алгоритмических моделей.

40. Конструктивные объекты. Счетные множества. Основные свойства счетных множеств. Алгоритмы и функции. Определение алгоритма, предложенное Черчем и Клини.

41. Рекурсивные функции. Исходные функции. Операторы суперпозиции, примитивной рекурсии. Определение примитивно рекурсивной функции.

42. Доказательство примитивной рекурсивности некоторых функций.

43. Оператор минимизации. Определение частично рекурсивных и общерекурсивных функций. Теорема о вычислимости всякой частично рекурсивной функции f. Тезис Черча.

44. Определение алфавита, слова в теории нормальных алгоритмов Маркова Понятия пустого слова и подслова. Определение марковской подстановки. Результат марковской подстановки. Соединение слов. Понятие расширения алфавита.

45. Определение алгоритма применимого к слову. Определение алгоритма над алфавитом. Простая и заключительная подстановки в теории нормальных алгоритмов Маркова. Схема алгоритма.

46. Определение нормального алгоритма Маркова в алфавите А.

47. Описание работы нормального алгоритма Маркова со словами.Определение нормально вычислимой функции, заданной на некотором множестве слов некоторого алфавита. Примеры нормально вычислимых функций.

48. Пример построения нормального алгоритма для функции.

49. Теорема о частичной вычислимости по Маркову всякой частично рекурсивная функции и следствие к ней. Принцип нормализации. Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу. Эквивалентность различных теорий алгоритмов.

50. Машина Тьюринга (МТ). Основные узлы, функционирование. Разновидности МТ. Данные МТ. Элементарные шаги МТ. Применение МТ к словам. Определение заключительного слова по заданному начальному слову и системе команд. Конструирование МТ: задание внешнего алфавита, множества состояний и системы команд. Композиция МТ.

51. Функция, вычислимая по Тьюрингу. Функция правильно вычислимая по Тьюрингу. Запись на ленте МТ значений аргументов функций. Запись результата вычислений на ленте. Зацикливание машины. Эквивалентность и суперпозиция машин Тьюринга. Тезис Тьюринга.

52. Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций.

53. Примеры алгоритмически неразрешимых проблем.

54. Меры сложности алгоритмов. Временная и емкостная сложность. Переборные и распознавательные задачи.