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

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Тверь 2002

Методические указания содержат сведения об основных положениях теории множеств и отношений. Методические указания предназначены для студентов специальности ЭВМ, изучающих курс "Дискретная математика", а также для использования при курсовом проектировании элементов вычислительной техники.

Методические указания рассмотрены на заседании кафедры № от и рекомендованы к изданию в электронном варианте.

Составитель АСЕЕВА Т.В

	ã Тверской государственный технический университет, 2002

Введение. 3

Алгебра множеств. 4

Основные определения. 4

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

Аксиомы и тождества алгебры Кантора. 5

Законы для разности множеств. 6

Подмножества и доказательства. 6

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

Элементы комбинаторики. 10

Отношения и функции. 14

Специальные бинарные отношения. 16

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

Отношения порядка. 18

Отображения и функции. 19

Математические модели. 19

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

Алгебра моделей с одной определяющей операцией. 20

Алгебра моделей с двумя операциями. 21

Решетки и булевы алгебры.. 21

Введение

Дискретная математика и математическая логика являются фундаментом, на котором воздвигается все здание специальности «Вычислительные машины, комплексы, системы и сети». Некоторые рекомендации, относящиеся к подготовке специалистов, способных создавать и обслуживать информационные системы, отвечающие ожиданиям пользователей, содержатся в работе Бертрана Мейера[1]. В статье отмечается, что математические дисциплины, изучаемые в процессе подготовки инженера-системотехника, специалиста по ЭВМ, должны включать математический анализ, дискретную математику и основы математической логики. Студенты, научившиеся применять математическое мышление к разработке программного обеспечения, имеют безусловные преимущества по сравнению с теми, кто этими навыками не обладает.

Общая тенденция сводится к необходимости отделять специалистов по программному обеспечению от программистов-любителей. Эти тенденции имеют важные последствия для вузов. Вопрос в том, стоит ли обучать будущих профессионалов фундаментальным методам мышления, которые будут применяться ими в течение всей карьеры и которые помогут добиваться успеха в столь быстро меняющейся области. Успех сопутствует тем, кто способен выйти за рамки инструментария, популярного в какой-то момент, и развиваться в соответствии с динамикой прикладной дисциплины. В любой инженерной дисциплине инструментарий составляет важную часть профессиональных навыков. Но нельзя ограничиваться только ими. Следует изучать фундаментальные концепции, которые не изменились практически с момента своего появления. Дискретная математика и математическая логика содержат формальные основания для понимания всего остального.

Алгебра множеств

Основные определения

Понятие множества является понятием первичным, т.е. не определяемым через другие элементарные понятия. Множество состоит из элементов. Отношение включения элемента х в множество М обозначается Запись означает, что элемент х не принадлежит множеству М. Существует несколько способов задания множеств, применение которых обусловлено контекстом. Ниже перечислены способы основные способы задания множеств:

· Перечислением элементов, которые указываются через запятую и заключаются в фигурные скобки. Например, запись M={x,y,z} означает трехэлементное множество. Очевидно, такой способ применим для не слишком больших множеств.

· Указанием характеристического свойства, например, M={x | xÎ N (N – множество натуральных чисел), 2<x<7}. Очевидно, эта запись указывает множество {3,4,5,6}.

· Графически с помощью диаграмм Эйлера-Венна. Диаграмма Эйлера-Венна представляет собой выпуклую самонепересекающуюся кривую, очерчивающую область, в которой находятся все элементы множества.

· Аналитически с помощью операций на множествах.

· С использованием характеристической функции, которая позволяет представлять множество двоичным словом.

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

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

Два множества называются равными, если они состоят из одних и тех же элементов. При этом порядок перечисления этих элементов не существен. Обозначение равенства множеств: А=В. Обозначение неравенства множеств А ¹ В.

Между множествами существует два вида отношений включения:

Ì - отношение истинного включения; А Ì В Û "х: х Î А Þ х Î В и А ¹ В;

Í - более общий тип включения, АÍ В Û "х: х Î А Þ х Î В или А=В.

Пустое множество является подмножеством любого множества: Очевидно также, что любое множество является своим подмножеством:

На основании определения отношения включения «Í », определение тождества множеств можно записать следующим образом: А = В Û А Í В и В Í А. Это определение используется для доказательства тождества множеств.

Общим свойством всех множеств является кардинальное число или мощность. Мощность множества А обозначается |A|.

