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

Стар 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

План реферата.

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 часть Элементы и множества

     Понятия  множества и элемента множества  относятся к понятиям, не определимым  явно, как, например, точка и прямая. Слова «совокупность», «семейство»,  «система», «набор» и т.п. –  синонимы слова «множество». Это  связано с тем, что некоторые понятия в математике должны быть исходными, служить теми «кирпичиками», из которых складывается общая теория. Мы определяем только, как соотносятся эти исходные понятия, не говоря о природе рассматриваемых объектов. Человеческое мышление устроено так, что мир представляется состоящим из отдельных «объектов». Философам давно ясно, что мир – единое неразрывное целое, и выделение в нем объектов – это не более чем произвольный акт нашего мышления, позволяющий сформировать доступную для рационального анализа картину мира. Но как бы то ни было, выделение объектов и из совокупностей – единственный (или даже единственно возможный) способ организации нашего мышления, поэтому неудивительно, что он лежит в основе главного инструмента описания точного знания – математики.

      Можно  сказать, что множество- это любая определенная совокупность объектов. Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличны друг от друга. Примерами множеств могут быть: множество людей, животных, растений на нашей планете, а также множество N натуральных чисел: 1,2,3,4…, множество Р простых чисел:2,3,5,7,11…, множество Z  целых чисел:…, -2,-1,0,1,2,…, множество R вещественных чисел и т.д. Множество, не содержащее элементов, называется пустым. Обозначение Пустое множество является подмножеством любого множества. Мощность пустого множества равна нулю. Понятие пустого множества (подобно понятию «нуль») возникает из потребности, чтобы результат всякой операции над множествами был также множеством.

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

        Если объект х является элементом множества M, то говорят, что х принадлежит М. Обозначение : В противном случае говорят, что х не принадлежит М. Обозначение: Элементы множества сами могут являться множествами. Например, множество групп студентов состоит из элементов (групп), которые, в свою очередь, состоят из студентов.

Рисунок 1 Множества.

Рассмотрим все на примере:

Пусть даны два множества  А и В, тогда

 

   Следующее понятие  - подмножество в теории множеств. Множество С является подмножеством множества В (   в случае, если каждый элемент множества С является также и элементом множества В. Например, множество всех четных чисел является подмножеством множества всех целых чисел. Если С является подмножеством В, то В называется надмножеством.

2 часть Количество элементов  в множестве.

 Мощность множества – это обобщение понятия количества ( числа элементов множества ), которое имеет смысл для всех множеств, включая бесконечные.

 Существует большие,  есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.

 В теории множеств  счётное множество есть бесконечное  множества, элементы которого  возможно занумеровать натуральными  числами. Более формально: множество  Х является счётным, если существует биекция  , где N обозначает множество всех натуральных чисел. Значит , счётное множество – это множество, равномощное множеству натуральных чисел.

  Счётное множество  является «наименьшим» бесконечным  множеством, т.е. в любом бесконечном множестве найдётся счётное подмножество.

Свойства счетного множества:

1. Любое подмножество счётного множества конечно или счётно;
2. Объединение конечного или счётного числа счётных множеств счётно;
3. Прямое произведение конечного числа счётных множеств счётно;
4. Множество всех конечных подмножеств счётного множества счётно;
5. Множество всех подмножеств счётного множества счётно;

Несчётное множество  – такое бесконечное множество, которое не является счётным. Таким  образом, любое множество является либо конечным, либо счётным, либо несчётным. Множество рациональных чисел и множество алгебраических чисел счётны, однако множество вещественных чисел континуально и, следовательно, несчётно. Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества – это соответствующий ему класс эквивалентности.

3 часть – операции над множествами.

В результате операций из исходных множеств получаются новые.

1 свойство – Сравнение множеств.множество элемент аксиоматический принность

Множество A содержится во множестве B (множество B включает множество A), если каждый элемент A есть элемент B:

.

Если  и , то A называется собственным подмножеством В. Заметим, что . По определению .

Два множества называются равными, если они являются подмножествами друг друга:

Теорема о сравнении  множеств. Для любых множеств A и B существует одна и только одна из следующих возможностей: |A| = |B|, |A| < |B|, |A| > |B|.

1 операция – объединение.

2 операция – пересечение.

          

    3 операция  – разность.

   4 операция –  симметрическая разность

5 операция – дополнение.

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):

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

Объединением двух множеств A È B (рис. 2.2.1) – называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств A и B

 

Пересечением множеств А∩В (рис 2.2.2), является множество, состоящее из всех тех элементов, которые принадлежат одновременно всем данным множествам.

Разностью множеств A \ B = A – B  – называется такое множество, каждый элемент которого принадлежит множеству A, но не принадлежит множеству B.

Симметрическая разность A D B

Дополнение к множеству A называется множество всех элементов, не входящих в множество A

 

4 часть свойства операций над множествами.

Пусть задан универсум U. Тогда

Пусть задан универсум U. Тогда для всех A,B,C Ì U выполняются следующие свойства (табл. 2.3.1):

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

Для объединения ( È )	Для пересечения ( Ç )
Идемпотентность
A È A = A	A Ç A =A
Коммутативность
A È B = B È A	A Ç B = B Ç A
Ассоциативность
A È (B È C) = (A È B) È C	A Ç (B Ç C) = (A Ç B) Ç C
Дистрибутивность
A È (B Ç C) = (A È B) Ç (A È C)	A Ç (B È C) = (A Ç B) È (A Ç C)
Поглощение
(A Ç B) È A = A	(A È B) Ç A = A
Свойства нуля
A È Æ = A	A Ç Æ = Æ
Свойства единицы
A È U = U	A Ç U = U
Инволютивность
= A
Законы де Моргана
Свойства дополнения
Выражение для разности
Выражение для симметрической разности

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

 Рассмотрим для  примера первое равенство: A È A = А. Возьмем произвольный элемент х, принадлежащий левой части равенства, х Î A È A. По определению операции объединения È имеем хÎ A È хÎ A. В любом случае хÎ A. Взяв произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению включения множеств получаем, что A È A Ì А. Пусть теперь хÎ A. Тогда, очевидно, верно хÎ A È хÎ A. Отсюда по определению операции объединения имеем х Î A È A. Таким образом, А Ì A È A. Следовательно, по определению равенства множеств, A È A = А. Аналогичные рассуждения нетрудно провести и для остальных равенств.

4 часть Представление множеств в ЭВМ

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

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими  разными способами, причем нельзя указать  способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других — другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.

Заключение.

Реферат выполнялся по теме: «Теория множеств». Здесь рассмотрены вопросы:

• Множества: элементы и множества, способы задания множеств, количество элементов в множестве;
• Операции над множествами: сравнение множеств, основные операции над множествами, свойства операций над множествами;
• Представление множеств в ЭВМ:

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

После проделанной работы можно сделать следующий вывод:

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

 

Список использованной литературы

 

1. Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.
2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)