ДМ РК1 подготовка. Теоретические вопросы (3 балла)
 Скачать 237.42 Kb.
|
|
Дискретная математика 4-й семестр, РТ5 (2019-20 уч. год) Модуль 1, рубежный контроль Вопросы для подготовки Теоретические вопросы (3 балла) 1. Как определяются операции объединения, пересечения, разности, симметрической разности и дополнения множеств? 2. Что такое кортеж? Что называют декартовым произведением множеств? Перечислите свой- ства декартова произведения множеств. 3. Что называют отображением из множества 𝐴𝐴 в множество 𝐵𝐵? Какое отображение называют инъективным, сюръективным и биективным? 4. Что называют соответствием из множества 𝐴𝐴 в множество 𝐵𝐵? Как строится график и граф со- ответствия? 5. Что такое область определения и область значения соответствия? Что такое сечение соответ- ствия по элементу 𝑥𝑥? В каком случае соответствие называют функциональным по компо- ненте? 6. Что называют бинарным отношением на множестве? Что называют 𝑛𝑛-арным отношением на множестве? Что называют рефлексивно-транзитивным замыканием бинарного отношения на множестве? 7. Какое бинарное отношение на множестве называют рефлексивным, иррефлексивным, симмет- ричным, антисимметричным и транзитивным? 8. Какое бинарное отношение на множестве называют толерантностью и какое эквивалентно- стью? 9. Какое бинарное отношение на множестве называют порядком, предпорядком, линейным по- рядком и частичным порядком? 10. Как на упорядоченном множестве определяется строгий порядок, двойственный порядок и от- ношение доминирования? 11. Какой элемент множества называют наибольшим, наименьшим, максимальным и минималь- ным? Что такое точная верхняя грань и точная нижняя грань множества? 12. Что такое булева функция и булев куб? Как определяется булев порядок и лексикографиче- ский порядок на булевом кубе? 13. Что называют фиктивной переменной булевой функции? Какие булевы функции называют равными? 14. Как определяется композиция булевых функций? Определите понятие формулы над заданным множеством 𝐹𝐹 булевых функций. Как определяется функция, представляемая формулой? 15. Что такое дизъюнктивная нормальная форма (ДНФ), совершенная дизъюнктивная нормальная форма (СДНФ), конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нор- мальная форма (СКНФ)? 16. Какая ДНФ называется минимальной и какая кратчайшей? В чём состоит задача минимизации булевых функций в классе ДНФ? 17. Что такое импликанта для заданной булевой функции, простая импликанта и ядровая импли- канта? 18. Какая ДНФ называется сокращённой? Какие импликанты в сокращённой ДНФ называются избыточными? Какая ДНФ называется тупиковой? 19. Какое множество булевых функций называют базисом Жегалкина? Что такое полином Жегал- кина? В чём заключается метод неопределённых коэффициентов построения полинома Же- галкина по таблице булевой функции? 20. Какая булева функция называется самодвойственной, какая монотонной и какая линейной? Теоретические вопросы ( 5 баллов) 1. Перечислите свойства операций объединения, пересечения, разности и симметрической раз- ности множеств. 2. Что называют характеристической функцией множества? В чём заключается метод характе- ристических функций доказательства теоретико-множественных тождеств? Напишите харак- теристические функции для пересечения, объединения, дополнения, разности и симметриче- ской разности. 3. Как определяется композиция соответствий и обратное соответствие? Перечислите свойства композиции соответствий и обратного соответствия. 4. Сформулируйте необходимые и достаточные условия рефлексивности, иррефлексивности, симметричности, антисимметричности и транзитивности бинарного отношения. 5. Что называют матрицей бинарного отношения? Сформулируйте теорему о матрице объедине- ния, пересечения и композиции бинарных отношений, а также о матрице обратного отноше- ния. 6. Сформулируйте теорему о том, как проверить рефлексивность, иррефлексивность, симмет- ричность, антисимметричность и транзитивность бинарного отношения по его матрице. 7. Что называют классом эквивалентности, фактор-множеством по заданному отношению экви- валентности и разбиением множества? 8. Сформулируйте определение индуктивного упорядоченного множества. Какое отображение одного индуктивного упорядоченного множества в другое называют непрерывным и какое монотонным? 9. Назовите основные этапы алгоритма Квайна–Мак-Клоски. 10. Перечислите классы Поста с описанием того, из каких функций состоит каждый класс. Что означает утверждение о том, что каждый класс Поста замкнут? Теоретические вопросы (6 баллов) 1. В чём заключаются метод двух включений и метод эквивалентных преобразований доказа- тельства теоретико-множественных тождеств? Докажите дистрибутивность пересечения от- носительно объединения методом двух включений. 2. Сформулируйте и докажите теорему о связи между отношением эквивалентности и разбие- нием множества. 3. Сформулируйте и докажите теорему о связи монотонности и непрерывности отображения од- ного индуктивного упорядоченного множества в другое. 4. Что называют неподвижной точкой отображения? Сформулируйте и докажите теорему о не- подвижной точке отображения индуктивного упорядоченного множества в себя. 5. Сформулируйте и докажите теорему о представлении булевой функции в виде СДНФ и СКНФ. 6. Сформулируйте и докажите утверждение о немонотонной булевой функции. 7. Сформулируйте и докажите утверждение о реализации констант 0 и 1 с помощью несамодвой- ственной булевой функции и отрицания. 8. Сформулируйте и докажите утверждение о реализации конъюнкции с помощью нелинейной булевой функции, констант и отрицания. 9. Сформулируйте и докажите утверждение о замкнутости классов Поста. 10. Сформулируйте и докажите критерий Поста о полноте множества булевых функций. Примеры задач 1. Метод двух включений (2 балла) 1.1. Используя метод двух включений, для произвольных бинарных отношений 𝜌𝜌, 𝜏𝜏 и 𝜎𝜎 вы- ясните, справедливо ли тождество (𝜌𝜌 −1 ∘ 𝜎𝜎 −1 ) ∘ 𝜏𝜏 −1 = �𝜏𝜏 ∘ (𝜎𝜎 ∘ 𝜌𝜌)� −1 1.2. Покажите, что для произвольных бинарных отношений 𝜌𝜌 1 и 𝜌𝜌 2 на множестве 𝐴𝐴 справед- ливо тождество (𝜌𝜌 1 ∩ 𝜌𝜌 2 ) −1 = 𝜌𝜌 2 −1 ∩ 𝜌𝜌 1 −1 2. Свойства бинарных отношений (3 балла) 2.1. Пусть в ℝ 3 задана плоскость 𝑎𝑎𝑥𝑥 + 𝑏𝑏𝑏𝑏 + 𝑐𝑐𝑐𝑐 = 0. Точки с радиус-векторами 𝑟𝑟⃗ 1 и 𝑟𝑟⃗ 2 связаны бинарным отношением 𝜏𝜏, если �(𝑟𝑟⃗ 1 − 𝑟𝑟⃗ 2 ), 𝑛𝑛�⃗ � = 0, где 𝑛𝑛�⃗ – нормаль к указанной плоскости, а ( ⋅ , ⋅ ) – скалярное произведение векторов. Покажите, что 𝜏𝜏 есть отношение эквива- лентности. Что будет классом эквивалентности точки из ℝ 3 ? 2.2. На множестве упорядоченных пар (𝑥𝑥, 𝑏𝑏), 𝑥𝑥, 𝑏𝑏 ∈ ℝ, задано отношение 𝜏𝜏 по правилу (𝑥𝑥 1 , 𝑏𝑏 1 ) 𝜏𝜏 (𝑥𝑥 2 , 𝑏𝑏 2 ) ⇔ 𝑥𝑥 1 2 − 𝑏𝑏 1 2 = 𝑥𝑥 2 2 − 𝑏𝑏 2 2 Покажите, что 𝜏𝜏 – отношение эквивалентности. Укажите классы эквивалентности. Для точки �1, √2� изобразите класс эквивалентности графически. 2.3. Пусть 𝐴𝐴 – конечное множество. Какое отношение эквивалентности на нём даёт наиболь- шее число эквивалентных классов? Сколько? Сколькими способами можно задать отно- шение эквивалентности, разбивающее 𝐴𝐴 на два класса? 2.4. Пусть 𝐹𝐹 – множество функций, непрерывных на [𝑎𝑎, 𝑏𝑏], и на множестве 𝐹𝐹 задано бинарное отношение 𝜏𝜏: 𝑓𝑓(𝑥𝑥) 𝜏𝜏 𝑔𝑔(𝑥𝑥), если ∫ 𝑓𝑓(𝑥𝑥) 𝑑𝑑𝑥𝑥 𝑏𝑏 𝑎𝑎 = ∫ 𝑔𝑔(𝑥𝑥) 𝑑𝑑𝑥𝑥 𝑏𝑏 𝑎𝑎 . Установите, будет ли отноше- ние 𝜏𝜏 отношением толерантности или эквивалентности. Если отношение является экви- валентностью, опишите классы эквивалентности по этому отношению. 2.5. Пусть 𝐹𝐹 – множество функций, непрерывных на [𝑎𝑎, 𝑏𝑏], и на множестве 𝐹𝐹 задано бинарное отношение 𝜏𝜏: 𝑓𝑓(𝑥𝑥) 𝜏𝜏 𝑔𝑔(𝑥𝑥), если и только если ∫ 𝑓𝑓(𝑥𝑥) 𝑑𝑑𝑥𝑥 𝑏𝑏 𝑎𝑎 ≤ ∫ 𝑔𝑔(𝑥𝑥) 𝑑𝑑𝑥𝑥 𝑏𝑏 𝑎𝑎 . Установите, яв- ляется ли 𝜏𝜏 отношением предпорядка или порядка. 2.6. Пусть 𝜏𝜏 – бинарное отношение на множестве ℕ 2 : (𝑎𝑎, 𝑏𝑏) 𝜏𝜏 (𝑐𝑐, 𝑑𝑑), если и только если 𝑎𝑎 ≤ 𝑐𝑐 и 𝑏𝑏 ≥ 𝑑𝑑. Является ли 𝜏𝜏 отношением порядка? Если да, установите, является ли этот по- рядок линейным и существует ли наименьший элемент по отношению 𝜏𝜏. 2.7. Пусть на множестве неотрицательных рациональных чисел определено бинарное отно- шение 𝑣𝑣: (𝑎𝑎 𝑏𝑏 ⁄ ) 𝑣𝑣 (𝑐𝑐 𝑑𝑑 ⁄ ), если и только если 𝑎𝑎𝑑𝑑 ≤ 𝑏𝑏𝑐𝑐. Покажите, что 𝑣𝑣 является отноше- нием порядка. Существует ли наименьший элемент? Является ли этот порядок линей- ным? 2.8. Пусть на множестве 𝑃𝑃 последовательностей длины 3, элементами которых являются натуральные числа, задано бинарное отношение 𝜏𝜏: 𝑎𝑎 1 𝑎𝑎 2 𝑎𝑎 3 𝜏𝜏 𝑏𝑏 1 𝑏𝑏 2 𝑏𝑏 3 , если и только если 𝑎𝑎 𝑖𝑖 делит 𝑏𝑏 𝑖𝑖 нацело, 𝑖𝑖 = 1, 2, 3. Установите, является ли 𝜏𝜏 отношением порядка. Является ли этот порядок линейным? Существует ли наименьший элемент? 2.9. Пусть на множестве 𝑃𝑃 последовательностей длины 2, элементами которых являются це- лые числа (кроме нуля), задано бинарное отношение 𝜏𝜏: 𝑎𝑎 1 𝑎𝑎 2 𝜏𝜏 𝑏𝑏 1 𝑏𝑏 2 , если и только если 𝑎𝑎 𝑖𝑖 делит 𝑏𝑏 𝑖𝑖 нацело, 𝑖𝑖 = 1, 2. Установите, является ли 𝜏𝜏 отношением предпорядка, по- рядка. 2.10. Пусть ≼ 𝑎𝑎 есть отношение порядка на множестве 𝐴𝐴, а ≼ 𝑏𝑏 – на множестве 𝐵𝐵. На множестве 𝐴𝐴 × 𝐵𝐵 зададим бинарное отношение ⋞: (𝑎𝑎 1 , 𝑏𝑏 1 ) ⋞ (𝑎𝑎 2 , 𝑏𝑏 2 ), если и только если 𝑎𝑎 1 ≼ 𝑎𝑎 𝑎𝑎 2 и 𝑏𝑏 1 ≼ 𝑏𝑏 𝑏𝑏 2 . Докажите, что ⋞ есть отношение порядка на 𝐴𝐴 × 𝐵𝐵. Является ли этот порядок линейным, если линейными являются порядки на множествах 𝐴𝐴 и 𝐵𝐵? 2.11. На множестве упорядоченных пар (𝑥𝑥, 𝑏𝑏), 𝑥𝑥, 𝑏𝑏 ∈ ℝ, задано отношение 𝜋𝜋 по правилу (𝑥𝑥 1 , 𝑏𝑏 1 ) 𝜋𝜋 (𝑥𝑥 2 , 𝑏𝑏 2 ) ⇔ 𝑥𝑥 1 ≤ 𝑥𝑥 2 и 𝑏𝑏 1 ≤ 𝑏𝑏 2 Покажите, что 𝜋𝜋 – отношение порядка. Устано- вите, является ли этот порядок линейным. Найдите множество нижних и верхних граней множества {𝐴𝐴, 𝐵𝐵}, где 𝐴𝐴 = (1, 2) и 𝐵𝐵 = (2, 1). Укажите inf{𝐴𝐴, 𝐵𝐵} и sup{𝐴𝐴, 𝐵𝐵}, если послед- ние существуют. Приведите графическую иллюстрацию. 3. Минимизация булевой функции (4 балла) 3.1. Минимизируйте функцию 𝑓𝑓 = (0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0) с использованием карты Карно. 3.2. Минимизируйте функцию 𝑓𝑓 = (1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1) с использованием карты Карно. 4. Проверка самодвойственности, монотонности и линейности булевой функции (4 балла) 4.1. Покажите, что функция 𝑓𝑓 = (0 1 0 1 1 1 1 1) не является самодвойственной. С использо- ванием отрицания реализуйте константы 0 и 1, т. е. задайте их формулами над {𝑓𝑓, � }. 4.2. Покажите, что функция 𝑓𝑓 = (0 0 0 1 1 0 1 0) не является монотонной. Указать все сосед- ние наборы, на которых нарушается монотонность. С использованием констант 0 и 1 ре- ализуйте отрицание, т. е. задайте отрицание формулой над {𝑓𝑓, 0, 1}. 4.3. Покажите, что функция 𝑓𝑓 = (1 0 1 0 0 1 1 1) не является линейной. С использованием констант 0, 1 и отрицания реализуйте конъюнкцию, т. е. задайте её формулой над {𝑓𝑓, 0, 1, � }. 5. Исследование полноты множества булевых функций (5 баллов) 5.1. Исследуйте на полноту множество булевых функций 𝐹𝐹 = {𝑓𝑓 1 , 𝑓𝑓 2 }, где 𝑓𝑓 1 = (0 1 0 1), 𝑓𝑓 2 = (0 0 1 1 1 1 0 0). В случае, если множество 𝐹𝐹 не является полным, добавьте к нему функ- цию общего вида так, чтобы множество стало полным. 5.2. Исследуйте на полноту множество булевых функций 𝐹𝐹 = { ⇒, 𝑓𝑓 1 }, где 𝑓𝑓 1 = (1 0 1 0 1 1 0 0). В случае, если множество 𝐹𝐹 не является полным, добавьте к нему функ- цию общего вида так, чтобы множество стало полным. |