Петухин. Лекции по дискретной математике. Скомп. справка в html.Содержание.
Алгебраические системы.
Общие понятия и определения.
Понятие алгебраической системы.
Алгебраические системы, алгебры и модели.
Изоморфизм алгебраических систем.
Подсистемы алгебраических систем.
Прямое произведение алгебраических систем.
Примеры алгебраических систем.
Числа со сложением и умножением.
Векторы на плоскости.
Алгебра подмножеств.
Классы алгебраических систем.
Графы.
Частично-упорядоченные множества.
Решётки.
Булевы алгебры.
Группы и полугруппы.
Графы.
Основные понятия.
Маршруты, цепи и циклы.
Раскраска, плоские графы.
Комбинаторные задачи на графах.
Литература.
Булевы функции.
Понятие булевой функции.
Суперпозиция функций.
Двойственные функции.
Разложение функции по переменным.
Литература.
Математическая логика.
Предмет математической логики.
Пример формальной системы.
Структура раздела.
Аксиоматический метод.
Аксиомы натуральных чисел.
Начальные задачи.
Сложение.
Порядок.
Наименьший элемент.
Умножение.
Системы Пеано.
Логика высказываний.
Объектный язык и метаязык.
Пропозициональные формулы.
Доказательство свойств формул по индукции.
Разбор формул.
Семантика.
Нормальные формы.
Выполнимость.
Логическое следование.
Пропозициональный вывод.
Правила для конъюнкции и импликации.
Правило введения посылки.
Корректность правил вывода.
Правила для отрицания и правила противоречия.
Правила для дизъюнкции.
Корректность и полнота логики высказываний.
Логика предикатов.
Язык логики предикатов.
Свободные и связанные переменные.
Представление предложений русского языка предикатными формулами.
Подстановка.
Семантика.
Выполнимость.
Логическое следование.
Выводы в логике предикатов.
Правила для кванторов всеобщности.
Правила для кванторов существования.
Корректность и полнота логики предикатов.
Функциональные символы и равенство: синтаксис.
Функциональные символы и равенство: семантика.
Выводы в логике первого порядка.
Теории первого порядка.
Пример: Теория линейного порядка.
Арифметика первого порядка.
Нестандартные модели арифметики.
Теорема неполноты Гёделя.
