к лабораторной работе №2

« Отношения и функции на декартовом произведении »

1. Цель работы:

Изучение приемов и правил работы с отношениями и функциями.

2 Задачи работы:

Разработать программу реализующую операции с отношениями или функциями.

Варианты работы:

1. Существуют ли такие множества А и В такие, что отображение f:R->[-2;2],f=sin(x)-0.3x²множества A в множество B сюръективно

2. Существуют ли такие множества А и В такие, что отображение f:R->[0.1,0.3], f=tg множества A в множество B инъетивно.

3. Существуют ли такие множества А и В такие, что отображение f:R->[0.1,0.3], f=3sin множества A в множество B биективно.

4. Разработать программу которая при введении 2 множеств А и В определяет биективно ли отображение f:A->B.

5. Разработать программу которая при введении 2 множеств А и В определяет инъективно ли отображение f:A->B.

6. Разработать программу которая при введении 2 множеств А и В определяет сюръективно ли отображение f:A->B.

Примечание. Множества вводятся попарно:

Например. А В

(1,1)

(2,4) и т.д.

7. Реализовать алгоритм который при введении бинарного отношения р проверяется является ли оно транзитивным.

8. Реализовать алгоритм который при введении бинарного отношения р проверяется является ли оно рефлексивным

9. Разработать программу которая при введении отношения p частично упорядочивает его.

10. Разработать программу которая при введении отношения p преобразует его в отношение линейной упорядоченности.

11. Реализовать алгоритм который при введении бинарного отношения р проверяется является ли оно симметричным

12. Реализовать алгоритм который при введении бинарного отношения р проверяется является ли оно антисимметричным.

13. Реализовать алгоритм который при введении бинарного отношения р проверяется является ли оно антирефлексивным.

14. Разработать программу которая при введении множеств А и В находит отношение p, согласно которому a ~ b (r).

15. Разработать программу которая при введении множеств А и В находит композицию А◦В.

3. Общие положения и содержание работы:

Соответствие f =(G, А, В) называется однозначным, если для всякого элемента x Îпр₁ G существует не более одного (а может быть и вовсе ни одного) значения y Îпр₂ G. Всюду определенное и однозначное соответствие называется функцией или отображением множества А в множество В. Если А и В числовые множества, то функция называется числовой.

Элемент х Î A называется неподвижной точкой отображения, если f (x) = x.

Отображение f: A ® B называется инъективным или взаимно-однозначным отображением множества А в В, если для " х ₁ ¹ х ₂Î A Þ f (x ₁) ¹ f (x ₂). Т.е. каждый образ имеет только один прообраз. Подчеркнем, что не все элементы множества В обязаны иметь прообраз (должны быть чьими-нибудь образами).

Отображение называется сюрьективным (или сюрьекцией или отображением множества А на множество В), если f (A) = B или " y Î B $ x Î A (один или несколько) и y = f (x), т.е. все элементы множества В являются чьими-нибудь образами (имеют по крайней мере один прообраз).

Отображение называется биективным (биекцией или взаимно однозначным отображением A на B), если оно одновременно инъективно и сурьективно.

Два множества А и В называются равномощными или эквивалентными, если между их элементами можно установить взаимно-однозначное соответствие или если существует биекция А на В. Обозначение: А ~ В. Мощность – это то общее, что имеется у всех равномощных между собой множеств. Будем обозначать мощность множества А так: Р(А) или | A |.

Некоторые свойства равномощности:

1) Рефлексивность: А ~ А для любого множества А.

2) Симметричность: для любых множеств А и В, если А ~ В, то В ~ А.

3) Транзитивность: для любых множеств А, В и С, если А ~ В и В ~ С, то А ~ С.

Для доказательства каждого из этих свойств достаточно указать биекцию между множествами. Так в первом случае – это тождественное отображение А на А.

То, что два элемента a и b находятся в отношении r,записывается так: (a, b)Î r или arb, или a ~ b (r) – читается: «a находится с b в отношении r». Общая теория бинарных отношений распадается на ряд направлений, изучающих отношения, обладающие теми или иными свойствами.

Бинарное отношение r называется рефлексивным, если любой элемент множества М находится в этом отношении с самим собой, т.е. " a Î M Þ a ~ a (r).

Отношение r называется транзитивным, если " a, b, с Î M, для которых a ~ b (r) и b ~ с (r), обязательно следует, что a ~ с (r).

Отношение r называется симметричным, если из a ~ b (r) всегда Þ b ~ a (r);

Отношение r называется антисимметричным, если одновременное выполнение a ~ b (r) и b ~ a (r) возможно только в случае, когда a = b. (Заметим, что пара (a, b), удовлетворяющая данному условию, может вообще не существовать.)

Бинарное отношение r, заданное на множестве М, называется отношением эквивалентности или просто эквивалентностью, если оно рефлексивно, транзитивно и симметрично. Для обозначения этого отношения чаще используется запись a ~ b без указания r.

Бинарное отношение, заданное на множестве М и обладающее свойствами рефлексивности, транзитивности и антисимметричности, называется отношением частичной упорядоченности или просто упорядоченностью. Множество М в этом случае называется упорядоченным. Упорядоченность называется строгой, если отношение не рефлексивно. Упорядоченность называется линейной, если для любых элементов а, b Î М => либо (a, b)Î r, либо (b, a)Î r. Множество М в этом случае называется линейно–упорядоченным или цепью.

Разработанная программа позволяет вводить 2 множества и определять инъективно ли отображение f: A®B.

Рисунок 1 – Формирование множеств «А» и «В»

Рисунок 2 – Ввод элементов множеств «А» и «В»

Рисунок 3 – Вывод ответа

4 Требования к отчету:

Отчет о проделанной работе должен содержать:

– название работы, ее задачи и описание последовательности выполнения;

Отчет представить в электронном виде, к отчету прилагается программный продукт.

Контрольные вопросы:

1. Что называется отображением (функцией)? Приведите примеры.

2. Что называется бинарным отношением? Приведите примеры.

3. Какие множества называются равномощными (эквивалентными)?

4. Назовите свойства равномощности.

5. Дайте определения рефлексивного, транзитивного, симметричного, антисимметричного и антирефлексивного отношения

6. Дайте определения и приведите примеры инъективного, сюрьективного, биективного отображения

7. Что такое отношение частичной упорядоченности?

8. Что такое отношение линейной упорядоченности?

9. Что такое неподвижная точка?

Рекомендуемая литература:

Белоусов А.И. Дискретная математика: учебник для вузов / А.И. Белоусов, С.Б. Ткачев - 4-е изд., доп. - М.: МГТУ им Н.Э. Баумана, 2006. – 744 с.

Тишин В.В. Дискретная математика в примерах и задачах: учеб. пособие/ В.В. Тишин – СПб.: БВХ-Петербург, 2008. – 337 с.

Новиков Ф.А. Дискретная математика для программистов: учеб. пособие для вузов/Новиков Ф.А. –СПб.: Питер, 2004. – 302 с.