Задания

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

Решение.Для удобства введем обозначения:

,

Множества равны, если они состоят из одних и тех же элементов. Следовательно, чтобы доказать тождество , надо показать, что каждый элемент является элементом множества и наоборот.

Пусть . Это означает, что либо , либо ( по определению объединения множеств ). Если , то и , а это значит , что

.

Если , то, по определению пересечения множеств, и

. Если , то ; если , то . Значит и . Следовательно

Итак, если , то , то есть .

Теперь покажем обратное. Пусть . Тогда, по определению пересечения множеств, и . По определению объединения множеств получаем: , либо и , либо .

Итак могут представиться следующие случаи: 1) и 2) и 3) и 4) и .

В случаях 1), 2), 3) , откуда следует, что

.

В случае 4) и , следовательно , а отсюда вытекает, что

Таким образом, если , то , то есть .

Так как и , то .

Тождество доказано.

Приведенные рассуждения можно представить в виде схемы:

Т.е.

и

и

Т.е.

Проверим тождество при помощи диаграммы Эйлера-Венна.

Известно, что любое множество можно изобразить графически при помощи диаграммы Венна (Эйлера-Венна). Для этого рисуют либо замкнутую кривую, либо замкнутую ломанную линию и сжимают, что область, ограниченная этими линиями, изображает рассматриваемое множество. В нашем примере на рис. 1и 2 универсальное множество U изображено в виде прямоугольника, а его подмножества A, B, C изображены овалами, ограниченными замкнутыми линиями.

Рассматриваемые множества на диаграммах изображены двойной штриховкой. Множества A, B, C надо стараться располагать одинаково на обеих диаграммах. Выделенные множества представляют одну и ту же часть универсального множества. Это и доказывает тождество.

2. Исходя из свойств сочетаний вычислить сумму:

, (1)

,

или

, (2)

, (3)

Все последующие преобразования будут даны с пояснениями.

Здесь использована формула определения числа сечения

В правой части знаменатели доведены до полных факториалов, а числители, для сохранения равнозначности преобразований, умножены на соответствующие величины.

Таким образом,

При n=6 имеем

,

Итак .

3. Задана симметрическая матрица А неотрицательных целых чисел.

1. Нарисовать на плоскости граф (единственный с точностью до изоморфа), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности графа G.

2. Нарисовать на плоскости орграф (единственный с точностью до изоморфизма), имеющий заданную матрицу А свое матрицей смежности. Найти матрицу инцидентности орграфа G.

А=

Решение1. Напомним, что матрицей смежности графа с множеством вершин называется матрица размера , в которой элемент равен числу ребер в G, соединяющих с . Матрица смежности графа G является симметрической, то есть

= .

Построим граф по заданной матрице смежности.

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

А=