Predikat tushunchasi. Predikatlar ustida mantiqiy amallar

2- misol. To‘g‘ri chiziqlar to‘plamida aniqlangan : « » predikatni ko‘raylik. Agar predikatga nisbatan kvantorli amallarni tadbiq etsak, u holda quyidagi sakkizta mulohazaga ega bo‘lamiz:
1. – «Har qanday to‘g‘ri chiziq har qanday to‘g‘ri chiziqqa perpendikulyar».
2. – «Shunday to‘g‘ri chiziq mavjudki, u har qanday to‘g‘ri chiziqqa perpendikulyar».
3. – «Har qanday to‘g‘ri chiziq uchun shunday to‘g‘ri chiziq mavjudki, to‘g‘ri chizig‘i to‘g‘ri chiziqqa perpendikulyar».
4. – «Shunday to‘g‘ri chiziq va shunday to‘g‘ri chiziq mavjudki, to‘g‘ri chiziq to‘g‘ri chiziqqa perpendikulyar».
5. – «Har qanday to‘g‘ri chiziq har qanday to‘g‘ri chiziqqga perpendikulyar».
6. – «Har qanday to‘g‘ri chiziq uchun shunday to‘g‘ri chiziq mavjudki, to‘g‘ri chiziq to‘g‘ri chiziqqga perpendikulyar».
7. – «Shunday to‘g‘ri chiziq va shunday to‘g‘ri chiziq mavjudki, to‘g‘ri chiziq to‘g‘ri chiziqqa perpendikulyar».
8. – «Shunday to‘g‘ri chiziq mavjudki, u har qanday to‘g‘ri
chiziqqa perpendikulyar». ■
Bu misoldan ko‘rinib turibdiki, umumiy holda kvantorlar tartibi o‘zgarishi bilan mulohazaning mazmuni va, demak, uning mantiqiy qiymati ham o‘zgaradi.
Chekli sondagi elementlari bo‘lgan to‘plamda aniqlangan predikat berilgan bo‘lsin. Agar predikat aynan chin bo‘lsa, u holda mulohazalar ham chin bo‘ladi. Shu holda mulohaza va kon’yunksiya ham chin bo‘ladi.
Agar hech bo‘lmaganda bitta element uchun yolg‘on bo‘lsa, u holda mulohaza va kon’yunksiya ham yolg‘on bo‘ladi. Demak,

teng kuchli ifoda to‘g‘ri bo‘ladi.
Yuqoridagidek fikr yuritish yo‘li bilan

teng kuchli ifodaning mavjudligini ko‘rsatish mumkin.
Bu yerdan kvantorli amallarni cheksiz sohalarda kon’yunksiya va diz’yunksiya amallarining umumlashmasi sifatida qarash mumkinligi kelib chiqadi.

KOMBINATORIKA ELEMENTLARI Ushbu bobda kombinatorikada qo‘llaniladigan usul va qoidalar, kombinatsiyalar, kombinatsiya tushunchasi, o‘rinlashtirishlar, o‘rin almashtirish, guruhlashlar (gruppalashlar), binom formulasi, takrorlanuvchi o‘rinlashtirishlar va o‘rin almashtirish, takrorli guruhlashlarga oid ma’lumotlar bayon qilingan. Shuningdek, kombinatorikaning asosiy qoidalari, o‘rinlashtirishlar, o‘rin almashtirish, guruhlashlar (gruppalashlar), binom formulasi, takrorlanuvchi o‘rinlashtirishlar, o‘rin almashtirish, guruhlashlarga va takrorlashga doir misollar keltirilgan. 1-§ Kombinatorikaning asosiy qoidalari, takrorsiz birlashmalar 1.1.Kombinatorika haqida umumiy tushuncha. Matematikaning kombinatorika (birlashmalar nazariyasi) deb ataluvchi bo„limida chekli yoki muayyan ma‟noda cheklilik shartini qanoatlantiruvchi ixtiyoriy elementlardan iborat to„plamni qismlarga ajratish, o„rin almashtirish, o„rinlashtirish, kombinatsiyalash, ya‟ni birlashmalar tuzish kabi masalalari o„rganiladi. Shuningdek, unda to„plamlar va kombinatsiyalar, ularning birlashmasi va kesishmasi hamda ularni turli usullar bilan tartiblash masalalari ham qaraladi. Kombinatsiya ‒ bu kombinatorikaning asosiy tushunchasi bo„lib, ixtiyoriy to„plamning qandaydir sondagi elementlaridan tuzilgan birlashmalar hisoblanadi. Kombinatorikada bunday birlashmalarni o„rin almashtirish, o„rinlashtirish, guruhlash deb ataluvchi asosiy ko„rinishlari o„rganiladi. Kombinatorik xarakterga ega bo„lgan masalalarda mumkin bo„lgan barcha variantlar sonini hisoblash uchun «nechta?» yoki «necha xil usulda?» kabi savollarga javob berish talab qilinadi. To„plamlar va kombinatsiya tushunchasi yordamida kombinatorikaning asosiy tushunchalarini ifodalash qulay. Elementlarining tartibi bilan bir-biridan farq qiladigan kombinatsiyalarni kortej deb ataymiz. Masalan, juftliklar elementlarining tartibi bilan farqlanuvchi ikkita turli kortej hisoblanadi. Kortejni tashkil qilgan elementlar soni kortejning uzunligi (quvvati) hisoblanadi. Ba‟zi hollarda kortej iborasi o„rniga juftliklar, yani uning uzunligini e‟tiborga olib, ikkilik, uchtalik va hokazo taliklar iborasi ham ishlatiladi

