Вариант 7. Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна

Фрагмент работы:

ВАРИАНТ 7

Задание 1

Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна.

=...

Решение:

а)...

Воспользуемся свойствами дистрибутивности, поглощения, а также......:

…

что и требовалось доказать.

б)......

Поскольку

и...

докажем, что... и..., пользуясь определениями операций.

1)...

и.........

2)...

и...

или...(что невозможно)......

То есть...............

что и требовалось доказать.

Задание 2

Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P1 ? A?B, P2 ? B2. Изобразить P1, P2 графически. Найти P = (P1?P2)-1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным.... =...

Решение:

Отношение Р1:

…

Отношение Р2:

…

Матрицы отношений:

…

Области определения:

Области значений:

Проанализируем матрицу...

…

1) На главной диагонали матрицы... есть один из элементов равен нулю - отношение Р2 не является рефлексивным

2) Найдем транспонированную матрицу...:

…

следовательно, отношение не является симметричным.

3) Перемножим матрицы... и.... Если отношение является антисимметричным, то результирующая матрица должна быть не больше матрицы, на главной диагонали которой расположены единицы, а остальные элементы нулевые:

…

Видим, что отношение... не является антисимметричным.

4) Определим транзитивность:

…

Поскольку..., то отношение... транзитивно.

Задание 3

Задано бинарное отношение P ? R2; найти его область определения и область значений. Проверить по определению, является ли P рефлексивным, симметричным, антисимметричным, транзитивным.... =...

Решение:

Данное отношение определяет окружность с центром в начале координат и радиусом 2:

…

Область определения:...

Область значений:...

1) Отношение рефлексивно, если..., т.е. должно выполняться равенство... для всех х из области определения. Но подставляя в это равенство..., получаем..., что невозможно. Таким образом, заданное отношение не рефлексивно.

2) Отношение симметрично, если из... следует..., то есть наряду с... должно также выполняться равенство.... Поскольку эти уравнения тождественны, то отношение симметрично.

3) Отношение антисимметрично, если из... и... следует, что.... Предполагая, что..., подставим в уравнение...:

Получили противоречие, следовательно, отношение не является антисимметричным.

4) Отношение транзитивно, если из... и... следует, что....

Пусть...

;......

…

Подставим значения... и... в.......... Получили противоречие, следовательно заданное отношение не транзитивно.

Задание 4

Доказать утверждение методом математической индукции:

для n ? 2.

Решение:

1) Проверим при...:

- выполняется.

2) Пусть при n также выполняется...

3) При... должно получиться:

…

Проверим

…

Таким образом, утверждение справедливо.

Задание 5

Восемь студентов должны сдавать зачет по пяти предметам: физике, архитектуре ЭВМ, математическому анализу, английскому языку и истории. Все зачеты назначены на одно время и каждый может сдавать только один зачет, поэтому студентам нужно распределиться на группы. Сколькими способами это можно сделать? Сколькими способами они могут разместиться после зачета за двумя совершенно одинаковыми столиками (не менее чем по одному) для того, чтобы отпраздновать результаты?

Решение:

Полагая, что на каждом из зачетов должен присутствовать как минимум один человек, получаем следующие варианты разбиения на группы: 3 группы по 2 человека и 2 группы по 1 или 1 группа по 3, 1 по 2, 3 по 1 или 1 по 4 и 4 по 1. Соответственно этому способов сформировать группы может быть:

…

За столиками студенты могут разместиться следующим образом: 1+7 или 2+6 или 3+5 или 4+4 или 5+3 или 6+2 или 7+1. Количество способов размещения в данном случае:

…

Задание 6

Сколько существует положительных трехзначных чисел: а) не делящихся ни на одно из чисел 5, 6, 16? б) делящихся ровно на одно из этих трех чисел?

Решение:

Введем обозначения:

U - множество всех трехзначных чисел от 100 999;

А - множество трехзначных чисел, делящихся на 5;

В - множество трехзначных чисел, делящихся на 6;

С - множество трехзначных чисел, делящихся на 16;

D - множество трехзначных чисел, не делящихся на 5, 6, 16.

Найдем мощности этих множеств. Мощность множества А будет равна разности мощности множества всех чисел от 0 до 999, делящихся на 5, и мощности множества чисел от 0 до 99, делящихся на 5. Количество чисел от 0 до 999, делящихся на 5:

…

Количество чисел от 0 до 99, делящихся на 5:

…

Тогда.... Мощность множеств В и С:

…

Найдем теперь мощности пересечений множеств. Сначала определим количество чисел, делящихся на 5 и на 6:

…

