Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Основные понятия теории множеств - файл 1.doc


Лекции - Основные понятия теории множеств
скачать (688 kb.)

Доступные файлы (1):

1.doc688kb.15.11.2011 22:33скачать

содержание

1.doc

  1   2   3
Лекции по дискретной математике.

Носырева Л.Л.


Введение.


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

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

Конечным итогом работы инженера-математика и системотехника является алгоритм, реализованный программным, аппаратурным или программно-аппаратурным способом. Эффективность используемых вычислительных средств во многом определяется оптимальностью разработанного алгоритма, которая оценивается временной и емкостной сложностью. Под временной емкостью понимается время работы алгоритма, под емкостной сложностью – объем памяти, необходимый для решения задачи. Временная и емкостная сложность являются функциями от размерности задачи. В настоящее время в связи с широким использованием вычислительной техники в различных сферах человеческой деятельности все большее значение приобретают вычисления на дискретных структурах – комбинаторные вычисления. Анализ трудностей, имевших место при поиске эффективных алгоритмов решения задач дискретной математики, привел к формулировке центральной теоретико-методологической проблемы дискретной математики – решению вопроса о возможности исключения перебора вариантов при решении задач на дискретных структурах.

При решении проблемы уменьшения перебора вариантов имеются группы алгоритмов: эвристические и характеризационные. К эвристическим относятся алгоритмы широкого класса, от ГСН-алгоритмов (грубая сила и невежество) и кончая «хитрыми» и «жадными». Название алгоритма соответствует тому виду эвристики, который определяет процедуру борьбы с перебором. Оценить, насколько удалено полученное с помощью эвристического алгоритма решение от минимального в смысле значения функционала качества решения принципиально невозможно.

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


^ Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

§ 1. МНОЖЕСТВО

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

Понятие «множество», как и любое другое исходное понятие математической теории не является строго определяемым. Его синони­мами являются «совокупность», «семейство», «класс», «система», «собрание», «ансамбль», «коллекция» и др.

Например, Кантор, основатель теории множеств, дал такое определение: «под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью».

Примеры множеств:

  • множество столов в комнате;

  • множество всех атомов на Марсе;

  • множество всех рыб в океане;

  • множество футболистов команды «Сибскана»

  • множество всех футбольных команд

В математике рассматриваются:

  • множество то­чек (например, окружности),

  • множество чисел (напри­мер, действительных)

  • Множество всех решений уравнения sinx=0,5

  • М
    ножество всех чисел вида

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

Тот факт, что элемент x принадлежит множеству А (x является элементом множества А), записывается так: . Если же x не является элементом множества А (x не принадлежит множеству А), будем писать . Таким образом, принадлежность - это отно­шение между элементами и множествами, при этом пред­полагается, что для любого конкретного элемента и любого конкретного множества можно определить, принад­лежит этот элемент данному множеству или нет.

Существенным в понятии «множество» является то, что мы объединяем некоторые предметы в одно целое. Георг Кантор (1845–1918), немецкий математик, созда­тель теории множеств, так подчеркнул это обстоятель­ство: «Множество есть многое, мыслимое нами как еди­ное». Чтобы наглядно представить понятие «множество», академик Н.Н. Лузин (1883–1950) предложил следую­щий образ. Представим прозрачную непроницаемую обо­лочку, нечто вроде плотно закрытого непроницаемого мешка. Предположим, что внутри этой оболочки заклю­чены все элементы x данного множества А и что кроме них внутри оболочки никаких других предметов нет. Эта оболочка с предметами x, находящимися внутри нее, и может служить образом множества А, составленного из элементов x. Сама же прозрачная оболочка, охваты­вающая все элементы (и ничего другого кроме них), довольно хорошо изображает тот факт объединения эле­ментов x, в результате которого создается множество А.

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

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

