Реферат: Элементы теории множеств

Федеральноеагентство по образованию

ФГОУ ВПО

Чувашскийгосударственный университет им. И.Н. Ульянова

Алатырскийфилиал

Факультетуправления и экономики

Кафедравысшей математики и информационных технологий

Курсоваяработа

 

подисциплине: Математическая логика

Элементытеории множеств

Выполнил студент

1 курса

группы — АФТ 61-06

Научный руководитель

проф. Мерлин А.В.

Алатырь

Введение

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

До второй половины XIX века понятие «множества» не рассматривалось в качествематематического (множество книг на полке, множество человеческих добродетелей ит. д. — всё это чисто бытовые обороты речи). Положение изменилось,когда немецкий математик Георг Кантор (рис. 1) разработал свою программустандартизации математики, в рамках которой любой математический объект долженбыл оказываться тем или иным «множеством».

Например, натуральное число, по Кантору, следовало рассматривать какмножество, состоящее из единственного элемента другого множества, называемого«натуральным рядом» — который, в свою очередь, сам представляет собоймножество, удовлетворяющее так называемым аксиомам Пеано. При этом общемупонятию «множества», рассматривавшемуся им в качестве центрального дляматематики, Кантор давал мало что определяющие определения вроде «множествоесть многое, мыслимое как единое», и т. д. Это вполне соответствовалоумонастроению самого Кантора, подчёркнуто называвшего свою программу не«теорией множеств» (этот термин появился много позднее), а учением омножествах (Mengenlehre).

Программа Кантора вызвала резкие протесты со стороны многих современныхему крупных математиков. Особенно выделялся своим непримиримым к ней отношениемЛеопольд Кронекер, полагавший, что математическими объектами могут считатьсялишь натуральные числа и то, что к ним непосредственно сводится (известна егофраза о том, что «бог создал натуральные числа, а всё прочее — дело рукчеловеческих»). Тем не менее, некоторые другие математики — в частности, ГотлобФреге и Давид Гильберт — поддержали Кантора в его намерении перевести всюматематику на теоретико-множественный язык.

Однако вскоре выяснилось, что установка Кантора на неограниченныйпроизвол при оперировании с множествами (выраженный им самим в принципе«сущность математики состоит в её свободе») является изначально порочной. Аименно, был обнаружен ряд теоретико-множественных антиномий: оказалось, что прииспользовании теоретико-множественных представлений некоторые утверждения могутбыть доказаны вместе со своими отрицаниями (а тогда, согласно правилам классическойлогики высказываний, может быть «доказано» абсолютно любое утверждение!).Антиномии ознаменовали собой полный провал программы Кантора.

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

Глава 1. Множества

 

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

 

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

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

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

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

/>

Рис 1.1.1

Пусть даны два множестваА и В (рис 1.1.1), тогда:

-  xÎA;

-  yÏA и yÏB;

Подмножество– понятие части в теории множеств. МножествоC является подмножеством множества B (рис. 1.1.1, обозначается CÌB) в случае, если каждый элементмножества C является также и элементом множестваB. Например, множество всех чётныхчисел является подмножеством множества всех целых чисел. Если C является подмножеством B, то Bназывается надмножеством C.

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

Понятия множества, элементаи принадлежности, которые на первый взгляд представляются интуитивно ясными,при ближайшем рассмотрении такую ясность утрачивают. Во-первых, проблематичнаотличимость элементов. Например, символы «е» и «а», которые встречаются на этойстранице, — это один элемент множества А или два разных элемента?Во-вторых, проблематична возможность (без дополнительных усилий) указать,принадлежит ли данный элемент данному множеству. Например, является ли число86958476921537485067857467 простым?

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

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

1.2 Способы заданиямножеств

Иррациональность чиселпоставила нас перед необходимостью работать с бесконечными множествами. Но насамом деле с бесконечностью приходится сталкиваться постоянно, например любаягеометрическая фигура – множество точек: отрезок, окружность, трапеция, конус…– все эти фигуры содержат бесконечное количество точек. Исходя из этого,возникает необходимость задания множеств, для удобства работы с ними. Чтобызадать множество, нужно указать, какие элементы ему принадлежат. Это можносделать различными способами. Укажем две наиболее употребительные формы задания(определения) множеств

