Логика алгебрасы» тақырыбы бойынша тест сұрақтары

1. Логика дегеніміз:

A) Адам ойлау түрлері мен заңдылықтарын зерттейтін ғылым;

B) Ақпарат заңдылықтарын зерттейтін ғылым

C) Табиғат заңдылықтарын зерттейтін ғылым

D) Есептеу құрылғысын зерттейтін ғылым

E) Күрделі жүйелердегі басқару заңдылықтарын зерттейтін ғылым

2. Логика алгебрасы дегеніміз:

A) Адам интеллектілік қызметін машиналық үлгілеу мәселелерін зерттейтін бөлімі

B) Информатиканың мамандандырылған ақпараттық жүйелердің негізінде қалыптасатын ақпараттық технологиялардың белгілі бір түрін зерттейтін бөлімі

C) Әртүрлі күрделі жүйелердегі ақпарат ағындарын анализдеу, тиімділеу, құрылымдау, ақпаратты сақтау және іздеу мәселелерін зерттейтін бөлімі

D) Күрделі логикалық тұжырымдар құрылымын және алгебралық әдістерінің көмегімен олардың ақиқаттылығын орнату әдістерін зерттейтін математикалық логиканың бөлімі

E) Информатикадағы математиканың математикалық логика саласына негізделген бөлігі.

3. Логика алгебрасындағы негізгі ұғым _____ болып табылады:

A) Сөйлем

B) Пікір

C) Теорема

D) Есеп

E) Аксиома

4. Пікірлер ____ және ______ болып екі түрге бөлінеді:

A) Аралас және құрмалас

B) Позициялық және позициялық емес

C) Бірікккен және ажыратылған

D) Жай және күрделі

E) Қарапайым және күрделі

5. Логика алгебрасы формулаларында айнымалылар логикалық болып табылады және олар тек екі мәнді ғана қабылдайды –

A) 0 немесе 1

B) Қосылған немесе ажыратылған

C) "жалған" немесе "ақиқат"

D) ток бар немесе ток жоқ

E) магниттелген немесе магниттелмеген

6. Логикалық (бульдік) айнымалы _______екі мәнін ғана қабылдай алатын х шамасы:

A) х = {0,1}

B) х = {0,2}

C) х = {-1,1}

D) х = {0,+∞}

E) х = {-∞,+∞}

7. Егер пікір ақиқат болса, онда кез келген пікірді х символы арқылы белгілеуге және _____ болады:

A) х= 2

B) х= 0

C) х=- 1

D) х≠ 1

E) х= 1

8. Пікірабсолюттіақиқат болады, егер оған тиісті логикалық шама кез келген шарттарда _____ мәнін қабылдаса

A) х= 2

B) х = 1

C) х= 0

D) х=- 1

E) х≠ 1

9. Пікірабсолюттіжалған болады, егер оған тиісті логикалық шама кез келген шарттарда _____ мәнін қабылдаса

A) х = 1

B) х= 2

C) х= 0

D) х=- 1

E) х≠ 1

10. Бульдік амалдардың қайсысы дұрыс жазылған?

A) 1 "және" 1=1

B) 0 "және" 1=1

C) 1 "және" 0=1

D) 0 "және" 0=1

E) 0"және"1=0

11. Бульдік амалдардың қайсысы дұрыс жазылған?

A) 0 "және" 0=1

B) 1"немесе"0=1

C) 0 "және" 1=1

D) 1 "және" 1=0

E) 0"немесе"1=0

12. «Емес» жалғауы қандай амалға тең?

A) Логикалық көбейту

B) Логикалық қосу

C) Логикалық терістік

D) Логикалық бөлу

E) Логикалық азайту

13. Инверсия ақиқат болады, егер пікір _______ болса:

A) ақиқат

B) жалған

C) ақиқат та, жалған да

D) абсолютті ақиқат

E) дұрыс жауабы берілмеген

14. Инверсия жалған болады, егер пікір _______ болса:

A) жалған

B) ақиқат та, жалған да

C) ақиқат

D) абсолютті ақиқат

E) дұрыс жауабы берілмеген

15. «Және» жалғауы қандай амалға сәйкес келеді?

A) Логикалық көбейту

B) Логикалық қосу

C) Логикалық бөлу

D) Логикалық азайту

E) Логикалық терістік

16. «Немесе» жалғауы қандай амалға сәйкес келеді?

A) Логикалық көбейту

B) Логикалық терістік

C) Логикалық азайту

D) Логикалық қосу

E) Логикалық бөлу

17. Екі логикалық пікірдің конъюнкциясы сонда және тек қана сонда ақиқат деп аталады, егер пікірлердің екеуі де………………..

A) жалған болса

B) ақиқат болса

C) абсолютті жалған болса

D) ақиқат та, жалған да болса

E) дұрыс жауабы келтірілмеген

18. Екі логикалық пікірдің конъюнкциясы сонда және тек қана сонда жалған деп аталады, егер пікірлердің ………………..

A) Бірі немесе екеуі де ақиқат болса

B) Екеуі де ақиқат болса

C) Бірі немесе екеуі де жалған болса

D) Барлық жауаптар дұрыс

E) Дұрыс жауабы келтірілмеген

19. Импликация амалы қандай таңбамен белгіленеді?

A)

B)

C)

D)

E)

20. Теңбе-теңдік амалы қандай таңбамен белгіленеді?

A)

B)

C)

D)

E)

21. Конъюнкция амалы қандай таңбамен белгіленеді?

A)

B)

C)

D)

E)

22. Дизъюнкция амалы қандай таңбамен белгіленеді?

A) ;

B) ;

C) ;

D) ;

E) .

 

Дұрыс жауаптар коды

Сұрақ нөмірі
Жауабы	A	D	B	D	C	A	E	B	C	A	B
Сұрақ нөмірі
Жауабы	C	B	C	A	D	B	C	A	B	C	D

 

Тьюринг машинасы

 

Ағылшын математигі А. Тьюринг (1912-1954 ж.ж.) 1936 ж. ойлап тауып, ал 1937 ж. бір жұмысын жарыққа шығарды. Онда ол алгоритм түсінігін қазіргі кезде Тьюринг машинасыдеп аталатын абстракт есепші машинаның көмегімен нақтылаған. Әр Тьюринг машинасында келесі үш бөлік бар: 1) сыртқы есте сақтағыш; 2) санап жазатын құрал; 3) басқаратын құрал.

Сыртқы есте сақтағыш екі жағынанда шектелмеген және өзара бірдей ұяшықтарға бөлінген лента.

Санап жазатын құрал – аңық бір уақытта қандайда бір ұяшыққа қарсы орналасатың құрал.Басқаратын құрал санап жазатын құралға түсетін бұйрықтарды дайындайды.Сонымен қатар басқаратын құралға санап жазатын құралдан қарсы орналасқан ұяшықтын символы келіп түседі.

Конфигурациядеп ұяшықтардын символдар a_i1, a_i2,..., a_ir, тізбегінен ішкі күйдің q_j символынан және санап жазатын құралға сәйкес тұрған ұяшықтын k нөмерінен құрылған жиынды атаймыз. Бұл берілгендер машина сөзі түрінде былай жазылады a_i1, a_i2 ,..., a_ik-1, q_j, a_ik,..., a_ir.

Тъюринг машинасы орындайтын барлық бұйрықтарды оның бағдарламасыдеп атаймыз.

Тюринг машинасын алгоритмдік үрдістерді сипаттау формализациясымен танысу құралы ретінде қарастырамыз. Тюринг машинасы екі жағынанда шексіз ленталармен жұмыс жасайды. Лента ұяшықтарға бөлінген, олардың жиынтығы машина жадын құрайды. Жадтың әрбір ұяшығы машинаның сыртқы алфавитін құратын алдын-ала фиксерленген символдар жиынтығы ішінен тек бір ғана символды сақтай алады.

S_0,S_1, S_2..., сыртқы алфавит символдарының ішінде ерекше бір символ бар бұл бос ˆ белгісімен белгіленеді. ˆбелгілерінен тұратын жад ұяшығын бос ұяшық деп атайды. Шексіз лентада орналасатын жадтан басқа машинаның бас ұшы деп аталатын арнайы құрылғы бар. Бас ұшы лента бойын жағалай орын ауыстыра алады. Бас ұшы көмегімен машина шолып шыққан ұяшықтың ішіндегісін оқи алады.

Машинасы жұмысы жеке такті ретінде құрайды. Олардың жүрісі барысында бастапқы ақпараттың қандайда бір ақырлы ақпаратты түрлендірілуі жүзеге асады.

S0

S1

….

Si

….

Sn

1 сурет - Машина конфигурациясының сызбасы

Мұндағы машинаның ішкі күйі q_k дәл сол уақыттағы шолып шыққан және S_і символынан тұратын ұяшық астында орналасқан. Машина жұмысының әрбір тактісінде:

a) Жадының шолып шыққан ұяшығында S_і символын оқиды.

b) Жадының шолып шыққан ұяшығына S_і сыртқы алфавитінің қандай да бір символын жазады.

c) Бас ұшын бір ұяшыққа не оңға не солға жылжытады немесе сол орнында қалтырады.

d) Қандай да бір q_і ішкі күйге көшеді.

Тюринг машинасына мысал: Тюринг машинасы қарапайым болғанымен сөздердің әр түрлі түрлендірілуін орындай отыра әр түрлі алгоритмдерді жүзеге асырады.

Тапсырма 1.

Лентадағы санға бірді қосып отыратын Тюринг машинасын құру керек. Ішкі сөз бүтін ондық сандар цифрінен тұратын лентаның тізбектелген ұяшықтарында орналасқан. Бастапқы мезетте машина санның ең соңғы оң жағында цифріне қарсы орналасқан.

Шешімі: Машина санның соңғы цифріне 1-ді қосып отыру керек, егерде соңғы цифр 9-ға тең болса,онда оны 0-мен ауыстырып 1- ді оның алдындағы цифрге қосу керек. Мұндай цифрлар Тьюринг машинасына арналған кесте төмендегідей болуы мүмкін:

	S0						….
Q1	1Hq0	1Hq0	2Hq0	3Hq0	4Hq0	5Hq0	….	8Hq0	9Hq0	0Hq0

Бұл Тьюринг машинасында q₁- цикл күйінің өзгеруі, q₀ күйі тоқтату күйі. Егер автомат 0 – ден 8- ге дейінгі цифрларды көрсе онда оларды сәйкесінше 1 –ден 9 ға дейін өзгереді және q₀ күйге көшеді. Егер де оны 9 цифрін көрсе онда оны 0 - мен ауыстырып, q₁ күйінде қала отырып солға жылжиды. Бұл процессте автомат 9-дан кіші цифрді кездестіргенше жалғасады. Егер барлық цифрлар 9-ға тең болса, онда барлығы 0- мен ауыстырылады, сонымен үлкен цифрі орнына үлкен цифрді жаза отырып, солға жылжып бос ұяшыққа 1-ді жазады, содан соң q₀ күйге көшеді, яғни тоқтайды. Тюринг машинасын жазуды қысқарту, яғни тоқтату күйіне көшуді «!» белгісімен белгілейді. Ол мынадай түрге келеді:

	S0						….
Q1	1H!	1H!	2H!	3H!	4H!	5H!	….	8H!	9H!	0H!

Тьюринг тезисі алгоритмдер теориясындағы Тьюринг түрінде берілген негізгі гипотеза болып табылады. Бұл тезис алгоритмнің формальды анықтамасын беруге мүмкіндік береді.

Алан Тьюринг кез келген алгоритмнің осы сөздің интуитивті мағынада Тьюринг машинасының эквивалентті болу мүмкіндігін айтты. Әр компьютер Тьюринг машинасын құрай алады (ұяшықты қайта жазу операциясы, машина жағдайының өзгеруінің көршілес ұяшыққа өтуі немесе салыстырылуы). Оның алгоритмді кез келген тұрғыда қарай алуы, сондай-ақ компьютерлердің алгоритм тапсырмаларын шешу мүмкіндіктері эквиваленттер көзқарасының мақсатында қолданылады.

Черч тезисі. Алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы екенін дәлелдеу мүмкін емес. Оны не қабылдауға,не қабылдамауға болады. Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды Черч айтқан болатын. Ол екі тезисті ұсынды:

1- Черч тезисі. Есептеуге болатын функциялар жиыны Тьюринг машинасында есептелінетін функциялар жиынына тең.

2-Черч тезисі. Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.

Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол үшін алгоритмнің дәл анықтамасы керек. Бұл тезиске келіспеген математиктердің Тюринг машинасы есептемейтін алгоритм табуға тырысқан еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен келіспеген математиктер қалмады деуге болады.

Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес. Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды.

Енді Черч тезисінен шығатын бірнеше теоремаларға тоқтала кетейік.

Теорема 1. Жартылай рекурсивті функциялар жиыны саналымды.

Дәлелдеуі. Черч тезисі бойынша f(х) = k функциясы кез келген k үшін рекурсивті. Сондықтан, жартылай рекурсивті функциялар кем дегенде саналымды.

Анықтама. Кез келген мәнінде анықталған жартылай рекурсивті функция жалпы рекурсивті функция деп аталады.

Салдар. Жалпы рекурсивті функциялар саналымды.

Дәлелдеуі. f(х) = k функциясы кез келген k үшін анықталған. Сондықтан, олар кем дегенде саналымды. Екінші жағынан, жалпы рекурсивті функциялар жиыны жартылай рекурсивті функциялар жиынының ішкі жиыны болғандықтан саналымдыдан артық емес.