562 трехзначных положительных числа не делятся на 5, 6, 16.

б) Количество чисел, делящихся только на 5:

…

Количество чисел, делящихся только на 6:

…

Количество чисел, делящихся только на 16:

…

Общее количество чисел: 141+113+38=292

292 трехзначных положительных числа делятся только на 5, на 6 или на 16.

Задание 7

Найти коэффициенты при a=x4·y·z3, b=x·y4·z, c=y2·z4 в разложении (3·x2+5·y+2·z)6.

Решение:

Воспользуемся бином Ньютона:

…

Выделим слагаемое, содержащее коэффициент...:

…

Определим коэффициент:

Слагаемого, содержащего коэффициент..., не существует (минимальная степень х вторая), поэтому....

Выделим слагаемое, содержащее коэффициент...:

…

Задание 8

Найти последовательность {an}, удовлетворяющую рекуррентному соотношению 3·an+2 - 8·an+1 + 5·an = 0· и начальным условиям a1=10, a2=20.

Решение:

Перейдем к характеристическому уравнению:

Общее решение заданного соотношения:

…

Частное решение:

Искомая последовательность:

…

Задание 9

Орграф задан матрицей смежности. Необходимо:

а) нарисовать граф;

б) выделить компоненты сильной связности;

в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

1

0

0

1

0

1 0

0

1

0

0

0 0

1

1

0

0

1 1

0

0

0

1

0 1

0

0

1

0

1 0

0

0

0

0

1

Решение:

а) Изображение графа:

…

б) Компоненты сильной связности:

1) а1, а5, а4 2) а3, а2

в) Заменяем все дуги ребрами:

…

Эйлерова цепь: а2, а3, а6, а1, а4, а5, а6

Задание 10

Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти:

а) остовное дерево минимального веса;

б) кратчайшее расстояние от вершины v3 до остальных вершин графа, используя алгоритм Дейкстры.

…

Решение:

Изображение графа:

…

а) Остовное дерево минимального веса:

1) В качестве ребра минимального веса выберем (а5,а6)

2) Ребром минимального веса, исходящим из вершин а5 или а6, будет ребро (а6,а1).

3) Ребрами минимального веса, исходящими из вершины а1, будут ребра (а1,а3) или (а1,а4)

4) Ребром минимального веса будет ребро (а4,а2).

5) Следующим ребром, не образующим цикла с уже введенными, будет ребро (а1,а3).

6) Добавление любого другого из трех оставшихся ребер приведет к образованию цикла. Остов минимального веса:

…

Вес минимального остова....

б) Присвоим вершине а3 метку 0, остальным вершинам ?:

…

1) Определим метки соседних с а3 вершин как сумму метки вершины а3 и длины соответствующего ребра. Для вершины а1 метка равна 0+2=2, для вершины а6 метка равна 0+4=4, для вершины а4 0+6=6. После этого вычеркнем вершину а3 как посещенную:

…

2) Переходим к вершине а1 как соседней с а3, поскольку длина пути до нее минимальна. Соседними с а1 являются вершины а2, а3, а4, а6. Вершину а3 уже не рассматриваем. Если идти в вершину а4 через а1, то длина пути будет 2+2=4. Это меньше, чем имеющаяся метка а4 6, поэтому меняем метку на 4. Проверяем а6. Длина пути до нее через а1 равна 2+3=5. Это больше, чем имеющаяся у а6 метка 4, поэтому метка не меняется. Длина пути до вершины а2 равна 2+5=7, это меньше имеющейся у нее метки ?, поэтому метка становится равна 7. После этого вычеркнем вершину а1 как посещенную:

…

3) Следующая вершина а6, соседние с ней а1, а3 (их уже не рассматриваем), метка пятой вершины равна 4+2=6, что меньше бесконечности. Вычеркиваем а6:

…

4) Следующая вершина а4 (как соседняя с а1), ее соседи из невычеркнутых а2 и а5. Если идти через нее в а2, то метка станет 4+3=7, т.е.такой же как и в настоящий момент, значит, метка не меняется. Если идти через нее в а5, то метка станет 4+5=9>6, значит, метка тоже остается прежней. Вычеркиваем а4:

…

5) Переходим к а2. Единственный невычеркнутый сосед - а5, путь до а5 через а2 равен 7+4=11>6, значит, метка не меняется. Вычеркиваем а2 и следом а5, поскольку у последней нет невычеркнутых соседей:

…

Метки вершин соответствуют кратчайшим расстояниям от вершины а3 до остальных вершин: до а1 2, до а2 7, до а4 4, до а5 6, до а6 4.

…