Технологии и формы обучения Рекомендации по освоению дисциплины для студента

Трудоемкость освоения дисциплины составляет 102 часа, из них 68 часов аудиторных занятий и 34 часа, отведенных на самостоятельную работу студента.

Рекомендации по распределению учебного времени по видам самостоятельной работы и разделам дисциплины приведены в таблице.

Контроль освоения дисциплины осуществляется в соответствии с ПОЛОЖЕНИЕМ о проведении текущего контроля успеваемости и промежуточной аттестации студентов СПбГУ ИТМО (БаРС).

Формы контроля и критерии оценивания приведены в Приложениях 4 и 5 к Рабочей программе.

Вид работы	Содержание (перечень вопросов)	Трудоемкость, час.	Рекомендации
Раздел 1. Математическая логика
Подготовка к лекциям	Систематическое повторение ранее прочитанного теоретического материала	2	По конспекту лекций
Выполнение текущих домашних заданий	Решение задач.	4	По образцу разобранных на занятиях.
Выполнение типового расчёта, включая подготовку к его защите	Решение задач; оформление отчета.	8
Подготовка к контрольной работе	Решение задач.	4
Итого по разделу		18 часов
Раздел 2. Теория алгоритмов
Подготовка к лекциям	Систематическое повторение ранее прочитанного теоретического материала	2	По конспекту лекций
Выполнение текущих домашних заданий	Решение задач.	3	По образцу разобранных на занятиях.
Выполнение типового расчёта, включая подготовку к его защите	Решение задач; оформление отчета.	8
Подготовка к контрольной работе	Решение задач.	3
Итого по разделу		16 часов

Приложение 4 к рабочей программе дисциплины «Математическая логика и теория алгоритмов»

Оценочные средства и методики их применения Фонды оценочных средств

Образцы задач для домашних заданий

Образцы вопросов и задач для зачета

11. Что такое диаграмма Эйлера-Венна? Проиллюстрируйте с помощью диаграммы Эйлера-Венна объединение и пересечение трех множеств.

12. Сформулируйте и докажите основные тождества алгебры множеств.

13. Следующий опрос 100 студентов (см. задачу 4) выявил следующие данные о числе студентов, изучающих различные иностранные языки: только немецкий — 18; немецкий, но не испанский — 23; немецкий и французский — 8; немецкий — 26; французский — 48; французский и испанский — 8; никакого языка — 24.

а) Сколько студентов изучают испанский язык?

б) Сколько студентов изучают немецкий и испанский языки?

в) Сколько студентов изучают французский язык, в том и только в том случае, если они не изучают испанский?

14. Является ли отношение {{1,4); (2, 3); (3, 2); (4,1)}, заданное на декартовом квадрате множества А = {1, 2, 3, 4}, биективным отображением?

15. Пусть X — множество пальто в гардеробе, У — множество крючков. В каком случае отображение множества пальто X в множество крючков У будет инъективным, сюръективным, биективным?

16. Для каждого из следующих высказываний: 1) найдите символическую форму; 2) постройте таблицу истинности. Воспользуйтесь буквенными обозначениями: X для «Джо умен»; У для «Джим глуп»; Z для «Джо получит приз».

1. Если Джо умен, а Джим глуп, то Джо получит приз.

1. Джо получит приз в том и только в том случае, если он умен или если Джим глуп.

2. Если Джим глуп, а Джо не удастся получить приз, то Джо не умен.

17. Таблица истинности высказывания, составленного из двух простых высказываний, состоит из четырех строк; а таблица истинности высказывания, составленного из трех простых высказываний, — из восьми строк. Сколько строк должна иметь таблица истинности высказывания, составленного из четырех простых высказываний? Сколько — из пяти? Сколько — из п? Укажите способ систематической записи таблиц истинности для произвольного п?

18. Представить сложное высказывание "Для повышения производительности труда и улучшения качества продукции персоналу фирмы необходимо пройти переподготовку и соблюдать производственную дисциплину" в виде логической формулы.

19. Отношение R на множестве всех книг библиотеки определили следующим образом. Пара книг а и b принадлежат R, если и только если в этих книгах есть ссылка на одни и те же литературные источники. Является ли R

а) рефлексивным отношением;

б) симметричным отношением;

в) транзитивным отношением?

20. Саша дружит с Олей, Коля и Юра дружат с Машей. Саша учится с Олей в одной группе, а Коля учится в одной группе с Викой. Вика учится вместе с Юрой и дружит с ним. Ввести бинарное отношение Т1 "учиться вместе", а также Т2 "быть другом". Построить матрицу смежности для Т1 и Т2. Определить свойства этих бинарных отношений.

Перечень теоретических вопросов к промежуточной аттестации

1. Высказывания и логические операции над ними

2. Формулы логики высказываний и их классификация

3. Общезначимые формулы

4. Логическое следование

5. Равносильность формул

6. Нормальные формы для формул алгебры высказываний

7. Формализованное исчисление высказываний

8. Теорема о дедукции

9. Полнота, непротиворечивость и разрешимость исчисления высказываний

10. Предикаты и их классификация.

11. Логические и кванторные операции над предикатами

12. Формулы логики предикатов и их классификация

