🗊Презентация Декартово произведение

Тема: Декарово произведение множеств

Повторение материала

Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком. Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком. Если множество не содержит элементов, обладающих данным признаком, то оно называется пустым и обозначается . Равными называют два множества A и B, состоящие из одинаковых элементов: . Число элементов множества A называется мощностью множества и обозначается или .

Множество, элементами которого являются подмножества множества М, называется семейством множества М или булеаном этого множества и обозначается В(М). Множество, элементами которого являются подмножества множества М, называется семейством множества М или булеаном этого множества и обозначается В(М). Мощность булеана множества М вычисляется по формуле , где n – это мощность множества М. Пример.

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

Примеры задания множества Множество всех чисел, являющихся неотрицательными степенями числа 2 можно задать: а) перечислением элементов: ; б) указанием характеристического свойства: ; в) с помощью порождающей процедуры по индуктивным правилам: ; если , то .

1.2. Основные операции над множествами Суммой или объединением двух множеств Х и Y называется множество, состоящее из элементов, входящих или во множество Х, или во множество Y, а может в оба множества одновременно (рис. 1.2). Обозначение:

Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х, и во множество Y (рис. 1.3). Обозначение: Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х, и во множество Y (рис. 1.3). Обозначение: Разностью множеств X и Y называется множество Z, содержащее все элементы множества X, не содержащиеся в Y (рис. 1.4); эта разность обозначается

Дополнением множества до универсального множества U (рис. 1.5) является множество Дополнением множества до универсального множества U (рис. 1.5) является множество

Симметрической разностью множеств X и Y называется множество Z, содержащее либо элементы множества X, либо элементы множества Y, но не те и другие одновременно (рис. 1.6); эта разность обозначается Х Y. Симметрической разностью множеств X и Y называется множество Z, содержащее либо элементы множества X, либо элементы множества Y, но не те и другие одновременно (рис. 1.6); эта разность обозначается Х Y. =

Вместо выражения Вместо выражения «любое х из множества Х» можно писать , где перевёрнутая латинская буква А взята от начала английского слова Any – любой. Вместо выражения «существует элемент х из множества Х» кратко пишут: , где перевёрнутая латинская буква Е является начальной в английском слове Existence – существование.

Множество A можно разбить на классы (непересекающиеся подмножества) Ai, если: Множество A можно разбить на классы (непересекающиеся подмножества) Ai, если: объединение всех подмножеств совпадает с множеством A: ; пересечение любых двух различных подмножеств пусто, т.е. для любых выполняется .

Для операций над множествами справедливы следующие тождества: Для операций над множествами справедливы следующие тождества: законы коммутативности объединения и пересечения законы ассоциативности объединения и пересечения

законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения законы поглощения законы склеивания законы Порецкого Операция имеет преимущество перед операцией . Скобки - для наглядности.

законы идемпотентности объединения и пересечения законы идемпотентности объединения и пересечения законы действия с универсальным (U) и пустым (  ) множествами законы де Моргана закон двойного дополнения

План Декартово произведение множеств. Отношения. Бинарные отношения и их свойства. Соответствие между множествами.

В начальных классах ученики решают задачу: используя цифры 1, 2, 3 образовать всевозможные двузначные числа. Путем перебора дети получают: 11 12 13 21 22 23 31 32 33

Запись каждого числа состоит из двух цифр, причем существенен порядок их следования. Например, из цифр 1, 2 образованы числа 12 и 21. В том случае, когда важен порядок следования элементов множества, в математике говорят об упорядоченных наборах элементов. В данной задаче – упорядоченные пары (а; b), образованные из элементов а и b. Это (1; 2), (1; 3), (1; 4) и т.д. Первый элемент а называют первой координатой пары, элемент b – второй.

Рассмотрим другой пример. Пусть А={1, 2, 3}, B={4, 5}. Образуем всевозможные пары (а;b) Получим некоторое новое множество {(1; 5), (1; 4), (2; 4), (2; 5), (3; 4), (3; 5)}, элементами которого являются упорядоченные пары чисел. Это новое множество называют декартовым произведением множеств А и В.

2. Понятие соответствия АхВ: Соответствие — это множество всех пар, в котором первый элемент принадлежит А, а второй В.

Проекция: AxBxCx...xM Если число сомножеств равно n, то это множество векторов длины n, в котором 1-й элемент принадлежит А, 2-й элемент принадлежит B и т.д. Проекция Pri(a1, a2… an) = ai

Соответствие Соответствием называется некое подмножество прямого произведения АхВ

Соответствия между множествами. Отображения Пары задают соответствие между множествами A и B, если указано правило R, по которому для элемента множества A выбирается элемент из множества B. Пусть для некоторого элемента a множества A поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента a и записывается . Тогда - прообраз элемента .

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

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

