4.4 Машина мысалдары
Мысал 1. Келесі Тьюринг машинасы унарлық санақ жүйесінде жазылған натурал сандарды қосады.
|
q1
|
q2
|
q3
|
|
|
|q1+1
|
q3-1
|
|q3-1
|
+
|
|q1+1
|
|
|
|
q2-1
|
|
q0+1
|
Мысал 2. Келесі Тьюринг машинасы унарлық санақ жүйесінде жазылған натурал сандарды екі есе көбейтеді.
|
q1
|
q2
|
q3
|
|
|
q1+1
|
|q2-1
|
|q3+1
|
|
|
|q3+1
|
|
|
q2-1
|
q0+1
|
|q2-1
|
Тақырып бойынша тесттер
1. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
2. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
3. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
4. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
5. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
6. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
КУРС БОЙЫНША ТестТЕР
1. Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
2. Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
3. формуланың рангін табыңыз:
7
6
5
4
4. – аймағында анықталған предикат болсын. Қандай шарт орындалса, Р тепе тең ақиқат предикат деп аталады?
IP=
IP=
LP=
5. – аймағында анықталған предикат болсын. Қандай шарт орындалса, Р тепе тең жалған предикат деп аталады?
LP=
IP=
LP=
6. Ықшамдаңыз:
7. Ықшамдаңыз:
y
х
8. Келтірілген ЖДНФ бойынша формуланың ЖКНФін табыңыз:
9. Келтірілген ЖКНФ бойынша формуланың ЖДНФін табыңыз:
10. Формуланың ақиқаттық кестесi бойынша оның ЖДНФ табыңыз:
-
x
|
y
|
F
|
0
0
1
1
|
0
1
0
1
|
0
0
0
1
|
11. Формуланың ақиқаттық кестесi бойынша оның ЖКНФ табыңыз:
-
x
|
y
|
F
|
0
0
1
1
|
0
1
0
1
|
0
1
1
0
|
12. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
13. Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= q1
-
|
q1
|
q2
|
q3
|
|
q2+1
|
q3+1
|
q1+1
|
|
q00
|
q0-1
|
q1-1
|
q0
q0
q0
q0
q0
14. формуланың жетілдірілген конъюнктивті нормал формасын табыңыз:
15. 0-ді Пирс функциясы арқылы өрнектеңіз:
16. Пирс функциясы арқылы өрнектеңіз:
17. Шеффер функциясы арқылы өрнектеңіз:
18. Шеффер функциясы арқылы өрнектеңіз:
19. x = 1, y = 1, z = 0 аргументтердің берілген мәндерінде және функциялардың мәндерін есептеңіз.
F = 1, G =1
F = 0, G = 0
F = 0, G = 1
F = 1, G = 0
20. x = 1, y = 1, z = 1 аргументтердің берілген мәндерінде және функциялардың мәндерін есептеңіз.
.F = 1, G = 0
F = 0, G = 1
F = 1, G = 1
F = 0, G = 0
ӘДЕБИЕТТЕР
Ершов Ю.Л., Палютин Е.А., «Математическая логика». М., Наука, 1979.
Жетпісов Қ., Түсіпов Ж.А., «Математикалық логика», Тараз, 2000.
Лавров И.А., Максимова Л.Л., «Задачи по теории множеств, математической статистике и теории алгоритмов». М., Наука, 1975.
Лихтарников Л.М., Сукачева Т.Г., «Математическая логика». СПб.: «Лань», 1998.
Мальцев А.И., «Алгоритмы и рекурсивные функции». М.: Наука, 1986.
Мендельсон Э., «Введение в математическую логику», М., 1976.
Достарыңызбен бөлісу: |
