5 bilet To’plamga tegishlilik tushunchasi. To’plamlarning tengligi. Tа’rif Ikkita to’plam teng

Ekvivalensiyaning chinlik to‘plami. va formulalar ekvivalensiyasining chinlik to‘plamini aniqlash uchun teng kuchlilikdan foydalanamiz. Yuqorida qilingan xulosalarga ko‘ra formulaning chinlik to‘plami bo‘ladi. 2- shaklda tasvirlangan to‘plamning bo‘yalmagan qismi ekvivalensiyaning chinlik to‘plamiga mos keladi

	a1 a2 a3 a4 a5 a6 a7
a1	0 1 1 0 1 0 0
a2	1 0 0 1 0 1 0
a3	1 0 0 1 1 0 0
a4	0 1 1 0 0 1 0
a5	1 0 1 0 0 0 1
a6	0 1 0 1 0 0 1
a7	0 0 0 0 1 1 0

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

A_ij=

Qo‘shmalik(insidentlik) matritsasi. Bizga G yo‘naltirilmagan graf berilgan bo‘lib, u chekli bo‘lsin. Aytaylik (a₁,…,a_n), G grafning qirralari bo‘lsin. U holda qo‘shmalik matritsasi ||A_ij||, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo‘ladi, A_ij matritsaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo‘yamiz. U holda
A_ij=
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