Дополнение к занятию «операции над множествами»

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

S = A⊕B = (A\B)∪(B\A) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯

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

1. 1) A⊕B = B ⊕A — коммутативность,

2. 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,

3. 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,

4. 4) A ⊕А = ∅

5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Упорядоченное множество

Упорядоченным множеством (или кортежем) называется последовательность элементов, то есть совокупность элементов, в которой каждый элемент занимает определенное место. Сами элементы — компоненты кортежа.

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

Число элементов кортежа называется его длиной. Обозначают кортеж скобками «< >», иногда круглыми «()». А=<a₁, a₂,..., a_n>. Кортежи длины 2 называются упорядоченными парами, 3 — тройками, n-ками.

Частный случай: кортеж длины 1 — <a>

кортеж длины 0 — < > или ∧ — пустой кортеж.

Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.

Упорядоченные множества, элементами которых являются вещественные числа, будем называть векторами или точками пространства (n-мерного).

Так, кортеж <a₁, a₂> может рассматриваться как точка на плоскости или вектор, проведенный из начала координат в данную точку. Тогда компоненты a₁, a₂ — проекции вектора на оси 1 и 2.

Пр₁ <a₁, a₂> = a₁, Пр₂ <a₁, a₂> = a₂, Пр_i <a₁, a₂, a₃>= a_i, Пр₁2 <a₁, a₂, a₃>= <a₁, a₂> — двухэлементный кортеж. Проекция кортежа на пустое множество осей — пустой кортеж.

Обобщая эти понятия, будем рассматривать упорядоченное n-элементное множество вещественных чисел (a₁,..., a_n) как точку в воображаемом n–мерном пространстве (иногда называемом гиперпространством), или как n-мерный вектор. При этом компоненты n-элементного кортежа а будем рассматривать как проекции этого кортежа на соответствующие оси.

Пр_i a = a_i, i=1,2,...,n

Пр_i,j,...,l a = <a_i, a_j,..., a_l>, i=1,2,...,n

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

<a₁,..., a_m> = <b₁,..., b_n> ⇔ m = n и a₁ = b₁, b₁ = b₂,...

Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):

Пример. Слова в предложении,

A = < <a₁, a₂>, <a₁, a₃>, <a₂, a₃> >

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Формально: X*Y = {<x,y>: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

X*Y ≠ Y*X

Прямое произведение множеств X₁, X₂,..., X_n — это множество, обозначаемое X₁*X₂*...*X_n и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X₁, вторая — X₂ и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X₁*X₂*...*X_n = ∅ тогда и только тогда, когда хотя бы одно из множеств X₁, X₂,..., X_n является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M^s=M*M*...*M, M¹=M, M⁰=∧.

Обычно R — множество вещественных чисел, тогда R²=R*R — вещественная плоскость и R³=R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3,...,8}

Тогда A*B ={a₁, a₂, a₃,..., h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества a_n называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A^* = ∪Aⁱ = A¹∪A²∪A³.... При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a₁, a₂,..., a_n — конечные множества и |a₁| = m₁, |a₂|=m₂,..., |a_n|=m_n. Тогда мощность множества a₁*a₂*a₃*...*a_n равна произведению мощностей a₁, a₂,..., a_n

|a₁*a₂*...*a_n|=|a₁|*|a₂|*|a₃|*...*|a_n|= m₁*m₂*...*m_n

Следствие |a_n|=|A|ⁿ

Проекция множества.

Операция программирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которых являются кортежи одинаковой длины.

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр₂М={2,1,3}, Пр₃M={3}, Пр₄M={4,5,3}, Пр₂₄M={<2,4>,<1,5>,<3,3>}, Пр₁₃M={<1,3>,<2,3>,<3,3>}, Пр₁₅M={<1,5>,<2,5>,<1,3>}, Пр₂₅M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр₁М=Х, Пр₂М=Y

и если Q⊆Х*Y то Пр₁Q⊆Х и Пр₂Q⊆Y

Пример. V={<a,b,d>,<c,b,d>,<d,b,b>}

Пр₁V={a,c,d}

Пр₂V={b}

Пр₃V={d,b}

Пр₁2V={<a,b>,<c,b>,<d,b>}

Пр₂3V={<b,d>,<b,b>}

Пр₁3V={<a,d>,<c,d>,<d,b>}

Пусть V — множество векторов одинаковой длины S.

Пр_iV ={Пр_iv/v∈Y}, Пр_ii...ikv = { Пр_ii...ikv/v∈Y}.

Если V =A₁*A₂*...*A_n, то Пр_ii...ikV=A_i1*A_i2*...*A_ik.

В общем случае Пр_iV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

Лекция 14: Соответствие и функции

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

Соответствием между множествами А и В называется подмножество G⊆A×B.

Если (a, b) ∈ G, то говорят, что b соответствует а при соответствии G. Множество np₁G называется областью определения соответствия, множество np₂G — областью значений соответствия. Если np₁G = А, то соответствие называется всюду определенным (в противном случае соответствие называется частичным); если np₂G = В, то соответствие называется сюръективным.

Множество всех b ∈ B, соответствующих элементу а ∈ А, называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G. Если С ∈ np₁G, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D для любого D ⊆ np₂G.

Соответствие G называется функциональным (или однозначным), если образом любого элемента из np₁G является единственный элемент из np₂G. Соответствие G между А и В называется взаимно-однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из np₂G является единственный элемент из np₁G.

Так, например, англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.

Позиция на шахматной доске представляет собой взаимно-однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых ими полей.

Различные виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и другие — являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. ∈тсутствие сюръективности означает, что не всякий код имеет смысл, т. е. соответствует какому-либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам.

Если между конечными множествами А и В существует взаимно-однозначное соответствие, то |А| = |В|.

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

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами A и В, то говорят, что функция f имеет тип А → B (обозначение f: А → В). Каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Это обозначается хорошо известной записью f(а) = b. Элемент а называется аргументом функции, b — значением функции на а.

Полностью определенная функция f: А → В называется отображением А в В. Образ А при отображении f обозначается f(А). Если соответствие f при этом сюръективно, т. е. каждый элемент В имеет прообраз в A, то говорят, что имеет место отображение A на B (сюръективное отображение).

Функции f и g равны, если их область определения — одно и то же множество A и для любого а ∈ A f(a) = g(a).

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

Пусть дано соответствие G⊆A×В. Если соответствие H⊆B×А таково, что (b, a) ∈ H тогда и только тогда, когда (а, b) ∈ G, то соответствие Н называется обратным к G и обозначается G^-1. Если соответствие, обратное к функции f: А → В, является функциональным, то оно называется функцией, обратной к f, и обозначается f^-1. Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к f: A → В, требуется, чтобы каждый элемент b из области значений f имел единственный прообраз. Это в свою очередь означает, что для функции f: А → В обратная функция существует тогда и только тогда, когда f является взаимнооднозначным соответствием между своей областью определения и областью значений.

Пусть даны функции f: А → В и g: B → C. Функция h: А → С называется композицией функций f и g (обозначение f°g), если имеет место равенство h (х) = g (f(x)), где x∈A. Композиция f и g представляет собой последовательное применение функций f и g; g применяется к результату f. Часто говорят, что функция h получена подстановкой f в g. Знак ° аналогично умножению часто опускается.