Geum.ru

Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс)

Вид материалаДокументы
Подобный материал:
Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс)


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. Сложность алгоритмов. Классификация задач по степени сложности. Класс P. Класс E: задачи, экспоненциальные по природе. Недетерминированные алгоритмы NP-трудные и NP-полные задачи

34. Нормальные алгоритмы Маркова. Алгоритм Евклида. Тезис Маркова

35. Рекурсивные функции. Суперпозиция частичных функций. Примитивная рекурсия. Операция минимизации.

36. Алгоритмическая машина Тьюринга.

37. Возможности машин Тьюринга. Основная гипотеза теории алгоритмов

38. Алгоритмическая машина Поста

39. Криптография. Основные задачи криптографии. Стойкость шифра.

40. Шифр перестановки. Шифр Виженера. Шифр простой подстановки