Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh
Joiz (ruxsat etilgan) kon’yunksiyalar
Yüklə 0,56 Mb.
|
- Bu səhifədəki naviqasiya:
- Joiz kon’yunksiyalarni topish.
- Qisqartirilgan diz’yunktiv normal shakl
- - m i s o l .
Joiz (ruxsat etilgan) kon’yunksiyalarJoiz kon’yunksiya tushunchasi. Ma’lumki, x1 , x2 ,..., xn o‘zgaruvchilardan 3n ta elementar kon’yunksiya va 23n ta diz’yunktiv normal shakl tuzish mumkin. Masalan, n 3 bo‘lsa, ya’ni x1 , x2 , x3 o‘zgaruvchilardan 1, x1 , x2 , x3 x1 , x2 , x3 , x1x2 , x1 x3 , x2 x3 , x1 x2 , x1x2 , x1 x3 , x1 x3 x2 x3 , x2 x3 , x1 x2 , x1 x3 , x2 x3 , x1 x2 x3 , x1 x2 x3 , (1) x1 x2 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 x3 elementar kon’yunksiya tuzish mumkin. Ammo, bu elementar kon’yunksiyalarning hammasi ham berilgan ixtiyoriy f (x1 , x2 , x3 ) funksiyani realizasiya qiladigan diz’yunktiv normal shakllarning ifodasida ishtirok etavermaydi. Shuning uchun “ 3n ta kon’yunksiyalarning qaysilari f (x1, x2 ,..., xn ) funksiyaning DNShda ishtirok qiladi?” degan masalani yechishga to‘g‘ri keladi. Buning uchun, birinchi navbatda, En \ N f to‘plamning elementlarida 1 qiymat qabul qiladigan kon’yunksiyalarni topish kerak bo‘ladi. Masalan, bo‘lsin. U holda f1(x,y,z) x yz xyz xyz xyz xyz xyz f N {(0,0,0), (0,1,1), (0,1,0), (1,0,1), (1,1,0), (1,1,1)} 1 (2)
(3) bo‘ladi. Demak, 4.1-jadvalga ega bo‘lamiz.
Ikkinchi navbatda, (1) kon’yunksiyalar orasidan 4.1-jadvaldagi kon’yunksiyalarni chetlashtiramiz, chunki f (x, y, z) funksiyaga N f ((3)ga qarang) 1 to‘plam mos kelgani uchun 4.1-jadvaldagi kon’yunksiyalar (2) funksiyani realizasiya qiladigan diz’yunktiv normal shakllar ifodasida umuman qatnashmaydi. Bu operatsiya natijasida f1(x, y, z) funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi mumkin bo‘lgan (qatnashishga ruxsat etilgan, qatnashishga joiz) kon’yunksiyalarga ega bo‘lamiz: x , y , xy , xz , xy , xz , yz , xy , yz , xyz , xyz , (4) xyz , xyz , xyz , xy z . Shunday qilib, 33 27 kon’yunksiyadan 15tasining berilgan f (x, y, z) funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi joiz ekan. 4.1 - t a ’ r i f . Ixtiyoriy f (x1, x2 ,..., xn ) funksiya va unga mos Nf to‘plam berilgan bo‘lsin. f (x1, x2 ,..., xn ) funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi mumkin bo‘lgan kon’yunksiyalar, ya’ni En \ N f to‘plamning nuqtalarida 1 qiymatga ega bo‘lgan kon’yunksiyalardan tashqari qolgan hamma kon’yunksiyalar joiz kon’yunksiyalar deb ataladi. Masalan, (4) dagi hamma kon’yunksiyalar joiz kon’yunksiyalar bo‘ladi. Joiz kon’yunksiyalarni topish.M i s o l . Berilgan va unga mos to‘plam berilgan bo‘lsin. f2 (x1, x2 , x3 ) x1 x2 x3 x1 x2 x3 x1 x2 x3 x1x2 x3 x1x2 x3 x1x2 x3 f N {(0,0,0), (0,0,1), (1,0,1), (1,1,1), (1,1,0), (0,1,0)} 2 (6) (5)
Joiz kon’yunksiyalarni topish uchun 2-jadvalni tuzamiz.
U holda (1) dagi kon’yunksiyalardan 4.2-jadvaldagi kon’yunksiyalarni chetlashtirish natijasida quyidagi joiz kon’yunksiyalarga ega bo‘lamiz: x1x2 , x1 x3 , x2 x3 , x2 x3 , x1 x2 , x1 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 x3 , (7) x1 x2 x3 , x1 x2 x3 , x1 x2 x3 . ■ n O’zgaruvchilar soni n ta bo‘lganda, 3n ta kon’yunksiya va ulardan 23 ta f (x1, x2 ,..., xn ) funksiyani realizasiya qilishi mumkin bo‘lgan DNSh tuzish mumkinligini aytgan edik. Demak, berilgan ixtiyoriy f (x1, x2 ,..., xn ) funksiyani realizasiya qiladigan tupikli (minimal) DNShlarni 23n ta DNShlar orasidan izlamasdan, balki 2 DNShlar ichidan izlash kerak degan natijaga keldik, bu yerda – joiz kon’yunksiyalar soni. Qisqartirilgan diz’yunktiv normal shakl1 . Maksimal interval va oddiy implikant tushunchalari. - t a ’ r i f . Agar N f to‘plamning qism to‘plami bo‘lgan Nk interval uchun: Nk N N ; k f 1 N 1 intervalning rangi N intervalning rangidan kichik k k shartlarni qanoatlantiruvchi N 1 interval mavjud bo‘lmasa, u holda N ( N ga k k f nisbatan) maksimal interval deb ataladi. - m i s o l .k1(x1, x2 , x3 ) x1x2 , k 2(x1, x2 , x3 ) x1 x2 , k 3(x1, x2 , x3 ) x2 bo‘lsin. U 2 3 holda Nk , Nk maksimal intervallar bo‘lib, Nk interval esa N f ning maksimal 1 intervali bo‘lmaydi, chunki N N k k 1 3 va Nk ning rangi Nk ning rangidan kichik. ■ 3 1 - m i s o l . 4-bo’limdagi (4) joiz kon’yunksiyalarga mos kelgan 15ta 1 intervaldan faqat Nx va Nx intervallar va o‘sha bo’lim, (7) dagi 12ta intervaldan 1 2 1 3 2 faqat Nx x , Nx x , N , N , x x x x 2 3 2 3 N , N x x x x 1 2 1 3 , intervallargina mos ravishda N f va N f 1 2 to‘plamlarga nisbatan maksimal intervallar bo‘ladi. ■ Yüklə 0,56 Mb. Dostları ilə paylaş:
| ||||||||||||||||