Раздел 1_РЕД_2. I. основы теории множеств. Системы счисления комбинаторика

• Название: I. основы теории множеств. Системы счисления комбинаторика
• Анкор: Раздел 1_РЕД_2.doc
• Дата: 29.11.2017
• Размер: 9.96 Mb.
• Имя файла: Раздел 1_РЕД_2.doc
• Тип: Документы; #10536
• страница: 1 из 17

Раздел I. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ. СИСТЕМЫ СЧИСЛЕНИЯ. комбинаторика

Любая теория предназначена для изучения свойств некоторого набора (множества) абстрактных объектов, моделирующих изучаемую реальную среду. Теория множеств рассматривает общие количественные и структурные свойства таких конечных и бесконечных наборов, а также операции с множествами.

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

Глава 1. МНОЖЕСТВА, ОПЕРАЦИИ С НИМИ. АЛГЕБРА МНОЖЕСТВ

1.1. Элементы и множества

Понятия множества и его элемента первичны, поэтому их нельзя строго выразить через термины, введенные в других дисциплинах. Интуитивно множество можно определить как совокупность объектов (элементов), имеющих некоторые общие свойства, представляющие интерес для их изучения, например, множество студентов университета, множество всех натуральных чисел, множество вещественных чисел на всей числовой оси и т.д. Обычно множества обозначают заглавными латинскими буквами без индексов и с индексами (А, В, С, А₁, С_i), их элементы — прописными буквами (также без индексов и с индексами). Включение элемента a₁ в множество А обозначают следующим образом: a₁  А .

Объекты, рассматриваемые в качестве элементов множеств, могут иметь самую различную природу, быть абстрактными и реальными: числа, геометрические фигуры, предметы окружающей среды, люди и т. д. Особую роль в теории множеств играют пустое и универсальное множества.

Определение. Пустым называется множество, не содержащее элементов. Обозначается оно .

Определение. Допустим, рассматриваются множества, состоящие из объектов некоторого вида. Универсальным называется множество U, содержащее полный набор таких объектов.

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

Для конкретного множества А универсальное множество U, как правило, можно принять не единственным образом.

Пример 1. Универсальное множество U=R= (–, +)составляютвсе вещественные числа. Выделим в нем следующие множества:

1)  R⁺=(0, +) — множество всех положительных вещественных чисел,

2)  R^–=(–, 0) — множество всех отрицательных вещественных чисел,

3)R⁺ =[0,+) — множество всех неотрицательных вещественных чисел,

4)R^– =(–, 0] — множество всех неположительных вещественных чисел.

Все рассмотренные множества бесконечны.

Пример 2. Универсальное множество U=R⁺ —совокупность всех неотрицательных вещественных чисел. Выделим в нем следующие множества:

1)  Е₂={0, 1}—множество из двух чисел: 0 и 1;

2)N={1, 2,3,…}—множество натуральных (положительных целых) чисел;

3)N={0,  1,  2,  3,  …}— расширенное множество натуральных чисел;

4)  Р ={1,  2,  3,  5,  7,  11, …}—множество положительных простых чисел (делящихся нацело только на себя и на единицу).

Первое множество конечно, так как в нем всего два элемента, остальные бесконечны. В качестве Uдля 1) — 4) можно было бы принять множество R всех вещественных чисел.

Пример 3. Универсальное множество С ={множество всех окружностей на декартовой плоскости Оху}. На нем можно рассмотреть множества С(а,b) окружностей с общим центром в точке с координатами (х = а, y= b). Каждое из них бесконечно, поскольку их элементы однозначно характеризуются радиусами R, а множество {R}=R⁺ — бесконечно.

Пример 4. Пусть А — это множество студентов внекоторой группе. Данное множество конечно. По отношению к А в качестве универсального могут быть приняты следующие более широкие множества:

1) U₁={множество всех студентов данного факультета};

2) U₂={множество всех студентов вуза}и т. д.

Определение. Декартовым произведением множеств А и В называют множество, обозначаемое АВ и состоящее из всех возможных пар (а,b), где аА, bВ. Степенью n множества А называют декартово произведение АА… А, куда А входит n раз. Обозначается оно Аⁿ.

