Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

to‘liq elementar kon’yunksiya (diz’yunksiya) deb ataladi.

2 - misol. Ushbu x x x , x x x x x va x x x x elementar kon’yunksiyalarning hech qaysi
1 2 3 1 2 3 2 3 1 5 3 2
biri x , x , x , x
1 2 3 4
elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya emas, lekin
ularning birinchisi x , x , x elementar mulohazalarga nisbatan, oxirgisi esa x , x , x , x elementar
1 2 3 1 2 3 5
mulohazalarga nisbatan to‘liq elementar kon’yunksiyadir.
Berilgan a  b  d  c elementar diz’yunksiya a, b, c, d elementar mulohazalarga nisbatan
1 4
1 3 4
3
mulohazalarga nisbatan to‘liq elementar diz’yunksiya bo‘lsada,
u x , x , x , x
1 2 3 4
to‘liq elementar diz’yunksiyadir, x  x  x elementar diz’yunksiya esa x , x , x elementar
elementar
mulohazalarga nisbatan to‘liq elementar diz’yunksiya bo‘la olmaydi. ■
3- 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.1
4- ta’ r i f . Berilgan x , x ,..., x
1 2 n
har bir
x 1
1 2 n
 x 2      x n had
elementar mulohazalarga nisbatan formulaning MKNShidagi
diz’yunktiv konstituyent, uning MDNShidagi har bir
x 1
1
 x 2  ...  x n had esa kon’yunktiv konstituyent deb ataladi.
2 n
4- ta’rifda yerda  (i  1, n) ch yoki yo qiymat qabul qiluvchi parametrni ifodalaydi va
i
x , x ,..., x o‘zgaruvchilar orasida bir xillari yo‘q.
1 2 n
1 “Mukammal kon’yunktiv normal shakl” iborasini, qisqacha, MKNSh, “mukammal diz’yunktiv normal shakl” iborasini esa, MDNSh deb yozamiz.