У дома » Направи си сам » Тествайте числови набори

Тествайте числови набори

Федерална агенция за образование

Чувашки държавен университет И.Н. Улянова

Клон Алатир

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

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

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

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

Елементи на теорията на множествата

Извършва се от ученик

1 курс

групи - AFT 61-06

Научен ръководител

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

Въведение

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

До втората половина на 19 век понятието "множество" не се смяташе за математическо (много книги на рафт, много човешки добродетели и т.н. - всичко това са чисто ежедневни обороти на речта). Ситуацията се промени, когато немският математик Георг Кантор (фиг. 1) разработи своята програма за стандартизация на математиката, в която всеки математически обект трябваше да се окаже едно или друго „множество“.

Например, естествено число, според Кантор, трябва да се разглежда като множество, състоящо се от един елемент на друго множество, наречено "естествена серия" - което от своя страна само по себе си е множество, което удовлетворява така наречените аксиоми на Пеано . В същото време Кантор даде малко дефиниращи дефиниции на общото понятие за „множество“, което той смяташе за централно за математиката, като „множеството е много неща, мислими като едно“ и т.н. „теория на множествата“ (това терминът се появи много по-късно), и преподаванеотносно комплектите ( Mengenlehre).

Програмата на Кантор предизвиква силни протести от страна на много от съвременните му големи математици. С непримиримото си отношение към него особено се отличаваше Леополд Кронекер, който вярваше, че само естествените числа и това, което пряко се свежда до тях, могат да се считат за математически обекти (известна е фразата му, че „Бог създаде естествените числа, а всичко останало е дело на човешки ръце ”). Някои други математици обаче - по-специално Готлоб Фреге и Дейвид Хилберт - подкрепиха Кантор в намерението му да преведе цялата математика на теоретико-множествен език.

Скоро обаче става ясно, че отношението на Кантор към неограничения произвол при работа с множества (изразено от самия него в принципа „същността на математиката е в нейната свобода“) е порочно по своята същност. А именно, бяха открити редица антиномии на теория на множествата: оказа се, че когато се използват представяния на теория на множествата, някои твърдения могат да бъдат доказани заедно с техните отрицания (и тогава, според правилата на класическата пропозиционална логика, абсолютно всяко твърдение може да бъде „доказано!“). Антиномиите бележат пълния провал на програмата на Кантор.

Въпреки това Кантор се смята за основател на теорията на множествата и има голям принос в съвременната математика. Той притежава следната характеристика на понятието "множество": Наборът е асоциация на определени, различни обекти, наречени елементи на набор, в едно цяло.

Глава 1

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

Понятията набор и елемент от набор се отнасят до понятия, които не са изрично дефинирани, като например точка и линия. Думите "колекция", "семейство", "система", "комплект" и др. - синоними на думата "много". Това се дължи на факта, че някои концепции в математиката трябва да бъдат първоначални, да служат като онези „тухли“, които формират общата теория. Ние само определяме как тези първоначални понятия се отнасят, без да говорим за природата на разглежданите обекти. Човешкото мислене е устроено по такъв начин, че светът се представя като състоящ се от отделни "обекти". За философите отдавна е ясно, че светът е единно неразделно цяло и изборът на обекти в него не е нищо повече от произволен акт на нашето мислене, което ни позволява да формираме картина на света, достъпна за рационален анализ. Но както и да е, изборът на обекти и техните набори е естествен (или дори единственият възможен) начин за организиране на нашето мислене, така че не е изненадващо, че той е в основата на основния инструмент за описание на точното знание - математиката.

Може да се каже, че няколко -това е всеки определен набор от обекти. Обектите, които съставляват едно множество, се наричат негови елементи.Елементите на комплекта са различни и различими един от друг. Примери за множества могат да бъдат: множество от хора, животни, растения на нашата планета, както и множество N от естествени числа 1, 2, 3, ..., множество P от прости числа 2, 3, 5, 7, 11, ... Набор Z от цели числа:…, -2, -1, 0, 1, 2, ..., набор от Rреални числа и т.н. Множество без елементи се нарича празно. Забележка: Æ. Празно множество е подмножество на всяко множество. Мощността на празното множество е нула. Концепцията за празно множество (като концепцията за "нула") възниква от необходимостта резултатът от всяка операция върху множества също да бъде множество.

