Абстрактные законы операций над множествами

⇐ ПредыдущаяСтр 3 из 8Следующая ⇒

Введенные операции над множествами подчинены некоторым очень простым абстрактным законам, которые будут перечислены в этом разделе.

Эти законы очень напоминают элементарные законы алгебры высказываний.

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

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

1.A∪ A=A

2.A∩ A=A

3.A∪ B=B∪ A

4.A∩ B=B∩ A

5.A∪ (B∪ C)=(A∪ B)∪ C

6.A∩ B(B∩ C)=(A∩ B) ∩ C

7.A∩ (B∪ C)=(A∩ B)∪ (A∩ C)

8.A∪ (B∩ C)=(A∪ B) ∩ (A∪ C)

9.A∪ U=U

10.A∩ Ø =Ø

11.A∩ U=A

12.A∪ Ø =A

Законы для дополнений:

2.A∪ =U

3.A∩ =Ø

Законы для разностей множеств:

1.A\B=A∩

2.U\A=

3.A\U=Ø

4.A\Ø =A

5.Ø \A=Ø

6.A\A=Ø

7.((A\B)\C)=A\(B∪ C)

8.A\(B\C)=(A\B)∪ (A∩ C)

9.A∪ (B\C)=(A∪ B)\(C\A)

10.A∩ (B\C)=(A∩ B)\(A∩ C)

Кортежи и декартовое произведение множеств

Определение. Пусть даны множества . Кортежем длины n, составленным из элементов этих множеств, называется конечная последовательность , где для всех k, , имеем .

Элемент называется k-йкоординатой или k-й компонентой кортежа α.

Два кортежа равны в том и только в том случае, когда они имеют одинаковую длину, причем их координаты, стоящие на местах с одинаковыми номерами, равны, т. е. кортежи равны только в том случае, когда m=n, причем для всех 1≤ k≤ n.

Кортежи длины два называют упорядоченными парами, длины три — упорядоченными тройками,..., длины п — упорядоченными n-ками. Для краткости речи слово «упорядоченные» часто опускают.

Кортеж, не содержащий ни одной координаты, т. е. кортеж длины 0, называется пустым.

Основные отличия понятий кортежа и множества следующие:

а) в множестве порядок элементов не играет роли, а кортежи, отличающиеся порядком элементов, различны, даже в случае, когда они имеют одинаковый состав;

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

В дальнейшем, чтобы различать множества и кортежи, будем элементы множества заключать в фигурные скобки, а координаты кортежа — в угловые.

Пусть — некоторые множества. Их декартовым произведением называют множество, состоящее из кортежей вида ( ), где . Декартово произведение обозначается так: .

Бинарные отношения

Пусть А и В два конечных множества. Декартовым произведением множеств А и В называют множество А х В, состоящее из всех упорядоченных пар (а, b), где .

Бинарным отношением между элементами множеств А и В называется любое подмножество R множества .

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т. е. множество пар), то говорят, что параметры х и у связаны бинарным отношением R, если пара (х, у) является элементом R, т. е. (х, у) ∊ R.

Высказывание: «предметы х и у связаны бинарным отношением R» записывают в виде х R y.

Таким образом, х R y ↔ (х, у) ∊ R.

Если R ⊂ А х А, то говорят, что бинарное отношение определено на множестве А.

Областью определения бинарного отношения R называется множество, состоящее из таких х, для которых (х, у) ∊ R хотя бы для одного у.

Область определения бинарного отношения будем обозначать .

Областью значений бинарного отношения R называется множество всех у, для которых (х, у) ∊ R хотя бы для одного х.

Область значений бинарного отношения будем обозначать .

Рассмотрим специальные бинарные отношения:

а) Бинарное отношение R на непустом множестве А называется рефлексивным, если (х, х) ∊ R для всех х ∊ А, и иррефлексивным, если (х, х) ∉ R для всех х ∊ А.

б) Бинарное отношение R на непустом множестве А называется симметричным, если (х, у) ∊ R => (у, х) ∊ R, и антисимметричным, если (х, у) ∊ R и (у, х) ∊ R => х = у.