Множество называется конечным, если число его элементов равно некоторому натуральному числу, и бесконечным, если такого натурального числа не существует. Мощность конечного множества равна числу его элементов. Мощность бесконечного множества зависит от типа множества. Бесконечные множества бывают счетные и несчетные. Самым простым из счетных множеств является множество натуральных чисел N = {1,2,…,n,…}. Его мощность обозначается специальным символом алеф-нуль a₀. Используя понятия непосредственного предшествования, можно дать такое определение счетного множества:

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

Множество всех подмножеств данного конечного множества называется булеаном этого множества. Булеан множества А обозначается Р(А), его мощность |P(A)| = 2^|^A|. Очевидно, что Æ,АÎР(А), так Æ является подмножеством любого множества. Само несущее множество А также является элементом булеана, т.е. АÎР(А). Æ и А являются несобственными подмножествами множества А. Остальные подмножества, входящие в булеан множества А, называются собственными подмножествами множества А. Элементам булеана конечного множества сопоставляют характеристические векторы длины n,которые определяют все 2ⁿ подмножеств n-элементного множества. Характеристический вектор – это булев вектор (двоичный вектор), длина которого равна длине универсума М, элементы вектора принимают значение 1, если они принадлежат к заданному подмножества универсума, и 0 – в противном случае.

При задании множеств с использованием характеристической функции необходимо задать конечный универсум М и зафиксировать порядок перечисления его элементов. При задании любого подмножества N множества М каждому его элементу характеристическая функция ставит в соответствие 0 или 1 в соответствии с правилом:

Изображением любого подмножества из М с помощью характеристической функции является двоичное слово длины |M|, в котором 1 в данном разряде означает присутствие соответствующего элемента множества М в подмножестве N, а 0 - его отсутствие

Например, если M={2,3,4,5}, то множество N = {3,5} с использованием характеристической функции будет записано как (0101), пустое множество – (0000), само множество М – (1111).

Аксиомы алгебры Кантора

А1. Тождественности:	А È А=А ;	А Ç А=А;
А2. Коммутативности:	А ÈВ=В È А;	А ÇВ= В ÇА;
А3.Ассоциативности:	А È (В ÈС)=(А È В) È С;	А Ç(В ÇС)=(А ÇВ) ÇС;
А4. Дистрибутивности:	А È(В ÇС)=(А ÈВ) Ç (А ÈС);	А Ç(В ÈС)= (А ÇВ) È(А ÇС);
А5. Поглощения:	AÇ(AÈB)=A	AÈ(AÇB)=A

А6.Законы дополнения:	А ÈI=I; А ÈÆ=А; А È`А =I; `I =Æ ;	А Ç 1=А; А Ç Æ= Æ; А Ç `А = Æ; `Æ=1;

А6. Закон двойного отрицания:

Правила де'Моргана:

Элементы комбинаторики

Спросил меня Голос в пустыне дикой:

-Сколько в море растет земляники?

-Столько же, сколько селедок соленых

Растет на березах и елках зеленых.

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

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

Если некоторое свойство, заданное на множестве целых неотрицательных чисел, справедливо для 1, и если, каково бы ни было целое положительное число n, из справедливости этого свойства для n вытекает справедливость его для n+1, то это свойство справедливо для всех положительных целых чисел.

Иначе, если В(х) - одноместный предикат, определенный на множестве целых положительных чисел, то приведенное выше определение можно переписать следующим образом:

Чтобы доказать методом математической индукции некоторое свойство, необходимо

1. Доказать справедливость этого свойства для единицы.

2. Для произвольного n доказать справедливость индукционного вывода:

3. Если это удается сделать, то доказываемое утверждение справедливо.

Такое доказательство называется доказательством по индукции. Его первая часть называется базисом индукции, вторая - индукционным шагом. При проведении индукционного шага посылку импликации, т.е. предложение B(n) называют предположением индукции, а B( n+1) –индукционным заключением.

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

Нередко метод индукции используется не для доказательства свойств целых чисел, а при рассмотрении каких-либо других объектов, занумерованных этими числами. Именно так он будет использоваться в комбинаторных задачах, к рассмотрению которых мы переходим.

Комбинаторными соединениями называются слова конечной длины, составленные из букв конечного алфавита по заранее определенным правилам. Рассмотрим некоторые из них и правила подсчета их числа.

РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ

Размещениями с повторением из n элементов по m называются комбинаторные соединения, представляющие собой слова длины m в алфавите объемом n, различающиеся либо самими буквами, либо их порядком.

