Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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

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

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

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

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

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

1.

2.A∪ =U

3.A∩

4.

5.

6.

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

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 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 называется инъективной, если для любых , х2, у из у = f( ) и y=f(x2) следует, что = х2.

Функция 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. III. Финансовый результат страховых операций.
  2. VII. Регламент переговоров при выполнении операций по закреплению железнодорожного подвижного состава на станционных железнодорожных путях
  3. А. Н. Леонтьев, А. В. Запорожец, В. П. Зинченко Формирование перцептивных механизмов и предметных образов на основе внешних ориентировочно-исследовательских операций и действий субъекта
  4. Абстрактные модели защиты информации
  5. АННАЛЫ И НАДПИСИ АССИРИЙСКИХ ЦАРЕЙ. № 44. БИТВА ПРИ КАРКАРЕ
  6. Артикулирование звуков, работа над дикцией
  7. Асимметричная федерация, которая характеризуется разностатусностью субъектов. Асимметричными федерациями являются Индия, Танзания, Россия, Бразилия, Канада.
  8. БАРЬЕРЫ НА ПУТИ К НАДЕЛЕНИЮ ПОЛНОМОЧИЯМИ
  9. Безопасность технических систем: критерии и уровни. Надежность технических систем.
  10. Британские доминионы. Канада
  11. БРОСИТЬСЯ С ЧЕТЫРНАДЦАТОГО ЭТАЖА


Последнее изменение этой страницы: 2016-05-28; Просмотров: 1821; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.029 с.)
Главная | Случайная страница | Обратная связь