Основна мета курсу „Математична логіка і теорія алгоритмів” - сформувати у студентів знання, вміння і навички, необхідні для усвідомлення і використання понять, законів і методів математичної логіки і теорії алгоритмів при розкритті природи математики та як засобу при вивченні інших галузей наукових знань.
Для досягнення основної мети в курсі „Математична логіка і теорія алгоритмів” розв’язуються основні завдання:
- розкривається місце і значення знань з математичної логіки і теорії алгоритмів у професійній підготовці майбутніх вчителів математики, фізики та інформатики;
- ґрунтовне ознайомлення студентів з формалізацією математичної мови, яка в цьому курсі іде значно далі, ніж в курсах алгебри, геометрії та аналізу;
- детальне ознайомлення студентів з формалізованим аксіоматичним методом побудови математичних теорій, проблемами несуперечності, повноти та алгоритмічної розв’язності теорій;
- уточнення поняття алгоритму і детальне ознайомлення з декількома такими уточненнями, з’ясування сутності алгоритмічної нерозв’язності, ознайомлення з прикладами алгоритмічно розв’язних та алгоритмічно нерозв’язних теорій, набуття навичок конструювання алгоритмів з класу точних алгоритмів для розв’язання найпростіших задач, зокрема, для обчислення числових функцій.
У результаті вивчення дисципліни студенти повинні:
знати:
- основні поняття і факти алгебри висловлень: логічні операції над висловленнями; формули алгебри висловлень та їх класифікацію; рівносильність формул; ДНФ, КНФ та їх властивості; сутність проблеми вирішення в алгебрі висловлень.
- числення висловлень як формалізований аналог алгебри висловлень: поняття формули в численні висловлень; основні теореми і метатеореми числення; правила виводу, теорему дедукції та додаткові правила виводу; проблеми несуперечності, повноти, незалежності та розв’язності в численні висловлень.
- основні поняття і факти логіки предикатів: предикати, логічні операції над ними та класифікацію предикатів; кванторні операції, формули та їх класифікацію; інтерпретації формул, зведену та випереджену форми формул логіки предикатів; проблему вирішення в логіці предикатів.
- формалізацію логіки предикатів і теорії першого порядку: терми, формули, аксіоми, правила виводу; метатеореми дедукції; питання несуперечності, повноти та алгоритмічної розв’язності теорій першого порядку.
- основні поняття теорії алгоритмів: інтуїтивне та уточнене поняття алгоритму; частково-обчислювальні (обчислювальні) та частково-рекурсивні (рекурсивні) функції; оператори регулярної суперпозиції, примітивної рекурсії та мінімізації; тезу Черча; нормальні алгоритми Маркова; машини Тюрінга; методологічну сутність алгоритмічно нерозв’язних проблем;
вміти:
- виконувати логічні операції над висловленнями і предикатами;
- використовувати рівносильність формул для їх перетворення до ДНФ, КНФ в алгебрі висловлень та до зведених і випереджених форм у логіці предикатів;
- практичні застосування алгебри висловлень та логіки предикатів в логіко-математичній практиці;
- доводити теореми в численні висловлень та в теоріях першого порядку з застосуванням основних і додаткових правил виводу;
- застосовувати на практиці оператори регулярної суперпозиції, примітивної рекурсії та мінімізації;
- конструювати найпростіші нормальні алгоритми Маркова та машини Тьюрінга для обчислення числових функцій.
- Автор курсу: Друшляк Марина Григорівна