1. Agar funktsiya a ni b ga turli qiymatli akslantirish bo‘lsa, u holda funktsiya a va b to‘plamlarning o‘zaro bir qiymatli mosligi

Gamilton grafi. Agar grafda oddiy cikl mavjud bo'lib, bu ciklda grafning barcha tugunlari qatnashsa, bunday tsikl Gamilьton tsikli deyiladi.
Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda tugunlarning hammasi ishtirok etsa. Tugun va qirralar takrorlanmasligi kerak.
Grafda Gamilton tsikli mavjud bo'lsa, bu graf Gamilton grafi deyiladi.


47-bilet
1 .Ma’lumki, mantiqiy amallar mulohazalar algebrasi nuqtai nazardan chinlik jadvallari bilan to’liq xarakterlanadi. Agarda funskiyaning jadval shaklda berilishini esga olsak, u vaqtda mulohazalar algebrasida ham funksiya tushunchasini aniqlashimiz mumkin.Mulohazalar ustida mantiqiy amallar. Mulohazalar ustida konyunksiya, dizyunksiya, implikatsiya va ekvivalensiya amallari mavjud bo’lib ularning rostlik jadvali quydagicha bo’ladi: Mulohaza va uning qiymatlari. Matematik mantiqning boshlang‘ich tushunchalaridan biri mulohaza tushunchasidir. “Mulohaza” deganda biz rost yoki yolg‘onligi haqida fikr yuritishi mumkin bo‘lgan darak gapni tushunamiz. Har qanday mulohaza yo rost yoki yolg‘onbo‘ladi. Hech bir mulohaza bir vaqtning o‘zida ham rost ham yolg‘on bo‘la olmaydi. Masalan, “ ”, “ ”, “5 son tub son”, “1 son tub son”, “o‘g‘limning yoshi otasining yoshidan katta” mulohazalarining birinchisi – rost, ikkinchisi yolg‘on, uchinchisi – rost, 4 chi va 5 chilari esa yolg‘on mulohazalardir.So‘roq va undov gaplar mulohaza bo‘la olmaydi. Ta’riflar ham mulohaza bo‘la olmaydi. Masalan, “2 songa bo‘linuvchi son juft son deyiladi” degan ta’rif mulohaza bo‘la olmaydi. Ammo “agar butun son 2 ga bo‘linsa, u holda bu son juft son bo‘ladi” degan darak gap mulohaza bo‘ladi. Bu mulohaza – rost.Mulohazaning qiymati deganda biz uning rost yoki yolg‘onligini tushunamiz. Mulohazalar odatda lotin alifbosining bosh harflari (A, B, C, .... X, Y, Z) bilan, ularning qiymatlari (“rost”, “yolg‘on”)ni R va Yo harflari bilan belgilaymiz. Bu yerda R – rost, Yo – yolg‘on. Shuningdek, ularni raqamlar bilan ham belgilash kiritilgan bo‘lib, rost mulohaza 1, yolg‘on mulohaza esa 0 bilan belgilanadi.Qismlarga ajratilmaydigan mulohazalar elementar mulohazalar deb aytiladi. Elementar mulohazalar yordamida undan murakkabroq mulohazalarni tuzish mumkin.
3. 4-Ta’rif. funksiyani ifodalovchi DNSh- tupikli DNSh deyiladi, agarda uning tarkibida birorta ham e.k. va birorta ham hadni tashlab yuborish mumkin bo‘lmasa.Masalan: tupikli DNSh, chunki bundan ni tashlab yuborish, shuningdek, e.k. ni ham tashlab yuborish mumkin emas.Faraz qilaylik, funksiyani ifodalaydigan tupikli DNSh lar bo‘lsin.5-Ta’rif. Agar DNSh₁ tupikli DNSh ning o‘zgaruvchilar soni, DNSh₂ tupikli DNSh ning o‘zgaruvchilar soniga nisbatan kichik bo‘lsa, u xolda tupikli DNSh₁ minimal DNSh deyiladi. 6-Ta’rif. Agar DNSh₁ tupikli DNSh ning kon’yunksiyalar soni, DNSh₂ tupikli DNSh ning konyuksiyalar soniga nisbattan kichik bo‘lsa, u xolda tupikli DNSh₁ qisqa DNSh deyiladi.7-Ta’rif. Har qanday minimal DNSh eng qisqa DNSh bo‘ladi.8-Ta’rif. Har qanday qisqa DNSh minimal DNSh bo‘lmaydi.