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

Унарные (одноместные) отношения отражают наличие какого-то одного признака R у элементов множества M (например, «быть красным» на множестве шаров в урне).

Бинарные (двуместные) отношения используются для определения взаимо

связей, которыми характеризуются пары элементов во множестве M .

Например, на множестве людей могут быть заданы следующие отношения: «жить в одном городе», «x работает под руководством y », «быть сыном», «быть старше» и т.д. на множестве чисел: «число a больше числа b », «число a является делителем числа b », «числа a и b дают одинаковый остаток при делении на 3».

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

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

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

Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда можно просто говорить об отношении R на A .

Пример 1 . Выпишите упорядоченные пары, принадлежащие бинарным отношениям R 1 и R 2 , заданными на множествах A и : , . Подмножество R 1 состоит из пар: . Подмножество .

Область определения R на есть множество всех элементов из A таких, что для некоторых элементов имеем . Иными словами область определения R есть множество всех первых координат упорядоченных пар из R .

Множество значений отношения R на есть множество всех таких, что для некоторых . Другими словами множество значений R есть множество всех вторых координат упорядоченных пар из R .

В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .

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

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

Пример 5 . Пусть , .

Пусть R 1 задано на перечислением упорядоченных пар: . Бинарное отношение R 2 на множестве задано с помощью правила: упорядочена пара , если a делится на b . Тогда R 2 состоит из пар: .

Бинарные отношения, из примера 2, R 1 и R 2 изображены графически на рис. 6 и рис.7.

Рис. 6 Рис. 7

Чтобы изобразить бинарное отношение с помощью стрелок, слева изображаются точками элементы множества A , справа - множества B . Для каждой пары (a, b) , содержащейся в бинарном отношении R , проводится стрелка от a к b , . Графическое изображение бинарного отношения R 1 , приведенного в примере 6, показано на рис.8.

Рис.8

Бинарные отношения на конечных множествах могут быть заданы матрицами. Предположим, что задано бинарное отношение R между множествами A и B . , .

Строки матрицы нумеруются элементами множества A , а столбцы – элементами множества B . Ячейку матрицы, стоящую на пересечении i - ой строки и j - ого столбца принято обозначать через C ij , а заполняется она следующим образом:

Полученная матрица будет иметь размер .

Пример 6. Пусть задано множество . На множестве задайте списком и матрицей отношение R – «быть строго меньше».

Отношение R как множество содержит все пары элементов (a , b) из M такие, что .

Матрица отношения, построенная по вышеуказанным правилам, имеет следующий вид:

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

1. Бинарное отношение R на множестве называетсярефлексивным , если для любого элемента a из M пара (a, a) принадлежит R , т.е. имеет место для любого a из M :

Отношения «жить в одном городе», «учиться в одном вузе», «быть не больше» являются рефлексивными.

2. Бинарное отношение называется антирефлексивным ,если оно не обладает свойством рефлексивности для любых a :

Например, «быть больше», «быть младше» - это антирефлексивные отношения .

3. Бинарное отношение R называется симметричным , если для любых элементов a и b из M из того, что пара (a, b) принадлежит R , , вытекает, что пара (b, a) принадлежит R , т.е.

Симметрична параллельность прямых, т.к. если // , то // . Симметрично отношение «быть равным» на любом множестве или «быть взаимнопростым на N».

Отношение R симметрично тогда и только тогда, когда R=R -1

4. Если для несовпадающих элементов верно отношение , но ложно , то отношение антисимметрично . Можно сказать иначе:

Антисимметричными являются отношения «быть больше», «быть делителем на N», «быть младше».

5. Бинарное отношение R называется транзитивным , если для любых трех элементов из того, что пары (a, b) и (b, c) принадлежат R , следует, что пара (a, c) принадлежит R :

Транзитивны отношения : «быть больше», «быть параллельным», «быть равным» и др.

6. Бинарное отношение R антитранзитивно , если оно не обладает свойством транзитивности.

Например, «быть перпендикулярным» на множестве прямых плоскости ( , , но неверно, что ).

Т.к. бинарное отношение может быть задано не только прямым перечислением пар, но и матрицей, то целесообразно выяснить, какими признаками характеризуется матрица отношения R , если оно: 1) рефлексивно, 2) антирефлексивно, 3)симметрично, 4) антисимметрично, 5) транзитивно.

Пусть R задано на , .R либо выполняется в обе стороны, либо не выполняется вообще. Таким образом, если в матрице стоит единица на пересечении i - ой строки и j - ого столбца, т.е. C ij =1, то она должна стоять и на пересечении j - ой строки и i - ого столбца, т.е. C ji =1, и наоборот, если C ji =1, то C ij =1. Таким образом, матрица симметричного отношения симметрична относительно главной диагонали.

