Mavzu: Funksional element. Sxema yasash usullari. Funksiyani sxemalar orqali ifodalash. Sxemaning matematik induksiya metodi bo‘yicha ta’rifi

1- t a ’ r i f . a) Har qanday funksional element sxema bo‘ladi. Uning kirishi funksional elementning kirishidan, chiqishi esa uning chiqishidan iborat bo‘ladi;

b) agar S0 sxema va uning ikkita kirishi aynan tutashtirilgan bo‘lsa, u holda hosil

bo‘lgan S qurilma ham sxema bo‘ladi. S ning chiqishi S0 ning chiqishidan va S ning kirishlari bo‘lsa, S0 ning tutashtirilmagan kirishlaridan va aynan tutashtirilgan ikkita kirishga mos kelgan kirishdan iborat bo‘ladi;

d) agar S0 va S1 sxemalar bo‘lsa, u holda S0 sxemaning birorta kirishiga S1 sxemaning

chiqishini ulash natijasida hosil bo‘lgan S qurilma ham sxema bo‘ladi. S sxemaning chiqishi

4- shakl

Haqiqatan ham, agar biror Si funksiyani realizatsiya qiladigan i elementning kirishiga

fi funksiyani realizatsiya qiladigan  j 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, 1 funksional element realizatsiya qiladigan

3- shakl

S0 sxemaning chiqishidan va uning kirishlari S1 ning hamma kirishlaridan hamda S ning chiqishi bilan tutashtirilgan S0 ning kirishidan tashqari ozod qolgan hamma kirishlaridan iboratdir;

e) ushbu ta’rifning b) va d) bandlarida tasvirlangan usullar orqali chekli qadamda har qanday sxemani funksional elementlardan yasash mumkin.

Bu ta’rif oldingi paragraflarda funksiyalar superpozitsiyasi haqida berilgan ta’rifdan shakli jihatdan birmuncha farq qiladi. Bu farq birinchi navbatda sxemaning rangi (funksional elementlardan sxema yasash uchun bajarilgan qadamlar soniga sxemaning rangi deb ataladi) tushunchasi kiritilmaganligi tufayli paydo bo‘ldi. Ikkala ta’rifni taqqoslab tahlil qilishni o‘quvchiga havola etamiz.

Endi mantiq algebrasining sxema realizatsiya qiladigan funksiyasini induksiya metodi orqali topaylik.

• Induksiya asosi. Har bir funksional element bitta mantiq algebrasining funksiyasini realizatsiya qilishi aniqlangan.
• Induktiv o‘tish. a) Agar S0 sxema f (x1, x2 ,..., xn ) funksiyani realizatsiya qilsa, u holda

1- ta’rifning b) bandi asosida qurilgan S1 sxema aynan tutashtirilgan kirishlarga mos keladigan

xi , x j argumentlarni aynan tenglashtirish natijasida hosil qilingan funksiyani realizatsiya qiladi;

b) f (x1, x2 ,..., xn ) funksiyani S0 sxema va  ( y1 , y2 ,..., ym ) funksiyani S1 sxema realizatsiya qilsin, bu yerda x1, x2 ,..., xn , y1, y2 ,..., ym lar bir-biriga teng bo‘lmagan o‘zgaruvchilar bo‘lsin. U holda 1- ta’rifning d) bandiga asosan qurilgan S sxema



f (x1,..., xi1, ( y1,..., ym ), xi1,..., xn ) ni realizatsiya qiladi. Bu yerda  ( y1 ,..., ym ) funksiya f

funksiyaning xi argumenti o‘rniga qo‘yilgan.

Teng kuchli funksiyalarni bir xil funksional element realizatsiya qiladi deb qabul qilamiz.

Buning uchun soxta kirish tushunchsiani kiritamiz.



• t a ’ r i f . Agar  funksional element realizatsiya qiladigan f (x, y1 ,..., yn ) funksiyaning

qiymati x argumentga mos kelgan kirish signalining qiymatiga (0 yoki 1ga) bog‘liq bo‘lmasa (ya’ni, x o‘zgaruvchi f (x, y1 ,..., yn ) ning soxta argumenti bo‘lsa, u holda  elementning x argumentga mos kirishi soxta kirish deb ataladi.

• t a ’ r i f . Faqatgina kirishlarning raqamlanish tartibi va soxta kirishlari bilan farq qiladigan funksional elementlar ekvivalent funksional elementlar deb ataladi.

Demak, funksional elementni o‘zgartirmasdan istalgancha soxta kirishlarni olib tashlash yoki qo‘yish mumkin.

Ф  (1 ,2 ,...,n ) sistema 1,2 ,...,n funksional elementlar sistemasi va

F  ( f1 , f2 ,..., fn ) sistema 1,2 ,...,n funksional elementlar mos ravishda realizatsiya qiladigan f1, f2 ,..., fn funksiyalar sistemasi bo‘lsin. Ф  (1 ,2 ,...,n ) sistema qanday shartlarni qanoatlantirganda, mantiq algebrasining istalgan funksiyasini uning 1,2 ,...,n funksional elementlaridan yasalgan sxema orqali realizatsiya qilish mumkinligi masalasini ko‘raylik.

• t a ’ r i f . Mantiq algebrasidagi istalgan f (x1 , x1 ,..., xn ) funksiyani Ф sistemadagi

1 ,2 ,...,n funksional elementlardan yasalgan sxema orqali realizatsiya qilish mumkin bo‘lsa, bu funksional elementlar sistemasi to‘liq sistema deb ataladi.

Biz yuqorida sxema realizatsiya qiladigan funksiya shu sxemani yasashda foydalanilgan funksional elementlar realizatsiya qiladigan funksiyalarning superpozitsiyasidan iborat ekanligini

ko‘rgan edik. Demak, F  { f1 , f2 ,..., fn } funksiyalar sistemasi Post teoremasining shartlarini

qanoatlantirgan taqdirdagina, Ф  (1 ,2 ,...,n ) sistemasidagi funksional elementlar orqali mantiq algebrasining istalgan funksiyasini realizatsiya qiladigan sxema yasashimiz mumkin

ekan. Bu yerdan funksional elementlardan yasalgan sxemalar tili mantiq algebrasi funksiyalarining superpozitsiyasi tiliga ekvivalentligi kelib chiqadi.

F1 ning iborat