Пусть А = {a₁, a₂, ..., a_n) - конечный алфавит, состоящий из n букв, и пусть - число слов в алфавите А, имеющих длину m, буквы в которых могут повторяться. Например, возможно слово а₁⁽^m), т.е. содержащее одну единственную букву. Возможны любые произвольные сочетания, включающие вхождения некоторых букв произвольное число раз и в произвольном порядке.

Теорема Число размещений с повторениями длины m в алфавите объемом n равно = n^m.

Доказательство: Можно дать еще одно определение этому комбинаторному соединению: это все элементы декартовой n-й степени алфавита: , . Докажем теорему методом математической индукции по m.

1. Базис: При m =1 число Q(1) различных слов, которые могут быть образованы в алфавите А, равно его мощности, т.е. n. Следовательно, Q(1)= = n¹=n. Базис индукции доказан.

2. Индукционное предположение: пусть для некоторого m доказано, что Q(m)= = n^m. Определим число слов в длины m+1 при этом предположении. Все слова длины m+1 можно получить, приписывая справа к каждому слову длины m какую-нибудь букву алфавита. Очевидно, каждое слово длины m можно дополнить n способами, т.е. общее число слов длины m+1 окажется в n раз больше числа слов длины m. Следовательно, Q(m+1)=Q(m)*n= n*n^m=n^m⁺¹= .

Доказательство окончено.

РАЗМЕЩЕНИЯ БЕЗ ПОВТОРЕНИЙ

Это комбинаторные соединения, представляющие собой слова длины m в алфавите объемом n, различающиеся составом букв или их порядком, в каждое из которых любая буква может войти не более одного раза.

Теорема: Число размещений без повторения длины m в алфавите объемом n равно .

Доказательство: Докажем теорему методом математической индукции по m.

1. Базис: При m=1 число Q(1) различных бесповторных слов в алфавите А равно его мощности, т.е. n. Подставляя m=1 в условие теоремы, получим n!/(n-1)!=n. Таким образом, базис индукции справедлив.

2. Индукционное предположение: пусть при некотором m число размещений без повторений Q(m) = . Определим число слов длины m+1, являющихся размещениями без повторений. Все такие слова можно получить, приписывая к каждому слову длины m одну из неиспользованных в слове букв алфавита А. Следовательно, каждое слово длины m порождает n-m слов длины m+1. Следовательно, число Q(m+1) слов длины m+1 равно

Q(m)*(n-m)= (n-m)= .

Теорема доказана. Разумеется, это доказательство имеет смысл только в случае, когда n > m.

ПЕРЕСТАНОВКИ

Это слова длины n в алфавите объемом n, в которых одна и та же буква не может повторяться. Т.е. это размещения без повторений из n по n. Число перестановок обозначается Р_n.

Теорема: P_n = n!

Доказательство автоматически следует из выражения для числа размещений без повторений. По определению 0!=1.

СОЧЕТАНИЯ ИЗ n ЭЛЕМЕНТОВ ПО m Это слова длины m в алфавите объемом n, различающиеся составом букв, но не их порядком, причем буквы в словах могут появляться не более одного раза. Число таких соединений обозначается как

Теорема:

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

Q(m)= .

Следствия

1. - следует из определения.

2. - так как все пустые слова одинаковы.

ª Возможно следующее доказательство этого свойства. Известно, что

где это биномиальные коэффициенты, определяющие число слагаемых вида xⁱyⁿ ^- ⁱ в сумме. В частном случае, когда х=1 и у=1 получаем непосредственно

требуемое выражение §

ª Доказывается аналогично доказательству свойства 3 в предположении, что х=1, у=-1. §

Задача: Доказать что мощность булеана конечного множества А равна 2^|^A|.

ª Мощность булеана конечного n- элементного множества есть число всех его подмножеств. Ранее мы без доказательства ввели утверждение, что |P(A)| = 2^|^A|. Так как есть не что иное, как число m-элементных подмножеств n-элементного множества, то указанная сумма действительно определяет число всех возможных подмножеств конечного множества.

Треугольник Паскаля

Рассмотрим рекуррентную по n процедуру определения биномиальных коэффициентов, т.е. определение если известно Пусть число r- элементных подмножеств (n+1)-элементного множества равно и известно, как определить И пусть |А | = n и мощность множества А È {a₀} равна n + 1.Тогда r- элементные подмножества множества А È {a₀} будут состоять из подмножеств двух типов: тех, которые не содержат элемент а₀, число их будет равно , и тех, которые содержат элемент а₀. Последние можно получить, взяв все (r-1) - элементные подмножества множества А, и добавив к каждому из них а₀. Тогда число r - элементных подмножеств (n + 1)-элементного множества определится, как Это рекуррентное соотношение используется для построения таблицы биномиальных коэффициентов, в которой коэффициенты расположены рядами друг над другом. Строки следуют в порядке возрастания n, а позиция коэффициента в ряду указывает число m подмножеств ранга 0,1,2,…,n, причем 0 £ m £ n, 0 £ n £ N.

Таблица биномиальных коэффициентов приводится в математических справочниках и имеет вид, представленный на Рис. 1.

Рисунок 1 Треугольник Паскаля

Отношения и функции

Отношение является фундаментальным понятием дискретной математики, которое используют для обозначения связи между объектами или понятиями. Например, отношение включения элемента во множество, отношение включения подмножества во множество, отношение параллельности и перпендикулярности прямых, отношение равенства чисел и множеств. Общим для всех отношений является то, что они ставят в соответствие друг другу объекты из разных множеств или из одного и того же множества. В общем случае отношение можно определить как некоторое утверждение, относительно которого можно сказать, что оно является истинным или ложным. В дискретной математике такое утверждение называется предикатом. Например, предикат x>y может быть истинным или ложным в зависимости от того, какие значения примут входящие в него переменные x и y. Понятие предиката непосредственно вытекает из понятия отношения. Если предикат устанавливает какое- либо соответствие между двумя объектами, то эту пару объектов можно рассматривать как элемент декартова произведения двух множеств, элементами которых и являются эти объекты. В силу последнего обстоятельства объекты, входящие в пары, могут принимать различные сочетания значений. При некоторых из них предикат будет истинным, при других ложным. Подмножество декартова произведения двух множеств, для каждого из элементов которого данный предикат будет истинным, называется двуместным (бинарным) отношением между элементами двух множеств.

В общем случае n - местным отношением между элементами множеств А₁, A₂, ..., A_n называется любое подмножество декартова произведения этих множеств. Соответственно бинарное отношение - это любое подмножество декартова произведения двух множеств (возможно, одного и того же множества). При n =1 отношение называется одноместным или унарным и обозначает просто свойство на множестве. Например, r={x | х положительное целое число} задает множество положительных целых чисел.

Для обозначения отношений принято использовать строчные буквы латинского или греческого алфавита. Будем обозначать n - местное отношение между элементами множеств А₁ , А₂, ..., А _n как r⁽ⁿ⁾Í А₁´А₂´...´А_n. Верхний индекс определяет местность отношения. Таким образом, n-местное отношение – это множество упорядоченных n-ок, элементы которых принадлежат соответствующим множествам, участвующим в декартовом произведении и порождающим универсум для этого отношения. Поэтому, например, если требуется определить все бинарные отношения на множестве {0,1}, то надо вначале найти декартов квадрат этого множества, который и будет универсумом для всех возможных отношений. Мощность множества {0,1}² равна 4. Следовательно, искомая мощность множества всех возможных отношений равна мощности булеана множества {00, 01, 10, 11}, т.е. 16.

Наиболее часто встречаются бинарные отношения вида r Í А´В или r Í А². В последнем случае множество А называется несущим множеством, на котором задано отношение r. В приведенном выше примере несущим множеством для всех бинарных отношений на множестве {0,1} является множество {00, 01, 10, 11}. С каждым бинарным отношением связывают два множества: область определения dom r и область значений rng r, которые определяются как проекции отношения r на первую и вторую координаты соответственно, т.е. dom r ={x| $y: (x,y) Î r},

rng r={x | $у: )(у,х) Î r}. Очевидно, каждое бинарное отношение задано на множестве (dom r È rng r).

Для обозначения бинарных отношений r Í А² часто используют следующие записи:

· хrу , читается "х находится в отношении r с у";

· (х,у) Î r, читается "элемент (х,у) принадлежит отношению r";

· у Î r(х).

Множество элементов отношения r называется графиком отношения r.

Отношение является множеством, следовательно, к нему применимы любые операции, определенные для множеств. Кроме того, для отношений определены также следующие операции:

· обратное отношение r^-1 , которое определяется как r^-1={(x,y) | (y,x) Îr}. Например, для отношения хrу Û х ³ у, заданного на множестве А={1,2,3}, r = {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)}, обратное отношение r^-1={(x,y)|y³x}; график обратного отношения получается простой перестановкой первого и второго элементов в каждой паре, участвующей в r: r^-1 = {(1,1), (1,2), (2,2), (1,3), (2,3), (3,3)};

· дополнение отношения ` r, которое определяется как дополнение r до универсального отношения: `r = {(x,y) | (x,y) Î А²\ r};

