Головна
Банківська справа  |  БЖД  |  Біографії  |  Біологія  |  Біохімія  |  Ботаніка та с/г  |  Будівництво  |  Військова кафедра  |  Географія  |  Геологія  |  Екологія  |  Економіка  |  Етика  |  Журналістика  |  Історія техніки  |  Історія  |  Комунікації  |  Кулінарія  |  Культурологія  |  Література  |  Маркетинг  |  Математика  |  Медицина  |  Менеджмент  |  Мистецтво  |  Моделювання  |  Музика  |  Наука і техніка  |  Педагогіка  |  Підприємництво  |  Політекономія  |  Промисловість  |  Психологія, педагогіка  |  Психологія  |  Радіоелектроніка  |  Реклама  |  Релігія  |  Різне  |  Сексологія  |  Соціологія  |  Спорт  |  Технологія  |  Транспорт  |  Фізика  |  Філософія  |  Фінанси  |  Фінансові науки  |  Хімія

Елементи теорії множин - Математика

Федеральне агентство з освіти

ФГТУ ВПО

Чуваська державний університет ім. І.М. Ульянова

Алатирський філія

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

Кафедра вищої математики та інформаційних технологій

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

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

Елементи теорії множин

Виконав студент

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, яке називається універсальним безліччю (або універсумом).

Якщо об'єкт х є елементом множини М, то кажуть, що х належить М. Позначення: хIМ. В іншому випадку кажуть, що х не належить М. Позначення: хIМ. Зауважимо, що елементи множини самі можуть бути множинами. Наприклад, безліч груп студентів складається з елементів (груп), які, в свою чергу, складаються зі студентів.

Рис 1.1.1

Нехай дано дві множини А і В (рис 1.1.1), тоді:

- XIA;

- YIA і yIB;

Підмножина - поняття частини в теорії множин. Безліч C є підмножиною множини B (рис. 1.1.1, позначається CIB) у випадку, якщо кожен елемент множини C є також і елементом множини B. Наприклад, множина всіх парних чисел є підмножиною множини всіх цілих чисел. Якщо C є підмножиною B, то B називається надбезліччю C.

Зазвичай безлічі позначають великими літерами латинського алфавіту, а елементи множин - малими літерами.

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

Множини, як об'єкти, можуть бути елементами інших множин. Безліч, елементами якого є множини, зазвичай називається класом або сімейством.

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

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

Ірраціональність чисел поставила нас перед необхідністю працювати з нескінченними множинами. Але насправді з нескінченністю доводиться стикатися постійно, наприклад будь-яка геометрична фігура - безліч точок: відрізок, окружність, трапеція, конус ... - всі ці фігури містять нескінченну кількість точок. Виходячи з цього, виникає необхідність завдання множин, для зручності роботи з ними. Щоб поставити безліч, потрібно вказати, які елементи йому належать. Це можна зробити різними способами. Вкажемо дві найбільш уживані форми завдання (визначення) множин

- Перерахування елементів, тобто вказівка всіх елементів множини, які прийнято укладати в фігурні дужки. Якщо елементи: O, A, A, A, w - належать безлічі М, то записується М = {O, A, A, A, w};

- Характеристичне властивість, коли серед елементів якого-небудь безлічі виділяються за допомогою висловлювання, елементи, що володіють деяким властивістю (характеризує це безліч). Нехай P (x) - якась властивість числа x. Тоді запис {x | P (x)} означає множину всіх таких чисел, які мають властивість P (x). Наприклад, безліч {x | x2- 3x + 2 = 0} є сукупність коренів рівняння x2- 3x + 2 = 0, тобто це множина складається з двох елементів: 2 і 1; {X | 3 12 і x <3} = ?;

Однак при завданні множин як одним, так і іншим способом можуть виникнути проблеми. Наприклад, нехай безліч А складається з російських слів «стіл», «мир» і символу «$» в стандартній символіці, тобто А = {стіл, мир, $}. Безліч А ^, що складається з таких же символів, але англійською мовою, буде іншим А ^ = {table, peace, $}. Так що потрібно бути точним у перерахуванні (тобто завданні множин шляхом перерахування). І ще один приклад, пов'язаний з яким-небудь підручником або книгою. Існує багато примірників якоїсь книги, якщо мається на увазі конкретна книга (наприклад, що належить певній людині), отримаємо один варіант, якщо малися на увазі всі екземпляри, що вийшли з друкарні (наприклад, тираж 100 тис. Книг) - інший варіант, якщо ж мати на увазі тільки збереглися до справжнього моменту - третій варіант. Тому необхідно бути точним при завданні множин перерахуванням.

Але й спосіб завдання множини за допомогою характеристичних властивостей елементів таїть деякі небезпеки, оскільки "неправильно" задані властивості можуть привести до протиріччя. Наведемо один з найбільш типових теоретико-множинних парадоксів - парадокс Рассела. Розглянемо безліч всіх множин, що не містять себе в якості елемента:

Y = {X | XIX}

Якщо безліч Y існує, то ми повинні мати можливість відповісти на наступне питання: YIY? Нехай YIY, тоді має виконуватися властивість, що задає безліч Y, тобто YIY. Нехай YIY, то, оскільки виконується властивість, що задає Y, приходимо до того, що YIY, а це суперечить припущенню. Виходить непереборні логічне протиріччя. Ось три способи уникнути цього парадоксу.

1. Обмежити використовувані характеристичні предикати видом

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

де A - відоме, свідомо існуюче безліч (універсум). Зазвичай при цьому використовують позначення {x I А | Q (x)}. Для Y універсум не вказаний, а тому Y безліччю не є;

2. Теорія типів. Об'єкти мають тип 0, безлічі мають тип 1, безлічі множин - тип 2 і т. Д. Y не має типу та безліччю не є;

3. Характеристичне властивість P (x) задано у вигляді обчислюваної функції (алгоритму). Спосіб обчислення значення властивості X I 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 E 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

Симетрична різниця ADB (рис. 2.2.4)

Рис. 2.2.4

Доповнення до безлічі A називається множина всіх елементів, що не входять в безліч A (рис 3.2.5)

Рис. 2.2.5

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

Нехай заданий універсум U. Тоді для всіх A, B, C I U виконуються наступні властивості (табл. 2.3.1):

Властивості операцій над множинами

 Для об'єднання (E) Для перетину (C)

 Ідемпотентність

 A E A = A A C A = A

 Комутативність

 A E B = B E A A C B = B C A

 Асоціативність

 A E (B E C) = (A E B) E CA C (B C C) = (A C B) C C

 Дистрибутивність

 A E (B C C) = (A E B) C (A E C) A C (B E C) = (A C B) E (A C C)

 Поглинання

 (A C B) E A = A (A E B) C A = A

 Властивості нуля

 A E ? = A A C ? = ?

 Властивості одиниці

 A E U = U A C U = U

 Інволютивними

 = A

 Закони де Моргана

 Властивості доповнення

 Вираз для різниці

 Вираз для симетричної різниці

У справедливості перерахованих властивостей можна переконатися різними способами. Наприклад, намалювати діаграми Ейлера для лівої і правої частин рівності і переконатися, що вони співпадають, або ж провести формальне міркування для кожного рівності. Розглянемо для прикладу першу рівність: A E A = А. Візьмемо довільний елемент х, що належить лівій частині рівності, х I A E A. За визначенням операції об'єднання E маємо хI A E хI A. У кожному разі хI A. Взявши довільний елемент з множини в лівій частині рівності, виявили, що він належить безлічі в правій частині. Звідси за визначенням включення множин отримуємо, що A E A I А. Нехай тепер хI A. Тоді, очевидно, вірно хI A E хI A. Звідси за визначенням операції об'єднання маємо х I A E A. Таким чином, А I A E A . Отже, за визначенням рівності множин, A E A = А. Аналогічні міркування неважко провести і для інших рівностей.

Доведемо властивість дистрибутивности для операції об'єднання на діаграмах Ейлера-Венна (рис 2.3.1):

A E (B C C) = (A E B) C (A E C)

Рис. 2.3.1

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

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

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

Після виявлення антиномії Рассела частина математиків (наприклад, Л. Е. Я. Брауер і його школа) вирішила повністю відмовитися від використання теоретико-множинних уявлень. Інша ж частина математиків, очолена Д. Гильбертом, зробила ряд спроб обґрунтувати ту частину теоретико-множинних уявлень, яка здавалася їм найменш відповідальною за виникнення антиномій, на основі свідомо надійної финитной математики. З цією метою були розроблені різні аксиоматизации теорії множин.

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

В даний час найбільш поширеною аксіоматичної теорією множин є ZFC - теорія Цермело - Френкеля з аксіомою вибору. Питання про несуперечності цієї теорії (а тим більше - про існування моделі для неї) залишається невирішеним.

3.2 Аксіоми теорії множин

Зараз у нас є всі засоби, щоб сформулювати систему аксіом теорії множин ZFC, в рамках якої можна викласти всі загальноприйняті в сучасній математиці способи міркувань і не проходить жоден з відомих теоретико-множинних парадоксів. Ця система дозволяє будувати всі математичні об'єкти виходячи з порожньої безлічі. Уявімо систему аксіом, Цермело - Френкеля (ZF).

1. Аксіома існування порожнього безлічі: Існує порожній безліч ?;

2. Аксіома існування пари: Якщо існують множини а й b, то існує безліч {a, b};

3. Аксіома суми: Якщо існує безліч X, то існує безліч EX = {a | a I b для деякого b I X};

4. Аксіома нескінченності: Існує безліч w = {0, 1, ..., n, ...}, де 0 = ?, n + 1 = n E {n};

5. Аксіома безлічі всіх підмножин: Якщо існує безліч А, то існує безліч:

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

6. Аксіома заміни: Якщо P (x, у) - деяка умова на безлічі x, у, таке, що для будь-якого безлічі x існує не більше одного безлічі у, задовольняє Р (х, у), то для будь-якого безлічі а існує безліч {b | P (c, b) для деякого з I а};

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

Два безлічі, що мають однакові елементи, рівні, будь-яке безліч визначається своїми елементами:

;

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

Всяке непорожнє безліч x має елемент а I х, для якого

a C x = ?.

З аксіоми регулярності випливає, що кожне безліч виходить на деякому кроці "регулярного процесу" утворення безлічі всіх підмножин, що починається з ? і подібного побудови натуральних чисел з пустого безлічі по аксіомі нескінченності. Це означає, що будь-який елемент будь-якого безлічі є множиною, сконструйованим з пустого множини.

Покажемо, як аксіоматика ZF дозволяє визначати теоретико-множинні операції.

1. Визначимо безліч A E В, виходячи з множин А до В. По аксіомі існування пари утворюється безліч {А, В}. За допомогою аксіоми суми отримуємо безліч E {A, B}, яке за визначенням збігається з безліччю A E B.

2. Перетин А C В множин А і В визначається за аксіомі заміни за допомогою наступного властивості Р (х, у): х = у і х I А. Маємо безліч {b | P (c, b) і з I В} = {b | з = b і з I А і з IВ} = {c | з I А і з IВ}.

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

Система аксіом ZFC утворюється з ZF додаванням однієї з наступних двох еквівалентних аксіом, які, з одного боку, є найменш "очевидними", а з іншого - найбільш змістовними,

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

Для будь-якого непорожнього безлічі А існує таке відображення j: Р (А) \ {?} ®A, що j (Х) I X | для всіх X I А, X ? ?.

2. Принцип повного упорядкування. Для будь-якого непорожнього безлічі А існує бінарне відношення ? на А, для якого {A, ?} цілком упорядкована множина.

В системі ZFC справедливий принцип трансфінітної індукції, що є узагальненням принципу повної індукції: якщо {A, ?} - цілком упорядкована множина, Р (х) - деяка властивість, то справедливість властивості Р (х) на всіх елементах х I А випливає з того, що для будь-якого z I А здійснимість властивості Р на елементах у, де у Глава 4. Подання множин в ЕОМ

Термін «уявлення» (ще вживають термін «реалізація») стосовно до програмування означає наступне. Задати уявлення будь-якого об'єкта (у даному випадку множини) - значить описати в термінах використовуваної системи програмування структуру даних, використовувану для зберігання інформації про представляемом об'єкті, і алгоритми над вибраними структурами даних, які реалізують властиві даному об'єкту операції. У даній роботі передбачається, що в використовуваної системі програмування доступні такі загальновживані структури даних, як масиви, структури (або запису) і покажчики. Таким чином, стосовно до множинам визначення подання на увазі опис способу зберігання інформації про приналежність елементів безлічі і опис алгоритмів для обчислення об'єднання, перетину та інших введених операцій.

Слід підкреслити, що, як правило, один і той же об'єкт може бути представлений багатьма різними способами, причому не можна вказати спосіб, який є найкращим для всіх можливих випадків. В одних випадках вигідно використовувати одне подання, а в інших - інше. Вибір уявлення залежить від цілого ряду чинників: особливостей акредитуючої об'єкта, складу і відносної частоти використання операцій в конкретній задачі і т. Д. Уміння вибрати найбільш підходяще для даного випадку подання є основою мистецтва практичного програмування. Хороший програміст відрізняється тим, що він знає багато різних способів подання і вміло вибирає найбільш підходящий.

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

Нехай універсум U - кінцевий, і число елементів у ньому перевершує розрядності ЕОМ: | U | 1, якщо u1IА

С [i] =

0, якщо unIА

де С [i] - це i-й розряд коду С;

Код перетину множин А і В є поразрядное логічне твір коду безлічі А і коду безлічі В. Код об'єднання множин А і В є поразрядное логічна сума коду безлічі А і коду безлічі В. У більшості ЕОМ для цих операцій є відповідні машинні команди. Таким чином, операції над невеликими множинами виконуються досить ефективно. Якщо потужність універсуму перевершує розмір машинного слова, але не дуже велика, то для представлення множин використовуються масиви бітових шкал. У цьому випадку операції над множинами реалізуються за допомогою циклів за елементами масиву.

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