- перечислениеэлементов, то есть указание всех элементов множества, которые принято заключатьв фигурные скобки. Если элементы: Ò, Â, Á, À, w — принадлежат множеству М, то записывается М={Ò, Â, Á, À, w };

- характеристическоесвойство, когда среди элементов какого-либо множества выделяются с помощьювысказывания, элементы, обладающие некоторым свойством (характеризующим этомножество). Пусть P(x) – какое-то свойство числа x. Тогда запись {x | P(x)} означает множество всех таких чисел,которые обладают свойством P(x). Например, множество {x | x2 – 3x +2=0} есть совокупность корней уравнения x2 – 3x +2=0, то есть это множество состоит из двух элементов: 2 и 1; {x | 3 < x < 7} – множество всех чисел, удовлетворяющих неравенствам 3 < x < 7; {x | x>12 и x<3} = Æ;

Однако при заданиимножеств как одним, так и другим способом могут возникнуть проблемы. Например,пусть множество А состоит из русских слов «стол», «мир» и символа «$» встандартной символике, то есть А={ стол, мир, $}. Множество А^, состоящее из таких же символов, но наанглийском языке, будет другим А^={ table,peace, $}. Так что нужно быть точным в перечислении (то естьзадании множеств путём перечисления). И ещё один пример, связанный с каким-либоучебником или книгой. Существует много экземпляров какой-то книги, если имеетсяв виду конкретная книга (например, принадлежащая определённому человеку),получим один вариант, если имелись ввиду все экземпляры, вышедшие из типографии(например, тираж 100 тыс. книг) – другой вариант, если же иметь ввиду толькосохранившиеся к настоящему моменту – третий вариант. Поэтому необходимо быть точнымпри задании множеств перечислением.

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

Y = {X | XÏX}

Если множество Y существует, то мы должны иметь возможность ответить наследующий вопрос: YÎY? Пусть YÎY, тогда должно выполняться свойство, задающее множество Y, то есть YÏY. Пусть YÏY, то,поскольку выполняется свойство, задающее Y, приходим к тому, что YÎY, а это противоречит предположению. Получается неустранимое логическоепротиворечие. Вот три способа избежать этого парадокса.

1. Ограничитьиспользуемые характеристические предикаты видом

P(x) = x Î A & Q(x),

где A – известное, заведомо существующее множество(универсум). Обычно при этом используют обозначение {x Î А | Q(x)}. Для Y универсум не указан, а потому Y множеством не является;

2. Теория типов.Объекты имеют тип 0, множества имеют тип 1, множества множеств — тип 2 и т. д. Y не имеет типа и множеством не является;

3. Характеристическоесвойство P(x) заданов виде вычислимой функции (алгоритма). Способ вычисления значения свойства X Î X не задан, а потому Y множествомне является.

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

1.3 Количествоэлементов в множестве

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

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

В теории множеств счётноемножество есть бесконечное множество, элементы которого возможно занумеровать натуральнымичислами. Более формально: множество X является счётным, если существует биекция/>, где />обозначаетмножество всех натуральных чисел. Другими словами, счётное множество — этомножество, равномощное множеству натуральных чисел.

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

Свойства:

1. Любоеподмножество счётного множества конечно или счётно;

2. Объединение конечногоили счётного числа счётных множеств счётно;

3. Прямоепроизведение конечного числа счётных множеств счётно;

4. Множество всехконечных подмножеств счётного множества счётно;

5. Множество всехподмножеств счётного множества континуально и, в частности, не являетсясчётным.

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

Свойства

· Два конечных множестваравномощны тогда и только тогда, когда они состоят из одинакового числа элементов.Т.е. для конечного множества понятие мощности совпадает с привычным понятиемколичества.

· Для бесконечныхмножеств мощность множества может совпадать с мощностью его собственногоподмножества, например />

Z (множество целых чисел) = {-3,-2,-1,0,1,2,3…};

N (множество натуральных чисел) = {1,2,3,4,5,6,7...};