· композиция отношений · , таких что и . Композиция отношений – это бинарное отношение, которое определяется следующим образом

На рис.2 приведен композиции двух бинарных отношений.

Рисунок 2 Композиция бинарных отношений

Отношение не обладает свойством коммутативности. Легко показать, что композиция отношений ассоциативна, а также, что

Для визуализации отношений можно использовать различные способы:

1. Задание отношения перечислением элементов.

2. Графиком отношения в декартовой системе координат.

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

4. Графом отношения.

5. Фактор - множеством, в котором перечисляются окрестности каждого из элементов несущего множества.

Рассмотрим различные способы на примере отношения хrу Û x > y, x,y Î {1, 2, 3, 4, 5}.

1. Перечислением элементов: r = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4)}. Это множество называется также графиком отношения.

2. Графиком отношения, т.е. указанием всех точек плоскости, в которых указанное отношение истинно. Для изображения графика отношения введем декартовы координаты, примем, что ось абсцисс - это ось х, а ось ординат - это ось у. Точки, находящиеся в пересечениях всех горизонталей и вертикалей, проведенных через точки координатных осей, изображающие элементы несущего множества, дадут "универсум", т.е. множество, мощность которого равна в данном случае 25. В этом множестве выделим точки, принадлежащие отношению, Рис.2.

Рисунок 3. Изображение отношения с помощью графика

3. Изображение отношения с использованием координатных осей и стрелок очевидно из

Рис. 3, a, b.

Рисунок 4. Изображение отношения стрелками.

4. Изображение отношения с помощью графа. Множество элементов несущего множества используется в качестве имен вершин графа отношения. Ребрами ориентированного графа являются элементы отношения, Рис. 4.

Рисунок 5. Изображение отношения с помощью графа.

5. При изображении отношения с помощью фактор -множества каждому элементу несущего множества сопоставляется его окрестность, определенная следующим образом:

О_r(v_i)={v_j | (v_i,v_j) Î r, v_i, v_j ÎA}, где А - несущее множество. Фактор - множество записывается в виде заключенной в фигурные скобки последовательности элементов несущего множества, под каждым из которых указывается его окрестность, т.е. множество вершин, смежных с данной вершиной. В рассматриваемом случае

Для любого множества А определим тождественное отношение I_A, которое называется также диагональю А, и универсальное отношение 1 следующим образом:

I_A = {(xx)| x ÎА}. 1 = А². Так как Æ Í А², то Æ является отношением на А и называется пустым отношением.

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

Бинарное отношение называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Эквивалентность обозначается символом ~, например, х ~ y. Граф отношения эквивалентности есть полный граф, заданный на множестве А, т.е. множество ребер графа отношения эквивалентности либо равно А², либо несвязный граф, каждая компонента связности которого является полным подграфом графа А² на некотором подмножестве вершин графа, образующем класс эквивалентности для данного отношения. Вообще, классом эквивалентности для отношения ~ на множестве А по элементу а называется множество, определенное следующим образом: [x]_~ или

X({a})={x | x~а, xÎA }.

Разумеется, элемент а, для которого класс эквивалентности определен таким образом, также входит в этот класс в силу рефлексивности отношения эквивалентности.

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

Таблица 2 Свойства отношения эквивалентности

Понятие	Свойство или определение	Пояснение
~ - отношение эквивалентности на А	· ~Í А´А · ~ рефлексивно в А · ~ транзитивно в А · ~ симметрично в А	i_AÍ ~ dom ~ = rng ~ = A ~ · ~ = ~ ~ = ~^-1.
A_a- класс эквивалентности отношения ~ по элементу а	[a]_~ = {x \| (a,x) Î ~ }	Множество всех элементов, таких, что x ~ a. Каждый класс эквивалентности определен заданием одного элемента.
Разбиение множества А	Z={Z₁,Z₂, …, Z_N}, Æ Ï Z,	Разложение множества А на непересекающиеся непустые подмножества, так что каждый элемент из А принадлежит одному и только одному из этих подмножеств.

Можно доказать, что отношение эквивалентности “~” на А образует разбиение А/ ~ множества А, причем элементами разбиения являются классы эквивалентности. Разбиение называется максимальным, если в каждый класс эквивалентности входит по одному элементу. Примером такого отношения является отношение х ~ у Û х=у, х,у Î N. Разбиение называется минимальным, если оно образует единственный класс эквивалентности, в который входят все элементы А.

Множество классов эквивалентности в множестве А по эквивалентности “~” называется фактор-множеством А по “~”, обозначается A/~.

