Эквиваленттік қатынас және бөлінділер жиыны. Эквиваленттік қатынастар. Факторлар Эквиваленттік қатынастар. Факторлар жиындары
(яғни келесі қасиеттерге ие: жиынның әрбір элементі өзіне эквивалентті; егер xэквивалент ж, Бұл жэквивалент x; Егер xэквивалент ж, А жэквивалент z, Бұл xэквивалент z ).
Содан кейін барлық эквиваленттік класстардың жиыны шақырылады факторлар жиынтығыжәне тағайындалады. Жиынды эквивалентті элементтердің кластарына бөлу оның деп аталады факторизация.
Көрсеткіштен Xэквиваленттік кластар жиынтығы деп аталады факторлық карталау.
Мысалдар
Жартылай нормаланғандардан нормаланған кеңістіктерді, дерлік ішкі туындысы бар кеңістіктерден ішкі туындысы бар кеңістіктерді және т.б. алу үшін жиынтық факторизацияны қолдану орынды. Ол үшін сәйкесінше класс нормасын енгіземіз. ерікті элементтің нормасы, ал класстардың ішкі туындысы класстардың ерікті элементтерінің ішкі туындысы ретінде. Өз кезегінде, эквиваленттік қатынас келесідей енгізіледі (мысалы, нормаланған бөлінді кеңістігін қалыптастыру үшін): нөлдік семинормасы бар элементтерден тұратын бастапқы жарты нормаланған кеңістіктің ішкі жиыны енгізіледі (айтпақшы, бұл сызықтық, яғни бұл ішкі кеңістік) және егер олардың айырмашылығы дәл осы ішкі кеңістікке жататын болса, екі элемент эквивалентті деп саналады.
Егер сызықтық кеңістікті көбейткіштерге бөлу үшін белгілі бір ішкі кеңістік енгізілсе және бастапқы кеңістіктің екі элементінің айырмасы осы ішкі кеңістікке жататын болса, онда бұл элементтер эквивалентті деп есептелсе, онда көбейткіштер жиыны сызықтық кеңістік болып табылады және деп аталады. фактор кеңістігі.
Мысалдар
да қараңыз
Викимедиа қоры. 2010.
Басқа сөздіктерде «Факторлар жиынтығы» не екенін қараңыз:
Абстракция арқылы анықтамалардың негізінде жатқан логикалық принцип (Абстракция арқылы анықтаманы қараңыз): элементтердің кейбір бастапқы жиынында анықталған теңдік түрінің кез келген қатынасы, түпнұсқаны бөлетін (бөлетін, жіктейтін)... ...
Заттар мен құбылыстардың маңызды қасиеттерін, байланыстары мен қатынастарын олардың қарама-қайшылығы мен дамуында көрсететін ойлау формасы; Белгілі бір жалпыға және жиынтыққа сәйкес белгілі бір таптың объектілерін жалпылайтын, ажырататын ой немесе ойлар жүйесі... ... Ұлы Совет энциклопедиясы
Галуа тобының когомологиясы. Егер M абельдік топ және M-ге әсер ететін кеңейтудің Галуа тобы болса, онда Галуа когомологиялық топтары барлық карталардан тұратын кешен арқылы анықталған когомологиялық топтар, ал d - когомологиялық оператор (топтардың когомологиясын қараңыз).... . .. Математикалық энциклопедия
Құрылыс, жұмақ, алдымен жиындар теориясында пайда болды, содан кейін алгебра, топология және математиканың басқа салаларында кеңінен қолданыла бастады. I. p.-дің маңызды ерекше жағдайы бір типті математикалық құрылымдардың бағытталған тобының I. p. болып табылады. Болсын… Математикалық энциклопедия
Ұпайлар X жиынында әрекет ететін G тобына қатысты болса да (сол жақта), Жиын G топшасының ішкі тобы болып табылады және деп аталады. тұрақтандырғыш немесе G-ге қатысты нүктенің стационарлық ішкі тобы. Карталау G/Gx және G(x) орбитасы арасында екі жақты индукцияны тудырады. ТУРАЛЫ.…… Математикалық энциклопедия
Бұл мақалада тым қысқа кіріспе бар. Мақаланың тақырыбын қысқаша ашатын және оның мазмұнын қысқаша баяндайтын кіріспе бөлімін қосыңыз... Wikipedia
Бұл мақала алгебралық жүйе туралы. Мәлімдемелерді және олардағы амалдарды зерттейтін математикалық логиканың бөлімі үшін Логика алгебрасын қараңыз. Буль алгебрасы екі екілік амалы бар бос емес А жиыны (конъюнктураға ұқсас), ... ... Wikipedia
Жиынға эквиваленттік қатынас берілсін. Сонда барлық эквиваленттік кластардың жиыны факторлар жиыны деп аталады және белгіленеді. Жиынды эквивалентті элементтердің кластарына бөлу оны көбейткіштерге бөлу деп аталады. Википедиядан... ... картасына түсіру
Геометрияда бағытталған кесінді деп реттелген жұп нүктелер түсініледі, олардың біріншісі А нүктесі оның басы, ал екіншісі В нүктесі оның соңы деп аталады. Мазмұны 1 Анықтама ... Уикипедия
Математиканың әртүрлі салаларында картаның ядросы белгілі бір мағынада f және инъекциялық кескіндеу арасындағы айырмашылықты сипаттайтын белгілі бір жиынтық керф болып табылады. Арнайы анықтама әртүрлі болуы мүмкін, бірақ инъекциялық карта үшін f... ... Wikipedia
Жиын теориясы. Негізгі ұғымдар
Жиын теориясы қазіргі математиканың негізгі анықтамасы болып табылады. Оны 1860 жылдары Георг Кантор жасаған. Ол былай деп жазды: «Көп көп, біртұтас тұтастық ретінде ойластырылған». Жиын ұғымы – математиканың негізгі, анықталмаған ұғымдарының бірі. Оны басқа, қарапайым ұғымдарға келтіруге болмайды. Сондықтан оны анықтау мүмкін емес, тек түсіндіруге болады. Сонымен, жиынтық дегеніміз – түйсігімізбен немесе ойымызбен анық ерекшеленетін бір тұтас объектілерге бірігу; жалпы сипаттамамен анықталған белгілі бір объектілердің жиынтығы.
Мысалы,
1. Воронеж қаласының көптеген тұрғындары
2. Жазық нүктелер жиыны
3. Натурал сандар жиыны ℕт.б.
Жиындар әдетте бас латын әріптерімен белгіленеді( A, B, Cжәне т.б.). Берілген жиынды құрайтын объектілер оның элементтері деп аталады. Жиын элементтері шағын латын әріптерімен белгіленеді( a, b, cжәне т.б.). Егер X– орнатыңыз, содан кейін жазыңыз x∈Xдегенді білдіреді Xжиынның элементі болып табылады Xнемесе не Xжиынтығына жатады X, және жазба x∉Xсол элемент Xжиынтыққа жатпайды X. Мысалы, ℕ натурал сандар жиыны болсын. Содан кейін 5 ℕ , А 0,5∉ℕ .
Егер жиынтық Ыжиынның элементтерінен тұрады X, сосын олар осылай дейді Ыжиынның ішкі жиыны болып табылады Xжәне белгілеңіз Y⊂Х(немесе Y⊆Х). Мысалы, бүтін сандар жиыны ℤ рационал сандардың ішкі жиыны болып табылады ℚ .
Екі жиынтық үшін болса XЖәне Ыекі қосынды бір мезгілде орын алады X YЖәне Y X, яғни. Xжиынның ішкі жиыны болып табылады ЫЖәне Ыжиынның ішкі жиыны болып табылады X, содан кейін жиындар XЖәне Ыбірдей элементтерден тұрады. Мұндай жиынтықтар XЖәне Ытең деп аталады және мынаны жаз: X=Y.
Бос жиын термині жиі қолданылады - Ø - бір элементі жоқ жиын. Бұл кез келген жиынның ішкі жиыны.
Жиындарды сипаттау үшін келесі әдістерді қолдануға болады.
Жиындарды анықтау әдістері
1. Объектілерді санау. Тек ақырлы жиындар үшін қолданылады.
Мысалы, X=(x1, x2, x3… x n). Y енгізу ={1, 4, 7, 5} жиынның төрт саннан тұратынын білдіреді 1, 4, 7, 5 .
2. Жиын элементтерінің сипаттамалық қасиетін көрсету.
Ол үшін белгілі бір қасиет орнатылады Р, ол элементтің жиынға жататынын анықтауға мүмкіндік береді. Бұл әдіс әмбебап болып табылады.
X=(x: P(x))
(бір топ Xсияқты элементтерден тұрады X, ол үшін мүлік иеленеді P(x)).
Бос жиынды оның қасиеттерін көрсету арқылы көрсетуге болады: Ø=(x: x≠x)
Жиындардағы әрекеттерді пайдаланып, бұрыннан анықталғандарды пайдаланып жаңа жиындар құруға болады.
Операцияларды орнату
1. Бірлестік (қосынды) – әрқайсысы жиындардың кем дегенде біреуіне жататын барлық элементтерден тұратын жиын Анемесе IN.
A∪B=(x: x A немесе x B).
2. Қиылысу (өнім) деп әрқайсысы бір мезгілде жиынға жататын барлық элементтерден тұратын жиынды айтады. А, және көптеген IN.
A∩B=(x: x A және x B).
3. Айырмашылықты орнату АЖәне INжиынға жататын барлық элементтерден тұратын жиын Ажәне көпшілікке жатпайды IN.
A\B=(x: x A және x B)
4. Егер А– жиынның ішкі жиыны IN. Бұл көп B\Aжиынның толықтауышы деп аталады Акөпке INжәне белгілеңіз A'.
5. Екі жиынның симметриялық айырмасы жиын болып табылады A∆B=(A\B) (B\A)
Н- барлық натурал сандар жиыны;
З- барлық бүтін сандар жиыны;
Q- барлық рационал сандар жиыны;
Р- барлық нақты сандар жиыны;
C- барлық комплекс сандар жиыны;
Z 0- барлық теріс емес бүтін сандар жиыны.
Жиындарға амалдардың қасиеттері:
1. А B=B A (одақтың коммутативтілігі)
2. А B=B A (қиылысудың коммутативтілігі)
3. А(Б C)=(A IN) C (одақ қауымдастығы)
4. А (IN C)=(A IN) C (қиылысу ассоциациясы)
5. А (IN C)=(A IN) (А C) (таратудың 1-ші заңы)
6. А (IN C)=(A IN) (А C) (таралудың 2-ші заңы)
7. А Ø=A
8. А U=U
9. А Ø= Ø
10. А U=A
11. (А B)'=A' B' (де Морган заңы)
12. (А B)'=A' B' (де Морган заңы)
13. А (А B)=A (сіңіру заңы)
14. А (А B)=A (сіңіру заңы)
No11 мүлікті дәлелдеп көрейік. (А B)'=A' IN'
Тең жиынтықтардың анықтамасы бойынша біз екі қосындыны дәлелдеуіміз керек 1) (А B)’ ⊂A’ IN';
2) A' B’⊂(А IN)'.
Бірінші қосуды дәлелдеу үшін ерікті элементті қарастырыңыз x∈(А B)’=X\(A∪B).Бұл дегеніміз x∈X, x∉ A∪B. Осыдан шығады x∉AЖәне x∉B, Сондықтан x∈X\AЖәне x∈X\B, білдіреді x∈A’∩B’. Осылайша, (А B)’⊂A’ IN'
Артқа егер x∈A’ IN', Бұл Xбір мезгілде жиынтыққа жатады A', B', білдіреді x∉AЖәне x∉B. Осыдан шығады x∉ A IN, Сондықтан x∈(А IN)'. Демек, A' B’⊂(А IN)'.
Сонымен, (А B)'=A' IN'
Элементтердің реті анықталған екі элементтен тұратын жиын реттелген жұп деп аталады. Оны жазу үшін жақшаларды пайдаланыңыз. (x 1, x 2)– екі элементті жиын, онда x 1 бірінші элемент, ал x 2 екінші болып саналады. Жұптар (x 1, x 2)Және (x 2, x 1),Қайда x 1 ≠ x 2, әртүрлі болып саналады.
Элементтерінің реті анықталған n элементтен тұратын жиын n элементтен тұратын реттелген жиын деп аталады.
Декарттық көбейтінді – ерікті жиын X 1, X 2,…,X n n элементтердің реттелген жиындары, мұндағы x 1 X 1 , x 2 X 2 ,…, x n Xn
X 1 Xn
Егер жиынтықтар X 1, X 2,…,X nсәйкестік (X 1 = X 2 =…=X n), онда олардың туындысы белгіленеді Xn.
Мысалы, ℝ 2 – нақты сандардың реттелген жұптарының жиыны.
Эквиваленттік қатынастар. Факторлар жиындары
Берілген жиынның негізінде кейбір ішкі жиындардың жиынын қарастыру арқылы жаңа жиындарды құруға болады. Бұл жағдайда біз әдетте ішкі жиындар жиыны туралы емес, ішкі жиындардың отбасы немесе класы туралы айтамыз.
Бірқатар сұрақтарда берілген жиынның осындай ішкі жиындарының класы қарастырылады Ақиылыспайтын және бірігуі сәйкес келетін А. Бұл орнатылған болса Аоның жұп-бөлінбеген ішкі жиындарының бірігуі ретінде ұсынылуы мүмкін, онда бұл туралы айту әдеттегідей. Асыныптарға бөлінеді. Сыныптарға бөлу қандай да бір сипаттама негізінде жүзеге асырылады.
Болсын Xбос жиын емес, кез келген ішкі жиын Ржұмыстан X Xжиынындағы екілік қатынас деп аталады X. Жұп болса (x,y)кіреді R,олар х элементінің қатынаста екенін айтады Рбірге сағ.
Мысалы, қарым-қатынастар x=y, x≥yжиынтықтағы екілік қатынастар болып табылады ℝ.
Екілік қатынас Ржиынтықта Xэквиваленттік қатынас деп аталады, егер:
1. (x,x) R; X X (рефлексиялық қасиеті)
2. (x,y) R => (y, x) R (симметрия қасиеті)
3. (x,y) R, (y,z) R, содан кейін (x,z) R (транзиттілік қасиеті)
Жұп болса (x,y)эквиваленттік қатынасқа енеді, онда х пен у эквивалент деп аталады (x~y).
1.Let ℤ - бүтін сандар жиыны; m≥1- бүтін сан. Эквиваленттік қатынасты анықтайық Рқосулы ℤ сондай-ақ n~k, Егер n-kбөлінген м. Қасиеттердің осы қатынасқа сәйкестігін тексерейік.
1. Рефлексивтілік.
Кез келген адам үшін n∈ℤ ℤ солай (p,p)∈R
р-р=0. Өйткені 0∈ ℤ , Бұл (p,p)∈ℤ.
2. Симметрия.
бастап (n,k) ∈Rмұндай нәрсе бар деген қорытынды шығады р∈ℤ, Не n-k=mp;
k-n =m(-p), -p∈ ℤ, демек (k,n) ∈R.
3. Транзитивтілік.
Неден (n,k) ∈R, (k,q) ∈Rондайлардың бар екені шығады б 1Және р 2 ∈ ℤ, Не n-k=mp 1Және k-q=mp 2. Осы өрнектерді қоссақ, біз мынаны аламыз n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Сондықтан (n,q) ∈ ℤ.
2. Жиынды қарастырыңыз Xкеңістіктің немесе жазықтықтың барлық бағытталған сегменттері . =(A, B). Эквиваленттік қатынасты енгізейік Рқосулы X.
G=(p 0 =e, p 1, …, p r) X = (1, 2, …, n) жиынында анықталған ауыстырулардың белгілі бір тобы e=p 0 бірдей ауыстыру бірлігі болсын. x~y қатынасын G(p(x)=y)-ға жататын p бар екендігіне x~y эквивалентін қою арқылы анықтайық. Енгізілген қатынас эквиваленттік қатынас, яғни үш аксиоманы қанағаттандырады:
1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;
А ерікті жиын болсын.
Анықтама: Екілік қатынас δ=A*A эквиваленттік қатынас (a ~ b арқылы белгіленеді), егер ол келесі аксиомаларды қанағаттандырса:
∀ a, b, c ∈ A
1) a ~ a – рефлексивтілік;
2) a ~ b ⇒ b ~ a – коммутативтілік;
3) a ~ b & b ~ c → a ~ c - өтпелілік
a ~ b, σ(a,b), (a,b) ∈ σ, a σ b арқылы белгіленеді.
Анықтама: А жиынының бөлімі - бұл бірлікте (барлығы) барлық А-ны беретін А-ның жұптастырылған ішкі жиындарының отбасы.
А= ∪А i, А i ∩А j = ∅, ∀i ≠ j.
A i ішкі жиындары бөлімнің косеттері деп аталады.
Теорема: А жиынында анықталған әрбір эквиваленттік қатынас А жиынының кейбір бөліміне сәйкес келеді. А жиынының әрбір бөлімі А жиынындағы кейбір эквиваленттік қатынасқа сәйкес келеді.
Қысқаша: А жиынында анықталған барлық эквиваленттік қатынастар кластары мен А жиынының барлық бөлімдерінің класы арасында бір-бір сәйкестік бар.
Дәлелдеу: А жиынындағы σ эквиваленттік қатынас болсын. a ∈ A болсын.
Жиын құрастырайық: K a =(x ∈ A,: x~a) – a-ға эквивалентті барлық элементтер. Жиын (белгілеу) σ эквивалентіне қатысты эквиваленттік класс деп аталады. Назар аударыңыз, егер b K a -ға тиесілі болса, онда b~a. a~b⇔K a =K b екенін көрсетейік. Шынында да, a~b болсын. K a-ға жататын ерікті c элементін алайық. Сонда c~a, a~b, c~b, c K b-ға жатады, демек, K b K a-ға жатады. К а-ның К b-ға жататындығы да осыған ұқсас түрде көрсетілген. Демек, K b =K a.
Енді K b =K a болсын. Сонда a K a = K b , a K b , a~b -ге жатады. Мұны көрсету керек еді.
Егер K a және K b 2 класстың ортақ с элементі болса, онда K a = K b. Шын мәнінде, егер c K a және K b ға жататын болса, онда b~c, c~a, b~a => K a = K b .
Сондықтан әртүрлі эквиваленттік кластар не қиылыспайды, не қиылысады, содан кейін сәйкес келеді. А-ның әрбір c элементі тек бір K c эквиваленттік класына жатады. Сондықтан қиылысатын жердегі бөлінген эквиваленттік кластар жүйесі бүкіл А жиынын береді. Сондықтан бұл жүйе А жиынының эквиваленттік кластарға бөлінуі болып табылады.
Керісінше: A = қосындысы артық болсын немесе A i - А бөлімі болсын. a~b ⇔ a,b бір бөлім класына жататындықтан, А-ға a~b қатынасын енгізейік. Бұл қатынас келесі аксиомаларды қанағаттандырады:
1) a ~ a (бір сыныпта болады);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, яғни. енгізілген ~ қатынасы эквиваленттік қатынас болып табылады.
Түсініктеме:
1) А жиынын бір элементті ішкі жиындарға бөлу және тек А жиынынан тұратын А бөлімі тривиальды (дұрыс емес) бөлімдер деп аталады.
2) А-ны бір элементті ішкі жиындарға бөлу теңдік болып табылатын эквиваленттік қатынасқа сәйкес келеді.
3) Бір А класынан тұратын А бөлімдері құрамында A x A бар эквиваленттік қатынасқа сәйкес келеді.
4) a σ b → [a] σ = [b] σ - белгілі бір жиында анықталған кез келген эквиваленттілік қатынасы бұл жиынды эквиваленттік кластар деп аталатын жұптық ажыратылған кластарға бөледі.
Анықтама: А жиынының эквиваленттік кластарының жиыны σ эквиваленттігі бойынша А жиынының A/σ бөлінділер жиыны деп аталады.
Анықтама: p(A)=[a] σ болатын p:A→A/σ салыстыру канондық (табиғи) кескіндеу деп аталады.
Белгілі бір жиын бөлімдерінде анықталған кез келген эквиваленттік қатынас бұл эквиваленттік сыныптар деп аталатын жұптық ажыратылған сыныптарға жиналады.
Егер көзқарас Р келесі қасиеттерге ие: рефлексиялық симметриялық өтпелі, т.б. жиындағы эквиваленттік қатынас (~ немесе ≡ немесе E). М , онда эквиваленттік кластар жиыны жиынның факторлық жиыны деп аталады М эквиваленттілікке қатысты Р және тағайындалады МЫРЗА
Жиын элементтерінің ішкі жиыны бар М эквивалент x , деп аталады эквиваленттік класс.
Факторлар жиынының анықтамасынан оның логикалық жиынның ішкі жиыны екендігі шығады: .
Функция шақырылады сәйкестендіружәне келесідей анықталады:
Теорема.Фактор алгебрасы Ф n /~ логикалық функциялар алгебрасына изоморфты Б n
Дәлелдеу.
Қажетті изоморфизм ξ : Ф n / ~ → Б n келесі ережемен анықталады: эквиваленттілік класы ~(φ) функциясы сәйкес келеді f φ , жиыннан ерікті формула үшін ақиқат кестесінің болуы ~(φ) . Әртүрлі эквиваленттік класстар әртүрлі ақиқат кестелеріне сәйкес келетіндіктен, салыстыру ξ инъекциялық және кез келген логикалық функция үшін f бастап б функцияны білдіретін формула бар f, содан кейін картаға түсіру ξ суръектив. Әрекеттерді сақтау, көрсетілген кезде 0, 1 ξ тікелей тексеріледі. CTD.
Тұрақты шама емес әрбір функцияның функционалдық толықтығы туралы теорема бойынша 0 , кейбір SDNF сәйкес келеді ψ , сыныпқа жатады ~(φ) = ξ -1 (f) функцияны білдіретін формулалар f . Сыныпта болу мәселесі туындайды ~(φ) ең қарапайым құрылымы бар дизъюнктивті қалыпты форма.
Жұмыстың аяқталуы -
Бұл тақырып келесі бөлімге жатады:
Дискретті математика пәні бойынша дәрістер курсы
Мәскеу мемлекеттік құрылыс университеті.. Құрылыстағы басқару экономикасы және ақпараттық жүйелер институты.. IEEE..
Егер сізге осы тақырып бойынша қосымша материал қажет болса немесе сіз іздеген нәрсені таба алмасаңыз, біз жұмыстардың дерекқорындағы іздеуді пайдалануды ұсынамыз:
Алынған материалмен не істейміз:
Егер бұл материал сізге пайдалы болса, оны әлеуметтік желілердегі парақшаңызға сақтауға болады:
| Твит |
Осы бөлімдегі барлық тақырыптар:
Дискретті математика пәні
Дискретті (ақырлы, ақырлы) математика пәні дискретті құрылымдардың қасиеттерін зерттейтін математика бөлімі болса, классикалық (үздіксіз) математика объектілердің қасиеттерін зерттейді.
Изоморфизм
Алгебралық амалдарды зерттейтін ғылым алгебра деп аталады. Бұл тұжырымдама курсты оқыған сайын нақтырақ және тереңдей түседі. Алгебраны тек ҚАЛАЙ әрекет ету керек деген сұрақ қызықтырады
Жаттығулар
1. Изоморфты бейнелеу әрқашан изотонды, ал керісінше дұрыс емес екенін дәлелдеңіз. 2. Өз тобыңызды жиындар тілінде жазыңыз. 3. Жиын тілінде болатын объектілерді жазыңыз
Жиын және жиын элементтері
Қазіргі уақытта бар жиынтық теориялары концептуалды негіз бен логикалық құралдардың парадигматикасымен (көзқарастар жүйесі) ерекшеленеді. Мысал ретінде қарама-қарсы екі нәрсені келтіруге болады
Ақырлы және шексіз жиындар
Жиын неден тұрады, яғни. Жиынды құрайтын объектілер оның элементтері деп аталады. Жиынның элементтері бір-бірінен ерекше және ерекше. Берілген мысалдан көрініп тұрғандай
Жиынның қуаты
Ақырлы жиын үшін негізгілік оның элементтерінің санына тең. Мысалы, n түбегейлі А жиынының В(А) ғаламының кардиналдығы
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3...An|
Ақырлы А жиыны 1 кесіндісіне тең болса, k кардиналдығына ие болады.. k;:
Ішкі жиын, меншікті жиын
Жиын ұғымы енгізілгеннен кейін бұрыннан барлардан жаңа жиындар құру, яғни жиындарға амалдарды анықтау міндеті туындайды. M жинағы",
Мағыналы жиынтық теорияларының символдық тілі
Курсты оқу барысында біз жиындар теориясының объектілік тілі мен оның көмегімен объектілік тіл зерттелетін метатілді ажыратамыз. Жиын теориясы тілі деп реляциялық деп түсінеміз
Дәлелдеу
В жиыны шексіз, яғни
Элементтерді қосу және жою
Егер A жиыны, ал x элементі болса, содан кейін элемент
Шектелген жиындар. Шекараларды орнату
Кейбір Х жиынында f(x) сандық функциясы берілсін. f(x) функциясының жоғарғы шегі (шекарасы) осындай сан болады
Дәл жоғарғы (төменгі) шек
Е барлық жоғарғы шекараларының жиынын Es арқылы, ал барлық төменгі шекараларды Ei арқылы белгілейді. Егер
Жиынның дәл жоғарғы (төменгі) шегі
Егер z элементі E жиынының және оның барлық жоғарғы шекараларының Es жиынының қиылысына жататын болса (тиісінше төменгі r
Жоғарғы және төменгі шекаралардың негізгі қасиеттері
X жартылай реттелген жиын болсын. 1. Егер, онда
Атрибутивтік көзқарас бойынша орнату
Жиынтық көзқарас, атрибутивтік көзқарастан айырмашылығы, Рассел мен Кантор типіндегі парадокстарға әкелетін мағынада логикалық тұрғыдан дәлелденбейді (төменде қараңыз). Атрибутивтік т шеңберінде
Құрылым
Ішінара реттелген Х жиыны, егер оның құрамында кез келген екі элементтен тұратын жиын болса, құрылым деп аталады
Жабу және бөлу жиынтықтары
А жиынының бөлімі Ai отбасы болып табылады
Екілік қатынастар
Ұзындығы n тізбегі, мүшелері a1, .... an, (a1, .... a) арқылы белгіленеді.
Бинарлы қатынастардың қасиеттері
Хо жиынындағы R екілік қатынасының келесі қасиеттері бар: (а) егер xRx болса рефлексиялық
Үштік қатынастар
Декарттық туынды XY
N-арлы қатынастар
Екі X,Y жиынының декарттық көбейтіндісіне ұқсастық арқылы біз Х декарттық көбейтіндісін құрастыра аламыз
Көрсеткіштер
Салыстыру – жиындардың элементтері арасындағы кейбір байланыстар. Қатынастардың қарапайым мысалдары х мүшелік қатынастары болып табылады
Корреспонденция
Декарттық көбейтіндінің S ішкі жиыны Mi жиындарының элементтерінің n-арлы сәйкестігі деп аталады. Ресми түрде
Функция
Дискретті математиканың барлық салалары функция ұғымына негізделген. X болсын -
Функцияны қатынас тұрғысынан көрсету
f екілік қатынасы функция деп аталады, егер және -ден
Инъекция, сюръекция, бижекция
«Карталау» терминін пайдаланған кезде XbY салыстыру мен Х-ны Y-ге салыстыру арасында айырмашылық жасалады.
Кері функция
Еріктілер үшін біз анықтаймыз
Жартылай реттелген жинақтар
S жиынына рефлексивті, транзитивті және антисимметриялық екілік ішінара реттілік қатынасы берілсе, ол ішінара реттелген (PUM) деп аталады.
Көрсетілімді азайтуды орнату
Осы заңдылықтарды пайдалана отырып, амалдар арқылы М жиынының бейнеленуін минимумға келтіру мәселесін қарастырамыз
Қайта реттеулер
А жиыны берілген. А n элементтен тұратын шекті жиын болсын A = (a1, a2, …, a
Қайталанатын орын ауыстырулар
А жиынында бірдей (қайталанатын) элементтер болсын. Композицияны қайталаумен ауыстыру (n1, n2, … ,nk
Орналастырулар
Ұзындығы k (1≤k≤n) кортеждері, n-элементтік жиынының әртүрлі элементтерінен тұратын А (кортеждер бір-бірінен ерекшеленеді
Қайталанатын орындар
А жиынында бірдей (қайталанатын) элементтер болсын. k атауының n элементінің қайталануы бар орналастырулар
Тәртіпті орналастыру
n нысанды m ұяшыққа орналастырайық, сонда әрбір қорапта бұрынғыдай оған орналастырылған нысандар жиыны емес, реттілік болады. Екі
Комбинациялар
m-элемент А жиынынан n ұзындығының реттелген жиынын саламыз, оның элементтері тақырыптары бірдей орналасулар.
Қайталаулармен комбинациялар
Алынған формулалар А жиынында бірдей элементтер болмаған кезде ғана жарамды болады. n типті элементтер және олардың кортежі болсын
Функция құру әдісі
Бұл әдіс комбинаторлық сандарды санау және комбинаторлық сәйкестіктерді орнату үшін қолданылады. Бастапқы нүкте реттілік (ai) комбинаторы болып табылады
Алгебралық жүйе
А алгебралық жүйесі – ‹M,O,R› жиыны, оның бірінші компоненті M бос емес жиын, екінші компоненті O жиыны.
Тұйықталу және субалгебралар
Ішкі жиын φ егер операциясы бойынша жабық деп аталады
Бір екілік амалы бар алгебралар
М жиынында бір екілік операция берілсін. Ол тудыратын алгебраларды қарастырайық, бірақ алдымен екілік амалдардың кейбір қасиеттерін қарастырамыз. Екілік о
Группоид
Пішін алгебрасы<М, f2>топоид деп аталады. Егер f2 көбейту сияқты операция болса (
Бүтін сандар модулі m
Бүтін сандар сақинасы берілген
Сәйкестіктер
Алгебраға сәйкестік A =
Графтар теориясының элементтері
Графиктер – математикалық объектілер. График теориясы физика, химия, байланыс теориясы, компьютерлік дизайн, электротехника, машина жасау, сәулет, зерттеу сияқты салаларда қолданылады.
График, шың, жиек
Бағытсыз граф (немесе қысқаша айтқанда, график) деп біз осындай ерікті жұпты айтамыз G =
Корреспонденция
Бағытталған G графының басқа, жиі қолданылатын сипаттамасы X төбелерінің жиынын және Г сәйкестігін көрсетуден тұрады.
Бағытсыз график
Егер жиектерде бағдар болмаса, онда график бағытталмаған (бағытсыз көшірме немесе бағдарсыз) деп аталады.
Инцидент, аралас график
Егер e шетінде (u, v) немесе пішіні болса<и, v>, онда біз e жиегі оқиға вер екенін айтамыз
Кері сәйкестік
Өйткені ол осындай шыңдардың жиынын білдіреді
Графикалық изоморфизм
Екі график G1 =
Жолға бағытталған бағыт
Бағытталған графиктің жолы (немесе бағытталған маршруты) доғалар тізбегі болып табылады
Іргелес доғалар, іргелес шыңдар, шыңдар дәрежесі
Доғалары a = (xi, xj), xi ≠ xj, ортақ соңғы төбелері бар, n
Қосылу мүмкіндігі
Графиктегі екі төбе, егер оларды қосатын қарапайым жол болса, олар қосылған деп аталады. Графиктің барлық төбелері қосылса, ол қосылған деп аталады. Теорема.
Салмақталған доға графигі
G = (N, A) графигі өлшенген деп аталады, егер қандай да бір l функциясы: A → R А доғалар жиынында анықталғандай
Күшті байланыс матрицасы
Күшті байланыс матрицасы: диагональ бойымен 1 қойыңыз; X1 жолын толтырыңыз - егер шыңға X1 және X1-ден жетуге болатын болса d
Ағаштар
Ағаштар білімнің әртүрлі салаларында қолданбаларды табуымен ғана емес, сонымен қатар графтар теориясында ерекше орынға ие болғандықтан да маңызды. Соңғысы ағаш құрылымының өте қарапайымдылығынан туындайды
Кез келген тривиальды емес ағаштың кем дегенде екі ілулі шыңы болады
Дәлелдеу G(V, E) ағашын қарастырайық. Ағаш - бұл байланысты график
Теорема
Еркін ағаштың ортасы бір төбеден немесе екі іргелес төбеден тұрады: Z(G) = 0&k(G) = 1 → C(G) = K1
Бағытталған, реттелген және екілік ағаштар
Бағытталған (реттелген) ағаштар практикалық өмірде де, математика мен бағдарламалауда да жиі кездесетін иерархиялық қатынастардың абстракциясы болып табылады. Ағаш (бағдар)
Дәлелдеу
1. Әрбір доға кейбір түйінге кіреді. 9.2.1 анықтамасының 2 тармағынан бізде: v
Тапсырыс берген ағаштар
Orderev балама анықтамасындағы T1,..., Tk жиындары ішкі ағаштар болып табылады. Егер ішкі ағаштардың салыстырмалы реті T1,...,
Бинарлы ағаштар
Екілік (немесе екілік) ағаш - бұл бос немесе түбірден және екі ажыратылған екілік ағаштан - сол және оң жақтан тұратын түйіндердің соңғы жиынтығы. Екілік ағаш java тілінде емес
Ағашты тегін көрсету
Ағаштарды көрсету үшін жалпы графиктерді көрсету сияқты әдістерді қолдануға болады - іргелес және инцидент матрицалары, іргелес тізімдер және т.б. Бірақ арнайы қасиеттерін пайдалана отырып
үшін аяқталады
Негіздеме Прюфер коды шын мәнінде еркін ағаш көрінісі болып табылады. Мұны тексеру үшін, егер T» ағаш екенін көрсетейік
Бинарлы ағаштардың көрінісі
Кез келген бос ағашты оның түйіндерінің бірін түбір ретінде белгілеу арқылы бағдарлауға болады. Кез келген тапсырысқа ерікті түрде тапсырыс беруге болады. Реттелген тәртіптің бір түйінінің (ағаларының) ұрпақтары үшін ол салыстырмалы түрде анықталады
Негізгі логикалық функциялар
Екі саннан тұратын жиынды E2 = (0, 1) деп белгілейік. 0 және 1 сандары дискретті кілемшеде негізгі болып табылады
Логикалық функция
x1, x2, … ,xn аргументтерінің логикалық функциясы жиынның n-ші дәрежесінен алынған f функциясы болып табылады.
Екі элементті буль алгебрасы
Во = (0,1) жиынын қарастырайық және көздер кестелері бойынша оған амалдарды анықтайық.
Логикалық функциялар кестелері
n айнымалының логикалық функциясын екі баған мен 2n жолдан тұратын кесте арқылы көрсетуге болады. Бірінші баған В-дан барлық жиындарды тізімдейді
F5 – y ішінде қайталау
f6 – қосынды модулі 2 f7
Операциялар тәртібі
Күрделі өрнекте жақша болмаса, онда амалдар келесі ретпен орындалуы керек: конъюнкция, дизъюнкция, импликация, эквиваленттілік, терістеу. Шеннонның бірінші теоремасының орналасуына қатысты конвенциялар
Бастапқы φ формуласына SDNF және SCNF эквивалентін табу мәселесін шешу үшін алдымен логикалық функцияның f(x1, x2 кеңейтулерін қарастырамыз.
Шеннонның екінші теоремасы
Дуальдылық принципінің арқасында 6.4.3 теоремасы (Шеннонның екінші теоремасы) буль алгебралары үшін орындалады. Кез келген логикалық функция f(x1, x2,...
Функционалдық толықтық
Теорема (функционалдық толықтық туралы). Кез келген логикалық f функциясы үшін f функциясын көрсететін φ формуласы бар
sdnf табу алгоритмі
SDNF табу үшін бұл формуланы алдымен DNF-ге келтіру керек, содан кейін оның конъюнктілерін келесі әрекеттерді қолданып бірлік құрамдас бөліктеріне айналдыру керек: а) конъюнктураға кейбіреулер кірсе.
Квин әдісі
Берілген логикалық функцияны көрсететін MDNF табу үшін Квин әдісін қарастырыңыз. Келесі үш операцияны анықтайық: - толық желімдеу операциясы -
Логикалық функциялардың канондық көрінісі
Логикалық (формулалар) функциялардың канондық пішіндері логикалық функцияны бірегей түрде көрсететін логикалық формуланың стандартты пішіні бар өрнектер болып табылады. Алгебрада
Логикалық функциялық жүйелер
Логикалық функциялар f(g1, g2, …, gm) және g1(x1, x2, …, xn), g2(x1) болсын.
Жегалкин негізі
Оны сынап көрейік Жүйені қарастырайық. Ол толық, өйткені стандартты негіздегі кез келген функция терминдермен көрсетіледі
Пост теоремасы
Пост теоремасы бульдік функциялар жүйесінің толықтығы үшін қажетті және жеткілікті шарттарды белгілейді. (Post E.L. Математикалық логиканың екі мәнді интерактивті жүйелері. – Math Annals. Stu.
Дәлелдеу
Қажеттілік. Керісінше. Болсын
Жегалкин алгебра Ұсыныс логикасы Предикаттың анықтамасы Алгебрадағы предикаттарды қолдану Бульдік предикат алгебра F↔G=(F→G)(G→F), F→G=FG емес Предикатты есептеу Келесі және эквиваленттілік Қабылданған белгілер Мета белгілеулер X жиынындағы R екілік қатынас болсын. R қатынасы деп аталады рефлексиялық
, егер (x, x) О R барлық x О X үшін; симметриялы
– егер (x, y) О R-ден (y, x) О R келсе; өтпелі сан 23, егер (x, y) О R және (y, z) О R (x, z) О R білдірсе, 24 нұсқасына сәйкес келеді. 1-мысал Біз x О X деп айтамыз ортақ қасиеті бар
y О X элементімен, егер жиын болса Эквиваленттік қатынас X бойынша рефлексиялық, өтпелі және симметриялық қатынас. R Í X ´ X эквиваленттік қатынас болатынын түсіну оңай, егер қосындылар орындалса ғана: Id X Í R (рефлексия), R -1 Í R (симметрия), R ° R Í R (өтпелілік). Шындығында бұл үш шарт келесіге тең: Id X Í R, R -1 = R, R ° R = R. Бөлу арқылы X жиынының - UA = X болатындай жұптастырылған a Í X ішкі жиындарының A жиыны. Әрбір А бөлімімен ~ эквиваленттік қатынасын X бойынша байланыстыруға болады, егер x пен у кейбір a Î A элементтері болса, x ~ y қоя аламыз. . X бойынша әрбір ~ эквиваленттік қатынасы A бөліміне сәйкес келеді, оның элементтері ішкі жиындар болып табылады, олардың әрқайсысы ~ қатынасындағылардан тұрады. Бұл ішкі жиындар деп аталады эквиваленттік кластар
. Бұл А бөлімі ~-ке қатысты Х жиынының факторлық жиыны деп аталады және былай белгіленеді: X/~. w натурал сандар жиынындағы ~ қатынасын анықтайық, егер х пен у-ны 3-ке бөлгеннен қалған қалдықтар тең болса, x ~ y мәнін қоямыз. Сонда w/~ 0, 1 және 2 қалдықтарына сәйкес келетін үш эквиваленттік кластан тұрады. Тапсырыс қатынасы Х жиынындағы екілік R қатынасы деп аталады антисимметриялық
, егер x R y және y R x нүктелерінен келесідей болады: x = y. Х жиынындағы екілік R қатынасы деп аталады тәртіп қатынасы
, егер ол рефлексивті, антисимметриялық және транзитивті болса. Бұл келесі шарттарға сәйкес келетінін көру оңай: 1) Id X Í R (рефлексия), 2) R Ç R -1 (антисиметрия), 3) R ° R Í R (өтпелілік). X жиынынан және X бойынша R реттік қатынастан тұратын реттелген жұп (X, R) деп аталады жартылай тапсырыс жиынтығы
. 1-мысал X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) болсын ), (1, 3), (2, 2), (3, 3)). R 1 – 3 шарттарды қанағаттандыратындықтан, (X, R) жартылай реттелген жиын болады. x = 2, y = 3 элементтері үшін x R y де, у R x те дұрыс емес. Мұндай элементтер деп аталады теңдесі жоқ
. Әдетте реттік қатынас £ арқылы белгіленеді. Келтірілген мысалда 0 £ 1 және 2 £ 2, бірақ 2 £ 3 екені дұрыс емес. 2-мысал Болсын< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество. Жартылай реттелген жиынның (X, £) x, y О X элементтері шақырылады салыстырмалы
, егер x £ y немесе y £ x болса. Жартылай реттелген жиын (X, £) шақырылады сызықтық реттелген
немесе шынжыр
, егер оның кез келген екі элементі салыстырмалы болса. 2-мысалдағы жиын сызықтық реттелген болады, бірақ 1-мысалдағы жиын емес. Жартылай реттелген жиынның (X, £) A Í X ішкі жиыны шақырылады жоғарыда шектелген
, барлық а О A үшін £ x болатындай x О X элементі болса. x О X элементі деп аталады. ең үлкен
X-де егер y £ x барлығы үшін y О X. x О X элементі максималды деп аталады, егер x £ y болатын x-тен өзгеше y О X элементтері болмаса. 1-мысалда 2 және 3 элементтер максимум болады, бірақ ең үлкен емес. Сол сияқты анықталған төменгі шегі
ішкі жиындар, ең кіші және ең кіші элементтер. 1-мысалда 0 элементі ең кіші және ең кіші болады. 2-мысалда 0 де осы қасиеттерге ие, бірақ (w, £) ең үлкен де, ең үлкен элемент те жоқ.
Қосынды модулі 2, конъюнкция және 0 және 1 тұрақтылары функционалды толық жүйені құрайды, яғни. алгебраны құрастыру – Жегалкин алгебрасы. A=
Математикалық логика табиғи тілдің синтаксисі (формасы) және семантикасы (мазмұны) туралы негізгі ұғымдарды зерттейді. Математикалық логиканың үш негізгі зерттеу саласын – логиканы қарастырайық
X1, X2, ..., Xn ерікті айнымалылар болсын. Бұл айнымалыларды тақырыптық айнымалылар деп атаймыз. Айнымалы мән сізді орнатсын
Бір ғана айнымалысы бос, біз х деп белгілейтін предикаттарды қарастырайық және алгебрадағы предикаттардың қолданылуын талқылайық. Типтік мысал
Логикалық амалдарды предикаттарға қолдануға болатындықтан, олар үшін буль алгебраның негізгі заңдары жарамды. Теорема. (Предикаттар үшін логикалық амалдардың қасиеттері). Mn
2. Заңды емес F=F емес, де Морган заңдарын қолданыңыз: емес (Ф
Предикаттарды есептеу бірінші ретті теория деп те аталады. Предикаттық есепте, сондай-ақ болжамдық есепте бірінші орында шешілу мәселесі тұрады.
Q2 ұсыныс формасы Q1 → Q2 импликациясы ақиқатқа айналса, Q1 ұсыныс түрінен шығады.
«Артық тапсырыс бермеу» символдары. f(n) және g(n) (теріс емес мәндермен) екі функцияның өсу жылдамдығын салыстыру кезінде мыналар өте ыңғайлы.
Таңбалар Мазмұны Мысал НЕМЕСЕ
x Ç y бос емес. Ортақ қатынас рефлексивті және симметриялы болады, бірақ өтпелі емес.
