ABOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
DISKRIT TUZILMALARI fanidan
MUSTAQIL ISH
Mavzu: Mukammal kon'yuktiv normal shakli (MKNSh),
uni tuzish usuli.
Bajardi: 073-21 gurux talabasi Saidjalol Qodirov
TOSHKENT – 2022
REJA:
1. Mukammal konyunktiv normal shakllar;
2. (MKNSh)ning tuzilish usullari;
3. Mukammal kon'yunktiv normal shakl (SKNF);
Har qanday mantiqiy formula uchun bir xil o'zgartirishlar yordamida unga ekvivalent bo'lgan cheksiz ko'p formulalar qurish mumkin. Mantiq algebrasida asosiy vazifalardan biri kanonik shakllarni izlashdir (ya'ni, bitta qoida bo'yicha tuzilgan formulalar, kanon). Agar mantiqiy funktsiya o'zgaruvchilarning diszyunksiyasi, konyunksiyasi va inkori orqali ifodalansa, u holda tasvirlashning bu shakli normal deyiladi. Oddiy shakllar orasida mukammal normal shakllar ajralib turadi (funktsiyalar o'ziga xos tarzda yozilgan shakllar). Toʼplamlar va ular ustida amallar. Munosabatlar. Relyatsion algebra. Binar munosabatlarning koʼpaytmasi. Mantiqiy bogʼlovchilar Muloxazalar algebrasi. Chinlilik jadvali. Formula, qism formula. Formulalarning teng kuchliligi. Mulohazalar algebrasining asosiy teng kuchliliklari. Keltirilgan formulalar. Mantiqiy amallarning toʼliq sistemalari. Normal formalari. Mukammal dizʼyunktiv va konyunktiv normal formalar. Mulohazalar algebrasi formulalarining tatbiqlari. Rele-kontakt sxemalari. Formal aksiomatik nazariya. Mulohazalar xisobi. Mulohazalar hisobining aksiomalari. Deduktsiya teoremasi. Toʼliqlik xaqida Gyodel teoremasi. Ziddiyatsizligi. Elementar Bul funktsiyalari. Ularning berilish usullari. Muxim va sohta oʼzgaruvchilar. Formula tushunchasi.Ekvivalent formulalar. Dual funktsiyalar. Duallik printsipi. Normal formalar. Funktsiyani oʼzgaruvchilar boʼyicha yoyish. Toʼliq sistemalar. Bul funksiyasini Jegalkin koʼpxadiga yoyish. Muxim yopiq sinflar. Oʼz-oʼziga dual boʼlmagan funktsiya xaqida lemma. Monoton boʼlmagan va chiziqli boʼlmagan funktsiyalar xaqidagi lemmalar. Post teoremasi va uning natijalari. Predikat tushunchasi. Predikatlar ustida mantiqiy amallar. Umumiylik va mavjudlik kvantorlari. Cheklangan kvantorlar. Mantiqiy kvadrat. Predikatlar algebrasining formulalari. Predikatlar algebrasida formulalarning teng kuchliligi. Formulalarning normal kanonik formalari. Kombinatorikaning asosiy elementlari. Аsosiy kombinatsiyalar. Kiritish chiqarish qoidasi. Rekkurent munosabatlar metodi. Fibonachchi sonlari. Xosil qiluvchi funktsiyalar. Graflar va ularning berilish usullari.Graflarning turlari. Graflarning bogʼliqligi. Marshrut, zanjir, sikl. Graf metrikasi. Eyler va Gamilton graflari. Orientirlangan graflar. Tranzitiv graflar. Graflarning bikomponenalari. Graflarni buyash. Xromatik sonlar. Toʼplamlar va ular ustida amallar. Munosabatlar. Relyatsion algebra. Binar munosabatlarning koʼpaytmasi. Funktsiya. Maxsus binar munosabatlar. Ekvivalentlik munosabati. Qisman tartiblangan toʼplamlar. Mantiqiy bogʼlovchilar Muloxazalar algebrasi. Chinlilik jadvali. Formula, qism formula. Formulalarning teng kuchliligi. Mulohazalar algebrasining asosiy teng kuchliliklari. Keltirilgan formulalar. Mantiqiy amallarning toʼliq sistemalari. Normal formalari. Mukammal dizʼyunktiv va konyunktiv normal formalar. Mulohazalar algebrasi formulalarining tatbiqlari. Rele-kontakt sxemalari. Formal aksiomatik nazariya. Mulohazalar xisobi. Mulohazalar hisobining aksiomalari. Deduktsiya teoremasi. Elementar Bul funktsiyalari. Ularning berilish usullari. Muxim va sohta oʼzgaruvchilar. Formula tushunchasi.Ekvivalent formulalar. Dual funktsiyalar. Duallik printsipi. Normal formalar. Funksiyani oʼzgaruvchilar boʼyicha yoyish. Toʼliq sistemalar. Bul funksiyasini Jegalkin koʼpxadiga yoyish. Post teoremasi va uning natijalari. Predikat tushunchasi. Oʼzgarmas predmetlar va oʼzgaruvchi muloxazalar. Predikatlar ustida mantiqiy amallar. Umumiylik va mavjudlik kvantorlari. Cheklangan kvantorlar. Mantiqiy kvadrat. Predikatlar algebrasining formulalari. Bajariluvchi, rad etiluvchi formulalar. Аynan rost, aynan yolgʼon formulalar. Predikatlar algebrasida formulalarning teng kuchliligi. Birinchi tartibli nazariya. Model. Kombinatorikaning asosiy elementlari. Аsosiy kombinatsiyalar Graflar va ularning berilish usullari.
Кon’yuktiv normal shakl (KNSH) deb funksiyani har biri, argumentning sodda dizyunksiyasi (yoki ularning inversiyalari) bo‘ladigan hadlar qatorining kon’uynksiyasi ko‘rinishida tasvirlash shakliga aytiladi.
KNSHga funksiyani tasvirlashning quyidagi shakli misol bo‘la oladi :
KNSH bo‘lmaydigan funksiyani tasvirlash shaklini keltiramiz :
Bu shakl MKNSH bo‘lmaydi, chunki uning birinchi hadi qolganlari bilan kon’yunksiya amali orqali bog‘lanmagan.
KNSHning har bir hadida MKNSH barcha argumentlari keltirilgan bo‘lishi kerak . KNSHdan MKNSH ga o‘tish uchun barcha argumentlarni o‘z ichiga olmaydigan har bir hadiga хi*хi ko‘rinishdagi hadlarni qo‘shish kerak, bu yerda хi haddagi mavjud bo‘lmagan argument
Do'stlaringiz bilan baham: |