При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается. При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается. Однозначным называется отображение, где каждому аргументу поставлено в соответствие не более одного образа. Отображения можно задавать: а) аналитически ( с помощью формул); б) графически ( с помощью стрелочных схем); в) с помощью таблиц.

Классификация отображений по мощности На множество «сюръекция»; На множество «биекция»; Во множество «инъекция».

На множество - «сюръекция» Соответствие. при котором каждому элементу множества А указан единственный элемент множества В, а каждому элементу множества В можно указать хотя бы один элемент множества А, называется отображением множества А на множество В

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

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

Пусть множество А отображается взаимно-однозначно на множество В, т.е. . Тогда отображение , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или . Пусть множество А отображается взаимно-однозначно на множество В, т.е. . Тогда отображение , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или . Если между элементами множеств установлено взаимнооднозначное соответствие, то эти множества равносильны, равномощны, или эквивалентны.

Кортежи. Декартовы произведения Кортежем длины n из элементов множества А называется упорядоченная последовательность элементов этого множества. Кортежи и называются равными, если они имеют одинаковую длину и их элементы с одинаковыми номерами совпадают, т. е. = , если и для

В отличие от элементов множества элементы кортежа могут совпадать. В отличие от элементов множества элементы кортежа могут совпадать. Например, в прямоугольной системе координат координаты точек являются кортежами. Операция, с помощью которой из двух кортежей длиной k и m можно составить новый кортеж длиной k + m, в котором сначала идут подряд элементы первого кортежа, а затем – элементы второго кортежа, называется соединением кортежей.

Существуют кортежи, элементы которых являются только нулями или единицами. Существуют кортежи, элементы которых являются только нулями или единицами. Кортеж из нулей и единиц можно рассматривать как двоичное представление натурального числа. Кортеж, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин, причём память может содержать числа, тексты, команды и т.д. Кортежи используются в штрих-кодах для сообщения нужной информации о характеристике объекта (белая полоска определённой ширины – 0, чёрная -1).

Декартово произведение Декартовым (прямым) произведением множеств называется множество , состоящее из всех кортежей длины n, в которых , где Пример. , , . Если , то пишут . называют n-й декартовой степенью множества А.

Отношения. Бинарные отношения и их свойства Подмножество называется n-местным отношением R на непустом множестве М. При n=2 отношение R называется бинарным. Свойства бинарных отношений: рефлексивность: антирефлексивность:

симметричность: симметричность: антисимметричность: асимметричность:

транзитивность: транзитивность: антитранзитивность: связность:

Каждое конкретное отношение может обладать или не обладать указанным свойством. Каждое конкретное отношение может обладать или не обладать указанным свойством. Примеры рефлексивных отношений: «быть не больше»; «быть делителем» на множестве N; «быть коллинеарным» на множестве векторов; Примеры антирефлексивных отношений: «быть больше»; «быть младше»; «быть перпендикулярной» на множестве прямых; Примеры симметричных отношений: «быть перпендикулярным»; «быть равным»; «быть параллельным»;

Примеры антисимметричных отношений: Примеры антисимметричных отношений: «быть меньше или равным»; «быть делителем»; «быть подмножеством»; Примеры асимметричных отношений; «быть больше»; «быть меньше»; «быть отцом»; Примеры транзитивных отношений: «быть больше»; «быть меньше»; «быть равным»; Примеры антитранзитивных отношений: «быть перпендикулярным» на множестве прямых плоскости; «быть сыном»; «жить этажом выше» для жильцов дома.

Примеры отношений связности: Примеры отношений связности: «быть больше», «быть меньше» на множестве N, R; «быть больше или равным», «быть меньше или равным» на множестве обыкновенных дробей. Примеры отношений эквивалентности: Отношение «быть равным», «иметь один и тот же остаток от деления на конкретное число»

Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности. Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности. На множестве обыкновенных дробей все классы эквивалентности по отношению равенства состоят из дробей, равных по своей величине. На множестве треугольников все классы эквивалентности по отношению подобия состоят из треугольников, подобных между собой.

Отношение эквивалентности – частный случай отношения толерантности. Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они рефлексивны, симметричны, но не транзитивны. Отношение «иметь непустое пересечение» для множеств – отношение толерантности.

Множество М, которое обладает отношением порядка, называется упорядоченным.

Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение. Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение. Пример. Отношения «больше» и «меньше» на множестве действительных чисел. Отношение называется отношением частичного порядка, если сравнимы не все элементы множества, на котором задано это отношение. Пример. Отношение «быть подмножеством» на множестве В(U) (булеан).