U aynan yolgon formuladir

Form ulalarning normal shakllari
Teng kuchli almashtirishlar bajarib, muloxazalar algebrasining formulalarini xar xil kurinishlarda yozish mumkin. Masalan, A -+ VS formulani L v i? C yoki {A v B )(A v Q . kurinishlarda yoza olamiz.

Mantik algebrasining kontakt va rele-kontaktli sxemalar, diskret texnikadagi tadbiqlarida va matematik mantikning boshk.a masalalarida formulalarning normal shakllari katga axamiyatga ega. Kuyidagi belgilashni kiritamiz:

kurinishdagi formula elementar dizʼyunksiya deb ataladi, bu yerda xam a = {st,, st2, ..., стл} ixtiyoriy kiymatlar satri va x(. uzgaruvchilar orasida bir xillari bulishi mumkin.

3 - t a ʼ r i f . Elementar dizʼyunksiyalarning konʼyu nksiyasi formulaning konʼyunktiv normal shakli (KNSH ) va element ar konʼyunksiyalarning dizʼyunksiyasi formulaning dizʼyunktiv normal shakli (DNSH) deb ataladi.

KN SH ga (x v u ) l (Zs v z) a (x v u v z) formula va D N SH ga x y v x z v xyz formula misol bula oladi.

1-teorema. Elementar muloxazalarning xar bir R formulasiga teng kuchli konʼyunktiv normal shakldagi Q formula mavj ud.

Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz:

1. 
   Rdagi elementar muloxazalar l va v amallari bilangina birlashtirilgan bulsa xam, lekin d sunggi amalni ifodalamaydi. Bu xolda Av(BaC) = (Av B)a(AvB) istributivlik konunidan foydalanib, sunggi amali d dan iborat teng kuchli formulaga keltiramiz;
   
2. 
   R formula - , V, d, -u, mantikiy amallar vositasida tuzilgan biror formulani ifodalasin. U xolda R ga (3) teng kuchliliklarni tatbik etib, R bilan teng kuchli va v, l bilan ifodalangan R 1 formulani xosil kilamiz. Agar R1 K N SH kurinishida bulmasa, unga Av (Ba Q = (AvB)a (Av B) distributivlik konunini tatbik etib, chekli adamlardan keyin R bilan teng kuchli Q konʼyunktiv normal shakldagi formulaga kelamiz.
   

Izox- R formulani konʼyunktiv normal shaklga keltirish jarayonida

Shunday kilib, P formulaning K N SH bittagina dizʼyunktiv (xvy) xaddan iborat ekan.

R formula tavtologiya ekanligini chinlik jadvaliga murojaat kilmay turib xam nikdash mumkinmi degan savolga kuyidagi chinlik alomati deb atalgan eorema ijobiy javob beradi.

2-teorema. R formula doimo chin bulishi uchun uning K N SH dagilar bir elementar dizʼyunktiv %adida kam ida bitta elementar muloxaza bilan birga bu muloxazaning inkori ham mavjud bulishi zarur va yetarli.
Isbot:

1. 
   R formulaning
   

R = A1 a A2 A ... a A„ (5)

K N SH dagi xar bir A1. xadida kamida bitta elementar muloxaza bilan birga bu muloxazaning inkori xam mavjud bulsin, yaʼni A/ = x v x v u v ...v i shaklida bulsin, u xolda x v x - J va J v A = J larga asosan A,- = J v ( y v . . . v u v V) = J buladi. Demak, R = J a J a ... a J = J buladi, yaʼni aynan chin formula buladi.

2. 
   Endi R tavtologiya bulsin va A, uning K N SH dagi shunday elementar dizʼyunktiv xadi bulsinki, unda birorta elementar muloxaza bilan birga uning inkori katnashmagan bulsin. Masalan, A, = x v u v ... v i shaklida bulsin. Endi, elementar muloxazalarning shunday kiymatlar satrini olaylikki, bu satrda x ning kiymati yo, u ning kiymati ch, Z ning kiymati yo, ..., i ning kiymati yo bulsin. U vakgda
   

D. = x v u v ... v i = yo v ch v ... v yo = yo v ... v yo = yo.

Demak, R = A1 a A2 a ... a A„ n i n g kiymati xam yolgon buladi. Ammo, eoremaning shartiga asosan R ning kiymati aynan chindir. Natijada karama-karshilikka keldik. Demak, elementar dizʼyu nksiyalarning xar bir xadida birorta muloxaza uzi va u:;ining inkori bilan katnashishi shart.