VII-БОБ. МАТЕМАТИК МАНТИКНИНГ ТЕХНИКАГА ТАТБИКИ

 

            Математик мантикнинг мухим булимларидан бирини ташкил этувчи мулохазалар алгебрасини техникага (математик кибернетикага) татбик этилишини куришга утамиз.

            Ушбу бобда реле-контактли схемалар, контактли схемалар ва уларнинг синтези, функционал элементлар ва улардан схемалар ясаш, куптактли схемалар, функционал элементлар системасининг туликлиги, схемаларни минималлаштириш муаммоси, тескари богланиши булмаган автоматлар, чекли автомат хакида умумий тушунчалар, Мили ва Мур автоматлари  каби масалалар куриб чикилган. Мантик алгебраси функцияларини схемалар (автоматлар) оркали реализация этиш масаласига алохида ахамият берилган.

 

1-§. Функционал элементлар ва улардан схемалар ясаш

Функционал элемент. -Курилма. -Схема ясаш усуллари. -Функциянинг реализацияси. -Схеманинг математик индукция методи бœйича таърифи. -Сохта кириш. -Функционал элементлар системасининг тœликлиги.

-Цикл. -Теорема.

 

            Кандайдир курилма берилган булсин, унинг ички таркиби бизни кизиктирмайди. Курилманинг n та тартибланган (масалан, 1 дан n гача ракамланган) “кириши” ва битта “чикиши” булсин (1-шакл).

 

 

 

                            

                                

                         1  2  3 ............  n-1 n

                                  1-шакл.

Курилманинг хар бир киришига икки хил сигнал бериш мумкин (ток бор ёки ток йук). Бу сигналларни биз мос равишда 1 ёки 0 билан белгилаймиз. Курилма киришларига берилган хар бир сигналлар мажмуаси учун унинг чикишида битта сигнал пайдо булади (1 ёки 0). Чикишдаги сигналнинг киймати киришларга берилган сигналлар мажмуасига боглик булади. Шундай аникланган курилмага биз функционал элемент деб айтамиз. Маълумки, хар бир функционал элементга мантик алгебрасининг битта  функцияси тугри келади, бу холда хар бир функционал элемент мантик алгебрасининг битта функциясини реализация этади деб айтамиз. Бунинг учун киришнинг хар бир  номерига  узгарувчини мос килиб куямиз. У вактда узгарувчиларнинг хар бир  кийматлар мажмуасига  функциянинг 0 ёки 1 га тенг  киймати мос келади.

            Агар бизда  функционал элементлар мавжуд булса, у холда улардан янги мураккаб функционал элементларни куйидагича ясаш мумкин.

1. Бирорта функционал элементнинг киришини иккинчи бир функционал элементнинг чикиши билан туташтириш натижасида мураккаб функционал элемент хосил килиш мумкин (2-шакл).

 

 

                                         j₃ 

 

 

                                    

                                    j₂  

                                                     

 

2-шакл.

            Хосил этилган курилмани янги функционал элемент деб кабул килиш мумкин. Бу функционал элементнинг чикиши  элементнинг чикишидан, киришлари эса,  ва  элементларнинг озод булган киришларидан иборат булади. Агар янги хосил булган курилманинг киришларига сигналлар  мажмуасини юборсак, у вактда  элементнинг озод киришларига сигналлар бир вактда етиб боради, колганига булса,  элементнинг чикишидаги сигнал тушади.

            2. Бирор функционал элементнинг икки ва ундан ортик киришларини айнан туташтириш натижасида янги мураккаб функционал элемент хосил килиш мумкин (3-шакл).

                  

 

                                   j₁  

 

 

                         

 

                               

                               3-шакл.  

Бу функционал элементнинг чикиши  элементнинг чикишидан иборат, киришлари булса, туташтирилмаган киришлардан ва айнан туташтирилган киришларга мос келадиган битта киришдан иборат булади.

            3. Учинчи усул биринчи ва иккинчи усулларнинг комбинациясидан иборат. Масалан, бирорта  элементнинг бирор киришига  элементнинг чикиши, иккинчи бирор киришига  элементнинг чикиши уланади ва айрим киришлари айнан тенглаштирилади ва хоказо (4-шакл).

 

                                  

 

                                    j

 

 

 

                    j₁                                          j₂

 

 

                                  4-шакл.

Хосил булган янги мураккаб функционал элементга биринчи ва иккинчи усулларни куллаб, яна янги мураккаб функционал элементга эга буламиз. Шу процессни чексиз давом эттиришимиз мумкин.

            Агар  функционал элементлар мос равишда  функцияларни реализация этса, у вактда хосил булган янги мураккаб функционал элемент реализация этадиган функция  функцияларнинг суперпозициясидан иборат булади.

            Хакикатан хам, агар бирор  функцияни реализация киладиган  элементнинг киришига  функцияни реализация киладиган  элементнинг чикиши уланган булса, у вактда  функциянинг уша киришига мос булган аргументи урнига  функцияни келтириб куйишимиз керак. Хамма айнан туташтирилган киришлар урнига уларга мос келган факат битта аргумент  куйиш керак, шунинг учун 2-шаклга асосан,  функционал элемент реализация киладиган  функциянинг  аргументи урнига  функционал элемент реализация киладиган  функцияни келтириб куйиш керак. Натижада,  функцияни реализация киладиган мураккаб функционал элементга эга буламиз,  функцияси булса, таърифга асосан,  ва  функциялар суперпозицияси махсулидир. 3-шаклдаги функционал элемент  функцияни, 4-шаклдаги функционал элемент эса  

 

функцияни реализация килади. Демак,  функция  ва  функциялар,  функция  функция  ва   функция эса   функцияларнинг суперпозициясидир.

            Биринчи ва иккинчи усулларни куллаш натижасида хосил этилган курилмалар - схемалар (тугри схемалар) деб айтилади.

            Энди схеманинг индукция методи буйича таърифини берайлик.

 

            1-таъриф. а) Хар кандай функционал элемент схема булади. Унинг кириши функционал элементнинг киришидан, чикиши булса - унинг чикишидан иборат булади.

б) Агар  схема ва унинг иккита кириши айнан туташтирилган булса, у холда хосил булган  курилма хам схема булади.  нинг чикиши  нинг чикишидан ва  нинг киришлари булса,  нинг туташтирилмаган киришларидан ва айнан туташтирилган иккита киришга мос келган киришдан иборат булади.

в) Агар  ва  схемалар булса, у холда  схеманинг бирорта киришига  схеманинг чикишини улаш натижасида хосил булган  курилма хам схема булади.  схеманинг чикиши  схеманинг чикишидан ва унинг киришлари  нинг хамма киришларидан хамда  нинг чикиши билан туташтирилган  нинг киришидан ташкари озод колган хамма киришларидан иборатдир.

г) б) ва в) пунктларда тасвирланган усуллар оркали чекли кадамда хар кандай схемани функционал элементлардан ясаш мумкин.

            Бу таъриф олдинги параграфларда функциялар суперпозицияси хакида берилган таърифдан форма жихатдан бирмунча фарк килади. Бу фарк биринчи навбатда схеманинг ранги (функционал элементлардан схема ясаш учун бажарилган кадамлар сонига схеманинг ранги деб айтилади) деган тушунчани киритмаганимиз туфайли пайдо булди. Иккала таърифни таккослаб тахлил этишни укувчига хавола этамиз.

            Энди схема реализация этадиган мантик алгебрасининг функциясини индукция методи оркали топайлик.

            1.Индукция асоси. Хар бир функционал элемент битта мантик алгебрасининг функциясини реализация этиши аникланган.

            2.Индуктив утиш. а) Агар  схема  функцияни реализация этса, у холда 1-таърифнинг б) пункти асосида курилган  схема айнан туташтирилган киришларга мос келадиган  аргументларни айнан тенглаштириш натижасида хосил этилган функцияни реализация этади.

            б)  функцияни  схема ва  ни  схема реализация килсинлар, бу ерда  лар бир-бирига тенг булмаган узгарувчилар булсин. У вактда 1-таърифнинг в) пунктига асосан курилган  схема , ,  ни реализация этади. Бу ерда  функция  функциянинг   аргументи урнига куйилган.

            Тенгкучли функцияларни бир хил функционал элемент реализация этади деб кабул киламиз. Бунинг учун сохта кириш деган тушунчани киритамиз.

 

            2-таъриф.  Агар  функционал элемент реализация киладиган  функциянинг киймати  аргументга мос келган кириш сигналининг киймати (0 ёки 1)га боглик булмаса (яъни  нинг сохта аргументи булса, у холда  элементнинг  аргументга мос кириши    сохта кириш деб аталади.

 

            3-таъриф. Факатгина киришларнинг ракамланиш тартиби ва сохта киришлари билан фарк киладиган функционал элементлар эквивалент функционал элементлар деб айтилади.

            Демак, функционал элементни узгартирмасдан исталганча сохта киришларни олиб ташлаш ёки куйиш мумкин.

              функционал элементлар системаси ва    функционал элементлар мос равишда реализация этадиган  функциялар системаси булсин.  система кандай шартларни каноатлантирганда, мантик алгебрасининг исталган функциясини унинг  функционал элементлари ясалган схема оркали реализация этиш мумкинлиги масаласини курайлик.

            4-таъриф. Мантик алгебрасидаги исталган  функцияни  системадаги  функционал элементлардан ясалган схема оркали реализация этиш мумкин булса, бу функционал элементлар системаси тулик система деб айтилади.

            Биз юкорида схема реализация этадиган функция шу схемани ясашда фойдаланилган функционал элементлар реализация этадиган функцияларнинг суперпозициясидан иборат эканлигини курган эдик. Демак,  функциялар системаси Пост теоремасининг шартларини каноатлантирган такдирдагина,  cистемасидаги функционал элементлар оркали исталган мантик алгебрасининг функциясини реализация этадиган схема ясашимиз мумкин экан. Бу ердан функционал элементлардан ясалган схемалар тили мантик алгебраси функцияларининг суперпозицияси тилига эквивалентлиги келиб чикади.

            Мисол. 1. функциялар системаси тулик булганлиги учун,  нинг элементларини мос равишда реализация этадиган  элементлардан иборат  система тулик булади.

            2. функциялар системаси тулик булмаганлиги учун,  нинг элементларини мос равишда реализация этадиган  элементлардан иборат  система тулик булмайди.

            3. функциялар системаси тулик булганлиги учун,  нинг элементларини мос равишда реализация этадиган  элементларидан иборат  система хам тулик булади.

            4. функциялар системаси тулик булганлиги учун,  нинг элементларини мос равишда реализация этадиган  элементларидан иборат  система хам тулик булади.

            Мисол.  ва  булсин.  функционал элемент  функцияни,  -  функцияни реализация этадилар. Ушбу функционал элементлар оркали , , , ,  ва  элементар функцияларни реализация этиш талаб этилсин.

            1)  ни реализация этиш учун = формуладан фойдаланамиз. Агарда  нинг киришига  сигнал берсак, у холда унинг чикишида = сигнал

 

                                         

                                            

                                                                                         j₂

          

                j₁                        j₂

                                              

                                                                                           j₁                

                                                     

                                                             

 

                                                                j₂                  j₂

 

                                               

                                                        

                                  