Shu kabi berilgan to„plamlar elemetlaridan tartiblangan uchtaliklar, umuman, ta to„plam elementlaridan tartiblangan taliklar to„plami tuziladi. Uzunliklari teng, tartibi va tarkibi bir xil bo„lgan kortejlar teng deyiladi. Masalan, va √ √ √ kortejlar teng va bir xil uzunliklarda elementlari: √ √ √ Lekin va kortejlarning uzunliklari va elementlari bir xil bo„lsa-da, lekin ular teng emas, chunki koordinatalari turli tartibda joylashgan. Birorta ham elementga ega bo„lmagan, ya‟ni 0 uzunlikdagi talik bo„sh talik deyiladi. To„plamlarda esa elementlarning tartibi rol o„ynamaydi, uzunlikdagi kortejda esa elementlarning tartibi ahamiyatli bo„lib, ular takrorlanishi ham mumkin. Ta’rif. Tartiblangan to„plamning elementlaridan tuzilgan va to„plamning elementini birinchi, to„plamning elementini ikkinchi va hokazo to„plamning elementini o„ringa qo„yib tuzilgan uzunlikdagi kortejlar to„plamiga Dekart ko„paytma deyiladi. Dekart ko„paytma { ̅̅̅ ̅ ̅} ko„rinishida yoziladi. Agar to„plamning birortasi bo„sh to„plam bo„lsa, u holda ulardan foydalanib birorta ham kombinatsiya tuzish mumkin emas. Demak, tarkibida hech bo„lmasa bitta bo„sh to„plam qatnashgan to„plamlarning Dekart ko„paytmasi bo„sh to„plam, ya‟ni bo„lar ekan. 1-misol. { } va { } to„plamlar elementlaridan shunday juftliklar tuzaylikki, ulardagi birinchi o„rindagi to„plamning tartib bilan olingan elementi, ikkinchi o„rinda to„plamning tartib bilan olingan elementi yoziladigan bo„lsin. Hosil bo„ladigan juftliklar to„plamini orqali belgilasak, { } to„plam hosil bo„ladi. Agar birinchi o„rinda to„plamning elementlari qo„yiladigan bo„lsa, yozilishi va tartibi bilan oldingisidan farq qiladigan: { } to„plam hosil bo„ladi. 29 Bu yerda kortejlarning tarkibidagi elementlar shu juftlikning komponentlari yoki koordinatalari deyiladi (lotincha componentis–tashkil etuvchi). 2-misol. { } va { } to„plamlarning Dekart ko„paytmasini topamiz. Dekart ko„paymada oltita kortej mavjud. Ular: { } to„plamni tashkil qiladi. va to„plamlarning elementlari sonini mos ravishda orqali, umumiy juftliklar sonini esa orqali belgilaylik. 1-teorema. va chekli to„plamlarning elementlaridan tuzilgan juftliklar soni shu to„plamlarning elementlari soni ko„paytmasiga teng. Bu teoremadan kombinatorikaning ko„paytirish qoidasi hisoblanib, undan quyidagi xulosa kelib chiqadi. Xulosa. Umuman, ta chekli to„plamdan tuzilgan uzunligi songa teng kombinatsiyalar soni bo„lar ekan. 2-teorema (umumlashgan ko‘paytirish qoidasi). Elementlari soni mos ravishda ta bo„lgan to„plamlardan bittadan element olib tuzilgan uzunlikdagi kombinatsiyalar soni songa teng. Isboti: teoremani isbotlash uchun matematika induksiya usulidan foydalanamiz. Induksiya bazasi: uchun teorema o„rinli, bo„lgan holda esa teoremaning isboti ko„paytirish qoidasidan kelib chiqadi. Induksion o‘tish: teorema uchun to„g„ri deb faraz qilib, uchun ham o„rinli ekanligini ko„rsatamiz. Dastlab uzunligi birga teng kombinatsiya tuzamiz. Bu kombinatsiya berilgan to„plamlarning ixtiyoriy biridan faqat bitta elementni tanlash orqali tuziladi. Masalan, bu kombinatsiya { } to„plamdan olinsa, bunday kombinatsiyalar soni ta. Uzunligi birga teng kombinatsiyaning ixtiyoriy birini olib, uning o„ng tomoniga to„plamdan farqli biror masalan { } to„plamning elementini joylashtirsak, uzunligi ikkiga teng kombinatsiyalar soni ta bo„ladi. Uzunligi birga teng kombinatsiyalar soni ta ekanligini hisobga olsak, uzunligi ikkiga teng jami ta kombinatsiyalar hosil bo„ladi. Kombinatsiyalar hosil qilish jarayonini yuqoridagidek davom