в) Бинарное отношение R на непустом множестве А называется транзитивным, если (х, у) ∊ R и (у, z) ∊ R => (х, z) ∊ R.

Рефлексивное, транзитивное и симметричное бинарное отношение R на множестве А называется эквивалентностью на А.

Отображение множеств

Соответствие f, сопоставляющее каждому элементу х множеств X один и только один элемент множества Y, называется отображением множества X во множество Y.

Элемент множества Y, соответствующий при отображении / элементу х из X, обозначают f(х) и называют образом элемента х при этом отображении.

Если f(х) = у, то элемент х называют прообразом элемента у при отображении f.

Совокупность всех прообразов элемента у при отображении f называется полным прообразом этого элемента и обозначается .

Правая часть читается: «совокупность таких х, что f(x) = у.

Каждому из подмножеству А множества X (А ⊂ X) соответствует его образ f(A) при отображении f. Этот образ состоит всех элементов множества Y, которые являются образами какого-нибудь элемента из А: f(A) = {y: y = f(a), а ∊ A}.

Каждому подмножеству В множества Y (В ⊂ Y) соответствует его полный прообраз (В) при отображении f. Он состоит из всех элементов, образы которых принадлежат В: (B) = {х: f(x) ∊ В}.

Множество А называется областью определения отображения f, а множество f(A) называется множеством значений этого отображения.

Частный случай отображения множества X в множество Y имеет место, если каждый элемент множества Y имеет прообраз. В этом случае отображение f называется сюръективным.

Если для каждого элемента у ∊ У существует не более одного прообраза, т. е. для любых , ∊ X, если , то отображение f называется инъективным.

Если отображение f сюръективно и инъективно, то оно называется биективным (взаимно-однозначным).

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

Если между элементами множеств А и В существует биективное отображение, то множества А и В называются равномощными.

Для конечных множеств А и В понятие равномощности означает, что они имеют одно и то же число элементов. Таким образом, если А — конечное множество, содержащее п элементов, то мощностью множества А называется число п и обозначается |А|, т. е. |А| = п.

Очевидно, что отношение равномощности является отношением эквивалентности, поэтому равномощные множества часто называют эквивалентными.

Функции

В основе всех разделов дискретной математики лежит понятие функции.

Функцией называется бинарное отношение а, если из (х, у) ? f и (х, z)? f следует, что y= z.

Две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции и область ее значений задается так же, как и для бинарных отношений. Если область определения = Х и область значений , то говорят, что функция f задана на множестве X со значениями во множестве Y, при этом f отображает множество X во множество Y. Это отображение обозначается как f: X → Y.

Если f — функция, то вместо (х, у) ∊ f пишут у = f(x) и говорят, что у — значение, соответствующее аргументу х, или у — образ элемента х при отображении f. При этом х называют прообразом элемента у.

Назовем f — n-местной функцией из X в Y, если f: . Тогда записываем y = f( ) и говорим, что у — значение функции при значении аргументов ,..., х_п.

Пусть f: X → Y. Функция f называется инъективной, если для любых , х₂, у из у = f( ) и y=f(x₂) следует, что = х₂.

Функция f называется сюръективной, если для любого элемента у єY существует элемент х X такой, что у = f(х).

Функция f называется биективной, если f одновременно сюръективна и инъективна.

Если существует биективная функция f: X → У, то говорят, что f осуществляет взаимно-однозначное соответствие между множествами X и Y.

Если f: X → Y, a g: Y → Z, то функция F: X → Z, определенная для каждого х∊ X формулой F(х) = g(f(x)), называется композицией (суперпозицией) функции f и g, или сложной функцией.

Пусть задана функция f: X → Y и — множество ее значений. Совокупность всевозможных упорядоченных пар вида (y, (y)), у ∊ образует функцию, которая называется обратной функцией для функции f и обозначается .

Обратная функция ставит в соответствие каждому элементу у ∊ его прообраз некоторое множество элементов. Заметим, что для того, чтобы являлась функцией, достаточно, чтоб функция f была инъективной.

⇐ Предыдущая 1 234 5 6 7 8 Следующая ⇒