5-шакл

 

пайдо булади.  сигнални хосил этиш учун  элемент  киришларининг бирига  ва иккинчисига  сигналларни берамиз. Натижада, унинг чикишида  сигнал пайдо булади ва уни  нинг кириши билан улаймиз. ва  ларни хосил этиш учун  иккита    элементнинг бирининг киришига  ва иккинчисининг киришига  сигналларни бериб, уларнинг чикишлари   нинг киришлари  билан уланади. Шундай килиб, 5-шаклда ифода этилган  функцияни реализация  этадиган  схемага эга буламиз.

2)  функцияни схема оркали реализация этиш учун == формуладан фойдаланамиз. Агарда  элементнинг киришига   сигнал берилса, у холда унинг чикишида берилган сигналнинг инкори, яъни = сигнал пайдо булади. Уз навбатида  сигнални хосил этиш учун  элемент киришларининг бирига  ва иккинчисига  сигнални бериш керак хaмда унинг чикишини  функцияни реализация этадиган   элементнинг киришига улаш керак.  сигнални хосил этиш учун  элементнинг киришига  сигнал бериб, унинг чикишини  нинг иккинчи киришига улаймиз. Натижада,  функцияни реализация этадиган  схемага эга буламиз (3.6-шакл).

           

 

 

 

 

                  

 

                                 j₂

 

                                       

 

                                 j₁

 

                                               

                                                j₂

 

                                                     

 

6-шакл.

 

                    

                  

                              j₁

                                           

                      j₂                          j₂       

          

                                        

                      j₁                                    j₁

                                                    

                        j₂                        j₂

                              

                                                          

                                       

                                                                                   

                                      

                            7-шакл.              

 

                  1=                             0=

 

          

               j₂                                                          j₁

                                                           

                  j₁                                                               

                                                                                                      j₂

                                                                  

                         j₂                                                           

                                                                                                                                    

                               

 

                  

                     а)                                       б)

8-шакл.

 

            3)  функцияни реализация этадиган схемани ясаш учун == формуладан фойдаланамиз. Юкорида акс эттирилган услубдан фойдаланиб, = функцияни реализация этадиган  схемани хосил киламиз (3.7-шакл).

            4) 1 константани реализация этиш учун  ва 0 ни реализация этиш учун  формулалардан фойдаланамиз ва уларни реализация этадиган схемалар 3.8-шаклда келтирилган.

Мисол ечимининг тахлилидан куриниб турибдики, бирор ихтиёрий  функцияни схема оркали реализация этиш учун:

            1) берилган   системасидаги  функционал элементлардан куп погонали схема тузишга тугри келади;

            2) куп погонали схемани юкоридан пастга караб ясашга тугри келади;

            3) схеманинг озод чикишли функционал элементи киришларига шундай сигналлар мажмуасини бериш керакки, унинг чикишида курилаётган схема реализация этиши керак булган  функцияга мос келадиган сигнал пайдо булсин;

            4) схеманинг ички функционал элементлари киришларига шундай сигналлар мажмуасини бериш керакки, унинг чикишида сизга керак булган сигнал пайдо булсин.

            Таърифга асосан берилган курилманинг схема эканлигини аниклаш мумкин. Аммо схема эмаслигини аниклаш учун берилган курилманинг схемага лойик булган хусусиятларга эга эмаслигини курсатиш керак булади.

5-таъриф.  функционал элементлар берилган булсин. Агар  элементнинг чикиши  элементнинг киришига,  нинг чикиши  элементнинг киришига ва хоказо,  чикиши  нинг киришига ва  нинг чикиши  нинг киришига уланган булса, у холда бундай курилмага цикл ва курилмада тескари богланиш бор деб айтамиз.

            Теорема.  функционал элементлардан ясалган  курилма:

            1)  элементлардан факатгина биттасининг  чикиши озод булса;

            2) хар бир  элементнинг кириши факатгина  элементларнинг биттасининг чикиши билан уланган булса;

            3)  курилмада цикл (тескари богланиш) мавжуд булмаса, шунда ва факат шундагина схема булади.

            Теоремани исбот килишни укувчиларга хавола этамиз.

 

2-§. Куптактли схемалар

 

Такт. -Ушлаб туриш вакти. -Ушлаб туриш элементи. -Кœптактли схема. -Бир тактли функционал элементлар системасининг тœликлиги. -Теорема.

 

            Ушбу бобнинг биринчи параграфида курилган функционал элементлар ва улардан ясалган схемалар оний равишда  ишлайди деб фараз килган эдик, яъни уларнинг киришларига сигналлар мажмуаси берилган захотиёк (уларнинг) чикишларида натижавий сигнал пайдо булади. Демак, киришларга берилган сигналлар мажмуасини ишлаб чикиш учун хеч кандай вакт сарфланмайди.

            Аммо, амалда функционал элемент киришларига берилган сигналлар мажмуасига мос келадиган унинг чикишидаги натижавий сигнални олиш учун бироз вакт сарф булади. Бундай холатда схеманинг киришларига берилган сигналлар мажмуаси унинг ички функционал элементларининг киришларига хар хил вактда етиб келади, чунки, биринчидан, элементларнинг киришларига етиб келган сигналлар бир канча элементлардан утиб келади, иккинчидан, хар бир элемент киришларига етиб келган сигналларни хар хил вактларда ишлаб чикади. Бирок схема киришларига берилган сигналлар мажмуасини етарлича узок вакт бериб туриш мумкинки, токи схема ички элементларининг хамма киришларига сигналлар етиб келсин. Натижада, схеманинг чикишида маълум вактдан кейин унинг киришларига берилган сигналлар мажмуасига мос келадиган сигнал пайдо булади. Шундан кейин киришларга берилган сигналлар наборини тухтатиш мумкин ва бу схемани у реализация этадиган функция кийматини аргументлар кийматининг бошка мажмуасида хисоблаш учун ишлатиш мумкин.

        Функционал элементнинг бу иккинчи хил ишлаши куйидаги камчиликларга эга булади:

            1) киришга сигналлар мажмуасини маълум вакт давомида бериб туриш;

            2) маълум вакт давомида схема чикишида пайдо буладиган сигнал унинг киришларига берилган сигналлар мажмуасига мос келмаслиги.

            Янги шароитда кандай курилмани биз функционал элемент деб биламиз деган саволга жавоб берайлик.

            1-таъриф. Элемент (1-шакл) учун аник булган n вактдан кейин унинг чикишида киришларига берилган сигналлар мажмуасига мос келадиган сигнал (реализация этиладиган функциянинг берилган сигналлар наборидаги киймати) пайдо булса, бундай курилма  функционал элемент деб аталади.

            Агар келгуси моментда элемент киришларига янги сигналлар мажмуаси берилса, у вактда  n  вактдан кейин унинг чикишида берилган сигналлар мажмуасига мос келадиган сигнал пайдо булади, яъни киришларга кетма-кет бериладиган сигналлар мажмуаси бир-бирига боглик булмаган холда ишлаб чикилади.

            Вакт дискрет равишда  узгаради деб фараз киламиз (t=1,2,3,...k) ва вакт бирлигини бир такт деб айтамиз.

            2-таъриф. n вактга (элемент киришига берилган сигналлар мажмуасига мос келадиган сигнал унинг чикишида пайдо булишигача сарф этилган вактга) функционал элементнинг ушлаб туриш вакти деб айтилади.

            Бундан кейин схемани берилган таърифга мос келадиган янги маънодаги функционал элемент сифатида караймиз.

            Бундай схемаларни ясаш жараёнида ушлаб туриш элементлари катта роль уйнайди.

        3-таъриф. Агар функционал элемент чикишида маълум вактдан (тактдан) кейин унинг киришига берилган (0 ёки 1) сигналнинг узи пайдо булса, у холда бундай функционал элементга ушлаб туриш элементи деб айтилади (9-шакл).

       Ушлаб туриш элементи функцияни реализация этадиган функционал элементдир, яъни унинг чикишида маълум вактдан кейин киришига берилган сигналнинг узи пайдо булади.

           

 

                                  j

 

 

       

 

                              9-шакл.

Бундан кейин (агарда махсус айтилган булмаса) хамма функцонал элементларни бир тактли, яъни элементнинг киришига сигнал берилгандан кейин унинг чикишида натижавий сигнал пайдо булгунча бир такт вакт утади деб фараз киламиз.

            4-таъриф. Агар  схеманинг  та киришларига  сигналлар мажмуасини бергандан маълум n тактдан кейин унинг чикишида  функциянинг  киймати хосил булса, у холда  схема  функцияни  ушлаб туриш вакти билан реализация этади деб айтилади.

Бундай  схемани n ушлаб туриш вакти билан  функцияни реализация этадиган функционал элемент деб караш мумкин.

            Мантик алгебрасининг исталган функциясини реализация этадиган схема тугри схема деб айтилади.

            Бир тактли функционал элементлардан тузилган схемани куптактли, оний равишда ишлайдиган функционал элементлардан тузилган схемани нультактли схема деб айтамиз.

            1-изох. Агар (биртактли функционал элементлардан тузилган) тугри схемадаги хамма функционал элементларни нультактли деб фараз килсак, у холда хосил булган нультактли схема хам куптактли схема реализация киладиган функцияни реализация килади.

            2-изох.  функцияни реализация этадиган  тугри схеманинг ушлаб туриш вакти n доимо схеманинг кетма-кет уланган ички функционал элементлари сонига тенг эмас. Масалан,  функционал элементлардан (10-шакл) тузилган схема (11-шакл), кетма-кет уланган функционал элементларнинг сони иккига тенг булишига карамасдан,  функцияни реализация килувчи бир тактли схемадир.

            3-изох. Константаларни (0 ёки 1) реализация этадиган схемалар ёки функционал элементларнинг хамма киришлари сохта киришлардир. Бундай схемаларни нультактли схемалар деб айтиш мумкин.

            Энди  биртактли функционал элементлардан иборат  системанинг туликлик масаласини куришга утамиз.

                                                

 

             j₁                     j₂              j₃           j₄

 

 

 

                                                   

10-шакл.

 

 

 

                                                                                         

 

 

                                 j₁

 

 

 

                              j₃                     j₂                  j₄

 

 

 

                                          

                                         

 

11-шакл.

 

            5-таъриф. Агар мантик алгебрасининг исталган функциясини  системасидаги функционал элементлардан тузилган схема оркали реализация этиш мумкин булса, у вактда  системасига тулик система деб айтилади.

            Мисол.  шундай биртактли функционал элементлар системасики, бу ерда   функцияни реализация этадиган ушлаб туриш элементи,   Шеффер функциясини реализация этадиган функционал элементдир.

а) ;  б) ;  в) ;  г) 1;  д) 0; е) ; з) ;

ж)   функцияларни реализация этувчи схемаларни  ва  функционал элементлар оркали ясаш ва ушлаб туриш вактини (тактини) аниклаш талаб этилади.

 

                                                  

       

                j₁                                                         j₂

 

                                                    

Юкорида курсатилган функцияларни реализация этадиган схемалар куйидагича булади:

      а)                    в)       

       

 

          j₂                                       j₂

 

 

                                          j₂                            j₂

 

                     

                                                             

            n=1                                        n=2

            б)                       г)

           

 

 

           j₂                                                j₂

 

 

 

           j₂                                                             j₁                  j₂

             

 

                 

           n=2                          

                                                        

                                                       n=2

д)                   е)

 

 

             j₂                                                               j₂

 

 

 

             j₂                         j₂                                 j₂

           

 

      j₁                   j₂                     j₁             j₂               j₂             j₁

  

 

 

 

                                                       

             n=3                                        n=3

 

 

               з)

        

                           

                                j₂                                                   

                                        

                          j₂                   j₂                                         

 

 

                                        

                                n=2

 

 

 

      ж)  

 

                             j₂

 

                                       

                             j₂

                                          

                   j₂                                         j₂

 

                                      

                   j₁                                                           j₁

                                                        j₂        j₂            

                   

                                         

                                                         

                                        

 

                                      n=3

 

                                 12-шакл.

           

            Мисол. 1. Шеффер функциясини реализация киладиган j элементдан иборат  система тулик буладими?

            2.  элементлар системаcининг  туликлигини исбот килинг.

            Мисоллар ечимларининг тахлилидан маълумки, биртактли   функционал элементлар системаси  нинг туликлик шартлари нультактли    функционал элементлар системаси  нинг тулик шартларига мос келмайди.

            Куйидаги белгилашларни киритамиз: 1) мантик алгебрасининг элементлари  ва  (0 ва 1 сакламовчи функциялар, яъни аргументларини айнан тенглаштирганда  функция  га тенг булади) функциялардан иборат тупламни  билан;

            2) исталган кисм узгарувчилар урнига константаларни (0 ёки 1) куйиб, колган кисмини айнан тенглаштирганда 0,1 ёки   (яъни  пайдо булмайди) хосил буладиган функциялардан иборат тупламни  билан белгилаймиз.

            Теорема. Агар  биртактли  функционал элементлар системаси реализация киладиган функциялар ичида

            а) Пост теоремаси шартларини каноатлантирувчи функциялар системаси;

            б) Q туплам элементи булмаган функциялар;

            в) R туплам элементи булмаган функциялар мавжуд булса, факат шундагина бундай система тулик булади.

 

РЕЖА:

 

            1.Математик мантикнинг дискрет техникага

            татбиклари.

            2.Функционал элементлар ва улардан схемалар

           ясаш. 

            3.Кœптактли схемалар.

           

 

 

 

 

 

 

Муаммоли масала ва топшириклар:

1.  системасидаги функцияларни реализация этадиган   функционал элемент-лар системаси берилган булсин.

                                      

 

                                

 

                               

                                            

            ,  ,  ,  ,  ва  элементар функцияларни реалилизация этадиган схемалар ясанг.

2.  ва  хамда  ва лар берилган булсин. Хамма элементар функцияларни реализация этадиган схемаларни аввал  функционал элементи оркали, кейин  - оркали ясанг.

3. 13-шаклдаги функционал элементлардан тузилган курилмаларнинг кайси бирлари схема булади?

 

 

             j₁                              j₁

 

 

                                      j₂                                                          

            j₂

                                          

 

                                               j₃                                      

                j₃

   

 

              а)                               б)

    

        

             j₁                                            

                                           j₁                           j₂

 

 

 

 

   j₂           j₃          j₄              j₃                        j₄               j₅                                                                               

        

 

            

           в)                                     г)

 

 

                                  j₁

 

 

                      j₂                                      j₃

 

 

                          

 

                        j₄                    

 

                                    д)

 

                              

 

13-шакл.

 

 

 

 

 

4. 14-шаклдаги курилмаларнинг кайси бири схема булади?

         

                            

            j₁                             j₁

                                              

                                    j₂

    j₂                    j₄             

                                                                

                                                      j₃

           j₃                                          

                  

                                             j₄

            j₅

 

                                                j₅

           

 

 

 

14-шакл.

 

5.  бœлсин, каерда  -  Шеффер функциясини ва  -  функциясини (ушлаб туриш элементи) реализация этади. Хамма мантик алгебрасининг элементар функцияларини реализация этадиган схемалар ясанг.

6.  бœлсин, каерда  -  Шеффер функциясини ва  -  функциясини (ушлаб туриш элементи) реализация этади. , , , , ,  функцияларни реали-зация этадиган схемалар ясанг.

 

 

Мустакил ишлаш учун саволлар:

 

            1.Функционал элементлар ва улардан схемалар

          ясаш. 

            2.Схеманинг математик индукция методи бœйича

          таърифи.

            3.Фукнкционал элементлар системасининг тœлик-

          лиги хакидаги теорема.

            4.Цикл деб нимага айтамиз?

            5.Ушлаб туриш вакти ва ушлаб туриш элементи.

            6.Кœптактли схеманинг таърифи.

            7.Биртактли функционал элементлар системаси-

          нинг тœликлиги хакидаги теорема. 

 

3-§. Тескари богланиши булмаган автоматлар

 

Элементнинг юкори ва куйи индекси. -Тœгри схема. -Тескари богланиши бœлмаган автомат. -Характеристик функция. --индекси.  -Кучсиз автоматли тœлик система.

 

            Утган параграфда мантик алгебрасининг функцияларини факат тугри схемаларгина реализация этишини курдик. Биртактли функционал элементлардан ясалган схеманинг умумий холда ишлаш жараёнини курайлик. Схема киришларига хар моментда сигналлар мажмуаси берилиб турилади. Аникки, схеманинг чикишидаги сигнал унинг киришларига олдинги моментларда берилган сигналлар мажмуасига боглик булади.

            Функционал элементнинг куйи ва юкори индекслари деган тушунчани киритайлик.

            1-таъриф. Схеманинг киришларига берилган сигналлар j функционал элементнинг чикишида хосил булишига кадар босиб утилган ички функционал элементларнинг максимал сонига ( элементнинг узи хам киради) элементнинг юкори индекси ва минимал сонига  куйи индекси деб айтилади.  функционал элемент  схеманинг чикиш элементи (яъни озод чикишга эга булган элементи) булсин. У вактда  элементнинг юкори ва куйи индексларини мос равишда  ва  билан белгилаймиз.

            Демак, схема тугри булиши учун бирор  элементнинг киришларига чикишлари уланган хамма функционал элементларнинг юкори индекслари тенг булиши керак (етарли шарт).

            Схема таърифига асосан,  вакт моментида схеманинг чикишидаги сигнал унинг киришларига  дан  моментгача берилган сигналлар наборига боглик булади. Демак,  моментдаги чикиш сигнали унинг киришларига  кетма-кет берилган сигналлар мажмуасининг функцияси булади:

.

            Бу ерда -мантик алгебрасининг  аргументли функцияси ва - киришларга  моментда берилган сигналлар мажмуаси булади. Агар схема тугри булса, у холда  функция катъиян  моментда (яъни , албатта ) берилган факатгина битта сигналлар  мажмуасига боглик булади ва  схема  функцияни  ушлаб туриш вакти ( такт) билан реализация этади.

            2-таъриф.  киришларга ва битта чикишга эга булган курилма берилган булсин (3.1-шакл) Хар бир моментда унинг киришларига 0 ёки 1 сигнал берилганда, чикишида хар бир  моментда 0 ёки 1 сигнал хосил булади. Чикишдаги сигнал киришларга  дан  моментгача  кетма-кет берилган сигналлар мажмуасининг функцияси булади:

.

Бу ерда  моментда берилган сигналлар мажмуига тенг булади. У вактда бундай курилмага тескари богланиши булмаган автомат деб айтилади. Мантик алгебрасининг  функцияси унинг характеристик функцияси, -индекси, -ушлаб туриш вакти деб айтилади.

            Агар тескари богланиши булмаган иккита автоматларнинг ₁ ва ₂ характеристик функциялари факатгина сохта аргументлари билан фарк килса, у холда бундай автоматларга эквивалент автоматлар деб айтилади.

            Хар кандай функционал элемент бирорта тескари богланиши булмаган автоматни ифодалайди. Бу элемент учун характеристик функция у реализация киладиган функция билан мос тушади, индекс ва ушлаб туриш вакти булса бирга тенг булади.

            Шундай килиб, бир тактли функционал элементлардан тузилган хар кандай схема тескари богланиши булмаган автоматни ифодалайди. Аслида функционал элементлар биртактли булиши шарт эмас. Факатгина схеманинг куйи ва юкори индексларини бошкача хисоблаш керак:

             элементнинг куйи ва юкори индекслари деб, схеманинг киришларига берилган сигналлар  элементнинг чикишида хосил булгунча босиб утилган функционал элементлар ушлаб туриш вактлари йигиндисининг мос равишда минимуми ва максимумига айтилади.       

            Хар кандай тескари богланиши булмаган автомат уз навбатида битта функционал элементлардан тузилган схемани ифодалайди (ушбу фикрнинг тугрилигини исботлашни укувчига хавола этамиз).

            3-таъриф. Функционал элементлардан тузилган  схема билан ифодаланадиган автомат тескари богланиши булмаган  автоматидан факатгина ушлаб туриш вакти   билан фарк килса, бу автомат  автоматни реализация этади дейилади.

            4-таъриф. Агар хар кандай тескари богланиши булмаган автоматни  функционал элементлардан тузилган схема оркали реализация этиш мумкин булса, у холда функционал элементлар системаси кучсиз автоматли тулик система деб айтилади. Биртактли функционал элементлар системаси туликлигининг етарли ва зарур шарти элементлар системасининг кучсиз автоматли туликлик  шартига мос келади.

 

4-§. Тескари богланиши булган функционал элементлардан схемалар ясаш. Чекли автомат хакида умумий тушунчалар

Тескари богланишли функционал элементлар. -Хотирада сакловчи курилма. -Схеманинг (t+1) моментдаги холати. - автомат. -Автомат холатлари. -Автомат ишининг натижалари.

            Хозиргача бизлар функционал элементлардан ясалган тескари богланиши булмаган схемаларни куриб утдик. Бундай чеклашни биз нультактли функционал элементлардан схемалар ясаш масаласини ечиш учун куйган эдик, чунки, акс холда, бундай схемаларнинг иш жараёнини ёритиш мумкин эмасди.

 

 

 

 

 

 

 

 

 

                            15-шакл

15-шаклда курсатилган функцияни реализация киладиган схеманинг иш жараёнини куриб утайлик.  функционални биртактли элемент деб хисоблаймиз. Агар бирор  моментда  j нинг чикишида 1 сигнал пайдо булса, у вактда шу моментнинг узида уша сигнал унинг киришида пайдо булади ва  моментда унинг чикишида 0 сигнал пайдо булади ва хоказо. Натижада,  функционал элементнинг чикишида кетма-кет 1,0,1,0,1,0,...... сигналлар пайдо булади ва  нультактли функционал элемент булган вактдаги карама-каршиликлар уз-узидан йуколади. Бу схемани “кунгирок” схемаси деб аташ мумкин, чунки кунгирокда бир тактда карама-карши кийматларга узгарадиган кетма-кет бериладиган сигналлар фойдаланилади.

            Бу параграфда биз куйидаги шартларни каноатлантирувчи тескари  богланишли схемаларни куриб чикамиз:

            1) Курилманинг   элементлари орасида факат ва факат биттагинаси озод чикишга эга;

            2)  элементнинг хар бир кириши  элементларнинг факатгина биттасининг чикиши билан уланади.

            Юкоридаги шартларни каноатлантирувчи бир тактли функционал  элементлардан ясалган тескари богланишли схемаларнинг ишлаш жараёнини куриб утайлик. Схема тескари богланишли булганлиги учун унинг чикишидаги сигнал на факат схема киришларига берилган сигналлар мажмуидан, балки  унинг ички элементларининг чикишидаги сигналларга хам боглик булади. Бу кейинги сигналлар схема киришларига берилган сигналларга боглик булмаслиги хам мумкин ёки анча олдин берилган кириш сигналларига боглик  булиши  мумкин. Масалан, цикл элементларининг кириши схема кириши булмаслиги мумкин. 16 - шаклдаги  биртактли элемент   функцияни,  биртактли элементи булса  функцияни реализация киладилар. -бир-тактли ушлаб туриш элементи.

                                                 

                                              

               f                                  f                                        

              

 

                                                

               j                                 y

                                         

 

             x        y                       x   y   z

            

               а)                                 б)

                           16-шакл.

Агар 16,а - шаклдаги схеманинг  киришига исталганча анча олдин 1 сигнали берилган булса, у холда шу сигналнинг узи доимо унинг чикишида пайдо булиб туради (яъни  сигнал хотирада сакланади).

16,б-шаклдаги схемада  сигнал факат  булгандагина хотирада сакланади.  сигнални бериб, хотирани тозалашимиз мумкин. Шундан кейингина  нинг янги кийматини хотирада саклай оламиз ( кийматда). Реал схемаларда “хотирада сакловчи курилма” цикл ёрдамида реализация этилади.

            Тескари богланишли схема иш жараёнининг характеристикасини ифодалашда унинг ички элементларининг  холатини хисобга олиш керак.

             - тескари богланишли схема ва  - унинг элементлари булсин. Бу ерда  - чикиш элементи булсин, яъни озод чикишга эга булган элементдир.  элементнинг чикишидаги  вакт моментидаги сигналини  билан белгилаймиз ( 0 ёки 1 га тенг). Схема чикишида  моментдаги сигнал  га тенг булади.

             га  схеманинг  вакт моментидаги холати деб айтилади.  моментда  схема киришларига берилган сигналларни  билан ва  оркали уларнинг мажмуини белгилаймиз. У вактда схеманинг  моментдаги холати , схеманинг  моментдаги  ва  лари  оркали бир кийматли аникланади, яъни

=.

            Демак,  моментдаги элементларнинг чикишидаги сигналлар уларнинг киришларига  моментда берилган сигналларга боглик булар экан, яъни  моментда схеманинг киришларига берилган сигналлар ва элементларнинг шу моментдаги чикиш сигналларига богликдир. Аникроги,  аргументли та  мантик алгебраси функцияларининг мажмуидан (тупламидан) иборат булади. Бу  аргументларнинг айримлари сохта булиши мумкин. Масалан,  учун факат куйидаги аргументлар сохта эмас:  элементнинг киришларига чикишлар уланган функционал элементларга ва схеманинг киришлари бевосита  элементнинг хам киришлари деб хисобланадиган сигналларга мос келадиган аргументлар. Агар факат шундай сохта эмас аргументларни хисобга олсак, у вактда  функция  элемент реализация этадиган функцияга мос келади ва юкоридаги формула  вакт моментида  элементларнинг чикишларида  моментда уларнинг киришларига берилган сигналлар мажмуига боглик булган кандай сигнал пайдо булишини курсатади.

            Таъриф.  -  узунликдаги иккилик мажмуаларнинг бирор туплами булсин. Агар  аргументли  та кисман аникланган  мантик алгеб-расининг функцияларидан иборат  мажмуи курсатилган булса, у холда  рухсат этилган холатлар тупламида  киришга эга булган  автомат берилган деб айтамиз.

            Бу ерда  функциялар шундай  узунликдаги иккилик мажмуаларда аникланганки, улардан  та элементи  кирувчи мажмуа булади ва шу мажмуадаги  функцияларнинг киймати  га киради.  тупламдаги элементлар сонига автоматнинг хотираси деб айтилади. Агар автоматнинг бошлангич холати , бирор натурал сон   (ушлаб туриш вакти деб айтилади) ва хар бир вакт моментида  узунликдаги  кириш сигналлар мажмуи берилган булсалар, у холда  автоматнинг иш жараёни аникланган деб айтилади.

            Агарда автоматнинг иш жараёни аникланган булса, у вактда  лар учун унинг кетма-кет холатлари

=,  

формула оркали аникланади. Бу формулага автоматнинг холатлар тенгламаси деб айтилади. Равшанки, автоматнинг хар кандай вакт моментидаги холати  булади.  кетма-кетлигига автоматнинг чикиши (ишнинг натижаси) деб айтилади. Агар  ва  факатгина  га боглик булса, у холда  автомат мантик алгебрасининг функциясига айланади.

            Кабул килинган белгилашларда биртактли функционал элементлардан ясалган тескари богланишли  схема куйидаги характеристикага эга булган автоматни ифодалайди: ;  моментдаги  схема элементлар чикишла-ридаги сигналлари; -хамма мумкин булган элементлар чикишидаги сигналлар мажмуи.

            Шундай килиб  ушлаб туриш вактига эга булган чекли автоматни биртактли функционал элементлардан ясалган тескари богланишли схема оркали ифодалаш мумкин.

              

 5-§. Мили ва Мур автоматлари

 

Чекли автомат модели. -Автомат ишининг каноник тенгламаси. -Инициал ва ноинициал автоматлар. -Мили ва Мур автоматлари ва улар орасидаги муносабатлар.

 

Чекли хотирали дискрет курилмалар чекли автомат модели булади. Бу автоматнинг   та кириши,   та чикиши ва  чекли ички холати мавжуд.

            Чекли автомат дискрет вакт  моментларида ишлайди. Агар  моментдаги  киришнинг,  чикишнинг ва  холатининг кийматларини мос равишда (t),  ва  билан белгиласак, у холда автоматнинг иши куйидаги каноник тенглама билан ифодаланади:

                   ,,     ,

      ,                     (1)

            (1) тенгламалардаги  ва  функциялар мос равишда  - чикишнинг функцияси ва утишлар функцияси деб айтилади. Автоматнинг иш жараёнини аниклаш учун унинг бошлангич  холатини курсатиш керак.

            Агар  ва 1-моментдаги кириш кийматлари  маълум булса, у холда (1) каноник тенгламадан фойдаланиб 1-моментдаги чикиш  ва  холатнинг кийматини,  ва  асосида 2-моментдаги чикиш  ва  холатларини аниклаш мумкин ва х.к. Икки турдаги автоматлар мавжуд: - инициал ва инициалмас (ноинициал). Инициал автоматларда бошлангич холат тайинланган (махкамланган) булади. Ноинициал автоматларда бошлангич холат сифатида исталган холатни олиш мумкин.

            Ихтиёрий сондаги кириш ва чикишга эга булган автомат ишини аниклаш масаласи 1 та кириш ва 1 та чикишга эга булган автоматнинг ишини аниклаш масаласига келтирилади. Шунинг учун асосий модел сифатида 1 та  киришга ва 1 та  чикишга эга булган автоматларни курамиз. Бундай автоматлар куйидаги каноник тенглама билан ифодаланади:

,      .

Бундай турдаги автоматга Мили автомати деб айтилади.

            Мили автомати чекли хотирали дискрет курилманинг ягона модели эмас. Иккинчи модель - Мур автомати мавжуд. Мур автоматида  чикиш киймати уша моментнинг узидаёк ички холатнинг киймати билан аникланади. Мур автоматининг каноник тенгламаси куйидаги куринишда булади

,      .

            Агар биринчи тенгламадан иккинчисига  кийматини куйсак ва  деб белгиласак, у холда иккинчи тенглама куйидаги куринишга келади

, .

            Демак, Мур автоматини Мили автоматининг хусусий холи деб караш мумкин. Бу ерда утиш функцияси махсус  куринишда булади. Худди шундай, Мили автоматини хам (айрим маънода) Мур автоматига келтириш мумкин.

            Демак, хар кандай инициал ва ноинициал Мили автоматлари учун уларга эквивалент булган инициал ва ноинициал Мур автоматлари мавжуд (Исботи А.А.Шоломовнинг “Основы теории дискретных логических и вычислительных устройств” китобида мавжуд).

 

РЕЖА:

 

            1.Тескари богланиши булмаган автоматлар.

            2.Тескари богланиши булган функционал эле-

          ментлардан схемалар ясаш. Чекли автомат

          хакида умумий тушунчалар.

            3.Мили ва Мур автоматлари.

 

Муаммоли масала ва топшириклар:

 

1. Хар кандай тескари алокаси бœлмаган автоматни функционал элементлардан ясалган кандайдир схема оркали ифодалаш мумкинлигини исботланг.

2. Хар кандай инициал ва ноинициал Мили автоматлари учун уларга эквивалент булган инициал ва ноинициал Мур автоматлари мавжуд эканлигини исботланг(Исботи А.А.Шоломовнинг “Основы теории дискретных логических и вычислительных устройств” китобида мавжуд).

3. Хар кандай тескари богланиши б¢лмаган автоматни бирорта функционал элементлардан ясалган схема оркали ифодаланишини исботланг.

4. Хар кандай ишлаб туриш вакти n=1 б¢лган чекли автоматни бир тактли функционал элементлардан ясалган схема оркали ифодаланишини к¢рсатинг.

 

 

Мустакил ишлаш учун саволлар:

 

            1.Элементнинг юкори ва куйи индекси. Тœгри

          схема.

            2.Тескари богланиши булмаган автоматлар.

            3.Характеристик функция. Кучсиз автоматли

          тœлик система.

            4.Тескари богланиши булган функционал эле-         

          ментлардан схемалар ясаш.

            5.Чекли автомат хакида умумий тушунчалар.

            6.Мили ва Мур автоматлари ва улар орасидаги

          муносабатлар.

            7.Автомат ишининг каноник тенгламаси.

          Инициал ва ноинициал автоматлар.

 

 

6-§. Реле - контактли схемалар

 

Œтказгичлар. -Реле-контактли схемалар. -Манфий контактли реле. -Мусбат контактли реле. -Ушлаб туриш элементи. -Реле-контактли схема оркали функцияни реализация этиш.

 

           

                                         

       :

 

                 

                 

      :

                                 A

 

                

                               17-шакл.

 

Бу параграфда мантик алгебраси функцияларини реле - контактли схемалар оркали реализация этиш усулини курамиз.

            Агар хар бир утказгичга  узгарувчини мос килиб куйсак, у холда   да утказгичда ток бор ва  да утказгичда ток йук деб хисоблаймиз.

У вактда утказгичларни кетма-кет уланганига узгарувчиларнинг конъюнкцияси ва параллель-дизъюнкцияси мос келади (17-шакл). Утказгичларни кетма-кет ва параллель улаш натижасида схема хосил киламиз. Бу схема факатгина монотон функцияларни реализация этади, чунки конъюнкция ва дизъюнкцияларнинг суперпозицияси оркали факат монотон функцияларни ифодалаш мумкин. Ихтиёрий функцияларни реализация этиш учун  функцияни реализация этадиган курилма керак булади. Буни манфий контактли реле оркали реализация этиш мумкин. Бундай реленинг  схемаси  18-шаклда  тасвирланган. Агар  галтак урамлари оркали ток утмаса , у холда пружина  контактни юкорига тортади ва занжир уланади(туташади).  Натижада,  чикишда ток пайдо булади (). Агар  булса ва  галтак урами оркали ток утса, у холда контакт  пастга тортилади ва  чикишда ток булмайди, яъни  булади. Демак, манфий контактли реле  функцияни реализация этади. Агар  контакт киришига 1 урнига -  сигнал берсак, у холда биз у функцияни реализация этамиз (19-шакл).

                                           C

                 1                                                                   

 

                                                  

                

                            18-шакл.

 

 

                                                   

 

                 

 

                               19-шакл.

 

 

 

                                                 

                                

 

              

 

                             20-шакл.

 

Мусбат контактли реледа агар галтак урамида ток булса (), у холда В контакт уланади ва  чикишда ток булмайди  (). Шундай килиб,  функцияни мусбат контактли реле оркали реализация этиш мумкин (20-шакл).  Маълумки, агар утказгичда ток булса, у холда  хар тарафга таркалади. Масалан,  ни 17-шаклдаги схема оркали реализация этсак, у вактда  ва  булганда, ток  нуктадан хар тарафга, шу жумладан  утказгичга мос булган утказгич оркали хам утади ( булишига карамасдан). Бундай шароитда схеманинг иш жараёнида ноаникликлар пайдо булади. Бу холдан кутулиш учун факат бир томонга ток утказадиган асбоблардан, шу жумладан, мусбат контактли реледан фойдаланиш мумкин. Масалан, мусбат контактли реледан фойдаланиб,  ни реализация этадиган схемани 21-шаклда тасвирлангандай ясаш мумкин.

            Энди реле - контактли схеманинг ишлаш вактини куриб утайлик. Ток утказгичлар буйича бирданига таркалади ва реле ишлаши учун (контакт уланиши учун) бир такт вакт кетади деб хисоблаймиз. Демак, 19 ва 20-шаклларда  cигналга нисбатан  сигнали бир тактдан кейин берилиши керак. 

 

         

               

 

   1                                                                  

 

       

 

 

                              21-шакл.

            Схема чикишидаги сигнал ( ёки )  cигнал билан бир вактда пайдо булади. Шунинг учун схемада берилган сигналларни ишлаб чикиш учун сарф буладиган вактни доимо хисобга олиш керак, реализация буладиган функцияни узгартирмасдан, айрим вактларда, бу вактни узгартириш керак. Бу процедурани, худди биртактли функционал элементлардан ясалган куптактли схемаларда килганимиздай, ушлаб туриш элементлари ёрдами билан бажариш мумкин. Ушлаб туриш элементи вазифасини мусбат контактли реле бажаради (20-шакл). Ушлаб туриш вакти 1 тактга тенг булади.

            Таъриф. Агар реле-контактли схеманинг киришларига  моментда  сигналлар набори берилганда, унинг чикишида  моментда  сигнал пайдо булса, у холда реле-контактли схема  функцияни  ушлаб туриш вакти билан реализация этади деб айтилади.

Кетма-кет берилган сигналлар бир-бирига боглик булмаган холда ишлаб чикилади.               

 

                                                  

 

                                                                                                                            

    1                                                          

                                                                                                                                                 

 

                                                

 

                                 а)

 

 

 

                                    

 

                                                                

                    

                                                                                   

  1                                                             

                                                      

 

                                                                 

 

                                          

                              

                                    б)

 

 

 

 

 

 

 

                                                                 

                                                          

                                                          

  1                                                

                                                             

                               

                                                       

  

 

                                                         

                                     

                                   в)

 

                                  22-шакл.

 

Шундай килиб, мантик алгебрасининг исталган функциясини айрим ушлаб туриш вакти билан реле-контактли схема оркали реализация этиш мумкин. (Ушбу хулосани исбот килишни укувчига хавола этамиз).

            Мисол. а) ;    б) ;    в)  функциялар реле-контактли схема оркали реализаия этилсин.

            Берилган функцияларни схема оркали реализация этиш учун утказгичларни кетма-кет ва параллель улаш натижасида элементар конъюнкцияларни ва уларнинг дизъюнкцияларини реализация этамиз. Манфий контактли реледан фойдаланиб узгарувчиларнинг ва айрим элементар конъюнкцияларнинг инкорларини реализация этамиз. Мусбат контактли реле оркали сигналларнинг бир вактда етиб келишини таъминлаймиз. Натижада, 22-шаклда курсатилган схемаларга эга буламиз.

 

 

7-§. Контактли схемалар ва уларнинг синтези

 

Автоматнинг кириши. -Автоматнинг чикиши. -Контактларни параллел ва кетма-кет улаш. -Œтказувчанлик функцияси. -Мухим занжир. -П-схема.

 

            Хар бир автомат турлича контактли ёки контактсиз схемалардан фойдаланиш асосида тузилади. Биз контактли схемалар билан жихозланган автоматларнинг ишини умумий холда куриб утамиз.

                                         P₂                             

                        P₁

                                         P₃

                                                                                                         

        T₁                                               T₂

                        P₄         P₅  

 

                              

                              23-шакл.

 

            Масалан, 23-шаклда курсатилганидек, симлардан, иккита  ва  кутбдан, бешта  кнопка билан таъминланган контактлардан ясалган тузилма контактли схема деб айтилади.  кутб электр токи манбаини ифодалайди,  кутб эса автоматнинг “чикиши” да ишни бажарувчи курилмани билдиради. Автоматнинг “чикиши” да иш бажарилганлиги хакида хабар берувчи контрол лампочка урнатиш мумкинлигидан,  кутб мана шу лампочкани тасвирлайди деб айта оламиз.

            Схемада кнопкалар тегишли равишда ёкилса, ва демак, схема буйича ток юрадиган булиб контактлар тикланса,  кутбдан  кутбга борган ток контрол лампочкани ёндиради.

            Энди хар бир мураккаб контактли схеманинг таркибий кисмларини ташкил этувчи энг содда контактли схемалар билан танишамиз.

 

       

                                     Р

                                    

           Т₁                                             Т₂

                             

                            24-шакл.

 

            24-шаклдаги схема битта симдан,  ва  кутблардан ва  кнопкали битта контактдан ясалган.   

             кнопка ёкилганда, контакт тикланиб, ток схема буйича  дан  га томон юради ва контрол лампочка ёнади.  кнопка очик булганда контакт узилиб, ток булмайди ва лампочка ёнмайди.  кнопкага  - “ кнопка ёпик” деган мулохазани мос келтирамиз.  кнопка хакикатан ёпик булса,  мулохаза чин булади. Бу холда контрол лампочка ёнади.  кнопка очик булганда эса,  мулохаза ёлгон булади ва бу холда контрол лампочка ёнмайди.

            Шундай килиб, х мулохазанинг чин-ёлгонлиги билан ток бор-йуклиги (контрол лампочканинг ёниш-ёнмаслиги) орасида узаро бир кийматлик мослик урнатилади ва буни ушбу жадвал ифодалайди:

 

	схемада ток
ч	бор
ё	йук

 

            Энди кетма-кет уланган иккита  ва  кнопкали (икки кетма-кет контактли) схемани олайлик.

 

                                Р₁                Q

        Т₁                                                                                                Т₂

                                 

                                 25-шакл.

 

 ва  кнопкаларга мос равишда  -” кнопка ёпик” ва у -” кнопка ёпик” деган мулохазаларни келтирамиз.

 

		Cхемада ток
1	1	Бор	1
1	0	йук	0
0	1	йук	0
0	0	йук	0

 

            Демак, схемада ток бор-йуклиги  конъюнкциянинг чин-ёлгонлигига мос келади.

            Параллель холатда уланган икки  ва  кнопкали схемага мурожаат киламиз.

 

                                   Р

 

 

   Т₁                                                                                                           Т₂

                                   Q

                      

 

                              26-шакл.

 

		Cхемада ток
1	1	бор	1
1	0	бор	1
0	1	бор	1
0	0	йук	0

            Демак, параллель холатда уланган икки  ва  контактли схемада ток бор-йуклиги  дизъюнкциянинг чин-ёлгонлиги билан аникланади.

            25 ва 26-шаклларда берилган схемаларни умумлаштириб,  та  кнопкаларни кетма-кет ва шунингдек параллель улаш мумкин. Бунинг натижасида  та кетма-кет ва  та параллель контактли схемалар ясалган булади. Улар мос равишда  ва   функцияларни реализация этади, бу ерда  кнопка ёпик эканлигини билдиради.

            Шундай жуфт-жуфт кнопкалар билан таъминланган контактли схемаларни хам ясаш мумкинки, хар жуфт кнопканинг исталган бири ёпилганда (очилганда), иккинчиси очилади (ёпилади). Бир жуфт кнопка  ва  каби белгиланади.  кнопкага х мулохаза мос келганда,  га х нинг  инкорини мос келтириш табиийдир, чунки -ёпик, демак, х-чин булганда, -очик, демак, -ёлгон булади.

            Бир жуфт кнопкали энг содда схемалардан биттаси куйидагичадир:

                               Р              

         Т₁                                                                                             Т₂

 

                             27-шакл.

 

            Кнопкаларнинг биттаси очилганда, иккинчиси албатта ёпилгани учун, бундай схемада ток хеч качон булмайди. 27-шаклдаги схема жадвали куйидагича булади:

 

			cхемада ток
1	0	0	йук
0	1	0	йук

            Бир жуфт кнопкали схемаларнинг иккинчиси куйидагича булади:

 

                                      Р

 

 

          Т₁                                                                                            Т₂

                                       

                      

                             

                                 28-шакл.

 

            Бу схемада ток хар вакт бор, чунки  ёпик булса (у холда  очик булади), ток юкори симдан  оркали утади. Схема жадвали куйидагича булади:

 

			cхемада ток