/>0,1,-1,2,-2,3,-3… целых чисел столько же, сколько инатуральных

1,2, 3,4, 5, 6, 7…

· Теорема Канторагарантирует существование более мощного множества для любого данного: Множествовсех подмножеств множества A мощнее A, или | 2A | > | A |.

· С помощью кантороваквадрата можно также доказать следующее полезное утверждение: Декартовопроизведение бесконечного множества A с самим собой равномощно A.

Следуя Кантору, мощностьмножества называется кардинальным числом и обозначается мощность такогомножества A через | A | (сам Кантор использовал обозначение />). Иногда встречается обозначение />.

Мощность множестванатуральных чисел />обозначаетсясимволом />(«алеф-нуль»). Множество называется бесконечным, если егомощность />, таким образом, счётные множества — это «самые маленькие»из бесконечных множеств. Следующие кардинальные числа в порядке возрастанияобозначаются />.

Про множества,равномощные множеству всех вещественных чисел, говорят, что они имеют мощностьконтинуума, и мощность таких множеств обозначается символом c (continuum). Континуум-гипотеза утверждает, что />.

Для мощностей, как и вслучае конечных множеств, имеются понятия: равенство, больше, меньше. Т.е. длялюбых множеств A и B возможно только одно из трёх:

1. | A | = | B | илиA и B равномощны;

2. | A | > | B | илиA мощнее B, т. е. A содержит подмножество, равномощное B, но A и B неравномощны;

3. | A | < | B |или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и Bне равномощны.

Ситуация, в которой A и Bне равномощны и ни в одном из них нет части, равномощной другому, невозможна.Это следует из теоремы Цермело. Иначе это означало бы существование несравнимыхмежду собой мощностей (что в принципе возможно, если не принимать аксиомувыбора).

Ситуация, в которой | A |> | B | и | A | < | B |, невозможна по теореме Кантора — Бернштейна.

Два множества называютсяэквивалентными, если их элементы можно разбить на пары, так, чтобы вне этих парне останется ни одного элемента из этих множеств.

Множество правильныхположительных дробей содержит столько же элементов, сколько и натуральныхчисел.

Глава 2. Операции надмножествами

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

2.1 Сравнение множеств

/>множество элементаксиоматический принадлежность

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

/>.

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

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

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

2.2 Основные операциинад множествами

Ниже перечислены основныеоперации над множествами:

·  объединение:

/>

·  пересечение:

/>

·  разность:

/>

·  симметрическая разность:

/>

·  дополнение:

/>

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

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

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

/>

Рис. 2.2.1

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

/>

Рис 2.2.2

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

/>

Рис. 2.2.3

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

/>

Рис. 2.2.4

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

/>

Рис. 2.2.5

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

Пусть задан универсум 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= А. Аналогичные рассуждения нетруднопровести и для остальных равенств.

Докажем свойстводистрибутивности для операции объединения на диаграммах Эйлера-Венна (рис 2.3.1):

A È (B Ç C) = (A È B) Ç (A È C)

/>/>

Рис. 2.3.1

Глава 3. Аксиоматическая теориямножеств

 

3.1 Наивная теория множеств

В начале XX века Бертран Рассел, изучая наивную теорию множеств, пришел кпарадоксу (с тех пор известному как парадокс Рассела). Таким образом, былапродемонстрирована несостоятельность наивной теории множеств и связанной с нейканторовской программы стандартизации математики. А именно, был обнаружен рядтеоретико-множественных антиномий: оказалось, что при использованиитеоретико-множественных представлений некоторые утверждения могут быть доказанывместе со своими отрицаниями (а тогда, согласно правилам классической логикивысказываний, может быть «доказано» абсолютно любое утверждение!). Антиномииознаменовали собой полный провал программы Кантора.

После обнаружения антиномии Рассела часть математиков (например, Л. Э. Я.Брауэр и его школа) решила полностью отказаться от использованиятеоретико-множественных представлений. Другая же часть математиков,возглавленная Д. Гильбертом, предприняла ряд попыток обосновать ту частьтеоретико-множественных представлений, которая казалась им наименееответственной за возникновение антиномий, на основе заведомо надёжной финитнойматематики. С этой целью были разработаны различные аксиоматизации теориимножеств.

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

