ТЕОРИЯ МНОЖЕСТВ

Определения

1. Множество A – совокупность элементов, объединённых каким-нибудь общим свойством.

2. xA – элемент x принадлежит множеству A.

3. xA – элемент x не принадлежит множеству A.

4.  – пустое множество.

5. B является подмножеством A, BA  (xB  xA), т.е. каждый элемент xB обладает свойством xA.

6.  , т.е.  является подмножеством любого множества.

7. Множества A и B равны, A=B  (  ).

8. B является строгим подмножеством A, BA  (BA  BA).

9. B является собственным подмножеством A  (BA  BA  B).

10. Операции над множествами:

- объединение множеств A и B:

= { x : x или xB}

- пересечение множеств A и B:

 = { x : x и xB}

- разность множеств A и B:

 \ B = { x : x и xB }

- симметрическая разность множеств A и B:

B = (A \ B)(B \ A)

- дополнение множества A относительно U, AU:

= U \ A

Следует обратить внимание:

1. При доказательстве включения AB использовать следующую схему доказательства:

«Пусть x, тогда ..., значит xB. Следовательно, AB.»

либо использовать элементарные соотношения типа:

(1)   A,   B

(2) A  AB, B  AB

(3) A \ B  

(4) A  B и B  C  A  C

и т.д.

2. При доказательстве равенства двух множеств нужно проверять два включения (см. определение равенства).

3. Правильно пользоваться отрицанием условий:

x  x и xB

x  x или xB

x \ B  x или xB

Примеры решения задач

1. Доказать равенство множеств:  = (B \ A).

Решение.

Докажем, что   (B \ A).

Пусть xAB, тогда xA или xВ.

Если xA, то по формуле (2) x(B \ A).

Если xA и xВ, то по определению разности множеств x(B \ A). По формуле (2) x(B \ A).

Докажем, что   (B \ A).

Пусть x(B \ A), тогда xA или x(B \ A).

Если xA, то по формуле (2) xB.

Если x(B \ A), то по определению разности множеств xB и xA. Так как xB, то по формуле (2) xB.

2. Доказать: ABC  AB и AC

Решение.

Докажем, что ABC  AB и AC.

Способ 1.

Чтобы доказать, что AB и AC, возьмем x. Так как ABC, то из x следует, что xB и xC. Значит, одновременно выполняются (x и xB) и (x и xC). Поэтому AB и AC.

Способ 2.

Учитывая соотношение (1) имеем: ABCB и ABCС. Отсюда по транзитивности получаем: AB и AC.

Докажем, что ABC  AB и AC.

Чтобы доказать, что ABC, возьмем x. Так как AB и AC, то из x следует, что xB и xC. По определению пересечения множеств получаем, что x BC.

3. Существуют ли такие множества А, В и С, что   , С = , () \ С = ?

Если существуют, то привести пример. Если не существуют, то доказать это.

Решение.

Докажем от противного, что таких множеств не существует.

Предположим, что существуют множества А, В и С, удовлетворяющие условию задачи. Так как   , то существует x, то есть x и xB. Поскольку x и по условию С = , то xС. Так как xС и x, то по определению разности множеств x() \ С. Значит, () \ С  , что противоречит условию задачи. Следовательно, таких множеств не существует.

4. Доказать равенство множеств А \ (А \ В) = АВ.

Решение.

xА \ (А \ В) 

xА и x А \ В 

xА и (xА или xВ) 

xА и xВ 

xАВ.

Задачи для самостоятельного решения:

1. Доказать: ABС  AС и BС.

2. A(BC) = (AB)(AC).

3. A (BC) = (A B)(A C).

4. Законы де Моргана для AU, BU:

(a)=.

(b)=.

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ

Определения

1. Мощность множества B – это число его элементов, обозначается |B|.

2. Мощность множества всех подмножеств множества A равна: |P(A)| = 2^|A|.

3. Декартово произведение множеств A и B: AB = { (x, y) : xA и yB}.

4. Мощность декартова произведения множеств A и B равна: |AB| = |A||B|.

Пример 1.

Пусть A={1, 2, 3}, B={a, b}. Тогда декартовы произведения:

AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) },

