86314 (612717), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

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

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

4. Аксиома бесконечности: Существует множество = 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 следует существование множества А² = {(a, b) a, b А} для любого множества А. Так как (a, b) = {{a}, {a, b}}, то А² P(Р(А)). Пусть свойство Р(х, у) означает, что существуют такие a, b А, что x = {{а}, {а, b}} и y = х. Тогда множество А² равно {b P(c,b), c Р(Р(А))} и по аксиоме 6 оно существует.

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

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

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

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

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

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

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

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

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

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

1, если u₁А

С_[i] =

0, если u_nА

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

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

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

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

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

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

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

for i from 0 to 2ⁿ – 1;

yield i;

end for;

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

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

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

elem = record;

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

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

end record;

При таком представлении трудоёмкость операции составит О(n), а трудоёмкость операций , , составит О(nm), где 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/)

Размещено на Allbest.ru

Характеристики

Список файлов курсовой работы