Примеры о тношений эквивалентности.

1. Отношение конгруентности треугольников.

2. Отношение тождества на множестве алгебраических выражений.

3. Отношение параллельности на множестве прямых.

4. Отношение учиться в одной группе на множестве студентов.

5. Отношение получить одну и ту же оценку по математике на экзамене.

6. Сравнимости чисел по модулю m (это отношение определяет множества чисел, дающих одинаковый остаток при делении на m). Например, отношение иметь одинаковый остаток при делении на 7 на множестве целых чисел Z:

7. Отношения равенства чисел (образует максимальное разбиение),

8. Конгруэнтности треугольников (классы эквивалентности включают все конгруэнтные треугольники),

9. Равенства множеств,

10. Равномощности множеств,.

Теорема. Если “~” – отношение эквивалентности, заданное на произвольном непустом множестве А, то существует разбиение, равное фактор множеству множества А по отношению ~, A/~ = {[x]_~ | "xÎ A$yÎA: x~y Û x,yÎ[x]_~} такое, что каковы бы ни были x,yÎ A, x ~ y тогда и только тогда, когда х и у принадлежат к одному и тому же классу разбиения.

§ Пусть ~ - эквивалентность на А и A/~= {[x]_~ | "x: xÎ A}- фактор-множество А по отношению ~. Докажем существование разбиения R_~, равного фактор множеству A/~.

· Пусть aÎA – произвольный элемент А. Обозначим A_a= [a]_~ = {x | x Î A, x ~ a} – класс эквивалентности по элементу а. Тогда, аÎА_а, и, следовательно, Так как элемент а выбирается произвольно, и каждый класс эквивалентности содержит только элементы множества А, то Из существования двух включений следует, что . Следовательно, объединение классов эквивалентности равно А.

· Докажем теперь, что попарные пересечения классов эквивалентности пусты. Пусть a,b Î A, aÎ A_a, b Î A_b, A_a и A_b –два класса эквивалентности. Пусть А_a Ç A_b ¹Æ. Тогда существует хотя бы один элемент сÎА такой, что с Î А_a и с Î А_b, т.е. с ~ a и c ~ b. Пусть z – произвольный элемент множества А_а. Тогда z ~ a и а ~ с. По свойству транзитивности отношения эквивалентности получаем z ~ c. Но с ~ b, следовательно, по свойству транзитивности z ~ b. Следовательно, z Î A_b. Следовательно, A_a Í A_b. Обратное включение доказывается аналогично. Следовательно, пересечение A_a и A_b не пусто тогда и только тогда, когда это одно и то же множество.

Таким образом, доказано, что множество классов эквивалентности образуют разбиение множества А. ¨

Отношения порядка

Бинарное отношение на А называется предпорядком на А, если оно рефлексивно и транзитивно, но не антисимметрично (например, отношение «х делитель у» на множестве целых чисел).

Частичным порядком на А называется бинарное отношение рефлексивное, транзитивное и антисимметричное. Частичный порядок часто обозначается символом “£”. Порядок £^-1 называется двойственным к £ и обозначается символом “³”. Будем писать x<y, если x<y и x¹y. Частичный порядок £ на множестве А называется линейным, если два любые элемента из А сравнимы между собой по £, т.е. x£y или y£x для любых х,у ÎА. Множество А с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.

Рисунок 6 Диаграмма Хассе для отношений не полного и полного частичного порядка и

Часто частично упорядоченное множество (ЧУМ) изображают в виде графа H=(V,£), из которого удалены все петли и транзитивно замыкающие дуги. Такой граф называется диаграммой Хассе. Диаграмма Хассе известна с конца XIX века. В течение многих лет ее применяли в генеалогии для задания родства.

Понятие непосредственного старшего легко задается в ЧУМ следующим определением: x покрывает у тогда и только тогда, когда y<x и не найдется такого элемента z, что y<z<x.

Таблица 3 Свойства отношений порядка

Понятие	Свойство или определение	Пояснения
Рефлексивный ЧП в А (£) (Нестрогий порядок)	· £ Í A´A, · £ рефлексивно в А, · £ транзитивно в А, · £ антисимметрично в А.	i_AÍ £, £·£=£, x£y и y£x Û x=y.
Иррефлексивный ЧП в А (<) (Строгий порядок)	· < Í A², · < иррефлексивный, транзитивный, асимметричный.	На множестве N отношение < не является ЧП, так как пары (n,n+1) не принадлежат отношению <. i_A Ç < = Æ, <·<Ì<, <·<^-1=Æ
£- ЧП в А, В Í А, B минимальный элемент в В: b = min B d – максимальный элемент в В: d = max B	· "x: xÎB Þ b £ x, bÎB, · "x:xÎB Þ x £ d, bÎB.	Элементы b и d сравнимы со всеми элементами из В.
£ – ЧП в А, ВÍА, а,bÎА. {а} – нижняя грань В, {b} – верхняя грань В.	· "x: xÎB Þ a £ x, · "x: xÎB Þ x £ b.	В отличие от минимального и максимального элемента В а и b не обязательно принадлежат В.
£ – ЧП в А, ВÍА; u, oÎA. u=inf B (точная нижняя граница В), o=sup B (точная верхняя граница В).	· u – максимальный элемент нижней грани, · о – минимальный элемент верхней грани.	Точная верхняя и нижняя границы не всегда существуют.
£ – ЧП в А, ВÍА; В - цепь в А	"x,y: x,yÎBÞx£y или y£x.	В линейно упорядочено отношением В²Ç £.

Подмножество В множества А, частично упорядоченного отношением £, называется цепью в А, если оно линейно упорядочено отношением £ Ç В².

Если А – ЧУМ, sup A, inf AÎB, то sup A называется единицей ЧУМ А (обозначается 1), а inf A – нулем ЧУМ А(обозначается 0).

Отношением частичного порядка является отношение включения «Í » на булеане конечного множества; примером линейного порядка является отношение £ на множестве чисел.

Линейный порядок £ на множестве А назовем полным, если каждое подмножество множества А имеет наименьший элемент. В этом случае множество А называется вполне упорядоченным.

Пусть А и В – частично упорядоченные множества и f – функция из А в В. f называется монотонным отображением, если их x₁£x₂ следует, что f(x₁) £ f(x₂), для любых x₁, x₂ Î A.

Если f и f^-1 – монотонные отображения, то f называется изоморфизмом частично упорядоченных множеств А и В, а множества А и В называются изоморфными.

Операции над отношениями

Основным компонентом реляционной модели базы данных является реляционная алгебра, которая состоит из восьми операторов, составляющих две группы по четыре оператора:

1) Традиционные операции над множествами: объединение (UNION), пересечение (INTERSECT), разность (MINUS) и декартово произведение (TIMES). Все операции модифицированы, с учетом того, что их операндами являются отношения, а не произвольные множества.

2) Специальные реляционные операции: ограничение (WHERE) , проекция (PROJECT), соединение (JOIN) и деление (DIVIDE BY).