Обикновено при конкретни разсъждения елементите на всички множества се вземат от едно, достатъчно широко множество U, което се нарича универсално множество (или вселена).

Ако обект x е елемент от множеството M, тогава x се казва, че принадлежи на M. Запис: xОM. В противен случай казваме, че x не принадлежи на M. Нотация: xÏM. Обърнете внимание, че самите елементи на набор могат да бъдат множества. Например набор от групи ученици се състои от елементи (групи), които от своя страна се състоят от ученици.

Нека са дадени две множества A и B (Фигура 1.1.1), тогава:

Подмножество – понятието част в теорията на множествата. Множеството C е подмножество на множеството B (фиг. 1.1.1, обозначено като CÌB), ако всеки елемент от множеството C е също елемент от множеството B. Например множеството от всички четни числа е подмножество на набор от всички цели числа. Ако C е подмножество на B, тогава B се нарича надмножество на C.

Обикновено множествата се обозначават с главни букви на латинската азбука, а елементите на множествата се обозначават с малки букви.

Понятията набор, елемент и членство, които на пръв поглед изглеждат интуитивно ясни, губят такава яснота при по-внимателно разглеждане. Първо, разграничаването на елементите е проблематично. Например знаците "e" и "a", които се срещат на тази страница, са един елемент от набора АИли два различни елемента? Второ, проблематично е да можете (без допълнителни усилия) да посочите дали даден елемент принадлежи към дадено множество. Например числото 86958476921537485067857467 просто ли е?

Множествата, както и обектите, могат да бъдат елементи на други множества. Обикновено се нарича множество, чиито елементи са множества класили семейство.

Семействата от множества обикновено се означават с главни "ръкописни" букви от латинската азбука, за да се разграничат от множества, които не съдържат множества като елементи.

1.2 Начини за дефиниране на множества

Ирационалността на числата ни наложи да работим с безкрайни множества. Но всъщност човек трябва да се занимава с безкрайност през цялото време, например всяка геометрична фигура е набор от точки: сегмент, кръг, трапец, конус ... - всички тези фигури съдържат безкраен брой точки . Въз основа на това е необходимо да се уточнят комплекти, за удобство при работа с тях. За да дефинирате набор, трябва да посочите кои елементи принадлежат към него. Това може да стане по различни начини. Нека посочим двете най-често използвани форми за специфициране (дефиниране) на множества

Изброяване на елементите, т.е. индикация за всички елементи на множеството, които обикновено са затворени във фигурни скоби. Ако елементите: Ò, Â, Á, À, w - принадлежат на множеството M, то M=(Ò, Â, Á, À, w);

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

Въпреки това, когато дефинирате набори по един или друг начин, могат да възникнат проблеми. Например, нека множеството A се състои от руските думи "таблица", "свят" и символа "$" в стандартната символика, т.е. A = (таблица, свят, $). Наборът A^, състоящ се от същите знаци, но на английски, ще бъде друг A^ = (таблица, мир, $). Така че човек трябва да бъде прецизен при изброяването (т.е. уточняване на набори чрез изброяване). И още един пример, свързан с някой учебник или книга. Има много копия на книга, ако имаме предвид конкретна книга (например принадлежаща на определено лице), получаваме една опция, ако имаме предвид всички копия, излезли от печатницата (например тираж 100 хиляди книги) - друг вариант, ако имаме предвид само тези, които са оцелели до настоящия момент, е третият вариант. Ето защо е необходимо да бъдете прецизни, когато задавате набори чрез изброяване.

Но методът за определяне на набор с помощта на характерните свойства на елементите е изпълнен с някои опасности, тъй като „неправилно“ определени свойства могат да доведат до противоречие. Ето един от най-типичните парадокси на теорията на множествата - Парадоксът на Ръсел.Разгледайте множеството от всички множества, които не съдържат себе си като елемент:

Ако множеството 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 Брой елементи в набор

Мощността на набор е обобщение на понятието количество (броят елементи на набор), което има смисъл за всички множества, включително безкрайните.

Има големи, има по-малки безкрайни множества, сред тях изброимото множество е най-малкото.

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