Пример 5. А ={0,1}, B={a,b}.

А²={(0,0); (0,1); (1,0); (1,1)};АВ = {(0,a); (0,b);(1,a); (1,b)};

ВА= {(a,0); (a,1); (b,0);(b,1)}; B² ={(a,a); (a,b); (b,a); (b,b)}.

Как видно из примера 5, декартово произведение не коммутативно: в нем нельзя переставлять местами различающиеся сомножители.

Пример 6. С помощью степеней множества всех вещественных чисел Rудобно задавать декартовы координаты точек в многомерных пространствах:

1) R² ={(x,y), xR, yR} — множество декартовых координат всех точек на плоскости;

2) R³={(x,y,z), xR, yR, zR} — множество декартовых координат точек в трехмерном пространстве.

Рассмотрим соотношения между множествами с точки зрения сходства элементов, входящих в них.

Определение. Множество В называют равным множеству А, если оба множества состоят их одинакового набора элементов. Обозначается равенство, как и в случае чисел: В = А.

Пример 7. Множество всех натуральных чисел равно множеству всех положительных целых чисел.

Определение. Множество В называют подмножеством множества А (множество В входит в множество А), если все элементы множества В входят в множество А.

Включение множества В в множество А может быть двух видов. Рассмотрим их.

1. Если помимо элементов множества В в множестве А есть и другие элементы (множество А ”больше” множества В), то данное включение множества В в множество А называют строгим и обозначают: В А.

2. Если наряду со строгим включением множества В в множество А (В  А) возможно и равенство этих множеств (В = А), то такое включение называют нестрогим и обозначают: В  А.

1.2. Отображения, функции, предикаты

Определение. Рассмотрим множества А и В. Отображением fмножества А в множество В называют любое правило, по которому элементам аА ставятся в соответствие элементы bB. При этом элемент bBназывают образом элемента аА, а элемент а называют прообразом элемента b.

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

Определение. Для отображения f: А  В множество А называют областью определения отображения f, множество В — областью значений. Множество образов b =f(а)всех элементов области определения А называют образом множества А и обозначают f(А).

Определение. Если областью определения отображения является декартово произведение длины n:f: А₁ А₂… А_n  В, то отображение называют n-местным.

Определение. Отображение f: А  В называют инъекцией, если образы любых двух различных элементов а₁А, а₂А, а₁ а₂тоже различны: f(а₁) f(а₂), т.е. в инъекции различные элементы из области определения не могут отображаться в один образ.

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

Отображение f: А  В, являющееся одновременно инъекцией и сюръекцией, называют взаимно однозначным или биекцией.

Важный практический смысл биекции или взаимно однозначного отображения f: А  В заключается в том, что каждому элементу аА ставится в соответствие один и только один образ f(а) =bВ, и наоборот, каждому образу bВ соответствует один и только один прообраз аА. При этом общее количество элементов в конечных множествах А и В совпадает. Проверить взаимную однозначность (биективность) отображения можно
и другим путем.

Определение. Отображение f: А  В называют однозначным, если любому элементу аА поставлен в соответствие единственный элемент bB.

Определение. Пусть f — отображение из А в В (f:AB). Обратным к f называется отображениеf^–1:BA, которое переводит элементы bB в элементы аА, такие, что f(a)=b.

Утверждение. Если отображение f:ABоднозначно и обратное к нему отображениеf^–1:BA существует и однозначно, то f является биекцией (взаимно однозначным отображением).

Пример 1. Пусть A = {места в вагоне}, B = {пассажиры}, отображение f задано билетами. В вагоне есть свободные места. Здесь отображение f:ABинъективно, но не сюръективно (f однозначно, но обратное отображение f^–1:BAне определено на свободных местах). Поэтому f не взаимно однозначно.

Пример 2. Пусть A = {места в вагоне}, B = {пассажиры}, отображение f задано билетами. В вагоне все места заняты. Здесь отображение f:ABвзаимно однозначно, поскольку оно одновременно инъективно и сюръективно (f однозначно, обратное к нему отображение f^–1:BAсуществует и также однозначно, а именно, каждому месту соответствует пассажир).

