Подготовка к коллоквиуму

Билет коллоквиума состоит из двух частей. Порядок проведения коллоквиума следующий. Вначале студент готовит в письменной форме ответы к заданиям части 1 (время подготовки 30-40 минут), после чего преподаватель проверяет написанное и при необходимости дополнительно устно беседует со студентом по вопросам части 1. В случае положительного ответа студент переходит к подготовке на вопрос части 2. При желании студент может ограничиться ответом только на задания 1-й части.

Часть 1 содержит 6 теоретико-практических заданий базового уровня сложности. Правильный ответ на каждое задание ориентировочно оценивается 2 баллами. Максимальное количество баллов за ответы на задания 1-й части – 12 баллов, минимальное положительное количество баллов – 8.

При ответе на вопрос части 2 проверяются знания и умения, соответствующие повышенному уровню сложности. Часть 2 коллоквиума содержит один теоретический вопрос из списка вопросов к коллоквиуму и сдается в форме устной беседы. Максимальное количество баллов, выставляемое за ответ на вопрос 2-й части, равно 8.

Начисленные за ответы баллы учитываются в рамках накопительной балльной системы.

Для подготовки к сдаче 1-й части коллоквиума студенту рекомендуется изучить материал разделов «Базовые понятия и утверждения» лекций 1-8 (в печатном варианте лекций - Олейник Т.А. «Основы дискретной математики: теория и практика», - М.:МИЭТ, 2010 - глава 1,2). Задания 1-й части билетов коллоквиума составляются на основе и с использованием этих материалов.

Для подготовки к сдаче 2-й части коллоквиума студенту рекомендуется изучить в полном объеме материал лекций 1-8 (в печатном варианте лекций - Олейник Т.А. «Основы дискретной математики: теория и практика», - М.:МИЭТ, 2010 - глава 1,2).

Образец билета коллоквиума приведен в таблице 7.

Таблица 7

БИЛЕТ КОЛЛОКВИУМА № 0 по курсу«Дискретная математика», Модуль 1 МП-П Часть I 1. Что такое разность множеств и ? Как обозначается эта операция? Как она иллюстрируется с помощью диаграмм Эйлера-Венна? Пусть , . Задайте перечислением элементов разность множеств и . 2. Что такое размещение с повторениями из элементов по ? По какой формуле вычисляется число таких размещений? Перечислите все размещения с повторениями из элементов 3-х элементного множества по 2. 3. Какие формулы над множеством булевых функций называются равносильными? Как доказывают равносильность формул, используя таблицы истинности? Докажите равносильность формул и . 4. Верно ли, что каждая булева функция может быть задана формулой над множеством ? Ответ обоснуйте. Задайте какой-нибудь формулой над множеством тождественную единицу ноль и штрих Шеффера. 5. Какие функции называют монотонными? Какие из элементарных функций двух переменных являются, а какие не являются монотонными? Приведите пример монотонной и пример не монотонной функции от трех переменных (функции задайте таблично). 6. Сформулируйте определение замкнутой системы булевых функций. Приведите примеры замкнутых систем функций. Часть II Сформулируйте и докажите теорему о разложении булевых функций по переменным.

Вопросы к коллоквиуму

1. Множества и операции над ними. Свойства операций над множествами. Правило суммы, правило включений-исключений. Разбиение множества.

2. Бинарные отношения на множестве. Свойства бинарных отношений. Отношение эквивалентности, отношение порядка. Теорема о свойствах классов эквивалентности.

3. Элементы комбинаторики. Правило произведения и правило суммы. Сочетания и размещения. Сочетания и размещения с повторениями. Биномиальные коэффициенты, треугольник Паскаля.

4. Булевы векторы и булевы функции от переменных. Элементарные булевы функции. Задание булевых функций формулами. Основные равносильности.

5. Существенные и фиктивные переменные булевых функций. Операция удаления (введения) фиктивной переменной.

6. Двойственные функции. Принцип двойственности.

7. Разложение булевых функций по переменным.

8. Совершенная дизъюнктивная нормальная форма функции.

9. Совершенная конъюнктивная нормальная форма функции.

10. Постановка задачи о минимизации ДНФ. Минимальная ДНФ. Сокращенная ДНФ. Тупиковые ДНФ.

11. Алгоритм поиска сокращенных, тупиковых и минимальных ДНФ.

12. Представление функций в виде полинома Жегалкина (существование и единственность). Поиск полинома Жегалкина методом равносильных преобразований и методом неопределенных коэффициентов.

13. Класс функций, сохраняющих 0. Класс функций, сохраняющих 1. Класс самодвойственных функций. Класс монотонных функций. Класс линейных функций

14. Замыкание системы булевых функций. Свойства замыкания. Теорема о замкнутости классов Поста.

15. Полные системы булевых функций. Теорема о полноте двух систем. Примеры полных систем. Базисы.

16. Лемма о функции, не сохраняющей 0. Лемма о функции, не сохраняющей 1.

17. Лемма о несамодвойственной функции.

18. Лемма о немонотонной функции.

19. Лемма о нелинейной функции.

20. Критерий полноты системы булевых функций (теорема Поста).

P.S. Объем подготовки по каждому вопросу зависит от того, на каком уровне студент собирается сдавать коллоквиум: базовом (студент собирается выполнять задания только 1-й части коллоквиума), или повышенном (студент также собирается отвечать на вопрос части 2). Вопросы, выделенные курсивом, изучаются исключительно для ответа на 2-ю часть коллоквиума.