Главная > Отношения > Свойства отношений на множестве. Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика Бинарные отношения для чайников


Свойства отношений на множестве. Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика Бинарные отношения для чайников




Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

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

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

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

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

Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.

В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами ) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.


Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).

Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.

Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .

4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями

.

Кстати, матричное представление является представлением отношения в компьютере.

Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:


Матричное представление этого бинарного отношения имеет вид:

. ,

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.


Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }

Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:

r-1={(b , a ) | (a , b )Îr}.

Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:

t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.

Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:

r={(1, x ), (1, y ), (3, x )};

s={(x ,), (x , !), (y , d), (y , à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},

поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;

из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;

из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;

из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

2) ;

3) - ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

3.2. Свойства бинарных отношений .

Рассмотрим специальные свойства бинарных отношений на множестве A .

Свойства бинарных отношений.

1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .

2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .

3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.

4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .

5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.

Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

(a , b )Îr

(b , a )

(b , a )Îr?

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

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

(a , b )Îr

(b , c )Îr

(a , c )

(a , c )Îr?

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

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности , если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности a rb часто обозначается: a ~ b .

Пример 3. 8 . Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .

Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;

это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

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

Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.

Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

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

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.

Понятие отношения наряду с понятием множества «пронизывает» всю математику. Интуитивно отношение понимается как связь объектов. Наша задача заключается в том, чтобы, используя сформулированные выше конструкции теории множеств, определить на математическом языке, что же понимается в математике под термином «отношение».

Бинарные отношения на множестве

Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л:,у) в качестве элемента некоторого множества; если д; не связан с у , значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.

Бинарным отношением на множестве А называется произвольное множество пар элементов из А.

Другими словами, бинарное отношение на множестве А - ото подмножество прямого произведения АхА=А 2 . В частности, само множество А 2 всех пар является бинарным отношением.

По аналогии с бинарным (или двуместным) отношением можно рассматривать п-местное отношение на множестве как подмножество прямого произведения А". Мы в основном будем рассматривать бинарные отношения, но для краткости речи говорить просто: «отношение на множестве А».

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

Если (л",у)е р, то говорят, что л" находится в отношении р с у, и пишут

Если (ду)?Р> то имеем отрицание соответствующего утверждения. В этом случае наряду с записью ~|(хру) (или хру) пишут д-ру, перечеркивая знак отношения.

Пример 8.1.1. Рассмотрим множество А = {1,2,3,4,5}. Множество пар

определяет на А отношение «меньше», обозначаемое знаком <.>

11а этом же множестве можно рассмотреть другое множество пар

оно определяет отношение равенства.

Пример 8.1.2. Рассмотрим множество {N, Z, Q, I, R} основных числовых множеств и множество пар

Имеем отношение, определенное нами в пункте 2.2 как отношение строгого включения множеств. Заметим, что, например, пара (Q. I) нс лежит в указанном множестве, так как Qczl, более того, эти множества не пересекаются.

Пример 8.1.3. Дано множество слов Л={ток, кот, шок, кол, лак}. Рассмотрим такое отношение:

р = {(ток, шок), (шок, ток), (шок, кол), (кол, шок),

(кол, лак), (лак, кол), (кот, кол), (кол, кот)}.

Это отношение можно выразить таким образом: слова множества А находятся в отношении р тогда и только тогда, когда они имеют ровно две одинаковые буквы.

Заметим, что любое множество пар является отношением, неважно, имеется ли для этого отношения хорошее словесное описание.

Так как отношение является множеством, то его можно задать характеристическим свойством, то сеть предикатом Р(ху): р = {(.*,>>) еЛ 2 Р(ху)}. Также используется запись:

Читают: «г находится в отношении с у тогда и только тогда, когда истинно Р(ху)».

Пример 8.1.4. Определим на множестве/! = {1,2,3,4,5} отношение:

Здесь Р(ху) = (л+2=у). Зададим это отношение перечислением пар:

Пример 8.1.5. Зададим на множестве Z (или на множестве N) отношение с помощью предложения: «Существует целое число /?, такое, что х=п у». Символически можно записать:

Имеем уже определенное ранее отношение делимости, обозначаемое знаком:. Этому отношению принадлежат такие пары, как (6,2), (6,3), (4,4), (111, -37) и другие. В отличие от предыдущих примеров это множество пар бесконечно, и перечислить все пары не удастся.

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

Отношение р на множестве А называется рефлексивным , если любой элемент х из А находится в отношении р сам с собой, то есть для всех д; из А выполняется лрт:

Пример 8.1.6. Рассмотрим отношение делимости на множестве Z. Возьмем произвольное целое число х. Так как х=х 9 то х‘:х. Значит, любое целое число делится на само себя: V.veZ (л:л). Поэтому отношение делимости рефлексивно.

Так как любое множество является подмножеством самого себя, то отношение включения множеств рефлексивно (на любой совокупности множеств).

Отношение р на множестве А называется аитирефлексивным , если ни один элемент множества А не находится в отношении р с самим собой:

Пример 8.1.7. R антирефлексивно, так как никакое число не меньше самого себя.

Построим отрицание к предложению «Отношение р рефлексивно»:

Таким образом, отношение р не является рефлексивным тогда и только тогда, когда существует элемент хеА, который не находится в отношении р сам с собой. Отношение, не являющееся рефлексивным, не обязано быть аитирефлексивным.

Пример 8.1.8. Рассмотрим отношение на множестве R, заданное предложением «Число х противоположно числу у». Число х называется противоположным числу у, если сумма х+у равна 0.

Это отношение не рефлексивно. Контрпример: х=1. Так как 1 + 1*0, то число 1 не противоположно 1.

Это отношение нс антирефлексивно. Контрпример: ,v=0. Так как 0+0=0, то число 0 противоположно 0.

Отношение р на множестве А называется симметричным , если из того, что х находится в отношении р с у, следует, что у находится в отношении р с

Пример 8.1.9. Из тождества х+у=у+.х вытекает утверждение: для любых действительных чисел х и у если х противоположно v, то у противоположно х. Значит, данное отношение симметрично. Часто говорят просто: «Числа х и у противоположны».

Отношение «Число х меньше числа у» на множестве R не является симметричным: 3 меньше 4, но 4 не меньше 3.

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

урх:

Пример 8.1.10. Отношение «меньше» на множестве R антисимметрично.

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

Используя таблицу истинности, можно доказать, что формула 1Р л М -равносильна формуле М л К -> Р, которая, в свою очередь, по правилу контрапозиции равносильна 1Р ->~|(Л/ л К). На основании этого можно сказать, что отношение р является антисимметричным тогда и только тогда, когда выполняется одно из равносильных условий:

А) Из того, что хру и урх, следует х=у:

Б) Никакие различные элементы не могут одновременно находиться в отношении р друг с другом.

Пример 8.1.11. Рассмотрим отношение включения на произвольном семействе множеств. Так как ЛсУл Y^X=>X=Y, то включение е есть антисимметричное отношение.

Пример 8.1.12. Отношение делимости на множестве Z не является ни симметричным, ни антисимметричным. Так как 4:2, но 2?4, то отношение не симметрично. Так как 2:(-2) и (-2):2, но (-2)^2, то отношение не является антисимметричным.

Однако на множестве N натуральных чисел имеем антисимметричное отношение: Vjt^eN (х:у лу:х ->х=у). Проверьте это утверждение, пользуясь определением делимости.

Отношение р на множестве А называется транзитивным , если из того, что х находится в отношении р с у, а у находится в отношении р с z, следует, что.V находится в отношении р с z:

Пример 8.1.13. Отношение делимости транзитивно (и на множестве Z и на множестве N): х:у л у: z => x:z. Покажем это. Пусть х:у и y:z. Тогда х=пу и y=kz для некоторых целых чисел п и к. Тогда х = n(kz) = (nk)z = mz, где т есть целое число. Поэтому xz.

Отношение включения множеств также транзитивно: XcY л YcZ => XezZ. Докажите.

Отношение «Числа х и у противоположны» не является транзитивным. Контрпример: х=2,у=-2, 2=2. Тогда числа 2 и (-2) противоположны, а также (-2) и 2 противоположны. Но числа х=2 и z=2 нс являются противоположными.

Пример 8.1.14. Рассмотрим некоторые примеры отношений из предыдущего пункта.

Отношение из примера 8.1.3 антирефлексивно и симметрично. Отношение из примера 8.1.4 антирефлексивно и антисимметрично. Ни одно из этих отношений нс транзитивно. Докажите это, рассмотрев соответствующие контрпримеры.

Некоторым отношениям, обладающим одновременно рядом свойств, даны общие называния. Из рассмотренных выше примеров одновременно свойствами рефлексивности, антисиммегричности и транзитивности обладают отношение включения множеств с и отношение делимости на множестве N. Также этими тремя свойствами обладает отношение «х меньше либо равно у », определенное на множестве R (или на любом его подмножестве):

Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка.

