Тест за набори на номера. Методи за определяне на множества

Тест по темата "Комплекти"

ИНСТРУКЦИИ:

Опция 1

1. Определете кое от множествата е подмножество на A = (10, 20, 30, 40, 50, 60)

а) (10, 20, 30, 40, 50, 60, 70) б) (10) в) (10, 35)

2. Кой от множествата определя дали A = (1, 2, 3, 4, 5), B = (3, 4, 5, 6, 7)

а) (1, 4, 5) б) (1, 2, 3, 4, 5) в) (1, 2, 3, 4, 5, 6, 7)

ако A = (1, 3, 5, 7, 9), B = (1, 2, 3, 4)

а) (1, 3, 5, 7) б) (1, 2, 3, 4, 5, 7, 9) в) (1, 3)

4. Множеството от триъгълници беше разделено на подмножества от разнообразни триъгълници, равнобедрени триъгълници и равностранни триъгълници... Разделен ли е наборът от триъгълници на класове?

а) да б) не

5. Коя фигура показва обединението на множествата A и B ()?

Тест по темата "Комплекти"

Тест с избора на верния отговор.

ИНСТРУКЦИИ:Изберете буквата с правилния отговор и я въведете в листа с отговори.

Вариант 2

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

A = (5, 15, 25, 35, 45, 55)

а) (55) б) (5, 25, 50) в) (25, 55, 75)

2. Кой от множествата определя дали A = (2, 4, 6, 8, 10), B = (8, 10, 12, 14)

а) (2, 4, 6, 8, 10, 12, 14) б) (8, 10, 12, 14) в) (8, 10)

3. Кой от множествата определя
ако A = (2, 4, 6, 8, 10), B = (2, 4, 8, 9)

а) (2, 4, 6, 8, 10) б) (2, 4, 8, 9) в) (2, 4, 8)

4. Множеството от всички ъгли беше разделено на подмножества от прави, тъпи и остри. Разделен ли е наборът от ъгли на класове?

а) да б) не

5. Коя фигура показва пресечната точка на множествата A и B (
)?

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

Чувашки Държавен университеттях. I.N. Улянов

Клон Алатир

Факултет по мениджмънт и икономика

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

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

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

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

Извършва се от студент

1 курс

групи - AFT 61-06

ръководител

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

Въведение

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

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

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

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

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

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

Глава 1. Комплекти

1.1 Елементи и комплекти

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

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

Обикновено при конкретни разсъждения елементите на всички множества се вземат от някакво, достатъчно широко множество 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. Нека YYY, след като свойството, определящо Y, е удовлетворено, стигаме до факта, че YÎY и това противоречи на предположението. Оказва се непреодолимо логическо противоречие. Ето три начина да избегнете този парадокс.

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

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

където А е известно, съзнателно съществуващо множество (вселена). Обикновено се използва нотация (xÎA | 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, или | 2А | > | А |.

Използвайки Канторовия квадрат, може да се докаже и следното полезно твърдение: Декартовото произведение на безкрайно множество A със себе си е равно на A.

След Кантор, мощността на множество се нарича кардинално число и мощността на такова множество А се обозначава с | А | (Самият Кантор използва нотацията). Понякога има обозначение.

Мощността на множеството естествени числа се обозначава със символа ("алеф-нула"). Множество се нарича безкраен, ако неговата мощност, следователно, преброимите множества са "най -малките" от безкрайните множества. Следните кардинални числа са посочени във възходящ ред.

За множествата, които са равни на множеството от всички реални числа, се казва, че имат мощността на континуума, а мощността на такива множества се обозначава със символа c (континуум). Хипотезата за континуума гласи, че.

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

1. | А | = | В | или А и В са равни;

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

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

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

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

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

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

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

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

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

аксиоматично членство на зададен елемент

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

Ако u, тогава 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 = 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
Инволюция
= А
Законите на Дьо Морган

Допълнителни свойства

Различен израз

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

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

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

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

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

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

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

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

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

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

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

Сега имаме всички средства за формулиране на системата от аксиоми на теорията на множествата ZFC, в рамките на която могат да бъдат представени всички методи на разсъждения, общоприети в съвременната математика и нито един от известните теоретични множества парадокси не преминава. Тази система ви позволява да изградите всичко математически обективъз основа на празния набор. Представяме системата от аксиоми, Zermelo - Fraenkel (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 Î 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 ) и c Î B) = (b | c = b и c Î A и c ÎB) = (c | c Î A и c ÎB).

3. Нека покажем, че аксиомите 5 и 6 предполагат съществуването на множеството A2 = ((a, b) | a, bÎ A) за всяко множество A. Тъй като (a, b) = ((a), (a, b)), след това A2 ÍP (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) \ (Æ) ®A такова, че j (X) ÎX | за всички XÍ A, X¹Æ.

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

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

Глава 4. Представяне на множества в компютър

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

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

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

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

1, ако u1 ОА

0, ако un ОА

където е 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;

добив i ;

край за ;

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

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

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

елем = запис ;

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

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

край запис ;

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

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

Заключение

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

Набори: елементи и множества, методи за определяне на множества, броя на елементите в набор;

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

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

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

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

След свършената работа можете да свършите следващ изход:

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

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

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

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

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

4. Шипачев В.С. Висша математика... Учебник. За университетите. - 4 -то изд., Изтрито. - М.: аспирантура... 1998 г.- 479 стр.

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

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

Отговор:

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

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

Отговор:

краен набор

Множество, което не е нито крайно, нито празно.

Отговор:

безкраен набор

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

празна

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

финалът

Набор от точки на окръжност.

безкраен

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

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

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

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

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

AIB = BIA

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

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

Разпределение

(AIB) ИC = AИ (BIC)

Методи за определяне на набори:

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

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

посочване на характерното свойство на елементите от множеството

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

допълване на комплекта

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

равен

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

Множество А е подмножество на множеството 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 ‡ 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∩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)

Намерете комплекта: XИ (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} Z{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)