Funksional yopiq sinflar. Post teoremasi

Tavsif

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,...,j n }funksiyalar   t a ’ r i f .  Agar mantiq algebrasining istalgan funksiyasini   F = {j1,...,j n }     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  (  P 2  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:   P 0 ,  P 1, 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,...,j n }   funksiyalar sistemasi to‘liq bo‘lishi       uchun bu sistemada   P 0, P 1, 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- jadval Berilgan funksiya Ikki taraflama funksiya f 1( x ) =  x f  *( x ) =  x 1 f 2 ( x ) =  x f  *( x ) =  x 2 f 3 ( x ,  y ) =  xy f  * =  x  Ú  y 3 f 4 ( x ,  y ) =  x  Ú  y f  * =  x y 4 f 5 ( x ,  y ) =  x  ®  y   f  * =  y  ®  x 5   f 6 ( x ,  y ) =  x  «  y   f  * =  x  «  y 6 f 7 = 1 f  * = 0 7 f 8 = 0 f  * = 1 8   funksiyaga   f  ( x 1,  x 2 ,...,  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  ( x 1,  x 2 ,...,  xn  )   o‘z-o‘ziga ikki taraflama funksiya  deb   t a ’ r i f .   å  xi 1   xi 2 ... xik     +  a   ko‘rinishdagi ko‘phad  Jegalkin ko‘phadi  deb   i ataladi, bu yerda hamma x    o‘zgaruvchilar birinchi darajada qatnashadi, j   ( i 1,..., ik  )       qiymatlarsatrida hamma i j   lar har xil bo‘ladi,   a  Î E 2 ={0, 1} .       t a ’ r i f . ataladi.   x   + x i i 1               2   + ... + x  + a i k   ko‘rinishdagi funksiya  chiziqli funksiya  deb   Mantiq algebrasidagi monoton funksiyalar. Tartiblash.   0<1   munosabati   orqali   {0,1}   to‘plamini                     tartiblashtiramiz.   a =(a1,...,a n  ) va   b =(b1,..., b n  )   qiymatlar satrlari bo‘lsin.       t a ’ r i f .  Agar  a i  £ b i   tengsizlik hech bo‘lmaganda bitta i uchun bajarilsa     yoki  a va  b qiymatlar satrlari ustma-ust tushsa, u holda  a qiymatlar satri  b     qiymatlarsatridan oldinkeladi  deb aytamiz va  a b   shaklda yozamiz.   t a ’ r i f .  Agar  a  b   munosabatdan   f  (a1,...,a n  ) £ f  (b1,..., b n  )   tengsizlikning   bajarilishi kelib chiqsa, u holda ataladi.   f  ( x 1,...,  xn  )   funksiya  monoton funksiya  deb   t a ’ r i f  Agar   a  b   munosabatdan   f  (a1,...,a n  ) > f  (b1,..., b n  )   tengsizlikning   bajarilishi kelib chiqsa, u holda   f  ( x 1,...,  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  ( x 1,...,  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  ( x 1,  x 2 ,...,  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   P 0 P 1 S L M j1           j 2           ... ... ... ... ... ... j n               Amalda berilgan   F = {j1,...,j n }   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,...,j n } 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   P 0, P 1, M  , S , L   maksimal   funksional   yopiq     sinflarning birortasini ham olib tashlash mumkin emas. Bu xulosadan, o‘z   navbatida,   P 0, P 1, 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  ={(( x 1 ®  x 2 ) Å ( x 2 ®  x 3 )) « ( x 2 ®  x 3 ); ( x 2 ®  x 1 ) × ( x 2 ¯  x 2 ); (( x 1 Ú x 2 ×  x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) « ( x 1 Ú  x 3 )}; Berilgan funksiyalar sinfining to’liqligini Post jadvali yordamida tekshirish 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  ={(( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 ); (( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) « ( x 2 ® x 3 ) ning qiymatini topamiz: (1-jadval) 1-jadval     a  = x 1 ® x 2 ;     b  = x 2 ® x 3 ;   c  = x 2 ® x 3 ;   deb belgilash kiritib olamiz.         x 1 x 2 x 3   x 2   x 3 x 1 ®  x 2   x 2 ®  x 3 x 2 ®  x 3 a  Å  b ( a  Å  b ) «  c                       0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0       Xulosa:  Ushbu (( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 ) formulaning chinlik jadvali {00110000}. 2-ish .  Endi quyidagi formulani chinlik jadvalini yuqoridagi ta’riflardan foydalanib tuzamiz: ( x 2 ® x 1 ) × ( x 2 ¯  x 2 );   2.1-ish.   ( x 2 ®  x 1 ) × ( x 2 ¯ x 2 );   ning qiymatini topamiz: (2-jadval) 2-jadval     x 1 x 2 x 2 ®  x 1 x 2 ¯  x 2 ( x 2 ®  x 1 ) × ( x 2 ¯  x 2 ) 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0   Xulosa:  Ushbu( x 2 ® x 1 ) × ( x 2 ¯  x 2 ); formulaning chinlik jadvali  f= {1010}.       3-ish .  Endi quyidagi formulani chinlik jadvalini yuqoridagi ta’riflardan foydalanib tuzamiz: (( x 1 Ú x 2 × x 3 ) ® ( x 2 ® x 1 ×  x 3 )) «( x 1 Ú x 3 );   3.1-ish.     (( x 1 Ú x 2 × x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) «( x 1 Ú x 3 );   ning qiymatini topamiz.(3-jadval)     a =  x 1 Ú  x 2 ×  x 3  ;     b  =  x 2 ®  x 1 ×  x 3;   3-jadval c =  x 1 Ú x 3 ; deb belgilash kiritib oldim.         Xulosa: Ushbu     (( x 1 Ú x 2 × x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) «( x 1 Ú x 3 );   formulaning chinlik   jadvali  f= {01111101}. Kiyingi qiladigan ishim 3 ta funksiyani ham Post  jadvaliga tekshiramiz. ish.  Formulalarni  P 0yopiq sinfga tegishli yoki tegishli emasligi tekshiramiz.   1)  f 1 ( x ,  y ,  z ) = (( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 )   f 1(0,0,0) = ((0 ®1) Å (0 ®1)) « (0 ® 0) = 0 ekan.   demak   f 1formula   P 0 yopiq sinfga tegishli   2)  f 1 ( x , y ,  z ) = ( x 2 ®  x 1 ) ×( x 2 ¯ x 2 );   f 2(0,0,0) = (0 ®0)(0 ¯ 0) =1 demak   f 2formula   P 0yopiq sinfga tegishli emas ekan.     3)  f 3 ( x ,  y ,  z ) = (( x 1 Ú x 2 × x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) «( x 1 Ú x 3 );   f 3(0,0,0) = ((0 Ú 0 ×1) ® (0 ® 0 × 0)) « (0 Ú 0) = 0 tegishli ekan.   demak   f 3formula   P 0 yopiqsinfga   ish . Formulalarni  P 1yopiq sinfga tegishli yoki tegishli emasligi tekshiramiz.   1)  f 1 ( x ,  y ,  z ) = (( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 ) f 1(1,1,1) = ((1 ® 0) Å (1 ® demak  f 1formula  P 1yopiq sinfga tegishli emas ekan. 2) f 1( x ,  y ,  z ) =( x 2 ® x 1 ) × ( x 2 ¯  x 2 );   demak       x 1 x 2 x 3 x 3 x 2  x 3 a x 1 x 3 b a  ®  b c ( a  ®  b ) «  c 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 1   f 2 formula   P 1yopiq sinfga tegishli emas ekan. f 2(1,1,1) = (1®1)(1¯ 1) =   3)  f 3 ( x ,  y ,  z ) = (( x 1 Ú x 2 × x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) «( x 1 Ú x 3 );     f 3(1,1,1) = ((1Ú1× 0) ® (1 ®1×1)) « (1Ú1) = 1demak ekan.   f 3formula   P 1 yopiq sinfga tegishli   ish.  o‘z-o‘ziga ikki taraflama funksiyalar sinfi;   1)  F  =(( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 );       a  = x 1 ® x 2 ;     b  = x 2 ® x 3 ;                               c  = x 2 ® x 3 ;   deb belgilash kiritib olamiz.       x 1 x 2 x 3   x 1   x 2   x 3   x 1 ®  x 2   x 2 ®  x 3 a  Å  b                                                    x 2 ®  x 3 ( a  Å  b ) «  c F  * 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1   Demak:   F *¹  F   funksiya o’z-o’ziga ikki taraflama emas ekan.       2)  F  *= ( x  ®  x  )( x  ¯ x  ); 2             1        2           2     x 1   x 2                             x 2 ®  x 1                     x 2 ¯  x 2 F  * 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0     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  = x 1 Ú x 2 × x 3 ;  ;                               b =  x 2 ®  x 1  x 3 ;   c  = x 1 Ú x 3 ; debbelgilash kiritib oldim.   Demak:   F *¹  F   funksiya o’z-o’ziga ikki taraflama emas ekan.   ish.  Formulalarni chiziqli yoki chiziqli emasligiga tekshiramiz. Buning uchun       x 1 x 2 x 3   x 1   x 2   x 3   x 2  x 3 a   x 1  x 3 b c a  ®  b ( a  ®  b ) «  c F  * 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 chinlik jadvalidagi oxirgi natijalardan foydalanamiz. 1)  f 1 ( x , y ,  z ) = (( x 1 ®  x 2 ) Å( x 2 ® x 3 )) « ( x 2 ®  x 3 )   L 1 =  a 0  xyz  +  a 1 xy  +  a 2  xz  +  a 3  yz  +  a 4  x  +  a 5  y  +  a 6  z  +  b ; f  (0,0,0) = 0 =  a 0 000 +  a 1 00 +  a 2 00 +  a 3 0 +  a 4 0 +  a 5 0 +  a 6 0 +  b ,       demak       b  = 0       f  (0,0,1)= 0 = a 61+0   demak   a 6 = 0     f  (0,1,0) =1 =  a 51+0 demak  a 5 = 1     f  (0,1,1) = 1 =  a 311+  a 51+  a 61+ 0   demak   a 3 = 0       f  (1,0,0) =0 =  a 41+ 0   demak   a 4  = 0   f  (1,0,1) = 0 =  a 211+  a 4 +  a 6 + 0 f (1,1,0) = 0=  a 111+  a 4 + a 5 +0   demak demak   a 2  = 0 a 1 =1   f  (1,1,1) = 0 =  a 0111+1+0 + 0 + 0 +1+ 0 +0 demak   a 0 = 0   bundan kelib chiqadiki     L  =  xy  + y  chiziqli emas ekan.   2)  f 1 ( x , y ,  z ) = ( x 2 ®  x 1 ) ×( x 2 ¯ x 2 );   L 1 = a 0  xy  + a 1 x  +  a 2  y  + b ; f  (0,0) = 1 =  a 0 00 +  a 10 +  a 2 0 +  b ,       demak       b  =1     f  (0,1) = 0 =  a 0 01+ a 10 +  a 21+1 demak  a 2 = 1   f  (1,0) = 1 =  a 010 +  a 11+  a 2 0 +1 demak  f  (1,1) = 0 = a 011+ a 11+ a 21+1 demak  L  =  xy  +  x  +  y  +1chiziqli emas ekan.   a 1 =1 a 0= 1bundan kelibchiqadiki   3)  f 1 ( x ,  y ,  z ) = (( x 1 Ú x 2 × x 3 ) ® ( x 2 ®  x 1 ×  x 3 )) «( x 1 Ú x 3 );   L 1 =  a 0  xyz  +  a 1 xy  +  a 2  xz  +  a 3  yz  +  a 4  x  +  a 5  y  +  a 6  z  +  b ; f  (0,0,0) = 0 =  a 0 000 +  a 1 00 +  a 2 00 +  a 3 0 +  a 4 0 +  a 5 0 +  a 6 0 +  b ,       demak       b  = 0       f  (0,0,1)= 1 = a 61+0   demak   a 6 =1     f  (0,1,0) = 1 =  a 51+0 demak  a 5 = 1   f  (0,1,1) =1 =  a 311+ a 51+ a 61+0 demak  a 3 = 1     f  (1,0,0) = 1 =  a 41+ 0   demak   a 4 =1   f  (1,0,1) =1 =  a 211+ a 4 + a 6 +0 demak  a 2 = 1     f  (1,1,0) = 0 =  a 111+  a 4 +  a 5 + 0   demak   a 1 =0       f  (1,1,1) = 1 =  a 0111+ 0 +1+1+1+1+1+ 0   demak   a 0 = 0   bundan kelib chiqadiki     L  =  xz  + yz  + x  + y  + z  chiziqli emas ekan.   ish formulalarni monotonlikka tekshiramiz. 1)  f 1 ( x ,  y ,  z ) = (( x 1 ® x 2 ) Å ( x 2 ®  x 3 )) «( x 2 ® x 3 )   (0,1,1)  (1,0,0) va  f (0,1,1)> f (1,0,0) demak  f 1   formula monoton emas.   2)  f 1 ( x , y ,  z ) = ( x 2 ®  x 1 ) ×( x 2 ¯ x 2 );   (0,0)  (0,1) va  f (0,0)> f (0,1) demak  f 2   formula monoton emas   3)  f 1 ( x ,  y ,  z ) = (( x 1 Ú x 2 × x 3 ) ® ( x 2 ® x 1 ×  x 3 )) «( x 1 Ú x 3 );     (1,0,1)  (1,1,0) va  f (1,0,1)> f (1,1,0) demak  f 3   formula monoton emas   Endi Post jadvalini tuzamiz:     P 0 P 1 S L M f 1 + - - - - f 2 - - + - - f 3 + + - - -    

Hujjat haqida

Kategoriya

Amaliy ishlar | Algebra

Format

DOCX

Hajmi

16 bet

Fayl hajmi

82.23 KB

Muallif

Avazbek Abdusalomov

Qo'shilgan

15.10.2024