7-mavzu. Mukammal kon`yunktiv va diz`yunktiv normal shakllar. Reja
Download 162.59 Kb. Pdf ko'rish
|
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
2 ,…,x
n elementar mulohazaning
....
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
2 ,…,x
n mulohazalarning har bittasi bir martagina qatnashgan bo`lsa, u x 1
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,
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: ). )( ( ; ; ); )( )( ( ;
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
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 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 B A C A D B D A B C
A D C D 1 1 1 0 0 0 1
1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0
1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 1 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
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'muriyatiga murojaat qiling