Կ-33-1

Բինար հարաբերություններ, գործողություններ նրանց հետ

AxB դեկարտյան արտադրյալի αεAxB ենթաբազմությունն անվանում են բինարհարաբերություն A եւ B բազմությունների տարրերի միջեւ: A եւ B
բազմությունները կոչվում են αεAxB բինար հարաբերության հենքային
բազմություններ:
Եթե a∈A եւ b∈B եւ (a,b)∈α, ապա ասում են, որ a-ն մտնում է b-ի հետ բինար
հարաբերության մեջ եւ գրվում է aαb:
Օրինակներ.
1.Փոքր է հարաբերությունը բնական թվերի միջեւ A=B=N, aαb↔a<b:
2. Փոքր է կամ հավասար հարաբերությունը ռացիոնալ թվերի միջեւ A=B=R,
aαb↔a≤b:
aαb↔a-նծանոթ է b-ին եւ այլն:
Դիցուք αεAxB եւ βεAxB: Քանի որ հարաբերությունը դեկարտյան արտադրյալիենթաբազմություն է, ուստի բնական են հետեւյալ սահմանումները.
ա) -ն կանվանենք α հարաբերության լրացում, կամ α-ին հակադիր
հարաբերություն
բ) -ն կանվանենք αևβ հարաբերությունների միավորում
գ) -ն կանվանենք αևβ հարաբերությունների հատում
և

դ) -ն կանվանենք αևβ հարաբերությունների տարբերություն և
ե) կարգավորված զույգի շրջում կանվանենք կարգավորված զույգը, կամ α-ին հակադարձ հարաբերություն(կնշանակենք ) եւ
կանվանենք այն հարաբերությունը, որին պատկանում են α-ի մեջ մտնող զույգերի շրջումները և միայն նրանք :
Պարզ է, որ

Վերը դիտարկված օրինակներում փոքր է հարաբերության շրջումը կլինի մեծ է հարաբերությունը(լրացում հարաբերությունը կլինի մեծ է կամ հավասարը)։Ծնող հարաբերության շրջումը կլինի զավակ հարաբերությունը, բարեկամ հարաբերության շրջումը նույն բարեկամ հարաբերությունն է։

հարաբերության կտրվածք a∈A տարրի նկատմամբ (կնշանակենքα(а)) կանվանենք այն  տարրերի բազմությունը, որոնք a-ի հետ մտնում են  հարաբերության մեջ

Հետևյալ պնդումներում ցանկացած հարաբերություններ են, իսկ

1․

2․

3․

4.( )=

5.

6.( )=

 ,  հարաբերությունների արտադրյալը նշանակենք կանվանենք այն γ հարաբերությունը А  և C բազմությունների տարրերի միջ, որը որոշվում է հետևյալ եղանակով․

γz  գոյություն ունի y B ((x y) և (y z))

 հարաբերությունը սահմանվում է, երբ առաջին՝  հարաբերության երկրորդ հենքային բազմությունը համընկնում է հարաբերերության  հարաբերության  առաջին հենքային բազմության հետ։ Ընդհանուր դեպքում

Օրինակ․ , իսկ      որոշված են

a b a b : Դժվար չէ ստուգել, որ , իսկ :

Հարաբերությունների որոշ դասեր։ Էքվիվալենտության հարաբերություն

  հարաբերության առաջին հենքային բազմության տարրերի բազմությունը կոչվում է այդ հարաբերության որոշման տիրույթ, իսկ երկրորդ հենքային բազմության տարրերի բազմությունը՝ արժեքների բազմություն։ Հետագայում մենք կդիտարկենք համասեռ հարաբերությունները, որոնց հենքային բազմությունները նույնն են՝ А=B: AxA բազմության  ենթաբազմությունն անվանում են անկյունագծային և նշագրում են :

 հարաբերության ո-րդ աստիճան սահմանենք հետևյալ կերպ

Հեշտ է ստուգել, որ

,

: Իսկապես, երբ n=0

Երբ А-ն անվերջ բազմություն է, և , ապա հարաբերությունները կարող են լինել իրարից տարբեր, օրինակ․  դեպքում ։

երկրորդ հենքային բազմությունը՝ Եվ եթե , ապա y y Վերջավոր բազմությունների դեպքում ճիշտ է հետևյալ պնդումը․