4. R антисимметрично, если из и следует: . Это означает, что в соответствующей матрице ни для каких i , j не выполняется C ij = C ji =1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали .

5. Бинарное отношение R на непустом множестве A называется транзитивным если

Вышеприведенное условие должно выполняться для любых элементов матрицы. И, наоборот, если в матрице R имеется хотя бы один элемент C ij =1, для которого данное условие не выполняется, то R не транзитивно.

Пусть 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. Какое множество называют упорядоченным?

Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.

Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) \in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) \notin R%% — %%a%% не уважает %%b%%.

Определение

Бинарным отношением , определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.

Пример

Рассмотрим отношение больше на множестве %%M = \{1, 2\}%%. Тогда

$$ M^2 = \big\{(1, 1), (1,2), (2,1), (2,2)\big\} $$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = \big\{(2,1)\big\} $$

Виды бинарных отношений

Рефлексивное бинарное отношение

рефлексивным , если для любого элемента %%a%% из %%M%%, выполняется условие %%a~R~a%%. $$ \begin{array}{l} \forall a\in M~~a~R~a \text{ или}\\ \forall a\in M~~(a,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
2. Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным , так как каждое действительное число равно самому себе.

Симметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется симметричным , если для любых двух элементов %%a, b%% из %%M%%, из условия %%a~R~b%% следует условие %%b~R~a%%.

$$ \begin{array}{l} \forall a,b\in M~~a~R~b \rightarrow b~R~a \text{ или}\\ \forall a,b\in M~~(a,b) \in R \rightarrow (b,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
2. Пусть %%R%% — отношение, определенное на множестве %%M = \{a,b,c\}%%. При этом %%R = \big\{ (a,b), (b,c), (a,a), (b,a), (c,b)\big\}%%. Для этого отношения имеем %%\forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. По определению %%R%% симметрично.

Транзитивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется транзитивным , если для любых элементов %%a, b, c%% из %%M%%, из условий %%a~R~b%% и %%b~R~c%% следует условие %%a~R~c%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text{ или}\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end{array} $$

Пример

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным , так как для любых элементов выполняется условние %%\forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).

Антисимметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным , если для любых элементов %%a, b%% из %%M%%, из условий %%a~R~b%% и %%b~R~a%% следует условие %%a = b%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text{ или}\\ \forall a,b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end{array} $$

Пример

Отношение больше или равно на множестве действительных чисел антисимметрично . Действительно, если %%a \geq b%% и %%b \geq a%%, %%a = b%%.

Эквивалентное бинарное отношение

эквивалентности , если оно рефлексивно , симметрично и транзитивно .

Нетрудно проверить, что отношение параллельности на множестве прямых плоскости является отношением эквивалентности.

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

Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка , если оно рефлексивно , антисимметрично и транзитивно .

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

Построение отрицаний

Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:

• отношение %%R%% рефлексивно,
• отношение %%R%% симметрично,
• отношение %%R%% транзитивно,
• отношение %%R%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%\forall a \in M~~a~R~a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%\overline{\forall a \in M~~a~R~a}%%. Используем равносильность %%\overline{\forall x P(x)} \equiv \exists x \overline {P(x)}%%. В нашем случае получаем %%\forall a \in M~~a~R~a \equiv \exists a\in M~~a~\not\text{R }~a%%, что и нужно.

Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:

%%R%% не рефлексивно тогда и только тогда, когда

$$ \exists a \in M~~a~\not R~a $$

%%R%% не симметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$

%%R%% не транзитивно тогда и только тогда, когда

$$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$

%%R%% не антисимметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$

Основы дискретной математики.

Понятие множества. Отношение между множествами.

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

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

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

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

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

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .

Например: , B =>

Свойство:

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

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

A

B

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

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

· Ассоциативность. ;

· Дистрибутивный. ;

U

4.Дополнение . Если А – подмножество универсального множества U , то дополнением множества А до множества U (обозначается ) называется множество состоящее из тех элементов множества U , которые не принадлежат множеству А .

Бинарные отношения и их свойства.

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

(а 1 , а 2 , а 3 ,…а n) , где а 1 ϵ А 1 ; а 2 ϵ А 2 ; …; а n ϵ А n ;

Декартовым (прямым) произведением множеств А 1 , А 2 , …, А n , называется мн-во, которое состоит из упорядоченных n k вида .

Н-р: М = {1,2,3}

М× М= М 2 = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n =2, то рассматривают бинарные отношения. При чем говорят, что а 1 , а 2 находятся в бинарном отношении R , когда а 1 R а 2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М 2 = {(a, b )| a, b ϵ M } в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

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

· Антирефлексивность (иррефлексивность): .

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

· Антисимметричность: .

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

· Асимметричность: .

Виды отношений.

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

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

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

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

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

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

Определения

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)