4-39. Predikatlar haqida tushuncha

1.Kombinatorika elementlari
Bir qator amaliy masalalarni yechish uchun berilgan to’plamdan uning qandaydir xossaga ega bo’lgan elementlarini tanlab olish va ularni ma’lum bir tartibda joylashtirishga to’g’ri keladi. Ta’rif. Biror chekli to’plam elementlari ichida ma’lum bir xossaga ega bo’lgan elementlaridan iborat qism to’plamlarni tanlab olish yoki to’plam elementlarini ma’lum bir tartibda joylashtirish bilan bog’liq masalalar kombinatorik masalalar deyiladi. Kombinatorik masalalar bilan shug’ullanadigan matematik fan kombinatorika deyiladi. To‘plamlar nazariyasi iboralari bilan aytganda, kombinatorikada kortejlar va to‘plamlar, ularning birlashmalari va kesishmalari hamda kortejlar va qism to‘plamlarni turli usullar bilan tartiblash masalalari qaraladi
2.Algoritm — maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. Oʻrta asrlarda sanoqning oʻnli tizimi boʻyicha toʻrt arifmetik amal bajariladigan qoidani A. deb atashgan. "Bu qoidalarni matematikaga IX asrda al-Xorazmiy kiritgan.
3. Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilanganXIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi.
“Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi.
4-39.Predikatlar haqida tushuncha.
Predikatlar mantiqi an’anaviy formal mantiq singari elementar mulohazani subyekt va predikat qismlarga bo‘ladi.
Subyekt – bu mulohazada biror narsa haqida nimadir tasdiqlaydi; predikat – bu subyektni tasdiqlash. 1-teorema . Predikatlar mantiqining har qanday formulasini normal shaklga keltirish mumkin. Masalan, «5 – tub son» mulohazada «5» – subyekt, «tub son» – predikat. Bu mulohazada «5» «tub son bo‘lish» xususiyatiga ega ekanligi tasdiqlanadi. Agar keltirilgan mulohazada ma’lum 5 sonini natural sonlar to‘plamidagi x o‘zgaruvchi bilan almashtirsak, u holda « x – tub son» ko‘rinishidagi mulohaza formasiga (shakliga) ega bo‘lamiz. Predikatlar ham mulohazalar singari faqatgina chin yoki yolg'on (1 yoki 0) qiymat qabul gilganliklari tufayli ular ustida mulohazalar mantiqidagi hamma mantiqiy amallami bajarish mumkin.
5.Daraxt tushunchasi (ma'lumotlar tarkibi) - Tree (data structure)
Buni chalkashtirib yubormaslik kerak uchlik, daraxtlar ma'lumotlar tuzilishining o'ziga xos turi. Buni chalkashtirib yubormaslik kerak daraxt (grafik nazariyasi), ma'lum bir matematik ob'ekt turi. Umumiy va shunga o'xshash ikkilik bo'lmagan, saralanmagan, ba'zi yorliqlar takrorlangan, daraxtning o'zboshimchalik diagrammasi.

6.Rekursiv toʻplam
Qaror qabul qilinadigan to'plamlarga qaraganda umumiyroq to'plamlar klassi rekursiv sanab o'tiladigan to'plamlardan iborat bo'lib, ular yarim hal qilinadigan to'plamlar deb ham ataladi . Bu to'plamlar faqat to'plamda raqam borligini to'g'ri aniqlaydigan algoritmni talab qiladi ; algoritm to'plamga kiritilmagan raqamlar uchun javob bermasligi mumkin (lekin xato qilmaslik). Agar x ∈ S bo'lsa f ( x ) = 1 va x ∉ S bo'lsa f ( x ) = 0 bo'ladigan umumiy hisoblanuvchi f funksiya mavjud bo'lsa , natural sonlarning S kichik to'plami rekursiv deyiladi . Boshqacha qilib aytganda, S ni rekursiv ravishda o'rnating , agar va faqat u holda indikator funksiyasi 1 S hisoblansa . Ma'lumki, muayyan funktsiyaning o'zini to'g'ridan-to'g'ri yoki bilvosita chaqirishi rekursiya, mos keladigan funksiya esa rekursiv funktsiyadir. Rekursiya jarayoni bir funksiya uchun bir nechta sonlarni takrorlash bilan bog'liq. …Rekursiya jarayonining bajarilishini yakunlash uchun bizda har qanday shartdan keyin asosiy holat bo'lishi kerak Rekursiya murakkab matematik hisoblash masalalari kabi muammolarni hal qilishda samarali yondashuvdir. Bu vazifani kichik vazifalarga bo'lish orqali amalga oshiriladi. Rekursiya murakkab matematik hisoblash masalalari kabi muammolarni hal qilishda samarali yondashuvdir. Bu vazifani kichik vazifalarga bo'lish orqali amalga oshiriladi.
10.O’rinlashtirishlar va kombinatsiyalar
Kombinatsiyalarni harflar yoki raqamlar ketma−ketligi bilan belgilaymiz, bunda bunday belgilash bir qiymatli boʻlsin. Kombinatsiyalarni alfavit tartibida (agar belgilashda harflar ishlatilsa) yoki sonlarni oʻsish tartibida yozib chiqamiz. Takrorlanadigan o’rinlashtirishlar. Masala. m elementli X to’plam elementlaridan tuzilgan k uzunlikdagi kortejlar sonini toping. Yechish. k o’rinli kortej dekart ko’paytmaning elementi bo’lib, tartiblangan k-likni (ka-lik 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=mk ga teng.
11.Eyler va Gamilton graflari
Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lum. L. Eyler 1736 yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda bog‘lamli grafda barcha qirralardan faqat bir marta o‘tadigan sikl mavjud bo‘ladi? Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri deb ataladi. Yopiq Eyler zanjiriga (ja’ni Eyler sikliga) ega graf Eyler grafi deb ataladi. Agar grafda yopiq bo‘lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler grafi deb ataladi. . Biroq, grafik Gamiltonian bo'lishi uchun ikki ulanishlik etarli emas Grafikning Gamiltoniy yoki yo'qligini aniqlash uchun oddiy mezon yo'q (masalan, grafik Eylerian yoki yo'qligini aniqlash uchun). Shunga qaramay, grafikning qirralari qanchalik ko'p bo'lsa, grafaning cho'qqilari darajasi qanchalik katta bo'lsa, grafikning Gamiltonian ekanligini kutish ehtimoli shunchalik yuqori bo'lishi aniq
12.Izomofizm, Tiplar va bog’lanishlar Izomorfizm (izo... va yun. morphe — shakl) — kimyoviy tarkibi va kristall strukturasi bir-biriga yaqin jinslarning oʻzgaruvchan tarkibli birikmalar (aralash kristallar) hosil qilish qobiliyati. I. hodisasini birinchi marta 1819-yil nemis kimyogari E. Mitcherlix aniqlagan vatermin sifatida taklif qilgan. I. tabiiy mineral va kristallarda keng tarqalgan boʻlib, yer poʻstining turli termodinamik zonalarida uchraydi. Elementlarning oʻzaro izomorf aralashma hosil qilishi ular atom radi-usining kattaligi, kristallokimyoviy xususiyatlari (koordinatsiya soni, va-lentligi, strukturasi, kristallanish sistemasi) va tabiiy termodinamik sharoitlar (temperatura, bosim, paydo boʻlgan chuqurligi va joyi)ga bogʻliq.
13.Hisoblanuvchanlik O'z navbatida Chyorch tezisi bo'yicha hisoblanuvchanlik tushunchasi bilan rekursivlik tushunchasi (qismiy effektiv hisoblanuvchanlik tushunchasi qismiy rekursivlik tushunchasiga) ekvivalentdir. A.A.Markov algoritmlar atamasida normallashtirish (normalizatsiya) prinsipini yaratdi: A a(favitdagi har qanda)' algorztm A ga nisbatan A ustidagi biror normal algoritmga batamom ekvivalentdir.
14.Algoritmik yechilmas muammo. Vaqt muammosi
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi
15=6.
16.Primitiv rekursiv funksiyalar
Primitiv-rekursiv funksiya 1) x1, x2 ,..., xn funktsiyaning y qiymati uning o'zgaruvchilari ixtiyoriy qiymatlarida aniqlashga imkon beruvchi algoritm mavjud bo'lsa ( ) y = j x1, x2 ,..., xn funktsiyasi hisoblangan funksiya deyiladi. Hisoblash algoritmi tushunchasi aniq belgilanmaganligi sababli, bu ta'rif ham mavjud intuitiv qabul qilinishi kerak. Ushbu ta'rifni aniqlashtirish uchun eng oddiy elementar funktsiyalardan biri dan boshlab, biz hisoblangan funksiyalarni qurishga harakat qilamiz. Manfiy bo'lmagan butun sonlar va o'zgaruvchilardan qo'shish va ayirish (bu erda x - y deb tushuniladi), ko'paytirish, bo'lish (bu erda [a / b] = chumoli(a / b) deb tushuniladi), so'm va mahsulot konstruktsiyasi yordamida olingan funksiyalarni elementar funksiyalar deb ataymiz. Elementar funksiyalarni qurishda foydalaniladigan barcha amallar elementar, chunki uni amalga oshirish algoritmlari yaxshi ma'lum Funktsiyalarni hisoblash mumkinligiga shubha yo'q.

