4. Материалы для подготовки коллоквиуму
Задания билетов коллоквиума, относящиеся к базовому уровню, составляются в соответствии с программой аттестации модуля I «Элементы теории множеств и комбинаторики. Алгебра логики». Для подготовки к сдаче коллоквиума на базовом уровне студенту рекомендуется изучить материал раздел «Базовые понятия и утверждения» лекций 1-8 (лекции написаны в точном соответствии с этой программой). При сдаче коллоквиума на базовом уровне проверяется знание теоретических фактов, способность иллюстрировать теоретические понятия и утверждения на примерах, а также умение решать типовые упражнения, аналогичные тем, которые приведены в п.5 данного файла.
Задания билетов коллоквиума, относящиеся к повышенному уровню, составляются в соответствии с программой аттестации курса повышенного уровня модуля I «Множества, бинарные отношения, комбинаторика. Алгебра логики». Для подготовки к сдаче коллоквиума на повышенном уровне студенту рекомендуется изучить в полном объеме материал лекций 1-8.
Вопросы к коллоквиуму № 1
Множества и операции над ними. Свойства операций над множествами. Правило суммы, правило включений-исключений. Разбиение множества.
Бинарные отношения на множестве. Свойства бинарных отношений. Отношение эквивалентности, отношение порядка. Теорема о свойствах классов эквивалентности.
Элементы комбинаторики. Правило произведения и правило суммы. Сочетания и размещения. Сочетания и размещения с повторениями. Биномиальные коэффициенты, треугольник Паскаля.
Булевы векторы и булевы функции от
переменных. Элементарные булевы функции.
Задание булевых функций формулами.
Основные равносильности.
Существенные и фиктивные переменные булевых функций. Операция удаления (введения) фиктивной переменной.
Двойственные функции. Принцип двойственности.
Разложение булевых функций по переменным.
Совершенная дизъюнктивная нормальная форма функции.
Совершенная конъюнктивная нормальная форма функции.
Постановка задачи о минимизации ДНФ. Минимальная ДНФ. Сокращенная ДНФ. Тупиковые ДНФ.
Алгоритм поиска сокращенных, тупиковых и минимальных ДНФ.
Представление функций в виде полинома Жегалкина (существование и единственность). Поиск полинома Жегалкина методом равносильных преобразований и методом неопределенных коэффициентов.
Класс функций, сохраняющих 0. Класс функций, сохраняющих 1. Класс самодвойственных функций. Класс монотонных функций. Класс линейных функций
Замыкание системы булевых функций. Свойства замыкания. Теорема о замкнутости классов Поста.
Полные системы булевых функций. Теорема о полноте двух систем. Примеры полных систем. Базисы.
Лемма о функции, не сохраняющей 0. Лемма о функции, не сохраняющей 1.
Лемма о несамодвойственной функции.
Лемма о немонотонной функции.
Лемма о нелинейной функции.
Критерий полноты системы булевых функций (теорема Поста).
P.S. Объем подготовки по каждому вопросу определяется уровнем сдачи коллоквиума. Вопросы, выделенные курсивом, изучаются только на повышенном уровне.