3) Результат выполнения любой операции реляционной алгебры над отношениями также является отношением. Эта особенность принято называть свойством реляционной замкнутости.

Булева алгебра

Частично упорядоченное множество А с заданными на нем операциями типа умножения Ç (И) и типа сложения È (ИЛИ) называется решеткой, если каждая пара сравнимых элементов имеет наибольший и наименьший элемент, причем inf(a,b)=aÇb, sup(a, b)=aÈb, и выполняются аксиомы решетки: коммутативности, ассоциативности и поглощения – для операций типа сложения È и типа умножения Ç.

Если в решетке выполняются аксиомы дистрибутивности, то решетка называется дистрибутивной.

Если для введенного на решетке отношения частичного порядка £ существуют наибольший и наименьший элементы, они называются единичным и нулевым элементами решетки. Сама решетка при этом называется решеткой с 0 и 1. Если для каждого элемента а решетки существует обратный элемент а^-1, такой что аÇa^-1=0, aÈ`а =1, то а^-1(`а ) называется дополнением а, а решетка называется решеткой с дополнениями.

Если в решетке выполняется аксиома дистрибутивности, она называется булевой алгеброй.

Примером булевой алгебры является алгебра Кантора.

Отображения и функции

Отображение (синоним – функция). Уточним понятия отображения как тройки объектов: двух множеств и правила, сопоставляющего элементам первого множества элементы второго множества. Отношение f называется функцией из А в В (из А на В), если dom f = A, rng fÍ B (rng f = B), и для всех х, у₁, у₂ из (х,у₁)Îf и (x,y₂)Îf следует у₁ = у_2. Т.е. каждый элемент первого множества (А) участвует в образовании пар ( x, y), где у ÎВ Функция f из А в В обозначается f:A®B. Если f – функция, пишем y = f(x) вместо (x,y) Î f и называем y значением аргумента функции f при значении аргумента x.

Если при этом rngf=B, то говорят, что а – отображение множества А на множество В. Это обозначается

Множество всех функций из А в В обозначается Таким образом, Очевидно, что

