Презентация на тему "Дискретная математика"

Содержание

• 
  Слайд 1

  Дискретная математика

  ЛЕКЦИЯ 4 Соответствия между множествами. Отображения

• 
  Слайд 2

  Основные понятия.

  Пусть даны два множества А={а1, а2,...} и В={b1, b2,...}. Тогда пары (ai, bj) задают соответствие между множествами А и В, если указано правило R, по которому для элемента ai множества А выбирается элемент bj из множества В. Например, соответствие между элементами множеств и задает точечное множество (xi, yj) координат точек на плоскости; русско-английский словарь устанавливает соответствие значений и написаний слов русского и английского языков.

• 
  Слайд 3
  

  Пусть задано соответствие R между множествами А и В, т. е. R: (a; b), Для некоторого элемента а множества А поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента а и записывается b = R(a).

• 
  Слайд 4
  

  Тогда а = R-1(b) — прообраз элемента который обладает свойствами единственности и полноты: • каждому прообразу соответствует единственный образ; • образ должен быть полным, так же как полным должен быть и прообраз.

• 
  Слайд 5
  

  Например, если А — множество парабол, В — множество точек плоскости, R — соответствие «вершина параболы», то R(a) — точка, являющаяся вершиной параболы a, a R-1(b) состоит из всех парабол аi с вершиной в точке b

• 
  Слайд 6
  

  Образ множества А при соответствии R называется множеством значений этого соответствия и обозначается R(A), если R(A) состоит из образов всех элементов множества А. Запись: Прообраз множества В при некотором соответствии R называют областью определения этого соответствия и обозначают R-1(B), т.е. R-1 является обратным соответствием для R.

• 
  Слайд 7
  

  Для описания соответствий между множествами используют понятие отображения (функции) одного множества на другое. Функцией f , действующей из множества X в множество Y (f: X Y) называется правило или закон, по которому каждому элементу xX ставится в соответствие один или несколько yY.

• 
  Слайд 8

  Задание отображений.

  Для задания отображения необходимо указать: • множество, которое отображается (область определения данного отображения D(f)); • множество, в (на) которое отображается данная область определения (множество значений этого отображения E(f)); • закон или соответствие между этими множествами, по которому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества. Приняты записи или f: A  В.

• 
  Слайд 9
  

  Способ задания отображений в виде формул называется аналитическим. Существуют еще табличный и графический способы. Для задания отображения множеств табличным способом принято строить таблицу, в которой первую строку составляют элементы области определения (прообразы вида а), а вторую строку — их образы, т. е. элементы вида  (х) при отображении  : а  (а), где Такой способ удобен при достаточно малой мощности прообраза (не более 10).

• 
  Слайд 10
  

  Графическое представление отображения связано со стрелочными схемами (диаграммами или графами). Пример графического задания отображения множества А ={а1,а2, а3 } в В = {b1, b2, b3, b4, b5}.

• 
  Слайд 11
  

  Отображения f: А  В и g: A  В называются равными, если Отображения называются однозначными, если каждому аргументу поставлено в соответствие не более одного образа.

• 
  Слайд 12

  Виды отображений.

  Различают два основных вида однозначных отображений (функций). По мощности они делятся на сюръективные и инъективные

• 
  Слайд 13

  Инъекция

• 
  Слайд 14

  Суръекция

• 
  Слайд 15
  

  Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества А, называется взаимно-однозначным соответствием между двумя множествами, или биекцией.

• 
  Слайд 16
  

  Два множества эквивалентны, если между их элементами можно установить биективное отображение. Это обозначается следующим образом: A ~ B.

• 
  Слайд 17
  

  Пусть множество А отображается взаимно-однозначно на множество В, т.е f:АВ. Тогда отображение f -1, при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается илиf-1:ВА. Так как одному образу при биекции соответствует в точности один прообраз, обратное отображение будет определено всюду на В и однозначно (отсюда название). Для биекции принята запись:

• 
  Слайд 18
  

  Если между элементами множеств установлено взаимно-однозначное соответствие, то эти множества имеют одинаковое количество элементов. Говорят, что они равносильны, равномощны, или эквивалентны.

• 
  Слайд 19
  

  Рассмотрим примеры отображений. 1) Каждому действительному числу поставим в соответствие его квадрат. Отображение хх2 не является взаимно-однозначным соответствием, так как для любого образа у=х2 можно найти два прообраза в области определения: х = +у их = -у.

• 
  Слайд 20
  

  Рассмотрим примеры отображений. 2) Англо-русский словарь устанавливает соответствие между множествами слов английского и русского языков. Такое соответствие не является однозначным, так как каждому английскому понятию соответствуют различные варианты перевода на русский язык, и наоборот.

• 
  Слайд 21
  

  Рассмотрим примеры отображений. 3) Различные виды кодирования (азбука Морзе, представление чисел в различных системах счисления, шифрованные сообщения) являются чаще всего примерами взаимно-однозначного соответствия между множествами.

• 
  Слайд 22

  Композиция функций.

  Пусть заданы отображения f1: АВ и f2: BC. Отображение f: АC, при котором каждому элементу хА соответствует определенный элемент zС, такой, что z = f2(y), где y=f1(x), называется произведением, композицией, или суперпозицией отображений f1и f2.

• 
  Слайд 23
  

  Отображение е: А  А называется тождественным (единичным), если каждому аргументу оно ставит в соответствие себя. Очевидно, такое отображение можно задать на любом непустом множестве. Если е(х) = х, то Е(е) = D(e) = А. Очевидно, что отображение, обратное единичному, также единичное.