1. Kombinatorika elementlari

Algoritmning ommaviyligi. Boshlang‘ich miqdorlar sistemasini ayrim potensial cheksiz to‘plamdan tanlash mumkin. Algoritmning natijaviyligi. Miqdorlarni topish jarayoni chekli bo‘lishi va natijani (masalaning yechimini) berishi kerak.
Matematik amallar asosiy rolni o‘ynaydigan algoritmlar sonli algoritmlar deb yuritiladi. Bundan tashqari, mantiqiy algoritmlar ham mavjud. Mantiqiy algoritmlardan biri quyidagi misoldagi o‘yinda ifodalangan.
49.Chiziqli funksiyalar, monoton funksiyalar.
Xi1 +Xi2 + ... + xik + a ко‘rinishdagi funksiya chiziqli funksiya deb ataladi, bu yerda aeE2 = {0, 1}. Chiziqli funksiyaning ifodasidan ko‘rinib turibdiki, n ta argumentli chiziqli funksiyalar soni 2"+1 ga teng va bir argumentli funksiyalar doimo chiziqli funksiya bo’ladi. Agar alfa y, x<->y, x + y funksiyalar esa nomonoton funksiyalardir.

50.Tyuring mashinasida algoritmni realizatsiya qilish.

0 ‘nlik sanoq sistemasida n sonning yozuvi berilgan bo‘lsin va n +1 sonning o ‘nlik sistemasidagi yozuvini ko'rsatish, ya’ni f(n) = n +1 funksiyani hisoblash talab etilsin. Ravshanki, mashinaning tashqi alfaviti 0,1,2,3,4,5,6,7,8,9 raqamlardan va bo‘sh katakcha a0 dan iborat bo‘lishi kerak. Lentaga o ‘nlik sistemada n sonini yozamiz. Bu yerda qatorasiga bo‘sh joysiz har bir katakchaga bitta raqam yoziladi. Qo’yilgan masalani yechish uchun ishning birinchi taktida mashina n sonning oxirgi raqamini o‘chirib, uni bir birlik katta songa almashtirib va agar oxirgi raqam 9 sonidan kichik bo‘lsa, u holda to‘xtash holatiga o‘tishi kerak. Agar n sonning oxirgi raqami 9 bo‘lsa, u holda mashina 9 raqamni o‘chirib, bo‘sh qolgan katakchaga 0 raqamni yozib, o‘sha holatda qolgan holda chapga yuqoriroq razryadli qo‘shnisiga surilishi kerak. Bu yerda ishning ikkinchi taktida mashina yuqoriroq razryadli raqamga 1 sonini qo‘shishi kerak. Tabiiyki, chapga surilish paytida yuqoriroq razryadli raqam bo'lmasa, u holda mashinaning boshqaruvchi kallagi bo‘sh katakchaga chiqishi mumkin. Bu holatda bo‘sh katakchaga mashina 1 raqamini yozadi. Aytilganlardan shu narsa kelib chiqadiki, f (n) = n + 1 funksiyani hisoblash algoritmini realizatsiya qilish paytida mashina bor yo‘g‘i ikkita q1 va q0 holatlarda bo’ladi.
51.Mulohazalar. Mulohazalar ustida amallar.
Ma ’nosiga ko ‘ra faqat chin yoki yolg ‘on qiymat qabul qila oladigan darak gap mulohaza deb ataladi. Mulohaza muayyan holatda chin yoki yolg‘on bo‘lishi mumkin. Shunday mulohazalar borki, ular mumkin bo‘lgan barcha hollarda (vaziyatlarda) ch (yoki yo) qiymat qabul qiladi. Bunday mulohazalar absolyut chin (yolg‘on) mulohazalar deb ataladi. ol.Misol: “Toshkent - 0 ‘zbekistonning poytaxti.”, “Oy yer atrofida aylanadi.” va “Agar fuqaro oliy ta’lim muassasalaridan birini muvaffaqiyatli tamomlasa, u holda unga oliy malumotliligini tasdiqlovchi diplom beriladi” degan gaplarning har biri chin, ammo “ Yer oydan kichik.” , “ 3 > 5 .” va “Ot, qo‘y, echki, it va mushuk uy hayvonlari emas.” degan gaplarning har biri esa yolg‘ondir. Mulohazalar algebrasida, odatda, muayyan o'zgarmas mulohazalar (ch, yo) bilangina emas, balki istalgan mulohazalar bilan ham shug‘ullaniladi. Bu esa o‘zgaruvchi mulohaza tushunchasiga olib keladi. Agar berilgan mulohazani x deb belgilasak, u holda x ch yoki yo qiymat qabul qiladigan o‘zgaruvchi mulohazani ifodalaydi.
52.Mulohazalar algebrasi formulalarining normal shakllari.
Berilgan elementar mulohazalar (o ‘zgaruvchilar) yoki ularning inkorlari kon’yunksiyalaridan tashkil topgan formula shu о ‘zgaruvchilar elementar kon’yunksiyasi, bu о‘zgaruvchilar yoki ularning inkorlari diz ’yunksiyalaridan tashkil topgan formula esa shu о ‘zgaruvchilar elementar diz’yunksiyasi deb ataladi. Tabiiyki, elementar kon’yunksiya (elementar diz’yunksiya) tarkibida faqat bitta o‘zgaruvchi ishtirok etishi ham mumkin. Shu sababli, bitta (masalan, x ) o‘zgaruvchining o‘zi yoki uning inkoridan iborat x yoki x-| ко‘rinishdagi ifodalar elementar kon’yunksiya ham, elementar diz’yunksiya ham bo‘la oladi.
53.Formulalarning normal shakllari.DNSH va KNSH.
Berilgan formulaning kon’yunktiv normal shakli deb, unga teng kuchli va elementar diz’yunksiyalarning kon’yunksiyalaridan tashkil topgan formulaga, diz’yunktiv normal shakli deb esa unga teng kuchli va elementar kon’yunksiyalarning diz’yunksiyalaridan tashkil topgan formulaga aytiladi. “Kon’yunktiv normal shakl” iborasini, qisqacha, KNSh, “diz’yunktiv normal shakl” iborasini esa, DNSh deb yozamiz. Mantiq algebrasining formulasi tavtologiya bo‘lishi uchun uning KNShidagi barcha elementar diz’yunktiv hadlarida kamida bittadan elementar mulohaza о‘zining inkori bilan birga qatnashishi zarur va yetarli. Mantiq algebrasining ixtiyoriy formulasini DNShga keltirish mumkin. Mantiq algebrasining formulasi aynan yolg ‘on bo‘lishi uchun uning DNShdagi barcha elementar kon’yunktiv hadlarida kamida bittadan elementar mulohaza о ‘zining inkori bilan birga qatnashishi zarur va yetarli.
54.Formulalarning MKNSH va MDNSH.
Agar formulaning KNShi (DNShi) ifodasida bir xil elementar diz ’yunksiyalar (коn ’yunksiyalar) bo ‘Imasa va barcha elementar dizyunksiyalar (kon’yunksiyalar) to ‘g ‘ri hamda ifodada qatnashuvchi barcha elementar mulohazalarga nisbatan to‘liq bo ‘Isa, u holda bu ifoda mukammal kon ’yunktiv normal shakl (mukammal diz’yunktiv normal shakl) deb ataladi. Elementar mulohazalarning tavtologiyadan farqli ixtiyoriy formulasini MKNShga keltirish mumkin. Elementar mulohazalarning aynan yolg ‘on bo ‘lmagan ixtiyoriy formulasini MDNShga keltirish mumkin. Agar formulaning MKNShi (MDNShi) ifodasida qatnashuvchi barcha elementar mulohazalardan tuzish mumkin bo'lgan barcha elementar diz’yunksiyalar (kon ’yunksiyalar) shu ifodada ishtirok etsa, u holda bunday MKNSh (MDNSh) to’liq MKNSh ( MDNSh) deb ataladi. Ushbu (x v y ) ( x v y ) ( x v y ) formula x va у elementar mulohazalarga nisbatan MKNShda bo‘lsada, u to‘liq MKNShda emas. X va у elementar mulohazalarga nisbatan to‘liq MKNShi ifodasi (x v y ) ( x v y ) ( x v y ) ( x v y ) ko‘rinishga ega. MDNShdagi xyz v xyz v xyz V xyz formula x , у va z elementar mulohazalarga nisbatan to‘liq MDNShda emas, lekin xvz V xyz V x y z V У xy z Vx y z Vx y z У xyz Vxyz formula bu elementar mulohazalarga nisbatan to‘liq MDNShdagi formuladir.
55.Munosabat tushunchasi.
munosabat tushunchasi predmetlar (narsalar) va tushunchalar orasidagi aloqani ifodalaydi. Munosabat tushunchasiga aniqlik kiritish uchun tartiblangan juftlik tushunchasidan foydalanamiz. Ma’lum tartibda joylashgan ikki predmetdan tuzilgan kortej tartiblangan juftlik deb ataladi. Tartiblangan juftliklardan birgalikda tartiblangan juftliklar to‘plamini tashkil etishadi.Misol: A={1,2,…,10} to’plamda 4ga katta munosabatni o’rnating.Yechish(5;1),(6;2),(7;3),(8;4),(9;5),(10;6) 6ta.Binar munosabatlarda juftliklardagi 1-elementar 1-koordinata, 2-elementlari esa 2-koordinatalar hisoblanadi. 1-koordinatalardan tuzilgan to’plamlarga shu munosabatning aniqlanish sohasi deyiladi.2-koordinatadan tuzilgan to’plamga esa shu munosabatning qiymatlar to’plami deyiladi.Bundan tashqari uchlik ternar, n-ar munosabatlar ham o’rnatilishi mumkin.