Возможны различные способы задания множеств. Один из них состоит в том, что дается полный список (полный перечень) элементов, входящих в данное мно­жество. Так, множество учеников класса определяется списком в журнале. Если множество А конечное, состоя­щее из элементов a1, … , an, то используют обозначение А = {a1, … , an}. В частности, {а} — множество, состоя­щее из одного элемента а.

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

Имеется другой, универсальный способ задания мно­жеств. Это - задание с помощью характеристического свойства множества ^ А, т.е. такого свойства, которым обладают все элементы множества А и не обладают эле­менты, не принадлежащие А. Если, например, Z - мно­жество всех целых чисел, то , , крокодил не принадлежит Z. Окружность радиуса 2 с центром в на­чале координат - это множество всех таких x, что x есть точка плоскости и x находится на расстоянии в две еди­ницы от начала координат.

Если Р(x) - некоторое свойство, то предполагается, что оно определяет некоторое множество^ А, состоящее из всех тех элементов x, которые удовлетворяют свой­ству Р(x). этом случае множество А обозначают так:
A = {x| P(x)} или A = {x: P(x)}. Например, если А = {a1, … , an}, то оно может быть определено с помощью характеристического свойства следующим образом: A = {x| x = a1 или x = a2, или … или x = an}. Множество всех сенаторов США может быть определено с помощью характеристического свойства так: {x| x — сенатор}, и это задание экономнее задания данного множества с по­мощью списка всех сенаторов.

Ясно, что существуют множества, состоящие из трех, двух или одного элемента. Например, множество родите­лей любого человека двухэлементное. Однако иногда приходится рассматривать и множество, не содержащее ни одного элемента. Оно называется пустым и обозна­чается . При задании множества характеристическим свойством не всегда известно, существует ли элемент с таким свойством. Например, мы говорим о множестве решений какого-либо уравнения, которое может и не иметь решения, т.е. это множество решений уравнения пустое. Более того, часто бывает очень трудно выяснить, является ли пустым данное множество. Неизвестно, на­пример, до сих пор, является ли пустым множество всех натуральных п > 2 таких, что уравнение
xn + yn = zn имеет положительное целочисленное решение (проблема Ферма).

Введем понятие «подмножество».

Определение 1. Пусть А и В — непустые мно­жества. Если каждый элемент множества А является вместе с тем и элементом множества В, то А называют подмножеством множества В (или А содержится в В, или В содержит А, или А включено в В) и обозначают . Положим, по определению, что пустое множест­во есть подмножество любого множества В**, в том числе и пустого.

Пусть, например, ^ С — множество всех комплексных чисел; R — множество всех действительных чисел; Q — множество всех рациональных чисел; Z — множество всех целых чисел; N — множество всех натуральных чи­сел. Тогда .

Понятие подмножества определяет отношение между двумя множествами — отношение включения. Отметим простейшие свойства введенного отношения включения:

  1. , т. е. любое множество А является подмно­жеством самого себя (рефлексивность);

  2. если , , то (транзитив­ность).

Чтобы в множестве А выделить подмножество В, до­бавляют к характеристическому признаку множества А то или иное дополнительное свойство Р(х) и обозначают это так: B = {| P(x)}. Например, {| x > 0} множество всех положительных действительных чисел.

Введем наряду с отношением включения множеств еще одно отношение — отношение равенства множеств.

Определение 2. Пусть А и В — два множества. Множества А и В называются равными, если каждый элемент множества А является вместе с тем и элементом множества В, и обратно, каждый элемент множества В является и элементом множества А. Другими словами, множества А и В называются равными, если выполняют­ся два включения: и .

Отношение равенства двух множеств, очевидно, удов­летворяет следующим условиям:

  1. А = А (рефлексивность);

  2. если А = В и В = С, то А = С (транзитивность).

Отметим, что пустое множество единственно. Действи­тельно, пусть
и — два пустых множества. Так как для любого множества А имеем, что , то взяв в качестве А множество , получим , а взяв в качестве А множество , получим . Отсюда .