Изброимо множество е "най-малкото" безкрайно множество, т.е. във всяко безкрайно множество има изброимо подмножество.

Имоти:

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(континуум). Хипотезата за континуума гласи, че.

За степените, както в случая с крайните множества, има понятия: равенство, повече, по-малко. Тези. за всякакви множества A и B е възможно само едно от трите:

1. | A | = | б | или А и В са еквивалентни;

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

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

Ситуация, в която А и Б не са еднакво силни и никой от тях няма част, която да е еквивалентна на другата, е невъзможна. Това следва от теоремата на Цермело. В противен случай това би означавало съществуването на несравними правомощия (което по принцип е възможно, ако не се приеме аксиомата за избор).

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

Две множества се наричат еквивалентни, ако техните елементи могат да бъдат разделени на двойки, така че нито един елемент от тези множества да не остане извън тези двойки.

Множеството от правилни положителни дроби съдържа толкова елементи, колкото са естествените числа.

Глава 2

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

2.1 Сравнение на комплекти

набор елемент аксиоматично членство

Набор A се съдържа в набор B (множество B включва множество A), ако всеки елемент от A е елемент от B:

Ако и, тогава A се нарича правилно подмножество на B. Забележете, че. А-приори.

Две множества се наричат равни, ако са подмножества едно на друго:

Теорема за сравнение на множество. За всякакви множества A и B има една и само една от следните възможности: |A| = |B|, |A|<|B|, |A|>|B|.

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

Следват основните операции върху множества:

· Съюз:

пресичане:

разлика:

симетрична разлика:

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

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

За по-добро разбиране на значението на тези операции се използват диаграми на Ойлер-Вен, които представят резултатите от операциите върху геометрични фигури като множества от точки.

Обединението на две множества AÈB (фиг. 2.2.1) е третото множество, всеки елемент от което принадлежи към поне едно от множествата A и B

Пресечната точка на множества A ∩ B (фиг. 2.2.2) е множество, състоящо се от всички онези елементи, които принадлежат едновременно на всички дадени множества.

Множествената разлика A \ B = A - B (фиг. 2.2.3) е такова множество, всеки елемент от което принадлежи на множеството A, но не принадлежи на множеството B.

Симетрична разлика ADB (фиг. 2.2.4)

Допълнението към множеството A се нарича набор от всички елементи, които не са включени в множеството A (Фигура 3.2.5)

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

Нека вселената бъде дадена U . След това за всички A,B,CÌ Uса изпълнени следните свойства (Таблица 2.3.1):

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

За съюз (È)	За пресичане (Ç)
Идемпотентност
A È A = A	A Ç A \u003d 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
Инволютивност
= А
Законите на Де Морган

Свойства на добавките

Израз за разлика

Израз за симетричната разлика

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

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

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

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

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

В началото на 20-ти век Бъртран Ръсел, докато изучавал наивна теория на множествата, стигнал до парадокс (известен като парадокс на Ръсел). По този начин беше демонстриран провалът на наивната теория на множествата и свързаната с нея програма за стандартизация на математиката на Кантор. А именно, бяха открити редица антиномии на теория на множествата: оказа се, че когато се използват представяния на теория на множествата, някои твърдения могат да бъдат доказани заедно с техните отрицания (и тогава, според правилата на класическата пропозиционална логика, абсолютно всяко твърдение може да бъде „доказано!“). Антиномиите бележат пълния провал на програмата на Кантор.

След откриването на антиномията на Ръсел някои математици (например Л. Е. Я. Брауер и неговата школа) решават напълно да се откажат от използването на теоретико-множествени представяния. Другата част от математиците, начело с Д. Хилберт, направиха редица опити да обосноват тази част от теоретико-множествените представи, които им се струваха най-малко отговорни за появата на антиномии, въз основа на очевидно надеждна крайна математика. За тази цел са разработени различни аксиоматизации на теорията на множествата.

