Дискретная математика (Хороший учебник по дискретной математике), страница 7

Всь 1Нсь ~А~ = и =ь 31 т' с; = с =ь свВс1В... Нс Нс +,Н... Нсь 1Всь =ь =ь (а,Ь) е Вь В Ь:=Ь вЂ” Ц вЂ” 1) епб чЫ!е СЛЕДСТВИЕ 1.5.6. Ядро отношения Если В с А х  — отношение из А в В, то Во В ' называется ядром отношения В. Ядро отношения В из А в В является отношением на А. Пример Пусть задано множество М, ~М~ = и.

рассмотрим отношение Р из булеана 2м в множество целых чисел О..п = (0,1,...,и), Р С 2 х О..п, где Р: = ((Х, Ь) ! Х с Мив Й ц О..пес (Х) = Ь). Тогда ядром отношения Р является отношение равномошности. Зб Глава 1. Множества и отношения 1.5.7. Свойства отношений Пусть В с Аг. Тогда отношение В называется если Ыа Е А айа; если Ыа Е А айа; если Ы а, Ь е А аВЬ =ь Ьйа; если Ыа, Ь Е А аЯЬХс Ьйа =ь а = 6; если Ыа, Ь,с е А аНБ|гЬйс =а айс если Ы а, Ь е А а тЬ Ь =ь аВЬ Ы Ьйа. рефлексивным, ант ирефлексивным, симметричныи, антисимметричным, транзитивным, полным, или линейным, ТЕОРЕМА Пусть В С А х А — отношение на А. Тогда: ч=ь 1 С В; е=ь В= В '; 1. В рефлексивно 2.

В симметрично 3. В транзитивно 4, В антисимметрично 5. В антирефлексивно Ь. В полно 4ю=Ф ВОВСЯ; е=ь ВОВ г С1; Ф-= » НОХ=И1 е — Ф В11111Я 1 ХХ ДокАЭАтял ьствО Используя определения свойств отношений, имеем: 1. =~: Ы а Е А аВа =ь Ыа Е А (а, а) Е В ==Ф 1 С В. 1. е=: 1 С В =ь Ыа (а, а) Е В =Ф Ыа айа, 2. =ь: (Ы а, Ь Е А аВЬ =ь 6йа) =~ (Ыа, Ь Е А (а, Ь) Е В ==а (Ь, а) Е В), ((а,Ь)ей=(Ь,а)ЕВ ~)==а(ВСВ гагй гСВ)=ай=В г. 2. е=: В = В г =ь Ыа,Ь е А ((а,Ь) Е В =ь (а,Ь) Е Я т Хг(а,Ь) Е В 1 =ь =Ь (а, Ь) Е В), ((а, Ь) Е Н = (Б, а) Е В ~) =Ь =ь ((а, Ь) Е В =~ (Ь, а) Е В) =ь (Ы а, Ь Е А аВЬ =ь Ьйа). 3. ииь: Ыа, Ь, с айЬ 4с Ьйс =о айс; аВ о ВЬ = 3 с Е А айс ХссйЪ =ь =Ф аВЬ=Ф ВоЯС В. 3.

е==: Вой С В =ь (Ыа, Ь Е А (а,6) Е НоВ =ь (а,6) Е В)=ь =ь (айсег сНЬ =Ф аНЬ). 4. =о: От противного. В О Н ' ф Х =ь 3 а ~ Ь аВЬ Хс ай гЬ =ь =ь д а те 6 ай6 8г Ьйа. 4. ч=г В П В г С Х =ь (аВЬХг ай 'Ь =ь а = Ь) =ь (аВЬ 4с ЬВа =ь а = Ь). 5. =ь: От противного. Н О 1 ф И =о (За Е А айа Хса1а) = (3а Е А айа) = Ыа Е А айа. 5.г==: ВПХ=ш=ь ЗаеАайа=ьЫаеА айа. 37 1.б. Отношения 6.

=о: (Уа, Ь Е А а ~ Ь =ь аНЬтгЬНа) =~ [а ф Ь ~ (а, Ь) Е В1.гВ т), [а = Ь =ь =ь (а, Ь) Е Х) =ь [т а, Ь Е А (а, Ь) Е В1г10 В ~) =ь ХХ С' В1г 11гВ т =о=о =о ХХ = В1.г10В т. 6, г=: В 1г 1 О В г = ХХ =ь (а = Ь й(а, Ь) Е 1 и а ~ Ь й(а, Ь) Е В и В т) =о =ь [а = Ьй(а,б) Е 1Ч(а фЬ=~ (а,б) Е ВЧ(а,б) Е В ~)) =~ =о (а ф Ь =о аВЬ ч ЬВа). П 1.5.8. Представление отношений в ЭВМ Пусть В с АЯ и ]А] = тг. Перенумеруем элементы множества А. Тогда отношение В можно представить матрицей В: аггау [1 ..и, 1..о] оХ 0..1, где ) 1, если тйг, (О,. если гйгб Матрица отношения В обозначается [В].