В настоящее время наиболее распространённой аксиоматической теориеймножеств является ZFC — теория Цермело — Френкеля с аксиомой выбора. Вопрос онепротиворечивости этой теории (а тем более — о существовании модели для неё)остаётся нерешенным.

3.2 Аксиомы теориимножеств

Сейчас у нас имеются всесредства, чтобы сформулировать систему аксиом теории множеств ZFC, в рамках которой можно изложить всеобщепринятые в современной математике способы рассуждений и не проходит ни одиниз известных теоретико-множественных парадоксов. Эта система позволяет строитьвсе математические объекты исходя из пустого множества. Представим систему аксиом,Цермело — Френкеля (ZF).

1. Аксиома существования пустого множества: Существует пустое множество Æ;

2. Аксиома существования пары: Если существуют множества а и b, то существует множество { a, b };

3. Аксиома суммы: Если существует множество X, тосуществует множество ÈX={a | a Î b для некоторого b Î X};

4. Аксиома бесконечности: Существует множество w = { 0, 1,…,n,… }, где 0 = Æ, n + 1 = n È { n };

5. Аксиома множества всех подмножеств: Если существует множество А, тосуществует множество:

Р(А) = { B | B Í A};

6. Аксиома замены: Если P(x, у) — некоторое условие на множества x, у, такое, что для любого множества x существуетне более одного множества у, удовлетворяющего Р(х, у), то для любогомножества а существует множество {b | P(c,b) для некоторого с Î а};

7. Аксиомаэкстенсиональности:

Два множества, имеющиеодинаковые элементы, равны, любое множество определяется своими элементами:

/>;

8. Аксиома регулярности:

Всякое непустое множествоx имеет элемент а Î х, для которого

a Ç x = Æ.

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

Покажем, как аксиоматика ZF позволяет определятьтеоретико-множественные операции.

1. Определим множество A È В, исходя из множеств А к В. По аксиоме существованияпары образуется множество {А, В}. С помощью аксиомы суммы получаем множество È{A, B}, которое по определению совпадает смножеством A È B.

2. Пересечение А Ç В множеств А и В определяется по аксиоме замены спомощью следующего свойства Р(х, у): х = у и х Î А. Имеем множество {b | P(c,b) и с Î В} = {b | с = b и с Î А и с ÎВ} = {c | с Î А и с ÎВ}.

3. Покажем, что из аксиом5 и 6 следует существование множества А2 = {(a, b) | a, b Î А} длялюбого множества А. Так как (a, b) = {{a}, {a, b}}, то А2 Í P(Р(А)). Пусть свойство Р(х, у) означает, что существуют такиеa, b Î А, что x ={{а}, {а, b}} и y = х. Тогда множество А2 равно {b | P(c,b), c Î Р(Р(А))} и по аксиоме 6 оносуществует.

Система аксиом ZFC образуется из ZF добавлением одной из следующих двухэквивалентных аксиом, которые, с одной стороны, являются наименее«очевидными», а с другой — наиболее содержательными,

1. Аксиома выбора.

Для любого непустогомножества А существует такое отображение j: Р(А) \ {Æ} ®A, чтоj (Х) Î X |для всех X Í А, X ¹ Æ.

2. Принцип полногоупорядочения. Для любого непустого множества А существует бинарное отношение £ на А, для которого {A, £} вполне упорядоченное множество.

В системе ZFC справедлив принцип трансфинитнойиндукции, являющийся обобщением принципа полной индукции: если {A, £} — вполне упорядоченное множество, Р(х) — некоторое свойство,то справедливость свойства Р(х) на всех элементах х Î А следует из того, что для любого z Î А выполнимость свойства Р на элементах у, где у < z, влечет выполнимость P(z):

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

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

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

4.1 Реализацияопераций над подмножествами заданного универсума U

Пусть универсум U – конечный, и число элементов в нёмпревосходит разрядности ЭВМ: |U | < n. Элементы универсума нумеруются: U= {u1… un}.Подмножество А универсума Uпредставляетсякодом (машинным словом или битовой шкалой) С, в котором

