Пусть 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. Какое множество называют упорядоченным?
Связанные определения
Свойства отношений
Бинарные отношения могут обладать различными свойствами, такими как
Виды отношений
- Рефлексивное транзитивное отношение называется отношением квазипорядка.
- Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности .
- Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка .
- Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка .
- Полное антисимметричное (для любых x, y выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка.
- Антирефлексивное асимметричное отношение называется отношением доминирования.
Виды двухместных отношений
- Обратное отношение [уточнить ] (отношение, обратное к R) - это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R −1 . Для данного отношения и обратного ему верно равенство: (R −1) −1 = R.
- Взаимо-обратные отношения (взаимообратные отношения) - отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого - областью значений другого.
- Рефлексивное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любого х этого множества элемент х находится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство , одновременность , сходство.
- Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отношении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
- Транзитивное отношение - двухместное отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
- Нетранзитивное отношение [уточнить ] - двухместное отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
- Симметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности , подобия , одновременности, некоторые отношения родства (например, отношение братства).
- Антисимметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR −1 y следует х = у (то есть R и R −1 выполняются одновременно лишь для равных между собой членов).
- Асимметричное отношение [уточнить ] - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
- Отношение эквивалентности (отношение тождества [уточнить ] , отношение типа равенства) - двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке, подобие , одновременность . Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
- Отношения порядка - отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») - «строгий» порядок.
- Функция - двухместное отношение R , определенное на некотором множестве, отличающееся тем, что каждому значению x отношения xRy y . Пример: «y отец x ». Свойство функциональности отношения R записывается в виде аксиомы: (xRy и xRz )→(y ≡z ). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y , но не наоборот.
- Биекция (одно-однозначное отношение) - двухместное отношение R , определенное на некотором множестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у , и каждому значению у соответствует единственное значение х . Одно-однозначное отношение является частным случаем однозначного отношения.
- Связанное отношение - это двухместное отношение R , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx ). Пример: отношение «меньше» (<).
Операции над отношениями
Так как отношения, заданные на фиксированной паре множеств , , суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных ,
Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.
Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.
Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом.
Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .
Пусть теперь , . Произведением отношений , называется отношение такое, что
Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.
Например, рассмотрим отношение строгого порядка определённого на множестве натуральных чисел. Несложно заметить, что
Бинарные отношения и называются перестановочными, если . Несложно заметить, что для любого бинарного отношения , определённого на , , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.
Имеют место следующие тождества:
Отметим, что аналоги последних двух тождеств для не имеют места.
Некоторые свойства отношения можно определить, используя операции над отношениями:
См. также
Литература
- А. И. Мальцев. Алгебраические системы. - М .: Наука, 1970.
Wikimedia Foundation . 2010 .
- двуместный предикат на заданном множестве. Под Б. о. иногда понимают подмножество множества упорядоченных пар (а, 6) элементов заданного множества А. Б. о. частный случай отношения. Пусть. Если, то говорят, что элемент находится в бинарном… … Математическая энциклопедияВ логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия
отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки
В теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия
У этого термина существуют и другие значения, см. Отношение. Отношение математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов … Википедия
У этого термина существуют и другие значения, см. Отношение. Отношение в логике первого порядка двух и более аргументный предикат (многоместный предикат), двух и более предикатное свойство. Знак отношения: R.[уточнить] В терминах отношений… … Википедия, А. И. Широков. Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое… электронная книга
Бинарные отношения.
Пусть A и B – произвольные множества.
Возьмем по одному элементу из каждого множества, a из A, b из B и
запишем их так:
Декартовым
произведением
произвольных множеств A и B (обозначается: AB)
называется множество, состоящее из всех возможных упорядоченных пар, первый
элемент которых принадлежит A, а второй принадлежит B. По определению: AB = {
Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.
AB = {
BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A 2 = {
BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
Бинарным
отношением
на множестве M называется множество некоторых
упорядоченных пар элементов множества M. Если r – бинарное отношение и пара
Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.
Пример 7.
Отношение ³ на множестве целых чисел
является бинарным отношением. Это бесконечное множество упорядоченных пар вида
Пример 8.
Отношение равенства на множестве A является бинарным
отношением: I A = {
Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.
Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.
Отношением, обратным
к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = {
Композицией
бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = {
Пример 9. Пусть бинарное отношение r
задано на множестве M = {a, b, c, d}, r = {
Пусть r – бинарное отношение на множестве M. Отношение r
называется рефлексивным
, если x r x для любого x Î M. Отношение r называется симметричным
, если вместе
с каждой парой
Укажем критерии выполнения этих свойств.
Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.
Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .
Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .
Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.
Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.
Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.
Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.
Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.
Определения
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)
При решении комбинаторных задач часто используются следующие правила комбинаторики:
- Правило суммы. Если объект А может быть выбран n способами, а объект B другими m способами, то выбор «либо А, либо В» может быть осуществлен n+m способами.
- Правило произведения. Если объект А может быть выбран 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 у элементов множества 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 не транзитивно.