Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

 x, agar   ch bo' lsa,

Ravshanki,

x, agar   yo bo' lsa,
x
1 2 n
hamda faqat va faqat x   bo‘lgandagina x ch qiymat qabul qiladi.
1- ta’ rif. Berilgan elementar mulohazalar (o‘zgaruvchilar) yoki ularning inkorlari kon’yunksiyalaridan tashkil topgan formula shu o‘zgaruvchilar elementar kon’yunksiyasi, bu o‘zgaruvchilar yoki ularning inkorlari diz’yunksiyalaridan tashkil topgan formula esa shu o‘zgaruvchilar elementar diz’yunksiyasi deb ataladi.
Tabiiyki, elementar kon’yunksiya (elementar diz’yunksiya) tarkibida faqat bitta o‘zgaruvchi ishtirok etishi ham mumkin. Shu sababli, bitta (masalan, x ) o‘zgaruvchining o‘zi yoki uning inkoridan iborat x yoki x ko‘rinishdagi ifodalar elementar kon’yunksiya ham elementar diz’yunksiya ham bo‘la oladi.
Umuman olganda, berilgan n ta x , x ,..., x o‘zgaruvchilar elementar kon’yunksiyasi
x 1
 x 2  ...  x n
2 n
1
(3)
ko‘rinishdagi, bu o‘zgaruvchilar elementar diz’yunksiyasi esa
x 1
 x 2      x n
2 n
1
(4)
ko‘rinishdagi formuladir. Bu yerda  (i  1, n) ch yoki yo qiymat qabul qiluvchi qandaydir
i
parametrni ifodalaydi hamda x , x ,..., x o‘zgaruvchilar orasida bir xillari bo‘lishi ham mumkin.
1 2 n
2. Formulaning normal shakllari.
Formulaning normal shakllari quyidagi ta’rif asosida aniqlanadi.
2- 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.
“Kon’yunktiv normal shakl” iborasini, qisqacha, KNSh, “diz’yunktiv normal shakl” iborasini esa, DNSh deb yozamiz.
(3) formula DNShning kon’yunktiv hadi, (4) formula esa KNShning diz’yunktiv hadi deb ham
yuritiladi.
1- va 2- ta’riflarga ko‘ra, teng kuchli almashtirishlar bajarib, mantiq algebrasining ixtiyoriy formulasi uchun turli KNShlar va DNShlar topilishi mumkin.
1- misol. Distributivlik va idempotentlik qonunlariga asoslanib, x  y(x  z) formulaning
kon’yunktiv normal shakllari, masalan,
(x  y)(x  z) , (x  y  y)(x  z) va
(x  y)(x  z)(z  x) formulalar, (x  y)  (x  z) formula uchun esa diz’yunktiv normal shakllar, masalan, x  yz va x  xz  yz formulalar bo‘lishiga ishonch hosil qilish qiyin emas. ■