7-mavzu. Mukammal kon`yunktiv va diz`yunktiv normal shakllar. Reja


Download 162.59 Kb.
Pdf ko'rish
Sana09.11.2020
Hajmi162.59 Kb.
#142778
Bog'liq
7-maruza


7-mavzu.Mukammal kon`yunktiv va diz`yunktiv normal shakllar. 

                                              Reja. 

                  1.Formulaning mukammal kon`yunktiv normal shakli. 

                  2.Formulaning mukammal diz`yunktiv normal shakli. 

                  3.Misollar. 

Tayanch 


iboralar:Formulaning 

mukammal 

kon`yunktiv 

normal 

shakli,                  

formulaning mukammal diz`yunktiv normal shakli. 

    


       Mantiq    algebrasining  bitta  formulasi    uchun  bir  nechta    DNSH  (KNSH) 

mavjud    bo`liushi    mumkin.Masalan,  (x

y)(x


z)  formulani  quyidagi  x

yz, 


x

xy



xz DNSH larga keltirish  mumkin.Bular distributivlik  va idempotentlik 

qonunlarini    qo`llash    natijasida  hosilqilingan.Formulalarni    bir    qiymatli  

normal  shaklda  tasvirlash  uchun  mukammal  diz`yuktiv  normal  shakl  va 

mukammal  kon`yunktiv  normal  shakl    (MDNSH  va  MKNSH)  deb  ataluvchi  

ko`rinishlalga ishlatiladi.  

 n ta x

1

,x



2

,…,x


n

 elementar  mulohazaning  

                              

n

n

x

x

x





....


2

1

2



1

    (1)  

Elementar diz`yunksiyalari va  

                                 



n

n

x

x

x



....


2

1

2



1



    ( 2) 

Elementar kon`yunksiyalari berilgan bo`lsin. 

1-ta`rif. (1) elementar diz`yunksiya ((2) elementar kon`yunksiya ) ifodasida har bir 

elementar    mulohaza  x

i

  bir  marta  qatnashgan  bo`lsa,  u  to`g`ri  elementar 



diz`yunksiya (to`g`ri elementar kon`yuksiya) deb ataladi. 

2-  ta`rif.    (1)  elementar  diz`yunksiya  ((2)  elementar  kon`yunksiya  )  ifodasida  

x

1

,x



2

,…,x


n

  mulohazalarning  har  bittasi  bir    martagina  qatnashgan  bo`lsa,  u 

x

1

,x



2

,…,x


n

 mulohazalarga nisbatan to`liq elementar diz`yunksiya (to`liq elementar 

kon`yuksiya) deb ataladi. 

3-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  MDNSH  (MKNSH)  deb 

ataladi.Masalan, 

z

y

x

yz

x

z

xy

xyz



  DNSH x,y,z larga nisbatan MDNSH bo`ladi. 

)

)(

)(



(

y

x

y

x

y

x



 KNSH mulohazalarga  nisbatan MKNSH bo`ladi. 

Asosiy    mantiqiy  amallarning  MDNSH  va  MKNSH  ko`rinishlari  quyidagicha  

bo`ladi: 

a)  MDNSH: 

;

;



;

ˆ

;



,

y

x

xy

y

x

y

x

y

x

xy

y

x

y

x

y

x

xy

y

x

xy

xy

x

x









  



