Нормал формулалар

Mavzu: Formulalarning normal shakllari.

x ,x, xy, xy ,x→y ,xy asosiy elementar funksiyalarning superpozitsiyasi vositasida hosil qilingan ifoda formula deb ataladi.

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 E₂ =0,1 deb belgilaymiz.

Ta’rif. n ta Bulo‘zgaruvchisiga bog‘liq bo‘lgan funksiyaga Bul funksiyasi deyiladi. Bul funksiyalarining aniqlanish va qiymatlari sohasi {0,1} 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 jadvalini quramiz (jadval):

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.

funksiya ayniy funksiya deyiladi:

funksiya x o‘zgaruvchiga teskari qiymatlarni qabul qiladi va x ning inkori deb ataladi, ko‘rinishda belgilanadi:

(x) =

Formulaning normal shakllari quyidagi ta’rif asosida aniqlanadi.

Ta’rif. 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.

Teorema. Mantiq algebrasining ixtiyoriy formulasini KNShga keltirish mumkin.

Teorema. Mantiq algebrasining formulasi tavtologiya bo‘lishi uchun uning KNShidagi barcha elementar diz’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.

Teorema. Mantiq algebrasining ixtiyoriy formulasini DNShga keltirish mumkin.

Elementarmulohazalarningharbir P formulasigatengkuchlikon’yunktiv normal shakldagi Q formula mavjud.

Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz:

;

2. ;

3. A→ B =  B ;

4. = A ;

5. A  B = (  B)  (A ) ;

6. (A  )  (  B).

Teorema. Mantiq algebrasining formulasi aynan yolg‘on bo‘lishi uchun uning DNShdagi barcha elementar kon’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.

To‘g‘ri va to‘liq elementar kon’yunksiya va diz’yunksiyalar.

 Yuqorida teng kuchli almashtirishlar bajarib, mantiq algebrasining berilgan formulasi uchun turli KNShlar va DNShlar topish mumkinligi haqida ma’lumot berilgan edi.

Formulalar uchun turli KNShlar va DNShlar orasida muayyan shartlarni qanoatlantiradiganlari muhim hisoblanadi. Quyida shunday shakllar o‘rganiladi.

Ta’rif. Agar elementar kon’yunksiya (diz’yunksiya) ifodasida ishtirok etuvchi har bir elementar mulohaza shu ifodada faqat bir marta uchrasa, u holda bu ifoda to‘g‘ri elementar kon’yunksiya (diz’yunksiya) deb ataladi.

Ta’rif.Agar berilgan elementar mulohazalarning har biri elementar kon’yunksiya (diz’yunksiya) ifodasida faqat bir matra qatnashsa, bu ifoda shu elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya (diz’yunksiya) deb ataladi.

Ta’rif. Agar formulaning KNShi (DNShi) ifodasida bir xil elementar diz’yunksiyalar (kon’yunksiyalar) bo‘lmasa va barcha elementar diz’yunksiyalar (kon’yunksiyalar) to‘g‘ri hamda ifodada qatnashuvchi barcha elementar mulohazalarga nisbatan to‘liq bo‘lsa, u holda bu ifoda mukammal kon’yunktiv normal shakl (mukammal diz’yunktiv normal shakl) deb ataladi.¹

Teorema. Elementar mulohazalarning aynan yolg‘on bo‘lmagan ixtiyoriy formulasini MDNShga keltirish mumkin.

Ta’rif. 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.

Quyida berilgan variantlardagi formulalarning DNSh, KNSh, mukammal DNSh va KNSh larini hosil qiling.



Foydalanilgan teng kuchli formulalar:

1.   (a)

2.   (b)

3.   (c)

1-ish. Berilgan formulani (a), (b) va (c) teng kuchli formulaga asosan soddalashtiramiz.



Natija ya’ni DNSh     ga teng.

2-ish. Formulaga asosan berilgan F funksiyaning KNSHsini quydagicha topamiz.

Formulaning KNSH si quyidagicha: 

3-ish Endi   funksiyaning chinlik jadvalini tuzamiz va funksiyaning rost qiymatlariga mos bo’lgan MDNSHlarni hosil qilamiz.(1-jadval)

Jadvaldan funksiyaning chin qiymatlarni olib quyidagi amallarni bajaramiz.

{0,0,0,}, {0,0,1}, {0,1,0}, {0,1,1} va {1,1,0}, endi 3- ta’rifga ko’ra ularning kanyuksiyalar dizyunksiyasi chin qiymat qabul qilishi uchun ularning inkorlarini olamiz va quyidagicha yozamiz.

Bundan ko’rinib turibdiki formulaning bu MDNSHsi quyidagicha:

To‘plamlar ustida bajariluvchi amallar xossalari va Bul funksiyalarining xossalari orasida bog‘lanish mavjud:

1.Birlashma va kesishmaning idempotentligi:

A =A ,

xususiy xolda,

A Ǿ = A, A Ǿ = Ǿ, A U=U, A U =A .

Dizyunksiya vakonyunksiyaning idempotentligi:

xx=x, xx=x ,

xususiy holda

x0 = 0 , x0=0, x1=1, x1=1

2. Birlashma va kesishmaning kommutativligi:

A B=B A , A B=B A

Dizyunksiya vakonyunksiyan ing kommutativligi:

xy =yx , xy =yx

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.

3. Birlashma va kesishmaning assotsiativligi:

A(B C)=(A B C,

(AB)C=A(BC)

Dizyunksiya va konyunksiya assotsiativligi:

x(yz)=(xy)z , x(yz)=(xy)z.

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

4. Birlashmaning kesishmaga nisbatan distrubutivligi va aksincha:

A(B  C)=(AB) (AC), ABC=(AB)(AC). Dizyunksiyaningkonyunksiyaga nisbatan distrubutivligi va aksincha:

x(yz)= (xy)(xz) , x(yz)=(xy)(xz)

5. Birlashma va kesishmaning yutilishi:

(AB)A=A, (AB)A=A

Dizyunksiya vakonyunksiyaning yutilishi:

(xy)y=y (xy)y=y

Yutilish qonunlari Bul funksiyalarini soddalashtirish imkonini beradi.

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

=A

Ikki karrali inkor qoidasi:

=x

7. deMorgan qonuni:

=  , = 

=  , =  .

de Morgan qonunlari dizyunksiyavakonyunksiya orasidagi bog‘lanishni ifodalaydi.

8. To‘ldiruvchi qonuni:

A =U, A = Ø.

Tavtologiya yoki uchinchisi istesno qonuni:

x =1

Muvofiqlik qonuni:

x = 0.

Ta’rif. Diz’yunktiv normal shakl (kon’yunktiv normal shakl) TDNSh (TKNSh) deb aytiladi, agar DNSh (KNSh) ifodasida bir xil elementar kon’yunksiyalar (elementardiz’yunksiyalar) bo‘lmasa va hamma elementar kon’yunksiyalar (elementar diz’yunksiyalar) to‘g’ri va to‘liq bo‘lsa.

Masalan,

xyzxy x z yz

DNSh x,y,z mulohazalarga nisbatan TDNSh bo‘ladi.

(xy), (x ), ( y)

KNSh x, y mulohazalarga nisbatanTKNShbo‘ladi. Asosiy mantiqiy amallarning TDNSh va TKNSh ko‘rinishlari quyidagicha bo‘ladi:

a)MDNSh: = ; xy = xy ; xy = xy yx ; x → y = xy y x ; x → y = xy .

b) TKNSh: = ; xy = ( y) (x ) (xy) ; xy = xy ; x → y = y ; x → y = ( y) (x )