Характеристика на аксиоматичния подход е отхвърлянето на идеята, залегнала в програмата на Кантор, за действителното съществуване на множества в някакъв идеален свят. В рамките на аксиоматичните теории множествата "съществуват" по чисто формален начин и техните "свойства" могат да зависят значително от избора на аксиоматика. Този факт винаги е бил обект на критика от онези математици, които не са били съгласни (както настоява Хилберт) да признаят математиката като игра на символи, лишена от каквото и да е съдържание. По-специално Н. Н. Лузин пише, че „силата на континуума, дори само да го мислим като набор от точки, е една единствена определена реалност“, чието място в поредицата от кардинални числа не може да зависи от това дали хипотезата за континуума се признава за аксиома или нейното отричане.

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

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

Сега имаме всички средства да формулираме системата от аксиоми на ZFC теорията на множествата, в рамките на която е възможно да се изложат всички общоприети в съвременната математика методи на разсъждение и нито един от известните теоретико-множествени парадокси не преминава. Тази система ви позволява да изграждате всички математически обекти на базата на празен набор. Нека си представим система от аксиоми, Zermelo - Frenkel (ZF).

1.Аксиома за съществуване на празно множество: Има празно множество Æ;

2. Аксиома за съществуването на двойка: Ако има множества a и b, то съществува множество (a, b);

3. Аксиома за сумата: Ако има множество X, то има множество ÈX=(a|aÎb за някакво bÎX);

4. Аксиома за безкрайност: Съществува множество w = ( 0, 1,…,n,… ), където 0 = Æ, n + 1 = nÈ(n);

5. Аксиома на множеството от всички подмножества: Ако има множество A, то има множество:

P(A) = (B|BÍA);

6. Аксиома за заместване: Ако P(x, y) е някакво условие на множествата х , г, така че за всяко множество x има най-много едно множество приудовлетворяващ P(x, y), тогава за всяко множество Аима множество (b|P(c,b) за някое c н a);

7. Аксиома за екстензионност:

Две множества, които имат еднакви елементи, са равни, всяко множество се определя от своите елементи:

8. Аксиома за редовност:

Всяко непразно множество x има елемент a n x, за който

От аксиомата за редовност следва, че всяко множество се получава на някаква стъпка от "регулярния процес" на формиране на множеството от всички подмножества, започвайки с Æ и подобно на конструирането на естествени числа от празното множество съгласно аксиомата на безкрайност. Това означава, че всеки елемент от всяко множество е множество, конструирано от празното множество.

Нека покажем как ZF аксиоматиката позволява да се дефинират теоретико-множествени операции.

1. Дефинираме множеството AÈ B, започвайки от множествата A до B. Съгласно аксиомата за съществуване на двойка се образува множеството (A, B). Използвайки аксиомата за сумата, получаваме множеството È(A, B), което по дефиниция съвпада с множеството AÈB.

2. Пресечната точка A Ç B на множества A и B се определя от аксиомата за заместване, като се използва следното свойство P(x, y): x = y и x Î A. Имаме множеството (b|P(c,b ) и с Î B) = (b| с = bи с О А и с ОВ) = (c| с О А и с ОВ).

3. Нека покажем, че аксиоми 5 и 6 предполагат съществуването на множество А2 = ((a, b) |a, bО А) за всяко множество А. Тъй като (a, b) = ((a), (a, b) ), тогава A2 UP(P(A)). Нека свойството P(x, y) означава, че има a, bÎ A такива, че x = ((a), (a, b)) и y = x. Тогава множеството A2 е равно на (b|P(c,b), cÎ P(P(A))) и съгласно аксиома 6 то съществува.

Системата от аксиоми ZFC се формира от ZF чрез добавяне на една от следните две еквивалентни аксиоми, които, от една страна, са най-малко "очевидни", а от друга страна, най-смислени,

1. Аксиома на избора.

За всяко непразно множество A съществува преобразуване j: P(A) \ (N) ®A такова, че j (X) nX|за всички XU A, X¹N.

2. Принципът на пълното подреждане. За всяко непразно множество A съществува двоично отношение £ върху A, за което (A, £) е добре подредено множество.

В системата ZFC е валиден принципът на трансфинитната индукция, който е обобщение на принципа на пълната индукция: ако (A, £) е напълно подредено множество, P(x) е някакво свойство, то свойството P(x ) на всички елементи x н A следва от факта, че за всяко zн A изпълнимостта на свойството P на елементите y, където y< z, влечет выполнимость P(z):

Глава 4

