6. Свойства операций над множествами:

1. А∪В=В∪А , А⋂В=В⋂А – переместительный закон (коммутативность) для операций объединения и пересечения

2. (А∪В)∪С=А∪(В∪С); (А⋂В)⋂С=А⋂(В⋂С) – сочетательный закон (ассоциативность) для операций объединения и пересечения

3. (А∪В)⋂С= (А⋂С) ∪ (В⋂С) – распределительный закон (дистрибутивность) пересечения относительно объединения множеств

4. (А⋂В)∪С=(А∪С) ⋂ (В∪С) – распределительный закон объединения относительно пересечения множеств.

5. A∪A=A; A⋂A=A – закон поглощения

6. U=∅’ ∅=U’ – т.е. универсальное и пустое множество являются дополнением друг друга.

7. Если обозначить через A_i все подмножества A₁, A₂, A₃, …A_n множества A, то будут справедливы равенства ∪. A\⋂_i A_i = ∪_i(A\A_i); A=∪_iA_i

8. Для любого множества x⊂U справедливо ¬¬x = ¬x’ = (x’)’= x

9. Для любых двух множеств x и y справедливо: если x⊂U, y<U, то, или, (x⋂y)’=x’∪y’ (x∪y)’= x’⋂y’

10. Множество А можно разбить на классы непересекающихся подмножеств A_i, если:

1. Объединение всех подмножеств совпадает с множеством А: A=∪_iA_i

2. Пересечение любых двух различных подмножеств пусто, т.е. для любых i≠j выполняется A_i⋂A_j = ∅

7. Пусть даны два множества: A={a₁,a₂,a₃…a_n}; B={b₁,b₂,b₃…b_n}, тогда пары (a_i;b_j) задают соответствия между множествами А и В, если указано правило R, по которому элементу a_i из множества А выбирают элемент b_j из множества В. Пример: A={0,1,2,3,4,5} B={0;1/2;1;1,5;2;2,5} соответствия. Пусть задано соответствие R между множествами A и B. Тогда для некоторого элемента а из А поставлено b из В, который называется образом элемента a: b=R(a), тогда элемент а будет называться прообразом b: a=R(b). Отображение одного множества на другое требует задания:

   1. Области определения

   2. Множества значений

   3. Закон и соответствие между ними.

Множество значений. Область определения. Обратное соответствие. Примеры.

8. Биекция – отображение множества А на множество В, при котором каждому элементу множества А соответствует единственный элемент множества В и наоборот. A={2,6,4} B={1,2,3} a:2

Сюрьекция – каждому элементу множества А указан единственный элемент множества В, а каждому элементу множества В можно указать хотя бы 1 элемент из А. A={2,-2,3,4} B={4,9,16} a²

Инъекция – каждому элементу множества А соответствует единственный элемент множества В, а каждому элементу множества В соответствует не более 1 прообраза из А. A={2,4,8} B={4,16,32,64}

Пусть заданы отображения f₁: A⇒B; f₂: B⇒C, тогда f:A⇒C, при котором каждому элементу множества А соответствует определенный элемент множества С, называется произведением (позицией или суперпозицией) отображения f₁ и f₂. Пример: Пусть множество А – множество людей, тогда f₁ – отображение множества А в множество А, при котором каждому человеку ставится в соответствие его мама; f₂ – отображение … папу. f₁*f₂ – бабушка по папе, f₂*f₁ – дедушка по маме, f₁*f₁ – бабушка по маме, f₂*f₂ – дедушка по папе.

Отображение множества А во множество А называется тождественным (единичным), если каждому элементу ставится в соответствие он сам.

9. Упорядоченная совокупность элементов называется кортежем, вектором или упорядоченным множеством. Элементы кортежа заключаются в угловые < > или круглые () скобки. Два кортежа A и B равны, если их компоненты попарно равны, т.е. ∀i ai=bi. Таким образом, <2, 4, a, d> и <a, d, 2, 4> - разные кортежи, хотя и состоят из одних и тех же элементов.

10. Декартовым произведением множеств А и В называют множество М, содержащее все возможные пары, в которых на первом месте стоит элемент из А, на втором – элемент из В. Формально АхВ = М, М={(ai , bj )| ai ∈A, bj ∈B}. Элементы декартова произведения являются кортежами. Пример. Пусть А={1,2,b} и B={a, b, 2}, тогда A*B={(1, a), (2, a), (b, a), (1, b), (2, b), (b, b), (1, 2), (2, 2), (b, 2)}. Если |A| =na и |B|=nb, то |A*B|=na⋅nb. Если все сомножители в произведении одинаковы, оно называется декартовой степенью: А=А¹; А*А=А²; А*А*А=А³; А*А*А...А = А^k, k>0. Результат декартова произведения не является подмножеством универсального множества. Для декартова произведения не выполняются условия коммутативности и ассоциативности.

Изоморфизм.

11. Комбинаторика - раздел математики, занимающийся подсчетами количества различных комбинаций между объектами.

Цели. Задачи. Связь с другими дисциплинами.