Diskret tuzilmalar fanidan

Bajardi: Mehriddinova S M

Qiymatlar jadvaliga ko’ra fikriy funksiyalarini tiklashda mukammal dizyunktiv va konyunktiv normal shakllar (MDNSH, MKNSH)

1- t a ’ r i f. Agar elementar kon’yunksiya (dizyunksiya) ifodasida ishtirok etuvchi har bir elementar mulohaza shu ifodada faqat bir marta uchrasa, u holda bu ifoda to‘g‘ri elementar kon’yunksiya (dizyunksiya) deb ataladi.

1 - m i s o l . Berilgan a  b  c va a  d  f elementar dizyunksiyalar to‘g‘ri elementar dizyunksiyalar, abdc va aecb elementar kon’yunksiyalar esa to‘g‘ri elementar kon’yunksiyalardir. Lekin, a  u  u  c va u  u  e  n elementar dizyunksiyalar ifodasida u elementar mulohaza bir martadan ortiq qatnashganligi sababli, ularning hech biri to‘g‘ri elementar dizyunksiya bo‘la olmaydi. elementar mulohaza va elementar kon’yunksiyalar tarkibida bir martadan ortiq qatnashganligi sababli, bu ifodalarning hech qaysisi to‘g‘ri elementar kon’yunksiya bo‘la olmaydi.

2- t a ’ r i f. Agar berilgan elementar mulohazalarning har biri elementar kon’yunksiya (dizyunksiya) ifodasida faqat bir matra qatnashsa, bu ifoda shu elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya (dizyunksiya) deb ataladi.

2 - m i s o l . Ushbu va elementar kon’yunksiyalarning hech qaysi biri elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya emas, lekin ularning birinchisi elementar mulohazalarga nisbatan, oxirgisi esa elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiyadir.

3- t a ’ r i f. Agar formulaning KNShi (DNShi) ifodasida bir xil elementar dizyunksiyalar (kon’yunksiyalar) bo‘lmasa va barcha elementar dizyunksiyalar (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.

3 - m i s o l . Tarkibida faqat bitta asosiy mantiqiy amal qatnashgan formulalarning mukammal normal sakllari (MKNShlari va MDNShlari) 1- jadvalda keltirilgan.
Yuqoridagi tasdiqning to‘g‘riligini tekshirish o‘quvchiga havola qilinadi. 1- jadvaldan ko‘rinib turubdiki, x formulaning MKNShi ham, MDNShi ham uning o‘zidan iborat; x  y formulaning MKNShida uchta ( x y , -x  y va x -y ) diz’yunktiv konstituyentlar bor, uning MDNShi esa bitta kon’yunktiv konstituyentdan (shu formulaning o‘zidan) iborat; va hokazo.

Misol.