“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti
Download 1.78 Mb. Pdf ko'rish
|
Diskret matematika
- Bu sahifa navigatsiya:
- 2-§. Kombinatorika
- Ta’rif. Agar
- Teorema.
- Teorema.
- 3-§. Matematik mantiq elementlari.
- 3.1. Mulohaza. Mantiqiy bog’lovchilar. Ta’rif
|
Misol va masalalar. 1.
to’plamning quvvati qanchaga teng? va
to’plamlarning quvvati qanchaga teng? 2 . Agar A va B to’plamlar uchun А В= o’rinli bo’lsa, А\В va В\А to’plamlar qanday to’plamlar bo’ladi? 3. Agar C va D to’plamlar uchun C = o’rinli bo’lsa, va
4. А, В, С to’plamlar berilgan. Elementlari shu to’plamlardan faqat ikkitasiningelementlaridan iborat bo’lganto’plamlarni aniqlang. 5. Avvalgi masalani A, B va C to’plamlar o’zaro kesishmaydi degan shart asosida yeching. 11
6. Har qanday A va B to’plamlar uchun quyidagi tenglik o’rinli ekanligini isbotlang =(A
) . 7. Har qanday A, B, C to’plamlar uchun (А В) (В С) (А С) = (А В) (В С) (А С) tenglik o’rinli bo’lishini isbotlang. 8. Quyidagi ayniyatlarni isbotlang: 1. A (B\A)=A B.2. A (B\C)=(A B)\C.3. A \ (B C)=(A\B)
(A\C).4. A (B \ A)= .5. A \ (A B )=(A\B).6. A \ (B C)=(A\B) (A\C).
9. X to’plam A, B va C to’plamlar orqasi X C=A В shartlar orqali aniqlangan bo’lsa, A, B, C lar qanday shartlarni qanoatlantirganda X ni topish mumkin? X ni toping. 10. Quyidagi tasdiqlarni isbotlang: 1) А В bo’lsa, А В = А va А В = В bo’lishi kelib chiqadi; 2) А В = А bo’lsa, А В bo’lishi kelib chiqadi; 3) А В = В bo’lsa, А В bo’lishi kelib chiqadi. 11. Isbotlang: 1) А (В С) = (А В) (А С); (distributivlikning 1-qonuni) 2) А (В С) = (А В) (А С). (distributivlikning 2-qonuni) 12. Ichkarisida yotishlarni isbotlang: 1) (А С) (В D) (А В) (С D);2) (В \ С) \ (В \А) А \ С; 3) А \ С (А \В) (В \ С). 13. Isbotlang: А В = (А В) \ (А В). 14. Har qanday A, B, C to’plamlar uchun quyidagi tasdiqlar to’g’rimi: 1) Agar А В va В С bo’lsa, u holda А С; 2) Agar А В va В С bo’lsa, u holda А С? 15. A va B larga qanday shartlar qo’yilganda (А – В) В = А tenglik o’rinli bo’ladi? 16. U={a, b, c, d, e, f} – to’plam universal, A = {a, b, c}, B = {a, c, e, f} va C = {d, e, f} bo’lsa, quyidagilarni toping: А \ В, В \ С, С \ В, А \ С, В, В
, А С, С А. 17. Tenglikni isbotlang: a) (А \ В) \ С = (А \ С) \ (В \ С);b) (А \ В) (В \ С) (С \А) (А В С) = А В С;c) А \ В = А \ (А В) = (А В) \ В;d) А \ (А \ В) = А В; e) А \ (В С) = (А \ В) (А \ С);f) А \ (В С) = (А \ В) (А \ С); g) (А В) \ С = (А \ С) (В \ С). 18. А \ В = С o’rinli bo’lsa, А = В С kelib chiqadimi? 12
19. А = В С o’rinli bo’lsa, А – В = С kelib chiqadimi? 20. А – berilgan to’plam va А Х = А o’rinli bo’lsa, Х = bo’lishini isbotlang. 21. Tengliklarni isbotlang: a) А (В D) = (А В) D;b) А (В D) = (А В) (А D);d) А А = ; e) А
= А. 22. Quyidagi ayniyatlarni isbotlang: a) (А В) (С D) = (А С) (В С) (А D) (В D);b) (А В) А = (А В) А = А;d) А \ (В \ С) = (А \ В) (А С);e) А (В \ С) = (А В) \ (А С) = (А В) \ С;f) А В = А (В \ А);g) ( )
= А;h) А = U;j) А
= ;i) [
В] А = А В;k) А (В-А) = ;l) А – (В С) = (А – В) – С. 23. Quyidagilarni isbotlang: a) (А В) С = А (В С) А С;b) А = В А В = ;d) А В = А В А = В;e) (А В) \ В = А А В = ;f) (А – В) В = А
В А;
g) (А В) С = А (В С) С А;h) А В А С В С;i) А В
А С В С;j) А В (С\В) (С\А);k) А В
;l) А = В С
А В= и А В = U. 24. Ayniyatlarni isbotlang: a) А В = А В (А В);b) А \ В = А \ (А В);d) А = А;e) А \ А = ;f) A U = ;g) А В = (А В) \ (А В); 25. Tenglamalar sistemasini yeching a)
, ,
X A B X A bu yerda А, В, С – В А С to’plamning elementlari. b) ,
, \
A X B X A bu yerda А, В, С – В А , А С = to’plamning elementlari. d)
, , \ C A X B X A bu yerda А, В, С – В А С to’plamning elementlari. 26. , , \ operatsiyalarni quyidagilar orqali aniqlang: а) и ;b) и ;d) \ и . 27. E, F, G, H to’plamlarning istalgani uchun quyidagilar o’rinli ekanligini isbotlang: a) E (F G) (E F) (E G);b) E (F – G) (F E) – (G E);d) (E F) (G H) (E G) (F H);e) (E F)-(G H) [E (F-H)] [(E- G) (F H)];f) E (F G)
(E F) (E G);g) (F E) (G H)
(G E) (F H). 13
28. Quyidagi tenglik o’rinlimi (А В) (С D) = (А С) (В D)? 29. Quyidagi tenglik o’rinlimi (А В) (С D) = (А С) (В D)?
2-§. Kombinatorika Kombinatorika – matematikaning shunday bo’limiki, bu bo’limda chekli to’plam elementlaridan biror qoida asosida elementlarni tanlab olish va o’rinlashtirish o’rganiladi. Berilgan to’plam elementlaridan har bir qoida orqali kombinatorik almashtirishlar yo’li bilan ba’zi bir konstruksiyalar ko’riladi. Shuni aytish mumkinki, kombinatorikaning maqsadi kombinatorik konfiguratsiyalarni o’rganish xisoblanadi. Bu masalalarga quyidagilar kiradi: bu konfiguratsiyalarning mavjudligi, ularni qurish algoritmi, bu algoritmlarni optimallash, sanash masalalari, ya’ni berilgan sinf elementlari sonini aniqlash. Kombinatorik konfiguratsiyalarning oddiy misoli o’rinlashtirish, o’rin almashtirish va gruppalashlar yoki kombinatsiyalar hisoblanadi. Kombinatorikaninng paydo bo’lishi va rivojlanishi matematikaning boshqa bo’limlari bilan bog’liq: sonlar, algebra nazariyasi. Qadimgi Sharq matematikasiga yana binominal koefitsiyentlar va Nyuton Binomning n ta natural sonlar uchun moslik formulasi ma’lum bo’lgan. Mistik maqsadlarda uchinchi tartibli afsungarlik kvadratlarining xususiyatlari o’rganilgan. Leybnits va Bernullining ehtimollar nazariyasiga bag’ishlangan “Tahminlar san’ati” nomli kitobining paydo bo’lishi bilan kombinatorik sxemalar matematikaning alohida qismiga ajralib chiqdi. Kombinatorikaga qiziqishning paydo bo’lishi XX asrning 50-yillariga to’g’ri keladi. Bu qiziqish kibernetikaning rivojlanishi bilan bog’liq. n ta turli elementlardan tashkil topgan A to’plamni ko’rib chiqamiz deb xisoblaymiz.
tarkib topgan tartiblangan har qanday qism to’plami elementdan tadan o’rinlashtirish deyiladi va ularning soni simvol bilan beldilanadi. Teorema. Takrorsiz o’rinlashtirish soni quyidagiga teng:
Isboti: k elementlarni ma’lum tartibda joylashtirish uchun bittasini tanlab olamiz va uni “birinchi” deb xisoblaymiz. Buni n ta usulda bajarish 14
mumkin. Qolgan to’plam n-1 ta elementdan iborat. Undan yana “ikkinchi” elementni tanlab olamiz. Ikkinchi elementni tanlashning n-1 ta usuli bor. n- 2 ta element qoldi. Shunday fikrlash natijasida tushunarliki, k elementning n – (k – 1) usuli bor. Bo’lim boshida keltirilgan izohdan foydalangan holda quyidagiga ega bo’lamiz:
iborat to’plamga n ta elementdan o’rin almashtirish deyiladi va ularning soni bilan belgilanadi. Teorema. O’rin almashtirish soni ga teng. Isboti: Oldingi teoremaning isboti takrorlanadi, k=n deb xisoblasaetarli.
gruppalash deb, xech bo’lmaganda bitta elementi bilan farqlanuvchi, bunda barcha elementlar turli xil, k ta elemntdan tashkil topgan barcha to’plamlarga aytiladi. Ularning soni bilan belgilanadi.
. Isboti: n tadan k tagacha elementlarni o’rin almashtirishlarini ko’rib chiqamiz. Elementlar tartibini xisobga olmaydigan bo’lsak ta o’rin almashtirish mavjud. Shunga ko’ra
soddalashtirib izlagan narsaga ega bo’lamiz. Ta’rif. Agar elementli to’plam bo’lsa, uning ta elementidan tarkib topgan, bir biridan elementi bo’yicha yoki tartibi bo’yicha farqlanuvchi A to’plamning k-elementli qismto’plami ta elementdan ta takroriy o’rinlashtirishlar deyiladi. Ularning soni belgilanadi. Bunda A to’plamga elementlarning takroriy kirishiga yo’l qo’yiladi.
ga teng. Isboti: Fikrlar takrorsiz o’rinlashtirishlar sonini isbotlashga juda o’xshaydi. “Birinchi” o’rinda turgan qiymatni n ta usulda tanlash mumkin. “Ikkinchi” o’rinda turgan qiymatni ham n ta usulda tanlash mumkin (elementlar tanlangandan so’ng to’plamdan o’chirilmaydi, chunki ular takrorlanishi mumkin). Shu tariqa vaziyat k marotaba takrorlanadi.
takroriy gruppalash deb, hech bo’lmaganda bitta elementi bilan 15
farqlanuvchi, bunda elementlar takrorlanishi mumkin, k ta elemntdan tashkil topgan barcha to’plamlarga aytiladi. Ularning soni bilan belgilanadi.
)! 1 ( ! )! 1 ( 1 n k k n C S k k n k n . Masalalar. 1. 5 xil convert va 4 xil marka mavjud. Qancha usulda markali konvertni tanlash mumkin? 2. 5 ta tildan istalgan birortasini istalgan boshqa tilga o’girish uchun nechta lug’at chiqarish kerak? 3. 5 razryadli raqamli qulf bor, har bir razryad 0 dan 5 gacha raqamdan iborat. Bunday raqamlarning nechta kombinatsiyasi mavjud? 4. 1 dan 2n gacha raqamdan iborat to’plamni, barja juft sonlar juft o’rinlarda turishini ta’minlagan holda, qancha usulda tartiblashtirish mumkin? 5. 1 dan n gacha raqamdan iborat to’plamni, 1, 2, 3 sonlar ketma ket va o’sish tartibida turishini ta’minlagan holda, qancha usulda tartiblashtirish mumkin? 6. 6Talabalarning kitobxonlik qiziqishlarini tadqiq qilish natijasida ma’lum bo’ldiki: 60% talabalar L jurnalini o’qishadi, 50%i – B jurnalni, 50%i – C jurnalni, 30%i – L va C jurnallarni, 20%i – B va C jurnallarni, 40%i – L va C jurnallarni, 10%i – L, B va C jurnallarni. Aniqlang, qancha foiz talabalar: 1) jurnallardan birortasini o’qimaydi; 2) aniq ikkita jurnal o’qiydi; 3) ikkitadan kam bo’lmagan jurnalni o’qiydi. 7. Institutning ma’lum bir kafedrasida 13 kishi ishlaydi, ularning hech bo’lmaganda bitta horijiy til biladi. O’n kishi ingliz tilini biladi, yettitasi – nemis, oltitasi – fransuz, beshtasi – ingliz va nemis, to’rtasi – ingliz va fransuz, uchtasi – nemis va fransuz. Aniqlang: 1) nechta kishi barcha uch tilni biladi; 2) nechta kishi aniq ikki tilni biladi; 3) nechta kishi faqat ingliz tilini biladi. 8. Bir kunning dars jadvali 5 ta darsdan iborat. 11 ta fandan iborat shunday dars jadvali sonini aniqlang. Javob: 55440. 9. Komissiya rais, uning o’rinbosari va yana besh a’zodan iborat. Nechta usul orqali komissiya a’zolari o’zaro majburiyatlarni taqsimlashi mumkin? 10.
Qulf faqat ma’lum uch xonali nomer terilgandagina ochiladi. Harakat shundan iboratki, berilgan beshta raqamdan tavakkal uchta 16
raqam teriladi. Barcha mumkin bo’lgan urinishlarning eng oxirgisida nomerni topish imkoni bo’ldi. Ungacha nechta urinishlar bo’lgan? Javob: 124. 11. 15 kishidan iborat guruhdan faqat to’rtasi 800+400+200+100 estafeta ishtirokchisi sifatida tanlanadi. Sportsmenlarni estafeta bosqichlari boyicha nechta usulda joylashtirish mumkin? Javob: 32760. 12.
0, 1, 3, 5, 7 raqamlardan iborat 5 ga bo’linadigan nechta to’rt xonali sonlarni tuzish mumkin, agar har bir son bir xil raqamdan iborat bo’lmasa? 13.
10 ta turli rangdagi lampochkalarni aylana bo’ylab joylashtirish orqali nechta turli xil yonuvchi aylanalar hosil qilish mumkin (ranglarning bir xil ketma-ketligida aylanalar bir xil xisoblanadi)? 14.
Kitob javonida 30 ta tomli kitob joylashadi. Qancha usulda ularni o’zaro joylashtirish mumkin, bunda birinchi va ikkinchi tomlar yonma-yon joylashmasligi kerak? Javob: 30! – 2*29!. 15. To’rta o’q sakkizta nishonni zabt etishi kerak (har biri ikkitadan). Qancha usul orqali o’qlar o’zaro nishonlarni taqsimlashi mumkin?
Javob: 2520. 16.
12 kishidan iborat guruhdan har kuni 6 kun davomida ikkita navbatchi tanlanadi. Navbatchilarning turli xil ro’yxatini aniqlang, agar har bir navbatchi bir marta navbatchilik qilsa. Javob: 12!/(2!) 6 .
3 raqami mavjud bo’lgan 0, 1, 2, 3, 4, 5 raqamlardan iborat nechta to’rt xonali sonlarni tuzish mumkin (agar sonlarda raqamlar takrorlanmasa)? Javob: 204. 18. O’nta guruh o’nta ketma ket joylashgan auditoriyalarda mashg’ulot olib borishadi. №1 va №2 guruhlar qo’shni auditoriyalarda joylashadigan dars jadvalinig nechta variantlari mavjud? Javob: 2*9! 19. Turnirda 16 ta shaxmat ustasi ishtirok etadi. Birinchi turning turli xil turnir jadvali sonini aniqlang (turnir jadvali turli xil xisoblanadi, agar hech bo’lmaganda bir partiya ishtirokchilari bilan farq qilsa). Javob: 2027025. 17
20. Turli materiallardan iborat oltita quti qurilishning beshta qavatiga yetkaziladi. Materiallarni qavatlar bo’yicha nechta usulda taqsimlash mumkin? Nechta variantda 5-qavatga faqat bitta material yetkazilgan? Javob: 5 6 ; 6*4 5 . 21. Ikkita pochtalon 10 ta adres bo’yicha 10 ta xatni tashishi kerak. Nechta usulda ular ishlarni o’zaro taqsimlashi mumkin? Javob: 2 10 . 22. Metro poyezdi barcha yo’lovchilar tushadigan 16 ta bekatda to’xtaydi. Boshlang’ich bekatda poyezdga chiqqan 100 ta yo’lovchi bu bekatlar bo’yicha o’zaro nechta usulda taqsimlanishi mumkin? Javob: 16 100
. 23.
0, 1, 2, 3, 4, 5 raqamlardan iborat 3 ga bo’linadigan nechta uch xonali sonlarni tuzish mumkin, agar har bir sonda raqamlar takrorlanmasa? Javob: 40. 24. 80 kishidan iborat yig’ilishda rais, kotib va taftish komissiyasining uch a’zosi saylanmoqda. Nechi xil usulda buni amalga oshirish mumkin? Javob: 80!(3!*75!). 25.
Beshta o’quvchini uchta parallel sinflar bo’yicha taqsimlash kerak. Nechta usulda buni amalga oshirish mumkin? Javob: 3 5 . 26. Lift 10 ta qavatda to’xtaydi. Liftda mavjud bo’lgan 8 ta yo’lovchini bu qavatlar bo’yicha o’zaro nechi xil usulda taqsimlash mumkin?
Javob: 10 8 . 27. Sakkizta muallif 16 ta bo’limdan iborat kitob yozishlari kerak. Mualliflar o’rtasida materialni nechi xil usulda taqsimash mumkin, agar ikkita muallif uchtadan bo’lim, to’rtasi – ikkitadan, ikkitasi – bittadan bo’lim yozishsa? Javob: 16!/(2 6 *3
). 28.
Shaxmat turnirida uchinchi razryaddagi 8 ta, ikkinchi razryaddagi 6 ta va birinchi razryaddagi 2 ta shaxmat ustasi qatnashmoqda. Birinchi turning shunday tarkibi aniqlansinki, bunda bir kategoriyadagi shaxmat ustalari o’zaro uchrashishsin (figuralar rangi xisobga olinmaydi). Javob: 420. 29. 1, 2, 3, 4, 5, 6, 7, 8, 9 raqamlardan barcha mumkin bo’lgan besh xonali sonlar tuzilgan: sonlardagi raqamlar takrorlanmaydi. Bir 18
vaqtning o’zida tarkibida 2, 4 va 5 raqamlari mavjud bo’lgan sonlar miqdorini aniqlang. Javob: 1800. 30. 0, 1, 2, 3, 4, 5 raqamlardan nechta to’rt xonali sonlar tuzish mumkin, agar a) raqamlar takrorlanmasa; b) raqamlar takrorlanishi mumkin; c) faqat toq raqamlardan foydalanilsa va ular takrorlanishi mumkin; d) faqat toq sonlar hosil bo’lsa va raqamlar takrorlanishi mumkin.
Javob: a) 5*5*4*3=300; b) 5*6=1080; c) 3 4 ; d) 5*6*6*3=540. 31. Sinfda 10 ta fan o’qitiladi. Dushanba kun uchun nechi xil usulda dars jadvalini tuzish mumkin, agar dushanba kuni 6 ta turli xil dars bo’lsa? Javob: A 6 10 . 32.
Bitta to’g’ri chiziqda m ta nuqta olingan, unga parallel to’g’ri chiziqda n ta nuqta olingan. Ushbu nuqtalarda uchi bo’lgan nechta uchburchaklarni hosil qilish mumkin? Javob: mC 2 n
2 m . 33. O’ngdan chapga va chapdan o’nga bir xil o’qiladigan nechta besh xonali sonlar mavjud, masalan 67876? Javob: 9*10*10=900. 34. A = {a
ij } to’g’ri burchakli matritsada m ta qator va n ta ustun bor. Har bir a ij {+1, -1}, a ij ning istalgan qator yoki ustun bo’yicha ko’paytmasi 1 ga teng. Shunday matritsalardan nechta? Javob: 2
(m-1)(n-1) . 35. 10 ta bir xil o’yin kubiklari tashlandi. Ular nechi xil usulda tushishi mumkin, agar: a. hech bir kubikda 6 ochko tushmaydi; b. hech bo’lmaganda bitta kubikda 6 ochko tushadi; c. uchta kubikda birdaniga 6 ochko tushadi; d. uchta kubikda birdaniga 6 ochko tushadi, boshqa ikkitasida 5 ochko tushadi. Javob: 5
10 ; 6
10 -
5 10 ; 24*5 8 , 630*4
6 .
Matematik mantiq – rasmiy mantiqning zamonaviy ko’rinishi bo’lib, hulosa chiqarishni ularning rasmiy qurilishiga ko’ra o’rganadigan fandir. XIX asr boshiga qadar rasmiy mantiq sillogik hulosa chiqarish chegarasidan chiqmagan.Lekin Dj.Bull ishlaridan so’ng uni matematik mantiqqa aylanishi haqida gapirish mumkin. Matematik mantiqning asosiy xususiyatlaridan suni ta’kidlai kerakki matematikada qo’llaniladigan 19
hulosa chiqarishga qaratilgan matewmatik apparatning mavjudligidir. Matematik mantiq – bu ananaviy muammjlardan tashqari matematikaning asoslari va algoritmlar nazariyasi masalalari bilan shug’ullanadidan fan va bir qator tatbiqlarga egadir.
mulohaza deyiladi. Mulohazalar odatda lotin alfavitining a, b, c, х 1 , х 2 , …harflari bilan belgilanadi.Mantiqda mulohazaning ma’nosi bilan emas balki uning rost yoki yolg’onligi bilan qiziqiladi .Rostlik qiymatlari-rost va yolgon- R va Y bilan belgilanadi. to’plam rostlik qiymatlari to’plami deyiladi. Ta’rif: Agar mulohaza yagona fikrni bildirsa va boshqa imkoniyatlar bo’lmasa u oddiy mulohaza deyiladi.Mantiqiy bog’lovchilar yordamida oddiy mulohazalardan tuzilgan mulohaza murakkab mulohaza deyiladi. Odatda gaplashishda “va”, “yoki”, “emas”, “u holda” kabi bog’lovchi so’zlar ishlatiladi.Mantiqda esa bog’lovchilar aniq ta’riflanishi kerak. Mantiqiy bog’lovchilarni tashkil qiluvchi mulohazalarning rostlik qiymatlariga ko’ra rostlik qiymatini qabul qiladigan murakkab mulohazanioddiy mulohazalar ustida amal deb qaraymiz. Bundan buyon “rost “ qiymatiga birni va yolg’on qiymatiga nolni mos keltiramiz.Har bir mantiqiy amalga uning rostlik jadvali mos keltiriladi. Bundan buyon rostlik jadvalidan murakkab mulohazani rostlik qiymatlarini aniqlasda uni tashkil qiluvchi oddiy mulohazalarningrostlik qiymatlarini bog’lovchi vosita sifatida foydalanamiz.
Download 1.78 Mb. Do'stlaringiz bilan baham: 
|