Главная страница

Дискретная математика(соответствия). Дискретная математика Соответствия Основные определения


Скачать 310.97 Kb.
НазваниеДискретная математика Соответствия Основные определения
Дата25.03.2019
Размер310.97 Kb.
Формат файлаpptx
Имя файлаДискретная математика(соответствия).pptx
ТипДокументы
#71455


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

Соответствия

Основные определения

Область определения соответствия G – множество пр1G={a: (a,b)G}

Область значений соответствия G – множество пр2G={b: (a,b)G}

Основные определения

Пример 1. Экзаменационная ведомость устанавливает следующее соответствие :
  • А={Иванов, Петров, Сидоров, Конев, Синицын, Васечкин, Макарова}.

  • В={2, 3, 4, 5}.

Иванов – 4

Петров – 2

Сидоров – 3

Конев – 4

Синицын на экзамен не явился

Васечкин – 3

Макарова – 5

G  АВ, G-соответствие между студентами и оценками

Основные определения G={(Иванов, 4), (Петров, 2), (Сидоров, 3), (Конев, 4), (Васечкин, 3), (Макарова, 5)}.

Область определения соответствия G –

пр1G={Иванов, Петров, Сидоров, Конев, Васечкин, Макарова}.

Область значений соответствия G – пр2G={2, 3, 4, 5}.

Основные определения

В примере 1:
  • образом Иванова является 4;

  • образом Сидорова - 3 и т.д.

  • Прообразом 2 является Петров;

  • Прообразом 4 – Иванов, Конев.



Свойства соответствий

  • Соответствие GАВ называется всюду (полностью) определенным, если область определения совпадает с множеством А, т.е. пр1G=А. В противном случае соответствие называется частично определенным.

  • Соответствие GАВ называется сюръективным, если область значений совпадает с множеством В, т.е. пр2G=В.

  • Соответствие GАВ называется функциональным, если образом любого элемента а из области определения пр1G является единственный элемент b из области значений пр2G.

  • Соответствие GАВ называется инъективным, если прообразом любого элемента b из области значений пр2G является единственный элемент а из области определения пр1G.



Свойства соответствий



Свойства соответствий



Свойства соответствий

Определим свойства отношения в примере 1.
  • Частично определено, так как нет образа для Синицына;

  • Сюръективно, так как для каждой оценки определен прообраз;

  • Функционально, так как каждому студенту соответствует единственная оценка;

  • Неинъективно, так как оценка 4 соответствует двум студентам.



Функции и отображения

Функциональное соответствие называется функцией.

Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип АВ (обозначается f : АВ).

Каждому элементу а из области определения функция f ставит в соответствие элемент b из области значений. Это обозначается f(а)=b. Элемент а называется аргументом функции, элемент b – значение функции на а.

Функции и отображения Отображением А в В называется всюду определенная функция f : АВ (обозначается f : А В).

Отображением А на В называется всюду определенная и сюръективная функция f : АВ (обозначается f : А В).

Функции и отображения
  • тип



Взаимно-однозначное соответствие

Соответствие называется взаимно-однозначным, если оно всюду определено, сюръективно, функционально и инъективно.

Мощность множеств

Понятие мощности возникает при сравнении множеств по числу элементов.

Мощностью конечного множества является число его элементов. Множество, не являющееся конечным, называется бесконечным.

Если между множествами А и В существует взаимно-однозначное соответствие, то мощности этих множеств равны, т.е. А=В. В таком случае говорят, что множества А и В равномощны.

Мощность множеств

Этот факт позволяет:
  • установить равенство мощностей двух множеств, не вычисляя этих множеств;

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

Существование биекции между двумя эквивалентными множествами позволяет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если |А|=n, то с элементами множества А можно работать как с числами 1,2,...,n.

Счетные множества Любое множество, равномощное множеству всех натуральных чисел, называют счетным. Мощность счетного множества обозначают 0 (читается „алеф нуль").

Если некоторое множество М равномощно множеству натуральных чисел N, то между М и N можно установить взаимно однозначное соответствие (биекцию) : N М, которое называют нумерацией счетного множества М.



Счетные множества Если элемент множества М есть (n) для некоторого n N, то этот элемент множества М обозначаем через an, называя натуральное число n номером элемента аn относительно данной нумерации .

Таким образом, элементы счетного множества можно перенумеровать, записав их в виде последовательности а1, ..., аn, ...

Счетные множества Пример. Множество всех нечетных натуральных чисел счетно. Нумерацию  можно задать так: (n) = 2n-1,

N={1, 2, 3, 4, 5, 6, 7, …}

M2n-1- счетно.

M2n-1={1, 3, 5, 7, 9, 11, 13, …}

Получили:
  • M2n-1 N;

  • M2n-1=N.



Счетные множества

Пример. Множество Z всех целых чисел счетно. Расположим элементы множества целых чисел в определенном порядке:
  • N={1, 2, 3, 4, 5, 6, 7, 8, 9, …}

  • Z={0, -1, 1, -2, 2, -3, 3, -4, 4, … }



Счетные множества

Нумерацию можно было установить так:

Z={…, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, … }

Получили:
  • N  Z;

  • N=Z.



Счетные множества

Примеры счетных множеств:
  • Множество рациональных чисел счетно;

  • Множество периодических дробей счетно;

  • Множество всех натуральных чисел, делящихся на заданное число к  2, счетно.



Счетные множества

  • Докажем, что Множество пар натуральных чисел счетно.



Счетные множества

Теорема .
  • (а) Подмножество счетного множества конечно или счетно.

  • (б) Всякое бесконечное множество содержит счетное подмножество.

  • (в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.



Несчетные множества

Теорема Кантора: Множество всех действительных чисел интервала (0,1) числовой оси несчетно.

Всякое множество, эквивалентное множеству всех действительных чисел интервала (0,1), называется континуальным или множеством мощности континуума.

Примеры континуальных множеств:
  • Множество действительных,

  • Множество иррациональных чисел ;

  • Множество точек на отрезке [0,5];

  • Множество точек квадрата [1,10]×[1,10];

  • Множество (М) всех подмножеств некоторого счетного множества М

  • Множество точек пространства R3.




написать администратору сайта