Курсовая работа (т): Основы теории множеств и ее реализация в языке программирования Паскаль

Основы теории множеств и ее реализация в языке программирования Паскаль

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО»

Кафедра информатики и программирования

основы теории множеств и ее реализация в языке программирования паскаль

КУРСОВАЯ РАБОТА

студентки 2 курса 261 группы

направления 050100.62 Педагогическое образование (профиль Информатика)

факультета компьютерных наук и информационных технологий

Чечёнковой Елены Анатольевны

Саратов 2015

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ТЕОРИЯ. МНОЖЕСТВА, ОПЕРАЦИИ НАД МНОЖЕСТВАМИ, МОЩНОСТЬ МНОЖЕСТВА

.1      Понятие множества

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

.3      Мощность множества

ГЛАВА 2. МНОЖЕСТВА В ПАСКАЛЕ. ОПИСАНИЕ, ОПЕРАЦИИ

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

.2 Построение множества в паскале

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

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

Объект исследования: теоритические основы информатики.

Предмет исследования: множества.

Цель курсовой работы: изучить основы теории множеств и рассмотреть ее реализацию в языке программирования.

Задачи исследования:

·        Обзор литературы;

·        Раскрыть, что представляет собой множество, какие операции применяются при работе с множествами;

·        Рассмотреть представление, построение множеств и применение операций над множествами в паскале.

ГЛАВА 1. теория. множества, операции над множествами, мощность множества

1.1    Понятие множества

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

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

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

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

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

 ;

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

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

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

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

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

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

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

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

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

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

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

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

|A| = |B|, |A| < |B|, |A| > |B|.

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

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

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

)        Разность:

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

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

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

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

Объединением двух множеств А и В (Рисунок 2) - называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств A и B

Рисунок 2. Объединение множеств

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

Рисунок 3. Пересечение множеств

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

Рисунок 4. Разность множеств

Симметрическая разность (Рисунок 5) - теоретико-множественная операция, результатом которой является новое множество, включающее все элементы исходных множеств, не принадлежащие одновременно обоим исходным множествам. Другими словами, если есть два множества A и B, их симметрическая разность есть объединение элементов A, не входящих в B, с элементами B не входящими в A. На письме для обозначения симметрической разности множеств A и B используется обозначение

 так же, реже используется обозначение:  [10]

Рисунок 6. Симметрическая разность множеств

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

Рисунок 7. Дополнение множества

Таким образом, выяснили, что с множествами можно выполнять ряд операций: сравнение, объединение, пересечение, разность, симметрическая разность и дополнение.

1.3 Мощность множества

Понятие мощности множества возникает при сравнении множеств по числу элементов. Мощность множества, кардинальное число множества (лат. <https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%82%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA> cardinalis ← cardo - главное обстоятельство, стержень, сердцевина) - характеристика множеств <https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE> (в том числе бесконечных <https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%81%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE>), обобщающая понятие количества (числа) элементов <https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE> конечного множества.

В основе этого понятия лежат естественные представления о сравнении множеств:

1.      Любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция <https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F>), содержат одинаковое количество элементов (имеют одинаковую мощность).

2.      Обратно: множества, равные по мощности, должны допускать такое взаимно-однозначное соответствие.

3.      Часть множества не превосходит полного множества по мощности (то есть по количеству элементов).

До построения теории мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.[19]

Мощность множеств позволяет сравнивать бесконечные множества. Например, счётные множества <https://ru.wikipedia.org/wiki/%D0%A1%D1%87%D1%91%D1%82%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE> являются самыми «маленькими» бесконечными множествами.

Мощность множества  обозначается через . Сам Кантор <https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D0%BD%D1%82%D0%BE%D1%80,_%D0%93%D0%B5%D0%BE%D1%80%D0%B3_%D0%A4%D0%B5%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D0%BD%D0%B4_%D0%9B%D1%8E%D0%B4%D0%B2%D0%B8%D0%B3_%D0%A4%D0%B8%D0%BB%D0%B8%D0%BF%D0%BF> использовал обозначение . Иногда встречаются обозначения  и card (A). [2]

·              Мощность множества натуральных чисел  обозначается символом  («алеф <https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B5%D1%84_(%D0%B1%D1%83%D0%BA%D0%B2%D0%B0)>-нуль»). Множество называется бесконечным, если его мощность  (не меньше мощности множества натуральных чисел), таким образом, счётные множества <https://ru.wikipedia.org/wiki/%D0%A1%D1%87%D1%91%D1%82%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE> - это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются (где индекс пробегает все порядковые числа <https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE>). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.

·              Про множества, равномощные множеству всех вещественных чисел <https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE>, говорят, что они имеют мощность континуума <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B8%D0%BD%D1%83%D1%83%D0%BC_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2)>, и мощность таких множеств обозначается символом . Предположение о том, что , называется континуум-гипотезой <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B8%D0%BD%D1%83%D1%83%D0%BC-%D0%B3%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0>.