Терминът "представяне" (използван е и терминът "имплементация") по отношение на програмирането означава следното. Да се зададе представяне на обект (в този случай набор) означава да се опише от гледна точка на използваната програмна система структурата от данни, използвана за съхраняване на информация за представения обект, и алгоритмите върху избраните структури от данни, които изпълняват операциите, присъщи на този обект. Тази статия предполага, че често използвани структури от данни като масиви, структури (или записи) и указатели са налични в използваната програмна система. По този начин, по отношение на наборите, дефиницията на представяне предполага описание на метода за съхраняване на информация за членството на елементи в набор и описание на алгоритмите за изчислително обединение, пресичане и други въведени операции.

Трябва да се подчертае, че по правило един и същи обект може да бъде представен по много различни начини и е невъзможно да се посочи най-добрият начин за всички възможни случаи. В някои случаи е изгодно да се използва едно представяне, а в други е изгодно да се използва друго. Изборът на представяне зависи от редица фактори: характеристиките на обекта, който се представя, съставът и относителната честота на използване на операциите в конкретна задача и др. Способността да се избере най-подходящото представяне за даден случай е в основата на изкуството на практическото програмиране. Добрият програмист се отличава с това, че знае много различни начини за представяне и умело избира най-подходящия.

4.1 Изпълнение на операции върху подмножества от дадена вселена U

Нека вселената U- ограничен, а броят на елементите в него надвишава капацитета на компютъра: | U | < n. Элементы универсума нумеруются: U = (u1 ... un). Подмножество А на Вселената Uпредставен с код (машинна дума или битова скала) C, в който

1 ако u1 ОА

0 ако un PA

където C[i] е i-тата цифра на C кода;

Кодът на пресичане на множества A и B е побитовото логическо произведение на кода на множество A и кода на множество B. Кодът за комбиниране на множества A и B е побитовата логическа сума на кода на множество A и кода на множество Б. Повечето компютри имат съответните машинни инструкции за тези операции. По този начин операциите върху малки набори се извършват много ефективно. Ако силата на вселената надвишава размера на машинна дума, но не е много голяма, тогава се използват масиви от битови мащаби за представяне на набори. В този случай операциите върху множества се изпълняват с помощта на цикли над елементи на масив.

4.2 Генериране на всички подмножества на вселената

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

Алгоритъм за генериране на всички подмножества на набор от n елемента:

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

Изход:последователност от кодове на подмножества i;

за i от 0 до 2n - 1;

добив аз ;

край за ;

Алгоритъмът произвежда 2n различни цели числа, следователно 2n различни кода. С нарастването на числото се увеличава и броят на битовете, необходими за представянето му. Най-голямото (от генерираното) число 2n - 1 изисква неговото представяне да бъде точно n бита. Така всички подмножества се генерират и то точно веднъж. Недостатъкът на този алгоритъм е, че редът, в който се генерират подгрупи, няма нищо общо с техния състав. Например код на подмножество 0111 ще бъде последван от код на подмножество 1000.

4.3 Представяне на набори чрез подредени списъци

Ако вселената е много голяма (или безкрайна) и подмножествата на разглежданата вселена не са много големи, тогава битовото представяне не е ефективно по отношение на спестяването на памет. В този случай наборите са представени от запис с две полета: информационно поле и указател към следващия елемент. Целият списък е представен от указател към първия елемент.

елемент = запис ;

аз : инфо ; (информационно поле);

н : н(указател към следващия елемент);

край запис ;

С това представяне сложността на операцията Î ще бъде O(n), а сложността на операциите Ì, Ç и È ще бъде O(n×m), където n и m са мощностите на множествата, включени в операцията.

Ако елементите в списъците са сортирани, например, във възходящ ред на стойността на полето i, тогава сложността на всички операции ще бъде O(n). Ефективното прилагане на операции върху набори, представени като подредени списъци, разчита на много общ алгоритъм, известен като алгоритъм за сливане. Алгоритъмът от тип сливане преминава паралелно през два набора, представени от подредени списъци, и на всяка стъпка се извършва напредък в набора, в който текущият елемент е по-малък.

Заключение

Курсовият проект е завършен по темата "Елементи на теорията на множествата". Той разглежда следните въпроси:

