Կախված է բազմաթիվ գործոններից. Համարժեք հարաբերություններ. Գործոնների հավաքածուներ. Կոմպլեկտներ նշելու մեթոդներ

Եթե ​​վերաբերմունքը Ռ ունի հետևյալ հատկությունները՝ ռեֆլեկտիվ սիմետրիկ անցումային, այսինքն. բազմության վրա համարժեքության հարաբերություն է (~ կամ ≡ կամ E): Մ , ապա համարժեքության դասերի բազմությունը կոչվում է բազմության գործակիցների բազմություն Մ համարժեքության վերաբերյալ Ռ և նշանակված է Մ/Հ

Կոմպլեկտի տարրերի ենթաբազմություն կա Մ համարժեք x , կանչեց համարժեքության դաս.

Գործոնների բազմության սահմանումից հետևում է, որ այն բուլյանի ենթաբազմություն է. .

Ֆունկցիան կոչվում է նույնականացումև սահմանվում է հետևյալ կերպ.

Թեորեմ.Գործոնային հանրահաշիվ Ֆ n /~ իզոմորֆ է Բուլյան ֆունկցիաների հանրահաշվին Բ n

Ապացույց.

Պահանջվող իզոմորֆիզմ ξ : Ֆ n / ~ → Բ n-ը որոշվում է հետևյալ կանոնով՝ համարժեքության դաս ~(φ) գործառույթը համընկնում է f φ , ունենալով բազմությունից կամայական բանաձևի ճշմարտության աղյուսակ ~(φ) . Քանի որ տարբեր համարժեքության դասեր համապատասխանում են ճշմարտության տարբեր աղյուսակների, քարտեզագրումը ξ ներարկային, և քանի որ ցանկացած բուլյան ֆունկցիայի համար զ -ից Պ–ում կա ֆունկցիան ներկայացնող բանաձև զ, ապա քարտեզագրումը ξ սուբյեկտիվ. Պահպանման գործողությունները, 0, 1, երբ ցուցադրվում է ξ ուղղակիորեն ստուգվում է. CTD.

Յուրաքանչյուր հաստատուն չհանդիսացող ֆունկցիայի ֆունկցիոնալ ամբողջականության թեորեմով 0 , համապատասխանում է որոշ SDNF-ի ψ , դասին պատկանող ~(φ) = ξ -1 (զ) բանաձևեր, որոնք ներկայացնում են ֆունկցիա զ . Դասարանում լինելու խնդիր է առաջանում ~(φ) տարանջատող նորմալ ձև, որն ունի ամենապարզ կառուցվածքը։

Աշխատանքի ավարտ -

Այս թեման պատկանում է բաժնին.

Դիսկրետ մաթեմատիկա առարկայի դասախոսությունների դասընթաց

Մոսկվայի պետական ​​շինարարական համալսարան.. Կառավարման էկոնոմիկայի և շինարարության տեղեկատվական համակարգերի ինստիտուտ.. IEEE..

Եթե ​​Ձեզ անհրաժեշտ է լրացուցիչ նյութ այս թեմայի վերաբերյալ, կամ չեք գտել այն, ինչ փնտրում էիք, խորհուրդ ենք տալիս օգտագործել որոնումը մեր աշխատանքների տվյալների բազայում.

Ի՞նչ ենք անելու ստացված նյութի հետ.

Եթե ​​այս նյութը օգտակար էր ձեզ համար, կարող եք այն պահել ձեր էջում սոցիալական ցանցերում.

Այս բաժնի բոլոր թեմաները.

Դիսկրետ մաթեմատիկայի առարկա
Դիսկրետ (վերջավոր, վերջավոր) մաթեմատիկայի առարկան մաթեմատիկայի մի ճյուղ է, որն ուսումնասիրում է դիսկրետ կառուցվածքների հատկությունները, իսկ դասական (շարունակական) մաթեմատիկան՝ առարկաների հատկությունները։

Իզոմորֆիզմ
Գիտությունը, որն ուսումնասիրում է հանրահաշվական գործողությունները, կոչվում է հանրահաշիվ: Այս հայեցակարգը կդառնա ավելի կոնկրետ և կխորանա դասընթացն ուսումնասիրելիս: Հանրահաշիվին հետաքրքրում է միայն այն հարցը, թե ԻՆՉՊԵՍ գործել

Զորավարժություններ
1. Ապացուցեք, որ իզոմորֆ քարտեզագրումը միշտ իզոտոն է, և հակառակը ճիշտ չէ: 2. Գրեք ձեր խումբը հավաքածուների լեզվով: 3. Բազմությունների լեզվով գրի՛ր այն առարկաները, որոնք

Կոմպլեկտ և հավաքածուի տարրեր
Ներկայումս գոյություն ունեցող բազմությունների տեսությունները տարբերվում են հայեցակարգային հիմքի և տրամաբանական միջոցների պարադիգմատիկայի (տեսակետների համակարգի) առումով։ Այսպիսով, որպես օրինակ կարող ենք բերել երկու հակադիր

Վերջավոր և անվերջ բազմություններ
Այն, ինչից բաղկացած է հավաքածուն, այսինքն. Օբյեկտները, որոնք կազմում են բազմություն, կոչվում են դրա տարրեր: Կոմպլեկտի տարրերը տարբերվում են և տարբերվում միմյանցից: Ինչպես երևում է բերված օրինակից

Կոմպլեկտի հզորությունը
Վերջավոր բազմության համար կարդինալությունը հավասար է նրա տարրերի թվին: Օրինակ՝ B(A) տիեզերքի կարդինալությունը A բազմության կարդինալության n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |Ա1A2A3…An|
A վերջավոր բազմությունն ունի k կարդինալություն, եթե այն հավասար է 1 հատվածին.. k;:

Ենթաբազմություն, սեփական ենթաբազմություն
Բազմության հայեցակարգի ներդրումից հետո խնդիր է առաջանում գոյություն ունեցողներից կառուցել նոր բազմություններ, այսինքն՝ սահմանել գործողություններ բազմությունների վրա: M-ի հավաքածու,

Իմաստալից բազմությունների տեսությունների խորհրդանշական լեզուն
Դասընթացի ուսումնասիրության ընթացքում մենք կտարբերակենք բազմությունների տեսության առարկայական լեզուն և մետալեզուն, որի միջոցով ուսումնասիրվում է առարկայական լեզուն։ Բազմությունների տեսության լեզու ասելով հասկանում ենք հարաբերական

Ապացույց
B բազմությունը անսահման է, ինչը նշանակում է

Նյութերի ավելացում և հեռացում
Եթե ​​A-ն բազմություն է, իսկ x-ը տարր է, ապա տարրը

Սահմանափակ հավաքածուներ. Սահմաններ դրեք
Թող թվային ֆունկցիան տրվի f(x) X որոշ բազմության վրա: f(x) ֆունկցիայի վերին սահմանը (սահմանը) այդպիսի թիվ է

Ճշգրիտ վերին (ստորին) սահման
Բոլոր վերին սահմանների բազմությունը E-ով նշվում է, իսկ բոլոր ստորին սահմանները՝ Ei-ով: Դեպքում