Множество А , на котором задано отношение порядка р, называется упорядоченным множеством . Пишут (А, р).

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

Интуитивно слова «упорядоченное множество» часто понимаются в более узком смысле. Рассмотрим упорядоченную л-ку, составленную из попарно различных элементов. Например, пятерка букв (III,К,О,Л,А) определяет слово ШКОЛА. В этом случае слова «элементы записаны в определенном порядке» понимаются в том смысле, что мы занумеровали их натуральными числами 1, 2, 3, 4, 5 и расположили в порядке возрастания номеров. Обобщим этот пример.

Пусть дано «-элементное множество А. Занумеровав каким-то образом ею элементы а, а 2 >а„, мы действительно получим упорядоченное множество, определив отношение порядка следующим образом:

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

Пример 8.1.15. Дано множество /4={а,б.в,г}. Упорядоченная четверка его различных элементов (б,в,а,г) задаст такое отношение порядка:

{(б,б), (б,в), (б,а), (б,г), (в,в), (в,а), (в,г), (а,а), (а,г), (г,г)}.

Заметим, что порядок не обязан обладать так называемым свойством линейности.

Пример 8.1.16. Рассмотрим на множестве А = {2,4,6,8} отношение делимости:. Задайте это отношение множеством пар. Так как в А лежат только натуральные числа, то: отношение порядка. Имеем упорядоченное множество А, :).

Такой порядок нельзя представить в виде упорядоченной четверки следующих друг за другом элементов. Можно привести графическую иллюстрацию отношения с помощью точек и стрелок: из точки х в точку у ведет стрелка тогда и только тогда, когда х:у.

Рассмотрим числа 6 и 4. Ни одно из них нс делится на другое. Говорят, что это несравнимые элементы.

Пусть на множестве А задано отношение порядка р. Элементы * и у называются сравнимыми , если выполняется хотя бы одно из двух соотношений хру или урх.

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

Пример 8.1.17. Отношение R является линейным порядком, так как Vx^yeR (х Поэтому (R,

упорядоченное множество.

Отношение делимости натуральных чисел в общем случае не является линейным порядком. Контрпример дан в примере 8.1.16.»

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

Декартовым произведением двух множеств X и Y называется множество всех упорядоченных пар (x , y ) таких, что
, а
.

Пример 1 . Пусть .

Тогда , .

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

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

Будем говорить, что задано соответствие q между множествами X и Y , если задана упорядоченная тройка
, где
.Множество X называется областью отправления, а Y – областью прибытия соответствия q (обозначают
). Каждый элементy в паре
называется образом элементаx (x – прообразом элемента y ) при данном соответствии q .

Соответствие
называетсяотображением множества X во множество Y , если каждый элемент
имеет образ
, т.е..

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

Если множество
совпадает с множествомY , то говорят, что
осуществляет отображениена множество Y .

Соответствие
называетсявзаимно однозначным (биекцией) , если а) является отображением; б) функционально; в) отображает X «на» множество Y ; г) из условия
следует
.

Другими словами,
является биекцией, если каждый элемент
имеет единственный образ
, а каждый элемент
имеет единственный прообраз
при данном отображении:

(1.2)

1.2.2 Определение бинарного отношения

Определение. Говорят, что на множестве X задано бинарное отношение R , если задано подмножество декартова произведения
(т.е.
).

Пример 2 . Пусть
Зададим наХ следующие отношения:

–отношение равенства;

–отношение предшествования;

делится на – отношение делимости.

Все эти отношения заданы с помощью характеристического свойства. Ниже перечислены элементы этих отношений:

Тот факт, что пара (x , y ) принадлежит данному отношению R , будем записывать:
или xRy . Например, для отношения Q запись 4Q 2 означает, что 4 делится на 2 нацело, т.е.

Областью определения
бинарного отношения R называется множество
Областью значений
называется множество

Так, для отношения Р из примера 2 областью определения является множество
, а областью значений –
.

1.2.3 Способы задания бинарного отношения

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

График отношения изображается в декартовой системе координат; на горизонтальной оси отмечается область определения, на вертикальной – множество значений отношения; элементу отношения (х,у ) соответствует точка плоскости с этими координатами. На рис. 1.7,а) приведен график отношения Q примера 2.

Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х,у ) принадлежит отношению R , то соответствующие точки из
и
соединяются отрезком прямой. На рис. 1.7,б) приведена схема отношения Q из примера 2.

Граф отношения
строится следующим образом. На плоскости в произвольном порядке изображаются точки – элементы множестваХ . Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х,у ) принадлежит отношению R . На рис. 1.8,а) приведен граф отношения Q примера 2.

Пусть
. Матрица отношения
имеет n строк и n столбцов, а ее элемент определяется по правилу:

На рис.1.8,б) приведена матрица отношения Q примера 2.

Определения

1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RÍA´B, RÍA´А.

2. Если А=В , то R – это бинарное отношение на A .

3. Обозначение: (x, y)ÎR Û xRy.

4. Область определения бинарного отношения R – это множество d R = {x : существует y такое, что (x, y)ÎR }.

5. Область значений бинарного отношения R – это множество r R = {y : существует x такое, что (x, y)ÎR }.

6. Дополнение бинарного отношения R между элементами А и В – это множество -R = (A´B) \ R .

7. Обратное отношение для бинарного отношенияR – это множество R -1 = {(y, x) : (x, y)ÎR} .

8. Произведение отношений R 1 ÍA´B и R 2 ÍB´C – это отношение R 1 × R 2 = {(x, y) : существует zÎB такое, что (x, z)ÎR 1 и (z, y)ÎR 2 }.

9. Отношение f называется функцией из А в В , если выполняется два условия:

а) d f = А , r f Í В

б) для всех x ,y 1 ,y 2 из того, что (x, y 1)Îf и (x, y 2)Îf следует y 1 =y 2 .

10. Отношение f называется функцией из А на В , если в первом пункте будет выполняться d f = А , r f = В .

11. Обозначение: (x, y)Îf Û y = f(x) .

12. Тождественная функция i A: A®A определяется так: i A (x) = x .

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

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

15. Свойства бинарного отношения R на множестве А :

- рефлексивность: (x, x)ÎR для всех xÎA .

- иррефлексивность: (x, x)ÏR для всех xÎA .

- симметричность: (x, y)ÎR Þ (y, x)ÎR .

- антисимметричность: (x, y)ÎR и (y, x)ÎR Þ x=y .

- транзитивность: (x, y)ÎR и (y, z)ÎR Þ (x, z)ÎR .

- дихотомия: либо (x, y)ÎR , либо(y, x)ÎR для всехxÎA иyÎA .

16. Множества А 1 , A 2 , ..., А r из Р(А) образуют разбиение множества А , если

- А i ¹ Æ , i = 1 , ..., r ,

- A = A 1 ÈA 2 È...ÈA r ,

- A i ÇA j = Æ , i ¹ j .

ПодмножестваА i , i = 1 , ..., r , называются блоками разбиения .

17. Эквивалентность на множестве А – это рефлексивное, транзитивное и симметричное отношение на А .

18. Класс эквивалентности элемента x по эквивалентности R – это множество [x] R ={y: (x, y)ÎR} .



19. Фактор множество A поR – это множество классов эквивалентности элементов множества А . Обозначение: A/R .

20. Классы эквивалентности (элементы фактор множества А/R ) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R , классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R . Классы эквивалентности либо не пересекаются, либо совпадают.

21. Предпорядок на множестве A – это рефлексивное и транзитивное отношение на А .

22. Частичный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А .

23. Линейный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пример 1.

Пусть A={1 , 2 , 3} , B={a , b} . Выпишем декартово произведение: A´B = { (1 , a) , (1 , b) , (2 , a) , (2 , b) , (3 , a) , (3 , b) } . Возьмём любое подмножество этого декартова произведения: R = { (1 , a) , (1 , b) , (2 , b) } . Тогда R – это бинарное отношение на множествах A и B .

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R – это множество d R = {1, 2} ¹ {1, 2, 3} , то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3 , a) или (3 , b) . Если добавить обе пары, то не будет выполняться второе условие, так как a¹b . По этой же причине из R нужно выбросить одну из пар: (1 , a) или (1 , b) . Таким образом, отношение R¢ = { (1 , a) , (2 , b) , (3 , b) } является функцией. Заметим, что R¢ не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1 , a) , (2 , a) , (3 , a) } , { (1 , a) , (2 , a) , (3 , b) } , { (1 , b) , (2 , b) , (3 , b) } и т.д.

Пример 2.

Пусть A={1 , 2 , 3} . Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) } . Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) } .

Примеры решения задач

1. Найти d R ,r R ,R -1 ,R×R ,R×R -1 ,R -1 ×R для R = {(x, y) | x, y Î D и x+y£0} .

Если (x, y)ÎR , то x и y пробегают все действительные числа. Поэтому d R = r R = D.

Если(x, y)ÎR , тоx+y£0 , значит y+x£0 и(y, x)ÎR . Поэтому R -1 =R .

Для любых xÎD , yÎD возьмём z=-|max(x, y)|-1 , тогда x+z£0 и z+y£0 , т.е.(x, z)ÎR и(z, y)ÎR .ПоэтомуR×R = R×R -1 = R -1 ×R = D 2 .

2. Для каких бинарных отношений R справедливо R -1 = -R ?

Пусть RÍA´B . Возможны два случая:

(1) AÇB¹Æ . Возьмём xÎAÇB . Тогда (x, x)ÎR Û (x, x)ÎR -1 Û (x, x)Î-R Û (x, x)Î(A´B) \ R Û (x, x)ÏR . Противоречие.

(2) AÇB=Æ . Так как R -1 ÍB´A , а-RÍA´B , то R -1 = -R= Æ . Из R -1 = Æ следует, что R = Æ . Из -R = Æ следует, что R=A´B . Противоречие.

Поэтому если A¹Æ иB¹Æ , то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)ÎR Û (x–y) – рациональное число. Доказать, что R есть эквивалентность.

Рефлексивность:

Для любого xÎD x-x=0 – рациональное число. Потому (x, x)ÎR .

Симметричность:

Если (x, y)ÎR , то x-y = . Тогдаy-x=-(x-y)=- – рациональное число. Поэтому (y, x)ÎR .

Транзитивность:

Если (x, y)ÎR , (y, z)ÎR , то x-y = и y-z = . Складывая эти два уравнения, получаем, что x-z = + – рациональное число. Поэтому (x, z)ÎR .

Следовательно, R – это эквивалентность.

4. Разбиение плоскости D 2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R , соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

а) две точки эквивалентны, если лежат на прямой вида y=2x+b , где b – любое действительное число.

b) две точки (x 1 ,y 1) и (x 2 ,y 2) эквивалентны, если (целая часть x 1 равна целой части x 2 ) и (целая часть y 1 равна целой части y 2 ).

с) решить самостоятельно.

Задачи для самостоятельного решения:

1. Доказать, что если f есть функция из A в B и g есть функция из B в C , то f×g есть функция из A в C .

2. Пусть A и B – конечные множества, состоящие из m и n элементов соответственно.

a) Сколько существует бинарных отношений между элементами множеств A и B ?

b) Сколько имеется функций из A в B ?

c) Сколько имеется 1-1 функций из A в B ?

d) При каких m и n существует взаимно-однозначное соответствие между A и B ?