Если и , то А называют собственным подмножеством множества В и обозначают . Введенное отношение называется отношением строгого включения. Например, . Отношение строгого включения удовлетворяет следующему свойст­ву: если и , то (транзитивность).

Пусть^ А — множество. Совокупность всех подмно­жеств множества обозначают через Р(А) и назы­вают булеаном множества А. Ясно, что , . Если, например, А = {а, b}, то P(A) = {, {a}, {b}, A}.


§2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Во всех рассуждениях о нескольких множествах бу­дем предполагать, что они являются подмножествами некоторого фиксированного множества , которое назо­вем универсальным, универсумом или пространством* и обозначать Е (или I). На практике это множество часто явно не указывают, предполагая, что в случае необходи­мости оно может быть восстановлено.

Определение 3. ^ Пересечением множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов, которые принадлежат обоим множествам А и В.

Это определение символически можно записать так:

. Например, ; . Если ^ А — множество всех четных чисел; В — множество всех простых чисел, то . Если А — множество студентов мужского пола; В — множество мужчин старше 20 лет, то — множество студентов мужского пола старше 20 лет.

Определение 4. Объединением множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов, которые принадле­жат хотя бы одному из множеств А, В.

Это определение символически можно записать так:

. Например, . Если — множество всех положительных действительных чисел, — множество всех отрицательных действительных чисел, то — множество всех действительных чисел, кроме 0. Если — множество всех действительных чисел мень­ше 1, то — множество всех действительных чисел.

Отметим, что объединение множеств А и В называют иногда суммой и обозначают А + В, а их пересечение — произведением и обозначают АВ.

Определение 5.^ Разностью множеств А и В называют множество, обозначаемое А\В и состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

Определение 6. Пусть А — подмножество мно­жества Е. Дополнением множества А в множестве Е называют множество, состоящее из всех тех и только тех элементов из Е, которые не принадлежат А, и обозначают .

Например, если ^ Е — множество всех целых чисел, А — множество всех четных чисел, то — множество всех нечетных чисел. Если Е — множество всех людей, А — множество всех мужчин, то — множество всех женщин.

Введенные операции объединения, пересечения и разности являются двуместными. Операция дополнения является одноместной.

Операции объединения, пересечения, разности и до­полнения множеств допускают очень наглядное графиче­ское истолкование с помощью так называемых кругов Эйлера (или диаграмм Венна). Универсальное множест­во Е изображается при этом множеством точек некото­рого прямоугольника, а его подмножества — в виде кру­га (или какой-нибудь другой простой области внутри этого прямоугольника).

Если изобразить таким образом множества А и В, то множества (рис.1), (рис.2) и (рис.3) изображаются заштрихованными областями.




Пусть Р(Е) — совокупность всех подмножеств мно­жества Е. Р(Е) замкнуто относительно операций объеди­нения, пересечения и дополнения множеств, т.е. произ­водя эти операции над элементами множества Р(Е), получаем элементы, принадлежащие Р(Е). Множество Р(Е) с введенными операциями называют буле­вой алгеброй подмножеств множества Е.

Подобно тому, как сложение и умножение чисел удовлетворяют известным законам коммутативности ассоциативности и дистрибутивности, операции объеди­нения, пересечения и дополнения в алгебре подмножеств подчинены аналогичным законам, а также ряду других. Выпишем основные законы, которым подчиняются эти операции:



Универсальным методом доказательства вышеприве­денных равенств является доказательство, основанное на определении равенств двух множеств, т.е. два множест­ва А и В равны тогда и только тогда, когда выполнены два включения: и . Приведем доказатель­ства некоторых из этих соотношений.

Чтобы доказать 7), достаточно проверить два вклю­чения:



Доказательство 7а). Пусть . Тогда или . Если, то и , а следовательно, х является элементом пе­ресечения этих множеств. Если , то и . Значит, и , так что и в этом случае х есть элемент их пересечения.

Доказательство 7б). Пусть . Тогда и . Следовательно, или же и . Из этого вытекает, что .

