Лекции по дискретной математике

Description

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