3. Доказать, что f удовлетворяет условию f(AÇB)=f(A)Çf(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

КОМБИНАТОРИКА

Произведение всех натуральных чисел от 1 до n обозначается:

n! = 1·2·3·…·(n-1)·n, 0! = 1

Пусть X={x 1 , x 2 , ..., x n } – это множество из n элементов, k £ n .

Размещение элементов из X объёма k – это упорядоченное подмножество из k элементов, принадлежащих X .

Количество размещений объёма k из n

= n k (знач мест)

Если на каждую i -ю из k позиций можно поставить один из q i элементов множества X, то количество таких размещений равно:

(q 1 , q 2 , ..., q n) = q 1 × q 2 × ... × q n

Количество размещений объёма k из n

= n (n - 1 )(n - 2 ) … (n - k + 1 )=

Перестановка элементов из X – это размещение элементов из X объёма n .

Количество перестановок из n различных элементов:

= P n = n!

Если n элементов содержат q i элементов i -го сорта, q 1 + q 2 + ... + q m = n и элементы одного сорта идентичны, то число перестановок равно:

P n (q 1 , q 2 , ..., q m) =

Сочетание элементов из X объёма k – это неупорядоченное подмножество из k элементов, принадлежащих X .

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

Количество сочетаний объёма k из n различных элементов без повторений:

Количество сочетаний объёма k из n различных элементов с неограниченными повторениями:

Бином Ньютона:

Свойства:

(2)

(4)

(5)

При решении комбинаторных задач часто используются следующие правила комбинаторики:

  1. Правило суммы. Если объект А может быть выбран n способами, а объект B другими m способами, то выбор «либо А, либо В» может быть осуществлен n+m способами.
  2. Правило произведения. Если объект А может быть выбран n способами и после каждого из таких выборов объект B в свою очередь может быть выбран m способами, то выбор «A и B» в указанном порядке может быть осуществлен n×m способами.

Задача-пример . Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей?

Решение . Условие «не более трех» означает, что в команду может входить либо 3 юноши, либо 2 юноши, либо 1 юноша, либо ни одного юноши. Таким образом, в задаче выделяются четыре различных случая. В соответствии с правилом сложения нужно подсчитать количества вариантов в каждом из этих случаев и сложить их.

Рассмотрим первый случай. Нужно подсчитать, сколькими способами можно выбрать из 12 девушек и 10 юношей команду, состоящую из 3х юношей и 2х девушек. Из 10 юношей можно выбрать 3х юношей способами. Для каждых трех выбранных юношей можно выбрать также способами 2х девушек из 12ти. Поэтому работает правило умножения и в первом случае число вариантов команд равно × .

Аналогично, во втором случае: × .

В третьем случае: × .

В четвертом случае: .

Окончательный ответ: × + × + × + .

Примеры решения задач

№1.17. n (n>2) человек садятся за круглый стол. Два размещения по местам будем считать совпадающим, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол?

Решение.

Общее количество всевозможных рассадок равно числу перестановок из n элементов P n = n! Однако из этих рассадок нужно исключить совпадающие. Отношение соседства сохраняется при циклических перестановках (их n штук) и при симметрическом отражении (их также n штук):

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

№1.19. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз?

Решение.

Всего способов вынуть 10 карт из колоды . Из них в случаях в выборке не окажется ни одного туза. Поэтому ответ – .

№1.20. Сколькими способами можно составить три пары из n шахматистов?

Решение .

Сначала выберем из n шахматистов 6 человек. Это можно сделать способами. Теперь каждую шестёрку будем разбивать на пары. Для этого поставим 6 шахматистов в ряд, считая, что они имеют имена: a, b, c, d, e, f. Это можно сделать 6! способами. Однако нам не важен порядок внутри каждой пары и порядок самих пар. Перестановок, в которых шахматисты меняются местами в парах 2 3 . Перестановок, в которых меняются местами пары 3!. Поэтому разбить на пары 6 шахматистов можно способами. Ответ .

№1.24. Сколько существует чисел от 0 до 10 n , в которые не входят две идущие друг за другом одинаковые цифры?

Решение.

Рассмотрим все n-значные числа. Первую цифру мы можем выбрать 9-ю способами. Чтобы вторая цифра была отлична от первой, то её также можно выбрать 9-ю способами. Количество таких n-значных чисел равно количеству размещений объёма n из 9 элементов с неограниченными повторениями, т.е. равна 9 n для n>1 и 10 для n=1.

Поэтому ответ 10+9 2 +9 3 +...+9 n . Число 10 n не подходит.

ТЕОРИЯ АЛГОРИТМОВ

· Пусть N – это множество натуральных чисел, включая нуль.

· В данном разделе курса будут рассматриваться функции многих переменных f n (x 1 , ..., x n), определенные на некотором множестве MÍN n c натуральными значениями, т.е. f n (x 1 , ..., x n)ÎN, x i ÎN для i=1, ..., n, или f n Í N n +1 .

· Функция f n (x 1 , ..., x n) называется всюду определенной, если её областью определения является N n ­ , т.е. для любого набора из n натуральных чисел существует натуральное число, являющееся значением функции f n .

· Простейшие всюду определенные функции:

1. s(x)=x+1 для любого x;

2. o(x)=0 для любого x;

3. I n m (x 1 , ..., x m , ..., x n)=x m .

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

· Оператор суперпозиции:

Функция h n (x 1 , ..., x n) получается из функций g m , f n 1 , ..., f n m с помощью оператора суперпозиции, если h n (x 1 , ..., x n) = g m (f n 1 (x 1 , ..., x n), ..., f n m (x 1 , ..., x n)).

· Оператор примитивной рекурсии:

Функция f n +1 (x 1 , ..., x n , y) получается из функций g n (x 1 , ..., x n) и h n +2 (x 1 , ..., x n , y, z) с помощью оператора примитивной рекурсии, если она может быть задана схемой примитивной рекурсии:

æf n+1 (x 1 , ..., x n , 0) = g n (x 1 , ..., x n),

èf n+1 (x 1 , ..., x n , y+1) = h n+2 (x 1 , ..., x n , y, f n+1 (x 1 , ..., x n , y)).

· Оператор минимизации:

Функция f n (x 1 , ..., x n) получается из функции g n +1 (x 1 , ..., x n , y) с помощью оператора минимизации и обозначается f n (x 1 , ..., x n)=my, если:

f n (x 1 , ..., x n) определено и равно y Û g n +1 (x 1 , ..., x n , 0), ..., g n +1 (x 1 , ..., x n , y-1) определены и не равны нулю, а g n +1 (x 1 , ..., x n , y)=0.

(Можно говорить также: «Функция f n (x 1 , ..., x n) равна минимальному значению y, при котором функция g n +1 обращается в нуль»)

· Примитивно рекурсивная функция (прф)

Функция f n +1 (x 1 , ..., x n , y) называется примитивно рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Следует отметить, что все примитивно рекурсивные функции всюду определены.

· Частично рекурсивная функция (прф)

Функция f n +1 (x 1 , ..., x n , y) называется частично рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

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

Примеры решения задач

1. Доказать, что следующие функции являются примитивно рекурсивными.

Решение . Функция f(x) может быть получена с помощью n-кратного применения оператора суперпозиции к простейшей функции s(x).

Решение . Функция f(x) может быть задана следующей схемой примитивной рекурсии:

æf(x, 0) = x = I 1 1 (x),

èf(x, y+1) = x+y+1=f(x,y)+1=s(f(x,y))=s(I 3 3 (x,y,f(x,y))).

Здесь функция g(x) имеет вид g(x)= I 1 1 (x) и является, как и полагается, функцией одной переменной. А функция h(x,y,z) имеет вид h(x,y,z)=s(I 3 3 (x,y,z)) и является функцией трех переменных.

Заметим, что функции g(x) и h(x,y,z) являются прф, т.к. g(x) – третья простейшая функция, а h(x,y,z) может быть получена из простейших функций s(x) и I 3 3 (x,y,z) с помощью применения оператора суперпозиции.

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x) и h(x,y,z), то f(x,y) – прф.

