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