Равенство 7) с помощью кругов Эйлера наглядно представлено на рис.4 и 5. На рис.4 множество А за­штриховано горизонтально, а — вертикально; по­этому — область, попадающая под верти­кальную или горизонтальную штриховку. На рис.5 мно­жество заштриховано горизонтально, a — вертикально; тогда — область, попадающая под обе штриховки. Легко видеть, что обе эти области совпадают.



Докажем 9). Для этого достаточно проверить:



Доказательство 9а. Пусть. Тогда . Значит и . Отсюда и , а потому .

Доказательство 9б. Пусть . Тогда и . Следовательно, и . Отсюда , а потому .

Равенство 9) наглядно представлено на рис.6 и 7.



На рис.6 множество заштриховано, поэтому — незаштрихованная область. На рис.7 множест­во заштриховано горизонтально, а — вертикально; тогда — область, попадающая под обе штриховки. Легко видеть, что обе эти области совпадают. Приведем еще два соотношения:


(законы поглощения)


Доказательство предоставляем читателю.

Отметим в заключение без доказательства, что мно­жество соотношений 1) – 15) полно в том смысле, что любое равенство, образованное при помощи (относительно ^ Е) и любого числа букв А, В, С, … , имею­щее место для любых подмножеств А, В, С, … множест­ва Е, может быть выведено из 1) – 15).

Формальное изучение этих законов восходит к англий­скому математику Дж. Булю (1815-1864).

§ 5. ОТОБРАЖЕНИЕ

Введем одно из основных понятий математики — ото­бражение (функция). Будем считать это понятие пока неопределяемым. Поясним, что следует понимать под отображением.

Пусть X, Y — непустые множества. Если каждому эле­менту соответствует единственный элемент , то говорят, что задано отображение множества Х в мно­жество Y или задана функция, определенная на множест­ве Х со значениями в множестве Y.

Отображение множества Х в Y обозначим буквой F. Если F — отображение Х в Y, то это символически запи­сывают так:

F: XY или

Каждому элементу при отображении ^ F: XY соответствует некоторый элемент из множества Y, кото­рый называется образом элемента х при отображении F и обозначается F(x). (Другие обозначения: Fx, xF, xF). Если у — образ элемента х при отображении F: XY, то это записывают так:

y = F(x), или , или

Элемент х называют прообразом элемента у при ото­бражении F: XY.

Определение 6. Два отображения F: XY и G: XY называются равными (обозначение F = G), если F(x) = G(x) для любого элемента (т.е. если результаты их действия одинаковы).

Определение 7. Пусть ^ F: XY — отображе­ние, а А — непустое подмножество множества X. Обра­зом множества А при отображении F называют совокуп­ность образов всех элементов множества А и обозначают F(А). Другими словами, . Ясно, что . В частности, для имеем .

Определение 8. Пусть F: XY — отображе­ние и . Отображение, которое каждому элементу , рассматриваемому как элемент из X, ставит в со­ответствие , называется сужением, или ограни­чением, F на А и обозначается FA или F/A.

Например, найдем все отображения множества X = {x1, x2, x3} в множество Y = {y1, y2}, и для каждого такого отображения найдем образ множества X.

Отображения F: XY в случае, когда Х — конечное множество, зададим таблицей, состоящей из двух строк. В верхней строке запишем элементы множества X, а под ними — их образы из множества Y.

Итак, запись означает, что F(x1) = y1, F(x2) = y2,
F(x3) = y1,

Выпишем все отображения множества Х в Y:



Отображение множества всех точек плоскости в себя, которое каждую точку плоскости переводит в точку, по­лученную из данной поворотом плоскости вокруг начала координат на угол φ, показано на рис.9, а отображение множества всех векторов трехмерного пространства, вы­ходящих из начала координат, в себя, которое каждый вектор переводит в его ортогональную проекцию на пло­скость X0Y, — на рис.10.



