Бинарные отношения и их свойства. Бинарные отношения, функции, порядок Рефлексивное бинарное отношение
Понятие отношения наряду с понятием множества «пронизывает» всю математику. Интуитивно отношение понимается как связь объектов. Наша задача заключается в том, чтобы, используя сформулированные выше конструкции теории множеств, определить на математическом языке, что же понимается в математике под термином «отношение».
Бинарные отношения на множестве
Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л:,у) в качестве элемента некоторого множества; если д; не связан с у , значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.
Бинарным отношением на множестве А называется произвольное множество пар элементов из А.
Другими словами, бинарное отношение на множестве А - ото подмножество прямого произведения АхА=А 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.»
Отмстим, что любой линейный порядок на конечном множестве задается нумерацией его элементов. Чтобы подчеркнуть, что порядок может быть нс линейным, упорядоченное множество в общем случае иногда называют частично упорядоченным.
Основы дискретной математики.
Понятие множества. Отношение между множествами.
Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.
Объекты, составляющие множество называются элементами множества. Для того чтобы некоторую совокупность объектов можно было называть множеством должны выполняться следующие условия:
· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.
· Должно существовать правило, по которому элементы можно отличить друг от друга.
Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:
· Перечисление элементов множества. - для конечных множеств.
· Указание характеристического свойства 
.
Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).
Два множества называются равными, если они состоят из одних и тех же элементов. , A=B
Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .
Например: , B =>
Свойство:
Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.
Операции над множествами.
| A |
| B |
2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.
Н-р: , ,
Свойство: операции объединения и пересечения.
· Коммутативность. 
· Ассоциативность. ;
· Дистрибутивный. ;
| 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 Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями,
т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.
Вообще бинарные отношения на множестве X определяют следующим способом:
Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения X х X.
Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.
Условимся отношения обозначать буквами R, S, Т, Р и др.
Если R - отношения на множестве X, то, согласно определению, R X х X. С другой стороны, если задано некоторое подмножество множества X х X, то оно определяет на множестве X некоторое отношение R.
Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) R или x R y. Последняя запись читается: «Элемент х находится в отношении R с элементом у».
Отношения задают так же, как соответствия. Отношение можно задать, перечислив пары элементов множества X, находящиеся в этом отношении. Формы представления таких пар могут быть различными - они аналогичны формам задания соответствий. Отличия касаются задания отношений при помощи графа.
Построим, например, граф отношений «меньше», заданного на множестве Х= (2, 4, 6, 8}. Для этого элементы множества X изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 1).
На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 2).
Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).
Для отношения R, заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше у», то обратным ему будет отношение «у больше х».
Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».
Свойства отношений
Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению ХхХ. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые. Рассмотрим на множестве отрезков, представленных на рис. 3, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 4) и будем их сравнивать.
Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно .
Определение. Отношение R на множестве X называется рефлексивным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.
R рефлексивно на Х <=> xRx для любого х X
Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.
Примеры рефлексивных отношений:
Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);
Отношение подобия треугольников (каждый треугольник подобен самому себе).
Существуют отношения, которые свойством рефлексивности на обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 4) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.
Обратим теперь внимание на графы отношений перпендикулярности и равенства отрезков. Они «похожи» тем, что если есть одна стрелка, соединяющая пару элементов, то обязательно есть и другая, соединяющая те же элементы, но идущая в противоположном направлении. Эта особенность графа отражает те свойства, которыми обладают отношения параллельности и равенства отрезков:
Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;
Если один отрезок равен другому отрезку, то этот «другой» равен первому.
Про отношения перпендикулярности и равенства отрезков говорят, что они обладают свойством симметричности или, просто симметричны.
Определение. Отношение R на множестве X называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.
Используя символы, это отношение можно записать в таком виде:
R симметрично на X <=> (xRy => yRx)
Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к х. Справедливо и обратное утверждение. Граф, содержащий вместе с каждой стрелкой, идущей от х к у, и стрелку, идущую от у к х, является графом симметричного отношения.
В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:
Отношение параллельности на множестве прямых (если прямая х параллельна прямой у, то и прямая у параллельна прямой х);
Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).
Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» на множестве отрезков. Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Про отношения «длиннее» говорят, что оно обладает свойством антисимметричности или просто антисимметрично.
Определение. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится .
антисимметрично на X <=> (xRy и х≠у => )
Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения.
Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:
Отношение «больше» для чисел (если х больше у, то у не может быть больше х);
Отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х).
Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 5. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.
Обратим внимание еще раз на одну особенность графа отношения «длиннее» (рис. 4). На нем можно заметить: если стрелки проведены от е к а и от а к с , то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с , то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.
Определение. Отношение R на множестве X называется транзитивным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z.
Используя символы, это определение можно записать в таком виде:
R транзитивно на X <=> (xRy и yRz => xRz)
Граф транзитивного отношения с каждой парой стрелок, идущих от х к у и у к z , содержит стрелку, идущую от х к z . Справедливо и обратное утверждение.
Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z , то отрезок х равен отрезку z . Это свойство отражено и на графе отношения равенства (рис. 4)
Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку d, а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!
Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.
Определение. Отношение R на множестве X называется связанным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находится в отношении R с элементом у, либо элемент у находится в отношении R с элементом х.
Используя символы, это определение можно записать в таком виде:
R связанно на множестве X <=> (х≠у xRy или yRx)
Например, свойством связанности обладают отношения «больше» для натуральных чисел: для любых различных чисел х и у можно утверждать, что либо х> у, либо у > х.
На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.
Существуют отношения, которые свойством связанности не обладают. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа хну, что ни число х не является делителем числа у, ни число у не является делителем числа х.
Выделенные свойства позволяют анализировать различные отношения с общих позиций - наличия (или отсутствия) у них тех или иных свойств.
Так, если суммировать все сказанное об отношении равенства, заданном на множестве отрезков (рис. 4), то получается, что оно рефлексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности-симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве
отрезков связанными не являются.
Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 6).
Решение. Отношение R- антисимметрично, так как вершины графа соединяются только одной стрелкой.
Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с , на графе есть стрелка, идущая от b к с .
Отношение R - связанно, так как любые две вершины соединены стрелкой.
Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.
Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.
Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число у не больше числа х в 2 раза.
Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.
Заданное отношение не транзитивно, так как из того, что число х больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.
Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3,5 и 8 и др.
Пусть задано некоторое непустое множество А и R – некоторое подмножество декартова квадрата множества А: R A A .
Отношением R на множестве А называют подмножество множества А А (или А 2 ). Таким образом отношение есть частный случай соответствия, где область прибытия совпадает с областью отправления. Так же, как и соответствие, отношение – это упорядоченные пары, где оба элемента принадлежат одному и тому же множеству.
R A A = {(a, b) | aA, bA, (a, b)R}.
Тот факт, что (a , b )R можно записать так: a R b . Читается: «а находится в отношении R к b » или «между а и b имеет место отношение R». В противном случае записывают: (a , b )R или a R b .
Примером отношений на множестве чисел являются следующие: «=», «», «», «>» и т.д. На множестве сотрудников какой-либо фирмы ‑ отношение «быть начальником» или «быть подчинённым», на множестве родственников – «быть предком», «быть братом», «быть отцом» и т.д.
Рассмотренные отношения носят название бинарных (двухместных) однородных отношений и являются важнейшими в математике. Наряду с ними рассматривают также п -местные или п -арные отношения:
R A A … A = A n = {(a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n A}.
Поскольку отношение есть частный случай соответствия, для их задания могут быть использованы все ранее описанные способы.
Очевидно, что задавая отношение матричным способом, мы получим квадратную матрицу.
При геометрическом (графическом) изображении отношения мы получим схему, включающую:
вершины, обозначаемые точками или кружочками, которые соответствуют элементам множества,
и дуги (линии), соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу a к вершине, соответствующей элементу b , если a R b .
Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.
Задача 4.9.1 . Отношение R «быть делителем на множестве M = {1, 2, 3, 4 }» может быть задано матрицей :
перечислением: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4)};
геометрически (графически) :
1. Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям на множестве А = {1, 2, 3, 4, 5, 6, 7}:
R1 = {(x, y)| x, yA; x + y = 9};
R2 = {(x, y)| x, yA; x < y}.
2. Отношение R на множестве X = {a, b, c, d} задано матрицей
,
у которой порядок строк и столбцов соответствует порядку выписанных элементов. Перечислить упорядоченные пары, принадлежащие данному отношению. Изобразить отношение с помощью графа.
3. Отношение на множестве А = {1, 2, 3, 4} представлено графом. Необходимо:
перечислить упорядоченные пары, принадлежащие R;
выписать соответствующую матрицу;
определить это отношение с помощью предикатов.
(ответ: a-b= 1).
4.10. Основные типы (свойства) бинарных отношений
Пусть задано бинарное отношение R на множестве А 2 : R A A = {(a , b ) | a A, b A, (a , b )R}
Бинарное отношение R на множестве А называется рефлексивным , если для любого a А выполняется a R a , то есть (а , а )R. Главная диагональ матрицы рефлексивного отношения состоит из единиц. Граф рефлексивного отношения обязательно имеет петли у каждой вершины.
Примеры рефлексивных отношений: , =, на множестве действительных чисел, «не быть начальником» на множестве сотрудников.
Бинарное отношение R на множестве А называется антирефлексивным (иррефлексивным ), если для любого a А не выполняется отношение a R a , то есть (а , а )R. Главная диагональ матрицы иррефлексивного отношения состоит из нулей. Граф иррефлексивного отношения не имеет петель.
Примеры антирефлексивных отношений: <, > на множестве действительных чисел, перпендикулярность прямых на множестве прямых.
Бинарное отношение R на множестве A называется симметричным , если для любых a , b А из a R b следует b R a , то есть если (a , b )R , то и(b , a )R . Матрица симметричного отношения симметрична относительно своей главной диагонали (σ ij = σ ji ). Граф симметричного отношения не является ориентированным (рёбра изображаются без стрелок). Каждая пара вершин здесь соединена неориентированным ребром.
Примеры симметричных отношений: на множестве действительных чисел, «быть родственником» на множестве людей.
Бинарное отношение R на множестве A называется:
анти симметричным , если для любых a , b А из a R b и b R a следует, что a =b . То есть, если (a , b )R и(b , a )R , то отсюда вытекает, что a =b . Матрица антисимметричного отношения вдоль главной диагонали имеет все единицы и не имеет ни одной пары единиц, расположенных на симметричных местах по отношению к главной диагонали. Иными словами, все σ ii =1, и если σ ij =1, то обязательно σ ji =0. Граф антисимметричного отношения имеет петли у каждой вершины, а вершины соединяются только одной направленной дугой.
Примеры антисимметричных отношений: , , на множестве действительных чисел; , на множествах;
а симметричным , если для любых a , b А из a R b следует невыполнение b R a , то есть если (a , b )R , то (b , a )R . Матрица асимметричного отношения вдоль главной диагонали имеет нули (σ ij =0) все и ни одной симметричной пары единиц (если σ ij =1, то обязательно σ ji =0). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.
Примеры асимметричных отношений: <, > на множестве действительных чисел, «быть отцом» на множестве людей.
Бинарное отношение R на множестве A называется транзитив ным , если для любых a , b , с А из a R b и b R a следует, что и a R с . То есть если (a , b )R и(b , с )R вытекает, что (а , с )R . Матрица транзитивного отношения характеризуется тем, что если σ ij =1 и σ jm =1, то обязательно σ im =1. Граф транзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно есть дуги из первой в третью вершину.
Примеры транзитивных отношений: <, , =, >, на множестве действительных чисел; «быть начальником» на множестве сотрудников.
Бинарное отношение R на множестве A называется антитранзитив ным , если для любых a , b , с А из a R b и b R a следует, что не выполняется a R с . То есть если (a , b )R и(b , с )R вытекает, что (а , с )R . Матрица антитранзитивного отношения характеризуется тем, что если σ ij =1 и σ jm =1, то обязательно σ im =0. Граф антитранзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно нет дуги из первой в третью вершину.
Примеры антитранзитивных отношений : «несовпадение чётности» на множестве целых чисел; «быть непосредственным начальником» на множестве сотрудников.
Если отношение не обладает некоторым свойством, то, добавив недостающие пары, можно получить новое отношение с данным свойством. Множество таких недостающих пар называют замыканием отношения по данному свойству. Обозначают его как R * . Так можно получить рефлексивное, симметричное и транзитивное замыкание.
Задача 4.10.1. На множестве А = {1, 2, 3, 4} задано отношение R={(a ,b )| a ,b A, a +b чётное число}. Определить тип данного отношения.
Решение. Матрица данного отношения:
.
Очевидно, что отношение является
рефлексивным
,
так как вдоль главной диагонали
расположены единицы. Оно симметрично
:
σ 13
= σ 31 ,
σ 24
= σ 42 .
Транзитивно
:
(1,3)R,
(3,1)R
и
(1,1)R;
(2,4)R,
(4,2)R
и
(2,2)R
и т.д.
Задача 4.10.2. Какими свойствами на множестве А = {a , b , c , d } обладает бинарное отношение R = {(a ,b ), (b ,d ), (a ,d ), (b ,a ), (b ,c )}?
Решение . Построим матрицуданного отношения и его граф:
Отношение иррефлексивно , так как все σ ii = 0. Оно не симметрично , так как σ 23 =1, а σ 32 =0, однако σ 12 =σ 21 =1. Отношение не транзитивно , поскольку σ 12 =1, σ 23 =1 и σ 13 =0; σ 12 =1, σ 21 =1 и σ 11 =0; но при этом σ 12 =1, σ 24 =1 и σ 14 =1.
Задача 4.10.3. На множестве А = {1,2,3,4,5} задано отношение R = {(1,2), (2,3), (2,4), (4,5)}. Определить тип отношения и найти следующие замыкания для R:
рефлексивное;
симметричное;
транзитивное.
Решение. Отношение иррефлексивно, поскольку нет ни одного элемента вида (а ,а ). Асимметрично, так как не содержит пар вида (a ,b ) и (b ,a ) и все диагональные элементы равны 0. Антитранзитивно, поскольку (1,2)R, (2,3)R, но (1,3)R. Аналогично (2,4)R, (4,5)R, а (2,5)R и т.д.
рефлексивное замыкание данного отношения R * ={(1,1), (2,2), (3,3), (4,4), (5,5)};
симметричное замыкание: R*={(2,1), (3,2), (4,2), (5,4)};
транзитивное замыкание: R*={(1,3), (1,4), (2,5)}. Рассмотрим граф исходного отношения и полученного транзитивного.
Задачи для самостоятельного решения.
1. Задано отношение R = {(1,1), (1,2), (1,3), (3,1), (2,3)}. Определить его тип и найти замыкания по рефлексивности, симметричности и транзитивности.
2.Отношение на множестве слов русского языка определено следующим образом: а Rb тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.
3. Указать примеры бинарных отношений на множестве А = {1, 2) и В = {1, 2, 3}, которые были бы:
не рефлексивное, не симметричное, не транзитивное;
рефлексивное, не симметричное, не транзитивное;
симметричное, но не рефлексивное и не транзитивное;
транзитивное, но не рефлексивное и не симметричное;
рефлексивное, симметричное, но не транзитивное;
рефлексивное, транзитивное, но не симметричное;
не рефлексивное, симметричное, транзитивное;
рефлексивное, симметричное, транзитивное.
Определения
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) 