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

жүктеу 3,94 Mb.

бет	8/25
Дата	14.12.2017
өлшемі	3,94 Mb.
	#4102
түрі	Жұмыс бағдарламасы

1 ... 4 5 6 7 8 9 10 11 ... 25

4 Предикаттар алгебрасы

Формалды тілдер теориясында тілді грамматика көмегімен көрсетіге болады. Грамматиканы жиі Бэкус-Наур (БНҚФ) қалыпты формасы арқылы анықтайды. Осында барлық қажетті жалпы анықтамалар берілген.

Анықтама 1. Ʃ алфавиті – дербес бос емес жиыны. Біз тек соңғы алфавиттермен жұмыс жасайтын боламыз. Мұның мысалы ретінде орыс тілінің алфавиті, ағылшын тілінің алфавиті, сандар жиыны, пернетақтада бар барлық символар жиыны бола алады.

Анықтама 2. Ʃ алфавитінің символы деп кез кедген оның элементін атаймыз, ал алфавит тізбегі деп символдарының кез келген тізбегін атаймыз. Тізбектер деп жиі сөздерді, сөз тіркестерін және сөйлемдерін атайды. Бос тізбек арнайы символымен белгіленеді, ал Ʃ алфавит бойынша барлық тізбектердің жиынын Ʃдеп белгіленеді. Егер Ʃ ретінде бос орын символымен және тыныс белгілерімен толықтырылған орыс тілі алфавитінің әріптерінің жиынын алатын болсақ, онда Ʃ құрамында орыс тілінің барлық сөз тіркестері болады.

Анықтама 3. тізбегінің ұзындығы депоның құрамына кіретін барлық символдардың санын атайды.

Бұл тізбектің ұзындығы 0-ге тең болады, ал басқа кез келген алфавиттің қалған тізбектерінің ұзындығы оң болады.

Анықтама 4. Екі тізбектің конкатенациясының операциясы келесі түрде анықталған.
, болсын, онда

.
Тұтасу операциясы немесе қалғанын жазу операциясы деп те аталатын конкатенация операциясы келесі қасиеттерге ие.

Ұсыныс 1. Кез келген

,, және тізбектері үшін келесі теңдіктер әділетті:
,

Барлық анықтамаларға сүйенсек, Ʃ алфавиті бойынша тілдің формалды анықтамасын беруге болады.

Анықтама 5. тілі – бұл Ʃ тізбектерінің жиынының кез келген ішкі жиыны.

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

Анықтама 6. Ʃ - қандай да бір алфавит,

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

-сы бар бір ереже ден кем емес кездеседі, ал бастапқы метасимвол деп аталады.

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

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

Анықтама 8. грамматикасынан туындағантілі барлық терминалды шығарылатын тізбектердің жиыны деп аталады.

Грамматиканы беру үшін жиі Бэкус-Наур қарапайым формасы (БНҚФ) деп аталатын көрсетудің көрнекі формасын қолданады.

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

Мысал ретінде предикаттар тілінің қатаң анықтамасын береміз немесе басқаша айтқанда тілдің синтаксисін береміз.

Анықтама 9. Предикаттар жиыны – бұл келесі грамматикадан туындаған тіл.

		(1-ші ереже: ақиқат)
		(2-ші ереже: жалған)
		(3-ші ереже: идентификатор)
		(4-ші ереже: теріске шығару)
		(5- ші ереже: дизъюнкция)
		(6- ші ереже: шартты Немесе)
		(7- ші ереже: конъюнкция)
		(8- ші ереже: шарттыЖәне)
		(9- ші ереже: импликация)
	e	(10- ші ереже: эквиваленттілік)

Берілген грамматиканың жалғыз метасимволы болып табылады, ал

алфавиті, мұндағы логикалық типті айнымалы бағдарламалардың барлық мүмкін идентификаторларынан тұратын жиын.

Берілген грамматикадағы шығарылатын тізбектің мысалын келтірейік:

.
Бұл теңдеуінің предикат болып табылатынын білдіреді. Бұл предикаттың басқа шығысын оңай құруға болады:

идентификаторына және

мәніне

метасимволын ауыстыру тәртібінен айырықша предикаты үшін шығарудың басқа да бірнеше тізбектері де бар. Төменде қарастырылатын барлық тізбектердің эквивалентті екендігі айқын көрініс табуда. Эквивалентті тізбектердің жиынын 2-ші суретте көрсетілген берілген предикаттың шығыс ағашы беретіні туралы айтылады.

2-сурет – предикатының шығыс ағашы

Бүгінгі таңда көптеген математикалық теориялар дедуктивты түрде құрылады. Теорияның негізіне аксиома деп аталатын негізгі ұғымдардың жиынтығы алынады. Басқа ұғымдар негізгі ұғымдардың негізінде қалыптасады. Осындай теориялардың негізінде келесі мәселелер туындайды:

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

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

Әрбір логикалық есептеу төмендегідей сипатталады:

- символдар жиынтығымен немес алфавитімен;

- алфавиттің негізінде мағыналы пайымдаулардың немесе формулалардың ережелерімен;

- аксиомалар жүйесі деп аталатын белгілі бір формулалар жиынтығымен;

- ережелер жиынтығымен.

Алфавит және формулалар жиынтығы есептеулер тілін құрайды, ал формулалардың жасалуы есептеулер синтаксисын құрайды.

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

Логикалық есептеуді анықтаудың аксиомасы және ережелері формулалар жиынтығынан дәлелденетін формулаларды немесе теоремаларды анықтауға мүмкіндік береді. Оларға шығару ережелері арқылы алынған аксиомалар мен теориялар жатады.

Алгебра предикаты σ сигнатурасының формуласы:

σ сигнатурасын σ = σ₁Uσ₂бірігуі түрінде белгілейік, мұндағы σ₁ операциялар формулаларының жиынтығы, σ₂М предикатының бос емес символдар жиынтығы. σ₀ ішкі жиыны арқылы σ₁ жиынының нуль-арлы операцияларын белгілейік. Ол М жиынының кез-келген ішкі жиыны болуы мүмкін. Формуланы анықтау барысында белгі ретінде әр түрлі әріптер қолданылуы мүмкін (индекспен болуы да мүмкін): σ₀ жиынында a, d, c; σ₁ жиынында f, φ, ψ; σ₂жиынында p, q. Сонымен қатар, x, y, z, u, v әріптерімен белгіленген (индекспен болуы да мүмкін) М жиынынан алынған Х символдар жиынтығы,, v, ->, ┐, ,  логиклық операцияларының жиынтығы және қызметтік символдар, яғни жақшалар алынуы мүмкін. Осылайша, формуланы шығару алфавиті ретінде келесі жиын қолданылады:
Ҩ = σ U X U O
Операциялар мен предикаттарға нақты мысалдарда жалпыға бірдей белгілер+, , *, =, ≤ қолданылады.

жүктеу 3,94 Mb.

Достарыңызбен бөлісу:

1 ... 4 5 6 7 8 9 10 11 ... 25