Программа

	лекц.	прак.
1. Введение.	2	-
Предмет курса. Основные понятия теории множеств и алгебраические понятия, используемые в курсе.
2. Алгебраические системы.	10	10
2.1. Общее понятие алгебраической системы.	4	6
Понятие алгебраической системы. Алгебры и модели. Изоморфизм, гомоморфизм, автоморфизм алгебраических систем. Подсистемы. Замыкание множества в алгебраической системе. Прямое произведение алгебраических систем.
2.2. Классы алгебраических систем.	6	6
Графы. Частично-упорядоченные множества. Решетки. Булевы алгебры. Теорема Стоуна. Группы, полугруппы, моноиды.
3. Графы.	4	2
Подграфы. Маршруты, цепи, циклы. Деревья. Раскраска графов. Плоские графы. Грани графа. Графы и многогранники. Двойственные графы. Комбинаторные задачи на графах.
4. Булевы функции.	4	6
Булевы функции. Суперпозиция функций. Двойственность. Разложения булевых функций. Совершенная дизъюнктивная и конъюнктивная нормальные формы.
5. Аксиоматический метод.	4	4
Аксиоматика натуральных чисел. Сложение. Порядок на натуральных числах. Индукция. Умножение. Рекурсивные определения. Системы Пеано.
6. Формальные системы.	12	14
Примеры простых исчислений.
6.1 Исчисление высказываний.	4	8
Синтаксис. Семантика. Эквивалентность формул. Нормальные формы. Выполнимость, логическое следование, тавтология. Аксиомы, правила вывода. Теоремы корректности и полноты.
6.2 Исчисление предикатов.	8	6
Синтаксис. Семантика. Формализация фраз русского языка с помощью формул исчисления предикатов. Аксиомы, правила вывода. Теоремы корректности и полноты. Теории первого порядка. Арифметика первого порядка. Нестандартные модели арифметики. Теорема Г¸деля о неполноте.