Операции над множествами. Алгебра Буля

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

Под множеством понимают совокупность объектов любой природы, обладающих некоторым общим свойством.

Объекты, объединенные одним общим свойством, называют элементами множества и обозначают a, b, c,... x, y, z. Множества обозначают A, B, C,... X, Y, Z. Запись aÎ A означает, что элемент " a" принадлежит множеству А, bÏ A означает, что элемент " b" не принадлежит множеству А.

Множество, число элементов которого конечно, называют конечным и бесконечным в противном случае.

Конечные множества разделяются на счетные и несчетные. Если элементы бесконечного множества можно пронумеровать с помощью натурального ряда чисел, то оно называется счетным и несчетным в противном случае. Так множество четных чисел - счетное, множество действительных чисел - несчетное.

Конечные и счетные множества называются дискретными множествами.

Дискретная математика - математика дискретных множеств.

Если каждый элемент множества А есть в месте с тем элемент множества В, то множество А называется частью, или подмножеством множества В и обозначается АÍ В.

Если АÍ В и ВÍ А, то множества А и В называются равносильными и обозначаются А=В.

Множество, не содержащее ни одного элемента, называется пустым и обозначается V, Æ. Пустое множество считают конечным множеством и подмножеством любого множества.

Любое множество есть подмножество самого себя. Такое подмножество так же, как и пустое, называют несобственными подмножествами в отличии от всех других подмножеств, которые называют собственными.

Пример.

Пусть А={а₁, а₂, а₃}. Подмножества {а₁, а₂, а₃} и V - несобственные подмножества А. Собственные: {а₁}, {а₂}, {а₃}, {а₁, а₂}, {а₁, а₃}, {а₂, а₃}.

Число подмножеств любого конечного множества, содержащего “n” элементов, равно 2ⁿ.

Множество всех элементов, которые могут встретиться в данном исследовании, называют универсальным и обозначают “U”.

На множествах определены следующие операции.

Объединением, или суммой множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А или В.

С=АÈ В={c_i: c_iÎ A или c_iÎ B}

Пересечением множеств А и В называется множество С, элементы которого принадлежат как множеству А, так и множеству В.

С=АÇ В={c_i: c_iÎ A и c_iÎ B}

Дополнением множества А есть множество, элементы которого принадлежат универсальному множеству U и не принадлежат А.

С= ={c_i: c_iÎ U и c_iÏ А}

Данные три основные операции обладают следующими свойствами.

	АÈ А=А
	АÇ А=А
	АÈ В=ВÈ А
	АÇ В=ВÇ А
	(АÈ В)È С=АÈ (ВÈ С)
	(АÇ В)Ç С=АÇ (ВÇ С)
	АÇ (ВÈ С)=(АÇ В)È (АÇ С)
	АÈ (ВÇ С)=(АÈ В)Ç (АÈ С)
	AÈ U=U
	AÇ V=V
	AÇ U=A
	AÈ V=A
	AÈ =U
	AÇ =V
	=U
	=V
	AÌ B равносильно

Соотношения 1-20 обладают свойствами двойственности: если в одной из формул поменять местами È и Ç, U и V, Ì и É, то получим другую формулу из этого списка.

Порядок выполнения операций: дополнение (^¾ ),

пересечение (Ç),

объединение(È).

Названные операции и свойства к ним могут быть проиллюстрированы диаграммами Эйлера-Венна (рис. 1.1).

Рис. 1.1

Абстрактная алгебраическая система подмножеств некоторого универсального множества с введенными для них операциями объединения, пересечения, дополнения, обладающая перечисленными выше свойствами, образует Булеву алгебру.

К операциям над множествами относятся также:

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

С=А\ В={c_i: c_iÎ A и c_iÏ B}

Очевидно, что справедлива формула С=А\ В= .

2. Симметрическая разность (А\ В) È (В\ А).

Эти операции можно проиллюстрировать на диаграммах Эйлера-Венна (рис. 1.2).

Рис. 1.2

Декартово (прямое) произведение множеств А и В: А´ В=С.

3. Декартовым произведением А´ В является множество С всех упорядоченных пар < a_i, b_j>, где a_iÎ А, b_jÎ В, т.е.

С=А´ В={< a_i, b_j>: a_iÎ А и b_jÎ В}

Иллюстрацией декартова произведения множеств A={a₁, a₂}и B={b₁, b₂, b₃} является рис. 1.3.

Рис. 1.3

В общем случае декартовым произведением множеств А₁, А₂,... А_n называется множество

А₁´ А₂´... ´ А_n={< a₁, a₂,... a_n>: a₁Î А₁, a₂Î А₂... a_nÎ А_n}

Рассмотрим несколько упражнений, помогающих усвоить приведенные выше понятия.