1	0	1	бор
0	1	1	бор

 

            Шундай килиб, хар бир содда контактли схема мулохазалар алгебрасининг маълум бир функциясини реализация этади. Бу функцияга контакт схеманинг утказувчанлик функцияси деб айтилади. Биз куриб утган энг содда схемаларнинг утказувчанлик функциялари куйидагича булади:

       ,  ,  ,  ,            (1)

            Бу функцияларнинг чинлик жадваллари тегишли схемаларда качон ток булиши ва качон булмаслигини курсатади.

            Содда схемаларнинг турли комбинацияларидан, хар хил мураккаб контактли схемаларни тузиш мумкин. Бундай схемаларнинг хар бирига (1) функцияларнинг суперпозициясидан хосил этилган функциялар мос келади.

Масалан,

                                             

                                            Q      R

                   

 

                                  P       

                        

    Т₁                                                                       P                                 Т₂

                     Р         Q

                                              

 

 

cхеманинг утказувчанлик функциясини топайлик: Аввало, , ,  кнопкаларга мос равишда  мулохазаларни мос келтирамиз. У холда  ларга -  мулохазалар мос келади. Схеманинг юкори кисми  формула билан, пастки кисми  формула билан ифодаланади. Юкори ва пастки кисмлар параллель улангани учун бутун схеманинг утказувчанлик функцияси куйидагича булади:

.

            Аксинча, мулохазалар алгебрасининг хар бир функциясига кандайдир контактли схема мос келади.

Масалан,

                  (2)

функция ва  узгарувчиларга мос келадиган , ,  кнопкалар берилган булсин. У вактда (2) функцияга куйидаги контактли схема мос келади. 

 

 

 

                                                  ₁     

                 Р_{1              2}            

                                                   Р₂

                Р₂              Р₃                                                       T₂                

                                               

                                                     ₃             

 

 

            Бундан кейин, схемаларнинг куриниши оддий булиши учун, контактни икки кутбга эга булган кесма оркали ифодалаймиз (кесмани икки кутбли деб айтамиз). Агар кесма уланувчи булса, уни  билан, ажратувчи булса,  билан белгилаймиз. Бу ерда  - галтакда реализация этиладиган узгарувчи. Хар бир галтакка битта узгарувчи мос келади ва у билан исталганча сон контактлар уланиши мумкин. Кесмалар кутблари оркали бир-бирлари билан уланади. Хар бир схема кириш ва чикишга эга булади. Схеманинг киришига ток берилганда, унинг чикишида бир тактдан кейин ток пайдо булса, у холда схемада утказувчанлик бор деб айтилади, акс холда, утказувчанлик йук деб айтилади.

            29-шаклдагидай кесмаларнинг кетма-кет уланишига занжир деб айтамиз.

 

                                         

                                                                  ^{.....................}                              

 

29-шакл.

 

                Занжирда битта контакт бир неча марта катнашиши мумкин. Биринчи контактнинг кириши схеманинг киришига ва охирги контактнинг чикиши схеманинг чикишига тугри келади. Узгарувчиларнинг бирор кийматлари мажмуида схеманинг (ДНШ куринишидаги функцияни реализация этадиган схеманинг) чикишида ток булиши учун хеч булмаганда бирорта занжирнинг хамма контактлари уланган булиши етарли ва зарурдир. Агар схемага кирувчи хар бир  занжирга узгарувчиларнинг ёки улар инкорларининг  элементар конъюнкциясини мос килиб куйсак, у вактда схемага кирувчи занжирларга мос келган  элементар конъюнкцияларнинг дизъюнкциясига схеманинг утказувчанлик функцияси мос келади.

            Шуни таъкидлаш керакки, схеманинг утказувчанлик функциясини хосил килиш учун айрим занжирларнинг дизъюнкциясини олиш кифоядир.

            1-таъриф. Хар бир кутбдан бир марта утган занжирга мухим (жиддий) занжир деб айтилади (яъни схеманинг кириши ва чикишига биттадан контакт ва занжирнинг колган кутбларига иккитадан контакт тугри келадиган занжирга мухим занжир деб айтилади).

 

 

                                          

                                                       

                                           

                                                             

                                                       

                                                        

                                       

                а)                     б)                   в)  

 

                              30-шакл.

 

Мисол. 1. Хар бир схемада чекли сондаги мухим занжирлар мавжуд булишини исбот килинг.

            2. Мухим занжирларга мос келувчи конъюнкцияларнинг дизъюнкцияси схеманинг утказувчанлик функциясига тенгкучли эканлигини исбот килинг.

            Иккинчи мисолнинг натижасига асосан, схемага караб унинг утказувчанлик функциясини ёзиш мумкин.

            30-шаклда берилган схемаларнинг утказувчанлик функцияларини топайлик. Бундан кейин рангсиз доирача билан схеманинг кириши ва рангли доирача билан схеманинг чикиши белгиланади.

    а)

    б)

    в)  лар шаклнинг мос равишда а), б) ва в) бандларида курсатилган схемаларнинг утказувчанлик функциялари булади.

            Энди тескари масалани курайлик, яъни берилган функцияга караб уни реализация этадиган схемани ясаш масаласини курамиз. Бунинг учун функцияни ДНШ куринишига келтирамиз. ДНШ ифодасидаги хар бир .... элементар конъюнкцияга мос равишда битта  кетма-кет уланган контактларни куямиз (29-шаклга каранг). Бундан кейин хамма киришларни ва чикишларни мос равишда айнан туташтирамиз. Хосил этилган схема ДНШ куринишидаги функцияни реализация этади.

            Берилган а)б)  ва в)  функцияларни контакт схемалар оркали реализация этайлик. Бунинг учун функцияларни ДНШ куринишига келтирамиз:

    а)  (31,а-шакл).

    б)

          (31,б-шакл).

    в)  (31,в-шакл).

 

 

 

                                                         

 

                                                        

                                                           

                                                          

                                                          

                                                         

 

                                                                  

             а)                   б)                       в)  

 

31-шакл.

 

            Биз юкорида ДНШ куринишидаги функцияни контакт схема оркали реализация этишни курдик. Табиийки, КНШ куринишидаги функцияни хам контакт схема оркали реализация этиш мумкин. Бунинг учун, биринчи навбатда, хар бир элементар дизъюнкцияларни реализация этадиган схемалар тузамиз (32-шакл).Иккинчи навбатда, элементар дизъюнкцияларга мос келган

 

                    

        

                      

           

                             

               

          32-шакл.                   33-шакл.      

 

 

 

схемаларнинг биттасининг чикишини иккинчисининг киришига, иккинчисининг чикишини учинчисининг киришига ва хоказо улаб чикамиз (33-шакл). Биринчисининг кириши контакт схеманинг кириши ва охиргисининг чикиши - чикиши булади. Хосил этилган схема КНШ куринишдаги функцияни реализация этади.

            Юкорида келтирилган алгоритмдан фойдаланиб, а)б)  ва в)  функцияларни контакт схемалар оркали реализация этиш талаб этилсин.

                                            

      

         

                                                            

                   а)                        б)

  

                                                                                

 

                                                                 

 

        

                                                                 

                    в) 

34-шакл.

 

            а)  функцияни КНШ куринишига келтирамиз ва уни соддалаштириш учун куйидаги бизга таниш

            ,                       ,

            ,                ,

            ,               

булган тенгкучли формулалардан фойдаланамиз:

      (34,а-шакл)

 

    б)

      =  (34,б-шакл)

    в)  (34,в-шакл)                         

                Параллель - кетма-кет улаш натижасида хосил этилган схемалар классини индуктив тарзда ифодалайлик

            2-таъриф. Бир контактдан иборат схема элементар схема деб айтилади. Элементар схемаларнинг айримларини чекли сон марта параллель ва кетма-кет улаш натижасида хосил булган контакт схемага параллель - кетма-кет схема ёки П-схема деб айтилади.

            Равшанки, элементар схемалардан хар кандай усул билан ясалган П-схемага дизъюнкция, конъюнкция ва инкор амаллари билан ифодаланган утказувчанлик функцияси мос келади ва, аксинча, хар кандай шундай функция учун маълум П-схема ясаш мумкин.

            Изох. Хар кандай контакт схема П-схема булаолмайди.

Мисол. Берилган  ва  функциялар учун П-схемалар ясаш талаб этилсин.

            а) , , , ,  ларни реализация этадиган элементар схемаларни тузамиз (35-шакл).

                                                       

  

35-шакл.

 ва  узгарувчиларга мос булган контактлар икки донадан булиши керак. Энди контактларни кетма-кет улаб, ,  ва  элементар конъюнкцияларни реализация этамиз (36-шакл).

                                                       

 

                               36-шакл.

 

     Учинчи кадамда, параллель улашдан фойдаланиб,  ва  функцияларни реализация этамиз (37-шакл).

                     

                                                     

                               

 

                                                                                                

 

37-шакл.

 

            Хосил этилган схемаларни кетма-кет улаб, берилган   функцияни реализация этадиган П-схемага эга буламиз (38-шакл).

 

                                                    

 

                    

 

 

                                                                           

 

