Носырева Л.Л. Дискретная математика. Теория множеств - файл n1.doc

приобрести
Носырева Л.Л. Дискретная математика. Теория множеств
скачать (1144.5 kb.)
Доступные файлы (1):
n1.doc1145kb.13.09.2012 16:42скачать

n1.doc

  1   2   3   4   5   6   7   8   9
Иркутский государственный технический университет

Факультет Кибернетики

Кафедра Автоматизированных систем


Носырева Л.Л.
ДИСКРЕТНАЯ МАТЕМАТИКА

Конспективный материал к лекциям


(рабочий вариант)
Для специальностей АСУ, МЭИ, АСОК


Часть 1

Теория множеств


Иркутск 2006

Оглавление


Конспективный материал к лекциям 1

Введение. 3

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

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

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

§ 3.ОТОБРАЖЕНИЕ 12

§ 4. УМНОЖЕНИЕ ОТОБРАЖЕНИЙ 16

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

Глава 2. БИНАРНЫЕ ОТНОШЕНИЯ.
ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И ПОРЯДКА. 19

§ 6. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ 19

§ 7. БИНАРНЫЕ ОТНОШЕНИЯ 21

§ 8. ОПЕРАЦИИ НАД БИНАРНЫМИ ОТНОШЕНИЯМИ. 24

§ 9. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ 27

§ 10. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ,
ЛИНЕЙНО УПОРЯДОЧЕННЫЕ
И ВПОЛНЕ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА.
АКСИОМА ВЫБОРА 30



Введение.



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

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

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

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


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

«Множество» не является строго определяемым понятием.
Примеры множеств:





Конечное

Бесконечное
Способы задания множеств:

  1. полный список (полный перечень) элементов

  2. задание с помощью характеристического свойства множества А,

  3. порождающая процедура.


Пустое


Подмножество


Равные множества


Собственное подмножество множества

Булеан множества

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

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

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

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

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

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

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

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

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

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

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

  • множество всех решений уравнения 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}.

  1   2   3   4   5   6   7   8   9


Иркутский государственный технический университет
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации