Задание по математической логике и теории алгоритмов
Исчисление высказываний
1.1 Проверить является ли данное выражение формулой ИВ (2 б.).
1.2 Построить вывод формулы в ИВ (10 б.)
Варианты
1. (A®B)®((C®A)®(C®B))
2. (A®B)®((C®A)®(C®B))
3. (A®B)®((C®A)®( C®B))
4. (A®(B®C))® ((A®B)®(A®С))
5. ((A®B)®(A®С))®(A®(B®C))
6. (A®(B®С))®((A®B)®(A®C))
7. ((A®B)®(A®C))®(A®(B®С))
8. (A® (B®C))®((A®B)®C)
9. (A® (B®С))® ((A®B)®C)
10. (A®B)®((A®С)®(B®С))
11. (A®(B®C))®((A®B)®(A®С))
12. ((A®B)®(A®С))®(A®(B®C))
13. (A®(B®С))®((A®B)® (A®C))
14. ((A®B)®(A®C))®(A®(B®С))
15. (A®B)®((C®A)®(C®B))
16. (A®B)®((C®A)®(C®B))
17. (A®B)®((C®A)®( C®B))
18. (A®(B®C))® ((A®B)®(A®С))
19. ((A®B)®(A®С))®(A®(B®C))
20. (A®(B®С))®((A®B)®(A®C))
21. ((A®B)®(A®C))®(A®(B®С))
22. (A® (B®C))®((A®B)®C)
23. (A® (B®С))® ((A®B)®C)
24. (A®B)®((A®С)®(B®С))
25. (A®(B®C))®((A®B)®(A®С))
2.1 Записать рассуждение в логической символике (3 б.)
2.2 Проверить правильность рассуждения методом Куайна (3 б.).
2.3 Проверить правильность рассуждения методом редукции (3 б.)
2.4 Проверить правильность рассуждения методом резолюций (3 б.)
Варианты
1. Если подозреваемый совершил кражу, то либо кража была тщательно подготовлена, либо имелся соучастник. Если бы кража была тщательно подготовлена, то был бы соучастник. Значит, подозреваемый не виновен в краже.
2. Намеченная атака удастся, только если захватить противника врасплох или же если позиции его плохо защищены. Захватить его врасплох можно только, если его позиции плохо защищены. Значит, атака не удастся.
3. Если бы у нее было много денег, она бы ездила в институт на такси и тогда бы никогда не опаздывала. Она постоянно опаздывает. Значит, у нее по-прежнему мало денег.
4. Если бы он хорошо знал английский язык или хотя бы она говорила помедленней, то он бы ее понял. Но он ее не понял. Значит, она как всегда говорила слишком быстро.
5. Муравей поднимет соломинку, если ее вес не превышает собственный вес муравья более, чем в 10 раз. Муравей не будет поднимать соломинку, если она ему не нужна. Муравей не стал поднимать соломинку. Значит, либо соломинка слишком тяжелая, либо муравью не нужна соломинка.
6. Если человек обедает в кафе быстрого питания, то он голоден и куда-то торопится. Человек не обедает в кафе быстрого питания, хотя и очень торопится. Значит, он не голоден.
7. Незнание правил дорожного движения не освобождает от ответственности в случае их несоблюдения. При нарушении правил водитель несет ответственность.. Следовательно, знать правила нужно.
8. Если бы он ей не сказал, она бы не узнала. А не спроси она его, он бы и не сказал ей. Но она узнала. Значит, она его спросила.
9. Если у меня хватит времени прочитать книгу, то я пойду погулять или встречусь с друзьями. С друзьями я встречаюсь во время прогулки. Значит, я встречусь с друзьями.
10. Мне обязательно нужно сходить в магазин. Я хожу в магазин только тогда, когда я свободен. Когда я свободен, я предпочитаю отдыхать. Значит, я не пойду в магазин.
11. Если подозреваемый совершил кражу, то либо кража была тщательно подготовлена, либо имелся соучастник. Если бы кража была тщательно подготовлена, то был бы соучастник. Значит, подозреваемый не виновен в краже.
12. Намеченная атака удастся, только если захватить противника врасплох или же если он беспечен. Захватить его врасплох можно только, если он беспечен. Значит, атака не удастся.
13. Если бы у нее было много денег, она бы ездила в институт на такси и тогда бы никогда не опаздывала. Она постоянно опаздывает. Значит, у нее по-прежнему мало денег.
14. Если бы он хорошо знал английский язык или хотя бы она говорила помедленней, то он бы ее понял. Но он ее не понял. Значит, она как всегда говорила слишком быстро.
15. Муравей поднимет соломинку, если ее вес не превышает собственный вес муравья более, чем в 10 раз. Муравей не будет поднимать соломинку, если она ему не нужна. Муравей не стал поднимать соломинку. Значит, либо соломинка слишком тяжелая, либо муравью не нужна соломинка.
16. Если человек обедает в кафе быстрого питания, то он голоден и куда-то торопится. Человек не обедает в кафе быстрого питания, хотя и очень торопится. Значит, он не голоден.
17. Незнание правил дорожного движения не освобождает от ответственности в случае их несоблюдения. Для того, чтобы не нести ответственность нужно не нарушать правила. Следовательно, знать правила нужно.
18. Если бы он ей не сказал, она бы не узнала. А не спроси она его, он бы и не сказал ей. Но она узнала. Значит, она его спросила.
19. Если у меня хватит времени прочитать книгу, то я пойду погулять или встречусь с друзьями. С друзьями я встречаюсь во время прогулки. Значит, я встречусь с друзьями.
20. Мне обязательно нужно сходить в магазин. Я хожу в магазин только тогда, когда я свободен. Когда я свободен, я предпочитаю отдыхать. Значит, я не пойду в магазин.
21. Если подозреваемый совершил кражу, то либо кража была тщательно подготовлена, либо имелся соучастник. Если бы кража была тщательно подготовлена, то если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый не виновен.
22. Намеченная атака удастся, только если захватить противника врасплох. Захватить его врасплох можно только, если он беспечен. Значит, атака не удастся.
23. Если бы у нее было много денег, то она бы ездила в институт на такси и тогда бы никогда не опаздывала. У нее денег немного. Поэтому она постоянно опаздывает.
24. Если бы он хорошо знал английский язык или хотя бы она говорила помедленней, то он бы ее понял. Но он ее не понял. Значит, она как всегда говорила слишком быстро.
25. Муравей поднимет соломинку, если ее вес не превышает собственный вес муравья более, чем в 10 раз. Муравей не будет поднимать соломинку, если она ему не нужна. Муравей не стал поднимать соломинку. Значит, либо соломинка слишком тяжелая, либо муравью не нужна соломинка.
3.1 Придумать рассуждение (не менее трех гипотез) (8 б.)
3.2 Проверить рассуждение методом резолюций (3 б.)
Исчисление предикатов
4. Пусть W - множество людей. На множестве W заданы следующие предикаты:
E(x, y) = И Û x и y – один и тот же человек;
P(x, y) = ИÛx родитель y;
C(x, y) = И Ûx и y – супруги;
M(x) = И Ûx – мужчина;
W(x) = И Ûx – женщина.
4.1 С использованием этих предикатов записать формулу, выражающую заданную фразу (3 б.)
4.2 Проверить, что полученное выражение является формулой логики предикатов (3б.)
4.3 В записанной формуле указать свободные и связанные переменные (2 б.)
4.4 Выписать все возможные подформулы записанной формулы (2б).
Варианты
1. У каждого есть отец и мать.
2. У каждого есть бабушка
3. У каждого есть дедушка
4. x – прабабушка
5. x – прадедушка
6. x – деверь
7. x – шурин
8. x – кузен
9. x – кузина
10. x – золовка
11. x – тесть
12. x – теща
13. x – свекровь
14. x – свекор
15. x – зять
16. x – сноха
17. x – правнук
18. У некоторых людей есть братья
19. У некоторых людей есть сестры
20. Некоторые супруги бездетны
21. Некоторые супруги имеют детей
22. Некоторые супруги имеют детей только женского пола
23. Некоторые супруги имеют детей только мужского пола
24. x – двоюродная тетя
25. x – племянница
5.1 Привести формулу к предваренной форме (3 б.)
5.2 Проверить общезначимость формулы методом резолюций (5 б.)
Варианты
1. ($x"yA(x, y))&($x"yB(x, y))
2. ($x"yA(x, y))®($x"yB(x, y))
3. ($x"yA(x, y))Ú($x"yB(x, y))
4. ($x"yA(x, y))®("x$yB(x, y))
5. ($x"yQ(x, y))®("y$xQ(x, y))
6. ("x$yQ(x, y))®($y"xQ(x, y))
7. ("x$yQ(x, y))®(($yQ(x, y))ÚR(x, y))
8. "x$yQ(x, y)®(($y"xP(x, y))®Q(x, y))
9. ("xQ(x, y))®(($yQ(x, y))Ú($xR(x, y)))
10. "x$yQ(x, y)®(($yP(x, y))®("xQ(x, y)))
11. ($x"yA(x, y))Ú($x"yB(x, y))
12. ($x"yA(x, y))®Ø("x$yB(x, y))
13. Ø($x"yQ(x, y))®("y$xQ(x, y))
14. ("x$yQ(x, y))®Ø($y"xQ(x, y))
15. ("xQ(x, y))®(($yQ(x, y))Ú($xR(x, y)))
16. "x$yQ(x, y)®(($yP(x, y))®("xQ(x, y)))
17. ($x"yA(x, y))Ú($x"yB(x, y))
18. ($x"yA(x, y))®Ø("x$yB(x, y))
19. Ø($x"yQ(x, y))®("y$xR(x, y))
20. ("xQ(x, y))®(($yQ(x, y))Ú($xR(x, y)))
21. "x$yQ(x, y)®(($yP(x, y))®("xQ(x, y)))
22. ($x"yA(x, y))Ú($x"yB(x, y))
23. Ø($xA(x, y))®("x$yB(x, y))
24. ($x"yA(x, y))&($x"yB(x, y))
25. ($x"yA(x, y))®($x"yB(x, y))
6.1 Придумать рассуждение (не менее трех гипотез) (10 б.)
6.2 Проверить рассуждение методом резолюций (5 б.)
Теория алгоритмов
7.1 Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны лишь нули и единицы, при этом пустые ячейки содержат нули. (10б)
7.2 Проверить работу машины Тьюринга для конкретных значений x,y (2 б.).
7.3 Нарисовать граф, соответствующий построенной МТ. (2 б.)
1. q1 1x01y0Þ q0 1y01x0
2. q1 1x01y0Þ q0 1x+y 01x 0
q11x01yÞ | q0 1x, если y>x |
q0 0, если y£x |
3.
q11x01y0Þ | q0 1y, если x>2 |
q0 1x, если x£2 |
4.
5. q1 1x0Þ q0 1x01x01x
6. q1 1x01y0Þ q0 1x+y01y+20
q11x01yÞ | q0 1x, если x>y |
q0 1y, если x£y |
7.
q11x01y0Þ | q0 1y, если x четно |
q0 1x+2, если x нечетно |
8.
q11x01y0Þ | q0 1y, если y>2 |
q0 1x, если y£2 |
9.
10. q1 1xÞ q0 1y, y – целая часть x/3
q11x01y0Þ | q0 1y0, если x>y |
q0 0, если x£y |
11.
12. q1 1xÞ q0 1x+20101x+2
13. q1 1xÞ q0 1x+20101x-2
14. q1 1xÞ q0 1y, y – целая часть x/2
q11x01yÞ | q0 1y, если x>2 |
q0 1y+3, если x£2 |
15.
q11x01yÞ | q0 1x+y, если y>2 |
q0 1x, если y£2 |
16.
17. q1 1x01y0Þ q0 1y01x0
18. q1 1x01y0Þ q0 1x+y 01x 0
q11x01yÞ | q0 1x, если y>x |
q0 0, если y£x |
19.
q11x01y0Þ | q0 1y, если x>2 |
q0 1x, если x£2 |
20.
21. q1 1x0Þ q0 1x01x01x
22. q1 1x01y0Þ q0 1x+y01y+20
q11x01yÞ | q0 1x, если x>y |
q0 1y, если x£y |
23.
q11x01y0Þ | q0 1y, если x четно |
q0 1x+2, если x нечетно |
24.
q11x01y0Þ | q0 1y, если y>2 |
q0 1x, если y£2 |
25.
8.1 Показать примитивную рекурсивность функции f(x,y) (5 б.)
1. f(x, y)=xy+2+y
2. 
3. f(x, y)=x+|xy-x|
4. 
5. 
6. 
7. 
8. f(x, y)=(x+y) mod 2
9. 
10. f(x, y)=x+|y-x|
11.
12. 
13.
14.
15. f(x, y)=x+|xy-x|
16.
17.
18.
19. f(x, y)=x+|y-x|
20.
21.
22.
23.
24.
25.