Решение. Функция f(x) может быть задана следующей схемой примитивной рекурсии:

æf(x, 0) = 0 = o(x),

èf(x, y+1) = x(y+1)=xy+x=f(x,y)+x= I 3 3 (x,y,f(x,y)))+ I 3 1 (x,y,f(x,y))).

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x)=o(x) и h(x,y,z) = I 3 3 (x,y,z)) + I 3 1 (x,y,z)), то f(x,y) – прф.

2. Пусть g(x 1 , ..., x n ,y) примитивно рекурсивная функция. Доказать, что следующая функция примитивно рекурсивна:

Решение. Особенность этой функции заключается в том, что суммирование ведется по переменному числу слагаемых. Однако функция f n +1 может быть задана следующей схемой примитивной рекурсии:

æf(x 1 , ..., x n , 0) = g(x 1 , ..., x n ,0) – прф,

èf(x 1 , ..., x n , y+1) = = f(x 1 , ..., x n , y) + g(x 1 , ..., x n ,y+1) – сумма прф g и самой функции f.

3. Доказать, что следующая функция частично рекурсивна.

Решение. Покажем, что функция f(x,y) может быть получена с помощью оператора минимизации.

Пусть x³y, тогда f(x,y) определена и принимает некоторое значение: f(x,y) = x-y = z. Как вычислить z? Можно предложить следующий способ: начиная с нуля перебирать по порядку все значения z, пока не выполнится условие x-y=z, или x-y-z=0. Такое z обязательно найдется, т.к. x-y³0. Если же x-y<0, то ни какое натуральное z не подойдет.

Программист записал бы это так:

unsigned int f(x,y)

while((x-y-z)!=0) z++;

То же самое можно записать и в терминах оператора минимизации:

f(x, y)=mz[|x–y–z|=0]

Модуль необходим для того, чтобы функция g(x,y,z)=|x–y–z| была определена, даже если x–y<0. Заметим, что g(x,y,z)=|x–y–z| является примитивно рекурсивной, т.к. может быть получена с помощью конечного числа применений оператора суперпозиции к простейшим функциям.

a) нигде не определённая функция (т.е. функция с пустой областью определения) ;

b)

c)

Пусть R - некоторое бинарное отношение на множестве X, а х, у, z любые его элементы. Если элемент х находится в отношении R с элементом у, то пишут xRy.

1. Отношение R на множестве X называется рефлексивным, если каждый элемент множества находится в этом отношении с самим собой.

R -рефлексивно на X <=> xRx для любого x€ X

Если отношение R рефлексивно, то в каждой вершине графа имеется петля. Например, отношения равенства и параллельности для отрезков являются рефлексивными, а отношение перпендику­лярности и «длиннее» не являются рефлексивными. Это отражают графы на рисунке 42.

