Жұмыс бағдарламасы мамандықтың жұмыс оқу жоспары және 20 ж бекітілген элективті пәндер каталогы негізінде әзірленген

Изоморфизм – математикалық нысандардың (объектілердің) не нысандар жүйесінің арасындағы сәйкестікті (қатысты), кейбір жағдайда олардың құрылысының теңдігін де көрсететін негізгі ұғымдарының бірі. Математикада изоморфтық ұғымы нақты алгебралық жүйелерге (ең алдымен топқа) қолдануға байланысты қалыптасты. Кейін ол математикалық құрылымдардың кең класына (мысалы, сақина, өріс, т.б.) қолданыла бастады. Изоморфты жүйелердің қарапайым мысалы ретінде, қосу амалы (x=x₁+x₂), берілген барлық нақты сандар (R) жүйесі мен көбейту амалы (y=y₁·y₂), берілген оң сандар жүйесі (R+) қарастырылады. Осы екі жүйенің ішкі “құрылысы” бірдей болатындығын дәлелдеуге болады. Ол үшін, R-дің x санын R+-дің y=ax, (a>1) санына сәйкес қоя отырып, R жүйесін R+ жүйесіне бейнелеу жеткілікті. Сонда x=x₁+x₂ сандарының қосындысы, x₁ және x₂ сандарына сәйкес келетін және сандарының y=y₁·y₂ көбейтіндісіне сәйкес келеді. R+-дің R-ге кері бейнеленуінің түрі мынадай: x=log_ay·R+ сандар жүйесінің қосындысына қатысты кез келген сөйлемнен оған сәйкес келетін R+ сандар жүйесінің көбейтіндісіне қатысты сөйлемді шығарып алуға болады. Мысалы, егер R-дегі арифметикалық прогрессия мүшелерінің қосындысы (s_n=x₁+x₂+...+x_n) мына s_n= формуласымен өрнектелсе, онда R+-дегі геометриялық прогрессия мүшелерінің көбейтіндісі (pn=y1·y2...yn) мына: pn= формуласымен өрнектеледі. Бұл жерде, R жүйесінен R+ жүйесіне ауысу кезінде: R-дегі n-ге көбейту амалы R+-дегі n-ге дәрежелеу амалына, ал екіге бөлу амалы квадрат түбір табу амалына сәйкес келеді. Топологияда маңызды рөл атқаратын гомеоморфтық ұғымы изоморфтық ұғымының дербес бір түрі болып есептеледі. Ал алгебралық жүйенің өзіне-өзінің изоморфтығы (бір мәнді бейнеленуі) автоморфтық деп аталады. “Изоморфтық” термині математикаға 19 ғасырдың ортасында енді. Оның қазіргі анықтамасы неміс математигі Э. Нeтердің (1882 – 1935) еңбектерінде қалыптасты.

Гоморфизм, изоморфизм және морфизм түсініктерін нақтылайтын біршама жалпы теориясы "Жиындар теориясы" атты кітабында Н. Бурбаки белгілі француз математиктер тобымен ұсынылған.

Анықтама:σ cигнатурасының 𝔐₁=1,σ> және 𝔐₂=2,σ> алгебралық жүйелері берілсін. Егер f: M_1⟶ M₂ бейнелеуі

1) g және h-m орынды алгебралық амалдары σ сигнатурасының m орынды F фукционалдық символының 𝔐₁ және 𝔐₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болып, кез келген a₁,….,a_mϵ M₁ элементтері үшін f(g(a₁,….,a_m))=h(f(a₁),…..,f(a_m)) теңдігі орындалады.

2) Сәйкес M₁ және M₂ жиындарында анықталған P және S-n орынды қатынастары σ сигнатурасының қандай да бір n орынды R предикаттық символының 𝔐₁ және 𝔐₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болса, кез келген a₁,….,a_mϵ M₁ элeменттері үшін қатынасы орындалғанда S(f(a₁),…..,f(a_n)) қатынасы да орындалады.

3) Егер a_k ϵ M₁ және b_k ϵ M₂ элементтері σ сигнатурасының c_k константа символының 𝔐₁ және 𝔐₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болса, онда f(a_k)=b_k теңдігі орындалады. Шарттарын қанағаттандырса, онда f: M_1⟶ M₂ бейнелеуін 𝔐₁ алгебралық жүйесінен 𝔐₂ алгебралық жүйесі гомоморфизм деп аталады. M₁ жиынының f бойынша алғашқы бейнелері бар элементтер жиыны 𝔐₁ алгебралық жүйесінің гомоморфрты бейнесі деп аталады. Ол элементтерден тұратын жиын σ сигнатурасының 𝔐₂ алгебралық жүйесіне сәйкес интерпретациясы бойынша σ сигнатурасының алгебралық жүйесі болады. Бұл алгебралық жүйелер арасындағы гомомофризмді f: 𝔐_{1 ⟶} 𝔐₂ арқылы белгілейміз.

