Новиков Ф.А. Дискретная математика для программистов (860615), страница 12
Текст из файла (страница 12)
Тотальная функция/ : М —> М называется преобразованием над М. Функция f \ А\ х • • • х АпВназывается функцией п аргументов, или п-местной функцией. Такая функцияотображает кортеж ( a i , . . . , ап) Е А\ х • • • х Ап в элемент Ь е B,b — / ( ( a i , . . . , ап)).При записи лишние скобки обычно опускают: b = f(a\,...
,a n ). Понятие функции удобно использовать для построения самых разнообразных математическихмоделей.Примеры1. Всякому подмножеству А универсума U можно взаимно-однозначно сопоставить тотальную функцию 1д: U —> 0..1. Эта функция называется характеристической функцией подмножества и определяется следующим образом:если а е А,если а А.611.6.
ФункцииХарактеристическая функция результата операции над множествами легковыражается через характеристические функции операндов:1 лив = f max (1л, 1в),1лпв = f min (1л, 1 в),1А\вmin(U,l-lB).Всякому отношению R между А и В (R с А х В) можно взаимпо-одпозпачиосопоставить тотальную функцию 1д: А х В —> 0..1 (эта функция называетсяхарактеристической функцией отношения), полагаяDef J1, если aRb,R{a,b) = <_10, если aRb.Характеристическая функция результата операции над отношениями легковыражается через характеристические функции операндов:lR-l(a,b)= f 1я(6,а),1д=*1-1д.1.6.2. Инъекция, сюръекция и биекцияПусть / : А —> В.
Тогда функция / называется:инъективной,сюръективной,биективной,или инъекцией,или сюръекцией,или биещией,если b — f(a\) & b — /(аг) => ai = а,2~,е с л и У б е В (ЗаеА(Ь — /(а)));если она ииъективная и сюръективная.ЗАМЕЧАНИЕБиективную функцию также называют взаимно-однозначной. Введенное в подразделе 1.2.2взаимно-однозначное соответствие есть биекция.Рисунок 1.3 иллюстрирует понятия отношения, функции, инъекции, сюръекциии биекции.Понятия инъективиости, сюръективности и тотальности применимы к любымотношениям, а не только к функциям. Таким образом, получаем четыре парныхсвойства отношения / с А х В, которые для удобства запоминания можно свестив следующую таблицу.АвФункциональностьVa £ A ((a, b) 6 f & (а, с) G / = > Ь = с)ИнъективностьV6 G В ((a, Ь) G / к (с, Ь) € /ТотальностьСюръективностьVae А (3be в ((а,ь) е /))Vbe в ( 3 а е А ((а,ь) е /))а = с)62Глава 1.
Множества и отношенияОтношение, но не функция/Ав4А>оо0"4О—'Инъекция, но не сюръекция4D/—\—XСюръекция, но не инъекцияБиекцияРис. 1.3. Различные виды функцийЕсли f : А —> В — тотальная биекция, то отношение /(обратная функция) является биекцией.ТЕОРЕМА1с В х АПоскольку / — биекция, имеем (b\ = f (а) k b2 = f{a) =>• Ь\ == f(ai) k b = f(a2) =>fl! = a2) k(Vb e В (За 6 A (b = /(a)))).ДОКАЗАТЕЛЬСТВО= Ь2) k(bПокажем, что f~l — функция.
Имеем f~l =f {(b, a) \ aeAkbeBkb= /(a)} .Пусть ai = / _ 1 (Ь) k a2 = f~l{b). Тогда b = / ( a i) kb = f(a2) = > ai = a 2 .Покажем, что / - 1 — инъекция. Пусть a = / _ 1 (61) k а = / _ 1 (6г)- Тогда bi == /(a) k b2 = f ( a )bi = b2. Покажем от противного, что / - 1 — сюръекция.Пусть З а 6 А ( - 3 6 е В (а = /~ 1 (Ь))). Тогда З а € A (VbeB(а^/"1^)))-1Обозначим этот элемент ао. Имеем V6 ( а о т ^ / ( Ь ) ) =>• V6 (6 ф /(ао)) =>•а0 & fA С Аа0 & А.•.Если / : А —• В — инъективная функция, то отношение fявляется функцией (возможно, частичной), /-1: В —> А.СЛЕДСТВИЕ1.6.3. Образы и прообразыПусть / : А —• В и пусть А\ с А, В\ С 5 . Тогда множество^ ( Л 1 ) ^ { б € В | З а е Ai (6 = /(а))}1сВ х А631.6.
Функцииназывается образом множества А\ (при отображении / ) , а множествоF-^Bi)=f{aeA\3beBl(b = f(a))}называется прообразом множества В\ (при отображении / ) . Введём обозначения/А •' = Dom / , /в : = Im / . Заметим, что F является отношением между множестваfAми 2 и 2 / в :F = f { ( Л ь 5 i ) | Л1 С Л к Вх С В к S i = F ( A i ) } .ТЕОРЕМАlви F~ : 2^Если f : А —» В — функция, то F: 2fA —• 2?в (переход к образам)(переход к прообразам) — тоже функции.ДОКАЗАТЕЛЬСТВОУпражнение 1.6.•ЗАМЕЧАНИЕФактически, это означает, что функцию можно применять не только к элементам областиопределения, а и к любым её подмножествам. На практике в целях упрощения записи дляобозначения применения функции к подмножеству используют ту же самую букву, что идля применения функции к отдельному элементу.1.6.4.
Суперпозиция функцийПоскольку функции являются частным случаем отношений, для них определенакомпозиция. Композиция функций называется суперпозицией. Для обозначениясуперпозиции применяют тот же знак о, но операнды записывают в обратномпорядке: если f : А ^ В и g\ ВС, то суперпозиция функций / и g записывается так: g о f . Такой способ записи суперпозиции функций объясняется тем,что обозначение функции принято писать слева от списка аргументов:(fog)(x)^f(g(x)).ТЕОРЕМАСуперпозиция функций является функцией:/: А ^ В k д: ВС => до / : А -> С.Пусть b = (д о /)(а) и с = (до /)(а).
Тогда b = g(f{a)) и с == g(f(a)). Но / и д функции, поэтому b = с.•ДОКАЗАТЕЛЬСТВО1.6.5. Представление функций в программахПусть / : А —• В, множество А конечно и не очень велико, |Л| = п. Наиболее общим представлением такой функции является массив array [A] of В, гдеА — тип данных, значения которого представляют элементы множества Л, а В —тип данных, значения которого представляют элементы множества В.
Если среда программирования допускает массивы только с натуральными индексами, тоэлементы множества Л нумеруются (то есть Л = { a i , . . . , a n } ) и функция представляется с помощью массива array [l..n] of В. Функция нескольких аргументовпредставляется многомерным массивом.64Глава 1.
Множества и отношенияОТСТУПЛЕНИЕПредставление функции с помощью массива является эффективным по времени, поскольку реализация массивов в большинстве случаев обеспечивает вычисление значенияфункции для заданного значения аргумента (индекса) за постоянное время, пе зависящееот размера массива и значения индекса.Если множество А велико или бесконечно, то использование массивов для представления функций является неэффективным с точки зрения экономии памяти.В таком случае для представления функций используется особый вид процедур, возвращающих единственное значение для заданного значения аргумента.Обычно такие процедуры также называются «функциями». В некоторых языкахпрограммирования определения функций вводятся ключевым словом function.Многоместные функции представляются с помощью нескольких формальныхпараметров в определении функции.
Свойство функциональности обеспечивается оператором возврата, часто обозначаемым ключевым словом return, которыйпрекращает выполнение тела функции и одновременно возвращает значение.ОТСТУПЛЕНИЕВ языке программирования Фортран и в некоторых других языках вызов функции иобращение к массиву синтаксически неразличимы, что подчеркивает родственность этихпонятий.1.7. Отношения эквивалентностиРазличные встречающиеся на практике отношения могут обладать (или не обладать) теми или иными свойствами. Свойства, введенные в подразделе 1.4.6,встречаются особенно часто (потому им и даны специальные названия). Болеетого, оказывается, что некоторые устойчивые комбинации этих свойств встречаются настолько часто, что заслуживают отдельного названия и специального изучения.
Здесь рассматриваются классы отношений, обладающих определённымнабором свойств. Такое «абстрактное» изучение классов отношений обладает темпреимуществом, что, один раз установив некоторые следствия из наличия у отношения определённого набора свойств, далее эти следствия можно автоматическираспространить па все конкретные отношения, которые обладают данным набором свойств. Рассмотрение начинается отношениями эквивалентности (в этомразделе) и продолжается отношениями порядка (в следующем разделе).1.7.1. Классы эквивалентностиРефлексивное симметричное транзитивное отношение называется отношениемэквивалентности. Обычно отношение эквивалентности обозначают знаком =.ПримерыОтношения равенства чисел, равенства множеств являются отношениями эквивалентности. Отношение равномощности множеств также является отношениемэквивалентное™.
Другие, более интересные примеры отношений эквивалентности, приведены в последующих главах книги.651.7. Отношения эквивалентностиПусть = — отношение эквивалентности на множестве М и х G М. Подмножествоэлементов множества М, эквивалентных х, называется классом эквивалентностидля х:[х]= =f {у G М \ у = х} .Если отношение подразумевается, то нижний индекс у обозначения класса эквивалентности (знак отношения) обычно опускают.ЛЕММА1\/аДОКАЗАТЕЛЬСТВОЛЕММА 2([а] фа = аа = b ==>• [А] =ДОКАЗАТЕЛЬСТВОЛЕММА 3е М0).а G [а].•[6].Пусть а = Ь. Тогда х е [а]а ф Ь ==> [А] П [6] =х= ах= Ьх е[Ь].•0.О Т противного: [а] П [Ь] Ф 0Зс е М (с е [о] П [6]) = >= > c G [a] &cG [Ъ] = > c = akc = b => a = cSzc = b => a = b, противоречие.ДОКАЗАТЕЛЬСТВО•Если = — отношение эквивалентности на множестве М, то классы эквивалентности по этому отношению образуют разбиение множества М, причёмсреди элементов разбиения нет пустых; и обратно, всякое разбиение Ъ = {Bi} множества М, не содержащее пустых элементов, определяет отношение эквивалентности на множестве М, классами эквивалентности которого являются элементыразбиения.ТЕОРЕМАДОКАЗАТЕЛЬСТВО[ = > ] Построение требуемого разбиения обеспечивается следующим алгоритмом.Вход: множество М, отношение эквивалентности = на М.Выход: разбиение Ъ множества М на классы эквивалентности.Ъ : = 0 { вначале разбиение пусто }for a G М dofor В G Ъ doselect b G В { берём представителя из В )if a = b thenВ \ = В + а { пополняем существующий класс эквивалентности }next for а { переходим к рассмотрению следующего элемента из М }end ifend forЪ: = Ъ и {{a}} { вводим новый класс эквивалентности }end for66Глава 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