Թեորեմ1․ եթե

և ապա գոյութուն ունեն(i,j)(0≤ )( ):

Ապացուցում․  բազմության ենթաբազմությունների թիվը  է, հետևաբար, к= դեպքում կպարունակի գոնե երկու հավասար անդամ։

Սահմանենք  համասեռ հարաբերության մի քանի դասեր․

ա) հարաբերությունն անվանենք ռեֆլեքսիվ, եթե , կամ, որ նույնն է, եթե ստույգ է բոլոր x-երի համար, որոնք պատկանում ենА-ին պնդումը։

բ) հարաբերությունն անվանենք սիմետրիկ, եթե , կամ էլ որ նույնն է, եթե ստույգ է , պնդումը:

գ) հարաբերությունն անվանենք անտիսիմետրիկ, եթե , կամ էլ որ նույնն է, եթե ստույգ է , x  ⇾x=y պնդումը:

դ) հարաբերությունն անվանենք տրանզիտիվ, եթե , կամ էլ որ նույնն է, եթե ստույգ է , x  ⇾x z պնդումը:

 Նշենք մի քանի հատկություններ՝( )

1.եթե  ռեֆլեքսիվ հարաբերություններ են, ապա , αβ, α β-ն ևս կլինեն ռեֆլեքսիվ,

2․եթե  սիմետրիկ հարաբերություններ են, ապա , , α β-ն ևս կլինեն սիմետրիկ, αβ-ն սիմետրիկ կարող է և չլինել,

3․ եթե α-ն և β-ն սիմետրիկ են, և   αβ=βα, ապա    αβ-ն ևս սիմետրիկ է,

4․ եթե  տրանզիտիվ հարաբերություններ են, ապա , , α⋂β, ևս կլինեն տրանզիտիվ,  αβ և -ն կարող են տրանզիտիվ չլինել։

5․եթե  տրանզիտիվ հարաբերություններ են և αβ= βα, ապա βα տրանզիտիվ է։

6․ Ցանկացած α հարաբերության համար և α սիմետրիկ է։

Դիցուք А-ն վերջավոր բազմություն է  հարաբերության տրանզիտիվ փակում նշանակենք , կանվանենք այն հարաբերությունը, որը բավարարում է հետևյալ պայմաններին՝

ա․ -ը տրանզիտիվ է,

բ․ α :

Սահմանում․  հարաբերությունը կանվանենք էքվիվալենտության հարաբերություն եթե այն ռեֆլեքսիվ է, սիմետրիկ և տրանզիտիվ, կամ էլ որ նույն է ցանկացած x,y, z   տարրերի համար ստույգ են հետևյալ պնդումները՝

1․x

2.եթե x

3.եթե x  , ապա x

Դժվար չէ ստուգել, որ նշված պնդումները համարժեք են հետևյալին․

 և

Օրինակներ․ 1․

2․А-ն դեկարտյան հարթության կետերի բազմությունն է․

3. Երկու կետեր մտնում են α հարաբերության մեջ եթե նրանցով անցնում է  ուղղին զուգահեռ ուղիղ։

Կարգի հարաբերություն

  հարաբերությունը անվանենք կարգի հարաբերություն, եթե այն ռեֆլեքսիվ է, անտիսիմետրիկ և տրանզիտիվ, կամ որ նույնն է x,y,z  կամայական տարրերի համար․

1․x

2.եթե x  , ապա x y

3.եթե x  , ապա x :

Դժվար չէ ստուգել, որ որ նշված պնդումները համարժեք են հետևյալին  և ։

Օրինակներ․

1․A=N և ։

2․ ենթաբազմությունների համար ,

3.A=Zև

4.A=R և :

կարգի հարաբերությունը հաճախ նշանակում են ≼ պայմանշանով․ և եթե կարգի հարաբերությունը, ապա A-ին անվանում են կարգավորված բազմություն և նշանակում կամ շղթա, այստեղ A-ի ցանկացած a և b տարրերիհամար կամ : Այսպես․ 3-րդ և 4-րդ օրինակներում և բազմություններըշղթաներեն, իսկ 1․ և 2․ օրինակներումըոչ։ Մենքկդիտարկենքմիայնվերջավորկարգավորվածբազմությունները։

