Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi

O`ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Kompyuter injiniring" fakulteti

Diskret tuzilmalar fanidan

MUSTAQIL ISH
№ 2

Bajardi: DI 21-10 guruh

talabasi Boboqulov.Sh
Tekshirdi: Saidov.O’

SAMARQAND 2023

MAVZU: Bul funksiyalari uchun diz’yunktiv va kon’yunktiv normal shakllar (DNSh, KNSh). Mukammal diz’yunktiv va mukammal kon’yunktiv normal shakllar (MDNSh, MKNSh)
Reja:

1. 
   Bul funksiyalari uchun normal shakllar(DNSh, KNSh, MDNSh, MKNSh).
   

2. Formulalarni KNSh va DNSh ko‘rinishga keltirish.
3. Formulalarni MKNSh va MDNSh ko‘rinishga keltirish.

1. Formulalarning normal shakllari

Mulohazalar algebrasida funksiya tushunchasi. Oddiy algebradagi funksiya tushunchasiga o‘xshash, mulohazalar algebrasida ham funksiya tushunchasi kiritilishi mumkin.
Ma’lumki, oddiy algebrada funksiyaning qiymatlari turli usullar vositasida, masalan, jadval yordamida berilishi mumkin. Mulohazalar algebrasida ko‘pchilik tushunchalarni ifodalashda Chinlik jadvallari qulay vosita hisoblanadi. Chinlik jadvallarida faqat ikkita o‘zgarmas (0 va 1) ishtirok etadi. Shu tufayli deb belgilaymiz.
Ta’rif 1. ta Bul o‘zgaruvchisiga bog‘liq bo‘lgan funksiyaga Bul funksiyasi deyiladi. Bul funksiyalarining aniqlanish va qiymatlari sohasi to‘plamdan iboratdir.
Istalgan Bul funksiyasini chinlik jadvali orqali berish mumkin, bunda o‘zgaruvchilarning mumkin bo‘lgan barcha qiymatlari to’plamiga mos mantiqiy qiymat beriladi.
O‘zgaruvchilarning mumkin bo‘lgan barcha qiymatlari to’plamida aynan bir xil qiymat qabul qiluvchi ikkita Bul funksiyasi teng kuchli funksiyalar deb ataladi.
Bitta o‘zgaruvchiga bog‘liq bo‘lgan Bul funksiyalarini chinlik 1-jadvalini quramiz.

1-jadval

0	0	0	1	1
1	0	1	0	1

Jadvaldan ko‘rinib turibdiki bitta o‘zgaruvchiga bog‘liq to‘rtta funksiya mavjud.

va mos ravishda 0 va 1 ga teng bo‘lgan o‘zgarmaslar deb ataladi.
funksiyaayniyfunksiyadeyiladi:
.
funksiya o‘zgaruvchiga teskari qiymatlarni qabul qiladi va ning inkori deb ataladi, ko‘rinishda belgilanadi:
.
Ikkita o‘zgaruvchiga bog‘liq bo‘lgan , , …, 16 Bul funksiyalarini chinlik jadvalini quramiz (2-jadval):
2-jadval

0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Jadvaldan ko‘rinib turibdiki ikkita o‘zgaruvchiga bog‘liq bo‘lgan funksiyalar soni 16 ta, o‘zgaruvchiga bog‘liq bo‘lgan funksiyalar soni taga teng bo‘ladi.

2-jadvaldan ko'rinib turibdiki, ikkitao'zgaruvchiggabog’liqfunktsiyalarbittao'zgaruvchigabog'liqbo'lganfunktsiyalarnio'zichigaoladi.
va funksiyalar mos ravishda 0 va 1 o‘zgarmaslarni beradi.
, , , funksiyalar bitta o‘zgaruvchiga bog‘liq: , – o‘zgaruvchini o‘zini qiymatiga teng, , – o‘zgaruvchilarning inkorlariga teng.
Qolgan funksiyalarning ko‘rinishlarini yozib chiqamiz:
– konyunksiya,
– dizyunksiya,
– ekvivalensiya,
– ikki modul bo‘yicha qo‘shish yoki Jegalkin amali,
– konversiya,
–implikatsiya,
–Sheffershtrixi,
–Pirsstrelkasi,
va funksiyalar implikatsiya va konversiyaga teskari hisoblanadi.
Bir va ikki o‘zgaruvchiga bog‘liq bo‘lgan bul funksiyalari elementar funksiyalar hisoblanadi.
To‘plamlar ustida bajariluvchi amallar xossalari va Bul funksiyalarining xossalari orasida bog‘lanish mavjud:
1. Birlashma va kesishmaning idempotentligi:
, ,
xususiy xolda
Ǿ , Ǿ = Ǿ, , .
Dizyunksiya vakonyunksiyaning idempotentligi:
, ,
xususiy holda
, , , .

2. 
   Birlashma va kesishmaning kommutativligi:
   

, .
Dizyunksiya vakonyunksiyaning kommutativligi:
, .
Kommutativlik ikki modul bo‘yicha qo‘shish, Pirs strelkasi va SHeffer shtrixi amallariga ham xos xususiyatdir. O‘zgaruvchilarning o‘rni almashishi funksiyaning qiymatiga ta’sir qilmaydi.

2. 
   Birlashma va kesishmaning assotsiativligi:
   

, .
Dizyunksiya vakonyunksiyaassotsiativligi:
, .
Assotsiativlik dizyunksiya vakonyunksiyaning bajarilish tartibi farqlanmasligini bildiradi, ikki modul bo‘yicha qo‘shish amali ham assotsiativlik qoidasiga bo‘ysunadi .

2. 
   Birlashmaning kesishmaga nisbatan distrubutivligi va aksincha:
   

, .
Dizyunksiyaningkonyunksiyaga nisbatan distrubutivligi va aksincha:
, .

2. 
   Birlashma va kesishmaning yutilishi:
   

, .
Dizyunksiya vakonyunksiyaning yutilishi:
, .
Yutilish qonunlari Bul funksiyalarini soddalashtirish imkonini beradi.

2. 
   Involyutivlik (ikki karrali to‘ldiruvchini aniqlash):
   

.
Ikki karrali inkor qoidasi:
.

2. 
   deMorgan qonuni:
   

, .
, .
de Morgan qonunlari dizyunksiyavakonyunksiya orasidagi bog‘lanishni ifodalaydi.

2. 
   To‘ldiruvchi qonuni:
   

, Ø.
Tavtologiyayoki uchinchisi istesno qonuni:
.
Muvofiqlik qonuni:
.
Bul funksiyalari ustida bajariladigan amallar tartibi: eng kuchli amal – inkor, undan keyinkonyunksiya, so‘ngra – dizyunksiya, so‘ngra – implikatsiya, so‘ngra – ekvivalensiya. Qolgan amallarning bajarilish tartibi qavslar bilan ajratib ko‘rsatiladi. Konyunksiya amali algebraik ko‘paytma ko‘rinishida ham ifodalanishi mumkin. Masalan de Morgana qonunlarini quyidagicha ifodalash ham mumkin: , .