Следующие примеры отображений хорошо известны (ниже: R — множество всех действительных чисел; — множество всех положительных действительных чисел; множество всех неотрицатель­ных действительных чисел):

а) F: RR, F(x) = sin x. Здесь (строгое включение);

б) F: R → [–1, 1], F(x) = sin x. В этом случае F(R) = [–1, 1];

в) F: RR, F(x) = х2. Тогда (стро­гое включение);

г) F: RR≥0, F(x) = х2. Имеем F(R) = R≥0;

д) F: (R≥0) → R≥0, F(x) = х2. Здесь F(R≥0) = R≥0.

Подчеркнем, что в рассмотренных примерах образ F(X) множества Х может совпадать с множеством Y (как в примерах б, г, д предыдущего абзаца) либо быть его собственным подмножеством (примеры а, в), а образы различных элементов из Х могут быть различ­ны (как в примере д), либо совпадать (как в приме­рах в, г, когда F(2) = F(—2) = 4), причем образы даже бесконечного множества различных элементов из Х могут совпадать (как в примерах а, б, когда, напри­мер, F(kπ) = 0, где k = 0, ±1, ±2, …).

Определение 9. Отображение F: X Y назы­вается инъективным (или инъекцией), если различным элементам из множества Х соответствуют различные эле­менты из множества Y при отображении F: X Y, т.е. если для любых x1 и x2 из Х истинна следующая импли­кация: . В силу закона контрапозиции это условие равносильно следующему: . Другое название инъективного отобра­жения ^ F: X Yвзаимно однозначное отображе­ние Х в Y.

Например, отображение F: R>0 R, F(x) = lg x инъективно, ибо из
lg x1 = lg x2, по известному свойству логарифмической функции следует, что
x1 = x2; анало­гично отображение F: R≥0R≥0, F(x) = х2 инъективно, так как если и , то x1 = x2. Отображение F: RR≥0, F(x) = х2 не является инъективным, так как, например, F(2) = F(—2) = 4, хотя .

Определение 10. Отображение ^ F: X Y назы­вается сюръективным (или сюръекцией), если каждый элемент множества Y является образом хотя бы одного элемента из Х при отображении F: X Y (или: если каждый элемент множества Y имеет хотя бы один прообраз в множестве Х при отображении F).

Иными словами, отображение F: X Y называется сюръективным, если образ F(X) множества Х при ото­бражении F: X Y совпадает с Y, т.е.
F(X) = Y.

Другое название сюръективного отображения F: X Yотображение множества Х на множество Y.

Например, отображения F: R → [–1, 1], F(x) = sin x, F: RR≥0, F(x) = х2 и F: R≥0R≥0, F(x) = х2 сюръективны, а отображения F: RR, F(x) = х2 и
F: RR, F(x) = sin x не являются сюръективными.

Подчеркнем, что для доказательства сюръективности отображения
F: XY необходимо проверить, что для любого элемента существует элемент такой, что у0 = F(x), т.е. необходимо проверить, что для лю­бого уравнение F(x) = у0 имеет хотя бы одно ре­шение .

Например, отображение F: R>0 R, F(x) = lg x сюръективно, ибо уравнение имеет решение (единственное) относительно x: , а ото­бражение F: R R, F(x) = 2x не является сюръективным, так как уравнение не имеет реше­ния, если у0 ≤ 0.

Определение 11. Отображение F: X Y назы­вается биективным (или биекцией), если оно одновре­менно и инъективно, и сюръективно.

Другое название биективного отображения ^ F: X Yвзаимно однозначное отображение множества Х на мно­жество Y.

Например, отображение F: R R, F(x) = 2x + 1 биективно. Действительно, F инъективно, так как из 2x1 + 1 = 2х2 + 1 следует, что x1 = x2. Кроме того, ото­бражение F сюръективно, ибо для любого урав­нение у0 = 2x + 1 имеет решение (и даже единственное) относительно х: х = (у0 – 1)/2.

  1   2   3



Скачать файл (688 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации