Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 11
Текст из файла (страница 11)
Для того чтобы иметь такую возможность, необходимо наложить дополнительныв условия, которые мы рассмотрим в следующей главе. Рассмотрим теперь несколько упражнений. Они иаображают ситуации, которые «легко описать» в математических терминах, однако следует заботиться о том, чтобы в отношение включались только тв пары, которые ему принадлежат, Мы обпаруясим, что иногда полезно воспольооваться диаграммами. У и р а ж н е н н е 2.6. $. Пусть В н Я определены на Р, где Р— множество всех людей, следующим обраэом: В ((х, у): х, у ж Р и х является отцом у), Я ((х, у): х, ушр и х — дочь у). Описать явно следующие отношения: а) В»; б) 8»; в) В ° Я; г) Я В; д) Я в'В-с; е) В-с ~8; ж) В-с Я-с; а) 8 ' ° В; ) Я ' ° 5 ', ) Я-' ° В '.
и 8. Замыкание отношений Понятие замыкания является фундаментальным математическим понятием и испольауется в большинстве равделов математики. Чтобы проиллюстрировать это понятие, рассмотрим следующий пример. Возьмем объект хо и процесс р, который порождает мнонсество и определяет последовательность хь х», ... ..., х„, ... такую, что х, «а р (хо), х» ж р (хс), х„ св р(х„ с), Множество, содержащее все элементы всех последовательностей, которые могут быть выведены при помощи р, и начинающиеся с хо, называется вамыпаниез«процесса р относительно хо. Поэтому «ответ» будет содержаться в р"(хо) при некотором и.
Однако мы не знаем заранее значение и. Более того, если мы возьмем произвольный элемент р из этого замыкания и выполним процесс р, начиная с р, то не получим ничего нового. Результат уже содержится в замыкании. Множество не может быть расширено таким путем (оно аамквуто). Пример 8Л. Возьмем квадрат 8, размеченный, как это покавано на рис. 2АЗ, и определим процесс г следующим образом. Иа ваданного положения Я процесс г по рождает множество всех положений, получаемых в результате поворота по часовой стрелке на прямой угол.
Рвс, 2А4 Рвс. 2ЛЗ Таким образом, г(Я) дает конфигурацию, изображенную на рис. 2.14. После применения г четыре раза, мы вернемся к положению, с которого начали, и, следовательно, замыкание в данном случае есть множество из четырех позиций. Рассмотрим теперь, что проиаойдет, если процесс определить при помощи отношения.
(В действительности вто всегда возмон«но, потому что мы можем определить подходящее отношение при помощи множества ((х, у): ра«р(х), где р — изучаемый процесс).) Для построения замыкания отношения А достаточно иметь составные отношения А, А', ..., А", ..., которые затем комбннвруются обычным теоретико-множественным путем. В д. кто, г, воз« 65 О п р е д е л е н в е. Траязигивным замыканием (или просто замыканием) отношения А на множестве называется бесконечное объединение () А"=А() А'() А'() ...11 е-» Транзитввность замыкания отношения следует, очевидно, нз его определения, однако слово «транзитивное» часто включают, чтобы подчеркнуть различие между этой и подобной ей операцией, которая вскоре будет определена. Транаитиввое замыкание отношения А обозначают А+.
П р и м е р 8.2. з. Пусть  — отношение на Р( такое, что 1« ((х, р): р х+1). Тогда Л+ ((х, у): х(р). 2. Пусть о — отношение на Я такое, что о ((х, р): х< у). Тогда о+ о, 3. Пусть р — отношение на (( такое, что р ((х, у): х«р (). Тогда р+( (х, х): х чь О) 0 р. 4. Пусть 1 — множество станций Лондонского метро и а, Ь н с — последовательные станции. Если отношение Ф на Б определено как )«' ((х, р): х является следующей за р станцией), то (а, Ь) и (Ь, с)«вФ и (а, а), (Ь, Ь)', (с, с) и (а, с)«в1»». Следовательно Ф+ ° У» ЬХБ. 1 Из этих примеров легко видеть, что замыкание отношения в общем случае не является рефлексивным.
Однако иногда удобно сделать его таквм, Это можно легко сделать. Вначале мы примем удобное допущение, что тождественное отношение на Х, 1 ((х, х): х«вХ) является нулевой степенью произвольного отношения на Х. Таким образом, А' ° 1 для любого А. Определение. РеЯлексивным замыканием А» отношения А называют множество А~ () А", е» Замыкания отношений связаны между собой очевидным соотношением Ае А+ 01. 1 Пример 8.3. Испольвуя отношения, определенные в предыдущих примерат, получаем )7е (1х р). я<р) ое ((л р).
к~у) р -р ис<о, о)), )у -.т. у Практические методы получения вамыканий отношений будут обсуждаться в гл. 6, 7. Упражнение 2 7. 1. Исаольвуя отношения В и Я упражнения 2.6, описать вамыкания следующих отношений: а) В+; б) Я+; в) В*; г) Я*; д) (Я Ю ')+; е) (Л ' В)*; ж) (У В')+. ГЛАВА 3 ФУНКЦИИ Понятие функции может быть уже известным читателю, однако в атой главе мы будем рассматривать функции как множество бинарных отношений. Собственно, будет дано определение функции и близкого к ней понятия отображения и изучены различные свойства, которыми они обладают.
Затем функции будут использованы для того, чтобы формализовать процесс вычислений и дать определение мощности множества. В заключение будут рассмотрены конкретные функции, представляющие особый интерес, и функции, которые удобно определить с помощью операторов. в 1. Функции и отображения О п р е д е л е н и е. Бинарное отношение р между множествами А и В является функцией, если из арЬ и арс следует, что Ь с; поэтому для любого хжА существует одно ужВ такое, что хру.
Можно дать определение функции следующим образом: р(х) И или р(х) (у). х Следует помнить, что если р(х) . существует (т. в. р(х)чь ю), то этот элемент единствен. Б случае, когда р(х) чь Ы, обычно опускают скобки при обозначении множества и записывают у-р(х) Функции обычно обозначают строчными латинскими буквами ~, у, Ь, ...
или в специальных случаях особыми сочетаниями, например зш, !оу, Р..... Если ~ — функция между множествами А и В, то этот факт может быть записан как !: А - В. Б дальнейшем, если хжА и х)у, мы будем обозначать зто соотношение следующим образом: Г'; х У. Это обозначение часто нспольауют для того, чтобы опи.
сать правило, определяющее функцию (если оно существует). Пример 1Л. Функция /: А ~ А, где А (-1, О, 1), определяется соотношением /: х х',// Даже когда ) не является отображением (см. ниже), мы часто будем использовать фразы типа «/ отображает х в х'». Понятия области определения и области значений в данном случае содержательны, поскольку функция является отношением, однано следует заметить, что обратная функция может не существовать. Паникер 1.2. На множестве ( — 1, О, 1) отношение /: х х является функцией, но обратной функции не существует, поскольку 1-'(1) ( — 1, 1).
в' Определение. Функция /: А- В является отображением, если ее область определения совпадает с А, т. е. йР, ° А. Функции, не являющиеся отображениями, называют частичными. Отображение на множество называют трансформацией (лреобравованием). 3 а м е ч а н и е, Часто терминология отличается от принятой в этой книге, особенно в американских книгах. Термины «фуикция» и «отображение» иногда используют как синонимы, а отображение в том смысле, как мы его определили, называют полной функцией.
Конечно, каждая функция может рассматриваться как отображение на своей области определения; иногда это полезно, когда строятся сложные функции. Как мы увидим в последующих параграфах, исследовать свойства функций легче в тех случаях, если на функцию наложить некоторые условия. Функция /: А - К называется функцией, принимающей действительные значения, а функция, область определения которой совпадает с ((, называется вещественной. Рассмотрим ограничения, которые помогут нам понять, что происходит с отдельными элементами в результате применения к ним функций. Будем заниматься классификацией функций, определенных на множествах, и предполагать, что мы имеем мало информации об втих множествах. Далее будут рассмотрены функции на множествах, где определены такие операции, как сложение.
Определение. Функция /: А - В называется сюръективной (на), если Я,-В. Это означает, что для данного б«и В имеем ) '(6)т» Ы. Функция ): А - В яв- 69 ляется иньективной, если иа аь л» «вА и /(а~) Яа») следует, что а~ а». 1 Итак, если 1: А - В и 1 сюръективна, то для любого ЬюВ имеем 1 '(Ь)«вУ(А)М. Это может быть проинтерпретировано следующим обраэом: каждая точка из В является «острым концом» по крайней мерв одной 1-стрелы, выходящей из А. Проиллюстрировать эту ситуацию достаточно трудно (исключая тривиальные случаи).
С другой стороны, наглядную характеристику инъективностн легко дать в виде ограничения или эаирета. Рис. ЗЛ Функция / не инъективна в случае, изображенном на рис. ЗЛ, а. Для сравнения на рис. 3.1, Ь иэображено зеркальное отражение, которое отличает функцию от бинарного отношения. Если 1: А - В инъективна и а ы Ж/, то а 1 '(/(а)). Далее, если Ь ж Я„т.
е. Ьон Ж „и в данном случае ~ ' — функция, то Ь 1Ц '(Ь)). Следовательно, если мы определим функцию 1«. 'Х-" Х как тождественное отображение на Х, т. е.1л. х х для всех х ж Х, тогда, если 1 инъективна, то 1' '1-1~> и 11 ' 1эт. / Используя функцию 1 иэ примера 1.2, мы видим, что / '(1(1))т»1. Это оэначает, что первое из этих тождеств в общем случае неверно, однако, как мы увидим в $2, вычисления становятся гораздо легче в случаях, когда оба тождества имеют место.
Прежде чем продолжить изложение, обсудим терминологию, объединяющую введенные выше свойства. Функция 1 биенгиена, если она сюръективна и инъективна. Биективное отображение называют биекцией. Следовательно, используя биекцию / между А н В, можно брать элементы иэ А и переходить в В посредством /, осуществляя некоторые вычисления, Переход на»ад к А осуществляется посредством 1 ', 70 Термины инъекции и сюръакции также применяются (для описания инъективного и сюръективного отображений), однако мы редко будем нх испольэовать.
У п р а ж н е н н е 3.1. 1. Какие нз укаэанных ниже отношений на множестве ( — 10, — 9, ..., О, 1, ..., 9, 101 являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией. (В ЗЛ, 1г) отношение порядка < является отношением, индуцярованным Х. В ЗЛ, 1а) — к) !х! определяется следующим обраэом: !х! х, если х>0, и!х! — х, если х~О.) а) р~ ((х, р): х уг); б) рэ ((х, у): х' у1„ в) рэ ((х, у): х — у1; г) р4 ((х, у): х ч.
у1; д) рэ - ((х, у): х э д 61; е) ре - ((х, р): х' - у); ж) рг - ((х, у): х - у'); В) рэ ((х, у); г !р!1; и) рэ ((х~ у); 1х! = !у~)~ к) рта ((х, у): у э !у! х ° Зх!1. 2. Построить функцию 1: А - А, где А (О, 11, не имеющую обратной. 3. Какие из следующих функций являются отооражен няни: а) ? на К определяется следующим образом: ((х, х~): хж В1; б) ? на К определяется следующим образом: ((хз, х): хж В1; в) 1 на В определяется следующим образом: ((х, хг): хж В1; г) 1 на В, ~: х е(п(х); д) 1 на К, ~: х 1(х; е) ( на Я, ?: х агсе1пх; ж) 1: А - У(А) определяется следующим образом: ~: х" (х)' в) (: лэ(А)- А определяется следующим образом: ((х, у): у ж х О (аИ, где а — фиксированный элемент из А? 4. Пусть 1: А - В и йч В-» С вЂ” отношения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