Հավաքածուի ճշգրիտ վերին (ներքևի) սահմանը
Եթե ​​z տարրը պատկանում է E բազմության և նրա բոլոր վերին սահմանների բազմության հատմանը (համապատասխանաբար ստորին r.

Վերին և ստորին սահմանների հիմնական հատկությունները
Թող X լինի մասամբ դասավորված բազմություն։ 1. Եթե, ապա

Սահմանել վերագրելի տեսանկյունից
Համախառն տեսակետը, ի տարբերություն վերագրվող տեսակետի, տրամաբանորեն անհիմն է այն իմաստով, որ այն հանգեցնում է Ռասելի և Կանտորի տիպի պարադոքսների (տես ստորև): վերագրվող տ

Կառուցվածք
Մասամբ դասավորված X բազմությունը կոչվում է կառուցվածք, եթե այն պարունակում է որևէ երկտարրից բաղկացած բազմություն

Ծածկման և բաժանման հավաքածուներ
A բազմության միջնորմը Ai ընտանիքն է

Երկուական հարաբերություններ
n երկարության հաջորդականությունը, որի անդամներն են a1, .... an, կնշանակվի (a1, .... a.

Երկուական հարաբերությունների հատկությունները
Երկուական R կապը Ho բազմության վրա ունի հետևյալ հատկությունները. ա) ռեֆլեքսիվ, եթե xRx

Երրորդական հարաբերություններ
Դեկարտյան արտադրանք XY

N-ար հարաբերություններ
Համեմատելով X,Y երկու բազմությունների դեկարտյան արտադրյալի հետ՝ մենք կարող ենք կառուցել X-ի դեկարտյան արտադրյալը։

Ցուցադրումներ
Քարտեզագրումները որոշ կապեր են հավաքածուների տարրերի միջև: Հարաբերությունների ամենապարզ օրինակներն են անդամակցության x հարաբերությունները

Նամակագրություն
Դեկարտյան արտադրյալի S ենթաբազմությունը կոչվում է Mi բազմությունների տարրերի n-ական համապատասխանություն: Ֆորմալ կերպով

Գործառույթ
Դիսկրետ մաթեմատիկայի բոլոր ճյուղերը հիմնված են ֆունկցիա հասկացության վրա։ Թող X -

Հարաբերությունների առումով ֆունկցիայի ներկայացում
Երկուական f հարաբերությունը կոչվում է ֆունկցիա, եթե և-ից

Ներարկում, ներարկում, բիեկցիա
«Քարտեզագրում» տերմինն օգտագործելիս տարբերակվում է XbY-ի և X-ի Y-ի քարտեզագրման միջև:

Հակադարձ ֆունկցիա
Կամայականների համար մենք սահմանում ենք

Մասնակի պատվիրված կոմպլեկտներ
S բազմությունը կոչվում է մասնակի կարգավորված (PUM), եթե նրան տրված է ռեֆլեքսիվ, անցողիկ և հակասիմետրիկ երկուական մասնակի կարգի հարաբերություն։

Սահմանել ներկայացուցչության նվազագույնի հասցնելը
Օգտվելով այս օրենքներից՝ մենք դիտարկում ենք M բազմության ներկայացվածությունը նվազագույնի հասցնելու խնդիրը՝ օգտագործելով գործողությունները

Վերադասավորումներ
Տրված է A բազմություն: Թող A-ն լինի վերջավոր բազմություն, որը բաղկացած է n տարրից A = (a1, a2, …, a

Փոխակերպումներ՝ կրկնություններով
Թող A բազմությունը ունենա նույնական (կրկնվող) տարրեր: Փոխակերպում կազմի կրկնություններով (n1, n2, …, nk

Տեղաբաշխումներ
K (1≤k≤n) երկարությամբ զույգեր, որոնք բաղկացած են A-ի n-տարրերի բազմության տարբեր տարրերից (բաժանորդները տարբերվում են.

Տեղադրումներ՝ կրկնություններով
Թող A բազմությունը ունենա նույնական (կրկնվող) տարրեր: k անունների n տարրերի կրկնություններով տեղադրումներ

Կանոնավոր տեղաբաշխում
Եկեք տեղադրենք n առարկա m վանդակներում այնպես, որ յուրաքանչյուր տուփ պարունակի հաջորդականություն, և ոչ թե, ինչպես նախկինում, իր մեջ տեղադրված առարկաների հավաքածու: Երկու

Համակցություններ
m-տարրերի բազմությունից մենք կառուցում ենք n երկարության դասավորված բազմություն, որի տարրերը նույն թեմաներով դասավորություններ են։

Համակցություններ կրկնություններով
Ստացված բանաձևերը վավեր են միայն այն դեպքում, երբ A բազմությունում նույնական տարրեր չկան: Թող լինեն n տեսակի տարրեր և դրանցից բազմապատիկ

Ֆունկցիայի գեներացման մեթոդ
Այս մեթոդը օգտագործվում է համակցական թվեր հաշվելու և համակցական ինքնություններ հաստատելու համար։ Ելակետը հաջորդականության (ai) կոմբինատորն է

Հանրահաշվական համակարգ
A հանրահաշվական համակարգը ‹M,O,R› հավաքածու է, որի առաջին բաղադրիչը M-ը ոչ դատարկ բազմություն է, երկրորդ բաղադրիչը O-ը բազմություն է:

Փակում և ենթահաշիվներ
Ենթաբազմությունը փակված է φ գործողության ներքո, եթե

Հանրահաշիվներ մեկ երկուական գործողությամբ
Թող տրվի մեկ երկուական գործողություն Մ բազմության վրա։ Եկեք դիտարկենք նրա ստեղծած հանրահաշիվները, բայց նախ կքննարկենք երկուական գործողությունների որոշ հատկություններ: Երկուական o

Խմբոիդ
Ձևի հանրահաշիվ<М, f2>կոչվում է խմբոիդ: Եթե ​​f2-ը բազմապատկման նման գործողություն է (

Ամբողջ թվեր մոդուլային մ
Տրվում է ամբողջ թվերի օղակ . Հիշեցնենք. Հանրահաշիվ<М,

Համապատասխանություններ
Համապատասխանություն հանրահաշվի վրա A = (Σ – հանրահաշվի ստորագրությունը բաղկացած է միայն ֆունկցիայի նշաններից) նման համարժեքության հարաբերություն է կոչվում

Գրաֆների տեսության տարրեր
Գրաֆիկները մաթեմատիկական առարկաներ են: Գրաֆիկների տեսությունը օգտագործվում է այնպիսի ոլորտներում, ինչպիսիք են ֆիզիկան, քիմիան, հաղորդակցության տեսությունը, համակարգչային դիզայնը, էլեկտրատեխնիկան, մեքենաշինությունը, ճարտարապետությունը, հետազոտությունները

Գրաֆիկ, գագաթ, եզր
Չուղղորդված գրաֆիկ ասելով (կամ, կարճ ասած, գրաֆիկ) մենք հասկանում ենք այնպիսի կամայական զույգ G = , Ինչ

Նամակագրություն
Ուղղորդված G գրաֆիկի մեկ այլ, ավելի հաճախ օգտագործվող նկարագրությունը բաղկացած է X գագաթների մի շարք և Г համապատասխանության սահմանումից,

Չուղղորդված գրաֆիկ
Եթե ​​եզրերը չունեն կողմնորոշում, ապա գրաֆիկը կոչվում է չուղղորդված (չուղղված կրկնօրինակ կամ չկողմնորոշված):

Միջադեպ, խառը գրաֆիկ
Եթե ​​e եզրն ունի (u, v) կամ<и, v>, ապա կասենք, որ e եզրը միջադեպ ver

Հակադարձ Match
Քանի որ այն ներկայացնում է նման գագաթների մի շարք

Գրաֆիկի իզոմորֆիզմ
Երկու գրաֆիկ G1 = և G2 = իզոմորֆ են (Գ

Ուղին ուղղված երթուղի
Ուղղորդված գրաֆիկի ուղին (կամ ուղղորդված երթուղին) կամարների հաջորդականությունն է, որում

Կից աղեղներ, հարակից գագաթներ, գագաթային աստիճան
Աղեղներ a = (xi, xj), xi ≠ xj, ունեն ընդհանուր ծայրային գագաթներ, n

Միացում
Գրաֆիկի երկու գագաթները կոչվում են միացված, եթե կա դրանք միացնող պարզ ճանապարհ: Գրաֆիկը կոչվում է միացված, եթե նրա բոլոր գագաթները միացված են: Թեորեմ.

Կշռված աղեղային գրաֆիկ
G = (N, A) գրաֆիկը կոչվում է կշռված, եթե l ֆունկցիան. A → R սահմանված է A աղեղների բազմության վրա, որպեսզի.

Ուժեղ կապի մատրիցա
Ուժեղ կապի մատրիցա. դրեք 1 անկյունագծով; լրացրեք X1 տողը, եթե գագաթը հասանելի է X1 և X1 դ

Ծառեր
Ծառերը կարևոր են ոչ միայն այն պատճառով, որ դրանք կիրառություն են գտնում գիտելիքի տարբեր ոլորտներում, այլ նաև այն պատճառով, որ նրանք հատուկ դիրք ունեն գրաֆների տեսության մեջ: Վերջինս պայմանավորված է ծառի կառուցվածքի ծայրահեղ պարզությամբ

Ցանկացած ոչ տրիվիալ ծառ ունի առնվազն երկու կախովի գագաթ
Ապացույց Դիտարկենք G(V, E) ծառը: Հետևաբար, ծառը կապված գրաֆիկ է

Թեորեմ
Ազատ ծառի կենտրոնը բաղկացած է մեկ գագաթից կամ երկու հարակից գագաթներից՝ Z(G) = 0&k(G) = 1 → C(G) = K1

Ուղղորդված, պատվիրված և երկուական ծառեր
Ուղղորդված (պատվիրված) ծառերը հիերարխիկ հարաբերությունների աբստրակցիա են, որոնք շատ հաճախ են հանդիպում ինչպես գործնական կյանքում, այնպես էլ մաթեմատիկայի և ծրագրավորման մեջ: Ծառ (կողմնորոշում)

Ապացույց
1. Յուրաքանչյուր աղեղ մտնում է ինչ-որ հանգույց: 9.2.1 սահմանման 2-րդ կետից ունենք՝ գ

Պատվիրված ծառեր
T1,..., Tk բազմությունները կարգևի համարժեք սահմանման մեջ ենթածառեր են։ Եթե ​​ենթածառերի հարաբերական կարգը T1,...,

Երկուական ծառեր
Երկուական (կամ երկուական) ծառը հանգույցների վերջավոր հավաքածու է, որը կա՛մ դատարկ է, կա՛մ բաղկացած է արմատից և երկու իրարից անջատված երկուական ծառերից՝ ձախ և աջ: Երկուական ծառ ոչ java-ում

Ծառերի անվճար ներկայացուցչություն
Ծառերը ներկայացնելու համար կարող եք օգտագործել նույն տեխնիկան, ինչ ընդհանուր գրաֆիկները ներկայացնելու համար՝ հարևանության և պատահականության մատրիցներ, հարևանության ցուցակներ և այլն: Բայց օգտագործելով հատուկ հատկությունները

Վերջ համար
Հիմնավորումը Prüfer ծածկագիրը իսկապես ծառի անվճար ներկայացում է: Սա ստուգելու համար եկեք ցույց տանք, որ եթե T»-ը ծառ է

Երկուական ծառերի ներկայացում
Ցանկացած ազատ ծառ կարող է կողմնորոշվել՝ նրա հանգույցներից մեկը որպես արմատ նշանակելով: Ցանկացած պատվեր կարելի է պատվիրել կամայականորեն։ Պատվիրված կարգի մեկ հանգույցի (եղբայրների) հետնորդների համար այն սահմանվում է հարաբերական

Հիմնական տրամաբանական գործառույթներ
E2 = (0, 1) նշանակենք երկու թվից բաղկացած բազմություն։ 0 և 1 թվերը հիմնական են դիսկրետ գորգում

Բուլյան ֆունկցիա
N արգումենտների բուլյան ֆունկցիան x1, x2, … ,xn բազմության n-րդ աստիճանից f ֆունկցիա է:

Երկու տարրից բաղկացած Բուլյան հանրահաշիվ
Դիտարկենք Во = (0,1) բազմությունը և սահմանենք գործողություններ դրա վրա՝ ըստ աղբյուրների աղյուսակների.

Բուլյան ֆունկցիայի աղյուսակներ
N փոփոխականների բուլյան ֆունկցիան կարող է սահմանվել երկու սյունակներից և 2n տողերից բաղկացած աղյուսակով: Առաջին սյունակում թվարկված են B-ի բոլոր հավաքածուները

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. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Ապացույց
Անհրաժեշտություն. Հակառակից. Թող այդպես լինի; թող դա լինի

Ժեգալկինի հանրահաշիվ
Գումարի 2 մոդուլը, կապը և 0 և 1 հաստատունները կազմում են ֆունկցիոնալ ամբողջական համակարգ, այսինքն. կազմել հանրահաշիվ - Ժեգալկինի հանրահաշիվ: A=

Առաջարկային տրամաբանություն
Մաթեմատիկական տրամաբանությունն ուսումնասիրում է բնական լեզվի շարահյուսության (ձևի) և իմաստաբանության (բովանդակության) հիմնական հասկացությունները։ Դիտարկենք մաթեմատիկական տրամաբանության հետազոտության երեք հիմնական ուղղություն՝ տրամաբանությունը

Նախադրյալի սահմանում
Թող X1, X2, ..., Xn լինեն կամայական փոփոխականներ: Մենք այս փոփոխականները կանվանենք առարկայական փոփոխականներ։ Թող փոփոխականը սահմանի ձեզ

Նախադրյալների կիրառումը հանրահաշիվում
Դիտարկենք պրեդիկատներ, որոնցում միայն մեկ փոփոխական է ազատ, որը մենք նշում ենք x-ով, և քննարկենք պրեդիկատների օգտագործումը հանրահաշիվում։ Տիպիկ օրինակ

Բուլյան պրեդիկատ հանրահաշիվ
Քանի որ տրամաբանական գործողությունները կարող են կիրառվել պրեդիկատների նկատմամբ, Բուլյան հանրահաշվի հիմնական օրենքները վավեր են նրանց համար։ Թեորեմ. (պրեդիկատների տրամաբանական գործողությունների հատկությունները): Մն

F↔G=(F→G)(G→F), F→G=ոչ FG
2. Օգտագործեք օրենքը ոչ թե F=F, դե Մորգանի օրենքները՝ ոչ (F

Պրեդիկատի հաշվարկ
Նախադրյալների հաշվարկը կոչվում է նաև առաջին կարգի տեսություն։ Նախադրյալ հաշվում, ինչպես նաև դրույթային հաշվում առաջին կարևորագույն տեղը լուծելիության խնդիրն է։

Հետևում և համարժեքություն
Առաջադրական Q2 ձևը բխում է Q1 առաջարկական ձևից, եթե Q1→Q2 ենթատեքստը ճշմարիտ է դառնում

Ընդունված նշումներ
«Այլևս կարգի» խորհրդանիշներ. F(n) և g(n) (ոչ բացասական արժեքներով) երկու ֆունկցիաների աճի տեմպը համեմատելիս շատ հարմար է հետևյալը.

Մետա նշանակումներ
Նշաններ Բովանդակություն Օրինակ ԿԱՄ

Թող R լինի երկուական հարաբերություն X բազմության վրա։ R կապը կոչվում է արտացոլող , եթե (x, x) О R բոլոր x О X-ի համար; սիմետրիկ – եթե (x, y) О R-ից հետևում է (y, x) О R; 23 անցումային թիվը համապատասխանում է 24 տարբերակին, եթե (x, y) О R և (y, z) О R-ն ենթադրում են (x, z) О R.

Օրինակ 1

Մենք կասենք, որ x О X ընդհանուր բան ունի y О X տարրով, եթե բազմությունը
x Ç y-ը դատարկ չէ: Ընդհանրություն ունենալու հարաբերությունը կլինի ռեֆլեքսիվ և սիմետրիկ, բայց ոչ անցողիկ:

Համարժեքության հարաբերություն X-ի վրա ռեֆլեքսիվ, անցումային և սիմետրիկ հարաբերություն է։ Հեշտ է տեսնել, որ R Í X ´ X կլինի համարժեքության հարաբերություն, եթե և միայն այն դեպքում, եթե ընդգրկումները պահպանվեն.

Id X Í R (ռեֆլեքսիվություն),

R -1 Í R (սիմետրիա),

R ° R Í R (անցանելիություն):

Իրականում այս երեք պայմանները համարժեք են հետևյալին.

Id X Í R, R -1 = R, R ° R = R:

Պառակտվելով X բազմության A բազմությունը A Í X զույգ-անջատված ենթաբազմությունների A բազմությունն է այնպես, որ UA = X: A յուրաքանչյուր բաժանման հետ մենք կարող ենք X-ի վրա կապել ~ համարժեքության առնչություն՝ դնելով x ~ y, եթե x-ը և y-ը a-ի որոշ տարրեր են: .

X-ի վրա համարժեքության յուրաքանչյուր հարաբերություն համապատասխանում է A բաժանմանը, որի տարրերը ենթաբազմություններ են, որոնցից յուրաքանչյուրը բաղկացած է ~ հարաբերության մեջ գտնվողներից։ Այս ենթաբազմությունները կոչվում են համարժեքության դասեր . Այս բաժանումը A կոչվում է X բազմության գործակիցների բազմություն ~-ի նկատմամբ և նշանակվում է X/~:

Սահմանենք ~ հարաբերությունը w բնական թվերի բազմության վրա՝ դնելով x ~ y, եթե x-ը և y-ը 3-ի բաժանելուց մնացած մնացորդները հավասար են։ Այնուհետև w/~ բաղկացած է երեք համարժեք դասերից, որոնք համապատասխանում են 0, 1 և 2 մնացորդներին։

Պատվերի հարաբերություն

Երկուական R կապը X բազմության վրա կոչվում է հակասիմետրիկ , եթե x R y-ից և y R x-ից հետևում է՝ x = y: Երկուական R կապը X բազմության վրա կոչվում է պատվերի հարաբերություն , եթե այն ռեֆլեքսիվ է, հակասիմետրիկ և անցողիկ։ Հեշտ է տեսնել, որ դա համարժեք է հետևյալ պայմաններին.

1) Id X Í R (ռեֆլեքսիվություն),

2) R Ç R -1 (հակասիմետրիա),

3) R ° R Í R (անցանելիություն).

Կանչվում է կարգավորված զույգը (X, R), որը բաղկացած է X բազմությունից և 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, ոչ 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-ի բազմությունը՝ ոչ:

Կոչվում է մասնակի կարգավորված բազմության A Í X ենթաբազմությունը (X, £): սահմանափակված վերևում , եթե կա x О X այնպիսի տարր, որ £ x բոլոր a О A-ի համար: x О X տարրը կոչվում է. ամենամեծն X-ում, եթե y £ x բոլոր y Օ X-ի համար: x О X տարրը կոչվում է առավելագույն, եթե չկան x-ից տարբերվող y О X տարրեր, որոնց համար x £ y: Օրինակ 1-ում 2-րդ և 3-րդ տարրերը կլինեն առավելագույնը, բայց ոչ ամենամեծը: Նմանապես սահմանված է ստորին սահմանը ենթաբազմություններ, ամենափոքր և նվազագույն տարրեր: Օրինակ 1-ում 0 տարրը կլինի և՛ ամենափոքրը, և՛ նվազագույնը: Օրինակ 2-ում 0-ն ունի նաև այս հատկությունները, բայց (w, £) չունի ոչ ամենամեծ, ոչ էլ առավելագույն տարրը:

Թող (X, £) լինի մասամբ դասավորված բազմություն, A Í X ենթաբազմություն: A-ի հետ կապված հարաբերությունը, որը բաղկացած է a, b О A տարրերի զույգերից (a, b), որոնց համար a £ b-ը կլինի կարգի հարաբերություն A-ի վրա: Այս հարաբերությունը նշվում է նույն խորհրդանիշով. £: Այսպիսով, (A, £) մասամբ պատվիրված բազմություն է։ Եթե ​​գծային կարգավորված է, ապա կասենք, որ Ա-ն է շղթա մեջ (X, £):

Առավելագույն սկզբունք

Որոշ մաթեմատիկական պնդումներ չեն կարող ապացուցվել առանց ընտրության աքսիոմայի: Այս հայտարարությունները ասվում է կախված է ընտրության աքսիոմից կամ վավեր է ZFC տեսության մեջ , գործնականում ընտրության աքսիոմի փոխարեն ապացուցման համար սովորաբար օգտագործվում է կա՛մ Զերմելոյի աքսիոմը, կա՛մ Կուրատովսկի-Զորնի լեմման, կա՛մ ընտրության աքսիոմին համարժեք որևէ այլ պնդում։

Կուրատովսկի-Զորն Լեմմա. Եթե ​​յուրաքանչյուր շղթա մասամբ պատվիրված հավաքածուի մեջ(X, £) սահմանափակվում է վերեւից, ապա ներս X կա առնվազն մեկ առավելագույն տարր:

Այս լեմման համարժեք է ընտրության աքսիոմային, ուստի այն կարելի է ընդունել որպես աքսիոմ։

Թեորեմ.Ցանկացած մասնակի պատվիրված հավաքածուի համար(X, £) կա հարաբերություն պարունակող հարաբերություն£ և փոխակերպում X գծային կարգավորված հավաքածուի մեջ:

Ապացույց. £ հարաբերություն պարունակող բոլոր կարգի հարաբերությունների բազմությունը դասավորված է ներառման U հարաբերությամբ: Քանի որ կարգի հարաբերությունների շղթայի միավորումը կլինի կարգի հարաբերություն, ապա Կուրատովսկի-Զորնի լեմայի համաձայն գոյություն ունի առավելագույն R հարաբերություն, որը x £ y-ն ենթադրում է x R y: Ապացուցենք, որ R-ը X գծային կարգ ունեցող հարաբերություն է: Ենթադրենք հակառակը՝ թող գոյություն ունենա a, b О X այնպիսին, որ ոչ (a, b), ոչ (b, a)-ը չեն պատկանում R-ին: Դիտարկենք հարաբերությունը.

R¢ = R È ((x, y): x R a և b R y):

Այն ստացվում է R¢-ին ավելացնելով (a, b) զույգը և (x, y) զույգերը, որոնք պետք է գումարվեն R¢-ին այն պայմանից, որ R¢ կարգի հարաբերություն է։ Հեշտ է տեսնել, որ R¢-ն ռեֆլեքսիվ է, հակասիմետրիկ և անցողիկ: Մենք ստանում ենք R Ì R¢, որը հակասում է R-ի առավելագույնին, հետևաբար, R-ն ցանկալի գծային կարգի հարաբերությունն է։

Գծային կարգավորված X բազմությունը կոչվում է լավ դասավորված, եթե դրա յուրաքանչյուր ոչ դատարկ A Í X ենթաբազմություն պարունակում է a Î A ամենափոքր տարրը: Կուրատովսկի-Զորնի լեմման և ընտրության աքսիոմը նույնպես համարժեք են հետևյալ հայտարարությանը.

Զերմելոյի աքսիոմա. Յուրաքանչյուր հավաքածուի համար կա կարգի հարաբերություն, որը այն վերածում է ամբողջությամբ պատվիրված հավաքածուի:

Օրինակ՝ բնական թվերի w բազմությունը ամբողջությամբ դասավորված է։ Ինդուկտիվության սկզբունքը ամփոփվում է հետևյալ կերպ.

Տրանսֆինիտային ինդուկցիա. Եթե(X, £) լրիվ դասավորված բազմություն է, իսկ F(x)-ը նրա տարրերի հատկությունն է,ճշմարիտ է ամենափոքր x 0 О X տարրի համար և այնպես, որ F(y)-ի ճշմարտությունից բոլոր y-ի համար < z следует истинность F(z), то F(x) ճիշտ է բոլորի համար x О X .

Այստեղ y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

Հզորության հայեցակարգ

Թող f: X à Y և g: Y à Z լինեն բազմությունների քարտեզներ: Քանի որ f և g հարաբերություններ են, դրանց կազմը սահմանվում է g ° f(x) = g(f(x)): Եթե ​​h: Z à T-ը բազմությունների քարտեզ է, ապա h ° (g ° f) = (h ° g) ° f: Id X և Id Y հարաբերությունները ֆունկցիաներ են, հետևաբար, սահմանվում են Id Y ° f = f ° Id x = f կոմպոզիցիաները: X = Y-ի համար մենք սահմանում ենք f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f:

F: X àY քարտեզագրումը կոչվում է ներարկման միջոցով , եթե X բազմության x 1 ¹ x 2 տարրերի համար ճշմարիտ է f(x 1) ¹ f(x 2): f-ի քարտեզագրումը կոչվում է վիրահատություն , եթե յուրաքանչյուր y OY-ի համար կա x O X այնպիսին, որ f(x) = y: Եթե ​​f-ը և՛ ներարկում է, և՛ ներարկում, ապա f կոչվում է բիեկցիա . Հեշտ է տեսնել, որ f-ը բիեկցիա է, եթե և միայն այն դեպքում, եթե f -1 Í Y ´ X հակադարձ կապը ֆունկցիա է:

Մենք կասենք, որ հավասարությունը |X| = |Y|, եթե X-ի և Y-ի միջև կա բիեկցիա: Թող |X| £ |Y|, եթե կա f ներարկում` X à Y:

Կանտոր-Շրյոդեր-Բերնշտայն թեորեմ. Եթե|X| £ |Y| Եվ|Ը| £ |X| , Դա|X| = |Y|.

Ապացույց. Ըստ պայմանի, կան f ներարկումներ՝ X à Y և g: Y à X: Թող A = g¢¢Y = Img լինի Y բազմության պատկերը g քարտեզագրման նկատմամբ: Հետո

(X \ A) Ç (gf)¢¢ (X \ A) = Æ,

(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,

(gf) n ¢¢ (X \ A) Ç (gf) n+1 ¢¢ (X \ A) = Æ, …

Դիտարկենք j քարտեզագրումը. X à A, տրված որպես j(x) = gf(x),

x Î (X \ A) È (gf)¢¢ (X \ A) È (gf) 2 ¢¢ (X \ A) È …, և j(x) = x այլ դեպքերում: Հեշտ է տեսնել, որ j-ն բիեկցիա է: X-ի և Y-ի միջև պահանջվող բիեկցիան հավասար կլինի g -1 ° j-ի:

Կանտորի հականոմինիա

Թող |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

Կանտորի թեորեմ. Ցանկացած X, |X| բազմության համար< |P(X)|, где P(X) – множество всех подмножеств множества X.

(այսինքն, որն ունի հետևյալ հատկությունները. բազմության յուրաքանչյուր տարր համարժեք է իրեն, եթե xհամարժեք y, Դա yհամարժեք x; Եթե xհամարժեք y, Ա yհամարժեք զ, Դա xհամարժեք զ ).

Այնուհետև կանչվում է համարժեքության բոլոր դասերի բազմությունը գործոնային հավաքածուև նշանակված է. Բազմության բաժանումը համարժեք տարրերի դասերի կոչվում է իր ֆակտորիզացիա.

Ցուցադրել ից Xհամարժեքության դասերի բազմության մեջ կոչվում է գործոնի քարտեզագրում.

Օրինակներ

Խելամիտ է օգտագործել սահմանված ֆակտորիզացիան՝ կիսանորմատիվներից նորմատիվ տարածություններ ստանալու համար, գրեթե ներքին արտադրյալով տարածություններից ներքին արտադրյալով տարածություններ և այլն: Դրա համար մենք ներկայացնում ենք, համապատասխանաբար, դասի նորմը, որը հավասար է կամայական տարրի նորմ, իսկ դասերի ներքին արտադրյալը՝ որպես դասերի կամայական տարրերի ներքին արտադրյալ։ Իր հերթին, համարժեքության կապը ներկայացվում է հետևյալ կերպ (օրինակ՝ նորմալացված քանորդային տարածություն ձևավորելու համար). ներմուծվում է սկզբնական կիսամիջուկային տարածության ենթաբազմություն, որը բաղկացած է զրոյական կիսանորմ ունեցող տարրերից (ի դեպ, այն գծային է, այսինքն. դա ենթատարածություն է) և համարվում է, որ երկու տարրերը համարժեք են, եթե դրանց տարբերությունը պատկանում է հենց այս ենթատարածությանը։

Եթե ​​գծային տարածությունը ֆակտորիզացնելու համար ներմուծվում է որոշակի ենթատարածություն և ենթադրվում է, որ եթե սկզբնական տարածության երկու տարրերի տարբերությունը պատկանում է այս ենթատարածությանը, ապա այդ տարրերը համարժեք են, ապա գործակիցների բազմությունը գծային տարածություն է և կոչվում է. գործոնային տարածություն.

Օրինակներ

տես նաեւ

Վիքիմեդիա հիմնադրամ. 2010 թ.

Տեսեք, թե ինչ է «Factor set»-ը այլ բառարաններում.

Վերացականության միջոցով սահմանումների հիմքում ընկած տրամաբանական սկզբունքը (Տե՛ս Սահմանում վերացականության միջոցով). Հավասարության տեսակի ցանկացած հարաբերություն, որը սահմանվում է որոշ սկզբնական տարրերի վրա, բաժանում է (բաժանում, դասակարգում) բնօրինակը... ...

Մտածողության ձև, որն արտացոլում է առարկաների և երևույթների էական հատկությունները, կապերն ու փոխհարաբերությունները դրանց հակասության և զարգացման մեջ. միտք կամ մտքերի համակարգ, որն ընդհանրացնում է, առանձնացնում որոշակի դասի առարկաները՝ ըստ որոշակի ընդհանուրի և ընդհանուրի... ... Խորհրդային մեծ հանրագիտարան

Գալուա խմբի կոհոմոլոգիա. Եթե ​​M-ը աբելյան խումբ է և M-ի վրա գործող ընդարձակման Galois խումբ, ապա Galois cohomology խմբերը համախոհ խմբեր են, որոնք սահմանվում են բոլոր քարտեզներից բաղկացած համալիրով, իսկ d-ը սահմանային օպերատոր է (տես Խմբերի կոհոմոլոգիա): .. Մաթեմատիկական հանրագիտարան

Շինարարությունը, դեպի դրախտ, սկզբում հայտնվեց բազմությունների տեսության մեջ, այնուհետև լայն կիրառություն գտավ հանրահաշվի, տոպոլոգիայի և մաթեմատիկայի այլ ոլորտներում: I. p.-ի կարևոր հատուկ դեպքը նույն տեսակի մաթեմատիկական կառուցվածքների ուղղորդված ընտանիքի I. p.-ն է: Թող լինի… Մաթեմատիկական հանրագիտարան

Կետերը թեև հարաբերական են X բազմության վրա գործող G խմբին (ձախ կողմում), բազմությունը G-ի ենթախումբ է և կոչվում է: կայունացուցիչ կամ կետի անշարժ ենթախումբ G-ի նկատմամբ: Քարտեզագրումը առաջացնում է բիեկցիա G/Gx-ի և G(x) ուղեծրի միջև: ՄԱՍԻՆ.… … Մաթեմատիկական հանրագիտարան

Այս հոդվածը չափազանց կարճ ներածություն ունի: Խնդրում ենք ավելացնել ներածական բաժին, որը համառոտ կներկայացնի հոդվածի թեման և ամփոփի դրա բովանդակությունը... Վիքիպեդիա

Այս հոդվածը հանրահաշվական համակարգի մասին է։ Մաթեմատիկական տրամաբանության այն ճյուղի համար, որն ուսումնասիրում է դրույթները և դրանց վերաբերյալ գործողությունները՝ տե՛ս Տրամաբանության հանրահաշիվ։ Բուլյան հանրահաշիվը ոչ դատարկ A բազմություն է՝ երկու երկուական գործողություններով (զուգակցման անալոգը), ... ... Վիքիպեդիա

Թող համարժեքության հարաբերություն տրվի բազմության վրա: Այնուհետև բոլոր համարժեքության դասերի բազմությունը կոչվում է գործակիցների բազմություն և նշվում։ Բազմության բաժանումը համարժեք տարրերի դասերի կոչվում է դրա ֆակտորիզացիա: Քարտեզագրում-ից մինչև... ... Վիքիպեդիա

Երկրաչափության մեջ ուղղորդված հատվածը հասկացվում է որպես դասավորված զույգ կետեր, որոնցից առաջինը՝ A կետը, կոչվում է իր սկիզբ, իսկ երկրորդը՝ B՝ վերջ։ Բովանդակություն 1 Սահմանում ... Վիքիպեդիա

Մաթեմատիկայի տարբեր ճյուղերում քարտեզագրման միջուկը որոշակի բազմության միջուկ է, որն ինչ-որ իմաստով բնութագրում է f-ի և ներարկային քարտեզագրման տարբերությունը։ Հատուկ սահմանումը կարող է տարբեր լինել, բայց ներարկային քարտեզագրման համար f... ... Վիքիպեդիա

Աշխատանքի աղբյուր. Առաջադրանք 10_20. Միասնական պետական ​​քննություն 2018 Սոցիալական ուսումնասիրություններ. Լուծում

Առաջադրանք 20.Կարդացեք ստորև բերված տեքստը, որում բացակայում են մի շարք բառեր (արտահայտություններ): Ընտրեք բառերի (արտահայտությունների) ցանկից, որոնք պետք է տեղադրվեն բացերի փոխարեն:

«Կյանքի որակը կախված է բազմաթիվ գործոններից՝ սկսած մարդու բնակության վայրից մինչև ընդհանուր սոցիալ-տնտեսական և (Ա) իրավիճակը, ինչպես նաև երկրի քաղաքական գործերի վիճակը: Կյանքի որակի վրա այս կամ այն ​​չափով կարող են ազդել ժողովրդագրական իրավիճակը, բնակարանային և արտադրական պայմանները, _____(B) ծավալն ու որակը և այլն։ Կախված տնտեսության կարիքների բավարարման աստիճանից՝ ընդունված է տարբերակել բնակչության կյանքի տարբեր մակարդակները. _____(G) նորմալ մակարդակը՝ ըստ գիտականորեն հիմնավորված չափանիշների, մարդուն ապահովելով ֆիզիկական և մտավոր ուժի վերականգնում. աղքատություն - ապրանքների սպառում աշխատունակության պահպանման մակարդակով, որպես վերարտադրության ամենացածր սահման _____(D); Աղքատությունը կենսաբանական չափանիշների համաձայն ապրանքների և ծառայությունների նվազագույն ընդունելի փաթեթի սպառումն է, որը թույլ է տալիս միայն պահպանել մարդու կենսունակությունը։

Բնակչությունը, հարմարվելով շուկայական պայմաններին, օգտվում է եկամտի տարբեր լրացուցիչ աղբյուրներից, այդ թվում՝ անձնական հողամասերից, շահույթ _____(E)-ից»:

Ցանկի բառերը (արտահայտությունները) տրվում են անվանական գործով: Յուրաքանչյուր բառ (արտահայտություն) կարող է օգտագործվել միայն մեկ անգամ:

Ընտրեք բառը (արտահայտությունը) մյուսի հետևից՝ մտովի լրացնելով յուրաքանչյուր բացը: Խնդրում ենք նկատի ունենալ, որ ցուցակում ավելի շատ բառեր (արտահայտություններ) կան, քան անհրաժեշտ կլինի բացերը լրացնելու համար:

Տերմինների ցանկ.

1) կապիտալ

2) բնապահպանական

3) ռացիոնալ սպառումը

4) սպառողական ապրանքներ

5) արտադրության միջոցներ

7) աշխատուժ

8) ձեռնարկատիրական գործունեություն

9) սոցիալական շարժունակություն

Լուծում.

Եկեք տերմինները մտցնենք տեքստի մեջ։

«Կյանքի որակը կախված է բազմաթիվ գործոններից՝ սկսած անձի բնակության վայրից մինչև ընդհանուր սոցիալ-տնտեսական և բնապահպանական (2) (Ա) իրավիճակը, ինչպես նաև երկրի քաղաքական գործերի վիճակը: Կյանքի որակի վրա այս կամ այն ​​չափով կարող են ազդել ժողովրդագրական իրավիճակը, բնակարանային և արտադրական պայմանները, սպառողական ապրանքների ծավալն ու որակը (4) (B) և այլն: Կախված տնտեսության կարիքների բավարարման աստիճանից. ընդունված է տարբերակել բնակչության տարբեր կենսամակարդակները. հարստություն - նպաստների օգտագործում (6) (B), որոնք ապահովում են անձի համակողմանի զարգացումը. ռացիոնալ սպառման նորմալ մակարդակ (3) (D) ըստ գիտականորեն հիմնավորված չափանիշների, որը մարդուն ապահովում է ֆիզիկական և մտավոր ուժի վերականգնում. աղքատություն - ապրանքների սպառում աշխատունակության պահպանման մակարդակում որպես աշխատուժի վերարտադրության ամենացածր սահման (7) (D); Աղքատությունը կենսաբանական չափանիշների համաձայն ապրանքների և ծառայությունների նվազագույն ընդունելի փաթեթի սպառումն է, որը թույլ է տալիս միայն պահպանել մարդու կենսունակությունը։