В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 3

Назовем ( л-местной функцией нэ Х з У, если ):Х -ь У. Тогда пишем д=Цхь..., х ) и говорим, что у — значение функции прн значении аргументов хь..., х . Пусть (:Х У. Функция (отображение) ) называеюя икъскгизлой (икъсьтилиым), сели длЯ любых хь хь У «з д )(х,) и у ((хз) следует, что х~ =ха (илн, иначе, из <хь д> ш( и <хь у> ек( слслует, что х, = ха). Функция (отображение) называсгся сюръсктивиой (гюръекгивиых), если длк любого элемента у ш У существует элемент хек Х такой, что д = ((х). Функция (отображение) ( называется бискгизяой (биекгив яыи), если ( одноаремскна сюръектнвна и ннъектнзна. Если существует бнективнак функция ):К У, то говорят, что г осуществляет ишшшо одиоэиачиое соотасгсгзие мсжау мнажествамн Х и У. 1З з)ример цй.

Рассмотрим три функции, отображающие множсс)во действительных чисел й во множестно действительных чисеи, (с: К-«й, с 1, 2, 3: 1) функция (~(х) е* инъептивиа, ио не сюръектввиа; 2) фуншгив (з(х) хз — х сюръективиа, но не ниъективнаг 3) функция (з(х) 2х + 1 бнективна. Композиция лвух функций ( и й есть отношение йО( (<х, н> ( существует р гансе, что х(р и рйс».

ртверждавнв 0.3. Композиция дву» функций есть функция. Ври атом, если (: Х вЂ” «У, й; У-«Я, то йО(: Х Х. Дейшвнтельнц если (х, р> шйО( и <к, а> шйОВ то существует такое и, что к)н, ийр, и существует такое о. что х(о, ойх. Поскольку ( — функшг», то и = о; поскольку й — функция, то р = х н, следовательно. й О ( — функция. Вторая часть утвержденп» очевипна. Верно также н слсцующее утверждение.

Утверждение 0.4. Композиция двух бнектизньи функций есть биектненоя фрнкцмн Уакдестееннмм отображением множества К в себя называется отображение ел: Х Х такое, что дея любого хшХ ех(х)=х. Тогда, если (:Х~У, то етО( (, (Оел=(. Пусть (-' — отношение, обратное ). Выясним, при панях условняк отношение Еь будет функцией. Его называют тогда обратной функцией или, если ( осуществляет отображение множества К ва множества У, обратным ошброишннем Утперж1шиие 0.3. Отображение (1Х-ь.

У имеет обратное отображение ( — ': У-«К гоедо с только тогда, когда ( — биекцик Если ( — биекцня, то. поскольку ( аоръектнвно, ~-' опреде. лспо на множестве У. Кроме того, ( — фунипия, та» каи если <р, хс> ев/ ' и (р, хз> ш ', тО <хь р> ш( и (кь р> ш(. а в силу пнъектнвности ( имеем х, = хь Пусть теперь отображение ( имеет обратное отображение ( ', определенное на множестве У со значениями по множестве Х.

Тогда ( сюръсктивно, поскольку любой элемент р ез У имеет прообраз кшХ. При этом ( инъектнвно, так нак если <х„ и> ш ( н <хь р> шй то <у. х~> ш/ ', <у, кз> ш( ', а по. скольку /-' — функция, то х~ Заметим, что, для того чтобы обратное отношение ( 1 было функцией, достаточно ннъектнвнасти функции 2 Поскольку функцмя есть бинарное отношение, то выполняются следующие свойства инъектнвпых функций ( и й: 1' (( ') '-( 2' (йОО ' ( 'Ой '. Если (:Х У вЂ” бнекция, то 3'. ((-'О() -ех; 4.

((О~ ') = ез. 1а Задача в унражнеянв 1. Найти Ог, Аь р '. рОр. р 'О р, р Ор ' стнопюннй а) р (<х, р> [х, у — натуральные чнсла н х делят р)1 б] р = (<х, р> )х, р — дейстаптельные числа н х+ р ф 0)г в) р (<х, р> [х, д сн [ — — ", з 1 н р > мпх). 2 2 1 2. Найтн геометрическую интерпретацию множества .фХ В, где А — множество точек отрезка [О, 1);  — множество точек квадрата с вершннамп а точках (О, 0), (О, 1), (1, 0), (1, !). 3. Доказать, что (ЛХВ)[](СХО)ш(АОС)Х(В()0).

Прн каких А, В, С, О вкзюченне молшо замсянть равснстпому ф Доказать, что для произвольных множеств А, В„С, Ог а) (А П В) Х (С(]Р) (А Х С) О (В ХО); б) (А[)В) Х С- (АХ С) О (В х С); в) (Ат,В) ХС (А Х С)~(ВХС); г) А Х (В~С) (А Х В)ц(А Х С). 5. Пусгь А ВчьИ н (А хВ) [](Вхд) .= СХО.

Доказать, что з этом случае А В С О. 6. Доказать, что чпсла бннарнык отношений нз л-элемент. аом множестве равно 2"'. 7. Пусть Х вЂ” конечное множество н отображеппе П Х-ьХ ннъектпвно. Доказать, что тогда / бпектнвно. 8. Характеристической функцпей множества А называется функцнп 1, есла хан А1 Х Кь (О, если ай]Я. Пусть известны характеркстнчесшге фупкшпг множеств А н В.

доказать чтог а) ХЛ (х) Х„(х) Хз(х]; б) Ххгц, (х) К „(х) + Х (х) — Х, (х) Х„(х); а) ХХ(х) - 1 - Х л(х): г) К„(х] Хл(х) — К л(х) . хз(х). 9. Доказать, что для любой функции [ н произвольных мне. шствА нВ: а) ((Я[)В) )(А! [][(В)1 б) )(А(]В) и[(А) Щ(В). В каком случае пключенне моагпо заменять равенствому п) )(Арт)(В) и((А~В). ра ЕпецнАЛиные БИВАРНЫе ОТНОШеНИя В и)тематике важную роль играют два вида специальньш бн. парных отнашенийг отношение эквивалентности и отношение подул~в Отнашенне р на множестве Х называется рефлексигямм. если ~для любого элемента х ш Х выполняется лрх. Очяошевце р на множестве Х иазывается симметричямм, если для любмх х, д ш Х нз хру следует урк.

Отношение р иа множестве Х иавывается траипвиеямм, если для лгсбых к, у, г ш Х из хру, ург следует «рг. Рефлексизясе. симметричиае й транзптпвиае отпошенне на мншкесгве Х называется омюивнием экеиеизгкгкогги на множестве Х. Пр р ауа 1. Отногиение равенства на множестве целых чисел есть отношение эквивалентности. а Отношение пцаобня на множестве треугольников есть отношение эквнвалевтносги.

3. Отношение х < д иа множестве действетшвных чисел не рирлекспвио, яе свмметричво, ио трапзитивна нз шом множестве. 4. Отношение сраввпмостц па модулю натурального числа л на множестве целых чисел Х:хч д(пюбл) тогла и толью тогда, ногда х — д делится на м Это отношение рефлексввно иа Х, так как для любого к шй х — х б, и, следовательно, делится иа я.

Это оигошеине симметрично, так наи если х — у делится на и. 'ш д — х делится на п. Это отношение транаитпвно, тан нак если к — у делится «а л, то для пекаторого целОго гг имеем х — у=си» а если д — я делятся иа л. то лдя некоторого целого 1г имеем у — г 1 ц Отсюда х — я (гг+сг)а„ т.

е. к — г делится нз л. б. Отношение прпиадлежвюти к одной студенческой группе на множестве студентов института — огяошение эквнвалеит. ности. 6. Нз множестве УХУ, где У вЂ” множество иатуральпых чисел, определим отношение рг<х, у>р<и, п>е:ьзв уи. Это отношение рефлексивнш <х, у> р <х, у>, так как хд = ухг снмметричног если <х, у> р <ге 'с>, то <и, о> р<» у>, так кзк иэ хо ди следует, что в иу сх; транзнтииног если <х, у> р<и, а>, <н, п>э<в, г>, то <х, у>р<в, х>, так как. перемножая левые и правые части равенств хо = ун и иг ов, после сокращения получаем хг дв.

Пусть р — отношение эквивалентности на множестве Х. Классом акаива мягкости, псрожцеииым элементом х, иазываешя палмнсжеспю множества Х состоящее из тех элементов 1З дшХ, дл» которык хрд. Класс зкэнвалентностн, порожден]гый «лене«том д обозначается через [х]г [х) (у ] д ш К н крд). Пример 0.11. 1. Отношение равенстве на множестве целых чпсел порождает слелующнс классы зюгепалснтностп: дла любого «левита хе«Е[х) (х), т. е.

«шкяый класс эквнэеленчнастн спбтонт талыш пз с«його элемента — числа х. 2. Отношенне срашшмостн по ыоаулю чпсла л ца множестве целмх чнссл 2 порождает следующие нлассы эквпвалентностпг «месте с любмм числам аш2 в этом же классе экшгввлентно. сгн содержатся эсе чксла вада а +Дл, где й — целое. Очевидно, что чнслл О, 1, 2,..., л — 1 порождают раап«чане клахы энвяэалептности, коюрые обозначим [О) (1), [2],..., [л — Ц.

Онн пааываются классами вычетов по модулю д Все остальные клас. сы эк«пвэлептностн для этого отношения совпадают с «ем«, так как любое чпсло ашй можно прелсгавпть в «пдс а=рв+ +г, где 0<г<л. 3. Для отношения прэпадлсжностн к одной студенческой группе классом эквцважнтносгн ««ляется множесио студентов ем«ой группы. 4. Класс зквнпалентностц, порожденный парой <х, д> лля отношения р нз яр«мера 0.10, п, Д определяется соотпошсннем (<х, д>] (<и, е> ]— э 1 Каждый «ласс эквивалентности э этом случае определяет одно поаожптельное рацнональное чнсао утвержден«е ОД Пусть р — оглошелпе зхеиеалггп«оши ха л«ам«атее Х. Тадп 1) если х ш Х, то х ш(х]г 2] если х, де«И п хрд, то [х]=(д] [г.

е. «ласс зкеиеашигпосги порождается люб«к сэопы заел««то«]. Дл» доказательства первой частя угэержденля достаточно аосполшолаться рафа«капа«остью опюшення ргкрх п, следовательно, хш[х]. Докажем вторую часть утверждения. Пусть ею[у]. Тогда дрх п в сплу траазнтпвцостп отношения р хрд т. е. аш[х]. Отсюда [д]ш[х]. Аналогично в сплу снмыетрпчностн р можно цокаыпь, что (х]«42) а значнт, (х]=(р). Разбиением множества Х называется совокупность попарно непересекающихся подмнож«стэ Х таюи, что каждый элемент множества Х принадлежит одному н только одному нэ эт«х подмншншчж Пример 0.12.

1. Х (1, 2, 3, 4, 5). Тогла ((1, 2), [3, 5), (4)) — разбиение множества Х. 2. Пусть Х вЂ” ыножестао студентов пист«туга. Тогда разбненнем этого множества является, например, сопонупность сту- Л«наезжих групп. !6' Утверждение 0.7. Всяяое разбиение множества Х определя.ет на Х отношение знвиеалентности р:хру тогда и только тогда, >согда х и у нринадлеясат одному подмножеству разбиения. Рефлезсивность и симметричность р очевидны.