Множества: елементи и множества, начини за задаване на множества, брой елементи в множество;

Операции върху множества: сравнение на множества, основни операции върху множества, свойства на операциите върху множества;

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

Представяне на множества в компютър: Изпълнение на операции върху подмножества на дадена вселена U , Генериране на всички подмножества на вселената, Представяне на множества чрез подредени списъци;

Въз основа на намерената информация (учебник, интернет) идентифицирах основните точки, които най-пълно и точно дават представа за теорията на множествата. При изпълнение на работата бяха дадени примери за набори, както и тези примери, които водят до противоречия с различни начини на тяхното уточняване. Докато изучавах свойствата на операциите върху множества, доказах едно от свойствата (разпределимост) с помощта на диаграми на Ойлер-Вен. И мисля, че в последната глава беше необходимо да се посочи връзката между множествата и тяхното представяне на компютър, това е особено важно според мен за специалността математик-програмист.

След извършената работа може да се направи следното заключение:

Понятията "множества" и "елементи на множества" съставляват основния речник на математическата логика. Именно тези концепции поставят основата, необходима за по-нататъшни конструкции.

Списък на използваната литература

1. Дискретна математика за програмисти / F.A. Новиков. - Санкт Петербург: Питър, 2002. - 304 с.

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

3. Судоплатов С.В., Овчинникова Е.В. Елементи на дискретната математика: Учебник. - М.: INFRA-M, Новосибирск: Издателство на NSTU, 2002. - 280 с. – (Поредица “Висше образование”)

4. Шипачев В.С. Висша математика. Proc. За университети. - 4-то изд., Sr. – М.: Висше училище. 1998. - 479 с.

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

II. Тестване: 41 мин

1. Какво е набор?

А) обединяването на някои обекти или предмети в едно цяло според някои общи свойства или закони

В) надеждни знания, чието съответствие с обективни явления и обекти от околния свят се потвърждава от практиката

В) наука за законите и формите на правилното мислене

2. Какво означава този знак в логиката?

А) пресичане

Б) празното множество

В) асоциация

3. Какво означава този знак в логиката ?

А) пресичане

Б) празното множество

В) асоциация

4. Какво означава този знак в логиката ?

А) пресичане

Б) празното множество

В) асоциация

5. Какво означава този знак \ в логиката?

Разлика

Б) елемент

C) подмножество

6. От представените знаци изберете знака за собственост:

а)

IN)

7. Какво се нарича обединение на множества A и B?

8. Какво се нарича пресечна точка на множества A и B?

A) ново множество, състоящо се от онези елементи, които са включени в поне едно от множествата A или B

В) ново множество, състоящо се от онези елементи, които принадлежат както на множество A, така и на множество B

C) ново множество, състоящо се от всички елементи на A, които не са включени в B

9. Какво се нарича разлика на множества A и B?

A) ново множество, състоящо се от онези елементи, които са включени в поне едно от множествата A или B

В) ново множество, състоящо се от онези елементи, които принадлежат както на множество A, така и на множество B

C) ново множество, състоящо се от всички елементи на A, които не са включени в B

10. Защо са необходими кръговете на Ойлер-Вен в логиката?

А) за изчисления

В) за проектиране на решения на логически проблеми

В) за илюстриране на връзката между множествата

11. Задава A=
и B=
, намери си В:

А) C=

B) C=

C) C=

12. Задава A=
и B=
, намери си В:

А) C=

B) C=

C) C=

13. Задава A=
и B=
, намерете A\B:

А) елемент

Б) подмножество

В) принадлежност

Тест: Основи на теорията на множествата Набор, който не съдържа никакви елементи.

Отговор:

празен комплект

Множество, съдържащо краен брой елементи.

Отговор:

крайно множество

Набор, който не е нито краен, нито празен.

Отговор:

безкрайно множество

Много реки в Русия.

празен

Много хора живеят на Марс.

финал

Много точки в кръг.

безкраен

набор от естествени числа

набор от цели числа

набор от рационални числа

набор от реални числа

комутативност

AIB = BIA

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

AI(B∩C) = (AIB)∩(AIS)

дистрибутивност

(AIB)IS = AI(VIS)

Начини за определяне на набори:

изброяване на всички елементи на едно множество