ТЕОРЕМА ~КЯЯ = ~УЯ х [ ВЯ, гг)е $Я х ЯД) [г,,т]: = 1Х [Вг ] [т Ь] й [Йз ] р, у] Доказательство Пусть (а,б) Е В„оВя, Тогда 3 с Е А аВ,сй сНаб =ь '[Йг] [а, с] = 1й[.йЯ [с, Ь] = 1 ь =ь ([ВДь [а, с] йЯЯ [с, Ь]) = 1 =~ ~/ г[7Я [а, Ь] й~ ХЯ [Ь, Ь]) ='1. ',ь=т и, следовательно, СНг~ х [Ва]) [а,Ь) =1. Пусть теперь (а,Ь) ф Вг о Нг. Тогда Все А аН,сйсНгб=о'т'сЕ А (аНдсйсйаб) =ь =Ь 1гс Е А аВгс М - сНгЬ =Ь Чс Е А Я ] [а, с] = 0 Ч [БЯ [с, Ь] = 0 =Ь =ь Чс Е А (~В~ [а,с] й[ХЯ [с Ь]) = 0 =~ ( ~/ [Нг) [а,Ь]й[ЕЯ [Ь Ь]] = 0 йг l и, следовательно, ЯЯ х[г Я) [а,б) = О.

СЛЕДСТВИЕ [В ]=]В] ТЕОРЕМА Я ~7ЙЯ = ((ВтЯЯ) где ([ЯЯ ~г']Я [т',у]: =[Нг) [т, Я тг(НЯ [т',1]. зв Глава 1. Множетвв и отношения доказатвльство Пусть (а, Ь) Е Вг 0 йз. Тогда айг Ь '«' айз6 =» ~7Я [а, Ь[ = 1 и Я, 1 [а, Ь[ = 1 =» ~ЕЯ [а, Ь[ у ~ ХЯ [а, Ь[ =» =о ЯЯ'гг'[Я [а,Ь[ = 1. Пусть теперь (а, Ь) К Вг 1.1 йа. Тогда айгЬ 8с . айаЬ =» ~ ЕЯ [а, Ь[ = О «с ~ЯД~ [а, Ь[ = О =» =~ ([ВД гЯ [а,Ь[=О.

П 1.6. Функции Понятие «функции» является одним из основополагающих в математике. В данном случае подразумеваются прежде всего функции, отображающие одно конечное множество объектов в другое конечное множество. Мы избегаем использования термина «отображение» и предпочитаем слово «фуикция» в расчете на постоянное сопоставление читателем математического понятия функции с понятием функции в языках программирования. 1.6.1. Определения Пусть | — отношение из А в В, такое что ч а (а, Ь) е 1 Мг(а, с) н,г ==» Ь = с. Такое свойство отношения называется однозначностью, или функциональностью, а само отношение называется функцией из А в В и обозначается следующим образом: У: А -» В или А — + В. Если Г": А -+ В, то обычно используется нрефиксная форма записи: Ь = г'(а): =(а,Ь) Е 1.

Если Ь = Г (а), то а называют аргументом, а Ь вЂ” значением функции. ЗАМЕЧАНИЕ Вообще, всякому отношению В из А в В (В С А х В) можно сопоставить (тотвльную) функцию В: А х В -+ 0..1 (эта функция называется характеристической функцией отношения), полагая (1, если аВЬ, В(а,Ь):= ~0, если аВЬ. ьб. Функции Пусть г': А -ь В, тогда область определения функции: Гл . = (а Е А ~ 3 Ь Е В Ь = )'(а)); область значений функции: Гп . '= (6 Е В ~ 3а Е А Ь = г(а)), Ксли Ул = А, то функция называется тотальной, а если гл ф А — частичной, Сужением функции у: А -+ В на множество М С А называется функция Дм, определяемая следуюшим образом: ДМ: = ((а, 6) ! (а, б) Е У й а Е М) .

Для тотальной функции Г = Д~,. Функция У: А1 х " х А„-+ В называется функцией и ареументов, или и-мест- ной функцией, 1.6.2. Инъекция, сюръекция и биекция Пусть |: А -+ В. Тогда функция г" называется; если Ь = )(аг) й Ь = 1(аг) =ь аг = аг,' если убЕВзаЕАЬ=)(а); если она инъективная и сюръективная. иньективной, сюрьеюпивной, биективной, ЗАМЕЧАНИЕ Биективиую функцию также называют вэвииновднозначной рис. 1.2 иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции. ТЕОРЕМА Если Г': А -ь  — тотальная биекция (7л = А), то отношение г е В х А (обратная функция) является биекцией. Доказательство Поскольку У вЂ” биекцня, имеем (Ь, = Яа) й(~ = Г(а) =ь Ь, = Ьг) й й(Ь = У(аг) йЬ = Х(аг) =о аг = аг) й(ЧЬ Е В За Е А Ь = )'(а)). Покажем, что г ' — функция. у г: = ((Ь, а) ! а Е А й Ь Е В й 6 = Да)) .

Пусть а, = у '(6) йаз = Г г(Ь). Тогда Ь = Яаг) йб = У(аг) =ь аг = аг. Покажем, что,1 ' — инъекция. Пусть а = Г '(Ьг)йа = У '(Ьг). Тогда 6| = = Да) й Ьг = Да) =ь Ьг = Ьг. Покажем от противного, что г ' — сюръекцня. Пусть За е А ЗЬ е В а = г '(6). Тогда За е А 76 е В а ф У '(Ь). Обозначим этот злемент ао. Имеем л'6 ао ~ г '(Ь) =о 'ч'Ь Ь Р' у(ав) => ао ф Ул с А =ь =ьаз ЕА П ЬО Глава 1.

Мнодкества и отношения Инъекция, но не сюръекция Отношение, но не функция Сюръекция, но не инъекция Биекция Рио. 1.2. Различные виды функций 1.6.3. Индуцироаанная функция Пусть Г: А -+ В и пусть Ад С А, Вд с В, Тогда множество Г(Ад):=(Ь Б В / За Б Ад Ь Да)) называется образом множества Ад, а множество Г (Вд): =(а Б А ~ ЗЬ Б Вд Ь = ~(а)) прообразом множества Вд. Заметим, что Г является отношением из множества 2т* в множество 2д»: Г: = ((Ад, Вд) ! Ад С Ай В С В $ В = Г(Ад)) ТЕОРЕМА Если Г': А + В функция, то Г: 2д" -+ 2т» и Г ' 2д» + 2ра тоже функции.

