MAVZU: Funksional yopiq sinflar. Post teoremasi. Reja: 1.Funksiyalar sistemasining to’liqligi. 2.Funksional yopiq sinflar. Post teoremasi. Funksional yopiq sinflar. Mantiq algebrasining sistemasi berilgan bo‘lsin. F= {j1,...,jn}funksiyalar t a ’ r i f . Agar mantiq algebrasining istalgan funksiyasini F = {j1,...,jn} sistemadagi funksiyalar superpozitsiyasi orqali ifodalash mumkin bo‘lsa, u holda F sistema to‘liq funksiyalar sistemasi deb ataladi. t a ’ r i f . Mantiq algebrasining superpozitsiyaga nisbatan yopiq bo‘lgan har qanday funksiyalar sistemasi funksional yopiq sinf deb ataladi.t a ’ r i f . O‘z-o‘zidan va mantiq algebrasining hamma funksiyalari sinfidan ( P2 dan) farq qiluvchi funksional yopiq sinflargakirmaydigan xususiy funksional yopiq sinf maksimal funksional yopiq sinf deb ataladi.Mantiq algebrasida hammasi bo‘lib beshta maksimal funksional yopiq sinf mavjud. Bular quyidagilardir: P0 , P1,M ,S,L . Post teoremasi. E. L. Post tomonidan funksiyalar sistemasi to‘liqligining yetarli va zarur shartlari topilgan. P o s t t e o r e m a s i . F= {j1,...,jn} funksiyalar sistemasi to‘liq bo‘lishi uchun bu sistemada P0,P1,M ,S,L maksimal funksional yopiq sinflarning har biriga kirmaydigan kamida bitta funksiya mavjud bo‘lishi Ikki taraflama funksiya.t a ’ r i f . Quyidagicha aniqlangan f *(x ,x ,..., x ) =f (x , x ,..., x ) 1 2 n 1 2 n 1- jadvalBerilgan funksiyaIkki taraflama funksiyaf1(x) = xf *(x) = x 1 f2 (x) = xf *(x) = x 2 f3 (x, y) = xyf * = x Ú y 3 f4 (x, y) = x Ú yf * = x y 4 f5 (x, y) = x ® y f * = y ® x 5 f6 (x, y) = x « y f * = x « y 6 f7 = 1f * = 0 7 f8 = 0f * = 1 8 funksiyaga f (x1, x2 ,..., xn ) funksiyaning ikki taraflama funksiyasi deb aytiladi. t a ’ r i f . Agar f (x ,x ,..., x ) =f *(x ,x ,..., x ) = f (x , x ,..., x ) 1 2 n 1 2 n 1 2 n munosabat bajarilsa, u holda ataladi. Jegalkin ko‘phadi. f (x1, x2 ,..., xn ) o‘z-o‘ziga ikki taraflama funksiya deb t a ’ r i f . å xi1 xi2 ...xik + a ko‘rinishdagi ko‘phad Jegalkin ko‘phadi deb iataladi, bu yerda hamma x o‘zgaruvchilar birinchi darajada qatnashadi, j (i1,...,ik ) qiymatlarsatrida hamma i j lar har xil bo‘ladi, a ÎE2 ={0, 1}. t a ’ r i f .ataladi. x +x i i1 2 + ... +x +a ik ko‘rinishdagi funksiya chiziqli funksiya deb Mantiq algebrasidagi monoton funksiyalar.Tartiblash. 0<1 munosabati orqali {0,1} to‘plamini tartiblashtiramiz. a =(a1,...,an ) va b =(b1,..., bn ) qiymatlar satrlari bo‘lsin. t a ’ r i f . Agar ai £ bi tengsizlik hech bo‘lmaganda bitta i uchun bajarilsa yoki ava bqiymatlar satrlari ustma-ust tushsa, u holda aqiymatlar satri b qiymatlarsatridan oldinkeladi deb aytamiz va a b shaklda yozamiz. t a ’ r i f . Agar a  b munosabatdan f (a1,...,an ) £f (b1,..., bn ) tengsizlikning bajarilishi kelib chiqsa, u holda ataladi. f (x1,..., xn ) funksiya monoton funksiya deb t a ’ r i f Agar a  b munosabatdan f (a1,...,an ) >f (b1,..., bn ) tengsizlikning bajarilishi kelib chiqsa, u holda f (x1,..., xn ) nomonoton funksiya deb ataladi. t e o r e m a . Monoton funksiyalarning superpozitsiyasidan hosil qilingan funksiya ham monoton funksiya bo‘ladi. t e o r e m a . Agar f (x1,..., xn ) ÎM bo‘lsa, u holda undan argumentlari o‘rniga 0, 1 va x funksiyani qo‘yish usuli bilan x funksiyani hosil qilish mumkin. 4 - t a ’ r i f . Agar f (x1, x2 ,..., xn ) funksiya uchun f (0,0,...,0) º 0 bo’lsa, u holda u 0 saqlovchi funksiya, ataladi. f (1,1,...,1) º 1 bo’lganda esa 1 saqlovchi funksiya deb Post jadvali P0P1SLMj1 j 2 ..................jn Amalda berilgan F = {j1,...,jn} funksiyalar sistemasining to‘liq yoki to‘liq emasligini aniqlash uchun Post jadvali deb ataluvchi jadvaldan foydalaniladi. Post jadvali quyida keltirilgan. Jadvalning xonalariga o‘sha satrdagi funksiya funksional yopiq sinflarning elementi bo‘lsa “+” ishora, bo‘lmasa “–” ishorasi qo‘yiladi. F= {j1,...,jn} sistema to‘liq funksiyalar sistemasi bo‘lishi uchun, Post teoremasiga asosan, jadvalning har bir ustunida kamida bitta “–” ishorasi bo‘lishi yetarli va zarur. Demak, Post teoremasi shartidan P0,P1,M ,S,L maksimal funksional yopiq sinflarning birortasini ham olib tashlash mumkin emas. Bu xulosadan, o‘z navbatida, P0,P1,M ,S,L maksimal funksional yopiq sinflarning birortasi ham boshqasining qism to‘plami bo‘la olmasligi kelib chiqadi. XULOSA 1.Funksiyalar sistemasining to’liqligi tushunchasi maliy jihatdan muhim ahamiyatga ega ekanligi ko’rsatildi. 2.Funksional yopiq sinflarnig ta’rifiga ko’ra, 0 va 1 saqlovchi hamda monoton, o’z-o’ziga qo’shma, chiziqli funksiyalar xususiyati o’rganildi; 3.Post teoremasi natijalarini amaliy tadbiqi o’rganildi. Quyida berilgan funksiyalar sinfining to’liqligini Post jadvali yordamida tekshiring;F ={((x1 ® x2 ) Å (x2 ® x3 )) « (x2 ® x3 ); (x2 ® x1 ) × (x2 ¯ x2 ); ((x1 Ú x2 × x3 ) ® (x2 ® x1 × x3 )) « (x1 Ú x3 )}; Berilgan funksiyalar sinfining to’liqligini Post jadvali yordamidatekshirish uchun quyidagi ketma-ketlikdagi ishlarni amalga oshiramiz: 1-ish. Berilgan formulada qatnashayotgan o’zgaruvchilar sonini aniqlab, jadvalning o’zgaruvchilar ustunini to’ldiramiz. Berilgan formulada uchta o`zgaruvchi qatnashgan, ya’ni x , y va z o`zgaruvchilar. Demak N=2n formula orqali o`zgaruvchilarning nechta qiymat qabul qilishini topamiz. Berilgan formulada uchta o`zgaruvchi qatnashganligi uchun o`zgaruvchilarning har biri 8 tadan qiymat qabul qiladi. Buni quydagi jadvalda o`zgaruvchilarning va ularning inkorlarini qiymatlarini keltiramiz. (1-jadval). 1.1-ish. Quyidagi formulani chinlik jadvalini yuqoridagi ta’riflardan foydalanib tuzamiz: 1.2-ish. F ={((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ); ((x1 ®x2 ) Å (x2 ® x3 )) « (x2 ®x3 ) ning qiymatini topamiz: (1-jadval) 1-jadval a =x1 ®x2 ; b =x2 ® x3 ; c =x2 ®x3 ; deb belgilash kiritib olamiz. x1x2x3 x2 x3 x1 ® x2 x2 ® x3 x2 ® x3a Å b(a Å b) « c 00011111000011011100010011100101100101111001111100101101110011001010101110000100 Xulosa: Ushbu ((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ) formulaning chinlik jadvali {00110000}. 2-ish . Endi quyidagi formulani chinlik jadvalini yuqoridagi ta’riflardan foydalanib tuzamiz: (x2 ®x1 ) × (x2 ¯ x2 ); 2.1-ish. (x2 ® x1 ) × (x2 ¯ x2 ); ning qiymatini topamiz: (2-jadval) 2-jadval x1x2x2 ® x1x2 ¯ x2(x2 ® x1 ) × (x2 ¯ x2 )00111010001011111100 Xulosa: Ushbu(x2 ®x1 ) × (x2 ¯ x2 ); formulaning chinlik jadvali f={1010}. 3-ish . Endi quyidagi formulani chinlik jadvalini yuqoridagi ta’riflardan foydalanib tuzamiz: ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); 3.1-ish. ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); ning qiymatini topamiz.(3-jadval) a = x1 Ú x2 × x3 ; b = x2 ® x1 × x3; 3-jadvalc= x1 Úx3 ; deb belgilash kiritib oldim. Xulosa: Ushbu ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); formulaning chinlik jadvali f={01111101}. Kiyingi qiladigan ishim 3 ta funksiyani ham Post jadvaliga tekshiramiz. ish. Formulalarni P0yopiq sinfga tegishli yoki tegishli emasligi tekshiramiz. 1) f1 (x, y, z) = ((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ) f1(0,0,0) = ((0 ®1) Å (0 ®1)) « (0 ® 0) = 0 ekan. demak f1formula P0 yopiq sinfga tegishli 2) f1 (x, y, z) = (x2 ® x1 ) ×(x2 ¯x2 ); f2(0,0,0) = (0 ®0)(0 ¯ 0) =1 demak f2formula P0yopiq sinfga tegishli emas ekan. 3) f3 (x, y, z) = ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); f3(0,0,0) = ((0 Ú 0 ×1) ® (0 ® 0 × 0)) « (0 Ú 0) = 0 tegishli ekan. demak f3formula P0 yopiqsinfga ish. Formulalarni P1yopiq sinfga tegishli yoki tegishli emasligi tekshiramiz. 1) f1 (x, y, z) = ((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ) f1(1,1,1) = ((1 ® 0) Å (1 ® demak f1formula P1yopiq sinfga tegishli emas ekan. 2)f1(x, y, z) =(x2 ®x1 ) × (x2 ¯ x2 ); demak x1x2x3x3x2 x3ax1x3ba ® bc(a ® b) « c0001000110000100001111010111000010110001111110010101111101001011111101110001011100111111 f2 formula P1yopiq sinfga tegishli emas ekan.f2(1,1,1) = (1®1)(1¯ 1) = 3) f3 (x, y, z) = ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); f3(1,1,1) = ((1Ú1× 0) ® (1 ®1×1)) « (1Ú1) = 1demak ekan. f3formula P1 yopiq sinfga tegishli ish. o‘z-o‘ziga ikki taraflama funksiyalar sinfi; 1) F =((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ); a =x1 ®x2 ; b =x2 ® x3 ; c =x2 ® x3 ; deb belgilash kiritib olamiz. x1x2x3 x1 x2 x3 x1 ® x2 x2 ® x3 a Å b x2 ® x3 (a Å b) « cF *000111000101001110011001010101110101011100110101100011101110101010110010110001110101111000110101 Demak: F*¹ F funksiya o’z-o’ziga ikki taraflama emas ekan. 2) F *= (x ® x )(x ¯x ); 2 1 2 2 x1 x2 x2 ® x1 x2 ¯ x2 F *11101101100100100110 Demak: F*= F funksiya o’z-o’ziga ikki taraflama ekan. 3) F*= ((x Ú x ×x ) ® (x ®x x )) « (x Úx ); 1 2 3 2 1 3 1 3 a =x1 Úx2 ×x3 ; ; b= x2 ® x1 x3 ; c =x1 Ú x3 ; debbelgilash kiritib oldim. Demak: F*¹ F funksiya o’z-o’ziga ikki taraflama emas ekan. ish. Formulalarni chiziqli yoki chiziqli emasligiga tekshiramiz. Buning uchun x1x2x3 x1 x2 x3 x2 x3 a x1 x3 bca ® b(a ® b) « cF *0001110111111000111011001001010101011111100111000101111010001100001101101010110000011100010001110111100000010101chinlik jadvalidagi oxirgi natijalardan foydalanamiz. 1) f1 (x, y, z) = ((x1 ® x2 ) Å(x2 ®x3 )) « (x2 ® x3 ) L1 = a0 xyz + a1xy + a2 xz + a3 yz + a4 x + a5 y + a6 z + b; f (0,0,0) = 0 = a0 000 + a1 00 + a2 00 + a3 0 + a4 0 + a5 0 + a6 0 + b, demak b = 0 f (0,0,1)= 0 =a61+0 demak a6 = 0 f (0,1,0) =1 = a51+0 demak a5 = 1 f (0,1,1) = 1 = a311+ a51+ a61+ 0 demak a3 = 0 f (1,0,0) =0 = a41+ 0 demak a4 = 0 f (1,0,1) = 0 = a211+ a4 + a6 + 0 f(1,1,0) = 0= a111+ a4 +a5 +0 demak demak a2 = 0 a1 =1 f (1,1,1) = 0 = a0111+1+0 + 0 + 0 +1+ 0 +0 demak a0 = 0 bundan kelib chiqadiki L = xy +y chiziqli emas ekan. 2) f1 (x, y, z) = (x2 ® x1 ) ×(x2 ¯x2 ); L1 =a0 xy +a1x + a2 y +b; f (0,0) = 1 = a0 00 + a10 + a2 0 + b, demak b =1 f (0,1) = 0 = a0 01+a10 + a21+1 demak a2 = 1 f (1,0) = 1 = a010 + a11+ a2 0 +1 demak f (1,1) = 0 = a011+ a11+ a21+1 demak L = xy + x + y +1chiziqli emas ekan. a1 =1 a0= 1bundan kelibchiqadiki 3) f1 (x, y, z) = ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); L1 = a0 xyz + a1xy + a2 xz + a3 yz + a4 x + a5 y + a6 z + b; f (0,0,0) = 0 = a0 000 + a1 00 + a2 00 + a3 0 + a4 0 + a5 0 + a6 0 + b, demak b = 0 f (0,0,1)= 1 =a61+0 demak a6 =1 f (0,1,0) = 1 = a51+0 demak a5 = 1 f (0,1,1) =1 = a311+a51+a61+0 demak a3 = 1 f (1,0,0) = 1 = a41+ 0 demak a4 =1 f (1,0,1) =1 = a211+a4 +a6 +0 demak a2 = 1 f (1,1,0) = 0 = a111+ a4 + a5 + 0 demak a1 =0 f (1,1,1) = 1 = a0111+ 0 +1+1+1+1+1+ 0 demak a0 = 0 bundan kelib chiqadiki L = xz +yz +x +y +z chiziqli emas ekan. ish formulalarni monotonlikka tekshiramiz.1) f1 (x, y, z) = ((x1 ®x2 ) Å (x2 ® x3 )) «(x2 ®x3 ) (0,1,1)  (1,0,0) va f(0,1,1)>f(1,0,0) demak f1 formula monoton emas. 2) f1 (x, y, z) = (x2 ® x1 ) ×(x2 ¯x2 ); (0,0)  (0,1) va f(0,0)>f(0,1) demak f2 formula monoton emas 3) f1 (x, y, z) = ((x1 Úx2 ×x3 ) ® (x2 ® x1 × x3 )) «(x1 Úx3 ); (1,0,1)  (1,1,0) va f(1,0,1)>f(1,1,0) demak f3 formula monoton emas Endi Post jadvalini tuzamiz: P0P1SLMf1+----f2--+--f3++---