BA = { (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }.

Видно, что AB  BA.

Мощности: |AB| = |BA| = 32=6.

Пример 2.

Пусть A=[-1, 2], B=[1, 3] – отрезки прямых. Тогда декартово произведение AB – это все точки (пары координат) прямоугольника:

Примеры решения задач

1. Доказать равенство множеств: (B)С=(AC)  (BC)

Решение.

Докажем, что (B)С(AC)  (BC).

Пусть z(AB)С, тогда z=(x, y), где xAB и yС. Значит, xA или xВ. То есть xA и yС или xВ и yС. Поэтому zAC или zBC. По определению объединения z(AC)  (BC).

Докажем, что (B)С  (AC)  (BC).

Пусть z(AC)(BC), тогда zAC или zBC. Так как z=(x, y), то xA, yС или xB, yС. Значит, xA или xВ при yС. Поэтому xAB и yС. По определению декартова произведения z(B)С.

БИНАРНЫЕ ОТНОШЕНИЯ, ФУНКЦИИ, ПОРЯДОК.

Определения

1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.

2. Если А=В, то R – это бинарное отношение на A.

3. Обозначение: (x, y)R  xRy.

4. Область определения бинарного отношения R – это множество _R = {x : существует y такое, что (x, y)R}.

5. Область значений бинарного отношения R – это множество _R = {y : существует x такое, что (x, y)R}.

6. Дополнение бинарного отношения R между элементами А и В – это множество R = (AB) \ R.

7. Обратное отношение для бинарного отношения R – это множество R^1 = {(y, x) : (x, y)R}.

8. Произведение отношений R₁AB и R₂BC – это отношение R₁  R₂ = {(x, y) : существует zB такое, что (x, z)R₁ и (z, y)R₂}.

9. Отношение f называется функцией из А в В, если выполняется два условия:

а) _f = А, _f  В

б) для всех x, y₁, y₂ из того, что (x, y₁)f и (x, y₂)f следует y₁=y₂.

10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться _f = А, _f = В.

11. Обозначение: (x, y)f  y = f(x).

12. Тождественная функция i_A: AA определяется так: i_A(x) = x.

13. Функция f называется 1-1-функцией, если для любых x₁, x₂, y из того, что y = f(x₁) и y = f(x₂) следует x₁=x₂.

14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если _f = А, _f = В и f является 1-1-функцией.

15. Свойства бинарного отношения R на множестве А:

- рефлексивность: (x, x)R для всех xA.

- иррефлексивность: (x, x)R для всех xA.

- симметричность: (x, y)R  (y, x)R.

- антисимметричность: (x, y)R и (y, x)R  x=y.

- транзитивность: (x, y)R и (y, z)R  (x, z)R.

- дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.

16. Множества А₁, A₂, ..., А_r из Р(А) образуют разбиение множества А, если

• А_i  , i = 1, ..., r,

• A = A₁A₂...A_r,

• A_iA_j = , i  j.

Подмножества А_i , i = 1, ..., r, называются блоками разбиения.

17. Эквивалентность на множестве А – это рефлексивное, транзитивное и симметричное отношение на А.

18. Класс эквивалентности элемента x по эквивалентности R – это множество [x]_R={y : (x, y)R}.

19. Фактор множество A по R – это множество классов эквивалентности элементов множества А. Обозначение: A/R.

20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.

21. Предпорядок на множестве A – это рефлексивное и транзитивное отношение на А.

22. Частичный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А.

23. Линейный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пример 1.

Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R – это бинарное отношение на множествах A и B.

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R – это множество _R = {1, 2}  {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.

Пример 2.

Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.

Примеры решения задач

1. Найти _R, _R, R^1, RR, RR^1, R^1R для R = {(x, y) | x, y  D и x+y0}.

Решение.

Е сли (x, y)R, то x и y пробегают все действительные числа. Поэтому _R = _R = D.

Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R^1=R.

Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR^1 = R^1R = D².

2. Для каких бинарных отношений R справедливо R^1= R?

Решение.

Пусть RAB. Возможны два случая:

1. AB. Возьмём xAB. Тогда (x, x)R  (x, x)R^1  (x, x)R  (x, x)(AB) \ R  (x, x)R. Противоречие.

2. AB=. Так как R^1BA, а RAB, то R^1= R= . Из R^1 =  следует, что R = . Из R =  следует, что R=AB. Противоречие.

Поэтому если A и B, то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R  (x–y) – рациональное число. Доказать, что R есть эквивалентность.

Решение.

Рефлексивность:

Для любого xD x-x=0 – рациональное число. Потому (x, x)R.

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

Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- – рациональное число. Поэтому  (y, x)R.

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

Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + – рациональное число. Поэтому (x, z)R.

Следовательно, R – это эквивалентность.

4. Разбиение плоскости D² состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

Решение.

а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b – любое действительное число.

b) две точки (x₁,y₁) и (x₂,y₂) эквивалентны, если (целая часть x₁ равна целой части x₂) и (целая часть y₁ равна целой части y₂).