13. Равносильность и логическое следование формул логики предикатов

14. Формализованное исчисление предикатов

15. Классическая логика и клаузальная логика

16. Логическое программирование. Клаузы Хорна и метод резолюций

17. Модальная логика

18. Нечеткая логика

19. Темпоральная логика

20. Задачи и алгоритмы. Свойства алгоритма.

21. Машина Тьюринга

22. Рекурсивные функции

23. Нормальные алгоритмы Маркова

24. Алгоритмически неразрешимые проблемы

Образец контрольной работы

1. Докажите, что теория графов в сигнатуре без равенства неполна.

2. Может ли полная теория в сигнатуре с равенством иметь нормальную конечную модель и нормальную бесконечную модель?

3. Пусть Т – полная теория с равенством, имеющая конечную модель. Докажите, что Т не имеет бесконечных моделей.

4. Докажите, что не существует теории первого порядка в сигнатуре {+,,=,0,1}, моделями которой являются в точности все конечные поля. Аналогично -- для полей ненулевой характеристики.

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

В пьесе у каждого участника есть брат и сестра, также участвующие в этой пьесе. Никто не является своим собственным братом или сестрой. Брат не может быть сестрой. Значит, либо в этой пьесе нет вовсе действующих лиц, либо же их не меньше четырех.

6. Постройте формулу 1-го порядка без равенства, имеющую 3-элементную модель, но не имеющую 2-элементных моделей.

Образец заданий для типового расчёта

ТР №1

1. _{Записать булевы выражения А, В и С в стандартных обозначениях}

2. _{Проверить, эквивалентны ли А и В}

3. _{Привести В и С к КНФ и ДНФ}

4. _{Написать двойственное к С выражение в виде многочлена Жегалкина}

5. _{Указать, при каких значениях переменных В истинно}

6. _{Проверить А на линейность и монотонность}

7. _{Проверить, не являются ли А, В и С тавтологиями}

ТР №3

1. Нарисовать контактно-релейные схемы, соответствующие A,B,C

2. Упростить А и изобразить соответствующую упрощенную схему

3. Нарисовать схему для С, использующую только элементы "и-не"

Примеры вариантов тестовых заданий

Вариант 1.

1. Какое из следующих равенств с множествами А и В является ложным:

1) ; 2)(А В) С=А (В С); 3) Если , то А В= А; 4)А Ø= А.

2. Дизъюнкцией высказываний А и В (обозначение АВ, читается: А или В) называется высказывание:

1. истинное тогда, когда истинно хотя бы одно из высказываний А и В, и ложное, если и А и В ложны

2. ложное в случае, если А истинно, а В ложно, и истинное в остальных случаях

3. истинное тогда, когда истинны оба высказывания А и В, и ложное в остальных случаях

4. истинное тогда, когда оба высказывания А и В либо истинны, либо ложны, и ложное если одно из высказываний А, В истинно, а другое ложно

3. Квантор общности обозначается символом:

1)¬; 2)^; 3) ; 4)

4. Информационная ленты, считывающая и записывающая головка и управляющее устройство – это состав машины:

1)Черча; 2)Маркова; 3)Паскаля; 4)Тьюринга

5. Оператор минимизации обозначается:

1) J_n,m ; 2)  (x); 3) _y; 4)R(g⁽ⁿ⁾ ; h⁽ⁿ⁺²⁾)

21.Пусть g(х)=C_i(х)=0; h(х;у;f (х; у)) = J_3,2=y. Пользуясь схемой примитивной рекурсии найти f(3):

1)0; 2)1; 3)2; 4)5

Вариант 2.

1. Какое из следующих равенств с множествами А и В является ложным:

1) ; 2)(А В) С=А (В С); 3)Если , то А В= В; 4)А Ø= Ø;

2. Формула V  V представляет собой закон:

1)идемпотентности 3)ассоциативности

2)коммутативности 4)тавтологии

3. Неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов установил:

1)Черч; 2) Марков; 3) Паскаль; 4) Тьюринг

4. Функция следования обозначается:

1) J_n,m ; 2)  (x); 3) _y; 4)R(g⁽ⁿ⁾ ; h⁽ⁿ⁺²⁾)

5. Пусть g(x)=J_1,1=x; h (х; у; f (х; у)) =  (J_3,3) = f (x; у) + 1

Пользуясь схемой примитивной рекурсии найти f(3;6):

1)3; 2)6; 3)9; 4)12

Вариант 3.

1 . Какое из следующих равенств с множествами А и В является ложным:

1) ; 2) (А В) С=А (В С); 3) Если , то А В= А; 4)А Ø= Ø

2. Какое из следующих свойств логических операций является неверным:

1) (  А)  (А); 2) (  (АВ))  (АВ); 3)(  (АВ))  (АВ); 4) ((АВ)С)  (А(ВС))

3. К числу элементарных операций не относят операцию:

1)константы; 2)суперпозиции; 3)рекурсии; 4)минимизации

4. Пусть g(x) = I_1,1 = x; h (х; у; f (х; у)) = ^-1 (J_3,3) = f (x; у) – 1

Пользуясь схемой примитивной рекурсии найти f(6;3):

1)3; 2)6; 3)9; 4)12