Реферат: Основные положения дискретной математики

Объединением множеств А и В (аддитивная операция) называется новое множество С, состоящее из элементов множества А и из элементов множества В.

АВ

Пример:

Разностью множеств А и В называется новое множество С, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

А\ В из А вычесть В

Пример:

.

Кроме рассмотренных двухместных операций существует одна одноместная операция – дополнение. Дополнением множества М является множество (не М) = .

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

1.3 Свойства операций

1. Ассоциативность;

2. Коммутативность;

3. Дистрибутивность.

Операция называется ассоциативной, если выполняется равенство:

.

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел - ассоциативные операции, что и позволяет не ставить скобки (пример: a+b+c; abc) пример неассоциативной операции: возведение в степень (a^b )^c здесь скобки необходимы.

Операция называется коммутативной, если выполняется условие: . Сложение и умножение являются коммутативными (от перемены мест слагаемых сумма не меняется). Вычисление и деление – некоммутативные, некоммутативной так же является операция умножения матриц.

Операция называется дистрибутивной, если выполняется условие: .

1.4 Тождества и их доказательство

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

Доказать, что M=N, где M и N – выражения с множествами.

Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».

1) Сначала предположим, что некий элемент х принадлежит левой части равенства: эта запись звучит следующим образом:

«если , то ».