У багатьох переборних алгоритмах потрібно послідовно розглянути всі підмножини заданої множини. У більшості комп'ютерів цілі числа представляються кодами в двійковій системі числення, причому число 2k- 1 представляється кодом, що містить k одиниць. Таким чином, число 0 є поданням порожнього безлічі ?, число 1 є поданням підмножини, що складається з першого елемента, і т.д. Наступний тривіальний алгоритм перераховує всі підмножини n-елементного безлічі.

Алгоритм генерації всіх підмножин n-елементного безлічі:

Вхід: n ? 0 - потужність множини;

Вихід: послідовність кодів підмножин i;

for i from 0 to 2n- 1;

yield i;

end for;

Алгоритм видає 2nразлічних цілих чисел, отже, 2nразлічних кодів. Зі збільшенням числа збільшується кількість двійкових розрядів, необхідних для його подання. Найбільше (з генеруються) число 2n- 1 вимагає свого представлення рівно n розрядів. Таким чином, всі підмножини генеруються, причому рівно по одному разу. Недолік цього алгоритму полягає в тому, що порядок генерації підмножин ніяк не пов'язаний з їх складом. Наприклад, слідом за підмножиною з кодом 0111 буде перераховано підмножина з кодом 1000.

4.3 Подання множин впорядкованими списками

Якщо універсум дуже великий (або нескінченний), а розглядаються підмножини універсуму не дуже великі, то уявлення за допомогою бітових шкал не є ефективним з точки зору економії пам'яті. У цьому випадку безлічі представляються записом з двома полями: інформаційним і покажчиком на наступний елемент. Весь список представляється покажчиком на перший елемент.

elem = record;

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

n: n {покажчик на наступний елемент};

end record;

При такому поданні трудомісткість операції I складе О (n), а трудомісткість операцій I, C, E складе О (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/)
Збитки фірми і їх класифікація
Збитки фірми і їх класифікація Зміст Введення 1. Класифікація потенційних ризиків виникнення збитків 2. Класифікація можливих збитків і їх оцінка 3. Оцінка можливих збитків фірми Список використаних джерел Введення Управління ризиками, як і багато які інші види ділової активності, - це процес,

Організація роботи "Азіатсько-Тихоокеанського Банку"
Зміст Глава 1. Історія «Азіатсько-Тихоокеанського банку» Глава 2. Відкриття і закриття, ведення банківських рахунків за вкладами фізичних осіб у валюті Російської Федерації та іноземній валюті 2.1 Порядок нарахування відсотків за вкладами 2.2 Відкриття банківського рахунку фізичній особі 2.3

Сучасні підходи до інтерпретації економічної природи прибутку
Сучасні підходи до інтерпретації економічної природи прибутку Одним з ключових питань фінансів суб'єктів господарювання є визначення фінансового результату діяльності. Адже прибуток вважається однією з найбільш неоднозначних економічних категорій, оскільки складність його визначення

Статистичне вивчення реалізації продукції птахівництва
Проектне завдання №6 До курсової роботи з статистики на тему: Статистичне вивчення реалізації продукції птахівництва 2007р.

Центральний Банк Росії і його роль в проведенні єдиної грошово-кредитної політики
Суть і походження центральних банків. З 15-16 вв. в Англії, в Італії, в Німеччині, в Нідерландах, де почав зароджуватися буржуазний лад, капіталістичні відносини, стала формуватися банківська система. І формування банківської системи завжди проходило як природним шляхом, так і шляхом різних

Соціальна політика Республіки Білорусь: основні напрями та механізми реалізації
РЕФЕРАТ Курсова робота: 35 с., 2 рис., 21 джерел, 1 табл., 1 дод. СОЦІАЛЬНА ПОЛІТИКА, СОЦІАЛЬНЕ РІВНІСТЬ, СОЦІАЛЬНЕ ПАРТНЕРСТВО, ЕФЕКТИВНІСТЬ СОЦІАЛЬНОЇ ПОЛІТИКИ, ПОКАЗНИКИ РЕЗУЛЬТАТИВНОСТІ СОЦІАЛЬНОЇ ПОЛІТИКИ, РІВЕНЬ ЖИТТЯ, ЯКІСТЬ ЖИТТЯ Об'єкт дослідження - соціальна політика держави, основні

Проблеми розвитку АПК в Красноярському краї
Зміст Введення 1. Проблеми розвитку сільської економіки і підходи до їх вирішення 1.1 Особливості та закономірності розвитку агропромислового комплексу 1.2 Невирішені проблеми у розвитку агропромислового комплексу та форми їх прояву 1.3 Підходи до вирішення проблем розвитку агропромислового

© 2014-2022  8ref.com - українські реферати