I.1. Множества и операции над ними

Дискретная математика

Методические указания и контрольные задания для студентов I курса заочной формы обучения

Оглавление

I. Краткие теоретические сведения. 1

I.1. Множества и операции над ними. 1

I.2. Бинарные отношения. 4

1. Отношение эквивалентности. 6

2. Отношение упорядоченности. 7

3. Функции. 9

I.3. Функции и формулы алгебры логики. 11

I.4. Двойственные функции и совершенные нормальные формы.. 18

1. Принцип двойственности. 18

2. Построение совершенных нормальных форм. 20

I.5. Полнота и замкнутость систем функций алгебры логики. 25

1. Полные системы функций алгебры логики. 25

2. Важнейшие замкнутые классы.. 27

II. Задание к контрольной работе по дискретной математике. 32

III. Варианты контрольных работ. 33

IV. Пример решения контрольной работы.. 46

V. Список литературы.. 54

I. Краткие теоретические сведения

I.1. Множества и операции над ними

Множество – понятие интуитивное, и поэтому не имеет точного математического определения. Под множеством обычно понимают совокупность определенных и хорошо различимых объектов, которые рассматриваются как единое целое. Объекты, составляющие множество, называются его элементами. Тот факт, что x является элементом множества M, записывается так: , где символ обозначает отношение принадлежности элемента множеству. Если x не является элементом множества M, то пишут: .

Два множества A и B называются равными, если они состоят из одних и тех же элементов, таким образом, тогда и только тогда, когда и . Символом обозначается отношение включения множеств, т.е. означает, что . В этом случае A называется подмножеством B, а B – надмножеством A. Если и , то A называется собственным подмножеством B, и в этом случае пишут: . Множество может состоять из конечного числа элементов (любого) или быть бесконечным. Множество, не содержащее элементов, называется пустым, и обозначается Æ. Множество множеств называют системой или семейством множеств.

Для записи множеств используется один из способов: а) перечисление элементов, например: , или б) указание свойств элементов, например: .

Объединением двух множеств A и B (или теоретико-множественной суммой) называется множество, состоящее из всех элементов, являющихся элементами хотя бы одного из множеств A или B. Таким образом, .

Объединением системы множеств называется множество .

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

Пересечением двух множеств A и B (или теоретико-множественным произведением) называется множество элементов, принадлежащих одновременно и A, и B. Таким образом, и .

Диаграмма Эйлера-Венна для пересечения двух множеств показана на рис.2.

Пересечением системы множеств называется множество .

Относительным дополнением множества B до множества A (или теоретико-множественной разностью) называется множество тех элементов A, которые не являются элементами B, таким образом, A \ B и . Диаграмма на рис.3.

Абсолютным дополнением множества A называется множество всех элементов, не принадлежащих A, таким образом, или U \ A, где U – некоторое универсальное множество, которое является надмножеством любого множества, рассматриваемого в данном рассуждении. Диаграмма на рис.4.

Симметрической разностью двух множеств A и B называется объединение двух разностей A \ B и B \ A, т.е. AÅB= (A \ B) (B \ A). Диаграмма на рис.5.

Декартовым (прямым) произведением двух множеств A и B называется множество всех упорядоченных пар (a,b)таких, что и , таким образом, и .

Декартовым (прямым) произведением множеств называется множество всех упорядоченных последовательностей – «энок» таких, что , т.е. .

Если , то множество называется прямой степенью множества A и обозначается Aⁿ.

Множества A и B в прямом произведении А´В называют координатными осями, а элементы xÎА и yÎВ – проекциями вектора z=(x,y)ÎА´В на координатные оси или координатами точки z (абсциссой и ординатой соответственно). Будем обозначать их пр_А z и пр_В z.

Пусть множество МÌ А´В, проекцией множества М на ось А называется множество всех абсцисс векторов из М , проекцией множества М на ось В называется множество всех ординат векторов из М, т.о. пр_А М={ пр_А z: zÎМ}={xÎА: $yÎВ и (x,y)ÎМ} и пр_В М={ пр_В z: zÎМ}={yÎВ: $xÎА и (x,y)ÎМ}.

Для многомерного случая A₁ ´ A₂ ´ A₃ ´ …´ A_n , каждое множество A_i называется i-той координатной осью. Проекция вектора z=(a₁, a₂,…, a_n) на i-тую координатную ось равна его i-той координате: пр_i z=a_i , где i=1,2,…,n. Если МÌ A₁ ´ A₂ ´…´ A_n , то пр_i М={ пр_i z: zÎМ}. Определены также проекции вектора z и множества векторов М на несколько координатных осей с номерами i₁, i₂,…,i_k: пр_{i1, i2…ik} z = ( a_i1, a_i2,…, a_ik) – k‑мерный вектор и пр_{i1, i2…ik} М = { пр_{i1, i2…ik} z: zÎМ } – множество k‑мерных векторов.

Пример:

Тройки вещественных чисел (а₁, а₂, а₃) можно рассматривать как точку в трехмерном пространстве (или вектор, проведенный в эту точку из начала координат). Тогда пр_i (а₁, а₂, а₃)=a_i, где i=1,2,3, пр_i,j (а₁, а₂, а₃)=(a_i, a_j), где i,j=1,2,3. См. рис.6.