1. Agar funktsiya a ni b ga turli qiymatli akslantirish bo‘lsa, u holda funktsiya a va b to‘plamlarning o‘zaro bir qiymatli mosligi


Download 0.85 Mb.
bet29/53
Sana10.08.2023
Hajmi0.85 Mb.
#1666230
1   ...   25   26   27   28   29   30   31   32   ...   53
Bog'liq
disker sessiya

3) Qo‘shnilik matritsasi. Faraz qilaylik G graf yo‘naltirilmagan bo‘lsin. Grafning qo‘shnilik matritsasida Aij ning ustunlariga ham qatorlariga ham grafning tugunlarini mos qo‘yamiz. U xolda

Aij=





Qo‘shmalik(insidentlik) matritsasi. Bizga G yo‘naltirilmagan graf berilgan bo‘lib, u chekli bo‘lsin. Aytaylik (a1,…,an), G grafning qirralari bo‘lsin. U holda qo‘shmalik matritsasi ||Aij||, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo‘ladi, Aij matritsaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo‘yamiz. U holda
Aij=
qoidadan foydadanib qo’shmalik matritsasini hosil qilamiz.

13.3-Misol.




a1

a2

a3

a4

a5

a6

a7

e1

1

1

0

0

0

0

0

e2

1

0

1

0

0

0

0

e3

0

1

0

1

0

0

0

e4

1

0

0

0

1

0

0

e5

0

1

0

0

0

1

0

e6

0

0

1

1

0

0

0

e7

0

0

1

0

1

0

0

e8

0

0

0

1

0

1

0

e9

0

0

0

0

1

0

1

e10

0

0

0

0

0

1

1



36 BILET

  1. 1. Binar munosabat. Diskret matematikada fundamental tushun chalardan biri bo'lgan munosabat tushunchasi predmetlar (narsalar) va tushunchalar orasidagi aloqani ifodalaydi. Quyidagi toiiqsiz gaplar munosabatlarga misol bo'la oladi. Odatda, munosabat tushunchasi to'plamlar nazariyasi nuqtai nazaridan turib o'rganiladi. Munosabat tushunchasiga aniqlik kiritish uchun
    tartiblangan juftlik tushunchasini o'rganamiz.
    1- t a ’ r i f . M a’lum tartibda joylashgan ikki predmetdan tuzilga kortej tartiblangan juftlik deb ataladi. Odatda tartiblangan juftlik quyidagi xususiyatlarga ega deb faraz qilinadi:
    1) ixtiyoriy x va у predmetlar uchun < x , y > kabi belgilanadigan muayyan obyekt mavjud bo'lib, har bir x va у predmetlarga yagona tartiblangan < x , y > juftlik mos keladi ( < x , y > yozuv “ x va у ning tartiblangan juftligi” deb o'qiladi);
    2) agar ikkita < x , y > va < u, v > tartiblangan juftlik uchun x = и va
    у = v bo'lsa, u holda < x , y >=< u , v > bo'ladi. < x , y > tartiblangan juftlik < x , y > - {{x},{x,y}} ko'rinishdagi to'plamdir, ya’ni u shunday ikki elementli to'plamki, uning bir elementi {x, y} tartibsiz juftlikdan iborat, boshqa {x} elementi esa, shu tartibsiz juftlikning qaysi hadi birinchi hisoblanishi kerakligini ko'rsatadi. Tartiblangan juftliklardan birgalikda tartiblangan juftliklar to‘plamini tashkil etishadi.
    2 - t a ’ r i f . < x, v > tartiblangan juftlikdagi x uning birinchi koordinatasi, у esa ikkinchi koordinatasi deb ataladi. Tartiblangan juftliklar atamasi asosida tartiblangan n -liklarni aniqlash mumkin. x, v va z predmetlarning tartiblangan uchligi quyidagi tartiblangan juftliklar shaklida aniqianadi: « x , y >, z > . Xuddi shu kabi x,,x2,...,xn predmetlarning tartiblangan « -ligi < x ,,x 2,...,x„ > , ta’rifga asosan, « x, ,x 2,...,x„_, >,x„ > tarzda aniqianadi. Matematik mantiqda n –ar munosabat tartiblangan n -liklar to'plami sifatida aniqianadi.

  2. Formulaning chinlik to‘plami tushunchasi. Ma’lumki, berilgan n ta o‘zgaruvchi elementar mulohazalar uchun barcha bir-biridan farqli mumkin bo‘lgan qiymatlar satrlari kombinatsiyalari n 2 ta (ushbu bobning 1- paragrafiga qarang). Tarkibida n ta o‘zgaruvchilar ishtirok etgan formula shu n 2 ta qiymatlar satrlarining bir qismida 1, qolgan qismida esa 0 qiymatni qabul qiladi. 1- t a ’ r i f. Berilgan formula tarkibidagi elementar mulohazalarning qiymatlaridan qandaydir tartibda tuzilgan va shu formulaning 1 qiymatiga mos keluvchi barcha kortejlar to‘plami formulaning chinlik to‘plami deb ataladi. Ravshanki, tarkibidagi o‘zgaruvchilarning soni qanday bo‘lishidan qat’iy nazar, aynan yolg‘on formulaning chinlik to‘plami bo‘sh () to‘plamdan iboratdir. n ta elementar mulohazalarning mumkin bo‘lgan barcha n 2 2 ta teng kuchlimas formulalaridan C n n 2 1  2 tasi qiymatlar satridagi n ta qiymatlardan faqat bittasi 1, qolgan ( n 1)tasi esa 0 bo‘lganda 1 qiymat qabul qiladi. Shuning uchun, bunday formulalarning har biri bir elementli chinlik to‘plamiga ega. Xuddi shuningdek, n ta elementar mulohazalarning mumkin bo‘lgan barcha teng kuchlimas formulalaridan C n 2 2 tasi qiymatlar satridagi n ta qiymatlardan faqat ikkitasi 1, qolgan ( n  2 )tasi esa 0 bo‘lganda 1 qiymat qabul qiladi. Shu sababli, bunday formulalarning har biri uchun chinlik to‘plam ikkita kortejdan tashkil topgan bo‘ladi. Shu usulda davom etsak, n 2 2 ta teng kuchlimas formulalardan C n 2 3 tasining har biri uch elementli chinlik to‘plamiga, 4 2 C n tasining har biri to‘rt elementli chinlik to‘plamiga, va hokazo, n n C n 2 2 1 2   tasining har biri ( 2 1 n ) elementli chinlik to‘plamiga, bitta ( 1 2 2  n C n ) formula esa n 2 ta elementli chinlik to‘plamiga egaligiga ishonch hosil qilamiz. Tarkibida n ta elementar mulohazalar ishtirok etgan aynan chin formulaga mos chinlik to‘plamni universal to‘plam (U ) deb olsak, tarkibida shu elementar mulohazalar qatnashgan mumkin bo‘lgan barcha formulalarning har biriga mos chinlik to‘plamlar U to‘plamning qism to‘plamlaridan iborat


Download 0.85 Mb.

Do'stlaringiz bilan baham:
1   ...   25   26   27   28   29   30   31   32   ...   53




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling