|
Tartiblash. 0<1 munosabati orqali {0,1} to‘plamini tartiblashtiramiz. x =(x1 ,...,xn ) va =(1 ,...,n ) qiymatlar satrlari bo‘lsin.
ta’ri f. Agar xi i tengsizlik hech bo‘lmaganda bitta i uchun bajarilsa yoki x va qiymatlar satrlari ustma-ust tushsa, u holda x qiymatlar satri qiymatlar satridan oldin keladi deb aytamiz va x shaklda yozamiz.
ta’ ri f. Agar x munosabatdan f (x1,...,xn ) f (1,...,n ) tengsizlikning bajarilishi kelib chiqsa, u holda f (x1 ,...,xn ) funksiya monoton funksiya deb ataladi.
ta’ ri f Agar x munosabatdan f (x1,...,xn ) f (1,...,n) tengsizlikning bajarilishi kelib chiqsa, u holda f (x1 ,...,xn ) nomonoton funksiya deb ataladi.
Asosiy elementar mantiqiy funksiyalardan 0, 1, x , xy , x = y funksiyalar monoton, x , x = y, x = y, x = y funksiyalar esa nomonoton funksiyalardir.
1- teo re ma. Monoton funksiyalarning superpozitsiyasidan hosil qilingan funksiya ham monoton funksiya bo‘ladi.
Isboti. Ф monoton funksiyalar sistemasi bo‘lsin. Shu sistemadagi funksiyalar superpozitsiyasidan hosil qilingan funksiya monoton bo‘lishini isbot qilish kerak. Matematik induksiya usulini qo‘llaymiz. Baza: 0 rangli superpozitsiya uchun bu tasdiqning to‘g‘riligi ravshan, chunki Ф sistemadagi hamma funksiyalar monoton funksiyalardir.
Induksion o‘tish. k rangli superpozitsiya uchun teoremadagi tasdiq to‘g‘ri bo‘lsin. Bu tasdiqning k =1 rangli superpozitsiya uchun ham to‘g‘riligini isbotlaymiz.
x(y1,...,yl ), (y1,..., yl )Ф(k ) bo‘lsin. U holda
x(x1 ,...,xi1 , y, xi=1 ,...,xk );
F(x1,...,xi1,xi=1,...,xk , y1,...,yl ) =
x(x1,...,xi1,(y1,..., yl ),xi=1,...,xn )
funksiyalarning monoton ekanligini isbotlash kerak. Bu yerda y va yi o‘zgaruvchilar x j o‘zgaruvchilarning birortasi bilan mos kelishi mumkin. x funksiyaning monotonligidan x(x1,...,xi1, y, xi=1,...,xk ) funksiyaning monoton funksiya ekanligi kelib chiqadi. F funksiyaning monotonligini isbotlaymiz. Buning uchun F funksiyaning ikkita ' va '' taqqoslanadigan qiymatlar satrini ko‘rib chiqamiz:
'= (x1' ,...,xi'1,...,xi'=1,...,xn' ,1' ,...,l' ) ;
''= (x1'' ,...,xi''1,...,xi''=1,...,xn'' ,1'' ,...,l'' )
va ''' bo‘lsin. U holda F(') F('') bo‘lishini ko‘rsatish kerak. Ma’lumki,
F(') =x('), bu yerda j =i bo‘lganda j’=xj’, i’=(') ;
F('') =x(''), bu yerda j =i bo‘lganda j''=xj’', i’'=('').
monoton funksiya va ''' munosabatdan ''' kelib chiqqani uchun '''
bo‘ladi, ya’ni x(') = F(') x('') = F(''), chunki x monoton funksiyadir.
x(x1,...,xi1, y,xi=1,...,xk )F(x1,...,xi1,xi=1,...,xn, y1,..., yl )Ф(k ) ekanligidan (k =1) rangli superpozitsiya uchun teoremadagi tasdiq isbotlandi. ■
Kon’yunksiya va diz’yunksiya monoton funksiya bo‘lganligi uchun, 1- teoremaga asosan, ularning superpozitsiyasidan hosil qilingan funksiya ham monoton bo‘ladi.
2- teo re ma. 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.
1.2. Matematik mantiqning diskret texnikaga tatbiqlari. Funksional elementlar va ulardan sxemalar yasash.
Funksional elementlar va ulardan sxemalar yasash
Funksional elementlar. Biror qurilma berilgan bo‘lsin, uning ichki tarkibi bizni qiziqtirmaydi. Qurilmaning n ta tartiblangan (masalan, 1dan ngacha raqamlangan) “kirishi” va bitta “chiqishi” bo‘lsin (1- shakl).
Qurilmaning har bir kirishiga ikki xil signal berish mumkin (elektr toki bor yoki elektr toki yo‘q). Bu signallarni mos ravishda 1 va 0 bilan belgilaymiz. Qurilma kirishlariga berilgan har bir signallar majmuasi uchun uning chiqishida bitta signal paydo bo‘ladi (1 yoki 0). Chiqishdagi signalning qiymati kirishlarga berilgan signallar majmuasiga bog‘liq bo‘ladi. Shunday aniqlangan qurilmaga biz funksional element deb ataymiz.
Ma’lumki, har bir funksional elementga mantiq algebrasining bitta f (x1 ,...,xn ) funksiyasi to‘g‘ri keladi, bu holda har bir funksional element mantiq algebrasining bitta funksiyasini realizatsiya qiladi deb aytamiz. Buning uchun kirishning har bir i raqamiga xi (1 i n ) o‘zgaruvchini mos qilib qo‘yamiz.
1- shakl
U holda o‘zgaruvchilarning har bir a1,...,an qiymatlar majmuasiga f (x1 ,...,xn ) funksiyaning 0 yoki 1ga teng f (a1,...,an ) qiymati mos keladi.
Funksional elementlar va ulardan sxemalar yasash. Agar x1,...,xn funksional elementlar mavjud bo‘lsa, u holda ulardan yangi murakkab funksional elementlarni quyidagicha yasash mumkin.
Birorta funksional elementning kirishini ikkinchi bir funksional elementning chiqishi bilan tutashtirish natijasida murakkab funksional element hosil qilish mumkin (2- shakl).
Hosil qilingan qurilmani yangi funksional element deb qabul qilish mumkin. Bu funksional elementning chiqishi x1 elementning chiqishidan, kirishlari esa, x1 va x2 elementlarning ozod kirishlaridan iborat bo‘ladi. Agar yangi hosil bo‘lgan qurilmaning kirishlariga signallar majmuasini yuborsak, u holda x1 elementning ozod kirishlariga signallar bir vaqtda yetib boradi, qolgan(lar)iga bo‘lsa, x2 elementning chiqishidagi signal tushadi.
Biror funksional elementning ikki va undan ortiq kirishlarini aynan tutashtirish natijasida yangi murakkab funksional element hosil qilish mumkin (3- shakl). Bu funksional elementning chiqishi x1 elementning chiqishidan iborat, kirishlari esa, tutashtirilmagan kirishlardan va aynan tutashtirilgan kirishlarga mos keladigan bitta kirishdan iboratdir.
Uchinchi usul birinchi va ikkinchi usullarning kombinatsiyasidan iborat. Masalan, qandaydir x elementning biror kirishiga x1 elementning
chiqishi, boshqa kirishiga x2 elementning chiqishi ulanadi va ayrim 2- shakl kirishlari aynan tenglashtiriladi va hokazo (4- shakl).
Hosil bo‘lgan yangi murakkab funksional elementga birinchi va ikkinchi usullarni qo‘llab, yana yangi murakkab funksional elementga ega bo‘lamiz. Shu jarayonni cheksiz davom ettirish mumkin.
Agar x1,x2 ,...,xn funksional elementlar mos ravishda f1 , f 2 ,..., fn funksiyalarni realizatsiya qilsa, u holda hosil 3- shakl
bo‘lgan yangi murakkab funksional element realizatsiya qiladigan funksiya f1 , f 2 ,..., fn funksiyalarning superpozitsiyasidan iborat bo‘ladi.
4- shakl
Haqiqatan ham, agar biror Si funksiyani realizatsiya qiladigan xi elementning kirishiga fi funksiyani realizatsiya qiladigan xj elementning chiqishi ulangan bo‘lsa, u holda fi funksiyaning o‘sha kirishiga mos bo‘lgan argumenti o‘rniga fi funksiyani keltirib qo‘yishimiz kerak. Hamma aynan tutashtirilgan kirishlar o‘rniga ularga mos kelgan faqat bitta argument qo‘yish kerak, shuning uchun 2- shaklga asosan, x1 funksional element realizatsiya qiladigan f (x1 ,x2 ,x3 ,x4 ) funksiyaning x2 argumenti o‘rniga x2 funksional element realizatsiya qiladigan f1(y1, y2 ) funksiyani keltirib qo‘yish kerak. Natijada, f (x1, f1(y1, y2),x3,x4) =3(x1,x3, x4, y1, y2) funksiyani realizatsiya qiladigan murakkab funksional elementga ega bo‘lamiz, 1 funksiyasi esa, ta’rifga asosan, f va f1 funksiyalar superpozitsiyasi mahsulidir. 3- shakldagi funksional element f (x1,x2,x2,x4,x5) =2(x1,x2,x5) funksiyani, 4- shakldagi funksional element esa
f (x1, x2 , x2 ,x4 ,x5 ,x6 ,x7 ,x7 ,x7 ,x8 ) =
= f (x1,x2 ,x4 ,x5 ,x6 ,x7 ,x8 ) =
= f (x1(y1, y2),x2, x4,x5,x2(t1,t2,t3)) =
=3 (x2 ,x5 , y1, y2 ,t1,t2 ,t3 )
funksiyani realizatsiya qiladi. Demak, 1 funksiya f va f1 funksiyalar, 2 funksiya f funksiya va 3 funksiya esa f , f1 , f 2 , f 3 funksiyalarning superpozitsiyasidir.
Birinchi va ikkinchi usullarni qo‘llash natijasida hosil qilingan qurilmalar sxemalar (to‘g‘ri sxemalar) deb ataladi.
Endi sxemaning induksiya metodiga asoslangan ta’rifini beraylik.
Do'stlaringiz bilan baham: |