56.Binar munosabatlar.

Matematik mantiqda n -ar munosabat tartiblangan n -liklar to‘plami sifatida aniqlanadi. Ba’zan n -ar munosabat iborasi o‘rniga n o‘rinIi munosabat iborasi qo‘llaniladi. Agar munosabat bir o'rinli bo'lsa, u holda u unar munosabat, ikki o'rinli bo'lganda esa binar munosabat deb ataladi. Unar munosabat xossa (xususiyat) deb ham yuritiladi. Adabiyotda, ko'pincha, 3-ar munosabat ternar munosabat deb nomlanadi. Ternar munosabatga misol:A={7;15} bu to’plamda qo’shish bu to’plamga ternar munosabatini o’rnating desa (14;7;7),(15;7;8),(15;8;7). Binar munosabatlarda juftliklardagi 1-elementar 1-koordinata, 2-elementlari esa 2-koordinatalar hisoblanadi. 1-koordinatalardan tuzilgan to’plamlarga shu munosabatning aniqlanish sohasi deyiladi.2-koordinatadan tuzilgan to’plamga esa shu munosabatning qiymatlar to’plami deyiladi.Bundan tashqari uchlik ternar, n-ar munosabatlar ham o’rnatilishi mumkin.
57.To’plam tushunchasi.
Matematikada, shu jumladan, diskret matematika, kombinatorika va graflar nazariyasida ham, turli to‘p!amlar bilan ish ko‘rishga to‘g‘ri keladi. Masalan, kutubxonadagi barcha kitoblar to‘plami, to‘g‘ri burchakli uchburchaklar to‘plami, suvda hayot kechiruvchi tirik organizmlar to‘plami, natural sonlar to‘plami, koinotdagi yulduzlar to'plami, to‘g‘ri chiziqda yotuvchi nuqtalar to‘plami va hokazo. To'plamni tashkil etuvchilar shu to‘plamning elementlari deb ataladi. To'plamlar nazariyasida to'plamning elementlari bir-biridan farqli deb hisoblanadi, ya’ni muayyan bir to‘plamning elementlari takrorlanmaydi. To'plamni tashkil etuvchi elementlar soni chekli yoki cheksiz bo’lishi mumkin. Birinchi holda chekli to‘plamga, ikkinchi holda esa, cheksiz to‘plamga ega bo'lamiz. To'plamlarni belgilashda, odatda, lotin yoki grek alifbosining bosh harflari, uning elementlari uchun esa alifboning kichik harflari qo’llaniladi. To'plamni tashkil etuvchi elementlar figurali qavslar orasiga olinib ifodalanishi mumkin. Masalan, A to'plamning a ,b ,c,d ,...,z elementlardan tuzilganligini A={a,b,c,d,…,z} ko’rinishda yozish mumkin.
58.To’plamlar ustida amallar.
To'plamlar ustida turli amallar bajarish mumkin. Har qanday ikkita to'plamning barcha elementlaridan, ularni takrorlamasdan, tuzilgan to'plamga shu to‘plamlarning birlashmasi (yoki y ig ‘indisi) deb ataladi. Har qanday ikkita to ‘plamning barcha umumiy elementlaridan tuzilgan to‘plamga to‘plamlarning kesishmasi (yoki ko’paytmasi) deyiladi. Kesishmasi bo‘sh bo’lgan to'plamlar o ‘zaro kesishmaydigan, kesishmasi bo‘sh bo’Imagan to‘plamlar esa о ‘zaro kesishadigan to‘plamlar deb ataladi. A to'plamning В to'plamda bo’lmagan barcha elementlaridan tuziladigan to‘plamni hosil qilish A to‘plamdan В to‘plamni ayirish deb, tuzilgan to'plam esa, shu A va В to‘plamlarning ayirmasi deb ataladi. В to'plamning A to'plamga kirmagan barcha elementlaridan tuzilgan B \A to ‘plam A to ‘plamning В to ‘plamgacha to‘Idiruvchi to‘plami deb ataladi.
59.Formulalarning teng kuchliligi.
Agar berilgan ikkita formula tarkibida ishtirok etuvchi elementar mulohazalarning har bir qiymatlar satri uchun bu formulalaming qiymatlari bir xil bo ‘Isa, u holda ular teng kuchli formulalar deb ataladi. Agar berilgan ikkita formula tarkibida ishtirok etuvchi elementar mulohazalarning qiymatlar satrlaridan hech bo‘Imaganda bittasi uchun bu formulalarning qiymatlari har xil bo ‘Isa, u holda ular teng kuchlimas formulalar deb ataladi. Teng kuchli va teng kuchlimas iboralari na faqat formulalarga nisbatan, balki ixtiyoriy mantiqiy mulohazalarga nisbatan ham qo‘llanilishi mumkin. Ba’zan, teng kuchli va teng kuchlimas iboralari o’rnida, mos ravishda, ekvivalent va ekvivalentmas iboralari ishlatiladi. Ekvivalentlik tushunchasi ekvivalensiya tushunchasiga ohangdosh bo‘lgani uchun, ularni bir-biridan farq qilish maqsadida ko‘proq teng kuchlilik iborasidan foydalanamiz. Berilgan formulalaming teng kuchli yoki teng kuchlimas bo‘lishini aniqlashda, odatda, ular uchun tuzilgan chinlik jadvallaridan foydalaniladi.
60.Formulalarning asosiy xossalari.Formulalarning chinlik to’plami.
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. Tarkibidagi o‘zgaruvchilarning soni qanday bo‘lishidan qat’i nazar, aynan yolg'on formulaning chinlik to‘plami bo‘sh to‘plamdan iboratdir. Dastlab mulohazalar algebrasining formula tushunchasiga murojaat qilib, intuitiv ravishda, uni berilgan elementar mulohazalardan inkor, diz’yunksiya, kon’yunksiya, implikatsiya, ekvivalensiya mantiqiy amallarining chekli kombinatsiyasi va, zarur bo‘lganda, mulohazalar ustida mantiqiy amallarning bajarilish tartibini ko‘rsatuvchi qavslar vositasida hosil qilingan murakkab mulohaza deb tushunamiz. Bu yerda qavslami ishlatish qoidalari sonlar bilan ish ko‘ruvchi (oddiy) algebradagidek saqlanadi.
61.L nazariya uchun Gyodelning to’liqlik haqidagi teoremasi.
L nazariyaning har qanday teoremasi tavtalogiya bo’ladi.Doim chin bo’ladi. F formula va uning tarkibiga kiruvchi x1,x2,…,xn propozitsional harflar, ularning chinlik qiymatlarini taqsimoti berilgan bo’lsa, xi bilan x1,x2,…,xn rost qiymatni qabul qilishini, xi bilan yolg’on qiymatni qabul qilishi belgilanadi. Xuddi shunday F bilan xuddi shu formula yolg’on qiymatni qabul qilishini, F bilan esa rost qiymat qabul qilishini belgilanadi va x1,x2,…,xn |- F1 (x1)’,(x2)’,…,(xn)’ |- F Gyodelning to’liqlik nazariyasi: Agar F formula L nazariyada aynan chin bo’lsa, u holda bu formula L nazariyasining teoremasi bo’lar ekan.
62.Mulohazalar algebrasi funksiyalari(Bul funksiyasi).
Oddiy algebradagi funksiya tushunchasiga o‘xshash, mulohazalar algebrasida ham funksiya tushunchasi kiritilishi mumkin. Argumentlari va o ’zi E2 to’p lamdan qiymatlar qabul qiluvchi funksiya mulohazalar algebrasining funksiyasi deb ataladi. Kon’yunksiya, diz'yunksiya, inkor amallari hamda 0 va 1 elementlari aniqlangan M to’plamda shu mantiqiy amallar bajarilsa, bunday M to ’plam Bul algebrasi deb ataladi. f va g funksiyalar mulohazalar algebrasining funksiyalari, x1,x2,...,xn о ’zgaruvchilar esa ularning hech bo’lmaganda bittasining argumentlari bo’lsin. Agar x1,x2,...,xn argumentlarning barcha qiymatlar satrlari uchun f va g funksiyalarning mos qiymatlari bir xil bo ’Isa, u holda f va g funksiyalar teng kuchli funksiyalar deb ataladi. Agar berilgan funksiyalar teng kuchli bo‘lmasa, u holda ular teng kuchlimas funksiyalar deb yuritiladi.
63.Teng kuchli formulalar. Asosiy teng kuchliliklar.
Mulohazalar algebrasida ixtiyoriy mantiqiy x, у va z o‘zgaruvchilar uchun quyidagi teng kuchliliklar o‘rinlidir: xvy = yvx; (xvy)vz = xv(yvz); х^у = у^х; (x^y)^Z=X^( y^z ); X^(уvz) = (x^у)v(x^z). A va В formulalar teng kuchli bo‘lishi uchun A va В formulalar teng kuchli bo‘lishi zarur va yetarli. Isboti. Berilgan A va В formulalar uchun A = B bo‘lsin. U holda A va В formulalar chinlik jadvalining ixtiyoriy satrida bu formulalarning qiymatlari bir xil bo‘ladi. Shuning uchun A va В formulalar chinlik jadvalining ixtiyoriy satrida ulaming qiymatlari ham bir xildir. Demak, A = B . Xuddi shunga o‘xshash, A = B teng kuchlilikdan A = B teng kuchlilik kelib chiqishini ko‘rsatish mumkin A va В formulalar teng kuchli bo ‘lishi uchun A<-> В formula tavtologiya bo‘lishi zarur va yetarli. Isboti.Berilgan A va В formulalar uchun A = B bo'lsin. U holda ekvivalensiya ta’rifiga asosan, A<-> В formula chinlik jadvalining barcha satrlaridagi qiymatlari ch bo‘ladi. Demak, A <-> В formula tavtologiyani ifodalaydi. Ixtiyoriy formulaning istalgan qismi о‘rniga shu qismi bilan teng kuchli boshqa formulani qo'yishdan hosil bo'lgan yangi formula dastlabki formula bilan teng kuchlidir.
64.Maxsus binar munosabatlar. Ekvivalentlik munosabati. Tartib munosabatlar turlari.
Matematik mantiqda n -ar munosabat tartiblangan n -liklar to‘plami sifatida aniqlanadi. Ba’zan n -ar munosabat iborasi o‘rniga n o‘rinIi munosabat iborasi qo‘llaniladi. Agar munosabat bir o'rinli bo'lsa, u holda u unar munosabat, ikki o'rinli bo'lganda esa binar munosabat deb ataladi. Unar munosabat xossa (xususiyat) deb ham yuritiladi. Adabiyotda, ko'pincha, 3-ar munosabat ternar munosabat deb nomlanadi. Ternar munosabatga misol:A={7;15} bu to’plamda qo’shish bu to’plamga ternar munosabatini o’rnating desa (14;7;7),(15;7;8),(15;8;7). Binar munosabatlarda juftliklardagi 1-elementar 1-koordinata, 2-elementlari esa 2-koordinatalar hisoblanadi. 1-koordinatalardan tuzilgan to’plamlarga shu munosabatning aniqlanish sohasi deyiladi.2-koordinatadan tuzilgan to’plamga esa shu munosabatning qiymatlar to’plami deyiladi.Bundan tashqari uchlik ternar, n-ar munosabatlar ham o’rnatilishi mumkin. Agar biror to‘plamdagi munosabat refleksiv, simmetrik va tranzitivlik xossalariga ega bo'lsa, u holda bunday munosabat shu to‘plamdagi ekvivalentlik munosabati deb ataladi. Berilgan X to'plamdagi x va у elementlar uchun у p x munosabat о ‘rniga x p у munosabat о ‘rinli bo‘lishini kо‘rsatuvchi munosabat tartiblash munosabati deb ataladi. Tartiblash munosabati yordamida elementlarni qanday tartibda qo‘yish masalasini hal etish mumkin. Haqiqiy sonlar to‘plami uchun <,<,>,> munosabatlar tartiblash munosabatlariga misol bo‘la oladi.