17.Tyuring mashinasi
Fan tarixchilari Alan Tyuringni informatika faniga asos solgan olimlardan biri deb e'tirof etishadi. U 1936-yilda e'lon qilingan o‘zining "Yechim mavjudligini aniqlash masalalariga tadbiq qilinadigan hisoblab chiqariladigan sonlar haqida" deb nomlangan mashhur ilmiy maqolasida, yechish yo‘lini algoritm tarzida ifodalasa bo‘ladigan istalgan matematik masalani "Tyuring mashinalari" orqali yechish mumkinligini isbotlab bergan edi. Elektron hisoblash mashinalarining mantiqiy imkoniyatlari chegarasini tushunishda "Tyuring mashinalari" olimlarga yaqindan yordam beradi.

18.Paradoks (qad. yun. - kutilmagan, galati) – kopchilik tomonidan qabul etilgan an’anaviy fikr, tajribaga oz mazmuni yoki shakli bilan keskin zid bolgan, kutilmagan mulohaza. Har qanday paradoks «shubhasiz togri» (asoslimi, asossizmi, bundan qat’i nazar) hisoblangan u yoki bu fikrni inkor etishdek korinadi. «Paradoks» terminining ozi ham dastlab antik falsafada har qanday galati, original fikrni ifodalash uchun ishlatilgan. Mantiqiy paradokslar, odatda, mantiqiy asoslari tola aniqlanmagan nazariyalarda uchraydim
19.Paradokslar va Sofizm–ataylab chiqariladigan notogri xulosa, biror tasdiqning notogri isboti. Bunda isbotdagi xato ancha ustalik bilan bilintirmay yuboriladi. Sofizmga oid masalalarni dastlab, miloddan avvalgi V asrda Qadimgi Yunonistonda yashagan matematik Zenon tuzgan. Paradoks - bu to'g'ri ko'rinadigan bayonot yoki bayonotlar to'plami qarama-qarshilik yoki qarama-qarshi xulosani keltirib chiqaradi. Ko'pincha, bir-biriga qarama-qarshi ko'rinadigan natija yoki natijalar aslida qarama-qarshi tomonlarga ega. Dilemma , ziddiyat , ziddiyat va chalg'ituvchi so'zlar turkiy tilda paradoks atamasining ekvivalenti sifatida ishlatiladi.
20=3
21.Kombinatorikada umumlashgan koʻpaytirish qoidasi. Kombinatorika - matematikaning berilgan qoidalarga muvofiq ba'zi bir asosiy to'plamdan elementlarni tanlash va joylashtirish masalalarini o'rganadigan bo'limi. Kombinatorikaning formulalari va tamoyillari ehtimollar nazariyasida tasodifiy hodisalarning ehtimolligini hisoblash va shunga mos ravishda taqsimot qonunlarini olish uchun ishlatiladi. Koʻpaytirish qoidasi. Agar A element dastlab m ta usul bilan, undan keyin esa B element n ta usul bilan tanlanishi mumkin boʻlsa, u holda A va B juftlikni mn ta usul bilan tanlanishi mumkin. Bu qoidani quyidagicha ham ifodalash mumkin: Koʻpaytirish qoidasi. A toʻplamdan bitta elementni, undan keyin esa B toʻplamdan bitta elementni tanlash usullari soni ga teng.
22.Mulohazalar algebrasi funksiyalari. Bul funksiyasi.
Mulohazalar va ular ustida bajariladigan mantiqiy amallar birgalikda mulohazalar algebrasi deb yuritiladi. Mulohazalar algebrasining asosiy vazifalaridan biri har qanday murakkab mulohazalarning rost yoki yolg’onligini isbotlashdan iborat. Lekin berilgan murakkab mulohazadagi sodda mulohazalar va ularni bog’lovchi mantiq amallar ortgan sari mazkur mulohazaning rostlik jadvalini tuzish qiyinlasha boradi. Bu qiyinchilikni bartaraf etish uchun mulohazalar algebrasining formulasi va o’zaro teng kuchli formulalar tushunchalarini kiritiramiz. Mantiqiy funksiyaning rostlik qiymati {1, 0} to’plam elеmеntlaridan iborat. Aniqlanish va o’zgarish sohalari {1, 0} to’plamdan iborat bo’lgan funksiyalarga Bul funksiyaslari dеyiladi (D. Bul – angliyalik mashhur mantiqchi va matеmatik)
23.Multigraf. Psevdograf. Chekli graflar Halqasiz chekli grafik multigraf deb ataladi. U elementar grafikdan farq qiladi, chunki u parallel qirralarni o'z ichiga olishi mumkin. Grafikning halqalar va parallel qirralarga ruxsat berilgan eng umumiy holati psevdograf deb ataladi. Keyinchalik, "grafik" atamasi bilan, agar maxsus shart qo'yilmasa, biz psevdografning eng umumiy holatini nazarda tutamiz. Multigrafning chetlarini belgilashning ikki xil usuli mavjud. Ba'zilarning ta'kidlashicha, bir nechta qirralari bo'lmagan grafiklarda bo'lgani kabi, chekka u bog'laydigan uchlari bilan belgilanadi, lekin har bir chekka bir necha marta takrorlanishi mumkin. Boshqalar esa chekkalarni grafikning uchlari bilan teng elementlari sifatida belgilaydi va ular o'z identifikatsiyasiga ega bo'lishi kerak.
24.Kombinatorika. Takrorli oʻrin almashtirish.
Kombinatorika - matematikaning berilgan qoidalarga muvofiq ba'zi (ko'pincha chekli) to'plam elementlarini tanlash va joylashtirish bilan bog'liq masalalarni echishga bag'ishlangan bo'limi. Har bir bunday qoida asl to'plamning elementlaridan ma'lum bir tanlovni belgilaydi, bu kombinatsion konfiguratsiya deb ataladi . Kombinator konfiguratsiyalarning eng oddiy misollari [1] [2] - almashtirishlar , kombinatsiyalar va joylashtirishlar Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2, 3, 4, 5, … (ya‘ni, natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si dastlabki ikkita natural sonlar yig‘indisi (3), 3-si dastlabki uchta natural sonlar yig‘indisi (6) va hokazo (1, 3, 6, 10, 15, …); uchinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si birinchi ikkita ikkinchi tartibli figurali sonlarlar yig‘indisi (4), 3-si birinchi uchta ikkinchi tartibli figurali sonlarlar yig‘indisi (10) va hokazo (1, 4, 10, 20, 35, …); va hokazo.
25.Post teoremasi. No’malum koeffitsientlar usuli yordamida Jegalkin ko‘phadiga keltirish
Halqasiz chekli grafik multigraf deb ataladi. U elementar grafikdan farq qiladi, chunki u parallel qirralarni o'z ichiga olishi mumkin. Grafikning halqalar va parallel qirralarga ruxsat berilgan eng umumiy holati psevdograf deb ataladi. Keyinchalik, "grafik" atamasi bilan, agar maxsus shart qo'yilmasa, biz psevdografning eng umumiy holatini nazarda tutamiz. (Post teoremasi). Funktsiyalar tizimi to'liq bo'lishi tizimdagiuchun unga tegishli bo'lmaganfunksiya mavjudbo'lishi zarur va etarli. Teorema: shartining zarurligi shundan kelib chiqadiki, agar ma'lum funktsiyalar tizimi har qanday funktsional yopiq sinfga tegishli bo'lsa, u holda bu funktsiyalarning barcha superpozitsiyalari ham shu sinfga tegishli.

26.To'la orgraf. Izomorf graflar. faqat bittadan yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi. Ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir.
27.Algoritm. Algoritmning determinantlanuvchanligi.
Informatika fanida deterministik algoritm - bu ma'lum bir kirish berilganda, har doim bir xil natijani beradigan algoritm bo'lib, asosiy mashina har doim bir xil holatlar ketma-ketligidan o'tadi. Deterministik algoritmlar hozirgacha eng ko'p o'rganilgan va tanish algoritm turi, shuningdek, eng amaliylaridan biri hisoblanadi, chunki ular haqiqiy mashinalarda samarali ishlashi mumkin. Rasmiy ravishda, deterministik algoritm matematik funktsiyani hisoblaydi ; funktsiya o'z domenidagi har qanday kirish uchun noyob qiymatga ega va algoritm bu aniq qiymatni chiqish sifatida ishlab chiqaradigan jarayondir.
29.Graflar nazariyasi. Grafning geometrik ifodalanishi
Grafning geometrik ifodalanishi: Graflarning turlicha berilish usullari mavjud. Grafning abstrakt matematik ta’rifi uning berilish usullaridan biridir. Grafning abstrakt matematik ta’rifi uni tasavvur qilish, anglash, uning xossalarini o’rganish va bu xossalarni amalda qo’llash jarayonida ba’zi qiyinchiliklar tug’dirishi tabiiydir. Shuning uchun grafning boshqa berilish usullaridan ham foydalaniladi.
30. Yechiluvchi va sanaluvchi toʻplamlar Toʻplamlar nazariyasi - matning toʻplamlar umumiy xossalarini oʻrganadigan boʻlimi. Toʻplam tushunchasi mat.ning boshlangʻich tushunchasidir. Toʻplamlar nazariyasi asoschilari chex matematigi B. Boltsano va nemis matematigi G. Kantor. Toʻplamni tashkil qilgan obʼyektlar uning elementlari deyiladi


31.Mulohazalar hisobining aksiomalar sistemasi. Isbotlanuvchi formula ta’rifi. Mulohazalar hisobi uchun aksiomalar sistemasi. Mulohazalar hisobining aksiomalar sistemasi XI aksiomadan iborat bo‘lib, ular to‘rt guruhga bo‘linadi Birinchi guruh aksiomalari: Rost qiymat istalgan qiymatdan kelib chiqadi. Implikatsiyaning chap distributivligi. Ikkinchi guruh aksiomalari: Ikki formulaning konyunksiyasidan ularning har biri kelib chiqadi. Agar ikki formulaning har biri bajarilsa ularning konyunksiyasi ham bajariladi Uchinchi guruh aksiomalari: Ikki formulaning dizyunksiyasi ularning har birida kelib chiqadi. Agar C formula A va B formulalarning har biridan kelib chiqsa u holda u ularning dizyunksiyasidan ham kelb chiqadi. To’rtinchi guruh aksiomalari: . Kontrapozitsiya qoidasi


32.Grafning maxsus turdagi kophad yordamida berilishi
Grafni maxsus turdagi ko‘phad yordamida ham berish mumkinligini ta’kidlaymiz. Uchlari to‘plami bo‘lgan graf berilgan bo‘lsin. grafning yakkalangan uchlari yo‘q deb faraz qilamiz,. Bu grafni ta o‘zgaruvchilarga bog‘liq

ko‘rinishdagi ko‘phad yordamida tasvirlash mumkin, bu yerda ko‘paytma shartni qanoatlantiruvchi barcha juftlar bo‘yicha amalga oshiriladi, o‘zgaruvchi uchga mos keladi, – va uchlarni tutashtiruvchi qirralar soni, – uchdagi sirtmoqlar soni.

34.Mantiq algebrasidagi ikki taraflama qonun. F(x1,x2..)funksiyaga ikki taraflama bo‘lgan funksiyani topish uchun funksiyaning chinlik jadvalida hamma o‘zgaruvchilarni ularning inkoriga almashtirish kerak, ya’ni hamma joyda 1ni 0ga va 0ni 1ga almashtirish kerak.



37-43. Keltirib chiqarish qoidasi (O‘rniga qo‘yish, xulosa chiqarish)
O’rniga qo’yish qoidasi. Agar A mulohazalar hisobining isbotlanuvchi formulasi, x -o’zgaruvchi, B mulohazalar hisobining ixtiyoriy formulasi bo’lsa, u vaqtda A formula ifodasidagi hamma x lar o’rniga B formulani qo’yish natijasida hosil etilgan formula ham isbotlanuvchi formula bo’ladi. Agar ( , ,..., ) 1 2 n A x x x – isbotlanuvchi formula va B B Bn , ,..., 1 2 mulohazalar hisobining ixtiyoriy formulalari bo’lsa, u vaqtda A formulaning n x , x ,...,x 1 2 o’zgaruvchi-lari o’rniga bir vaqtda mos ravishda B B Bn , ,..., 1 2 formulalarni qo’yish natijasida C isbotlanuvchi formulani hosil qilish, bir vaqtda o’rniga qo’yish qoidasi deb ataladi. A xulosa chiqarish qoidasi, xulosa qilish qoidasi yoki o'zgartirish qoidasi a mantiqiy shakl binolarni egallaydigan, ularni tahlil qiladigan funktsiyadan iborat sintaksis va xulosani qaytaradi (yoki xulosalar ). Masalan, chaqirilgan xulosa qoidasi modus ponens biri "Agar p keyin q", ikkinchisi "p" shaklida ikkita bino oladi va "q" xulosasini qaytaradi.

44.Kombinatorika. n elementli o'rin almashtirish
Ta’rif: n elementni n tadan o’rinlashtirishlar o’rin almashtirishlar deyiladi. O’rin almashtirishlar P_n bilan belgilanadi.O’rin almashtirishlar sonini o’rinlashtirishdagi k ning o’rniga n ni qo’yib keltirib chiqarish mumkin. A = n (n-1)…(n-(k-1)) (1) k = n
A = n (n-1)…(n-(n-1)) = n (n-1) (n-2)…1=1·2·3·…(n-2) (n-1)n = n! P_n =A = n! Demak, n elementni o’rinlashtirishlar soni n faktorialga teng.Birdan n gacha bo’lgan sonlar ko’paytmasi factorial deyiladi. P_n = n!

Nyuton binomi.

Mantiq algebrasidagi arifmetik amalllar Jegalkin ko'phadi
Mantiq algebrasidagi istalgan funksiyani yagona arifmetik ko'phad shakliga keltirish mumkin. Haqiqatan ham, biz oldingi paragraflarda istalgan funksiyani kon'yunksiya va inkor mantiqiy amallar orqali ifodalash mumkinligini ko'rgan edik. Yuqorida kon'yunksiya, diz'yunksiya va inkor mantiqiy amallarni arifmetik amallar orqali ifodaladik
Bul algebrasidagi xy kon`yuksiya amali oddiy arifmetikada 0 va 1 sonlari ustidagi kо‘paytma amaliga mos keladi. Ammo 0 va 1 sonlarini qо‘shish natijasi tо‘plam doirasidan chetga chiqadi. Shuning uchun I.I.Jegalkin 2 moduliga qо‘shish amalini kiritadi (I.I.Jegalkin о‘tgan asrning 30-yillar boshida Moskva davlat universitetida birinchi bо‘lib matematik mantiq bо‘yicha ilmiy seminar tashkil etgan.) x vа y mulohazalarni 2 moduli bо‘yicha qо‘shishni x+y ko`rinishda belgilaymiz va u quyidagi chinlik jadvali bilan beriladi:

Kombinatorikada qoʻshish va koʻpaytirish qoidasi.
Kombinatorika - matematikaning berilgan qoidalarga muvofiq ba'zi bir asosiy to'plamdan elementlarni tanlash va joylashtirish masalalarini o'rganadigan bo'limi. Kombinatorikaning formulalari va tamoyillari ehtimollar nazariyasida tasodifiy hodisalarning ehtimolligini hisoblash va shunga mos ravishda taqsimot qonunlarini olish uchun ishlatiladi. tasodifiy o'zgaruvchilar. Bu, o'z navbatida, tabiatda va texnologiyada namoyon bo'ladigan statistik qonuniyatlarni to'g'ri tushunish uchun juda muhim bo'lgan ommaviy tasodifiy hodisalarning qonuniyatlarini o'rganish imkonini beradi. Kombinatorikada qo'shish va ko'paytirish qoidalari Jamlama qoidasi. Agar ikkita A va B amallar bir-birini istisno qilsa va A harakat m usulda, B esa n ta usulda bajarilishi mumkin bo'lsa, u holda bu harakatlardan istalgan biri (A yoki B) n + m usulda bajarilishi mumkin.
42-4-59. Teng kuchli formulalar MA ning  va  formulalari berilgan bo‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A₁ ,. . ., A_m - lardan iborat bo‘lsin. Agar A₁ , . . . , A _m mulohazalarning barcha qiymatlar tizimlari ( i₁, . . . , i_m ) lar uchun  va  formulalar bir щil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi.  va  formulalarning teng kuchliligi    ko‘rinishda ifodalanadi. ( A₁,. . . , A_n) formulasi A₁ ,. . . , A_n mulohazalarning barcha qiymattizimi ( i₁, . . . , i_n) uchun 1 qiymat qabul qilsa, aynan rost formula yoki tavtologiya yoki mantiq qonunii deyiladi.
45.Hisoblanuvchi funksiyalar. Qismiy rekursiv va umumrekursiv funksiyalar
Agar g = f(xl,x2,...,xn) funksiyaning qiymatini hisoblovchi algoritm mavjud bo‘Isa, и holda и effektiv (samarali) hisoblanuvchifunksiya deb ataladi. Bu ta’rifda algoritm tushunchasi intuitiv ma’noda tushunilganligi sababli, effektiv hisoblanuvchi funksiya tushunchasi ham intuitiv tushuncha bo‘ladi. Ta’rif: (x1,…,xn) funksiya qismiy rekursiv funksiya deyiladi agarda u sodda funksiyalardan S,R,M operatorlarni chekli marta qo’llash bilan olinishi mumkin bo’ladi. Agar / ( x , , x 2,...,x n) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo ‘Isa, u holda f (x ,, x 2,..., x n) umumrekursiv funksiya deb ataladi. Ushbu A(x), 0 (x ), I'”(x), /(v,x) = v + x, f(y,x)-x-y va / (y,x) = x n funksiyalar umumrekursiv funksiyalardir.
46.Funksional yopiq sinflar. To‘liq funkiyalar sistemasi
Mantiq algebrasining superpozitsiyaga nisbatan yopiq bo‘lgan har qanday funksiyalar sistemasi funksional yopiq sinf deb ataladi. Ravshanki, muayyan xususiyatga ega bo‘lgan funksiyalar sistemasi funksional yopiq sinfni tashkil etadi va, aksincha, ma’lum funksional yopiq sinfga kiruvchi funksiyalar bir xil xususiyatga ega bo‘lgan funksiyalardir. Agar [ A] =P₂ bo‘lsa, u holda A funksiya-lar sistemasi to‘liq deb ataladi. funksiyalar sistemasining to‘liq bo‘lishi uchun bu sistemada har qanday xususiy funksional yopiq sinfga kirmaydigan funksiya topilishi yetarli va zarurdir.
47.O‘rinlashtirishlar. Kombinatorika-24 n ta elementli to‘plam berilgan bo‘lsin. to‘plamning ixtiyoriy m ta elementidan hosil qilingan tartiblangan tuzilmaga (kombinatsiyaga) n ta elementdan m tadan o‘rinlashtirish deb ataladi. Bu ta’rifdan ko‘rinib turibdiki, elementlari soni bir xil bo‘lgan ikkita har xil o‘rinlashtirishlar bir-biridan elementlari bilan yoki bu elementlarning joylashish tartibi bilan farq qiladilar. Bundan tashqari, n ta elementdan m tadan o‘rinlashtirishlar uchun bo‘lishi ham ravshan.

48.Algoritmning xarakterli xususiyatlari