b)  MKNSH: 

).

)(



(

;

;



);

)(

)(



(

;

y



x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

xy

x

x











 

1-teorema.n ta  elementar mulohazaning aynan chin formulasidan farqli har bir A 



formulani  MKNSH ga keltirish  mumkin. 

Isboti.Tavtalogiyadan  farq  qiluvchi  har  qanday  A  formulani  MDNSH  ga 

keltiruvchi algoritm mavjud u quyidagidan iborat: 

1.Avvalo  A  formulani  kon`yunktiv  normal  shaklga  keltiramiz.  Buning  uchun  A 

formulani  kon`yuksiya,  diz`yunksiya  va  inkor    amallari    orqali  ifodalaymiz(inkor 

amali  faqat  o`zgaruvchini  ustida  bo`lishi  kerak).  So`ngra  distributivlik  qonunidan 



foydalanib  ,  A  formulani  KNSHga    keltiramiz  va  hamma  lozim  bo`lgan 

soddalashtirishlarni bajaramiz. 

2.Agar KNSH ifodasida bir nechta bir xil elementar diz`yunksiyalar mavjud bo`lsa 

,  u  holda  x

x  =  x    teng  kuchlilik  formulasidan  foydalanib,  ulardan  bittasini  A 



formulada qoldiramiz. 

3.Quyidagi  ikki  usul  orqali  hamma  elementar  diz`yunksiyalarni  to`g`ri  elementar 

diz`yunksiyalarga aylantiramiz:

 

a) agar biror elementar diz`yunksiya ifodasida birorta o`zgaruvchi o`zining inkori 



bilan qatnashgan bo`lsa, u holda                                    

x

x

x

ch

x

ch

ch

x

x





,

,



    

Teng  kuchli  formulalarga  asosan  biz  bu  elementar  konyunksiyani  KNSH  ga  olib 

kelamiz; 

b)agar  biror  o`zgaruvchi  elementar  diz`yunksiya  ifodasida  bir  necha  marta 

qatnashgan  bo`lsa  u  holda   

x

x

x



              formulaga  asosan  biz  ulardan  faqatgina 

bittasini KNSH ifodasiga  qoldiramiz  

Natijada  hamma  elementar  diz`yunksiyalar    to`g`ri  elementar    diz`yunksiyalarga 

aylanadi. 

4.Agar ba`zi elementar diz`yunksiyalar to`liq elementar diz`yunksiyalar bo`lmasa, 

ya`ni  diz`yunktiv hadlarda  elementar  mulohazalarning    ba`zilari    yoki    yo`qlainig 

inkorlari  qatnashmasa,  u  holda  bunday  elementar  diz`yunksiyalarni  to`liq 

elementar diz`yunksiya ko`rinishiga olb kelish kerak. 

Agarda elementar diz`yunksiya ifodasida bir nechta y

1

,y



2,….

y

m



 lar qatnashmayotgan 

bo`lsa, u holda uning ifodasiga  

)

(

i



i

y

y

  (i  =1,2,…m)    kon`yuksiyalarni  mantiqiy  qo`shib,  distributivlik  qonunini 



qo`llaymiz Natijada, bitta to`liq bo`lmagan elementar diz`yunksiya o`rniga  2m ta 

to`liq elementar diz`yunksiyaga ega bo`lamiz. 

5.To`rtinchi  qadam  bajarilishi  natijasida  KNSH  ifodasida  bir  xil  elementar 

diz`yunksiyalar paydo bo`ladi.Shu sababli yana 2- qadamni ishlatamiz. 

Demak, 1-5 qadamlar natijasida KNSH ifodasida bir xil elementar diz`yunksiyalar  

mavjud  bo`lmaydi  va    hamma  elementar  diz`yunksiyalar  to`g`ri  va  to`liq 

bo`ladi.Ta`rifga  asosan, bunday KNSH  MKNSH bo`ladi. 

n ta mulohazali MKNSH 

                             

)

...



(

1

1



2

1

1



n

x

x

x



     



ifodasida 

o`rniga 



  ni  aksincha  ,

  o`rniga 



  ni  qo`yganimizda  biz  n  ta  

mulohazali  

                         

)

...


(

1

1



2

1

1



n

x

x

x



 



MDNSH ega bo`lamiz. 

MDNSH ning  har bir  

                 

)

...



(

1

1



2

1

1



n

x

x

x



 

hadi  kon`yuktiv konstituent  deb ataladi. 



2-teorema. n ta elementar mulohazalarning aynan yolg`on formulasidan farqli har 

bir A formulasini MDNSH ga keltirish mumkin.    

               Formulalarning asosiy xossalari. 


Ma`lumki,  berilgan  formula  uchun  chinlik  jadvali  tuzish  mumkin.Formulaning 

chinlik jadvalini tuzishni bilamiz. Endi teskari  masala bilan shug`ullanaylik, ya`ni 

berilgan  chinlik  jadvali  bo`yicha  firmulani  topishni  maqsad  qilib  qo`yaylik, 

Masalan, x va y elementar mulohazalarning quyidagi chinlik jadvaliga ega bo`lgan 

A , B, C , D  formulalarni topaylik: 

 

X  Y  A  B  C  D  A



A



A



B



A



B



C

 

A



D



C



1  1 



0  1 




1  0 





0  1 





0  1 



0  0 




0  0 





1  0 





 

Bundan keyin biror mulohazaning ‘chin” qiymatini “1” , “yolg`on” qiymatini “0” 

deb belgilaymiz. Ma`lumki, 

 

.



,

,

,



y

x

D

y

x

C

y

x

B

y

x

A







                               (1) 

(1) 


formulalarning  har  qaysisi  uchun  jadvalning  ,  mos  ravishda  ,1,2,3,4- 

satrlarida “1” qiymat qolgan satrlarida “0” qiymat turibdi.(1) formulalar 

ikki mulohazali kon`yunktiv constituentlardan iborat. 

 Endi shunday formulalarni topaylikki, ular uchun jadvalning ikki satrida “ 1 “ 

qiymat  va  ikki  satrida  “0”  qiymat  turgan  bo`lsin.  Bu  talablarga    quyidagi 

formulalar javob beradi: 

A



B:  A



C;   A


D;  B


D   va h.k. 

Shunday  qilib,  ushbu  qioda  o`rinli:  2  va  4-satrlarda  “1”,  1  va  3-satrlarda  “0” 

qiymatga  ega  bo`lgan  formulani  hosil  qilish  uchun,bittasining  “1”  qiymati 

xuddi  2-satrda  va  ikkinchisining    “1”  qiymati  xuddi  4-satrda  turgan  ikki 

kon`yunktiv constituent diz`yunksiyasini olamiz: 

              B 

 D. 



Xuddi shu kabi , jadvaldagi uchta kon`yunktiv constituent diz`yunksiyasi uchta 

satrda “1” qiymatga ega bo`lgan formulani tasvirlaydi.Masalan, 

                A

B



C. 


Shuday  qilib,  to`rtala  A,B,C,D  lar  diz`yunksiyasi  to`rtala  satrda  ham  ”1” 

qiymatga ega bo`lgan, ya`ni aynan chin: 

 

)

(



)

(

)



(

)

(



y

x

y

x

y

x

y

x

D

C

B

A

E









 

Bu formula ikki mulohazali to`liq MDNSH iborat. 



U holda E ning inkori MKNSH iborat: 

)

(



)

(

)



(

)

(



y

x

y

x

y

x

y

x

D

C

B

A

E









Demak,  ikki  x  va  y  elementar  mulohazalar    uchun  chinlik  jadvaliga  qarab 



ularga  mos formulalarni tiklash  mumkin. 

                      Savollar va topshiriqlar. 

          1.Formulaning mukammal kon`yunktiv normal shakliga misol keltiting. 

          2.Formulaning mukammal diz`yunktiv normal shakliga misol keltiring. 



          3.Chinlik  jadvaliga  qarab  formulani  normal  ko`rinishga  keltirishga  misol 

keltiring. 



 

Download 162.59 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling