Зміст

1 Зміст курсу

Зміст курсу

Змістовий модуль І

Тема 1. Алгебра висловлень

1.1 Вступ. Предмет математичної логіки. Історична довідка.
1.2 Побудова алгебри висловлень: висловлення та операції над ними. Алфавіт алгебри висловлень.
1.3 Формули алгебри висловлень. типи формул. Тавтології. Способи побудови.
1.4 Відношення рівносильності в алгебрі висловлень. Рівносильні формули. Основні рівносильності. Теорема про заміну. Двоїсті операції. Двоїсті формули. Закон двоїстості.
1.5 Проблема вирішення в алгебрі висловлень. Способи її розв’язання.
1.6 Нормальні форми формул алгебри висловлень. Досконалі ДНФ та КНФ.
1.7 Відношення логічного наслідку в алгебрі висловлень. Логічність міркувань. Критерії логічного наслідку.
1.8 Основні схеми логічних висновків. Знаходження логічних наслідків заданих гіпотез.

Тема 2. Булеві функції

2.1 Булеві змінні, булеві вектори та їх кількість. Булеві функції від n змінних.
2.2 Булеві функції однієї та двох змінних.
2.3 Зв’язок булевих функцій з формулами алгебри висловлень.
2.4 Функціональна повнота системи булевих функцій.
2.5 Алгебра Жегалкіна. Способи побудови поліномів Жегалкіна.
2.6 Двоїсті функції та формули. Класи булевих функцій: T0, T1, M, L, S та їх замкнутість. Теорема Поста.
2.7 Застосування булевих функцій до побудови релейно-контактних схем. Аналіз та синтез РК-схем.
2.8 Застосування алгебри висловлень в шкільному курсі математики. Логічний квадрат.

Тема 3. Числення висловлень

3.1.Схема формалізації змістовної теорії. Аксіоматична побудова числення висловлень.
3.2 Поняття теореми та формального доведення. Приклади виводу формул.
3.3 Виведення із припущень. Метатеорема дедукції. Похідні правила виведення, приклади виводу теорем.
3.4 Несуперечливість, повнота і розв’язність числення висловлень. Незалежність аксіом числення висловлень.
3.5 Різні аксіоматики числення висловлень.

Змістовий модуль ІІ.

Тема 1. Логіка предикатів

1.1 Поняття предикату, область істинності предиката, типи предикатів. Операції над предикатами. Квантори загальності та існування. Формули логіки предикатів. Вільні і зв’язані змінні.
1.2 Інтерпретація формул. Типи формул. Модель множини формул. Виконувані та загальнозначущі формули. Основні логічно загальнозначущі формули.
1.3 Приклад формули виконуваної в нескінченній області і не виконуваної в жодній скінченній області інтерпретації.
1.4 Відношення рівносильності в логіці предикатів. Основні рівносильності. Рівносильні перетворення формул. Зведена та пренексна (випереджена) нормальні форми.
1.5 Відношення логічного наслідку в логіці предикатів. Основні правила слідування.
1.6 Проблема розв’язності в логіці предикатів.
1.7 Застосування мови логіки предикатів для запису математичних тверджень, означень, побудови заперечень тверджень.

Тема 2. Математичні теорії першого порядку

2.1 Мова першого порядку. Терми і формули. Логічні і спеціальні системи аксіом. Правила виведення. Приклади математичних теорій. Доведення в теорії. Похідні правила виводу. Приклади доведень. Теорема дедукції.
2.2 Проблеми несуперечливості, повноти, розв’язності теорій. Несуперечливість числення предикатів. Інтерпретація мови теорії. Модель теорії. Ізоморфізм. Категоричність теорії. Теорема повноти.
2.3 Формальна арифметика - теорія натуральних чисел. Мова. Спеціальні аксіоми. Теорема Геделя про неповноту.

Тема 3. Теорія алгоритмів

3.1 Поняття алгоритму та необхідність його уточнення. Алфавітні оператори та алгоритми. Алгоритмічна система.
3.2 Нормальні алгоритми Маркова. Приклади. Гіпотеза Маркова. Поняття про універсальний нормальний алгоритм.
3.3 Обчислювальні функції. Уточнення поняття алгоритму за допомогою рекурсивних функцій. Розв’язні і перераховані множини
3.4 Машини Тьюрінга і Поста.
3.5 Поняття про алгоритмічно нерозв’язні проблеми, їх приклади. Методологічна суть алгоритмічної нерозв’язності математичних проблем.