Егер f: 𝔐_{1 ⟶} 𝔐₂ гомоморфризм және f(M₁₎₌M₂ болса, мұндай гомоморфризм эпиморфизм деп аталады. Ал 𝔐₂ алгебралық жүйесін 𝔐₁ алгебралық жүйесінің эпиморфты бейнесі дейді.

Егер f: 𝔐_{1 ⟶} 𝔐₂ эпиморфизм және f өзара әрменді сәйкестік және екінші шарт екі жақты болса, оны 𝔐₁ және 𝔐₂ алгебралық жүйелерінің изоморфизмі деп аталады. Ал аралында изоморфизм болатын 𝔐₁ және 𝔐₂ алгебралық жүйелері изоморфты деп аталып, бұл жағдай 𝔐₁=𝔐₂ арқылы белгіленеді

Бұл анықтамалардан кез келген қатаң гомоморфизм ауқатты болып табылатыны анықталады.

Осы барлық түсініктердің дифференциалды меңгеру үшін келесілер бар болатынын көрсететін қарапайым мысалдарын өз бетінше құру болып табылады:

- биективті гомоморфизмдер, яғни, бірінші жүйенің негізгі жиынын изомоморфизмамдер болып табыламайтын екінші жүйенің негізгі жиынын бейнелейтін биективті гомоморфизмдер;

- не қатаң, не ауқатты болып табыламайтын гомоморфизмдер;

- ауқатты болып саналатын, бірақ қатаң емес гомоморфизмдер.

6 Формальды тілдердің синтаксистық құрамының алгебралық құрылымы

Логикалық есептеу белгілі бір формальды тілдің негізінде құрылады. Формальды тілдің құрылымы төменде келтірілген (А.Черч бойынша):

1) Тілде (алфавитте) қолданылатын біркелкі бөлінбейтін алғашқы символдар теріп жазылады;

2) Соңғы алғашқы символдардың тізбегі формулаға айналады (формулалар жиыны);

3) Барлық формулалардың ішінен белгілі бір ережеге сәйкес дұрыс құрылған формулалар анықталады, олардың кейбіреулері аксиома болып табылады (аксиомалар жиыны);

4) Қорытынды ережелерді шығару реті анықталады, дұрыс құрылған формулалардың ішінен қорытынды ретінде дұрыс құрылған формула анықталады (қорытынды ережелер жиынтығы).

Құрылған формальды тіл тиімділік талаптарына сай болу керек:

- кез-келген таңбаның бастапқы таңбаның (алфавиттың) бірі болып табылатынын тиімді анықтайтын әдістің болуы;

- кез-келген формуланың (алфавиттың символдарынан құралған) дұрыс құрылғандығын тиімді анықтайтын әдістің болуы;

- кез-келген формуланың (алфавиттың символдарынан құралған) аксиома болатындығын тиімді анықтайтын әдістің болуы;

- кез-келген дұрыс құрылған формуланың қорытынды болатынын тиімді анықтайтын әдістің болуы.

Формальды тілді қолданудың ережесі адам түсінетін тілде берілуі керек (мұндай тіл метатіл деп аталады).

Формальды тіл бағдарламау тілдерінің негізі болып табылады. Бағдарламалу тілі – белгілі бір символдар жиынынан құрылған, ке-келген уақытта толықтыруға келетін ашық жиын. Кез-келген тіл (табиғи, формальды, бағдарламалау) синтаксис және семантикадан тұрады.

Формальды тілдердің синтаксисы сол тілдің сөйлемдерін құру ережесі жүйесінен және сол сөйлемдердің дұрыс құрылған формулалар, аксиомалар, теоремалар, қорытындылар немесе дәлелдеулер болатындығын тексеретіндей болу керек.

Бағдарламалау тілінің синтаксисы – кез-келген бағдарламмаға қойылатын талаптардан тұрады (мәтіндерді құру ережесі). Бағдарламаға синтаксистық талдау қандай бөліктерден тұратынын, бағдарламалардың қандай жолмен құрылатынын, аталмыш бағдарламаның символдарының оқылу ретін анықтау арқылы жүргізіледі.

