Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh
Minimallashtirish masalasining geometrik tarzda qo‘yilishi
Yüklə 0,56 Mb.
|
- Bu səhifədəki naviqasiya:
- 3.1 - t a ’ r i f .
- - m i s o l .
3. Minimallashtirish masalasining geometrik tarzda qo‘yilishi3.1. Birlik kub va uning elementlariga mos keladigan funksiya. Hamma {1, 2 ,...,n} majmua to‘plamini E n bilan belgilaymiz. E n to‘plamni birlik kubning hamma uchlari to‘plami sifatida qarash mumkin. Shu sababli E n to‘plam n o‘lchovli kub, {1, 2 ,...,n} esa kub uchlari deb ataladi. n 3 o‘lchovli kub 3.1-shakldagidek tasvirlanishi mumkin. 3.1 - t a ’ r i f .i ,i ,...,i shunday 0 va 1 sonlardan iborat tayinlangan sonlar 1 2 r sistemasi bo‘lib, 1 i1 i2 ... ir n , uchun i i , i i ,..., i i bajarilganda 1 1 2 2 r r E n kubning uchlaridan tuzilgan to‘plam (n r) o‘lchovli yoq deb ataladi. Mantiq algebrasining f (x1 , x2 ,..., xn ) funksiyasi berilgan bo‘lsin. E n kubning f (1, 2 ,...,n ) 1 shartni qanoatlantiradigan barcha uchlaridan tashkil topgan to‘plamni N f bilan belgilaymiz, ya’ni f (1, 2 ,...,n ) 1 bajarilganda va faqat shunda (1,2 ,...,n ) N f , bo‘ladi. Masalan, 2-bo’limdagi 2.1-jadvalda berilgan f (x1, x2 , x3 ) funksiyaga Nf {(0,0,0), (0,0,1), (0,1,1), (1,0,0), (1,1,0), (1,1,1)} to‘plam mos keladi. Ravshanki, N En . Agar N to‘plam berilgan bo‘lsa, u holda unga mos f f f funksiyaning analitik ko‘rinishini yozish mumkin. - m i s o l . Quyidagi to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi topamiz: f N {(0, 0, 0),(1, 0, 0),(1, 0,1)}; 1 f N {(1,1,1),(1,1, 0),(1, 0,1),(0, 0,1)}. 2 Berilgan to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi 1 Яблонский С.В. Введение в дискретную математику. М.: Наука. 1979. 213- sahifaga qarang. quyidagicha bo‘ladi: f1 (x1, x2 , x3 ) x1 x2 x3 x1 x2 x3 x1 x2 x3 ; f2 (x1, x2 , x3 ) x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 . ■ Shunday qilib, N f to‘plam berilgan bo‘lsa, u holda unga mos f funksiyani, f (x1, x2 ,..., xn ) funksiya berilganda esa, N f to‘plamni topish mumkin. Dastlabki funksiya sifatida r rangli k(x , x ,..., x ) x1 x2 ... xr elementar kon’yunksiyani olaylik. 1 2 n i1 i2 ir - t a ’ r i f . K kon’yunksiyaga mos Nk ataladi. to‘plam r rangli interval deb O’z-o‘zidan ravshanki, r rangli N interval (n r) o‘lchovli yoqni ifodalaydi. - m i s o l .k1 (x1, x2 , x3 ) x2 x3 , k2 (x1, x2 , x3 ) x1 x2 , k3 (x1, x2 , x3 ) x1 kon’yunksiyalarga N {(1,1,1),(0,1,1)}, k 1 N {(0, 0, 0),(0, 0,1)}, k 2 k N {(0, 0, 0),(0,1, 0),(0, 0,1),(0,1,1)} intervallar mos keladi. Bu intervallar mos ravishda 3 2, 2 va 1 rangli, hamda va 1 o‘lchovli yoq (qirra), 1 o‘lchovli yoq (qirra) va 2 o‘lchovli yoqdir. ■ Agar f (x1, x2 ,..., xn ) g(x1, x2 ,..., xn ) h(x1, x2 ,..., xn ) bo‘lsa, u holda Ng N f , Nh N f ; N f bo‘ladi. Ng ∪ Nh Umuman olganda, agar f (x1, x2 ,..., xn ) D va D K1 K2 ... Ks bo‘lsa, u holda yuqoridagi xossalarga asosan N N k f i (i 1,2,..., s) va N N f k 1 ∪ N k 2 ∪... ∪ N , k s 1 2 s ya’ni f funksiyaga N f to‘plamning Nk , Nk , ... , Nk intervallardan iborat qobiq 1 2 s mos keladi va har bir Nk , Nk ,..., Nk intervallardan iborat N f to‘plamning qobig‘iga D diz’yunktiv normal shaklda ifodalangan f funksiya mos keladi. Demak, mantiq algebrasining har bir f (x1, x2 ,..., xn ) funksiyasiga bitta N f to‘plamning Nk ,Nk ,..., Nk intervallardan (Nk N f ) iborat qobig‘i va, aksincha, har 1 2 n j bir N f to‘plamning Nk ,Nk ,..., Nk intervallardan iborat qobig‘iga bitta f (x1, x2 ,..., xn ) 1 2 n funksiya mos keladi, ya’ni N f ning qobig‘i bilan f (x1, x2 ,..., xn ) funksiya o‘rtasida o‘zaro bir qiymatli moslik bor. - m i s o l . 2-bo’limdagi 2.1-jadval bilan berilgan f (x1 , x2 , x3 ) funksiya
uchun D1 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 , D2 x2 x3 x1 diz’yunktiv normal shakllar topilgan edi. Bu DNShlarga Nf {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)} to‘plamning quyidagi ikkita qoplamasi mos keladi: k k Nf Nk ∪ Nk ∪ Nk ∪ Nk ∪ Nk , N f N 1 ∪ N 2 , 1 2 3 4 5 0 0 bu yerda N {(0,0,0)}, k 1 N {(1,0,0)}, k 2 N {(1,0,1)}, k 3 N {(1,1,0)} , k 4 N {(1,1,1)}, k 5 k N 0 {(0,0,0), (1,0,0)}, 1 N 0 {(1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Birinchi qoplama beshta k 2 i nuqtadan, ikkinchisi esa qirra va ikki o‘lchovli yoqdan iborat. Nk intervalning rangi ri bo‘lsin (u Ki kon’yunksiyaning rangiga teng). U holda s r ri i 1 (4) qoplamaning rangi deb ataladi. 3.2. Mantiq algebrasi funksiyasini minimallashtirish muammosiga ekvivalent qoplamalar haqidagi geometrik masala. Mantiq algebrasi funksiyasi f (x1, x2 ,..., xn ) ni minimallashtirish (minimizasiyalash) muammosiga ekvivalent bo‘lgan qoplamalar haqidagi geometrik masala quyidagicha qo‘yiladi. Berilgan Nf Nk ∪ Nk ∪... ∪ Nk to‘plamning Nk , Nk ,..., Nk ( Nk N f , j 1,2,..., s ) 1 2 s 1 2 s j intervallardan iborat shunday qobig‘ini topish kerakki, uning r rangi eng kichik bo‘lsin, ya’ni qaralayotgan masala topish masalasiga keladi. s min r minri i 1 (5) Demak, mantiq algebrasi funksiyasini minimallashtirish masalasini ikki formada ko‘rish mumkin: birinchisi – analitik formada, ikkinchisi – geometrik formada. Shuning uchun adabiyotda ikki til ishlatiladi: analitik va geometrik. Ayrim hollarda ikki tilning kombinatsiyasidan foydalaniladi. Masalan, kon’yunksiyani interval va DNShni qoplama deb ataydilar. Yüklə 0,56 Mb. Dostları ilə paylaş:
|