Конспект лекцій з математичної логіки та теорії алгоритмів

Вінниця, 2007.
Конспект лекцій відповідає діючій програмі з математичної логіки і теорії алгоритмів для математичних спеціальностей педагогічних університетів.
Зміст: Вступ.
1. Логіка висловлень.
Логічні операції над висловленнями.
Логічне слідування в логіці висловлень.
Рівносильність формул логіки висловлень. Нормальні форми.
Повні системи булевих функцій. Алгебра Жегалкіна.
Замкнені класи булевих функцій. Теорема про функціональну повноту.
2. Числення висловлень.
Числення висловлень. Теорема дедукції.
Повнота, несуперечність і незалежність аксіом числення висловлень.
3. Логіка предикатів.
Предикати і квантори.
Загальнозначущість і виконуваність формул в логіці предикатів.
4. Математичні теорії першого порядку.
Означення теорії першого порядку. Числення предикатів.
Несуперечність і повнота числення предикатів.
Формальна арифметика.
5. Елементи теорії алгоритмів.
Поняття алгоритму та його характерні риси.
Нормальні алгоритми.
Про алгоритмічно нерозв'язні проблеми.
Обчислювальні функції.
Машина Тьюрінга.
Література.