с) решить самостоятельно.

Задачи для самостоятельного решения:

1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.

2. Пусть A и B – конечные множества, состоящие из m и n элементов соответственно.

1. Сколько существует бинарных отношений между элементами множеств A и B?

2. Сколько имеется функций из A в B?

3. Сколько имеется 1-1 функций из A в B?

4. При каких m и n существует взаимно-однозначное соответствие между A и B?

3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

КОМБИНАТОРИКА

Произведение всех натуральных чисел от 1 до n обозначается:

n! = 1·2·3·…·(n-1)·n, 0! = 1

Пусть X={x₁, x₂, ..., x_n} – это множество из n элементов, k  n.

Размещение элементов из X объёма k – это упорядоченное подмножество из k элементов, принадлежащих X.

Количество размещений объёма k из n различных элементов с неограниченными повторениями:

= n^k (знач^мест)

Если на каждую i-ю из k позиций можно поставить один из q_i элементов множества X, то количество таких размещений равно:

(q₁, q₂, ..., q_n) = q₁  q₂  ...   q_n

Количество размещений объёма k из n различных элементов без повторений:

= n(n - 1)(n - 2) … (n - k + 1)=

Перестановка элементов из X – это размещение элементов из X объёма n.

Количество перестановок из n различных элементов:

= P_n = n!

Если n элементов содержат q_i элементов i-го сорта, q₁ + q₂ + ... + q_m = n и элементы одного сорта идентичны, то число перестановок равно:

P_n(q₁, q₂, ..., q_m) =

Сочетание элементов из X объёма k – это неупорядоченное подмножество из k элементов, принадлежащих X.

Сочетания, размещения и перестановки могут быть также с повторениями элементов множества X (неограниченными и ограниченными).

Количество сочетаний объёма k из n различных элементов без повторений:

Количество сочетаний объёма k из n различных элементов с неограниченными повторениями:

Бином Ньютона:

Свойства:

(1)

(2)

(3)

(4)

(5)

При решении комбинаторных задач часто используются следующие правила комбинаторики:

1. Правило суммы. Если объект А может быть выбран n способами, а объект B другими m способами, то выбор «либо А, либо В» может быть осуществлен n+m способами.

2. Правило произведения. Если объект А может быть выбран n способами и после каждого из таких выборов объект B в свою очередь может быть выбран m способами, то выбор «A и B» в указанном порядке может быть осуществлен nm способами.

Задача-пример. Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей?

Решение. Условие «не более трех» означает, что в команду может входить либо 3 юноши, либо 2 юноши, либо 1 юноша, либо ни одного юноши. Таким образом, в задаче выделяются четыре различных случая. В соответствии с правилом сложения нужно подсчитать количества вариантов в каждом из этих случаев и сложить их.

Рассмотрим первый случай. Нужно подсчитать, сколькими способами можно выбрать из 12 девушек и 10 юношей команду, состоящую из 3х юношей и 2х девушек. Из 10 юношей можно выбрать 3х юношей способами. Для каждых трех выбранных юношей можно выбрать также способами 2х девушек из 12ти. Поэтому работает правило умножения и в первом случае число вариантов команд равно .

Аналогично, во втором случае: .

В третьем случае: .

В четвертом случае: .

Окончательный ответ: +++.

Примеры решения задач

№1.17. n (n>2) человек садятся за круглый стол. Два размещения по местам будем считать совпадающим, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол?

Решение.

Общее количество всевозможных рассадок равно числу перестановок из n элементов P_n = n! Однако из этих рассадок нужно исключить совпадающие. Отношение соседства сохраняется при циклических перестановках (их n штук) и при симметрическом отражении (их также n штук):

Поэтому всего способов (делить, т.к. правило умножения)

№1.19. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз?

Решение.

Всего способов вынуть 10 карт из колоды . Из них в случаях в выборке не окажется ни одного туза. Поэтому ответ –.