използвайки кръгове на Ойлер

указание за характерното свойство на елементите на множеството

определяне на първия и последния елемент на набор

добавяне на много

универсален комплект

равен

подмножество

Набор A е подмножество на набор D

Набор D е подмножество на набор A

Набор A и набор D са равни

Комплект A - степен на набор D

(0;1)

(3;1)

(2;0)

(1;0)

много студенти от факултета, които имат домашен персонален компютър

празен комплект

множествата A и B са равни

Нека множеството M=(-1;1) е интервал, а множеството N=[-1;0] е сегмент от числовата ос, тогава множеството K=M 3 N, като числов интервал, ще бъде равна на...

K=[-1, 1]

K=(-1,0]

K=(-1,0)

K=(-1, 1]

		(-1;0)
		(1;1)
		(0;1)
		(-1;1)

симетрична разлика

допълнение

еднакво мощни

Изберете правилните твърдения:

Безкрайните неизброими множества са по-малко мощни от безкрайните неизброими множества.

Безкрайните неизброими множества са по-мощни от безкрайните изброими множества.

Безкрайните изброими множества са множества, които са достигнали кардиналността на континуума.

Всяко крайно множество ще бъде по-малко мощно от всяко безкрайно изброимо множество.

множествата A и B имат еднакви елементи

множествата A и B са равни

комплект A включва комплект B

множество A е подмножество на множество B

Опростете, ако A=B, A∩C=∅ :

(((AИB)∩(C∩C))\(B∩A)∩B))∆A=…

празен комплект

Опростете, ако A=B, A∩C=∅ :

((D\(A∩B))∩((CIC)∩B)=…

празен комплект

Опростете, ако A=B, A∩C=∅ :

(C∩B)∆((AИB)И(C∩A))=…

празен комплект

X=(1,5); Y=(1,2,4); Z=(2,5)

Намерете набор: XI(Y∩Z)

{1,2,4,5}

{1,2,5}

{1,4,5}

{1,2,4}

Нека са дадени следните множества:

X=(1,2,3,4,5); X=(1,5); Y=(1,2,4); Z=(2,5)

Намерете набор: (XИY)∩(XИZ)

{1,2,4,5}

{1,5}

{1,2,5}

{2,5}

A = (5, 7, 9) И (5, 12, 15)

Следвайте стъпките и определете кардиналността на получения набор:

б = {5, 7, 9, 12} З{5,12, 15}

Следвайте стъпките и определете кардиналността на получения набор:

А = (5, 7, 9){5, 57, 59}

Следвайте стъпките и определете кардиналността на получения набор:

б = {5, 7, 9} И{5, 57, 59}

Следвайте стъпките и определете кардиналността на получения набор:

{1, 2, 3}\ {2, 3}

Следвайте стъпките и определете кардиналността на получения набор:

{1, 2, 3}\ {4, 5}

x ≤ 3

x  (1, 2, 3)

1 < x < 5

x  (2, 3, 4)

3 < x ≤ 6

x  (4, 5, 6)

2 ≤ x ≤ 4

1 ≤ x< 4

Колко ученици са решили всички задачи?

В кандидатстудентската олимпиада по математика участваха 40 ученици, които трябваше да решат една задача по алгебра, една по геометрия и една по тригонометрия. По алгебра задачата са решавали 20 души, по геометрия - 18 души, по тригонометрия - 18 души.

Алгебра и геометрия решаваха 7 души, алгебра и тригонометрия - 9 души. Нито един от проблемите не е решен от 3 души.

Колко ученици са решили само две задачи?

Колко ученици са решили само една задача?

Първа или втора контролна работа по математика са написали успешно 33 ученици, първа или трета – 31 ученици, втора или трета – 32 ученици. Най-малко два теста бяха попълнени от 20 ученици.

Колко ученици са решили успешно само един тест?

В класа има 35 ученици. Всеки от тях използва поне един от видовете градски транспорт: метро, автобус и тролейбус. И трите вида транспорт ползват 6 ученици, метро и автобус - 15 ученици, метро и тролейбус - 13 ученици, тролейбус и автобус - 9 ученици.

Колко ученици използват само един вид транспорт?

Отговор:

Нека A = (1,2,3,8) и B =(a,b,c)