/> 1, если u1ÎА

С[i] =

0, если unÏА

где С[i] – это i-йразряд кода С;

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

4.2 Генерация всехподмножеств универсума

Во многих переборныхалгоритмах требуется последовательно рассмотреть все подмножества заданногомножества. В большинстве компьютеров целые числа представляются кодами вдвоичной системе счисления, причём число 2k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0является представлением пустого множества Æ, число 1 является представлением подмножества, состоящего изпервого элемента, и т.д. Следующий тривиальный алгоритм перечисляет всеподмножества n-элементного множества.

Алгоритм генерации всехподмножеств n-элементного множества:

Вход: n ³ 0 – мощность множества;

Выход: последовательность кодов подмножествi;

 

for i from0 to 2n – 1;

yieldi;

endfor;

Алгоритм выдаёт 2n различных целых чисел,следовательно, 2nразличных кодов. С увеличением числа увеличивается количество двоичныхразрядов, необходимых для его представления. Самое большое (из генерируемых)число 2n – 1 требует своего представленияровно n разрядов. Таким образом, всеподмножества генерируются, причём ровно по одному разу. Недостаток этогоалгоритма состоит в том, что порядок генерации подмножеств никак не связан с ихсоставом. Например, вслед за подмножеством с кодом 0111 будет перечисленоподмножество с кодом 1000.

4.3 Представлениемножеств упорядоченными списками

Если универсум оченьвелик (или бесконечен), а рассматриваемые подмножества универсума не оченьвелики, то представление с помощью битовых шкал не является эффективным с точкизрения экономии памяти. В этом случае множества представляются записью с двумяполями: информационным и указателем на следующий элемент. Весь списокпредставляется указателем на первый элемент.

elem= record;

i: info; {информационное поле};

n: ­n {указатель на следующий элемент};

endrecord;

При таком представлениитрудоёмкость операции Î составит О(n), а трудоёмкостьопераций Ì, Ç, È составит О(n×m), где n и m – мощности участвующих в операциимножеств.

Если элементы в спискахупорядочить, например, по возрастанию значения поля i, то трудоёмкость всех операций составит О(n). Эффективная реализация операцийнад множествами, представленными в виде упорядоченных списков, основана навесьма общем алгоритме, известном как алгоритм слияния. Алгоритм типа слиянияпараллельно просматривает два множества, представленных упорядоченнымисписками, причём на каждом шаге продвижение происходит в том множестве, в которомтекущий элемент меньше.

Заключение

Курсовой проект выполненна тему «Элементы теории множеств». В нём рассмотрены вопросы:

—   Множества: элементы и множества,способы задания множеств, количество элементов в множестве;

—   Операции над множествами: сравнениемножеств, основные операции над множествами, свойства операций над множествами;

—   Аксиоматическая теория множеств:наивная теория множеств, аксиомы теории множеств;

—   Представление множеств в ЭВМ:Реализация операций над подмножествами заданного универсума U, Генерация всех подмножеств универсума, Представлениемножеств упорядоченными списками;

На основании найденнойинформации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно даютпредставление о теории множеств. При выполнении работы были приведены примерымножеств, а также и те примеры, которые приводят к противоречиям при различномспособе их задания. При исследовании свойств операций над множествами я доказалодно из свойств (дистрибутивность) с помощью диаграмм Эйлера-Венна. И я считаю,что в последней главе необходимо было указать на связь между множествами и ихпредставлением на ЭВМ, особенно это важно, на мой взгляд, для специальностиматематика-программиста.

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

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

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

1. Дискретнаяматематика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.

2. Жолков С.Ю.Математика и информатика для гуманитариев: Учебник. – М.: Гардарики, 2002. –531 с.

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

4. Шипачёв В.С.Высшая математика. Учеб. Для вузов. – 4-е изд., стер. – М.: Высшая школа. 1998.– 479 с.

5. Материал изВикипедии — свободной энциклопедии. Георг Кантор (http://www.peoples.ru/science/mathematics/kantor/)