1. Konyuktiv normal shakl.(Knsh) Mukammal kon’yuktiv normal shakl(MKnsh)

REJA:
1.Konyuktiv normal shakl.(KNSH)
2.Mukammal kon’yuktiv normal shakl(MKNSH)
3.Mukammal kon’nyuktiv normal shaklga doir misollar

KON’YUNKTIV NORMAL SHAKL (KNSH)

Teng kuchli almashtirishlar bajarib, mulohazalar algebrasining formulalarini har xil ko’rinishlarda yozish mumkin.Masalan,
A’ BC formulani A V BC yoki (A V B)(A V C) ko’rinishida yoza olamiz.
Mantiq algebrasining kontakt va rele-kontakli sxemalar, diskret texnikadagi tatbiqlarda va matematik mantiqning boshqa masalarida formulalarning normal shakllariga katta ahamiyatga ega.
1-TA’RIF. Ushbu
X1*x2*..........xn
ko’rinishidagi formula elementar kon’yuksiya deyiladi
2-TA’RIF.
Elementar diz’yunksiyalarning kon’yuinksiyasi formulaning konyuktiv normal shakli (KNSH) va elementar kon’yuksiyalarning dizyunksiyasi formulararning dizyunktiv normal shakli (DNSH) deb ataladi.
KNSH ga (x v y)^(x’ v z)^(x v y’ v z) formula va DNSH ga xy v x’z v xy’z formulalar misol bo’la oladi.
1-TEOREMA. Elementar mulohazalarning har bir P formulasiga teng kuchli kon’yuktiv normal shakldagi Q formula mavjud.
Bu teoremani isbotlashda quyidagi teng kuchli formulalardan foydalanamiz:
1)(A ^B)’=A’ V B’ ;

2)(A V B)’=A’ ^ B’; 3)(A B)=A’ V B ;
2- TEOREMA.P formula doimo chin bo’lishi uchun uning KNSH dagi har bir elementar diz’yunktiv xadida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo’lishi zarur va yetarli.
ISBOT: a) P formulaning
P=A1 ^ A2 ^…..^An
KNSH dagi har bir A1 hadida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo’lsin,ya’ni A1=x v x’ vy v……..v u shaklda bo’lsin, u holda x v x’=J va J v A=J larga asosan A1=J v(y v ….v u v V)=J bo’ladi.Demak, P= J ^ J^ …^J=J bo’ladi, ya’ni aynan chin formula bo’ladi.
b) Endi P taftalogiya bo’lsin va A1 uning KNSH dagi shunday elementar mulohaza bilan birga uning inkori qatnashmagan bo’lsin. Masalan,A1=x v y’ v….v u shaklda bo’lsin. Endi,elementar mulohazalarning shunday qiymatlar satrini olaylikki, bu satrda x ning qiymati g, u ning qiymati ch , z ning qiymati g, …, u ning qiymati g bo’lsin. U vaqtda
A1=x v y’ v….v u=g v ch v… v g= g v …v g=g
Demak, P=A1 ^A2^…^An ning qiymati ham yolg’on bo’ladi .Ammo, teoremaning shartiga asosan P ning qiymati aynan chindir.Natijada qarama-qarshikka keldik.Demak, elementar diz’yunksiyalarning har bir xadida birorta mulohaza o’zi va o’zining inkori bilan qatnashishi shart.
MISOL;

1. 
   P=x ^ x’ (y ^y’)’=(x ^x’)’ v (y ^ y’)’=x’ v x v y y’.
   

P=x’ v x y v y’ -- aynan chindir.

2.(x ^ x’)’ ^ (y ^ y’ z)=(x’ v x)^ (y’ v y) v z= P(x’ v x) ^ (y’ v y v z)—
Aynan chin formuladir.
Berilgan formulani doimo KNSH ga keltirib bo’ladi.Agar u KNSH shaklda bo’lmasa.
MUKAMMAL KON’YUKTIV NORMAL SHAKL(MKNSH)
Mantiq algebrasining bitta formulasi uchun bir nechta DNSH (KNSH) mavjud bo’lishi mumkin.Masalan,(x vy) (x v y)formulani quyidagi x v yz, x v xy v xz DNSH larga keltirish mumkin.Bular distributivlik va idempotentlik qonunlarini qo’lash natijasida hosil qilinadigan.
Formulalarni bir qiymatli ravishda normal shaklda tasvirlash uchun mukammal diz’yuntiv normal shakl va mukammal kon’yunktiv normal shakl (MDNSH va MKNSH ) deb ataluvchi ko’rinishlari ishlatiladi.
n ta x1, x2,…..,xn elementar mulohazalarning
x1 ^ x2 ^…. ^ xn
elementar kon’yunksiyalari berilgan bo’lsin.
TA’RIF
Elementar kon’yunksiyaning ifodasida x1,x2,….,xn mulohazalarning
har bittasi birmartagina qatnashgan bo’lsa,u x1, x2 ,……xn
mulohazalarga nisbatan to’liq elementar kon’yunksiya deyiladi.
C

ZZZZZZZZ

TA’RIF
Elementar kon’yunksiya ifodasida har bir elementar mulohaza x1 bir marta qatnashgan bo’lsa, u to’g’ri elementar kon’yunksiya deyiladi.
TA’Rif
Agar DNSH (KNSH) ifodasida bir xil elementar kon’yunksiyalar (elementar diz’yunksiyalar) bo’lmasa va hamma elementar kon’yunksiyalar (elementar diz’yunksiyalar) to’g’ri va to’liq bo’lsa, u mukammal diz’yunktiv normal shakl (mukammal kon’yunktiv normal shakl ) MDNSH (MKNSH) deb ataladi
Masalan;
Xyz v xyz’ v x’yz v xy’z DNSH x, y ,z mulohazalarga nisbatan MDNSH bo’ladi.
(x v y)(x v y’)(x’ v y) KNSH mulohazalarga nisbatan MKNSH bo’ladi.