38-шакл.

 

            б) функцияни реализация этадиган П-схема 39-шаклда курсатилган.

                                                        

 а)        

 

            

                                                           

                                                  

    б)                                           

        

                                                            

                                                          

                                  

                                             

   

       в)                                       

                                   

      

                            39-шакл.

 

 

 

8-§. Контакт схемаларни минималлаштириш муаммоси

 

Минимал схема. -Схемаларни минималлаштириш муаммоси. -Минимал схема бœлишнинг шарти. -Шеннон функцияси. -Контактлар сонини бахолаш.

 

            Маълумки, битта функциянинг узини хар хил контактли схемалар оркали реализация этиш мумкин, чунки функциянинг ДНШ (КНШ) куриниши ягона эмас. Функцияни контакт схема оркали реализация этишда, табиийки, схемада мавжуд булган контактлар сони мумкин булгунча энг кам булишига ёки, хеч булмаганда, шу энг кам сондан салгина ортикрок булишига интиламиз. Битта утказувчанлик функциясига эга булган хамма схемалар ичида мумкин булгунча энг кам сонли контактга эга булган схемага минимал схема деб айтилади.

            Мантикий алгебра функцияларини минимал схемалар оркали реализация этиш муаммосини ечиш жуда катта илмий - амалий ахамиятга эга булган актуал муаммодир. Афсуски, аник схемаларнинг минимал схема эканлигини исботлаш айрим холлардагина мумкин.

            Схемаларни минималлаштириш муаммоси мантик алгебраси функцияларини минималлаштириш муаммоси билан чамбарчас боглангандир.

            Айрим  холларда берилган схеманинг минимал схема эканлигини курсатадиган хусусиятларни топиш мумкин. Буни мисолларда курайлик. 40-шаклда курсатилга “куприкча” минимал схема эканлигини исботлайлик.

            Агар бирорта узгарувчи функциянинг сохта эмас (мухим) аргументи булса, у холда ушбу функцияни реализация этадиган схемада камида уша узгарувчига мос келадиган бир дона контакт мавжуд булиши керак. “Куприкча” реализация этадиган утказувчанлик функцияси  булади. Бу функциянинг хамма  аргументлари мухим аргументлардир (масалан, ,  булганда, функциянинг киймати  га боглик булади;  булганда функциянинг киймати  га боглик булади ва хоказо). Схемада бу аргументларга мос келган контактлар бир мартадан катнашган. Демак, “куприкча” схемаси минимал схемадир.

            Шундай килиб, агар схемадаги контактлар хар хил узгарувчиларга мос келса ва бу узгарувчилар утказувчанлик функциясининг мухим аргументлари булса, у вактда схема минимал схема булади.

            Энди 40-шаклда ифодаланган схема минимал схема булишини курсатайлик.

 

             _{2         3                                  n-1}

    ₁                                                 ^{........................}                             _n

                                                                     

                         

     ₁                                                ^{......................}                              _n

               _{2        3                                     n-1}

 

                         40-шакл.

 

            Берилган ихтиёрий схемада ₁ узгарувчига мос  булган контактлар факатгина мусбат контактли булсин. У вактда  утказувчанлик функцияси учун

муносабат хамма  лар учун бажарилади (агар схемада айрим контактлар уланган булса, у холда схемада утказувчанлик йуколмайди). Худди шундай, ягар x₁ га факатгина манфий контактли контактлар мос келса, у холда

муносабат хамма  учун бажарилади.

            Шундай сигналлар мажмуи  мавжуд булсинким,  бажарилсин. У вактда  функция ₁ аргументи буйича купаймайди ва  фунцкцияни реализация этадиган хар кандай схемада ₁ га мос булган манфий контактли контакт бор деб айтамиз.

            Худди шундай,  (b₂,......, b_n) мажмуа учун

бажарилса, у вактда  функция ₁ аргументи буйича камаймайди ва  ни реализация этадиган схемада ₁ га мос мусбат контакт бор деб айтамиз. Агарда  функция ₁ аргументи буйича на камаювчи ва на усувчи функция булса, у вактда  функцияни реализация этувчи схемада ₁ аргумент буйича хам манфий ва хам мусбат контактлар мавжуд булади. 41-шаклдаги схеманинг утказувчанлик функциясининг куриниши  булади.  да  функция ₁ аргументи буйича купаювчи булмайди ва  да - камаювчи булмайди. Курилаётган функция хамма аргументларига нисбатан симметрик булгани учун, колган хамма аргументлари буйича хам купаювчи ва камаювчи функция булмайди. Курилаётган схемада хар бир узгарувчига мусбат ва манфий контакт тугри келгани учун бу схема минимал схема булади.

            Демак, агар схемада хар бир узгарувчига биттадан мусбат ва манфий контакт мос келса, функциянинг хамма аргументлари мухим аргументлар булса ва бу узгарувчилар буйича функция усувчи хам камаювчи хам булмаса, у холда схема минимал схема булади.

             функцияни реализация этадиган 41-шаклдаги схемадан фарк киладиган минимал схема тузиш талаб этилсин. Бунинг учун  функцияни

куринишдаги КНШга келтирамиз ва уни реализация этадиган схема минимал  булади (42-шакл).

                                                    

 

                                      ..........

 

                                                        

                             41-шакл.

            Демак, битта функцияни хар хил минимал схемалар оркали реализация этиш мумкин экан, яъни минимал схема ягона эмас.

            П-схемалар тупламида (классида) хам минимал схемалар мавжуд булади. Минимал П-схема хамма схемалар классида хам минимал схема булаоладими ёки йукми деган савол тугилади.

            “Куприкча” минимал схемаси оркали реализация этилган  функция учун 5 контактли П-схема мавжуд эмаслиги куйилган саволга жавоб беради.

             мантик алгебрасининг функцияси булсин.  оркали уни реализация этадиган минимал схемадаги контактлар сонини ва  схемадаги контактлар сонини белгилаймиз. У вактда

£

булади. max  ва  ларга Шеннон функциялари деб айтилади.  аргументли  функцияни схема оркали реализация этиш учун зарур булган максимал ва минимал контактлар сонини топиш масаласи катта амалий ахамиятга эга эканлиги хаммамизга маълум. Илмий изланишлар хозирги вактда куйидаги бахони беради

                                  

 

РЕЖА:

 

            1.Реле - контактли схемалар.

            2.Контактли схемалар ва уларнинг синтези.

            3.Контакт схемаларни минималлаштириш

            муаммоси.

 

 

Муаммоли масала ва топшириклар:

1.      а);      б);   в);

        г);    д);    е); 

        ж); з);   и)

функцияларни реализация этадиган реле-контактли схемалар ясанг.

 

2. Хар бир схемада чекли сондаги мухим занжирлар мавжуд булишини исбот килинг.

 

3. Мухим занжирларга мос келувчи конъюнкцияларнинг дизъюнкцияси схеманинг утказувчанлик функциясига тенгкучли эканлигини исбот килинг.

Мисолнинг натижасига асосан, схемага караб унинг утказувчанлик функциясини ёзинг.

 

4. Хар кандай контакт схема П-схема б¢ла олмаслигини исботланг.

5.

               

         

функцияларни реализация этадиган П-схемаларни топинг.

            42-шаклда курсатилган схема (“куприкча”) П-схема булаолмаслигини исботланг.

 

                                               

 

                                     

 

                       

                                            

 

42-шакл.

6. Агар куйидагилар аник бœлса, у холда тœртта талабадан кайси бири имтихон топширган:

1) Агар биринчи талаба имтихон топширган бœлса, у холда иккинчиси хам топширган.

2) Агар иккинчи талаба имтихон топширган бœлса, у холда учинчиси топширган ёки биринчиси топширмаган.

3) Агар тœртинчи талаба имтихон топширмаган бœлса, у холда биринчиси топширган ва учинчиси топширмаган.

4) Агар тœртинчи талаба имтихон топширган бœлса, у холда биринчиси хам топширган.

 

7. Тœртта дœст – Сафаров (С), Бекмуродов (Б), Ходжаев (Х), Азизов (А) мехнат таътилларини (отпускаларини) тœртта хар хил шахарларда Тошкент, Бухоро, Самарканд ва Фаргонада œтказишга келишдилар.

Куйидаги чеклашлар мавжуд бœлган холда уларнинг хар бири кайси шахарга боришини аниланг:

                1) Агар С Тошкентга борамаса, у холда Х Бухорога бормайди.

2) Агар Б Тошкентга хам, Фаргонага хам бормаса, у холда С Тошкентга боради.

                 3) Агар Х Фаргонага бормаса, у холда Б Самаркандга боради.

                4) Агар А Тошкентга бормаса, у холда Б Тошкентга бормайди.

                 5) Агар А Бухорога бормаса, у холда Б Тошкентга бормайди.

 

8. Терговчи бир вактда учта шохидни сœрок килди: Донакулни, Тошпœлатни ва Косимни. Уларнинг кœсатмалари бир-бириникига карама-карши эди ва уларнинг хар бири кимнидир ёлгончиликда айбларди:

             1) Донакул Тошпœлатни ёлгон кœрсатма бераяпти деб айбларди.

2) Тошпœлат Косимни ёлгончи деб айбларди.