Формальды тілдердің құрылу әдісін анықтау кезінде, оның синтаксистық ерекшеліктерін және мүмкіншіліктерін зерттеу барысында студенттер индуктивты анықтамалардың спецификасымен танысады.

Атап айтсақ, базалық есептеулердегі (пікірлер есептеулері және предикаттар есептеулері) сөздердің синтаксистық құрылымының индуктивтық анализы (сөздердің реттілігі) бізге береді:

- аталмыш сөздің формула екендігін анықтау алгоритмін;

- аталмыш формуланың ішкі формулаларын жазу алгоритмін;

- соңғы формулалар тізімінің қорытынды тізім екендігін анықтау алгоритмін.

Аталған алгоритмдерді және соған ұқсас алгоритмдерді синтаксистік тұрғыдан зерттеудің мақсаты есептеуді жүргізетін үрдістердің бар болуын анықтау. Дәл осы кезде синтаксистық конструкцияның алгоритмдық мәні түсіндіріледі.

Алгоритм ұғымы бір типті есептерді шығарудың нақты шығару кезеңдері көрсетілетін және осы класстың кез-келген есебін есебін шығаруда қолданылатын нұсқаулықтар тізбегін айтады.

- алгоритм соңғы өлшемдері берілген нұсқаулар жиынтығы;

- нұсқаулықтарды қолдана білетін және есептеуді жүргізе алатын есептеуіш (әдетте адам);

- алгоритм шексіз класстың бір типті есептерін шығаруда қолданылады;

- есептеуші нұсқаулықтарды қадам ретімен дискретті уақытта жүргізеді;

- есептеудің басында шаманың алғашқы мәндері қолданылады, келесі қадамдарда бұған дейінгі қадамның нәтижесі негізінде анықталып орындалады;

- алғашқы шамалардың негізінде кейінгі шаманы алу қарапайым әрі түсінікті болып табылады және арнайы әдістер мен құрылғыларды қажет етпейді.

Сонымен қатар, алгоритм нұсқаулықтар жиынтығынан және есептеу қадамдары саны шексіз болғандықтан, алгоритм бір немесе бірнеше қадамдардың есептеу барысында көп рет қайталану (цикл) үрдісін сипаттайды. Есептеу үрдісін қадам ретінде ұйымдастыру үшін, алгортм неден басталатынын, бір қадамнан екінші қадамға өту қалай жүзеге асырылатыны және соңғы нәтиже қандай болатыны анық болу керек.

«::=»– белгісі «мүмкін осымен алмастырылады», «|»– «және» деп оқылады.

Алфавиттың символдары көп жағдайда терминальды символдар немесе терминалдар деп аталады және өзгертілмей жазылады. Басқа символдар арқылы анықталатын тілдік конструкцияның атауын (терминальды емес символдар немесе терминал емес) жазу барысында бұрышты жақшаға алыны жазылады («< », « >»). Мысалы, БНФ жазылған <Бүтін> конструкциясын жазу ережесі төмендегідей болуы мүмкін:

<Бүтін>::= <Белгі><Белгісі жоқ бүтін>│<Белгісі жоқ бүтін>

< Белгісі жоқ бүтін >::= < Белгісі жоқ бүтін ><Сан>│<Сан>

< Сан >::= 0│1│2│3│4│5│6│7│8│9

< Белгі >::= +│-

<Белгісі жоқ бүтін> конструкциясының кұрамында шексіз сандар болатындай көрсету үшін сол жақты рекурсия ережесі қолданылады. Бұл ережені қолдану нәтижесінде кез-келген цифр саны бар нақты санды алуға мүмкіндік береді.

Синтаксистық диаграммалар конструкцияларды құру ережелерінің көрнекті түрінде береді. Мұндай диаграммаларда алфавит символдар блогы овал рамкаларда, конструкциялар атауы тік төртбұрыштарда, конструкцияны құру ережелері – ұшында бағыты бар сызықтармен белгіленеді. Егер сызық блокқа бағытталған болса, онда аталып отырған конструкцияға сәкес символ енгізілу керек. Сызықтың тармақталуы басқа жағдайларды бар екенін білдіреді.

6.2-сурет <Бүтін> конструкциясының алғашқы екі ережесінің синтаксистық диаграммасы берілген. Диаграммада көріп отырғанымыздай бүтін сан белгі арқылы немесе белгісіз жазылуы мүмкін және шексіз цифрлардан тұруы мүмкін. Н.Вирт синтаксистық конструкцияны бейнелеуде осы синтаксистық диаграмманы қолданды, сондықтан конструкцияның мазмұны ұзақ әрі нақыт болмаса біз синтаксистық диаграмманы қолданатын боламыз.