Вопросы к экзамену по математической логике и теории алгоритмов Понятие формальной теории (исчисления). Синтаксический вывод и семантическая истинность. Задачи математической логики



Скачать 14.21 Kb.
Pdf просмотр
Дата15.02.2017
Размер14.21 Kb.
Просмотров253
Скачиваний0
ТипВопросы к экзамену

Факультет компьютерных наук
Кафедра кибернетики
КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ
АЛГОРИТМОВ
Инструкция: Выполняется один вариант заданий. Вариант студенту назначает преподаватель
Задание 1.
Доказать секвенцию исчисления высказываний тремя способами:
• сравнением таблиц истинности;
• построением доказательства в виде дерева;
методом резолюций.
Задание 2.
Перевести с естественного языка на язык исчисления предикатов и сделать вывод, если это возможно.

Задание 3.
Доказать или опровергнуть секвенцию в указанном исчислении.

Вопросы к экзамену по математической логике и теории алгоритмов
1. Понятие формальной теории (исчисления). Синтаксический вывод и семантическая истинность. Задачи математической логики.
2. Исчисление высказываний (ИВ). Определение доказуемости.
3. Эквивалентность формул. КНФ и ДНФ.
4. Семантика ИВ. Таблицы истинности.
5. Характеризация доказуемых формул ИВ.
6. Полнота и непротиворечивость ИВ.
7. Метод резолюций для ИВ. Хорновские дизъюнкты.
8. Исчисление предикатов (ИП). Кванторы.
9. Основные эквивалентности формул ИП. Пренексная нормальная форма.
10. Полнота и непротиворечивость ИП.
11. Унификация формул ИП.
12. Сколемизация формул. Метод резолюций для ИП.
13. Логическое программирование. Язык ПРОЛОГ.
14. Особенности перевода с естественного языка на язык математической логики.
15. Интуиционистская логика
16. Нечеткие множества и нечеткая логика.
17.
Модальная логика. Исчисления I и T.
18.
Модальная логика. Исчисления S4 и S5.
19. Семантика Крипке для модальной логики.
20.
Деонтические модальные исчисления.
21. Временные логики. Алгоритмические логики.
22. Понятие алгоритма. Тезис Черча. Нормальные алгорифмы.
23. Примитивно рекурсивные, частично рекурсивные и рекурсивные функции.
24. Машины Тьюринга.
25. Понятие универсальности.
26. Рекурсивные и рекурсивно перечислимые множества. Пример рекурсивно перечислимого не рекурсивного множества.
27. Теорема Геделя о неполноте арифметики.
28. Сложность алгоритмов.
Литература
1.
Гуц А.К. Математическая логика и теория алгоритмов. М.: 2009.
2.
Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. Новосибирск: 2004.
3.
Бесценный И.П. Практикум по математической логике. Омск: 2008.
4.
Бесценный И.П. Практикум по модальной логике. Омск: 2009.


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


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

войти | регистрация
    Главная страница


загрузить материал