Для любого множества А определяем i_A: A®A следующим образом: i_A(x) = x. Отображение i_A называется диагональю множества А².

Функция f называется 1-1 функцией, если для любых x₁, x₂, y из того, что y = f(x₁) и y = f(x₂) , следует x₁ = x₂. Иначе

Функция f:A®B осуществляет взаимно однозначное соответствие между А и В, если dom f = A, rng f = B и f есть 1-1 – функция.

Взаимно однозначное соответствие f:A®A называется подстановкой множества А.

n-местным отношением на А назовем любое подмножество множества Aⁿ. Функцию f: Aⁿ®B назовем n-местной функцией из А в В и будем писать f(x₁, … , x_n) = y и называть у значением функции f при значении аргументов x₁, …, x_n. n-местной операцией на А называется отображение f: Aⁿ ® A. Ей соответствует n+1 – местное отношение на А.

В общем случае отображение f:M®N может быть представлено тройкой (M, N, f).

Пусть f: M ® N, и B Í N.

Образом множества А при отображении f называют множество определяемое следующим образом:

Прообразом множества В при отображении f называют множество определяемое как

Свойства образов и прообразов

Пусть f: M ® N, Тогда имеют место соотношения:

Докажем первое свойство

ªПусть

Û или или

Математические модели

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

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

Решетки и булевы алгебры

Множества, на которых кроме операций заданы отношения, называются алгебраическими системами. Алгебра – частный случай алгебраической системы, в которой множество отношений пусто. Другим частным случаем алгебраических систем являются модели, т.е. множества, на которых заданы только отношения. Для исследования двоичных систем особое значение имеют решетки (структуры).

Частично упорядоченное множество А с заданными на нем операциями типа умножения (Ç, И) и типа сложения (È, ИЛИ) называется решеткой, если каждая пара сравнимых элементов имеет наибольший и наименьший элемент, причем inf(a,b)=aÇb, sup(a, b)=aÈb, и выполняются аксиомы решетки: коммутативности, ассоциативности и поглощения – для операций типа сложения È и типа умножения Ç.

Если в решетке выполняются аксиомы дистрибутивности, то решетка называется дистрибутивной.

Если для введенного на решетке отношения частичного порядка £ существуют наибольший и наименьший элементы, они называются единичным и нулевым элементами решетки. Сама решетка при этом называется решеткой с 0 и 1. Если для каждого элемента а решетки существует обратный элемент а^-1, такой что а Ç a^-1=0, a È `а =1, то а^-1(`а ) называется дополнением к а, а решетка называется решеткой с дополнениями.

Если в решетке выполняется аксиома дистрибутивности, она называется булевой алгеброй.

Примером булевой алгебры является алгебра Кантора.

[1] Бертран Мейер. Программная инженерия как предмет обучения. Открытые системы. Июль-август 2001, 80-86.

Тверь 2002

Составитель АСЕЕВА Т.В

	ã Тверской государственный технический университет, 2002

Введение. 3

Алгебра множеств. 4

Основные определения. 4

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

Аксиомы и тождества алгебры Кантора. 5

Законы для разности множеств. 6

Подмножества и доказательства. 6

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

Элементы комбинаторики. 10

Отношения и функции. 14

Специальные бинарные отношения. 16

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

Отношения порядка. 18

Отображения и функции. 19

Математические модели. 19

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

Алгебра моделей с одной определяющей операцией. 20

Алгебра моделей с двумя операциями. 21

Решетки и булевы алгебры.. 21

Введение

Алгебра множеств

Основные определения

· Аналитически с помощью операций на множествах.

· С использованием характеристической функции, которая позволяет представлять множество двоичным словом.

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

Между множествами существует два вида отношений включения:

Ì - отношение истинного включения; А Ì В Û "х: х Î А Þ х Î В и А ¹ В;

Í - более общий тип включения, АÍ В Û "х: х Î А Þ х Î В или А=В.

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

Объединением множеств А и В называется множество АÈВ = {x | "x: xÎ A или xÎ B}.

Пересечением множеств А и В называется множество А Ç В = {x | "x: xÎA и x Î B}.

Разностью множеств А и В называется множество A\B = {x | "x: x Î A и x Ï B}.

Разность универсума I и множества А называется дополнением А и обозначается `А или .

Симметрической разностью множеств А и В называется множество

Универсум с заданными на нем подмножествами, операциями и отношениями образует алгебру Кантора (алгебру множеств).

Дата: 2019-03-05, просмотров: 255.

12 3 4 5 6 7 Следующая ⇒