Матвієнко М. П. Математична логіка та теорія алгоритмів

510(075.8)
М33
Матвієнко М. П. Математична логіка та теорія алгоритмів : навч. посіб. студ. для вищих навч. закладів / М. П. Матвієнко, С. П. Шаповалов ; М-во освіти і науки України, Сумський держ. ун-т. – Київ : Ліра-К, 2015. – 211 с.

У навчальному посібнику наведено основні поняття і методи математичної логіки, а також основи теорії алгоритмів. Теоретичний матеріал проілюстровано вправами та задачами для набуття читачем практичного досвіду.
Навчальний посібник призначено для студентів, аспірантів і спеціалістів, які використовують відповідні методи класичної і некласичної математичної логіки та теорії алгоритмів.

Передмова
Частина І. КЛАСИЧНА МАТЕМАТИЧНА ЛОГІКА
Розділ 1. Основні поняття логіки висловлювань
1.1. Висловлювання та логічні зв’язки
1.2. Умовні та еквівалентні висловлювання
1.3. Ітерпретація формул логіки висловлювань
1.4. Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій
1.5. Дедуктивні висновки в логіці висловлювань
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 2. Числення висловлювань
2.1. Формальна аксіоматична теорія L
2.2. Теорема дедукції
2.3. Побудова доведень у логіці висловлювань
2.4. Аксіоматичний метод
2.5. Конструктивний метод
2.6. Метод доведення від супротивного
2.7. Метод резолюцій
Контрольні запитання
Задачі для самостійною розв’язування.
Коментарі
Розділ 3. Логіка предикатів першого порядку
3.1. Квантори
3.2. Формули логіки предикатів
3.3. Рівносильність формул логіки предикатів
3.4. Закони і тотожності логіки предикатів
3.5. Властивості числення предикатів першою порядку
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 4. Аксіоматичні системи логік
4.1. Система аксіом і правил виведення
4.2. Випереджені нормальні форми
4.3. Побудова доведень в аксіоматичній системі
4.4. Метод ідентифікації
4.5. Метод резолюцій
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Частина ІІ. НЕКЛАСИЧНА МАТЕМАТИЧНА ЛОГІКА
Розділ 5. Нечітка логіка
5.1. Основні визначення
5.2. Операції над нечіткими множинами
5.3. Поняття нечіткої та лінгвістичної змінної
5.4.1. Нечіткі висловлювання та нечіткі предикати
5.4.2. Основні логічні операції з нечіткими висловлюваннями
5.5.1. Правило нечіткого логічного виводу
5.5.2. Композиційне правило нечіткого виводу Заде
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 6. Модальна логіка
6.1. Особливості побудови модальних систем
6.2. Семантика Кріпке
6.3. Теорія “двійників” К. Льюїса
Контрольні залитання
Задачі для самостійного розв’язування
Коментарі
Розділ 7. Епістемічна логіка
7.1. Оператори знання й переконання, їхні властивості
7.2. Формальна мова епістемічної логіки
Контрольні запитання
Коментарі
Розділ 8. Деонтична логіка
8.1. Синтаксис та семантика деонтичної логіки
Контрольні запитання
Коментарі
Розділ 9. Інтуїціоністська логіка
9.1. Числення висловлювань в інтуїціоністській логіці
9.2. Доведення формул числення висловлювань в інтуїціоністській логіці висловлювань
9.3. Застосування моделі Кріпке в інтуїціоністській логіці
Контрольні запитання
Коментарі
Частина ІІІ. ЕЛЕМЕНТИ ТЕОРІЇ АЛГОРИТМІВ
Розділ 10. Основні визначення властивості та способи задання
10.1. Поняття про алгоритм. Еволюція тлумачення та властивості
10.2. Способи задання алгоритмів
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 11. Алгоритми та обчислювальні функції
11.1. Оператор суперпозиції
11.2. Оператор примітивної рекурсіі
11.3. Оператор мінімізації
11.4. Гіпотеза Черча та примітивно-рекурсивні функції
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 12. Алгоритмічні моделі
12.1. Машини Тьюрінга
12.2. Нормальні алгоритми Маркова
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 13. Нумерації алгоритмів
13.1. Попередні відомості
13.1.1. Нумерація за Гьоделем
13.1.2. Головні універсальні функції та множини
13.1.3. Канторові нумерації кортежів натуральних чисел
13.1.4. Нумерації Кліні та Поста
13.2. Нумерація машин Тьюрінга та частково- рекурсивних функцій
13.З. S-m-n – теорема
13.4. m – Зведення та властивості зліченних множин
13.5. Теорема Кліні про нерухому точку
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ 14 Складність алгоритмів
14.1. Асимптотичні оцінювання складності
14.2. Класи складності
Контрольні запитання
Задачі для самостійного розв’язування
Коментарі
Розділ І5. NP – повні, складні та алгоритмічно нeрозв’язні проблеми
15.1.1. Розв’язні та нерозв’язні проблеми, NP – повнота, складність, зведення
15.1.2. Приклади NP- повних задач
15.2. Алгоритмічно нерозв’язні проблеми
Контрольні запитання
Задачі для самостійною розв’язування
Коментарі
Список літератури

Напишіть відгук

Ваша пошт@ не публікуватиметься. Обов’язкові поля позначені *

Можна використовувати XHTML теґи та атрибути: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>