Спирина, М.С. Дискретная математика

Задание отображений. Для описания соответствий между мно­ жествами используют понятие отображения (функции) одного множества на другое. Для задания отображения необходимо указать: • множество, которое отображается (область определения дан­ ного отображения, часто обозначается / ) ( / ) ) ; • множество, в (на) которое отображается данная область оп ­ ределения (множество значений этого отображения, часто обозна­ чается £ ( / ) ) ; • закон или соответствие между этими множествами, по кото­ рому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества. Приняты за­ писи А — -— >В или / : А -» В. Везде при записи/ : А -э В будем подразумевать, что отображе­ ние / определено всюду на А, т.е. А — полный прообраз отображе­ ния f хотя для В такого свойства полноты подразумевать не будем. Запись ДА ) означает, что это множество состоит из образов всех элементов множества А: Д А ) ={Да)\а е А}. Очевидно, что ДА ) с В. Далее будем иметь дело в основном с однозначными отображени­ ями, где каждому аргументу поставлено в соответствие не более одного образа. Способ задания отображений в виде формул называется ана­ литическим. Существуют также табличный и графический спосо­ бы задания. Для задания отображения множеств табличным способом при­ нято строить таблицу, в которой первую строку составляют эле­ менты области определения (прообразы вида а), а вторую стро­ ку —их образы, т. е. элементы вида у(х) при отображении у а - » у(а), где а е А (табл. 1.2). Такой способ удобен при достаточно малой мощности прообраза (не более 10). Но все же иногда такой способ задания функции является единственно возможным. Например, публикация в газете многотысячной армии победителей лотереи: аргументом является лотерейный номер, образом — приз. Графическое представление отображения связано со стрелочны­ ми схемами (диаграммами или графами), которые подробно рас­ сматриваются в гл. 2. На рис. 1.4 показан пример графического зада­ ния отображения множества А - {ах, а2, аг) в В = {Ьх, Ь2, Ь2, £4, 6 5}. Т а б л и ц а 1.2 Табличное задание отображения X а\ а2 ... ап y W Y(ai) У(а2) У(а„) 22