կարգավորված բազմության տարրըկանվանենքմաքսիմալ, եթեգոյությունչունի այնպիսին, որ  ≽

 բազմության ը կանվանենքմինիմալը, եթեայդբազմությանմեջբոլոր տարրերիհամարտեղիունի

Թեորեմ 1․ կարգավորված ոչ դատարկ բազմությունն ունի մաքսիմալ և մինիմալ տարրերը։

Ապացուցում․ Իրոք, եթե x տարրը մաքսիմալ չէ, ապա գոյություն ունի y որ ։Բայց A-ն վերջավոր է, հետևաբար այդ գործընթացը անվերջ չի շարունակվի, նույն եղանակով կապացուցվիմինիմալ տարրի գոյությունը։

Թեորեմ 2․Եթե կարգավորված  բազմության մաքսիմալ տարրը միակն է, ապա այն ամենամեծն է, եթե մինիմա տարրը միակն է, ապա նա ամենափոքրն է։

Նկատենք, որ այդ պնդումները անվերջ բազմությունների վրա չեն տարածվում։ Դիցուք կարգավորված  բազմություն է և x  :  x-ը կամ մինիմալ է, կամ գոյություն ունեն  տարրեր այնպես, որ , , և -ը  մինիմալ է։ ,  հաջորդականությունը կանվանենք շղթա, որը սկսվում է  մինիմալ տարրով և վերջանում մաքսիմալ տարրով։ Այդ շղթայի երկարությունը կհամարենք նրա տարրերի քանակը`S+1: x-ով վերջացող շղթաների քանակը վերւավոր է, հետևաբար գոյություն ունի ամենաերկարը, որի երկարությունը կնշանակենքd -ով և կանվանենք x տարրի բարձրություն՝  թիվը կանվանենք կարգավորված  բազմության բարձրություն։։

Սահմանենք հետևյալ բազմությունները

Անդրադարձ առնչություններ

Դիտարկենք  ( 1)

Պայմաններին բավարարող հաջորդականության ընդհանուր անդամի գտնելու խնդիրը, երբ հայտնի ֆունցիա է։

( 1) առնծությունից հերթով գտնում ենք թվերը։ Անդրադարձ առնչությունը լուծելու համաչ անհրաժեշտ է -ը արտահայտել n-ի,  ի միջոցով։

Դիտարկենք p=1 մասնավոր դեպքը։ Հերթականորեն գրենք առնչության n=0, n=1, n=2, ...  աևժեքները և գումարենք․

...

Կստանանք
, հետևաբար p=1-ի դեպքում ( 1) առնչության լուծումը կլինի

Նույն դատողությունները կարոց ենթ անել ընդհանուչ դեպքում

...

Այդ հավասարումներից առաջինը բազմապատկելով -ով, երկրորդը երրորդը  և այլն և վերջինը  ով և գումարելով, կստանանք․

                                        (3)    

Քննարկենք մի քանի օրինակներ․

1.Ամենաշատը քանի մասի կբաժանվի հարթությունը ո ուղիղների միջոցով։ Ակնհայտ է, որ ամենաշատմասերի հարթությունը կբաժանվի երբ այդ ուղիղները զուգահեռ չեն և դրանցից ոչ մի եռյակ չի անցնում մի կետով։

նշանակենք n ուղիղներով հարթության տրոհման ամենաշատ մասերի թիվը։ Ակնհայտ է, որ =7: Ենթադրենք հարթությունը ո ուղիղներով տրոհվել է նշված պայմաններով։ տանենք ո+1-րդ ուղիղը։ Այն տարված ուղիղների հետ կհատվի ո կետերում և հարթությունը կբաժանի ևս ո+1 մասի։ (Նկատենք, որ

Օգտվելով  (2) բանաձևից կստանանք՝

Հետաքրքիր անդրադարձ առնչություն է Ֆիբոնաչիի բանաձևը․ , ... ,  անդրադարձ առնչությունը, ինչը գրվել է դեռևս 13-րդ դարում։ Այն բավականաչաձ զգալի տեղ է զբաղացնում մաթեմատիկայի նշված բաժնում և հետագայում պարզվել է, որ այն կապ ունի նաև ոսկե հատման հետ։

 

Տարրական բանաձևեր։ Նյուտոնի երկանդամը

 

Դիցուք և r N: r ընտրույթ А բազմությունից անվանենք այդ բազմության տարրերի հաջորդականությունը(պարտադիր չէ միմյանցից տարբեր)։

Դիտարկենք երկու տիպի ընտրույթներ․

ա) կարգավորված r ընտրույթներ, կամ r երկարությամբ բառեր(հավաքածուներ)А-ից այբուբենում, որոնցում տարբեր տարրերի(տառերի) դասավորությունն էական է: Երկու բառեր կհամարենք իրար հավասար, եթե նրանք ուներ նույն երկարությունը և համապատասխան տեղերում գրված են նույն տառերը,

բ) ոչ կարգավորված r ընտրույթներ А բազմությունից, որոնցում տարրերի դասավորությունն էական չէ, էականը յուրաքանչյուր տարրի համար պատիկությունն է, այն ցույց է տալիս թե а տարրը քանի անգամ է տարրը մտնում r ընտրույթի մեջ: Երկու ոչ կարգավորված ընտրույթ կհամարենք հավասար, եթե А բազմության յուրաքանչյուր տարր նրանցում ունի նույն պատիկությունը և  համապատասխան տեղերում գրված են նույն տառերը։

Հետագայում կդիտարկենք նաև ընտրույթներ չկրկնվող տարրերով, որոնցում A-ին պատկանող յուրաքանչյուր a տարրի համար՝պատիկությունը փոքր կամ հավասար է 1-ից և ընտրույթներ կրկնվող տարրերով երբ  A-ին պատկանող յուրաքանչյուր տարր կարող է հանդես գալ 1,2,,․․,r անգամ։

N տարրերից կարգավորված r ընտրույթյուն անվանենք rկարգավորություն ո տարրերից(կարգավորությունում տարրը կարող է հանդես գալ 0 կամ 1 անգամ)։

Թեորեմ1։ա) = , բ) =n(n-1)(n-2)...(n-r+1):

Օրինակ 1․Հաշվել բոլոր յոթանիշ թվերի քանակը։

Օրինակ2․ Հաշվել 3 թվանշանը պարունակող բոլոր հնգանիշ թվերի քանակը։

Լուծում․ Բոլոր հնգանիշ թվերի քանակը 9․ -ն է, իսկ 3 չպարունակողինը՝ -ն է։ 3 պարունակողիների քանակը կյինի 9․ - ։

Օրինակ 3․Գտնել 1,2,․․․ո տարրերի այն տեղափոխությունների քանակը, որոնցում 1-ը և 2-ը գրված են հարևանությամբ։

Լուծում․ 2․

Նյուտոնի երկանդամը

(1)

Ապացուցենք, որ (1)-ը ճիշտ է։ n=2, 3 -ի դեպքում ճիշտ է։ Ապացուցենք, որ այն ճիշտ է կամայական ո-ի դեպքում։ ենթ․ այն ճիշտ է ո-1-ի համար։

,(2)

Սա ստացվում է  նույնությունից, որը հեշտ ապացուցվում է։

Նյուտոնի երկանդամից կարելի է ստանալ տաչբեր հետևանքներ, մենք կսահմանափակվենք դրանցից երկուսով, երբ a=b=1, ապա (2)-ից կստանանք

1.   

2.    , а=1, b=-1

 

Ներառման և արտաքսման սկզբունքը։ Դիրիխլեի սկզբունքը

 

Մաթեմատիկական ինդուկցիայի և Դիրիխլեի սկզբունքի հետ միասին ներառման և արտաքսման սկզբունքը(բանաձևը) մաթեմատիկայում հանդիսանում է կարևորագույն գործիք։ Հատկապես կոմբինատորիկայում, երբիմանալով բազմությունների տարրերի քանակը քանակը(վերջավոր) անհրաժեշտ է լինում գտնել մի այլ բազմության տարրերի քանակը, որը ձևավորվում է հենց այդ բազմությունների տվյալների միավորման և հատման գործողություններից։Երբ խոսքը վերաբերում է 2 կամ 3 բազմություններին, դժվար չէ նկատել․ որ

բանաձևը մենք ստացանք -ից եչկու անգամ կիրառելով գումարի բանաձևը։

նդհանուր դեպքում եփե տրված են և  բազմությունները, ապա

n(A)= -

Ապացուցենք  -ը։ Ենթադրենք x տարրը պատկանում է այդ բազմություններից m-ին, առանց ընթանրությունը խախտելու, կարող ենք ընդունել, որ դրանք , առաջին m բազմություններն են:Ցույց տանք, որ հավասարման ձախ և աջ մասերում վերը նշված x տարրը հանդես է գալիս նույն թվով անգամ։ (3) հավասարման ձախ մասում այն = է 1-ի, աջ մասի առաջին գումարում՝ այն հանդես է գալիս   անգամ, երկրորդ գումարում(գումարելիում) անգամ, երրորդ գումարելիում և այլն m-րդ գումարելիում՝ անգամ։ Բայց Նյուտոնի երկանդամի երկրորդ հետևանքից ։  հավասարման իսկությունը ապացուցվեց։

Խնդիր(Լյուիս Կերոլ)։ Ծեծկռտուքին մասնակիցներից 70%-ը վնասել է աչքը, 75%-ը ականջը, 80%-ը ձեռքը, 85%-ոտքը։ Ամենաքիչը քանի հոգի է վնասել աչքը, ականջը, ձեռքը և ոտքը։

Լուծում․ n(A)-ով նշանակենք մասնակիցների թիվը, )-ով նշանակենք աչքը, ականջը, ձեռքը և ոտքը վնասողների թիվը համապատասխանաբար։ Աչքը և ականջը վնասողների թիվը համաձայն բանաձև կլինի

≥ + -n = ,

Հանգունորեն․

≥ + -n = ,

≥ + -n = ,

Պատասխան ոչ պակաս քան 10 տոկոսը։

 

 

Գրաֆներ

Գրաֆի սահմանումը, տրման եղանակները և պարզագույն հատկությունները

Սահմանում 1․ Գրաֆը վերջավոր V բազմության և այդ բազմության տարրերից կազմված երկտեղանի որոշակի տարրերի E բազմության միավորում բազմությունն է։ V բազմության տարրերը կոչվում են այդ գրաֆի գագաթներ, իսկ E-ի տարրերը՝ կողեր։ Գրաֆը նշանակում են : V-ի a և b տարրերը կոչվում են միացված, եթե (a,b)⋲E։    Սահմանում 2․ Եթե (a,b)-ն կող է, ապա  a-նև b-ն կոչվում են այդ կողի ծայրակետեր և (a,b) կողն անվանում են ինցիդենտ a և b գագաթներին և հակառակը a և b գագաթները կոչվում են ինցիդենտ (a,b) կողին։

Երկու գագաթներ կոչվում են կից, եթե հանդիսանում են նույն կողի ծայրակետեր։

Երկու կող կոչվում են կից եթե նրանք ինցիդենտ են ընդհանուր գագաթին։

Կողը, որը ելնում և մտնում է նույն գագաթը, կոչվում է հանգույց։ Եթե գրաֆում կան հանգույցներ, ապա գրաֆը կոչվում է հանգույցներով գրաֆ։

Եթե գրաֆում երկու գագաթների միջև կան երկու և ավելիկողեր, ապա գրաֆը կոչվում է մուլտիգրաֆ։

Եթե գրաֆում կան հանգույցներ և երկու գագաթներ միացված են երկու և ավելի կողերով, ապա այն կոչվում է պսեվդոգրաֆ։

Գրաֆների տեսության հիմնադիր է համարվում Էյլերը, Քյոնիքսբերգի կամուրջների խնդրով` սկսել և վերադառնալ նույն կետը անցնելով քաղաքի յոթ կամուրջներով յուրաքանչյուր կամուրջով ճիշտ մեկ անգամ։

Սահմանում 3․Գրաֆի գագաթի աստիճան անվանում են այդ գագաթին ինցիդենտ կողերի թիվը։ 0 աստիճանի գագաթը անվանում են մեկուսացված գագաթ։

Թեորեմ 1։ Գրաֆի գագաթների աստիճանների գումարը միշտ զույգ է։

Ապացուցում․ Քանի որ գրաֆում կողն ունի երկու ծայրակետ(գագաթ), ուստի յուրաքանչյուր կող գագաթների աստիճանը ավելացնում է երկուսով, իսկ մեկուսացված գագաթները չեն ազդում աստիճանի վրա։

Թեորեմ 2։ Յուրաքանչյուր գրաֆում կենտ աստիճանով գագաթների թիվը զույգ է։

Ապացուցումը՝ նախորդ թեորեմից։