Дискретная математика / Множества

Множества

Основные положения

Любое понятие дискретной математики можно определить с помощью понятия множества.

Под множеством понимается объединение в одно общее объектов, различаемых нашей интуицией и мыслью. Множества обозначаются, как правило, большими (прописными) буквами. Объекты – это элементы множества, обозначается малыми (прописными) буквами mM, или mM. Множество можно задавать перечислением элементов, из которых оно состоит, в этом случае M={0,1,2,3,4, …, 9} – множество цифр десятичного алфавита. Еще одним способом является способ, при котором элементы характеризуются определенными свойствами: M = {i / i - целое, 0 ≤ i ≤ 9}, где справа от наклонной черты указаны свойства элементов этого множества.

Множество является бесконечным, если число элементов в нем бесконечно, в противном случае множество конечное. Если же множество не содержит ни одного элемента, то оно называется пустым (Ø).

Два множества эквивалентны, если между их элементами можно установить взаимнооднозначное соответствие. Общее свойство эквивалентных множеств называется мощностью множества |М|.

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

Для обозначения собственных подмножеств используется знак «» - строгого включения.

1.1.Операции над множествами

1) Объединением множеств A и B называется множество, элементы которого принадлежат или A, или B, или одновременно и А и В (обозначение: AB).

Высказывательная форма объединения:

AB = {x / x  A  x  B}

2) Пересечением множеств А и В называется множество, элементы которого принадлежат одновременно и А и В (обозначение: AB)

Высказывательная форма пересечения:

.

Дополнением к множеству A называется множество, состоящее из всех элементов, не принадлежащих A в заданном универсальном множестве (обозначение: )

Высказывательная форма дополнения:

3) Разностью множеств A и B называется множество, состоящее из тех и только тех элементов множества A, которые не принадлежат множеству B (обозначение: A\B)

Высказывательная форма разности:

.

4) Симметрической разностью множеств A и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В или из элементов множества В, не принадлежащих множеству А (обозначение: А÷В)

Высказывательная форма симметрической разности:

1.2. Свойства операций над множествами

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

• Законы идентичности:

• Коммутативные законы:

• Дистрибутивные законы:

• Ассоциативные законы:

• Инволюционный закон:

• Законы де Моргана:

• Законы идентичности:

• Законы дополнительности:

• Законы поглощения:

1.3. Декартово произведение множеств

Одним из важных понятий теории множеств является поня­тие декартова произведения множеств.

Декартовым произведением «А х В» множеств А и В называется множество М вида:

М = {(ai, bj) : аi А, bj В}

Здесь круглыми скобками () обозначается последователь­ность, т.е. множество, в котором зафиксирован порядок элемен­тов (упорядоченное множество). Другое название такой последо­вательности — вектор (кортеж). Вектор (кортеж) – это упорядоченный набор (последовательность) элементов, в котором каждый элемент занимает определённое место: А=(а1, а2, а3). Число элементов кортежа называют его длиной или размером. Кортеж длиной 2 называют двойкой (упорядоченной парой).

Прямым (декартовым) произведением множеств A и B называют множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству A, а вторая – множеству B (обозначается AB). Таким образом, элементами прямого произведения множеств являются двухэлементные кортежи (a, b);

Прямым произведением n множеств A1, A2,…,An называют множество A= A1A2...An и состоящее из вех тех и только тех кортежей длины R, первая компонента которых принадлежит множеству A1, вторая - A2 и так далее.

A1A2...An={( a1, a2,…,an)/ a1A1, a2 A2,…,anAn}

Если a1= a2=…=an, то множество A1A2...An называется прямой n-ной степенью множества A и обозначается An.