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

Актуальність дисципліни

Апарат математичної логіки і теорії алгоритмів є основою сучасних інформаційних та програмних систем, він належить до основних засобів моделювання різноманітних предметних областей. В загальносвітоглядному аспекті, поняття й методи математичної логіки дають обґрунтування правильності тих чи інших способів отримання істинного знання.

Математична логіка та теорія алгоритмів мають чітко окреслене прикладне спрямування. Саме апарат математичної логіки (алгебра логіки) лежить в основі схемотехніки комп'ютерів. Теорія алгоритмів безпосередньо пов’язана з теорією керування, вона є теоретичним фундаментом програмування й інформатики. Мови програмування базуються на уточненнях поняття алгоритму. Розвиток інформаційних технологій та пов'язана з цим поява нових задач і проблем ведуть до залучення для їх розв'язку все нових понять і засобів математичної логіки та теорії алгоритмів. Це теорія доведень, нетрадиційні логіки (багатозначні, інтуїціоністські, модальні, темпоральні, епістемічні, динамічні, програмні, можливісні), метод нерухомої точки, теорія обчислень тощо. Результати, отримані в області математичної логіки й теорії алгоритмів, та задачі, які розв'язуються їх засобами і методами, знаходять різноманітні й ефективні застосування в різних сферах діяльності людини. Ідеї та методи математичної логіки й теорії алгоритмів глибоко пронизують математику та інформатику.

Мета дисципліни - засвоєння базових знань з основ математичної логіки та теорії алгоритмів, включаючи вивчення семантичних моделей логіки та їх можливості для опису предметних областей, систем пошуку виведень, формальних моделей алгоритмів та обчислюваних функцій, питань обчислюваності, розв’язності, часткової розв’язності та нерозв’язності масових проблем.

Завдання дисципліни - набуття компетенцій, знань, умінь та навиків на рівні новітніх досягнень у математичній логіці та теорії алгоритмів відповідно до кваліфікації фахівець з прикладної математики.

В результаті вивчення дисципліни «Математична логіка та теорія алгоритмів» студент

повинен знати:

• основні поняття, засоби та методи математичної логіки і теорії алгоритмів, їх застосування в інформатиці й програмуванні;
• мови логіки та їх можливості для опису предметних областей;
• основні методи пошуку доведень та засоби логічного виведення;
• мати уявлення про нетрадиційні логіки (багатозначні, інтуїціоністські, модальні, темпоральні, епістемічні) та їх застосування;
• основні формальні моделі алгоритмів та обчислюваних функцій;
• властивості рекурсивних та рекурсивних перелічних множин, рекурсивних та частково-рекурсивних предикатів, арифметичних множин та предикатів;
• мати уявлення про розв’язність, часткову розв’язність та нерозв’язність масових проблем, про складність обчислень;

повинен вміти:

• описувати на мовах 1-го порядку твердження стосовно різних предметних областей;
• встановлювати істинність та виконуваність, наявність логічного наслідку;
• встановлювати виразність та невиразність предикатів у семантичних моделях мови;
• проводити виведення в численнях гільбертівського типу та в секвенційних численнях;
• будувати формальні моделі алгоритмів та обчислюваних функцій (МНР-програми, машини Тьюрінга, системи Поста, рекурсивні, частково-рекурсивні, програмовані функції);
• встановлювати розв’язність, часткову розв’язність, нерозв’язність масових проблем, встановлювати клас множини та предиката, їх місце в арифметичній ієрархії.

Зв’язок з іншими дисциплінами

Отримані в результаті вивчення дисципліни «Математична логіка та теорія алгоритмів» знання та уміння потрібні для подальшого вивчення:

1) дисциплін обов’язкових та вибору ВНЗ: "Бази даних та інформаційні системи", "Комп’ютерна алгебра", "Основи методів обчислень", "Чисельний аналіз", "Теорія керування";

2) дисциплін вільного вибору студента: "Сучасні методи комп’ютерного моделювання", "Ймовірнісний аналіз алгоритмів", "Цифрова обробка інформації", "Технології математичного та комп’ютерного моделювання", "Паралельні методи обчислень"; "Системне програмування", "Розробка мовних процесорів", "Теорія прийняття рішень", "Моделі та методи прийняття рішень", "Обробка та розпізнавання зображень".

Структура дисципліни

Вступ

• Тема 1. Основні поняття логіки та теорії алгоритмів.

Основи математичної логіки

• Тема 2. Пропозиційна логіка. Пропозиційне числення.
• Тема 3. Пошук виведень. Метод резолюцій. Пропозиційне секвенційне числення.
• Тема 4. Квазіарні функції та предикати. Реномінації, суперпозиції, квантори.
• Тема 5. Логіки 1-го порядку, їх мови і семантичні моделі. Істинність, виконуваність, логічний наслідок.
• Тема 6. Еквівалентні перетворення формул. Виразність. Метод автоморфізмів.
• Тема 7. Теорії 1-го порядку. Несуперечливість, повнота, розв’язність.
• Тема 8. Теорема Гьоделя про повноту, її наслідки. Категоричність.
• Тема 9. Секвенційні числення логік 1-го порядку.

Основи теорії алгоритмів

• Тема 10. Формальні моделі алгоритмів. МНР-програми, машини Тьюрінга.
• Тема 11. Системи Поста. Частково рекурсивні функції.
• Тема 12. Програмовані функції. Теза Чорча.
• Тема 13. Нумерації. Універсальні функції.
• Тема 14. Рекурсивні, рекурсивно перелічні множини. Рекурсивні, частково рекурсивні предикати.
• Тема 15. Розв’язність, часткова розв’язність, нерозв’язність. Індексні множини, теорема Райса.
• Тема 16. Відносна обчислюваність. Звідності.
• Тема 17. Складність обчислень.
• Тема 18. Арифметичність. Арифметична ієрархія.

Нетрадиційні логіки

• Тема 19. Логіки часткових квазіарних предикатів.
• Тема 20. Логіки вищих порядків. Багатозначні логіки. Інтуїціоністська логіка.
• Тема 21. Модальні логіки. Темпоральні логіки, епістемічні логіки, їх застосування.

У курсі передбачено 2 контрольних роботи та 2 колоквіуми.