2. Отношение R на множестве X называется симметричным, если из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у находится в этом же отношении с элементом х.

R - симметрично на (хЯу =>у Rx)

Граф симметричного отношения содержит парные стрелки, идущие в противоположных направлениях. Отношения параллельнос­ти, перпендикулярности и равенства для отрезков обладают симмет­ричностью, а отношение «длиннее» - не является симметричным (рис. 42).

3. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у в этом отношении с элементом х не находится.

R - антисимметрично на Х« (xRy и xy ≠ yRx)

Замечание: черта сверху обозначает отрицание высказывания.

На графе антисимметричного отношения две точки может сое­динять только одна стрелка. Примером такого отношения является отношение «длиннее» для отрезков (рис. 42). Отношения параллель­ности, перпендикулярности и равенства не являются антисиммет­ричными. Существуют отношения, не являющиеся ни симметрич­ными, ни антисимметричными, например отношение «быть братом» (рис. 40).

4. Отношение R на множестве X называется транзитивным, если из того, что элемент х находится в данном отношении с элементом у и элемент у находится в этом лее отношении с элементом z, следует, что элемент х находится в данном отношении с элементом Z

R - транзитивно на A≠ (xRy и yRz=> xRz)

На графах отношений «длиннее», параллельности и равенства на рисунке 42 можно заметить, что если стрелка идет от первого элемента ко второму и от второго к третьему, то обязательно есть стрелка, идущая от первого элемента к третьему. Эти отношения яв­ляются транзитивными. Перпендикулярность отрезков не обладает свойством транзитивности.

Существуют и другие свойства отношений между элементами одного множества, которые мы не рассматриваем.

Одно и то же отношение может обладать несколькими свойст­вами. Так, например, на множестве отрезков отношение «равно» - рефлексивно, симметрично, транзитивно; отношение «больше» - антисимметрично и транзитивно.


Если отношение на множестве X рефлексивно, симметрично и транзитивно, то оно является отношением эквивалентности на этом множестве. Такие отношения разбивают множество X на классы.

Данные отношения проявляются, например, при выполнении заданий: «Подбери полоски равные по длине и разложи по груп­пам», «Разложи мячи так, чтобы в каждой коробке были мячи одно­го цвета». Отношения эквивалентности («быть равным по длине», «быть одного цвета») определяют в данном случае разбиение мно­жеств полосок и мячей на классы.

Если отношение на множестве 1 транзитивно и антисимметрич­но, то оно называется отношением порядка на этом множестве.

Множество с заданным на нем отношением порядка называется упорядоченным множеством.

Например, выполняя задания: «Сравни полоски по ширине и разложи их от самой узкой до самой широкой», «Сравни числа и разложи числовые карточки по порядку», дети упорядочивают эле­менты множеств полосок и числовых карточек при помощи отно­шений порядка; «быть шире», «следовать за».

Вообще отношения эквивалентности и порядка играют боль­шую роль в формировании у детей правильных представлений о классификации и упорядочении множеств. Кроме того, встречается много других отношений, которые не являются ни отношениями эквивалентности, ни отношениями порядка.


6. Что такое характеристическое свойство множества?

7. В каких отношениях могут находиться множества? Дайте пояснения каждому случаю и изобразите их при помощи кругов Эйлера.

8. Дайте определение подмножества. Приведите пример множеств, одно из которых является подмножеством другого. Запишите их от­ношение при помощи символов.

9. Дайте определение равных множеств. Приведите примеры двух равных множеств. Запишите их отношение при помощи символов.

10. Дайте определение пересечения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.

11. Дайте определение объединения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.

12. Дайте определение разности двух множеств и изобразите ее при помощи кругов Эйлера для каждого частного случая.

13. Дайте определение дополнения и изобразите его при помощи кругов Эйлера.

14. Что называется разбиением множества на классы? Назовите усло­вия правильной классификации.

15. Что называется соответствием между двумя множествами? Назо­вите способы задания соответствий.

16. Какое соответствие называется взаимно однозначным?

17. Какие множества называют равномощными?

18. Какие множества называют равночисленными?

19. Назовите способы задания отношений на множестве.

20. Какое отношение на множестве называют рефлексивным?

21. Какое отношение на множестве называют симметричным?

22. Какое отношение на множестве называют антисимметричным?

23. Какое отношение на множестве называют транзитивным?

24. Дайте определение отношения эквивалентности.

25. Дайте определение отношения порядка.

26. Какое множество называют упорядоченным?