№1.20. Сколькими способами можно составить три пары из n шахматистов?

Решение.

Сначала выберем из n шахматистов 6 человек. Это можно сделать способами. Теперь каждую шестёрку будем разбивать на пары. Для этого поставим 6 шахматистов в ряд, считая, что они имеют имена: a, b, c, d, e, f. Это можно сделать 6! способами. Однако нам не важен порядок внутри каждой пары и порядок самих пар. Перестановок, в которых шахматисты меняются местами в парах 2³. Перестановок, в которых меняются местами пары 3!. Поэтому разбить на пары 6 шахматистов можно способами. Ответ.

№1.24. Сколько существует чисел от 0 до 10ⁿ, в которые не входят две идущие друг за другом одинаковые цифры?

Решение.

Рассмотрим все n-значные числа. Первую цифру мы можем выбрать 9-ю способами. Чтобы вторая цифра была отлична от первой, то её также можно выбрать 9-ю способами. Количество таких n-значных чисел равно количеству размещений объёма n из 9 элементов с неограниченными повторениями, т.е. равна 9ⁿ для n>1 и 10 для n=1.

Поэтому ответ 10+9²+9³+...+9ⁿ. Число 10ⁿ не подходит.

ТЕОРИЯ АЛГОРИТМОВ

• Пусть N – это множество натуральных чисел, включая нуль.

• В данном разделе курса будут рассматриваться функции многих переменных fⁿ(x₁, ..., x_n), определенные на некотором множестве MNⁿ c натуральными значениями, т.е. fⁿ(x₁, ..., x_n)N, x_iN для i=1, ..., n, или fⁿ Nⁿ⁺¹.

• Функция fⁿ(x₁, ..., x_n) называется всюду определенной, если её областью определения является Nⁿ_­, т.е. для любого набора из n натуральных чисел существует натуральное число, являющееся значением функции fⁿ.

• Простейшие всюду определенные функции:

1. s(x)=x+1 для любого x;

2. o(x)=0 для любого x;

3. Iⁿ_m(x₁, ..., x_m, ..., x_n)=x_m.

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

• Оператор суперпозиции:

Функция hⁿ(x₁, ..., x_n) получается из функций g^m, fⁿ₁, ..., fⁿ_m с помощью оператора суперпозиции, если hⁿ(x₁, ..., x_n) = g^m(fⁿ₁(x₁, ..., x_n), ..., fⁿ_m(x₁, ..., x_n)).

• Оператор примитивной рекурсии:

Функция fⁿ⁺¹(x₁, ..., x_n, y) получается из функций gⁿ(x₁, ..., x_n) и hⁿ⁺²(x₁, ..., x_n, y, z) с помощью оператора примитивной рекурсии, если она может быть задана схемой примитивной рекурсии:

fⁿ⁺¹(x₁, ..., x_n, 0) = gⁿ(x₁, ..., x_n),

fⁿ⁺¹(x₁, ..., x_n, y+1) = hⁿ⁺²(x₁, ..., x_n, y, fⁿ⁺¹(x₁, ..., x_n, y)).

• Оператор минимизации:

Функция fⁿ(x₁, ..., x_n) получается из функции gⁿ⁺¹(x₁, ..., x_n, y) с помощью оператора минимизации и обозначается fⁿ(x₁, ..., x_n)=y[gⁿ⁺¹(x₁, ..., x_n, y)=0], если:

fⁿ(x₁, ..., x_n) определено и равно y  gⁿ⁺¹(x₁, ..., x_n, 0), ..., gⁿ⁺¹(x₁, ..., x_n, y-1) определены и не равны нулю, а gⁿ⁺¹(x₁, ..., x_n, y)=0.

(Можно говорить также: «Функция fⁿ(x₁, ..., x_n) равна минимальному значению y, при котором функция gⁿ⁺¹ обращается в нуль»)

• Примитивно рекурсивная функция (прф)

Функция fⁿ⁺¹(x₁, ..., x_n, y) называется примитивно рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

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

• Частично рекурсивная функция (прф)

Функция fⁿ⁺¹(x₁, ..., x_n, y) называется частично рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

• Из определений легко заметить, что примитивно рекурсивные функции являются также частично рекурсивными. Однако существуют частично рекурсивные функции, не являющиеся примитивно рекурсивными.