MAVZU: Takrorsiz va takroriy o’rinlashtirishlar

MAVZU: Takrorsiz va takroriy o’rinlashtirishlar
Guruhlashlar.
Takrorlanmaydigan o'rin almashtirishlar
Agar chekli X to'plam elementlari biror usul bilan nomerlab chiqilgan bo'lsa, X to'plam tartiblangan deyiladi.
Masalan, X={x1, x2, ..., xn}.
Bitta to'plamni turli usullar bilan tartiblash mumkin.
Masalan, sinf o'quvchilarini yoshiga, bo'yiga, og'irligiga qarab
yoki o'quvchilar familiyalari bosh harflarini alifbo bo'yicha tartiblash mumkin.
Takrorlanmaydigan o'rinlashtirishlar
Umumiyroq masalani ko‘rib chiqaylik: m elementli X to'plamdan nechta tartiblangan elementli to'plamlar tuzish mumkin?
Bu masalaning oldingi masaladan farqi shundaki, tartiblash k elementda tugatiladi. Ularning umumiy soni
m(m - 1)(m - 2) • ... • (m - k + 1)
ko'paytmaga teng. U Am bilan belgilanadi va m elementdan k tadan takrorlanmaydigan о‘rinlashtirishlar sonideb ataladi:
Am = m(m- 1)•...•(m - k + 1)
Am= Pm = m! 0! = 1 deb qabul qilinadi
Takrorlanadigan o'rinlashtirishlar
Masala. m elementli X to'plam elementlaridan tuzilgan uzunlikdagi kortejlar sonini toping.
Yechish. O‘rinli kortej X × X ×...× X dekart
ko'paytmaning elementi bo'lib, tartiblangan k-likni (kalik deb o'qiladi) bildiradi. Masalani yechish uchun X×X×...×X dekart ko'paytma elementlari sonini topish kerak. Bu son n(X) = m bo'lgani uchun
n(X × X × . . . × X ) = n(X) • n(X) •... • n(X) = m- m -... m=m
ga teng.
k
}
k marta
Takrorlanmaydigan guruhlashlar
«m elementli X to'plamning nechta elementli qism to'plamlari bor?» — degan masalani
hal qilaylik.
Masalan, 4 elementli A = {a; b; c; d} to'plamning nechta 3 elementli qism to'plami borligini ko'raylik. Ular {a; b; c}, {a; b; d}, {a; c; d}, {b; c; d). Demak, 4 ta shunday qism to'plam bor ekan. Bunday qism to'plamlar takrorlanmaydigan guruhlashlar
deb ataladi.
Mavzu: Matematik mulohazalar va
uning elementlari.
Tushuncha
Atrofimizdagi olam turli obyektlardan iborat. Ular o ‘ziga xos xossalar va o ‘zaro munosabatlarga ega. Bu
obyektlami o‘rganganimizda ularni o‘xshashligi va umumiy xossalariga qarab sinflarga ajratamiz. Bu obyektlar va sinflar ma’lum bir nom bilan nomlanadi. Masalan, «daraxt», «chumchuq»,
«mushuk», «uy», «avtobus» yoki «o‘simlik», «qush», «hayvon»,
«bino», «mashina» va hokazo.
Tushuncha— bu narsalar va hodisalami ba’zi bir muhim alomatlariga ko‘ra farqlash yoki umumiylashtirish natijasi ekan. Alomatlar esa narsa yoki hodisalarning bir-biriga
o ‘xshashligi yoki farqlanishini bildiruvchi xossalardir.
Muhim xossadeb, faqat shu obyektga tegishli va bu xossasiz obyekt mavjud bo‘la olmaydigan xossalarga aytiladi. Obyektning mavjudligiga ta’sir qilmaydigan xossalar muhim bo'lmagan xossalar debsanaladi.
Geometrik tushunchalarga misol qilib uchburchak, to'rtburchak, aylanani keltirishimiz mumkin.
Obyektning barcha muhim xossalari to'plami tushunchaning mazmunini tashkil qiladi. Masalan, «son» tushunchasi mazmuniga sonlarni taqqoslash, yozuvda ifodalash, son o'qida tasvirlash, sonlar ustida turli arifmetik amallar bajarish kabi
xossalar kiradi.
Bir xil muhim xossalarga ega obyektlar to'plami tushuncha hajmini tashkil etadi. Masalan, «son» tushunchasi hajmini natural, nomanfiy, butun, kasr, ratsional, irratsional, haqiqiy, mavhum va kompleks sonlar tashkil etadi.
Demak, tushuncha hajmi bitta tushuncha bilan nomlanishi mumkin bo'lgan obyektlar to'plami ham ekan. Tushuncha mazmuni uning hajmini aniqlaydi va aksincha.
Tushunchaning hajmi qancha «katta» bo'lsa, mazmuni shuncha «kichik» va aksincha bo'ladi.
Tushunchaga ta’rif berishning bir necha usuli bor. Shulardan biri oshkor ta ’rif boiib, unda, ta’riflanayotgan tushunchaga nisbatan umumiyroq tushunchani ko'rsatib, shu umumiy tushuncha bilan nomlangan obyektlardan ta’riflanayotgan tushuncha qanday xossalari bilan ajralib turishi ko'rsatiladi.
Masalan, «barcha tomonlari teng parallelogramm — romb deyiladi», ta’rifida parallelogramm umumiy tushuncha bo'lib , romb qolgan parallelogrammlardan tomonlarining tengligi bilan ajralib turadi. Bunday ta’rif odatda jins va tur orqali ta ’riflash deyiladi.
Jins: parallelogramm
Tur: romb
Tushunchaning ta'rifiga qo'yiladigan talablar
Tushuncha ta’rifiga qo'yiladigan talablar quyidagilardan iborat. Tushuncha ta’rifi:
1) ta’riflanayotgan tushunchani bir qiymatli aniqlashga imkon berishi;
2) avval ma’lum bo'lgan tushunchalarga asoslanishi;
3) yolg'on doiraga, ya’ni tushunchaning o'zi yoki shu
tushuncha bilan ta’riflangan tushuncha orqali ta’riflashga yo'l qo'ymasligi;
4) ortiqcha xossalarni (qolganlaridan keltirib chiqarish mumkin bo'lganlarni) ko'rsatmasligi kerak.
Demak, ta’rifda qisqa va ixcham shaklda ta’riflanayotgan tushuncha haqida aniq m aium ot berilishi kerak.
Mulohaza
Rost yoki yolg‘onligi bir qiymatli aniqlanadigan darak gaplar mulohazadeyiladi.
So'roq yoki his-hayajon gaplar mulohaza bo'la olmaydi. Noma’lum qatnashgan gaplar ham mulohazaga kirmaydi.
Mulohazalar lotin alifbosining bosh harflari:
А, В, C, D, ... orqali belgilanadi.
Mulohazalar sodda va murakkabbo'ladi.
Murakkab mulohazalami sodda mulohazalarga ajratish mumkin.
Mulohaza inkori
A mulohaza inkorideb, A rost bo'lganda yolg'on, yolg'on bo'lganda rost bo'luvchi mulohazaga aytiladi.
A mulohaza inkori Ā ko'rinishda belgilanadi va «А emas», «А ekanligi yolg'on» deb o'qiladi.
Mulohazalar konyunksiyasi
Ikkita sodda A, В mulohazalardan tuzilgan «А va В» mulohazaga mulohazalar konyunksiyasi deyiladi.
Mulohazalar konyunksiyasi uning tarkibiga kirgan mulohazalar rost bo'lganda, rost bo'ladi va « А В» yoki «АВ» ko'rinishda yoziladi hamda «А va В» kabi o'qiladi.
A
|
B
|
|
R
|
R
|
R
|
R
|
Y
|
Y
|
Y
|
R
|
Y
|
Y
|
Y
|
Y
|
Ikkita sodda A, В mulohazalardan tuzilgan «А yoki
В» mulohazaga mulohazalar dizyunksiyasi deyiladi.
Mulohazalar dizyunksiyasi «A v В» ko'rinishda yoziladi, «А yoki B» deb o'qiladi va uning tarkibiga kirgan mulohazalarning hech bo'lmaganda bittasi rost bolganda, rost bo'ladi.
Mulohazalar dizyunksiyasi
A
|
B
|
|
R
|
R
|
R
|
R
|
Y
|
R
|
Y
|
R
|
R
|
Y
|
Y
|
Y
|
Mulohazalar implikatsiyasi
Sodda A va В mulohazalardan tuzilgan «Agar A
bo'lsa, В bo'ladi» ko'rinishidagi mulohaza A va В mulohazalarning implikatsiyasideyiladi va «А=B» ko'rinishda belgilanadi.
A=B implikatsiya faqat A rost, B yolg'on bo'lgandagina yolg‘on bo‘ladi. A — implikatsiya sharti, В — xulosasi deyiladi. A ni B uchun yetarli, B ni A uchun zaruriy shart deb ham ataladi.
A
|
B
|
=
|
R
|
R
|
R
|
R
|
Y
|
Y
|
Y
|
R
|
R
|
Y
|
Y
|
R
|
Mulohazalar ekvivalensiyasi
Sodda A va В mulohazalardan tuzilgan «А faqat va
faqat В bo‘Igandagina bo‘ladi» kо‘rinishdagi mulohaza A va В ning ekvivalensiyasideyiladi va «АВ» ko‘rinishda yoziladi.
AВ ekvivalensiya A va B mulohazalarning qiymatlari bir xil bo'lganda rost bo'ladi.
A
B
|
|
|
|
|
R
|
R
|
R
|
R
|
Y
|
Y
|
|
Y
|
R
|
Y
|
|
Y
|
Y
|
R
|
|
Predikat
O'zgaruvchi qatnashgan va o'zgaruvchi o'rniga qiymatlar qo‘yilgandagina rost yoki yolg'on mulohazaga aylanadigan darak gap predikatdeyiladi.
Predikatlar tarkibiga kirgan o'zgaruvchilar soniga qarab bir o'rinli, ikki o'rinli va hokazo bo‘ladi. Biz ko'proq bir o‘rinli predikat haqida gapiramiz, uni A(х), B(y), ... ko'rinishda belgilaymiz.
Predikat tarkibiga kirgan o'zgaruvchi qabul qilishi mumkin bo'lgan barcha qiymatlar to'plami predikatning aniqlanish sohasi deyiladi. Aniqlanish sohasi X, Y, Z, ... kabi belgilanadi.
O'zgaruvchi o'rniga qo'yilganda predikatni rost mulohazaga aylantiruvchi qiymatlar predikatning rostlik to'plami deyiladi, A(x) predikatning aniqlanish sohasi X to'plam bo'lsa, rostlik to'plami TA bilan belgilanadi va x є Х ТА с Х bo'ladi.
ТА
Х
Predikatni mulohazaga aylantirishning yana bir usuli kvantorlardan foydalanishdir. Ikki xil kvantor bor bo'lib, ularning biri «umumiylik», ikkinchisi «mavjudlik» kvantori deb ataladi.
Umumiylik kvantori « » belgisi bilan belgilanadi va «har bir», «hamma», «barcha» so'zlari bilan ifodalanadi. inglizcha «All» so'zining bosh harfidan olingan va «hamma» ma’nosini bildiradi.
Mavjudlik kvantori « » belgisi bilan belgilanadi, inglizcha «Exist» — «mavjud» so'zining bosh harfidan olingan va «bor», «mavjud», «topiladi» so'zlarini bildiradi.
Kvantor
A
A
E
Predikatning inkori
X to'plamda A(x) predikat berilgan bo'lsin. A(x) rost bo'lganda yolg'on, yolg'on bo'lganda, rost bo'ladigan
Ā(x) predikat A(x) ning inkori deyiladi. A(x)ning rostlik to'plami T bo'lsa, Ā(x)ning rostlik to'plami T' bo'ladi
T
T'
Predikatlar konyunksiyasi
A(x) va B(x) predikatlaming har ikkalasi rost bo‘lganda rost, qolgan hollarda yolg'on bo'ladigan predikatga ularning konyunksiyasideyiladi va
A(x) B(x) ko'rinishda belgilanadi.
Agar A(x) ning rostlik to‘plami TA, B(x) ning rostlik to'plamini TB, A(x) B(x) ning rostlik to'plamini T
desak, T=TATBbo'ladi.
U
Predikatlar dizyunksiyasi
A(x) va B{x) predikatlarning har ikkalasi yolg'on
bo'lganda yolg'on, qolgan barcha hollarda rost bo'ladigan predikatga A(x) va B(x) predikatlar dizyunksiyasideyiladi.
Predikatlar dizyunksiyasi «A(x) v B(x)» ko'rinishda belgilanib, «A(x) yoki B(x)» deb o'qiladi. A(x) predikatning rostlik to'plami TA, B(x) ning rostlik to'plami TB, A (x) v B(x) ning rostlik to'plamini T desak, T=TAU TBbo'ladi.
Predikatlar implikatsiyasi
A(x) predikat rost bo'lib, B(x) predikat yolg'on bo'lganda yolg'on, qolgan hollarda rost bo'ladigan mulohaza A(x)
va B(x) predikatlarning implikatsiyasideyiladi.
Predikatlar implikatsiyasi « A(x) =B(x) » ko'rinishda belgilanadi va u A(x) predikatdan B(x) predikat kelib chiqadi deb o'qiladi. Bu holda B(x) predikat A(x) predikat uchun «zaruriy shart», A(x) predikat B(x) predikat uchun «yetarli shart» deyiladi. A(x) predikatning rostlik to'plami TA, B(x) niki TBva A(x)=B(x)ning rostlik to'plami T bo'lsa, T = T'AUTB bo'ladi.
Predikatlar ekvivalensiyasi
A(x) va B(x) predikatlarning har ikkalasi yolg'on
bo'lganda hamda har ikkalasi rost bo 'lganda rost bo'ladigan, qolgan hollarda yolg'on bo'ladigan mulohaza predikatlar ekvivalensiyasideyiladi.
Predikatlar ekvivalensiyasi A{x)B(x) ko'rinishda belgilanadi va «A(x) bilan B(x) teng kuchli» deb o'qiladi. Agar ikkita predikat teng kuchli, ya’ni ekvivalent bo'lsa, ularning har biri ikkinchisi uchun zaruriy va yetarli shart hisoblanadi.
Teorema
Tushunchalarning asosiy bo'lmagan va ta'rifga kiritilmagan xossalari odatda isbotlanadi.
Tushunchaning isbot qilinadigan xossalari teoremalar deyiladi. Ular har xil ko'rinishda isbotlanishidan qat'i nazar isbotlanishni talab qiladigan fikrlardir.
Shunday qilin, teorema bu a xossadan b xossaning kelib chiqishi haqidagi fikr. Bu fikrning chinligi isbotlash yo'li bilan aniqlanadi.
Teoremaning qismlari
Teoremaning sharti;Teoremaning xulosasi;Tushuntirish qismi
Teoremaning sharti va xulosasi o'rni almashsa, berilgan teoremaga teskariteorema hosil bo'ladi.
Teoremaning sharti va xulosasi ularning inkorlari bilan almashtirilsa, berilgan teoremaga qarama-qarshiteorema hosil bo'ladi:
Mavzu: Algebraik operatsiyalar.
Agar X to'plamdan olingan har bir (x; y) juftlikka
yana shu to ‘plamdan z element mos kelsa, u holda bu moslik X da berilgan binar algebraik operatsiyadeyiladi, ya’ni ( (x; y )єX , zєX)((x ; y) = z).
Misol. Qo‘shish N to‘plamda algebraik operatsiya bo‘ladi.
Haqiqatan ham, ( (a; b)є N, ссN )(a + b = c).
Agar X to ‘plamdan olingan ba ’zi (x; y) — juftliklarga shu to'plamdan bitta z element mos kelsa, u holda bu moslikqisman algebraik operatsiyadeyiladi, ya’ni
( (x;y)єX, zєX )((x ; y) = z).
Masalan, ayirish va bo'lish N da qisman algebraik operatsiya
bo'ladi.
A
E
E
A
E
A
Algebraik operatsiyaning xossalari
X to'plamda * va • algebraik operatsiyalari berilgan bo'lsin.
Agar X to ‘plamdan olingan istalgan x, y, z elementlar uchun (x * y) * z = x *(y * z) shart bajarilsa , u holda «*» operatsiyasi assotsiativ deyiladi, ya’ni ( x, y, zєX)((x*y)*z= x*(y*z)).
Masalan, «+» operatsiyasi N da assotsiativ algebraik operatsiyadir. Chunki
( a, b, cєN )((a+b)+c = a + (b + с)).
А
А
Agar X dan olingan istalgan x, у elementlar uchun
x*y = y*x shart bajarilsa, u holda (*) operatsiyasi kommutativdeyiladi.
Qisqacha: ( x, yєX )(x*y = y*x) kabi yoziladi.
Masalan, (+ ) operatsiyasi N da kommutativdir, chunki
( a,bєN)(a + b = b + a).
Agar X dan olingan istalgan x, y, z elementlar uchun
x * (y•z ) = (x*y)•(x*z) shart bajarilsa, u holda (*) operatsiya (•) ga nisbatan distributivdeyiladi.
Qisqacha ( x, y, zєX ) (x*(y•z)= (x*y)•(x*z)) yoziladi.
Masalan, N da ko'paytirish qo'shishga nisbatan distributiv
bo'ladi. Haqiqatdan ( a, b, cєN)(a • (b + c) = a • b + a • c).
A
A
A
A
Agar X dan olingan istalgan x, у lar uchun shunday bir aєX topilib, x*a = y*a dan x = у kelib chiqsa,u holda (*) operatsiya qisqaruvchan deyiladi.
Qisqacha: ( x, у є X , X ) (a*x = a*y=x = y) kabi yoziladi.
Masalan, a + x = a + у =x = у demak, «+» qisqaruvchan operatsiya.
А
Algebraik operatsiyaning neytral,simmetrik, yutuvchi elementlari
Agar istalgan x є X uchun shunday e є X topilsaki, natijada xTe = eTx = x shart bajarilsa, u holda e shu «Т» operatsiyasi
uchun neytral elementdeyiladi.
Qisqacha ( xєX , eєX)(xTe = eTx = x) kabi yoziladi.
Agar X to'plamda berilgan (*) operatsiyaga nisbatan e є X neytral element bo ‘Isa va
x * x" = x" * x = e shart bajarilsa,
u holda x"єX simmetrik elementdeyiladi.
Masalan, - a element a ga qo'shishga nisbatan simmetrik
bo'ladi, chunki a + (-a) = 0.
А
Е
Agar X to'plamda berilgan (*)ga nisbatan a*e=e*a=e shart bajarilsa, u holda e — yutuvchi element deyiladi.
Masalan, 0 element ko‘paytirishga nisbatan yutuvchidir.
Xulosa
Xulosa qilib aytganda hozirgi zamonaviy asrda kombinatorikaning ahamiyati katta.Biz kombinatorikaga kundalik hayotimizda ham koʻp marotaba murojaat qilamiz.Koʻpincha buni oʻzimiz bilmagan holda amalga oshiramiz misol uchun uyga mehmon kelganda dasturxon tuzashda likopcha sanchiqi qoshiqlarni nechadur xil usulda kombinatsiyalarini amalga oshiramiz.Yoki bizda besh xil turdagi sabzavotlar bor ulardan foydalanib necha xil turdagi salat tayyorlash umkinligi haqida ham kop oylab koʻrganmiz va amalda sinab koʻrganmiz.Shu jarayonlarda biz kombinatorikaning guruhlashlar qismiga murojaat qilamiz.
FOYDALANILGAN ADABIYOTLAR
Yuldashev U. Y.,oqiyev R. R., Zokirova F. M., "Informatika" – T, 2002 y.
Abduqodirov A. A., Hayitov A., Shodiyev R. "Axborot texnologiyalari"– T, 2002 y.
Akademik litseylar uchun "Informatika" fanidan o’quv dasturi – T, 2000 y.
Бекаревич Ю., Пушкина Н. Самоучитель Microsoft Access 2002,
|