Определение. Пусть на множествах А, В, С заданы отображения g:AB; f: В  С. Композицией отображений gиfназывают отображение h =fg (h:AC), полученное при последовательном применении отображений g иf.

Операция композиции сохраняет взаимную однозначность отображений, т. е., если g и fвзаимно однозначны, то h = gf также представляет собой взаимно однозначное отображение.

Отображенияf:AB, где областью значений Bявляются числовые множества, называют функциями.

Для них используют ту же систему обозначений, что и для отображений. Различие в терминологии следующее.

Определение. Пусть f— функция, действующая из области определения А в область значений В:f:AB. Элементы аА называют аргументами функции f, элементы b=f(a)B — значениями функции f.

Для функций, как для частного случая отображений, также рассматривают инъективность, сюръективность, биективность, однозначность и обратные функции.

Пример 3. А = R — множество всех вещественных чисел, B =[–1,+1], f = sin. Функцияf однозначна, но не взаимно однозначна, так как значения образов b = sin(a) по заданному элементу аА определяются однозначно, а обратное отображение f^–1:BA, задающее значения прообразов по их образам (a = sin^–1(b)), имеет при каждом b бесконечное число решений (функция сюръективна, но не инъективна).

Пример4. A=[ –2, 2]; B=[–1,+1]; f= sin. Данная функция взаимно однозначна.

Пример 5. Рассмотрим произвольную линейную функцию f с ненулевым линейным коэффициентом, отображающую одно множество вещественных чисел A на другое — B . В общем случае формула перехода от элемента aA к некоторому элементу bB имеет вид: b = С₀a + С₁, где С₀и С₁— некоторые константы. При С₀ 0 такая функция однозначна.

Докажем от противного. Допустим, существует некоторый элемент aA, который отображается на множество B не единственным образом, т.е. имеет как минимум два различных образа b и b (b–b 0). Так как b = С₀ a + С₁ и b = С₀ a + С₁, то, вычитая из первой формулы вторую, получим: b–b = С₀(а––а)= 0. При С₀0 это противоречит предположению
о различии b и b, а следовательно, о неоднозначности рассмотренной линейной функции.

Следствие. Любая линейная функция fс ненулевым линейным коэффициентом не только однозначна, но и взаимно однозначна.

Справедливость данного утверждения следует из того, что обратной к линейной функции f, переводящей элементы aA в элементы bВ по формуле b = С₀ a + С₁ (где С₀ 0), будет также линейная функция f^-1с ненулевым линейным коэффициентом, переводящая элементы bВ в элементы aAпо формуле a =(1/С₀) b – С₁/С₀.

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

Определение. Отображение называют логической функцией или предикатом, если ее областью значений являются логические значения «ложь» («false») и «истина» («true»), которые в математике обозначают соответственно 0 и 1. Таким образом, у логической функции область значений Е₂= {0,1}.

Предикаты, как и отображения, могут быть n-местными. В отличие от отображений и функций их обозначают заглавными латинскими буквами с индексами и без — например, Q(x), Р(х,у),R₂(x,y,z). Поскольку результат у предикатов — логическое значение, то они формулируются в отличие от обычных числовых функций в виде некоторого логического условия.

Определение. Областью истинности предиката Р(х₁, х₂, …, х_n), определенного на декартовом произведении Х₁Х₂…Х_n, называется множество наборов значений (х₁, х₂, …, х_n), принадлежащих Х₁Х₂…Х_n, на которых Р(х₁, х₂, …, х_n)= «истина» (Р(х₁, х₂, …, х_n) = 1).

Пример 6. U=R. Q(x)= «x больше 0». Для любого вещественного числа x можно определить, положительно оно или нет. В первом случае Q(x)=1 , во втором Q(x)=0. Областью истинности данного предиката будет множество R⁺,входящее в U=R.

Пример 7. U=R⁺. Q₁(x) = «x может быть представлен в виде дроби m/n, где m и n — целые числа, m ≥ 0, n>0 ». Поскольку логическое условие предиката совпадает с определением неотрицательного рационального числа, то его областью истинности будут все такие числа на неотрицательной числовой полуоси.