дискретная математика 7 вариант. Документ. Решение. Действительно Так как, то
![]()
|
ВАРИАНТ 7 1.Определить операции ∪ и \ (каждую по отдельности) через операции Δ и ∩. Решение. ![]() Действительно: Так как ![]() 1). По определению операции ![]() ![]() ![]() ![]() ![]() ![]() 2). По определению операции ![]() ![]() ![]() ![]() ![]() ![]() 2. Является ли тавтологией формула ![]() Решение. Предположим, что формула ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() не является тавтологией. 3. Переведите с естественного языка на язык логики предикатов: Для любого натурального числа найдется большее его простое число. Решение. Универсум: ![]() Предикаты: ![]() ![]() Формула: ![]() 4. Переведите с естественного языка на язык логики предикатов: Все лягушки, увидев аиста, прыгают и квакают. Решение. Универсум: М = {лягушки}. Предикаты: ![]() ![]() Формула: ![]() 5. Для бинарного отношения x ρ y ⇔ «x перпендикулярна y», определенного на множестве всех прямых плоскости, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. Решение. Рассмотрим наличие свойств у заданного отношения: а) рефлексивность : для любого ![]() ![]() б) симметричность: для любых ![]() ![]() ![]() ![]() ![]() в) антисимметричность: если для любых ![]() отсюда не следует, что ![]() ![]() г) транзитивность: пусть для любых ![]() отсюда не следует, что ![]() ![]() Таким образом, заданное отношение обладает симметричностью, и не обладает рефлексивностью, антисимметричностью, транзитивностью. 6. На множестве R вещественных чисел задано отношение ![]() Решение. 1) заданное на множестве R отношение ![]() ![]() ![]() 2) заданное на множестве R отношение ![]() ![]() ![]() ![]() 3) заданное на множестве R отношение ![]() ![]() ![]() ![]() Таким образом, данное отношение рефлексивно, симметрично, транзитивно и , следовательно, - по определению эквивалентности,- оно является отношением эквивалентности на множестве R. Класс эквивалентности, порожденный элементом ![]() ![]() класс эквивалентности, порожденный нулем: ![]() 7. Используя математическую индукцию, докажите, что ![]() Решение. Базис индукции: ![]() ![]() Индуктивный переход: пусть при произвольном ![]() ![]() докажем, что исходное равенство выполняется при ![]() Запишем сумму из ![]() ![]() Что и требовалось доказать. Таким образом, равенство ![]() ![]() 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O(следующая)): ![]() Решение. 1) ![]() докажем с помощью предела: ![]() 2) ![]() докажем с помощью предела: ![]() расширим область определения функций на всю числовую ось (пусть ![]() ![]() 3) ![]() докажем с помощью предела: ![]() Здесь было использовано, что для ![]() ![]() ![]() Индуктивный переход: пусть при ![]() ![]() ![]() ![]() 4) ![]() докажем с помощью предела: ![]() В итоге получаем : ![]() ![]() ![]() ![]() |