1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
| 3.4. ЛОГИКА АЛГЕБРАСЫ
1. Логика алгебрасының функциялар Айталық U-{u1,и2,...,иm,...} - айнымалылардың бастапқы алфавиті болсын. Аргументтері E2={О,1} жиынында анықталған және аiÎЕ2(і = 1,2,...,n), егер аiÎЕ2(і = 1,2,...,п) шартын қанағаттандыратын ƒ(u ,u ,…,u ) функциялары қарастырылады. Бұл функциялар логика алгебрасыныц функциялары немесе буль фунщиялары деп аталады. Р2 арқылы U алфавитінде берілген, сондай-ақ 0 және 1 тұрақтыларын қамтитын барлық логика алгебрасының функциялар жүйесін белгілейміз. Теорема. х1,х2,...,хn п айнымалыға тәуелді Р2 жиынындағы барлық функциялар саны P2 (n) - 22 -ге тең. Логика алгебрасы функцияларың мысалдары: ƒ1(x) =0 -тұрақты 0 ƒ2(x) =1-тұрақты 1; ƒ3(x)=x –тепе-тең функция; ƒ4(x)= - х -ті жоққа шығару; ƒ5(x1,x2)= (x1&x2) - x1 мен x2 –нің конъюнкциясы (логикалық көбейту); ƒ6(x1,x2)= (x1∨x2) - x1 мен x2 –нің дизъюнкциясы (логикальщ қосу); ƒ6(x1,x2)=Бұл функциялардың мәні. xx 0 0 11 xx 00 00 11 00 11 11 00 11 11 00 x1 x2 (х1&х2) (x1∨x2) (х1→х2) (x1Åx2) (x1\x2) (x1 ~x2) (х1↓x2) 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 4.1
Автоматтар теориясы — теориялық кибернетиканың дискретті ақпараттың түрлендіргіштерін зерттейтін саласы. Ол есептеуіш машиналарды жобалауға және биол., экон., т.б. күнделікті өмір талабы аса қажет еткен ғылым салаларындағы ақпараттарды қайта өндеу процестерінің матем. модельдерін жасауға байланысты пайда болды. Автоматтар теориясының негізі абстракт автомат пен автоматтар композициясы ұғымдарынан тұрады. Абстракт автомат ұғымы қарастырылатын қондырғыны, яғни өзі жүзеге асыратын ақпараттарды қайта өңдеу алгоритмі түрғысынан сипаттайды. Автоматтар композициясы қондырғыны оның құрылысы тұрғысынан қарастырады. Қазіргі автоматтар теориясының— сан алуан мәселелері бар және жан-жақты қолданылатын дербес ғылым саласы. Автоматтар теориясы абстрактілі автоматтарды - математикалық модельдер ретінде ұсынылған компьютерлерді және олар шеше алатын есептерді зерттейтін дискретті математиканың бөлімі болып табылады.Автоматтар теориясы алгоритмдер теориясымен ең тығыз байланысты: автомат қадамдар бойынша дискретті ақпаратты уақыттың дискретті моменттеріне түрлендіреді және берілген алгоритм қадамдары бойынша нәтиже шығарады. Жартылай сақиналарды, формальды дәрежелік қатарларды, ағаштар үстіндегі формальды қатарларды, бекітілген нүктелер теориясын және матрицалық теорияны қолданатын автоматтар теориясының алгебралық өңдеуі бар. Бұл дәріс жоспарына информатика саласындағы негізгі модельдер аппараты кіреді: жиындар теориясының түсініктері, буль алгебрасы, ұсыныстар мен предикаттардың формальды логикасы, графиктер, т.б. сонымен қатар информатиканың бір саласы, онсыз автоматтар теориясын құру мүмкін емес. Сонымен қатар, алгоритмдер теориясының және Тьюринг машинасының негізгі түсініктері, сонымен қатар автоматтық жүйелердегі параллель процестерді модельдеу үшін Петри торларын қолдану туралы қысқаша ақпарат берілген. Автомат «жалпы» – басқару жүйесі, ол шектеулі автомат немесе оның құрамдас бөліктерін немесе жұмыс істеуін өзгерту арқылы алынған оның кейбір модификациялары. «Ақырлы автомат» негізгі ұғымы 20 ғасырдың ортасында пайда болды. Жүйке жүйесінің, әмбебап компьютерлердің және басқа да нақты автоматтардың жұмысын математикалық тілде сипаттау әрекеттеріне байланысты. Бұл сипаттаудың сипатты белгісі сәйкес математикалық модельдердің дискреттілігі және олардың параметрлерінің диапазондарының шектілігі болып табылады, бұл ақырлы автомат ұғымына әкеледі. Автоматтар теориясындағы мәселелердің көпшілігі басқару жүйелерінің негізгі түрлеріне ортақ. Оларға автоматтарды талдау және синтездеу есептері, толықтық, минимизациялау мәселелері, автоматтардың эквивалентті түрлендірулері және т.б. Талдаудың міндеті - берілген автоматтың әрекетін сипаттау немесе автомат және оның жұмыс істеуі туралы толық емес мәліметтер негізінде оның бір немесе басқа қасиеттерін белгілеу. Автомат синтезінің міндеті берілген мінез-құлық немесе операция бар автомат құру болып табылады. Жалпы жағдайда эквивалентті түрлендірулердің міндеті белгілі бір шарттарды қанағаттандыратын және ерікті автоматты кез келген эквивалентке түрлендіруге мүмкіндік беретін автоматтарды түрлендіру ережелерінің жүйесін табу болып табылады. Автоматтың әрекеті - автоматтың қоршаған ортамен әрекеттесуін сипаттайтын математикалық түсінік. Автомат ұғымы әртүрлі ғылыми және қолданбалы зерттеулерде автоматтар теориясын қолдануға мүмкіндік беретін көптеген мәселелерде үлгі нысаны бола алады. Бұл теорияға үлкен қызығушылық оны қолданудың кең мүмкіндіктеріне байланысты. Автоматтар теориясы қазіргі теориялық және практикалық информатиканың іргелі блоктарының бірі болып табылады деп артық айтпауға болады. Математиканың негізгі, бастапқы, ұғымдарының бірі жиын және оның элементтері туралы түсініктер. Жиын деп біз санауға жататын, жиындардың элементтері деп аталатын бір-бірінен өзгеше, бірақ бір типті объектілердің жиынтығын түсінеміз. Осылайша, жиын элементтерден тұрады. Жиындарды латын әліпбиінің бас әріптерімен (A,B,C,…,Z), ал жиындардың элементтерін кіші әріптермен (a,b,c,...,z), сандармен және сандармен белгілеу әдетке айналған. сәйкестендіру өрнектері. Жиындардың мысалдары: натурал сандар жиыны, топтағы студенттер жиыны, факультеттегі топтар жиыны және т.б. Жиындар шекті болуы мүмкін. Яғни,элементтердің шектеулі саны бар жиындар және шексіз. Курстың қолданбалы мәнін және оны ақырлы автоматтар синтезінің негіздерін оқу үшін пайдалануды ескере отырып, біз шекті жиындарды қарастырамыз. Шекті M жиынындағы элементтер саны кардиналдық деп аталады және |М| арқылы белгіленеді. Егер жиында элементтер болмаса, онда ол бос деп аталады. Бос жиын кез келген жиынның ішкі жиыны болып табылады деп жалпы қабылданған. Жиын санау (элементтер тізімі), генерациялау процедурасы немесе оның элементтері болуы тиіс сипаттамалық қасиеттердің сипаттамасы арқылы анықталуы мүмкін. Тізім ретінде тек ақырлы жиындарды көрсетуге болады. Тізім бұйра жақшаға алынған. Мысалы, A = {a, b, d, h} А жиынының a, b, d және h төрт элементтен тұратынын білдіреді. Соңғы автоматтың формальды анықтамасы. Автоматты 5 кортежбен көрсетуге болады (Q, ∑, δ, q 0 , F), мұндағы – Q – күйлердің шекті жиыны. ∑ — автомат алфавиті деп аталатын шекті белгілер жиынтығы. δ – ауысу функциясы. q 0 – кез келген кіріс өңделетін бастапқы күй (q 0 ∈ Q). F - соңғы күйлердің / Q күйлерінің жиыны (F ⊆ Q). Q – күйлердің шекті жиыны. ∑ — автомат алфавиті деп аталатын шекті белгілер жиынтығы. δ – ауысу функциясы. q 0 – кез келген кіріс өңделетін бастапқы күй (q 0 ∈ Q). F - соңғы күйлердің / Q күйлерінің жиыны (F ⊆ Q). жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|