ЗАМЕЧАНИЕ Р называется индуяирееанной функцией, а Г ' — переходом к прообразам 41 1.7. Отношения эквивалентности 1.6.4. Представление функций в ЭВМ Пусть Х: А -+ В, множество А конечно и не очень велико, ~А~ = н. Наиболее общим представлением такой функции является массив штау [А1 ог" В, где А — тип данных, значения которого представляют элементы множества А, а В— тип данных, значения которого представляют элементы множества В. Если среда программирования допускает массивы только с натуральными индексами, то элементы множества А нумеруются (то есть А = 1ам..., а„)) и функция представляется с помощью массива апау [1..п] оГ В.

Функция нескольких аргументов представляется многомерным массивом. ОТСТУПЛЕНИЕ Представление функции с помощью массива является эффективным по времени, поскольку реализация массивов в большинстве случаев обеспечивает получение значения эа постоянное время, не зависящее от размера массива и значения Индекса. Если множество А велико илн бесконечно, то использование массивов для представления функций является неэффективным с точки зрения экономии памяти.

В таком случае для представления функций используется особый вид процедур, возвращающих единственное значение для заданного значения аргумента. Обычно такие процедуры также называются «функциями». В некоторых языках программирования определения функций вводятся ключевым словом йшсвоп. Многоместные функции представляются с помощью нескольких формальных параметров в определении функции. Свойство функциональности обеспечивается оператором возврата, часто обозначаемым ключевым словом геГцгп, который прекращает выполнение тела функции и одновременно возвращает значение.

ОТСТУПЛЕНИЕ- В языке программирования Фортран и некоторых других языках вызов функции и обращсние к массиву синтаксически неотличимы, что подчеркивает родственность этих понятий. 1.7. Отношения эквивалентности Различные встречающиеся на практике отношения могут обладать (или не обладать) теми или иными свойствами. Свойства„введенные в подразделе 1,5,7, встречаются особенно часто (потому им и даны специальные названия). Более того, оказывается, что некоторые устойчивые комбинации этих свойств встречаются настолько часто, что заслуживают отдельного названия и специального изучения.