Математическая логика и теория алгоритмов

Контрольная работа

назад | оглавление | вперёд

 

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

При выполнении контрольной работы необходимо строго придерживаться указанных ниже правил. Работы, выполненные без соблюдения этих правил, не засчитываются и возвращаются студенту для переработки.

  1. Контрольную работу следует выполнять в редакторе Microsoft Word. Формулы следует набирать в специальном редакторе Microsoft Equation.

  2. На титульном листе должны быть ясно написаны фамилия студента, его инициалы, номер варианта, название дисциплины.

  3. В работу должны быть включены все задачи, указанные в задании, строго по своему варианту. Контрольная работа, содержащая не все задачи или задачи не своего варианта, не рассматривается.

  4. Решения задач необходимо располагать в порядке номеров, указанных в заданиях, сохраняя номера задач. Решение каждой задачи должно быть полным и максимально понятным.

  5. Перед решением каждой задачи необходимо выписать полностью ее условие. В том случае, если несколько задач, из которых студент выбирает задачу своего варианта, имеют общую формулировку, следует, при переписывании условия задачи, заменить общие данные конкретными из соответствующего номера.

  6. После получения прорецензированной работы, как незачтенной, студент должен исправить все отмеченные рецензентом ошибки и недочеты, выполнить все рекомендации и прислать для повторной проверки в короткий срок.

  7. Без выполненной контрольной работы студент к зачету не допускается.

ПРАВИЛА ВЫБОРА ВАРИАНТА
Вариант контрольной работы соответствует двум последним цифрам пароля. Будьте внимательны при выборе варианта.

Работа, выполненная не по своему варианту, возвращается без проверки!

Задание по математической логике и теории алгоритмов

Исчисление высказываний

1. Пользуясь определением формулы исчисления высказываний проверить является ли данное выражение формулой.

 

Варианты

1.       

2.     

3.       

4.     

5.     

6.     

7.     

8.     

9.     

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

21. 

22. 

23. 

24. 

25. 

 

2.  Записать рассуждение в логической символике и проверить правильность рассуждения  методом Куайна, методом редукции и методом резолюций.

 

Варианты

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.     

2.     

3.     

4.     

5.     

6.     

7.     

8.     

9.     

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

21. 

22. 

23. 

24. 

25. 

 

 

Теория алгоритмов

4 Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны нули и единицы, пустые ячейки содержат нули, .  Проверить работу машины Тьюринга для конкретных значений x,y. Нарисовать граф, соответствующий построенной МТ.

 

1.     

2.     

3.            

4.     

5.     

6.     

7.     

8.     

9.     

10. 

11. 

12.  , где  z  целая часть x/3

13. 

14. 

15. 

16.  , где  z   целая часть x/2

17. 

18. 

19. 

20. 

21. 

22. 

23. 

24. 

25. 

 

5  Показать примитивную рекурсивность функции f(x,y).

 

1.     

2.     

3.     

4.     

5.     

6.     

7.     

8.     

9.       (используется усеченная разность)

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

21. 

22. 

23. 

24. 

25. 

 


Список основной литературы
  1. Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов. - М. Горячая линия - Телеком, 2007.

  2. Треногин В.А. Дискретная математика: Учебник для вузов. Стандарт третьего поколения 2011

  3. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2001.

  4. Пономарев, В. Ф. Дискретная математика для инженеров. – М. : Горячая линия-Телеком, 2009.

  5. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.


Список дополнительной литературы
  1. Игошин В.И. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М. : Издательский центр «Академия», 2008. — 448 с.

  2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В. И. Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.

  3. Зарипова Э.Р. Лекции по дискретной математике. Математическая логика [Электронный ресурс]: учебное пособие/ Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А.— Электрон. текстовые данные.— М.: Российский университет дружбы народов, 2014.— 120 c.— Режим доступа: http://www.iprbookshop.ru/22190.— ЭБС «IPRbooks», по паролю

  4. Маньшин М.Е. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Маньшин М.Е.— Электрон. текстовые данные.— Волгоград: Волгоградский институт бизнеса, Вузовское образование, 2009.— 106 c.— Режим доступа: http://www.iprbookshop.ru/11334.— ЭБС «IPRbooks», по паролю

  5. Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 240 c.— Режим доступа: http://www.iprbookshop.ru/11947.— ЭБС «IPRbooks», по паролю

  6. Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов [Электронный ресурс]: учебное пособие/ Лавров И.А., Максимова Л.Л.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 256 c.— Режим доступа: http://www.iprbookshop.ru/12903.— ЭБС «IPRbooks», по паролю

  7. Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c.— Режим доступа: http://www.iprbookshop.ru/11948.— ЭБС «IPRbooks», по паролю


назад | оглавление | вперёд